Лекции.Орг


Поиск:




Расширенная двойственная задача




Решение двойственной задачи приводим в виде симплекс-таблиц.

Расчётная таблица М (симплекс) метода. Двойственная задача. Нулевая итерация

   
  -2     -1 -1        
  -1     -2   -1      
Индексная строка -6М 3М-10 -3М+20 -2М+14 3М-14 М М      

Расчётная таблица М (симплекс) метода. Двойственная задача. Первая итерация

   
  -3/2   1/2   -1 1/2    
-20   -1/2   1/2 -1   -1/2    
Индексная строка -3М-20 3М/2   -6-М/2   М 10-М/2    

Расчётная таблица симплекс метода. Двойственная задача. Вторая итераци я

(план)      
-14   -3       -2   Двойственный симплекс метод
-20 -2       -1   -1
Индексная строка -44              
          -6   -6

 

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

Расчётная таблица симплекс метода. Двойственная задача. Третья итерация.

(план)    
 
-14   -3       -2  
    -1 -1     -1  
Индексная строка -56            

В индексной строке симплекс таблицы все критерии положительны. Планы также положительны. Следовательно, получен оптимальный план двойственной задачи. Переменные и не входят в базис. Все свободные переменные считаются нулевыми. Поэтому и равны нулю. =6, и =2. Балансовые переменные и .также являются свободными и равны нулю. Таким образом, оптимальный план двойственной задачи следующий: . Минимальное значение целевой функции =- =56.☻

 

Сравнение результатов решения исходной и двойственной задач

1. Если исходная задача имеет оптимальное решение, то и двойственная ей задача имеет оптимальное решение. Причём, максимум целевой функции совпадает с минимумом целевой функции .

2. В индексной строке оптимального решения двойственной задачи содержится оптимальное решение исходной задачи и наоборот. Например: =18= ; =6= ; =14= ; =0= .





Поделиться с друзьями:


Дата добавления: 2015-10-06; Мы поможем в написании ваших работ!; просмотров: 381 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Не будет большим злом, если студент впадет в заблуждение; если же ошибаются великие умы, мир дорого оплачивает их ошибки. © Никола Тесла
==> читать все изречения...

1014 - | 828 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.01 с.