Основні теореми двоїстості

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

Перша теорема двоїстості. Якщо одна з пари двоїстих задач має оптимальний план, то інша задача також має оптимальний розв’язок, причому значення цільових функцій для оптимальних планів дорівнюють одне одному, тобто maxZ = minZ^*, і навпаки.

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

Якщо одна з пари не має розв’язку, то цільова функція другої задачі або необмежена, або також не має розв’язку.

Якщо пряма задача лінійного програмування має оптимальний план Х_опт, знайдений симплекс-методом, то оптимальний план Y_onm двоїстої задачі визначається за формулою:

де с_баз - вектор-рядок, який складається з коефіцієнтів при невідомих цільової функції прямої задачі, що є базисними в оптимальному плані; - матриця, обернена до матриці D, що складається з базисних векторів оптимального плану, компоненти яких узято з початкового опорного плану задачі. Обернена матриця завжди знаходиться в останній симплекс-таблиці задачі в тих стовпчиках, де в першій таблиці знаходилась одинична матриця.

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

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

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

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