2.4. Распределительный метод

Все полученные планы являются допустимыми, так как в них удовлетворены потребности потребителей и исчерпаны запасы поставщиков, причем один из них c F = 88 т-км можно считать оптимальным. Тем не менее, улучшить исходный план можно путем перераспределения поставок, которое связано с записью поставок в свободные клетки, при этом произойдет изменение поставок в трех или более заполненных клетках. Изменение поставок в заполненных клетках не должно нарушать итоговые величины в строках и столбцах табл. 2.3.

Например, при записи поставки в свободную клетку П₃М₁ изменение произойдет в трех заполненных клетках: П₂М₁, П₂М₃, П₃М₃ (рис. 2.1).

Запись в свободной клетке П₁М₁ вызовет изменение поставок в шести заполненных клетках (рис. 2.2).

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

Объем работы в цепи (рис. 2.1) составляет F = 34 + 16 + 27 = 32 т-км. Если в свободную клетку записать поставку 2 т, то в клетках цепи произойдут изменения: в положительных - поставки увеличатся, в отрицательных - уменьшатся (рис. 2.3), при этом получим работу F = 14 + 36 + 28 = 38 т-км, что привело к ухудшению плана на 6 т-км.

- П₂М₁ + П₂М₃ + П₁М₁ - П₁М₅

4

(3)

6

(1)

6

4

(3)

6

(1)

+ П₂М₃

8

7

(2)

6

(1)

+

7

(2)

10

(2)

П₃М₁ - П₃М₃ - П₂М₁

Рис. 2.1.

- П₃М₃ + П₃М₅

Рис. 2.2.

- П₂М₁ + П₂М₃ - П₂М₂ + П₁М₅ - П₁М₂ + П₁М₅

4

1

6

3

5

3

6

3

5

1

6

1

6

10

2

8

2

7

10

6

2

+ П₃М₁ - П₃М₃ + П₃М₂ - П₃М₅ + П₃М₂ - П₃М₅

Рис. 2.3. Рис. 2.4. Рис. 2.5.

О характере изменения плана (улучшении или ухудшении) можно судить до перераспределения по так называемой характеристике, которая представляет собой алгебраическую сумму расстояний в вершинах цепи с соответствующими знаками. Например, характеристика для цепи на рис.2.1 Н = + 8 – 4 + 6 - 7 = +3 указывает на то, что при заполнении этой клетки произойдет увеличение объема работы на 3 км на каждую единицу груза, т.е. при перераспределении (рис.2.3) объем работы увеличится на величину  = 3км2т = 6 т-км.

Рассмотрим цепь для свободной клетки П₃М₂ (рис. 2.4).

Объем работы F = 35+16+210 = 41 т-км.

Характеристика для этой цепи Н = 6 – 5 + 6 - 10 = -3.

Отрицательная характеристика указывает на то, что заполнение клетки позволит уменьшить объем работы на 3 км на каждую тонну груза. При этом в свободную клетку следует записать наименьшую величину из отрицательных вершин цепи (С₃₃ = 2, рис 2.4). Перераспределение показано на рис. 2.5, при этом объем работы для этой цепи F = 15 + 36 + 26 = 35 т-км, что на 6 т-км меньше плана на рис. 2.4.

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

В табл. 2.3 общее число свободных клеток равно 8. Для каждой из этих клеток необходимо построить цепь и вычислить характеристики. Для трех свободных клеток П₃М₁ (рис 2.1), П₁М₁ (рис 2.2), П₃М₂ (рис 2.4) цепи построены и характеристики вычислены (для пяти оставшихся клеток П₂М₂, П₁М₃, П₁М₄, П₃М₄, П₂М₅ самостоятельно построить цепи и вычислить характеристики).

Из восьми свободных клеток запись можно производить только в трех: П₃М₂, П₂М₂, П₂М₅, которые имеют отрицательные характеристики, равные соответственно -3; -1, -1. При перераспределении запись производится первоначально в ту свободную клетку, отрицательная характеристика которой имеет наибольшую абсолютную величину, т.е. П₃М₂ (табл. 2.4).

В плане перевозок после перераспределения объем работы составит:

F = 15 + 36 + 34 + 16 + 35 + 26 + 27 = 82 т-км.

В этом плане тоже восемь свободных клеток. При этом цепи и соответственно характеристики незаполненных клеток П₃М₁, П₃М₄, не изменились. Остальные пять свободных клеток связаны с клеткой П₃М₅, которая в результате перераспределения оказалась свободной и для нее характеристика не определяется, так как она заведомо будет положительной.

Таблица 2.4

Поставщик и его запас аi		Потребитель и его потребность bj
		М1	М2	М3	М4	М5
		3	3	3	3	3
П1	4	6	5 ( 1 )	8	7	6 ( 3 )
П2	7	4 ( 3 )	7	6 ( 1 )	5 ( 3 )	8
П3	4	8	6 ( 2 )	7 ( 2 )	9	10

Свободные клетки будут иметь характеристики:

П₁М₁ : Н₁₁ = 6 – 5 + 6 – 7 + 6 – 4 = +2,

П₁М₄ : Н₁₄ = 7 – 5 + 6 – 7 + 6 – 5 = +2,

П₂М₅ : Н₂₅ = 8 – 6 + 7 – 6 + 5– 6 = +2,

П₁М₃ : Н₁₃ = 8 – 7 + 6 – 5 = +2,

П₂М₂ : Н₂₂ = 7 - 6 + 7 – 6 = +2.

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

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

Алгоритм распределительного метода включает следующие основные этапы:

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

2. Для каждой свободной клетки составляют цепь и определяют характеристику.

3. Для цепей с отрицательными характеристиками проводят перераспределение с заполнением свободной клетки.

4. Полученный план проверяют на оптимальность.

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

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

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