Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 183
Скачиваний: 0
6.2. ПРЯМО-ДВОЙСТВЕННЫЙ МЕТОД |
121 |
|||||
при условиях |
|
|
|
|
|
|
|
2xi —х2+ Зх3 —2х4= 3, |
|
||||
— |
Зх2— |
|
|
= 1 , |
(6) |
|
x j > 0 |
(j = l, |
2, |
3, 4). |
|
||
Двойственная задача к (6 ) имеет вид |
|
|
||||
найти максимум |
w = |
Зя4 + |
я 2 |
|
||
|
|
|||||
при условиях |
2 я1 |
|
я 2 |
|
1 , |
|
|
|
|
|
|||
|
—Я1 -f- Зя2 ^ 1 , |
(7) |
||||
|
3я1 — |
4 я 2 |
2, |
|||
|
|
|||||
|
— 2 я ! |
+ |
4я 2 |
^ |
8. |
|
Вектор (яь я 2) = (0, |
0) — допустимое |
решение задачи (7). |
При |
|||
таких значениях вектора я все ограничения задачи (7) выполняют
ся как строгие неравенства, |
поэтому множество индексов / пусто. |
||
Выпишем условия вспомогательной задачи: |
|||
минимизировать |
|
|
|
Е= |
а . |
а |
|
X i + |
X 2 |
||
при ограничениях |
|
|
|
4 |
= |
3, |
|
4 |
= |
1, |
(8) |
4 > 0 |
(г = 1 , 2) . |
||
Выпишем оптимальное решение задачи, двойственной к задаче (8 ):
(nt, я2) = (1, 1), |
а целевая функция |
£ = |
4. |
|
|
|
|
|
с2 —(0, 0) а2 |
|
J_ |
(для яа;- > 0 ). |
|||
|
(1, 1) а2 |
|
~ |
2 |
|||
|
|
|
|
|
|||
Таким образом, |
новое допустимое |
решение |
задачи |
(7) имеет вид |
|||
я' = я + 01Я = (О, 0) + 4 -(1, |
1 ) = ( |
2 ’ |
2 |
)■ |
|||
|
|
|
|
|
L |
_ 1 |
|
Подставляя значения я' в условия (7), видим, что второе ограни чение превращается в равенство. Поэтому вспомогательная задача принимает следующий вид:
найти минимум
£ =
122 ГЛ. 6. МЕТОД ОДНОВРЕМЕННОГО РЕШЕНИЯ
при условиях
— Ж2 + Ж1 = 3,
3;г2 - \- х 2 = \ , |
(9) |
X 2, х \ , я2> 0 .
О пти м а л ьн ы м |
реш ением |
задачи, |
двойственной к вспом огатель |
|||
н о й (9 ), будет |
я = (1, Vs) |
с |
яЬ = |
1 = 10/з- |
|
|
|
0 |
— С1/2i ‘•/г) al |
_ 1 — 4/2_ |
^ |
||
|
01 “ |
(1 , i/s) а! |
*/з |
Ю • |
||
Вновь полученное допустимое |
решение — |
|
||||
|
Л ' = |
(112> V 2) + |
VlO (1> Vs) = (4/ 5’ 3/б)’ |
|||
Подставляя полученный результат в условия задачи (7), видим что первое и второе ограничения выполняются как равенства. Остальные ограничения превращаются в строгие неравенства. Следовательно, новая вспомогательная задача имеет вид:
минимизировать
|
|
|
|
|
е. |
|
а |
| |
а |
|
|
|
|
|
|
|
|
l ^ |
X |
i + |
X z |
|
|
|
|
при условиях |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2xi— |
a;2 + ^i = |
3, |
|
||||||
|
|
|
— |
X i |
- j - 3 |
x |
2 + |
|
X 2 = |
l |
, |
(10) |
|
|
|
|
|
|
|
а |
|
л __а |
|
|
|
|
|
|
|
X i , |
х 2 , |
X I , |
|
х 2 > и . |
|
|||
= |
2 , х2 = 1 |
при |
| = |
0 |
— оптимальное |
решение задачи (1 0 ). |
||||||
Это |
означает, |
что |
(xi, |
х2, х 3, xt) |
— (2 , |
1 , |
0 , 0 ) — оптимальное |
|||||
решение задачи (6 ). Заметим, что выполнены условия дополняю
щей нежесткости:
(ct — я а 1) х 1 = |
(1 — (4/ 5, |
3/ б) [ |
2 , |
— 1 |
] ) - 2 |
= |
0, |
(с2 — я а 2) г 2 = |
(1 — (4/ в, |
3/s) [ — 1, |
3 |
] ) - 1 |
= |
0, |
|
(с3—я а 3) х 3 = |
(2 — (4/ 5, |
3/&) [ |
3, |
— 4 ]) • 0 |
= 0, |
||
(с4— я а 4) г 4 = |
(8 — (4/ 6, |
Vs) [ — 2, |
4 ] ) - 0 |
= |
0. |
||
Зная идею рассмотренного метода, опишем процесс решения при мера еще раз с помощью таблиц, подобных симплексным. Табли ца 6.17 включает в себя исходную целевую функцию задачи (6 ),
а также функцию |, представляющую собой сумму невязок. Заме тим, что в 1 -строке звездочкой помечены две позиции, расположен
ные над единичной матрицей. Числа, появляющиеся в этих пози циях в следующих таблицах, равны значениям 1 — ^ и 1 — я 2
соответственно.
|
6.2. |
ПРЯМО-ДВОЙСТВЕННЫЙ МЕТОД |
123 |
|
Вычитая из ^-строки третью |
и четвертую строки, |
получим |
||
табл. |
6.18, которая |
является стандартной для минимизации £ |
||
с х\ и ж® в качестве |
исходных базисных переменных. Поскольку |
|||
все |
коэффициенты |
в z-строке |
неотрицательные, л = |
(0 , 0 ) — |
допустимое решение задачи (7). Умножая соответствующим обра зом третью и четвертую строку на (0 , 0 ) и вычитая их из z-строки,
получаем ту же самую z-строку. (В вычитании не участвуют эле менты, соответствующие искусственным переменным.) Результат вычитания не изменит табл. 6.18. Поскольку все коэффициенты z-строки неотрицательны, ни один из столбцов под xi, х2, х3 и ж4
не может быть использован во вспомогательной задаче. Вспомога тельная задача «заключена» в первых трех столбцах и последних
трех строках табл. 6.18. Из |
этой подтаблицы видно, что £ = 4 |
и 1 — iti = 0, 1 — я 2 = 0 |
или Я1 = 1, я 2 = 1. Заметим, что |
значения (—яа7-) записаны в позициях ^-строки, а значения (Cj—
— ли,-)— в позициях z-строки. Таким образом, значение 0j опре деляется, как
0 i = mm |
- з а ; |
mm |
|
|
з а ,- |
Умножая g-строку на 1/2 и прибавляя z-строку, получим табл. 6.19 {в сложении не участвуют элементы, соответствующие переменным
х1 и х%). Эта процедура равносильна Cj — ла}- + 0i (—яа;), или
Cj — (я + 0 4л) aj, или Cj — я'а;.
Теперь, поскольку коэффициент в z-строке под х2 равен нулю, этот столбец может быть использован во вспомогательной задаче. Преобразовав последние три строки табл. 6.19 при помощи итера ции симплекс-метода, получим табл. 6 .2 0 .
Вследствие того что все коэффициенты в g-строке под ж“, х%
их2 неотрицательны, g = 10/3— решение вспомогательной задачи
иоптимальное решение я задачи, двойственной к вспомогательной,
задается |
1 — я4 = 0 и |
1 — я 2 |
= 2/3. Иначе говоря, п± = 1 и |
|
.Я'2 = 1/3. |
Значение 04 определится следующим |
образом: |
||
|
0 ! = min |
Уг |
3/2 |
3_ |
|
-5/з |
-6/з |
10 |
|
|
|
|||
Итак, (я;, я;) = (1/2, 1/2) + |
3/io(l, |
Уз) = (*/5 , 3/s). |
|
|
Прибавляя g-строку, умноженную на 3/10, к z-строке (исключая элементы, соответствующие искусственным переменным), получим табл. 6.21. Теперь, поскольку коэффициенты в z-уравнении под Xi и х2 равны нулю, соответствующие им столбцы могут быть использованы во вспомогательной задаче. В табл. 6.21 эти столб цы помечены стрелками. Применяя итерацию симплекс-метода к последним трем строкам табл. 6.21, получим табл. 6.22. Посколь
ку g |
= |
0 , эта таблица оптимальна при z = 3, xt = 2 , х2 = 1 , |
х 3 = |
0 , |
т4 = 0 . |
|
|
|
|
Таблица 6.17 |
|
|
|
|
|
|
1 |
х° |
|
|
х2 |
х2 |
Ж4 |
|
|
— Z |
0 |
|
|
1 |
1 |
2 |
8 |
|
|
- 1 |
0 |
|
' l * |
0 |
0 |
0 |
0 |
J t Я |
|
< |
3 |
1 |
0 |
2 |
- 1 |
3 |
- 2 |
0 |
|
2 |
1 |
0 |
1 |
- 1 |
3 |
- 4 |
4 |
0 |
|
|
|
|
Таблица 6.18 |
|
|
|
|
||
|
|
|
|
|
|
|
|
||
|
1 |
|
|
Xt |
х2 |
х3 |
|
|
|
— Z |
0 |
|
|
1 |
1 |
2 |
8 |
|
|
- £ |
- 4 |
0 |
0 |
- 1 |
- 2 |
1 |
- 2 |
Я Я |
|
*? |
3 |
1 |
0 |
2 |
- 1 |
3 |
— 2 |
0 1 |
|
< |
1 |
0 |
1 |
- 1 |
3* |
- 4 |
4 |
0 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
„а |
Таблица 6.19 |
|
|
|
|
|
|
1 |
яа |
Xi |
#2 |
*3 |
4 |
|
|
|
|
Х2, |
|
|
Я |
|
|
|||
|
|
1 |
|
|
5/2 |
7 |
|
|
|
— Z |
- 2 |
|
|
1 / 2 |
0 |
|
|
||
- 1 |
- 4 |
0 |
0 |
- 1 |
- 2 |
1 |
- 2 |
Я Я |
|
ха |
3 |
1 |
0 |
2 |
- 1 |
3 |
- 2 |
1 / 2 1 |
|
1 |
|||||||||
„а |
1 |
0 |
1 |
- 1 |
3* - 4 |
4 |
1 / 2 |
1 |
|
X2 |
|
|
|||||||
|
|
|
|
Таблица 6.20 |
|
хк |
|
|
|
|
1 |
< |
ха |
Xi |
Х 2 |
*3 |
|
|
|
|
|
хг |
|
|
|
|
|
|
|
— Z |
- 2 |
|
|
1 / 2 |
0 |
5/2 |
7 |
|
|
- 1 |
-1 0 /3 |
0 |
2/3 |
-5 /3 |
0 |
- 5 /3 |
2/3 |
Я |
я |
ха |
10/3 |
1 |
1/3 |
5/3 |
0 |
5/3 |
- 2 /3 |
1 / 2 |
1 |
х2 |
1/3 |
0 |
1/3 |
- 1 /3 |
1 |
- 4 /3 |
4/3 |
1/2 |
1/3 |
|
|
|
|
Таблица 6.21 |
|
|
|
|
|
|
1 |
|
|
1 |
1 |
|
^4 |
|
|
|
*? |
*2 |
* 1 |
х2 |
*3 |
|
|
||
— Z |
- 3 |
|
36/5 |
|
|
||||
|
|
0 |
0 |
2 |
|
|
|||
- 1 |
-1 0 /3 |
0 |
2/3 |
- 5 /3 |
0 |
-5 /3 |
2/3 |
Л |
я |
ха |
10/3 |
1 |
1/3 |
5/3* |
0 |
5/3 |
- 2 /3 |
4/5 |
1 |
х2 |
1/3 |
0 |
1/3 |
- 1 /3 |
1 |
- 4 /3 |
4/3 |
3/5 |
1/3 |
|
|
|
|
Таблица 6.22 |
|
|
|
|
|
|
1 |
*? |
*2 |
Х 1 |
д:2 |
х3 |
*4 |
|
|
— Z |
—3 |
|
|
|
36/5 |
|
|
||
|
|
0 |
0 |
2 |
|
|
|||
- 6 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
Я |
Я |
XI |
2 |
3/5 |
1/5 |
1 |
0 |
1 |
- 2 /5 |
4/5 |
0 |
х% |
1 |
1/5 |
2/5 |
0 |
1 |
- 1 |
18/15 |
3/5 |
0 |