Несиметричні двоїсті завдання

Правило побудови двоїстої задачі

У всіх обмеженнях вихідного завдання вільні члени повинні бути у правій частині, а члени з невідомими – у лівій.
Обмеження-нерівності вихідної задачі мають бути записані так, щоб знаки нерівностей у них були спрямовані в один бік.
Якщо знаки нерівностей у вихідному завданні «≥», цільова функція повиннамаксимізуватися, тобто. Z(X)→ max, а якщо «≤», томінімізуватися.
Кожному обмеженню вихідного завдання відповідає невідоме двоїсте завдання; так нерівності ai1x1+ai2x2+…+ainxn≤bi відповідає yi≥0 (i=1,2…,m).
Кожному невідомому вихідного завдання відповідає обмеження двоїстої задачі. Таким чином, кількість невідомих одного завдання відповідає числу обмежень іншого.
Матриця коефіцієнтів системи обмежень двоїстої задачі є транспонована матриця коефіцієнтів системи обмежень вихідної задачі.
Цільова функція двоїстої задачі має вигляд: F(Y) = b1y1 + b2y2 + ... + bmym, де y1, y2, ..., ym - невідомі в двоїстої задачі, b1, b2, ... bm - вільні члени в обмеження вихідного завдання.
Цільова функція F(Y) двоїстої задачі повинна оптимізуватися протилежним чином порівняно з Z(X), тобто. якщо Z(X)→max, то F(Y)→min і навпаки.

У теорії двоїстості використовуються чотири пари двоїстих завдань (наведемо їх у матричній формі запису):Вихідна задача Подвійна задачаСиметричні пари

Y – будь-якого знаку

Рішення: Наведемо систему обмежень до одного знаку нерівностей: , Ведемо змінні двоїстої задачі Помножимо праві частини обмежень на відповідні змінні двоїстої задачі та складемо їх, отримаємо цільову функцію, яка максимізується, оскільки цільова функція вихідної задачі мінімізувалася: F(Y)=-10y1+6y2+12y3→max. Помножуємо коефіцієнти при x1 на відповідні змінні двоїстої задачі і складаємо їх. Ця сума менша або дорівнює коефіцієнту при x1 у цільовій функції –y1+2y2+y3≤1. Аналогічно складаються ще два обмеження двоїстої задачі. Отримано двоїсте завдання, що становить вихідну симетричну пару: F(Y)=-10y1+6y2+12y3→max yi ≥ 0; i = 1,2,3.