Асиметрични дуални задачи в линейното програмиране

Правилото за конструиране на двоен проблем

  1. Във всички ограничения на оригиналния проблем, свободните термини трябва да са от дясната страна, а термините с неизвестни отляво.
  2. Ограниченията на неравенството на първоначалния проблем трябва да бъдат написани така, че техните знаци за неравенство да сочат в една посока.
  3. Ако признаците на неравенства в първоначалния проблем са "≥", тогава целевата функция трябва максимизирайте, тези. Z (X) → max и ако "≤", тогава минимизиране.
  4. Всяко ограничение на оригиналния проблем съответства на неизвестното на дуалния проблем; така че неравенството ai1x1 + ai2x2 + ... + ainxn≤bi съответства на yi≥0 (i = 1,2 ..., m).
  5. Всяко неизвестно на първоначалния проблем съответства на ограничението на дуалния проблем. По този начин броят на неизвестните на единия проблем съответства на броя на ограниченията на другия.
  6. Матрицата на коефициентите на системата от ограничения на двойствения проблем е транспонираната матрица на коефициенти на системата на ограниченията на първоначалния проблем.
  7. Целевата функция на дуалния проблем има формата: F (Y) = b1y1 + b2y2 + ... + bmym, където y1, y2, ..., ym са неизвестни в двойствения проблем, b1, b2, ... bm са свободни термини в ограничения на първоначалния проблем.
  8. Целевата функция F (Y) на дуалния проблем трябва да бъде оптимизирана по обратния начин в сравнение със Z (X), т.е. ако Z (X) → max, тогава F (Y) → min и обратно.

В теорията на двойствеността се използват четири двойки двойствени задачи (представяме ги в матрична нотация):
Първоначален проблем Двоен проблем
Симетрични двойки

Y - всеки знак

Y - всеки знак

Решение: Нека намалим системата от ограничения до един знак за неравенство:
,
Провеждане на променливите на дуалния проблем

Умножаваме дясните страни на ограниченията със съответните променливи на дуалния проблем и ги добавяме, получаваме целевата функция, която е максимизирана, тъй като целевата функция на първоначалния проблем е сведена до минимум: F (Y) = - 10y1 + 6y2 + 12y3 → макс.
Умножаваме коефициентите на x1 по съответните променливи на дуалната задача и ги добавяме. Тази сума е по-малка или равна на коефициента при x1 в целевата функция –y1 + 2y2 + y3≤1. По същия начин се компилират още две ограничения за дуалния проблем.
Получава се двоен проблем, който образува симетрична двойка с оригинала:
F (Y) = - 10y1 + 6y2 + 12y3 → макс
yi ≥ 0; i = 1,2,3.