Линейное программирование. Некоторые примеры экономических задач, приводящих к модели линейного программирования. Геометрическая интерпретация и графическое решение задачи ЛП, страница 15

                                                      

                                                       .

В начальной таблице   с базисными  переменными  , u  целевую функцию Н надо выразить через свободные переменные       Решение вспомогательной задачи заканчивается на таблице 

                  

     Здесь   перестраиваем в начальную таблицу    для   исходной   зада-

чи – вычеркиваем строку  Н и столбец u  и находим выражение F  через  свободные переменные 

                 

Затем записываем   следующая таблица   уже удовлетворяет  условию  оптимальности .

                      

     Обратите внимание на «неправильный» выбор разрешающего столбца в  , что было бы при  «правильном»?  В    как  и  в  примере 10,  внутренние  элементы

не  вычисляются.

     Ответ:   .

     Пример 13. Решить задачу ЛП

                                                

                                                         

                                                         

                                                       

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

	Так как    строка Н  получается просто сложением строк     с пос- ледующим  изменением знака:   и т.д. Далее симплекс-методом получаем

 

                

В    решение вспомогательной  задачи закончено, 

     Ответ: в задаче нет допустимых планов, она не имеет решения.

Заметим, что противоречивость  ограничений можно обнаружить, вычитая из удвоенного 1-го уравнения2-е. Получим  что противоречит 

     Пример 14. Решить задачу ЛП

                                                         

                                                        

                                                            

                                                           

                                                                

      Решение. Задача имеет каноническую форму ,  можно использовать как начальную базисную, искусственные переменные   вводим  только во второе и третье уравнения.

             

                   

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

         

     Начальная таблица   уже удовлетворяет  условию оптимальности.

     Ответ:      

Упражнения

     17. Найти с помощью вспомогательной  задачи начальную симплексную  таблицу и решить симплекс–методом следующие задачи ЛП:

     а)   с ограничениями      

     

     б)    с ограничениями     

  

     в)

          

          

          

           

     

                       

6. Двойственность в линейном программировании

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

     Двойственной к стандартной  задаче (14) – (16) называется задача ЛП от m переменных   вида

                                                                     (31)

                                                                                 (32)

                                                                                                (33)

Связь между условиями прямой задачи (14) – (16) и двойственной (31) – (33) показана схематически в таблице 5:

                                                                                                                           Таблица 5