Зв’язок між розв’язками прямої та двоїстої задач

Розглянемо пару двоїстих задач, створену основною задачею ЛП і двоїстою до неї.

Початкова задача:

, (46)

за умов

(); (47)

,(). (48)

Двоїста задача:

, (49)

за умов

(). (50)

Між розв’язками прямої та двоїстої задач існує зв’язок, якій характеризується сформульованими нижче лемами та теоремами.

Лема 1. Якщо – деякий план початкової задачі (46)-(48), а – будь-який план двоїстої задачі (49), (50), то значення цільової функції початкової задачі при плані завжди не перевищує значення двоїстої задачі при плані , тобто .

Лема 2. Якщо для деяких планів та задач (46)-(48) та (49), (50), то – оптимальний план початкової задачі, а – оптимальний план двоїстої задачі.

Теорема 9. (перша теорема двоїстості). Якщо одна з пари двоїстих задач (46)-(48) або (40), (41) має оптимальний план, то і друга має оптимальний і значення цільових функцій задач при оптимальних планах рівні між собою, тобто .

Якщо ж цільова функція для однієї з пар двоїстих задач не обмежена (для початкової (46)-(48) – зверху, для двоїстої (49), (50) – знизу), то друга задача взагалі не має планів.

Теорема 10. (друга теорема двоїстості). План задачі (46)-(48) та план задачі (49), (50) є оптимальними планами задач тоді і тільки тоді, коли для , () виконується рівняння .

Дата добавления: 2014-01-13