60. Теория на дуалността
Всеки проблем на линейното програмиране може да бъде свързан с неговия присъединен или двоен проблем. Освен това съвместното изследване на тези проблеми обикновено дава много повече информация, отколкото изследването на всеки един от тях поотделно.
Всеки проблем с линейно програмиране може да бъде написан като:
Оригиналната задача се наричаПървоначалнаилиДиректна.
Моделът на двойната задача има формата:
Променливите на двойния проблем се наричат обективно определени оценки или двойни оценки.
Връзката между първоначалните и двойните проблеми се крие по-специално във факта, че решението на една от тях може да бъде получено директно от решението на другата. Всяка от задачите на двойната двойка всъщност е независима задача за линейно програмиране и може да бъде решена независимо от другата.
Двойният проблем по отношение на оригиналния се съставя съгласно следните правила:
1.Целевата функция на изходния проблем е формулирана за максимума, а целевата функция на дуалния проблем е формулирана за минимума, докато в задачата за максимума всички неравенства във функционалните ограничения имат вида , а в задачата за минимума - вида ;
2.Матрица
3.Броят на променливите в двойния проблем е равен на броя на функционалните ограничения на първоначалния проблем, а броят на ограниченията в системата на двойния проблем е равен на броя на променливите в оригиналния проблем;
4.Коефициентите на неизвестните в целевата функция на двойния проблем са свободни членове в системата от ограничения на първоначалния проблем и десните страни в ограниченията на двойния проблемзадачи - коефициенти на неизвестни в целевата функция на изходната задача;
5.Всяко ограничение на една задача съответства на променлива на друга задача: номерът на променливата съответства на номера на ограничението; в този случай ограничението, записано като неравенство, съответства на променлива, обвързана от условието за неотрицателност. Ако функционалното ограничение на първоначалния проблем е равенството, тогава съответната променлива на двойния проблем може да приеме както положителни, така и отрицателни стойности.
Математическите модели на двойка двойни проблеми могат да бъдат симетрични и асиметрични. В асиметричните двойствени задачи системата от ограничения на първоначалната задача е дадена под формата на равенства, а в двойствената задача - под формата на неравенства, като променливите в двойствената задача могат да бъдат и отрицателни. В симетрични двойни проблеми системата от ограничения както за първоначалния проблем, така и за двойния проблем е дадена под формата на неравенства, а условието за неотрицателност е наложено на двойните променливи.