Пара несиметричних двоїстих завдань
Пара двоїстих завдань може також бути несиметричною. Несиметрична пара двоїстих завдань задовольняє наступним умовам:
1. Матриці систем обмежень завдань транспоновані по відношенню один до одного.
2. Кожному обмеженню одного завдання відповідає змінна у другому завданні; при цьому змінна, що відповідає обмеженню-нерівності в одному завданні, задовольняє умові невід'ємності в іншій, а змінна, що відповідає обмеженню-рівності, може бути будь-якого знака.
3. Коефіцієнти при змінних у цільовій функції одного завдання є вільними членами відповідних обмежень іншого. У цьому вільні члени цільових функцій завдань збігаються.
4. Цільові функції задач оптимізуються протилежним чином, тобто якщо одне із завдань - на максимум, то друге - на мінімум, а якщо одне із завдань на мінімум, то друге - на максимум.
5. Якщо цільова функція задачі максимізується, то знаки нерівностей в обмеженнях задачі мають вигляд «£», а якщо мінімізується, то мають вигляд «³».
6. У всіх обмеженнях завдань вільні члени перебувають у правій частині, а члени зі змінними – у лівій.
Нарешті, умови 1 - 6 називаютьсяумовами двоїстості.
Таким чином, симетрична та несиметрична пари двоїстих завдань відрізняються лише 2-ою умовою.
Приклад 1. Скласти подвійні завдання:
а) 2x 1+2x 2-5x 3 ® max(min); б) 2x 1+2x 2-5x 3 ® min
Рішення. а) Спочатку складемо подвійну до завдання максимум (max). Подвійна – наступна:
Покажемо, що справді отримали подвійне завдання. Для цього покажемо, що для пари
2x 1+2x 2-5x 3 ®max 12y 1-2y 2+24y 3 ® min
задач виконано всі умови двоїстості.
1. Матриці систем обмежень завдань транспоновані по відношенню один до одного:
=.
2. У кожному завданні три обмеження і три змінні, тобто кожному обмеженню однієї задачі відповідає змінна в іншій задачі. При цьому всі змінні одного завдання відповідають обмеженням-нерівностей іншого, і тому задовольняють умови невід'ємності.
3. Коефіцієнти 2, 2, -5 при змінних цільової функції першої задачі є вільними членами відповідних обмежень другої і, навпаки, коефіцієнти 12, -2, 24 при змінних цільової функції другого завдання є вільними членами відповідних обмежень першої. У цьому вільні члени цільових функцій завдань збігаються (обидва рівні 0).
4. Цільові функції задач оптимізуються протилежним чином: вихідне завдання – на максимум, а друге – на мінімум.
5. Витримано вимоги до відповідності типу екстремуму цільової функції до типів нерівностей в обмеженнях: якщо цільова функція задачі максимізується, то знаки нерівностей в обмеженнях задачі мають вигляд «£», а якщо мінімізується, то мають вигляд «³».
Тепер складемо подвійну задачу на мінімум (min). Тоді вихідну необхідно переписати згідно з виглядом екстремуму цільової функції – мінімуму. Це означає, що всі нетривіальні нерівності у вихідному завданні повинні набути вигляду «³». Для цього достатньо ці нерівності помножити на -1:
Переконуємося в цьому так само, як і в попередньому випадку.
б) Подвійна - наступна:
Покажемо, що справді отримали подвійне завдання. Для цього покажемо, що для пари
2x 1+2x 2-5x 3 ®min 12y 1-2y 2+24y 3 ® max
задач виконано всі умови двоїстості.
1. Матриці систем обмежень завдань транспоновані по відношенню один до одного:
=
2. У кожному завданні три обмеження і три змінні, тобто кожному обмеженню однієї задачі відповідає змінна в іншій задачі. При цьому змінніx 1,x 2,x 3,y 1,y 2, що відповідають обмеженням-нерівностям в одному завданні, задовольняє умовам невід'ємності в іншому, а зміннаy 3, що відповідає обмеженню-рівності в першій, може бути будь-якого знака (на неї обмеження невід'ємності не накладається).
3. Коефіцієнти 2, 2, -5 при змінних цільової функції першої задачі є вільними членами відповідних обмежень другої і, навпаки, коефіцієнти 12, -2, 24 при змінних цільової функції другого завдання є вільними членами відповідних обмежень першої. У цьому вільні члени цільових функцій завдань збігаються (обидва рівні 0).
4. Цільові функції задач оптимізуються протилежним чином: вихідне завдання – на мінімум, а друге – на максимум.
5. Витримано вимоги до відповідності типу екстремуму цільової функції до типів нерівностей в обмеженнях: якщо цільова функція задачі максимізується, то знаки нерівностей в обмеженнях задачі мають вигляд «£», а якщо мінімізується, то мають вигляд «³».
У всіх обмеженнях завдань вільні члени перебувають у правій частині, а члени зі змінними – у лівій.