ІІ теорема теорії подвійності.

Основна нерівність теорії подвійності.

Теорема про минимакс.

Якщо одна із задач лінійного програмування (ЗЛП) має оптимальний план, то й інша задача буде мати оптимальний план. Причому при оптимальних рішеннях значення цільових функцій будуть збігатися, тобто

.

Якщо ж в одній із задач цільова функція необмежена, то двоїста задача буде суперечлива (якщо система обмежень несумісна). Якщо ж, нарешті, пряма задача суперечлива, то для двоїстої буде виконуватися альтернатива, або двоїста задача буде також суперечлива, або її цільова функція буде необмежена.

Розглянемо деякі приклади складання пари взаємо-двоїстих задач

Розглянемо пару взаємо-симетричних двоїстих задач

(56)

(57)

(58)

(59)

(60)

(61)

Нехай деякий вектор є деяким припустимим планом прямої задачі, а є деякий припустимий план двоїстої задачі. Помножимо кожне обмеження системи (57) на відповідну йому двоїсту змінну, а кожне обмеження системи (60) - на відповідну йому змінну прямої задачі. При цьому маємо

(62)

(63)

Після процедури додавання обмежень (62) маємо

(64)

( – цільова функція двоїстої задачі)

Реалізуючи аналогічну операцію для обмежень (63) маємо

(65)

Об'єднаємо нерівність (64) і (65) в одна єдину здвоєну нерівність

(66)

Нерівність (66) - основна нерівність теорії подвійності. З такої нерівності виходить:

1. При будь-яких припустимих планах max цільової функції прямої задачі не перевищує min цільової функції двоїстої задачі.

2. Якщо значення max цільової функції прямої задачі буде відповідати значенню min цільової функції двоїстої задачі, то основна нерівність теорії подвійності перетворюється в рівність.

Виявляється, що цей факт є необхідною умовою існування оптимальної пари взаємо-двоїстих задач.