Правила построения двойственной задачи в общем случае

Дополнительные правила записи двойственной задачи получим, сводя несимметричные условия прямой задачи к симметричным.

1.Среди условий прямой задачи есть равенство. Пусть таким условием является k -е, а остальные условия записаны как неравенства. Заменив k- е условие-равенство двумя неравенствами

Û

приходим к симметричному случаю. Если новым неравенствам сопоставить неотрицательные двойственные переменные и , то в соответствии с вышеописанными правилами запишем критерий и неравенства двойственной задачи

После вынесения общих множителей за скобки получаем

Так как и входят в модель только в виде разности, то можно произвести замену и, таким образом, иметь одну двойственнную переменную, соответствующую равенству прямой задачи, но при этом она не будет ограничена по знаку.

2. Переменная x_k в прямой задаче не ограничена по знаку. Заменим эту переменную всюду в модели разностью неотрицательных переменных:

Этим переменным в двойственной задаче будут соответствовать 2 неравенства

которые эквивалентны равенству

Итак, в общем случае 5-е правило записи двойственной задачи включает 4 пункта, представленные в следующей таблице

Правило	Прямая задача	Двойственная задача
5.1	Переменная xj ³0	j -е условие ³
5.2	Переменная xj не ограничена по знаку	j -е условие =
5.3	i- е условие £	Переменная Ui ³0
5.4	i- е условие =	Переменная Ui не ограничена по знаку

Эти правила предполагают, что прямая задача записана с критерием на максимум и неравенствами в виде “меньше или равно”. Очевидно, что в симметричном случае из 5-го правила применяются только пункты 5.1.и 5.3.

Пример 1. Прямая задача:

L=2x₁+x₂ - x₄+3x₅ ® max;

5x₁ - 7x₂+4x₃+2x₅ £ 8;

3x₂+6x₃ - 2x₄ ³ 10;

x₁+4x₂+x₃ -3x₄=5;

9x₁ - x₂+5x₄ -4x₅ ³16;

x₁³0, x₃³0, x₄³0.

Перепишем эту модель, изменив знаки 2-го и 4-го неравенств и сопоставив условиям двойственные переменные:

L= 2 x ₁ + x ₂ - x ₄ + 3 x ₅ ® max;

U ₁: 5 x ₁ - 7 x ₂ + 4 x ₃ + 2 x ₅ £ 8;

U ₂: -3 x ₂ - 6 x ₃ + 2 x ₄ £ - 10;

U _3: x ₁ + 4 x ₂ + x ₃ - 3 x ₄ = 5;

U ₄: -9x₁ + x ₂ - 5 x ₄ + 4 x ₅ £ - 16;

x ₁³0, x ₃³0, x ₄³0.

В соответствии с правилами для общего случая записываем модель двойственной задачи

= 8 U ₁ - 10 U ₂ + 5 U ₃ - 16 U ₄ ® min;

5 U ₁ +U ₃ - 9 U ₄ ³ 2;

- 7 U ₁ - 3 U ₂ + 4 U ₃ + U ₄ = 1;

4 U ₁ - 6 U ₂ + U ₃ ³ 0;

2 U ₂ - 3 U ₃ - 5 U ₄ ³ - 1;

2 U ₁ + 4 U ₄ = 3;

U ₁ ³ 0, U ₂³ 0, U ₄³ 0.

Дата добавления: 2014-01-11