Циклы пересчета в таблице перевозок
При решении транспортной задачи для перехода от одного решения к другому, уменьшающему стоимость перевозок, используются циклы пересчета.
Циклом пересчета в таблице перевозок называется последовательность переменных хіj, удовлетворяющих следующим условиям:
1) в каждый цикл может входить только одно свободное переменное (пустая клетка – клетка с прочерком). Все остальные переменные должны быть базисными (заполненные клетки);
2) каждые две последовательные переменные, входящие в цикл, могут находиться только на одной строке или только в одном столбце;
3) каждая строка или столбец данного цикла может содержать только две переменные;
4) каждый цикл замкнут. То есть, при последовательном обходе выбранных переменных цикл начинается и заканчивается одной и той же клеткой.
Если для свободной клетки исходной таблицы, заполненной методом северо-западного угла, можно построить цикл пересчета, то такой цикл является единственным. Число вершин в этом цикле чётно. Если же для какой-либо свободной клетки исходной таблицы цикл пересчета построить нельзя, то для реализации этой возможности некоторые из свободных переменных обращаются в базисные переменные с нулевыми значениями (в пустых клетках записываются нули. См. пример № 2). Решение, содержащее нулевые значения базисных переменных, называется вырожденным.
Укажем циклы пересчета для всех свободных клеток таблицы 1 и пере-распределение груза в них по следующим правилам:
|
|
|
а) снабдим свободную клетку знаком (+) и с каждым переходом к следую-щей клетке цикла будем изменять знак на противоположный;
б) в клетках, отмеченных знаком (-) выберем наименьшее из чисел. Это то количество груза, которое будет последовательно перевозиться из одной клетки в другую. Из клеток, отмеченных знаком (-), зафиксированное количество груза вывозится; в клетках со знаком (+) – прибывает.
Циклы пересчета в примере №1:
1) 
F = 70·170 + 50·110 + 80·20 + 40·100 + 60·50 + 11·50 = 26 550 (т.км.);
2) 
F = 70 · 90 + 50 · 110 + 15 · 100 + 80 · 80 + 60 · 70 + 11 · 50= 24 450 (т.км.);
3) 
F = 70 · 170 + 50 ·30 + 15 ·100 + 80 · 90 + 60 · 70 + 11 · 50 = 26 850 (т.км.);
4) 
F = 70 ·120 + 50 ·110 + 15 ·70 + 40 ·30 + 60 ·120 + 50 · 50 = 25 850 (т.км.);
5) 
F = 70 · 170 + 50 · 60 + 15 · 70 + 40 ·30 + 60 ·120 + 10 · 50 = 24 850 (т.км.);
6) 
F = 70 ·170 + 50 ·110 + 15 · 20 + 40 · 30 + 60 ·120 + 90 ·50 = 30 600 (т.км.);
Следует сравнить стоимость перевозок в каждом цикле со стоимостью перевозок по опорному (первоначальному) плану
Fнач = 70·170 + 50·110 + 15·20 + 40·80 + 60·70 + 11·50 = 25650 (т.км.)
и выбрать наименьший из всех результатов – результат (2), который представ-лен в таблице 2.
Таблица 2
|
|
|
|
Базы | Заказчики | Запасы на базах | |||
| В1 | В2 | В3 | В4 | ||
| А1 | 70 90 | 50 110 | 15 100 | 80 ― | 300 т. |
| А2 | 80 80 | 90 ― | 40 ― | 60 70 | 150 т. |
| А3 | 50 ― | 10 ― | 90 ― | 11 50 | 50 т. |
| Потребности заказчика | 170 т. | 110 т. | 100 т. | 120 т. | 500 т. 500 т. |
Примечание. Если минимальное значение среди базисных переменных содержится в цикле пересчета в нескольких отрицательных вершинах цикла, то свободной (с прочерком) оставляют только одну из них, а в других клетках с таким же минимальным значением записываются нули. Эти нули являются новыми значениями базисных переменных. Образуется вырожденное решение.
Дата добавления: 2019-09-13; просмотров: 689; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!