ВУЗ:
Составители:
Рубрика:
На новом допустимом решении двойственной задачи значение целевой
функции равно 1140 + 30 = 1170.
Таблица 9.8
j
v
i
u
2 1 0 3 0
−1
4 0 0 0 0 2 5
5 0 0 0 1 1 2
3 3 1 3 0 0 6
4 0 2 1 0 0 6
3 0 0 4 2 2 0
В табл. 9.8 указаны также новые значения двойственных переменных,
определенные в соответствии с (9.14)
Снова переходим к шагу 2 (табл. 9.9). Мы начинаем с потока, который
был построен как максимальный на предыдущей итерации.
Пятая строка получает метку (
s
+
,30). От нее меткой (5
+
, 30) метятся 1,
2, 6-й столбцы. От 2-го столбца меткой (2
−
, 30) метится первая строка. От
1-ой строки можно пометить меткой (1
+
, 30) 3-й столбец, от которого
меткой (3
+
, min(30, 80 − 50))= (3
+
,30) метится сток. На самом деле меток
можно поставить больше, все они указаны в табл. 9.9, но мы показали
только, как метятся вершины увеличивающей цепи, по которой можно
увеличить поток на 30 единиц. Прямые дуги этой цепи: (
s, 5 стр.), (5 стр., 2
столб.), (1 стр., 3 столб.), (3 столб.,
t). Обратная дуга одна – (1 стр., 2
столб.). Увеличиваем поток на прямых дугах и уменьшаем поток на
обратной дуге на 30 единиц (табл. 9.10).
Все запасы вывезены, все потребности удовлетворены. Оптимальные
перевозки следующие:
x
12
= 20, x
13
= 70, x
22
= 10, x
23
= 10, x
34
= 30, x
41
= 40,
x
45
= 10, x
52
= 30, x
56
= 50. Остальные перевозки равны нулю.
Оптимальное решение двойственной задачи:
u
1
=4, u
2
=5, u
3
=3, u
4
=4, u
5
=3, v
1
=2, v
2
=1,
v
3
=0, v
4
=3, v
5
=0, v
6
= −1.
Оптимальность найденных решений следует из условий дополняющей
нежесткости.
Оптимальное значение целевой функции Т3 равно:
1170502430
104406306105106704205
5
1
6
1
=×+×+
+×+×+×+×+×+×+×=
∑∑
==ij
ijij
xc
Страницы
- « первая
- ‹ предыдущая
- …
- 81
- 82
- 83
- 84
- 85
- …
- следующая ›
- последняя »
