ТЕМА 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
25 26 27 28 29 30 Наверх ↑