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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

Положим, что затраты
ij
c занесены в матрицу затрат
C
размерности
nm × .
Пусть найдено допустимое решение
),,,,,(
11 nm
vvuuy LL
=
задачи
(9.21 − 9.22). Выделим в матрицу затрат те клети (
ij
c ), для которых
ijji
cvu =+ . Будем считать эти клетки допустимыми, построим
соответствующую транспортную сеть (рис. 2.14) и решим для этой сети
задачу о максимальном потоке.
Рис. 9.11. Транспортная сеть, соответствующая ТЗ
Правило построения сети: источник
s
соединен с каждой вершиной
i
A
дугой
),(
i
As
с пропускной способностью, равной
i
a
, i = 1, 2, …, m.
Каждая вершина
j
B соединена со стоком
t
дугой ),( tB
j
с пропускной
способностью, равной
j
b , j = 1, 2,
…
, n. Если справедливо равенство c
ij
=
u
i
+ v
j
, то в транспортной сети есть дуга (A
i
, В
j
) с пропускной
способностью, равной ∞, i = 1, 2, …, m, j = 1, 2,
…
, n. Возможны два
случая:
а) все дуги, выходящие из источника (соответственно все дуги,
входящие в сток), насыщены. Это значит, что все запасы вывезены (все
потребности удовлетворены). Тогда неизвестные перевозки x
ij
просто
равны потокам на соответствующих дугах двудольного графа. При этом
получено оптимальное решение транспортной задачи, потому что для
имеющихся допустимых решений
y
x
, пары двойственных задач
выполнены условия дополняющей нежесткости;
a
m
a
i
a
1
b
j
A
1
B
n
A
m
B
1
s t
A
i
B
j
∞
b
1
b
n
∞
∞
∞
∞

Страницы