Елементи теорії подвійності

Фундаментальне значення в дослідженнях операцій, а також її додатках має теорія подвійності, основні положення якої розробив Л. В. Канторович. У рамках цієї теорії виникає питання оцінок оптимального плану, які використаються в економічному аналізі задач найкращого використання сировини. Необхідно відзначити, що теорія подвійності служить джерелом для розробки інших ефективних обчислювальних процедур.

Розглянемо задачу, що приводить до двоїстої. Задача про використання сировини.

Задача. Деяке підприємство освоїло випуск 2-х видів виробів Р₁ і Р₂. При цьому використовується 4 види сировини S₁, S₂, S₃, S₄. Запаси сировини й норма їх витрат представлені в наступному виді

	Р1	Р2	Зап.
S1
S2
S3
S4
Приб.

Сформулюємо задачу математично. Позначимо через х₁ і х₂ кількість виробів відповідно виду Р₁ і Р₂, що повинне виготовити підприємство для одержання максимального прибутку. Математична модель задачі:

(50)

(51)

(52)

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

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

(53)

у – ціна за одиницю ресурсу

(54)

(55)

При цьому тут задача (50-52) називається прямою задачею, а задача (53–55) називається двоїстою задачею. Між прямою і двоїстою задачами встановлюються наступні відповідності:

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

2. У прямій задачі всі обмеження-нерівності мають характер - «», у двоїстої такі обмеження мають характер - «».

3. Число змінних однієї задачі відповідає числу обмежень іншої задачі (і навпаки).

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

– Матриця коефіцієнтів при невідомих

5. Стовпець вільних членів однієї із задач відповідає коефіцієнтам при невідомих цільовий функції іншої задачі.

Пара задач зв'язана між собою зазначеними особливостями називається парою взаємо-двоїстих задач. Для пари взаємо-двоїстих задач справедливий принцип взаємної подвійності: усяка ЗЛП – є двоїстою стосовно своєї двоїстої задачі.

Відзначимо, що в задачах (50–52), (53–55) одна з них орієнтована на opt max, інша – на opt min. Всі обмеження однієї й іншої мають характер нерівностей. Крім того, на всі змінні, як однієї, так і іншої задачі, накладаються умови невід’ємності. Тоді така пара двоїстих задач називається симетричною парою.

Дата добавления: 2014-12-07