Максимально допустимый сдвиг по циклу пересчета.

Понятие цикла пересчета

Пусть имеется транспортная задача (5.1 - 5.4) и соответствующая таблица 5.1. Циклом называется замкнутая ломаная линия, вершины которой лежат в клетках таблицы, а звенья попеременно принадлежат то строке, то столбцу.

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

Цикл называется означенным, если его вершинам попеременно приписаны знаки "+" и "–".

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

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

В таблице 5.4 пунктиром показан один цикл пересчета, который проходит через свободную клетку (1,1).

 

Сдвигом на величину h ≥ 0 по циклу пересчета называется увеличение на число h перевозок, стоящих в положительных вершинах цикла, и уменьшение на число h перевозок, стоящих в отрицательных вершинах.

Так как в каждой строке и каждом столбце транспортной таблицы
количество положительных вершин равно количеству отрицательных
вершин цикла, то при сдвиге на любое число h условия (5.2) и (5.3)
не нарушаются. Чтобы не нарушалось условие (5.4), величина сдвига
не должна превышать минимальной перевозки, стоящей в отрицательной
вершине цикла.

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

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

Рассмотрим пример (табл.5.4). Сделаем максимально допустимый сдвиг по циклу пересчета, проходящему через свободную клетку (1,3). Перевозки, стоящие в отрицательных вершинах цикла, равны 40, 30 и 40. Поэтому величина максимально допустимого сдвига h=min(40,30,40)=30. После сдвига получим новый опорный план перевозок (табл.5.5).

Таблица 5.5.

Пн По	В1	В2	В3	Запасы
А1	2 10	3	1
А2	4 60	2	5
А3	3	2 40	6 10
Потребности				150=150

 

Разумеется, в новом опорном плане число базисных клеток по-прежнему равно 5.

Если минимальная перевозка стоит в нескольких отрицательных клетках, то в результате максимально допустимого сдвига только одна из этих клеток превращается в свободную, а остальные клетки остаются базисными и в них проставляется число 0. Только при соблюдении этого условия число базисных клеток остается равным m+n–1.

Обратимся к таблице 5.5. Величина максимально допустимого сдвига по указанному пунктиром циклу пересчета равна 10. Из двух отрицательных клеток (1,1) и (3,3) только одна в результате сдвига превращается в свободную. Сделав свободной клетку (3,3), получим новый опорный план перевозок (табл.5.6).

Сравним суммарные стоимости планов перевозок, изображенных в
таблицах 5.4, 5.5, 5.6.

Таблица 5.4: f = 40·2 + 30·4 + 30·2 + 10·2 + 40·6 = 520
Таблица 5.5: f = 10·2 + 30·1 + 60·4 + 40·2 + 10·6 = 430
Таблица 5.6: f = 40·1 + 60·4 + 10·3 + 40·2 = 390