9. Поняття двоїстості (економічна постановка двоїстої задачі).

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

2. Коефіцієнти цільової функції прямої задачі c₁, з₂, ..., с_n стають вільними членами обмежень двоїстої задачі.

3. Вільні члени обмежень прямої задачі b₁, b₂, ..., b_m стають коефіцієнтами цільової функції двоїстої задачі.

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

5. Знаки нерівностей в обмеженнях змінюють на зворотні.

6. Число обмежень прямої задачі дорівнює числу змінних двоїстої задачі, а число обмежень двоїстої задачі дорівнює числу змінних прямої задачі.

В двойственных задачах переменные экономически можно интерпретировать как ценность ресурса, по ним можно определить либо ресурс дефицитный(если переменная > 0), либо недефицитный(если переменная = 0). Ограничения двойственной задачи экономически можно интерпретировать как суммарную оценку затрат на производство единицы продукции.

Як видно з прикладу, вирішення прямої задачі дає оптимальний план виготовлення виробів А і В, а вирішення двоїстої задачі – оптимальну систему оцінок сировини, використовуваної для виготовлення цих виробів.

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

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

Между переменными двойственных задач есть система следующих взаимосвязей:

1. Исходные переменные 1 задачи соответствуют добавочным переменным второй и наоборот

Первоначальные переменные исходной задачи Х1, Х2…Хn являются объемами производства продукции

Следовательно, добавочные переменные исходной задачи являются остатками ресурсов.

4) Исходные переменные двойственной задачи y1, y2..Ym являются ценностями ресурсов.

5) Добавочные переменные двойственной задачи являются превышением оценки затрат над ценой продукции:

Выразим добавочные переменные исходной задачи

10. Несиметричні та симетричні двоїсті задачі. Двоїсті пари задач лінійного програмування бувають симет­ричні та несиметричні.

У симетричних задачах обмеження прямої та двоїстої задач є нерівностями, а змінні обох задач можуть набувати лише не­від'ємних значень.

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

Різні можливі форми прямих задач лінійного програмуван­ня та відповідні їм варіанти моделей двоїстих задач наведено далі.

Пряма задача		Двоїста задача
	Симетричні
	Несиметричні