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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

От четвертого столбца по допустимой клетке с ненулевым потоком 30
метится третья строка меткой (4
−
, min(40, 30))=(4
−
, 30).
От пятого и шестого столбцов нельзя пометить ни одной строки. От
помеченной первой строки метятся 2-й и 3-й столбцы меткой (1
+
, 40). Но
третий потребитель недополучил 70 единиц товара. Найдена
увеличивающая цепь. Восстановим ее (рис. 9.12).
Третий столбец по прямой дуге помечен от первой строки; 1-я строка
по обратной дуге помечена от 1-го столбца; 1-й столбец по прямой дуге
помечен от четвертой строки; 4-я строка помечена от источника. Сток
метится от 3- го столбца меткой (3
+
, min(40, 80 − 10))=(3
+
, 40). В табл. 9.6
прямые дуги цепи отмечены знаком «+», обратные – знаком «
−».
Таблица 9.6
)40,4(
+
)40,1(
+
)40,1(
+
)40,4(
+
)40,4(
+
)30,5(
+
)40,1(
−
)30,4(
−
)40,(
+
s
)30,(
+
s
Увеличиваем поток на прямых дугах на 40 единиц и уменьшаем поток
на обратной дуге на 40 единиц (табл. 9.7).
Пытаемся снова увеличить поток. Пятая строка получает метку (
s
+
, 30),
от нее 6-й столбец получает метку (5
+
, 30). Больше ничего отметить нельзя.
Для данной транспортной сети найден максимальный поток, но не все
запасы 5-го поставщика вывезены (соответственно 3-й потребитель
недополучил 30 единиц груза). Можно улучшить решение двойственной
задачи.
i
j
1 2 3 4 5 6
40
40
60
60
80
10+
30
30
10
10
50
50
1
90
90
x
40−
x
50
x
+
x
2
20
20
x
x
10
x
10
3
30
30
x
30
x
4
50
10+
x
+
x
x
10
5
80
50
x
50

Страницы