Асиметрични дуални задачи в линейното програмиране
Правилото за конструиране на двоен проблем
- Във всички ограничения на оригиналния проблем, свободните термини трябва да са от дясната страна, а термините с неизвестни отляво.
- Ограниченията на неравенството на първоначалния проблем трябва да бъдат написани така, че техните знаци за неравенство да сочат в една посока.
- Ако признаците на неравенства в първоначалния проблем са "≥", тогава целевата функция трябва максимизирайте, тези. 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 - всеки знак
Y - всеки знак
Решение: Нека намалим системата от ограничения до един знак за неравенство:
,
Провеждане на променливите на дуалния проблем
Умножаваме дясните страни на ограниченията със съответните променливи на дуалния проблем и ги добавяме, получаваме целевата функция, която е максимизирана, тъй като целевата функция на първоначалния проблем е сведена до минимум: F (Y) = - 10y1 + 6y2 + 12y3 → макс.
Умножаваме коефициентите на x1 по съответните променливи на дуалната задача и ги добавяме. Тази сума е по-малка или равна на коефициента при x1 в целевата функция –y1 + 2y2 + y3≤1. По същия начин се компилират още две ограничения за дуалния проблем.
Получава се двоен проблем, който образува симетрична двойка с оригинала:
F (Y) = - 10y1 + 6y2 + 12y3 → макс
yi ≥ 0; i = 1,2,3.
- Двойка асиметрични двойни задачи
- Асиметрични дуални задачи
- Основни задачи и функции на архива
- Изследователска работа - изопериметрични проблеми, социална мрежа на образователните работници
- Основи на физиката на твърдото тяло - Проблеми в основите на физиката на твърдото тяло (с подробно решение)