p>
Отже, за лемою 3.2 (Достатньо Умова оптімальності планом задачі лінійного програмування) план є оптимальним планом двоїстої задачі (3.4) - (3.6).
Аналогічно доводитися, что коли двоїста задача має розв'язок, то початкова такоже має розв'язок и віконується Рівність:.
Для доведення Другої Частини теореми допустимо, что лінійна функція початкової задачі Необмежена зверху. Тоді з нерівності маємо, что, что НЕ має змісту. Отже, двоїста задача в даним разі НЕ має розв'язків. Доведена теорема Дає змогу в процесі розв'язування однієї задачі водночас знаходіті план Другої.
Економічний Зміст Першої теореми двоїстості . Максимальний прибуток ( Fmax ) предприятие отрімує за умови виробництво продукції згідно з оптимальним планом, однак таку саму торбу грошів () воно может мати, реалізувавші ресурси за оптимальними ценам. За умів Використання других планів на підставі ОСНОВНОЇ нерівності Теорії двоїстості можна стверджуваті, что прибутки від реалізації ПРОДУКЦІЇ всегда Менші, чем витрати на ее виробництво.
3.2 Друга теорема двоїстості
Між розв'язки спряжених задач крім рівності значень цільовіх функцій існує тіснішій Взаємозв'язок. Для его Дослідження розглянемо Дві сіметрічні задачі лінійного програмування.
Пряма задача:
В
(3.20)
.
Двоїста задача
В
(3.21)
В
Для розв'язування задач симплексним методом звітність, звесті їх доканонічної форми, для чого в системі обмежень завдань (3.20) і (3.21) звітність, ввести відповідно m та n невід'ємніх змінніх. Поставімо обмеженності кожної задачі у відповідність змінні ее двоїстої задачі.
В В
отримай таку відповідність между зміннімі спряжених задач:
Следующая теорема в літературі, як правило, має Назву теореми про доповнюючу нежорсткість.
Теорема ( одного теорема двоїстості для симетричний завдань ) . Для того, щоб плани X * та Y * відповідніх спряжених задач були оптимальними, звітність, и Достатньо, щоб віконуваліся умови доповнюючої нежорсткості:
(3.22)
. (3.23)
В
Доведення . Необхідність . Нехай X * та Y * - оптімальні плани відповідно прямої та двоїстої задач (3.20) i (3.21). З Першої теореми двоїстості відомо, что
,
а такоже компоненти векторів X * та Y * задовольняють системи обмежень задач (3.20) та (3.21), тоб:
, (3.24)
. (3.25)
Помножімо (3.24) на, а (3.25) - на і підсумуємо праві та ліві Частини. Отрімаємо:
;
В
Праві Частини останніх двох нерівностей НЕ збігаються, альо оскількі їх ліві Частини однакові, те це означає, что разом смороду віконуються позбав за умови рівностей, тоб:
;
В
Виконаємо Перетворення для шкірного рівняння:
; (3.26)
. (3.27)
Оскількі, то в рівнянні (3.26) Кожна з компонент, а, того Виконання рівняння (3.26) можливе позбав у тому разі, коли Кожний доданок увазі. Аналогічне міркування проведемо для (3.27), после чего можна вісновуваті, що.
Достатність . За умів віконуються рівняння
,
,.
звітність, довести, что X * та Y * - оптімальні плани відповідно прямої (3.20) та двоїстої (3.21) завдань. У шкірному рівнянні розкріємо дужки та підсумуємо перше рівняння по, а друге - по. Отрімаємо:
;
.
Ліві Частини ціх рівнянь однакові, отже,. Тоді за дерло теореми двоїстості, оскількі Значення цільовіх функцій ціх завдань збігаються, можна вісновуваті, что X * та Y * - оптімальні плани спряжених симетричний завдань. Теорему доведено. p> Очевіднішій Взаємозв'язок между оптимальними планами прямої та двоїстої задач встановлює наслідок Другої теореми двоїстості.
Наслідок . Если в результаті підстановкі оптимального планом однієї Із завдань (прямої чи двоїстої) в систему обмежень цієї задачі і- ті обмеження віконується як строга нерівність, те відповідна и -та компонента оптимального плану спряженої задачі дорівнює нулю.
Если и -та компонента оптимального плану однієї Із завдань додатного, то відповідне и -ті обмеження спряженої задачі віконується для оптимального плану як рівняння.
Економічний Зміст Другої теореми двоїстості Стосовно оптимального плану Х * прямої задачі . Если для виготовлення всієї продукції В обсязі, что візначається оптимального плану Х * , витрати одного і- го ресурсу суворо Менші...
