Сформулировать и доказать малую теорему двойственности.
МАЛАЯ ТЕОРЕМА ДВОЙСТВЕННОСТИ. Для существования оптимального решения любой из задач двойственной пары необходимо и достаточно существование допустимого решения для каждой из них.
Поскольку для любого допустимого решения х прямой задачи согласно т неравенству 
, а по усл. 
, то для любого допустимого х 
, т.е. 
- оптимальное решение прямой задачи. Точно так же 
, но , откуда 
, поэтому 
- оптимальное решение
Сформулировать и доказать первую основную теорему двойственности. В чем состоит экономическое содержание первой основной теоремы двойственности?
Если одна из двойственных задач имеет оптимальное решение, то двойственная ей задача также имеет оптимальное решение, причем экстремумы целевых функций равны, т.е. 
.
Если одна из двойственных задач не имеет оптимального решения, то другая задача также не имеет оптимального решения, причем если одна из задач не имеет оптимального решения из-за неограниченности целевой функции, то другая из-за несовместности системы ограничений.
Д-во: Пусть существует оптимальное решение х* прямой задачи, тогда оптимальное базисное решение расширенной задачи лп существует и имеет вид:
Где B* - оптимальная базисная матрица.
Оптимальное значение функции цели расширенной задачи равно
. Но поскольку коэффициенты функции цели при дополнительных переменных расширенной задачи равны нулю, то это значение является одновременно и оптимальным значением целевой функции первоначальной задачи : 
|
|
|
Докажем теперь, что существует оптимальное решение двойственной задачи P*/ Для этого докажем что решение двойственной задачи 
допустимо, а затем то, что оно оптимально. В самом деле, поскольку решение 
оптимальное базисное решение расширенной задачи, то для него все симплекс-разности неположительны 
. Но поскольку то 
. В первоначальной нумерации матрица неА и цены неС расширенной задачи имеют следующую структуру: неА=(А,Em) неС=(с,0). В соответствии с данной структурой неравенства разделяются на 2 части: 
И 
, поэтому Ро допустимое решение двойственной задачи. Кроме того, в соответствии с 
, поэтому согласно теореме о достаточном условии оптимельности решений пары двойственных задач лп Po является оптимельным решением. Пусть теперь целевая функция прямой задачи не ограничена. Предположим, что двойственная задача имеет допустимое решение Р тогда по основному неравенству теории двойственности значения функции цели для всех допустимых решений прямой задачи были бы ограничены сверху величиной рb, но это противоречит тому. Что ф-я цели не ограничена, поэтому двойственная задача не имеет решения.
|
|
|
Экономическое содержаниепервой основной теоремы двойственности ЛП таково. В терминах оценок она может быть сформулирована следующим образом: если задача определения оптимального плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения минимальных оценок ресурсов, причем цена продукта, полученного реализацией оптимального плана, совпадает с суммарной оценкой имеющихся ресурсов.
Дата добавления: 2018-06-01; просмотров: 463; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!