Двойственность линейного программирования. Правила построения двойственных задач: 1. Если в исходной задаче целевая функция исследуется на min, то в двойственной. - презентация

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

2 Правила построения двойственных задач: 1. Если в исходной задаче целевая функция исследуется на min, то в двойственной задаче она будет исследоваться на max и наоборот. 2. Если в исходной задаче n переменных и m уравнений, то в двойственной задаче будет m переменных и n уравнений. 3. Коэффициенты целевой функции исходной задачи становятся правыми частями ограничений двойственной задачи, а правые части системы ограничений исходной задачи становятся коэффициентами целевой функции исходной задачи.

3 4. Матрица ограничений двойственной задачи получается из матрицы ограничений исходной задачи транспонированием. 5. Если в исходной задаче то в двойственной задаче k-ое ограничение будет неравенством, если же в исходной задаче ; если же в исходной задаче l -ое ограничение - равенство, то в двойственной задаче нет ограничений на знак y i. не имело ограничений на знак, то k -ое ограничение в двойственной задаче будет равенством. 6. Если в исходной задаче l -ое ограничение - неравенство, то в двойственной задаче

4 Пример построения двойственной задачи. Исходная задача A=A= Двойственная задача

5 Лемма 1 Если исходная задача (X) исследуется на max, а двойственная (Y) на min, то Лемма 2 Если, то – оптимальные планы. Теорема 1 (1 –ая теорема двойственности) Если одна из пары двойственных задач имеет оптимальные планы, то и другая имеет оптимальный план, причем : Z* max = Z* min Если же в одной из задач целевая функция не ограничена на ОДЗ, то у другой задачи вообще нет допустимых планов. Теорема 2 Планы x* и y* пары двойственной задачи являются оптимальными тогда и только тогда, когда выполняется:

6 Пара симметричных двойственных задач. Пары сопряженных переменных. Основные Дополнительные Дополнительные Основные

7 Экономический смысл двойственных задач об использовании ресурсов Задача I (исходная) Составить такой план выпуска продукции при котором прибыль (выручка) от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов.

8 , при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции Найти такой набор цен (оценок) ресурсов Задача II (двойственная)

9 Экономический смысл основной теоремы двойственности План производства и набор цен ресурсов оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная при внешних(известных заранее) ценах,равна затратам на ресурсы при внутренних (определяемым только из решения задачи) ценах Для всех других планов X и Y обеих задач прибыль (выручка) от продукции всегда меньше (или равна) затратам на ресурсы.

10

11 Компоненты оптимального решения двойственной задачи называются оптимальными двойственными оценками исходной задачи (скрытые доходы). Они определяют степень дефицитности ресурса.

12 Исследование на устойчивость Исследование на устойчивость – исследование диапазона изменения правых частей системы ограничений, при котором найденное оптимальное решение не изменяется. Исследование на чувствительность При исследовании на чувствительность исследуется зависимость решения ЗЛП от небольших изменений коэффициентов в условии задачи. При этом предыдущее решение может стать либо недопустимым, либо неоптимальным. К недопустимости пред. решения могут привести изменения запасов ресурсов и/или добавление новых ограничений. К неоптимальности пред. решения могут привести изменение целевой функции и/или изменение технологических коэффициентов и/или включение в модель нового вида производственной деятельности.