Распределительный метод решения транспортной задачи

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

Оценка клетки (i,j)в матрице оценок вычисляется по следующему правилу: оценка i -й строки + оценка j -го столбца + число в левом верхнем углу клетки (i,j). Оценки строки и столбца выбираются таким образом, чтобы оценки всех отмеченных клеток были равны нулю.

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

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

Начинать можно с любой строки или любого столбца. Начнем с 1-й строки, приписав ей ноль (впрочем, на 1-м шаге можно приписать любую оценку). В 1-й строке находятся две отмеченные клетки (1,2) и (1,3). Их оценки в матрице оценок должны быть нулевыми, Из этого условия, зная оценку 1-й строки, найдем оценки 2-го и 3-го столбца.

Оценка клетки (1,2) = Оценка 1-й строки + оценка 2-го столбца + число в левом верхнем углу клетки (1,2)

0 = 0 + оценка 1-го столбца + 1 (так должно быть для отмеченной клетки). Отсюда оценка 1-го столбца = -1.

Оценка клетки (1,3) = оценка 1-й строки + оценка 3-го столбца + число в левом верхнем углу клетки (1,3)

0 = 0 + оценка 3-го столбца + 3 = 0 (так должно быть для отмеченной клетки). Отсюда оценка 3-го столбца = -3. Найденные оценки столбцов запишем под таблицей, найденные оценки строк — справа от таблицы.

После этого шага получаем следующую таблицу:

Таблица 19.

5	1 130	5					Оце н ки ст рок
	4			125
125	3	50
	-1	-3
О ц е н к и с т о л б ц о в

Известна оценка 3-го столбца и имеется незадействованная отмеченная клетка в этом столбце, поэтому можно найти оценку 3-й строки.

Оценка клетки (3,3) = оценка 3-й строки + оценка 3-го столбца + число в левом верхнем углу клетки (3,3).

0 = оценка 3-й строки -3 + 4 = 0. Отсюда оценка 3-й строки = -1.

Известна оценка 3-й строки и имеется незадействованная отмеченная клетка (3,4) в этой строке, поэтому можно найти оценку 4-го столбца.

Оценка клетки (3,3) = оценка 3-й строки + оценка 4-го столбца + число в левом верхнем углу клетки (3,4).

0 = -1 + оценка 4-го столбца + 5 = 0.

Оценка 4-го столбца = -4.

Известна оценка 4-го столбца и имеется незадействованная отмеченная клетка (2,4) в этом столбце, поэтому можно найти оценку 2-й строки.

Оценка клетки (2,4) = оценка 2-й строки + оценка 4-го столбца + число в левом верхнем углу клетки (2,4).

0 = -4 + оценка 4-го столбца + 8 = 0.

Оценка 5-го столбца = -4.

Известна оценка 2-й строки и имеется незадействованная отмеченная клетка (2,5) в этой строке, поэтому можно найти оценку 5-го столбца.

Оценка клетки (2,5) = оценка 2-й строки + оценка 5-го столбца + число в левом верхнем углу клетки (2,5).

0 = -4 + оценка 5-го столбца + 9 = 0.

Оценка 5-го столбца = -5.

Таблица 20.

5	1 130	5					Оце н ки ст рок
	4			125		-4
125	3	50				-1
	-1	-3	-4	-5
О ц е н к и с т о л б ц о в

Известна оценка 2-й строки и имеется незадействованная отмеченная клетка (2,5) в этой строке, поэтому можно найти оценку 5-го столбца.

Оценка клетки (2,5) = оценка 2-й строки + оценка 5-го столбца + число в левом верхнем углу клетки (2,5).

0 = -4 + оценка 5-го столбца + 9 = 0.

Оценка 5-го столбца = -5.

Известна оценка 3-й строки и имеется незадействованная отмеченная клетка (1,3) в этой строке, поэтому можно найти оценку 1-го столбца.

Оценка клетки (1,3) = оценка 3-й строки + оценка 1-го столбца + число в левом верхнем углу клетки (1,3).

0 = -1 + оценка 1-го столбца + 2.

Оценка 1-го столбца = -1.

Известна оценка 5-го строки и имеется незадействованная отмеченная клетка (4,5) в этой строке, поэтому можно найти оценку 4-й строки.

Оценка клетки (4,5) = оценка 4-й строки + оценка 5-го столбца + число в левом верхнем углу клетки 42,5).

0 = оценка 4-й строки -5 + 1.

Оценка 4-й строки = 4.

Найдены оценки всех строк и столбцов. После этого шага получаем таблицу 21.

Таблица 21.

5	1 130	5					Оце н ки ст рок
	4			125		-4
125	3	50				-1
-1	-1	-3	-4	-5
О ц е н к и с т о л б ц о в

Вычислим оценки всех клеток и составим матрицу оценок.

Оценки отмеченных клеток равны нулю.

Таблица 22.

Оценка клетки (1,1) = оценка 1-й строки + оценка 1-го столбца + число в левом верхнем углу клетки (1,1) = 0 -1 + 5 = 4.

Оценка клетки (1,4) = оценка 1-й строки + оценка 4-го столбца + число в левом верхнем углу клетки (1,4) = 0 -4 + 4 =0.

Оценка клетки (1,5) = оценка 1-й строки + оценка 5-го столбца + число в левом верхнем углу клетки (1,5) = 0 -5 + 5 = 0.

Оценка клетки (2,1) = оценка 2-й строки + оценка 1-го столбца + число в левом верхнем углу клетки (2,1) = -4 -1 + 3 = -2.

Оценка клетки (2,2) = оценка 2-й строки + оценка 2-го столбца + число в левом верхнем углу клетки (2,2) = -4 -1 + 4 = -1.

Оценка клетки (2,3) = оценка 2-й строки + оценка 3-го столбца + число в левом верхнем углу клетки (2,3) = -4 -3 + 5 = -2.

Оценка клетки (3,2) = оценка 3-й строки + оценка 2-го столбца + число в левом верхнем углу клетки (3,2) = -1 -1 + 3 = 1.

Оценка клетки (3,5) = оценка 3-й строки + оценка 5-го столбца + число в левом верхнем углу клетки (3,5) = -1 -5 + 6 = 0.

Оценка клетки (4,1) = оценка 4-й строки + оценка 1-го столбца + число в левом верхнем углу клетки (4,1) = 4 -1 + 4 = 7.

Оценка клетки (4,2) = оценка 4-й строки + оценка 2-го столбца + число в левом верхнем углу клетки (4,2) = 4 -1 + 5 = 8.

Оценка клетки (4,3) = оценка 4-й строки + оценка 3-го столбца + число в левом верхнем углу клетки (4,3) = 4 -3 + 6 = 7.

Оценка клетки (4,4) = оценка 4-й строки + оценка 4-го столбца + число в левом верхнем углу клетки (4,4) = 4 -4 + 7 = 7.

Получаем следующую матрицу оценок:

Таблица 23

-2	-1	-2

Так как матрица оценок содержит отрицательные числа (-2, -1 -2) наш план поставок является неоптимальным. Проведем его оптимизацию. Выбираем клетку с наименьшей оценкой. Это клетки (2,1) и (2,3). Оценка клеток равна -2. Наша задача — построить цикл пересчета. Выходя из клетки и двигаясь только по отмеченным клеткам, нужно вернуться в стартовую клетку. При этом запрещается делать два последовательных шага в одной строке или в одном столбце. Запрещается двигаться по диогонали. Например, подходит цикл (2,3)-(3,3)-(3,4)-(2,4)-(2,3).

Нарисуем этот цикл. Для каждой клетки указаны ее индексы и объем поставок.

Таблица 24.

5 +	8 – 20
4 – 50	5 +

Стартовой клетке (2,3) припишем знак «+». Двигаясь по циклу, чередуем знаки. Среди поставок в клетки со знаком «—» (это клетки (3,3), (2,4)) найдем минимальную; min (20, 50) = 20 (см. Табл. 24). После этого в клетках со знаком «—» уменьшим поставки на этот минимум, а в клетках со знаком «+» увеличим на этот минимум, Клетка (2,3) становится отмеченной. Если получена одна клетка с нулевой поставкой, то она становится пустой. У нас таких клеток одна — (2,4). Поэтому пустой объявим эту клетку. Если бы таких клеток было две и более, то пустой объявляется клетка с наибольшим тарифом (в остальные клетки были бы сделаны нулевые поставке, и они остались бы отмеченными, это делается для выполнения соотношения: число отмеченных клеток = число строк + число столбцов – 1). Получаем новый план поставок.

Таблица 25.

5	1 130	5					Оце н ки ст рок
	4	20		125		-4
125	3	30				-1
-1	-1	-3	-4	-5
О ц е н к и с т о л б ц о в

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

Для нового плана находим оценки строк и столбцов (см. Табл. 27). Затем получим матрицу оценок клеток:

Таблица 26.

				-2
				-2

Таблица 27.

5	1 130	5					Оце н ки ст рок
	4	20		125		-2
125	3	30				-1
-1	-1	-3	-4	-7
О ц е н к и с т о л б ц о в

План является неоптимальным, так как оценка клеток (1,5) и (3,5) меньше нуля. Строим для нее цикл пересчета. Например: (3,5)-(2,5)-(2,3)-(3,3)-(3,5).

Таблица 28.

5 + 20	9 – 125
4 –	6 +

Получаем новый план поставок.

Таблица 29.

5	1	5					Оце н ки ст рок
	4	50				-2
125	3			30
-3	-1	-3	-6	-7
О ц е н к и с т о л б ц о в

Для нового плана находим оценки строк и столбцов (см. Табл. 29). Затем получим матрицу оценок клеток:

Таблица 30.

			-2	-2
-2

План является неоптимальным, так как оценка клеток (2,1), (1,4), (1,5) меньше нуля. Строим для нее цикл пересчета. Например: (3,5)-(2,5)-(2,3)-(3,3)-(3,5).

Таблица 31.

3 +	9 – 95
2 –	6 +

Получаем новый план поставок.

Таблица 32.

5	1	5					Оце н ки ст рок
95	4	50				-2
30	3			125		-1
-1	-1	-3	-4	-5
О ц е н к и с т о л б ц о в

Для нового плана находим оценки строк и столбцов (см. Табл. 32). Затем получим матрицу оценок клеток:

Таблица 33.

План является оптимальным. Матрица оценок не содержит отрицательных чисел. Суммарные затраты на перевозку груза равны: 1x130 + 3x5 + 3x95 + 5x50 +2х30 + 5x95 +6x125 + 1х310 = 2275. В общем случае оптимальных планов может быть несколько.