Введение в линейное программирование. Палий И.А. - 80 стр.

UptoLike

ВУЗ: 

СибАДИ | Омск

Составители: 

Рубрика: 

;4)8,6,7,4,,5,6min(min
11
=
==
j
j
cu
;5min
22
=
=
j
j
cu
;3min
33
==
j
j
cu
;4min4
44
=
=
j
j
c
;2min
55
=
=
j
j
cu
;2)25,46,38,57,46min()(min
11
=
−
−
−
−
−
=−=
ii
i
ucv
;1)24,47,35,56,45min()(min
22
=
−
−
−
−
−
=−=
ii
i
ucv
;0)(min
33
=−=
ii
i
ucv
;3)(min
44
=
−
=
ii
i
ucv
;0)(min
55
=−
=
ii
i
ucv
0)(min
66
=−=
ii
i
ucv
.
Исходное значение целевой функции двойственной задачи таково
.1140303
601402802504303205904
=×+
+
×
+
×
+
×
+
×
+
×+
×
+×=W
Шаг 2. Вычисляем
jiijij
vucc
−
−
=
′
, mi ,,1 L
=
, n
j
,,1 L
=
.
Результаты расчетов приведены в табл. 9.5.
Таблица 9.5
j
v
i
u
2 1 0 3 0 0
4 0 0 0 0 2 4
5 0 0 0 1 1 1
3 3 1 3 0 0 5
4 0 2 1 0 0 5
2
1 1
5 3 3 0
Шаг 3. Решим задачу о максимальном потоке, считая допустимыми
клетки с нулями. Ход решения отражен табл. 9.6.
Для сокращения числа итераций начальный поток взят ненулевым. Не
вывезены запасы 4-го и 5-го поставщиков. У первого поставщика осталось
40, у второго – 30 единиц продукта. Метим четвертую и пятую строки
соответственно метками (s
+
, 40) и (s
+
, 30). От четвертой строки по
допустимым клеткам метятся 1, 4, 5-й столбцы меткой (4
+
, 40). От пятой
строки метится по допустимой клетке 6-й столбец меткой (5
+
, 30).
От первого столбца по допустимой клетке с ненулевым потоком 40
метится первая строка меткой (1
−
, min(40, 40)) = (1
−
, 40).

Страницы