ТЕМА 5. ЕЛЕМЕНТИ ТЕОРІЇ ДВОЇСТОСТІ В ЛІНІЙНОМУ ПРОГРАМУВАННІ

5.1. Двоїстість та його роль в лінійному програмуванні.

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

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

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

5.2. Побудова моделі двоїстої задачі.

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

У формульному виді пару сполучених задач (пряму і двоїсту) можна представити таким чином:

 Пряма задача Двоїста задача

в стандартній формі

z=  ® max (min) w=  ® min (max)

 

Сформулюємо тепер правила побудови моделі двоїстої задачі:

1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі й навпаки: кожній змінній прямої задачі відповідає обмеження двоїстої.

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

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

4. Якщо пряма задача є задачею максимізації, то двоїста – задачею мінімізації, і всі її обмеження мають знак “£”. Навпаки: якщо пряма задача – задача мінімізації, то двоїста – задача максимизации, і усе її обмеження мають знак “³”.

5. У загальному випадку змінні двоїстої задачі не мають обмеження на знак.

Розглянемо наступний приклад.

Приклад 5.1. Задача лінійного програмування задана у вигляді:

z=5x1+12x2+4x3®max

 

Для подання ЗЛП у стандартній формі зведемо перше обмеження до рівності, вводячи залишкову змінну x4:

 

Побудуємо модель двоїстої задачі, застосовуючи вище згадані правила:

W=10y1+8y2®min

 

Розглянемо, як перетвориться модель двоїстої задачі, якщо модель прямої задачі буде містити штучні змінні, тобто мати наступний вигляд:

Z=5x1+12x2+4x3-Мx1-Mx2®max

 

Відповідна модель двоїстої задачі:

W=10y1+8y2®min

 

Обмеження y2³-M є надлишковим. Таким чином, не має значення, коли будувати модель двоїстої задачі: до або після введення штучних змінних у модель прямої задачі.

Приклад 5.2. Задача лінійного програмування задана наступною моделлю:

Z=5x1+6x2®min

 

Подамо дану задачу в стандартній формі:

z=5x¢1 -5x¢¢1+6x2®min

 

Побудуємо модель двоїстої задачі:

w=5y1+3y2+8y3 ® max

 

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

w=5y1+3y2+8y3 ® max