Лекции по линейному программированию
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

 

Перейдем теперь к построению задачи двойственной. В соответствии с правилами построения, она примет вид

Система ограничений:

Базис пространства переменных прямой задачи, в котором выполнены все ограничения двойственной задачи, будем называть Сопряженным базисом.

Введем следующие обозначения:

И в качестве сопряженного базиса возьмем, например, векторы Тогда из системы (см. систему ограничений двойственной задачи):

Найдем значение опорного плана двойственной задачи:

Становится очевидным, что данный базис не может быть взят в качестве сопряженного, так как при и второе ограничение системы не выполняется. Тогда, попробуем в качестве сопряженного базиса выбрать векторы Из системы:

Находим значения Неравенство

При этих значениях выполняется и, следовательно, система векторов в самом деле может рассматриваться в качестве сопряженного базиса двойственной задачи.

Далее, определим коэффициенты разложения небазисных векторов по векторам базиса и найдем псевдоплан исходной задачи:

Очевидно, что базисные векторы будут иметь вид

Так как среди компонент разложения вектора по сопряженному базису имеются отрицательные, то критерий оптимальности не выполнен, то есть указанный план не доставляет минимального значения функции и за счет перехода к новому базису ее значения можно еще уменьшить.

Заполняем первую таблицу  и приступаем к итерациям.

Таблица I.

№ 1

8

6

0

0

 

 

6

4

1

0

1

10

0

-18

0

1

-5

-39

8

6

0

0

 

-

0

0

Результат итераций будем записывать в таблицу II.

Таблица II.

№ 2

8

6

0

0

 

6

0

1

8

1

0

0

6

 

-

-

-

-

В столбце свободных членов (он выделен в таблице II) нет отрицательных элементов, следовательно, полученный план: - оптимален.

Количество операций, необходимое для одной итерации в симплекс-методе и двойственном симплекс-методе, соизмеримо. Однако, двойственный симплекс-метод целесообразно использовать при решении таких задач ЛП, в которых нахождение начального допустимого базисного решения затруднительно (например, приходится вводить искусственные переменные), а начальный псевдоплан определяется автоматически.

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство