 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Запись двойственной задачи в общем случае
|
|
Дополнительные правила записи двойственной задачи получим, сводя несимметричные условия прямой задачи к симметричным.
1.Среди условий прямой задачи есть равенство. Пусть таким условием является k -е, а остальные условия записаны как неравенства. Заменив k- е условие-равенство двумя неравенствами
Û 
приходим к симметричному случаю. Если новым неравенствам сопоставить неотрицательные двойственные переменные 
и 
, то в соответствии с вышеописанными правилами запишем критерий и неравенства двойственной задачи
После вынесения общих множителей за скобки получаем
Так как и входят в модель только в виде разности, то можно произвести замену 
и, таким образом, иметь одну двойственнную переменную, соответствующую равенству прямой задачи, но при этом она не будет ограничена по знаку.
2.Переменная xk в прямой задаче не ограничена по знаку. Заменим эту переменную всюду в модели разностью неотрицательных переменных:
 |
Этим переменным в двойственной задаче будут соответствовать 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.
Пример 4.4. Прямая задача:
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;
3 x 2 + 6 x 3 - 2 x 4³ 10;
x 1 + 4 x 2 +x 3 - 3 x4= 5;
9x1 - x 2 + 5 x 4 - 4 x 5³16;
x 1³0, x 3³0, x 4³0.
Перепишем эту модель, изменив знаки 2-го и 4-го неравенств и сопоставив условиям двойственные переменные:
L= 2 x 1 + x 2- x 4 + 3 x 5 ® max;
U 1: 5 x 1 - 7 x 2 + 4 x 3 + 2 x 5£ 8;
U 2: -3 x 2 - 6 x 3 + 2 x 4£ - 10;
U 3: x 1 + 4 x 2 + x 3 - 3 x 4 = 5;
U 4: -9x1 + x 2 - 5 x 4 + 4 x 5£ - 16;
x 1³0, x 3³0, x 4³0.
В соответствии с правилами для общего случая записываем модель двойственной задачи
= 8 U 1 - 10 U 2 + 5 U 3 - 16 U 4 ® min;
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.
Дата публикования: 2015-01-23; Прочитано: 254 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
