Составители:
Рубрика:
Процедура улучшения неоптимального плана сводится к перемещению
загрузок в потенциальные клетки матрицы. Поскольку нельзя просто
переставить в потенциальную клетку одну из загрузок, не нарушив итоги по
строкам и столбцам, разработан специальный способ перемещения загрузок. Он
состоит из составления цепочки возможных перемещений загрузок в матрице,
определения величины загрузки, подлежащей перемещению, и собственно
перемещения.
Цепочку возможных перемещений определяют следующим образом. Для
потенциальной клетки с наибольшим потенциалом строят замкнутую цепочку
из горизонтальных и вертикальных отрезков так, чтобы одна ее вершина
лежала в данной потенциальной клетке, а все остальные - в занятых клетках.
Такую цепочку всегда можно построить и притом единственным способом. Ее
вершины отмечают клетки
матрицы, которые должны участвовать в
перераспределении загрузок с целью улучшения плана. Возможны различные
конфигурации цепочек.
Составив цепочку, помечают знаком «+» ее нечетные вершины (считая
первой вершину в потенциальной клетке), а четные знаком «—». Наименьшая
из четных загрузок определяет величину перемещаемой загрузки. Уменьшив на
эту величину объемы перевозок, записанные в клетках со знаком минус
, и
увеличив на ту же величину объемы клеток со знаком плюс, получают новый
вариант плана с меньшей транспортной работой.
В рассматриваемом примере построена цепочка для потенциальной клетки
А
3
Б
3
и расставлены знаки (табл. 10).
Таблица 10
Вспомогательные Пункт назначения
Б
1
Б
2
Б
3
Б
4
Пункт
отправлен
ия
строка
столбец
9 14 5 8
Наличи
е груза,
т
А
1
0
+ 9
10
15
5
⎯40.
8
30.
80
А
2
⎯5
4
20 ⎯
+ 9
30
6 5
50
А
3
8
16
1
22
⎯40.
+ 10
3
18
40
Потребность в грузе, т 30 70 40 30 170
Наименьшая среди четных загрузок (отмеченных знаком минус) равна 20
(в клетке А
2
Б
1
). Уменьшив на 20 загрузки клеток А
1
Б
3
, А
2
Б
1
и А
3
Б
2
и увеличив
также на 20 загрузки клеток А
3
Б
3
, А
1
Б
1
и А
2
Б
2
, получим новый план,
представленный в табл. 11. По этому варианту плана транспортная работа
составит 1700 тонно-километров, или на 60 тонно-километров меньше.
Страницы
- « первая
- ‹ предыдущая
- …
- 13
- 14
- 15
- 16
- 17
- …
- следующая ›
- последняя »
