Полная версия

Главная arrow Математика, химия, физика arrow Математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Улучшение плана перевозок. Цикл пересчета

В предыдущем параграфе мы уже бегло ознакомились со способом улучшения плана, состоящим в переносе (перестановках) некоторых перевозок, без нарушения баланса, из клетки в клетку по некоторому замкнутому циклу. Рассмотрим циклические перестановки подробнее.

Возьмем транспортную таблицу, состоящую, например, из т - 5 строк и п = 6 столбцов (число строк и столбцов несущественно).

Циклом пересчета в транспортной таблице мы будем называть несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке совершает поворот на 90°.

Например, в табл. 3.35 изображены два цикла: первый с четырьмя вершинами (2, 1), (2, 3), (4, 3), (4, 1) и второй — с восемью вершинами (1,4), (1, 6), (4, 6), (4,4), (3,4), (3, 5), (5, 5), (5,4). Стрелками показано направление обхода цикла.

Нетрудно убедиться, что каждый цикл имеет четное число вершин и, значит, четное число звеньев (стрелок). Условимся отмечать знаком “+” вершины цикла, в которых перевозки увеличиваются, а знаком вершины, в которых они уменьшаются. Цикл с отмеченными вершинами будем называть означенным. В табл. 3.36 показано два означенных цикла: первый Цх с четырьмя вершинами (1,1), (1, 2), (3,2) и (3,1) и второй Ц2 с восемью вершинами (3,4), (3, 6), (5, 6), (5, 3), (2, 3), (2, 5), (4, 5) и (4,4).

Перенести (“перебросить”) какое-то количество единиц груза по означенному циклу — это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц и уменьшить на то же количество перевозки, стоящие в отрицательных вершинах. Очевидно, что при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется: по-прежнему сумма перевозок в каждой строке равна запасам этой строки, а сумма перевозок в каждом столбце — заявке этого столбца. Таким образом, при любом циклическом переносе, оставляющем перевозки неотрицательными, допустимый план

Таблица 3.36

остается допустимый. Стоимость же плана при этом может меняться — увеличиваться или уменьшаться.

Назовем ценой цикла увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Очевидно, что цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, причем в положительных вершинах стоимость берется со знаком а в отрицательных — со знаком Например, для цикла Цх в табл. 3.36 цена равна

для цикла Ц2

Обозначим цену цикла через у При перемещении одной единицы груза по циклу стоимость перевозок увеличивается на величину у, а при перемещении к единиц груза — соответственно, на ку

Очевидно, для улучшения плана имеет смысл перемещать перевозки только по тем циклам, цена которых отрицательна. Каждый раз, когда нам удастся совершить такое перемещение, стоимость плана уменьшается на соответствующую величину ку.

Так как перевозки не могут быть отрицательными, мы будем пользоваться только такими циклами, отрицательные вершины которых лежат в базисных клетках таблицы, где стоят положительные перевозки[1]. Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что дальнейшее улучшение плана невозможно, т.е. оптимальный план достигнут.

Метод последовательного улучшения плана перевозок и состоит в том, что в таблице отыскиваются циклы с отрицательной ценой, по ним перемещаются перевозки, и план улучшается до тех пор, пока циклов с отрицательной ценой уже не останется.

При улучшении плана циклическими переносами, как правило, пользуются приемом, заимствованным из симплекс-метода: при каждом шаге (цикле) заменяют одну свободную переменную на базисную, т.е. заполняют одну свободную клетку и взамен того освобождают одну базисную клетку. При этом общее число базисных клеток остается неизменным: т + п- 1. Этот прием удобен тем, что для него легче находить подходящие циклы.

Можно доказать, что для любой свободной клетки транспортной таблицы всегда существует цикл (и притом единственный), одна из вершин которого лежит в этой свободной клетке, а все осшальныев базисных клетках. Если цена такого цикла (с плюсом в свободной клетке) отрицательна, то план можно улучшить перемещением перевозок по данному циклу. Количество единиц груза к, которое можно переместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла (если переместить большее число единиц груза, возникнут отрицательные перевозки).

ОПРИМЕР 3.14. Найти оптимальный план для транспортной задачи, приведенной в табл. 3.37.

Таблица 3.37

пн

по

А

А

А

А

Запасы а,

А

1 0

7

6

8

3 1

А

5

6

5

4

48

А

8

7

6

7

38

Заявки Ь.

22

34

4 1

20

1 17

Решение. Составляем опорный план способом северо-западного угла (табл. 3.38).

Таблица 3.38

Стоимость этого плана

Число базисных переменных, как и полагается в невырожденном случае, равно г = т + п - 1 = 3 + 4-1 =6.

Попробуем улучшить план, заняв свободную клетку (2, 4) с минимальной стоимостью 4. Цикл, соответствующий этой клетке, показан в табл. 3.38. Цена этого цикла равна у=4-7 + 6- 5 = -2.

По этому циклу мы можем переместить максимум 20 единиц груза (чтобы не получить в клетке (3,4) отрицательной перевозки). Новый, улучшенный план показан в табл. 3.39.

Таблица 3.39

Стоимость этого плана L2 = 796 + 20 • (-2) = 756. В нем по- прежнему шесть базисных клеток.

Для дальнейшего улучшения плана обратим внимание на свободную клетку (2, 1) со стоимостью 5. Цикл, соответствующий этой клетке, показан в табл. 3.39. Цена его у= 7 - 6 + 5 - 10 = -4. По этому циклу переместим 22 единицы груза, чем уменьшим стоимость перевозок до Ьъ = 756 + 22 • (-4) = 668 (табл. 3.40).

Попробуем дальше улучшить этот план, подсчитывая цены циклов, начинающихся положительной вершиной в свободной клетке. Просматриваем имеющиеся свободные клетки табл. 3.40 и определяем цену цикла для каждой из них. Все эти цены или положительные, или нулевые (предлагаем читателю проверить это

пн

по

я,

в2

в,

в4

Запасы а,

А

31

А

48

А

38

Заявки bj

22

34

41

20

117

самостоятельно). Следовательно, никакой циклический перенос перевозок не может улучшить план перевозок. Таким образом, план, полученный в табл. 3.40, является оптимальным. ?

Указанный метод отыскания оптимального решения ТЗ называется распределительным; он состоит в отыскании свободных клеток с отрицательной ценой цикла и в перенесении перевозок по этому циклу.

[>ПРИМЕР 3.15. Найти оптимальный план перевозок для ТЗ, условия которой приведены в табл. 3.41.

Таблица 3.41

ПН

ПО

в,

в2

в>

Запасы а.

А

1 0

5

4

40

А

6

4

5

23

А

7

3

6

20

Заявки bj

20

20

43

83

Решение. Строим опорный план способом северо-западного угла; он получается вырожденным. Чтобы избежать этого, нарушаем баланс запасов и заявок на е в первой и третьей строках, не нарушая общего баланса (сумма запасов равна сумме заявок). После этого строим опорный план тем же способом северо-западного угла (табл. 3.42), в нем ровно столько базисных переменных, сколько нужно: пять. Улучшаем план перевозок переносом 20 - г единиц груза по циклу, показанному в табл. 3.42; получим новый, улучшенный план (см. табл. 3.43).

План, приведенный в табл. 3.41, еще не оптимален, так как цикл с началом в свободной клетке (2, 1) имеет отрицательную цену: у= 6-10 + 4-5 = -5.

Таблица 3.42

Таблица 3.43

Перемещаем по этому циклу 20 единиц груза; получаем табл. 3.44.

Таблица 3.44

Цена цикла, начинающегося в клетке (2, 2) табл. 3.44, также отрицательна: 4-5 + 4- 5 = -2. Однако по этому циклу можно перенести только перевозку, равную ?. Тем не менее сделаем это и получим новый план (табл. 3.45).

Таблица 3.45

...... пн

по

я,

в2

в,

Запасы ai

А

со

+

О

А

23

А

20-е

Заявки b

J

20

20

43

83

В табл. 3.45 все циклы, соответствующие свободным клеткам, имеют неотрицательную цену, поэтому план, приведенный в табл. 3.45, является оптимальным. Полагая в нем ? = 0, получим окончательный оптимальный план (табл. 3.46) с минимальной стоимостью перевозок

L . = 40- 4 + 20- 6 + 3- 5 + 20-3 = 355. ?

пип

Таблица 3.46

пн

по

5,

в.

А

Запасы а.

А

40

Л

23

А

20

Заявки Ь.

20

20

43

83

Заметим, что примененный здесь метод “ликвидации вырождения” путем ?-изменения запасов не совсем удобен, так как требует дополнительных действий с е-измененными данными. Проще было бы при заполнении табл. 3.42 не изменять запасы, а вообразить их себе измененными и вместо ? поставить в базисной клетке (3, 3) нуль. Базисная клетка с нулевой перевозкой будет отличаться от свободной тем, что в ней нуль будет проставлен, а в свободной — нет. Дальнейшие манипуляции с транспортной таблицей будут точно такими же, как если бы в базисных клетках стояли только положительные перевозки. Разница лишь в том, что, когда одна из отрицательных вершин цикла окажется в базисной клетке с нулевой перевозкой, нужно переносить по этому циклу нулевую перевозку (фиктивный перенос). Если в транспортной таблице немного (одна-две) базисных переменных обращаются в нуль, можно рекомендовать этот простой метод вместо ?-изменений запасов (заявок). (Предлагаем читателю самостоятельно решить пример 3.15 упрощенным способом.) Следует иметь в виду, что при большом количестве базисных переменных, обращающихся в нуль, упрощенный метод становится менее удобным, так как легко запутаться с расстановкой по таблице нулевых базисных перевозок (т.е. ошибочно проставить базисные клетки там, где они находиться не могут).

  • [1] В случае вырождения, как мы увидим далее, может оказаться полезным фиктивный перенос по циклу, отрицательная вершина котороголежит в клетке с нулевой перевозкой.
 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>