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

 

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

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

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

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

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

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

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

 

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

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

Z=  max (min) w=  min (max)

 

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

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

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

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

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

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

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

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

Z=5x1+12x2+4x3max

 

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

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

W=10y1+8y2min

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

Z=5x1+12x2+4x3-Мx1-Mx2max

 

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

W=10y1+8y2min

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

 

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

Z=5x1+6x2min

 

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

Z=5x1 -5x1+6x2min

 

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

W=5y1+3y2+8y3  max

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

W=5y1+3y2+8y3  max

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 
25 26 27 28 29  Наверх ↑