Асиметрични дуални задачи
Празната ZLP е зададена в канонична форма:
(),
().
Нека преведем този проблем в симетрична форма:
Директен проблем до максимум, така че неравенствата трябва да бъдат ≤. Умножете второто неравенство по (-1). Получаваме:
Нека съставим двоен проблем за получения симетричен. За това въвеждаме двойни променливи и. Получаваме:
Ние трансформираме системата от ограничения, както следва:
Нека обозначим с y разликата. и положителни, но разликата им може да бъде както положителна, така и отрицателна.
В резултат на това получаваме двоен проблем на формата:
Обобщавайки горното, ние описваме прекия и двоен проблем за LPP в общия случай:
По този начин се компилира двоен проблем със смесени ограничения със следните допълнителни правила:
1. Ако условието за неотрицателност е наложено на променливата на директния проблем, тогава j-тото условие на системата от ограничения на дуалния проблем под формата на неравенства и обратно.
2. Ако условието за неотрицателност не е наложено на променливата на директния проблем, тогава j-тото ограничение на дуалния проблем се записва под формата на строго равенство.
3. Ако в директния проблем има ограничения на равенството, тогава неотрицателното условие не се налага върху съответните променливи на дуалния проблем.
Дуалният проблем ще съвпадне с оригиналния. Следователно няма разлика коя задача може да се приеме като пряка, коя като двойна. Трябва да говорим за двойка взаимно двойни задачи.