Теорія двоїстості в лінійному програмуванні

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

Побудуємо пару двоїстих задач.

Нехай задано задачу лінійного програмування: яку вважатимемо прямою задачею.

Двоїстою до неї буде така задача:

Правила побудови двоїстої задачі:

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

2. Обмеження в задачі на максимум повинні бути записані за допомогою і (або) =, а в задачі на мінімум — за допомогою і (або) =.

3. Кількість змінних однієї задачі має бути такою самою, як кількість нерівностей і рівнянь в системі обмежень іншої задачі.

4. Кожній нерівності системи обмежень однієї задачі повинна відповідати в іншій задачі невід’ємна змінна, а кожному рівнянню повинна відповідати змінна в іншій задачі, на знак якої не накладено обмежень.

5. Коефіцієнти цільової функції однієї задачі повинні бути правими частинами (вільними членами) системи обмежень іншої задачі.

6. Матриця системи обмежень однієї задачі повинна бути транспонованою матрицею системи обмежень іншої задачі.

Приклад 3. Скласти двоїсту задачу до задачі лінійного програмування

Розв’язання: Оскільки цільова функція прямує до максимуму, то всі знаки в системі обмежень мають бути або :

Кількість змінних двоїстої задачі дорівнює кількості обмежень прямої задачі за правилом 3, тобто в двоїстій задачі буду чотири змінних . Цільова функція двоїстої задачі повинна прямувати до мінімуму за правилом 1, за правилом 5 коефіцієнтами цільової функції є праві частини системи обмежень прямої задачі, таким чином маємо цільову функцію: . Складемо матрицю системи обмежень прямої задачі і за правилом 6 її транспонуємо:

.

Таким чином, враховуючи, що за правилом 2 в системі обмежень знаки повинні бути і (або) =. В системі обмежень двоїстої задачі друге обмеження буде рівністю за правилом 4, оскільки на другу змінну не було накладено умову невід’ємності:

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

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

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

Теорема (основна нерівність теорії двоїстості). Для будь-яких допустимих розв’язків прямої задачі і двоїстої , справедлива нерівність: .

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

Теорема (мала теорема двоїстості). Для існування оптимального розв’язку кожної із задач двоїстої пари необхідно і достатньо існування допустимого розв’язку кожної з цих задач.

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

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