Запись двойственной задачи в общем случае
Дополнительные правила записи двойственной задачи получим, сводя несимметричные условия прямой задачи к симметричным. 1.Среди условий прямой задачи есть равенство (k -е условие). Заменив k- е условие-равенство двумя неравенствами
приходим к симметричному случаю. Если новым неравенствам сопоставить неотрицательные двойственные переменные
Так как 2.Переменная xk в прямой задаче не ограничена по знаку. Заменим эту переменную всюду в модели разностью неотрицательных переменных: Этим переменным в двойственной задаче будут соответствовать 2 неравенства
которые эквивалентны равенству Итак, в общем случае 5-е правило записи двойственной задачи включает 4 пункта, представленные в следующей таблице
Эти правила предполагают, что прямая задача записана с критерием на максимум и неравенствами в виде “меньше или равно”. Очевидно, что в симметричном случае из 5-го правила применяются только пункты 5.1.и 5.3. Пример. Прямая задача: Преобразовав: L= 2 x 1 +x 2- x 4 + 3 x 5 ® max; L= 2 x 1 + x 2- x 4 + 3 x 5 ® max; 5 x 1 - 7 x 2 + 4 x 3 + 2 x 5£ 8; U 1: 5 x 1 - 7 x 2 + 4 x 3 + 2 x 5£ 8; 3 x 2 + 6 x 3 - 2 x 4³ 10; U 2: - 3 x 2 - 6 x 3 + 2 x 4£ - 10; x 1 + 4 x 2 +x 3 - 3 x4= 5; U 3: x 1 + 4 x 2 + x 3 - 3 x 4 = 5; 9x1 - x 2 + 5 x 4 - 4 x 5³16; U 4: - 9x1 + x 2 - 5 x 4 + 4 x 5£ - 16; x 1³0, x 3³0, x 4³0. x 1³0, x 3³0, x 4³0. В соответствии с правилами для общего случая записываем модель двойственной задачи
5 U 1 +U 3 - 9 U 4 ³ 2; - 7 U 1 - 3 U 2 + 4 U 3 + U 4 = 1; 4 U 1 - 6 U 2 + U 3 ³ 0; 2 U 2 - 3 U 3 - 5 U 4³ - 1; 2 U 1 + 4 U 4 = 3; U 1³ 0, U 2³ 0, U 4³ 0.
|
Û 
и 
, то в соответствии с вышеописанными правилами запишем критерий и неравенства двойственной задачи
После вынесения общих множителей за () получаем 
и иметь одну двойственную переменную, соответствующую равенству прямой задачи, но при этом она не будет ограничена по знаку.
= 8 U 1 - 10 U 2 + 5 U 3 - 16 U 4 ® min;
