Тема 4. Двоїста задача лінійного програмування

Правила побудови двоїстої задачі лінійного програмування:

Кожній задачі лінійного програмування можна поставити у відповідність іншу, пов’язану певним чином з початковою задачею. Такі задачі називають двоїстими, або спряженими. Спільний розгляд двоїстих пар задач дуже важливий в економічному аналізі оптимального плану. Відповідність між вихідною та двоїстою задачами полягає в побудові на основі першої задачі двоїстої до неї /як вихідна може розглядатися будь-яка зі спряженої пари задач/. Двоїсті задачі бувають симетричні і несиметричні.

Симетричні задачі

Початкова задача Двоїста задача

/1.10/ /1.10а/

/1.11/ /1.11а/

/1.12/ /1.12а/

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

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

1. Кожному і - му обмеженню вихідної задачі відповідає змінна двоїстої задачі; і навпаки, кожному j - му обмеженню двоїстої задачі відповідає зміннавихідної задачі.

2. Якщо одна з пари двоїстих задач сформульована на максимум цільової функції, то друга - на мінімум і навпаки.

3. Обмеження-нерівності слід записувати зі знаком «» - при мінімізації цільової функції.

4. Коефіцієнти цільової функції однієї із задач є вільними членами системи обмежень другої задачі.

5. Матриці, складені з коефіцієнтів обмежень вихідної і двоїстої задач, є взаємно транспонованими.

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

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

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

Оптимальний розв’язок двоїстої задачі знаходять за даними останьої симплексної таблиці вихідної задачі за формулою

, де - матриця-рядок двоїстих змінних;

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

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

Зауважимо, що для оптимального плану вихідної задачі матриця утворюється в останній таблиці відповідно стовпцям одиничної матриці першої симплексної таблиці. Змінні оптимального плану двоїстої задачіможна також дістати в рядку (m+1) останньої симплексної таблиці, де містяться оцінкивихідної задачі. Змінні оптимального планудвоїстої задачі розміщуються під відповідними одиничними векторамив рядку (m+1), причому їх значення дорівнюють.

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

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

Наведемо формальний запис цієї теореми для задач /1.10/ - /1.12/ і /1.10а/ - /1.12а/.

Нехай дано оптимальний план вихідної задачі у вигляді .

Тоді маємо:

якщо , то;

якщо , то.

У разі, коли дано оптимальний план двоїстої задачі дістаємо:

якщо , то;

якщо , то.

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

або .

Приклад 1.1. Розв’язати двоїсту задачу, використовуючи розв’язок вихідної

Записуємо двоїсту задачу

Здобута пара задач несиметрична, оскільки обмеження вихідної задачі записані в канонічній формі. Отже, двоїсті змінні У - довільні /можуть бути як додатними, так і від’ємними або такими, що дорівнюють нулю/.

Задачі для самостійного розв’язання

Розв’язати задачу лінійного програмування, записати і розв’язати двоїсту до неї задачу.

1		2		3
4		5		6
7		8		9
10		11		12

Питання для самоконтролю

Економічний сенс задачі, спряженої до задачі планування обсягів виробництва.

За яких умов спряжені задачі називаються симетричними?

Якими правилами необхідно користуватися, формулюючи спряжену симетричну задачу?

Як пов’язані оптимальні розв’язки спряжених задач?

Як пов’язані змінні вихідної та спряженої задач?

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

Що стверджують основні теореми спряженості?