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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

составляют все дуги вида (s, i) или (j, t), где строка с номером i – не
помечена, а столбец с номером j – помечен. И тогда
Рис. 9.13. Максимальный поток и минимальный разрез
∑∑
−−
+=
пом пом не
*
),(),(),(
ji
tjrisrRRr
=
∑
∑
−−
+
пом пом не
),(),(
ji
tjxisx
(9.19)
9.6. Венгерский алгоритм решения транспортной задачи
Напомним математическую модель задачи, двойственной
транспортной.
Максимизировать целевую функцию
∑∑
==
→+=
n
j
jj
m
i
ii
vbuaW
11
max
; (9.20)
при условиях
ijji
cvu ≤+ , i = 1, 2, …, m, j = 1, 2,
…
, n. (9.21)
Воспользуемся условиями дополняющей нежесткости.
Допустимые решения
),,(
11 mn
xxx L
=
и
),,,,,(
11 nm
vvuuy LL
=
ТЗ и двойственной ей задачи оптимальны тогда и только тогда, когда
справедливы равенства
)(
ijjiij
cvux −+ = 0, i = 1, 2, …, m, j = 1, 2,
…
, n. (9.22)
5(5)
6(6)
4(4)
s
2 1
t
1
3
4
2
3
4(2)
5(4)
2(2)
1(1)
2(2)
3(3)
2(2)
1(1)
3(3)
3(3)
3

Страницы