Сущность распределительного метода.

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

Остановимся на рассмотренных понятиях подробнее.

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

Например, в табл. 3.11 изображены два цикла: первый с четырьмя вершинами (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.11

ПН ПО	B 1	B 2	В 3	B 4	В 5	В 6	Запасы аi
A 1	С 11	С 12	С 13	С 14 +	С 15	С 16 -	а 1
A 2	C 21 +	C 22	C 23 -	C 24	C 25	C 26	а 2
А 3	C 31	C 32	C 33	C 34 +	C 35 -	C 36	а 3
A 4	C 41 -	C 42	C 43 +	C 44-	C 45	C 46 +	а 4
A 5	C 51	C 52	C 53	C 54 -	C 55 +	C 56	а 5
Заявки bj	b 1	b 2	b 3	b 4	b 5	b 6

 

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

Назовем ценой цикла увеличение стоимости перевозок при перемещение одной единицы груза по означенному циклу. Очевидно, цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, причем стоимости, стоящие в положительных вершинах, берутся со знаком «+», а в отрицательных - со знаком «-». Например, для цикла Ц₁ в таблице 3.11 цена равна: ν₁ = с ₂₁ - с ₂₃ + с ₄₃ - с ₄₁,

а для цикла Ц₂: ν₂ = с ₁₄ - с ₁₆ + с ₄₆ - с ₄₄ + с ₃₄ - с ₃₅ + с ₅₅ - с ₅₄.

Обозначим цену цикла Ц через n. При перемещении одной единицы груза по циклу Ц стоимость перевозок увеличивается на величину n; при перемещении по нему k единиц груза стоимость перевозок увеличивается на kn.

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

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

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

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