Многоэтапные транспортные задачи

Существуют два типа много этапных задач:

1) производственные мощности промежуточных звеньев меньше либо равны мощности начального и конечного звеньев;

2) мощность промежуточных звеньев превышает мощность начального и конечного звеньев.

Задачи первого типа не отличаются от однопродуктовых. Такая задача разбивается на блоки и решение осуществляется по блокам.

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

Пример. С трех глиняных карьеров А_1, А₂ и А₃ поступает глина на четыре кирпичных завода В₁, В₂, В₃ и В₄. Кирпичные заводы поставляют свою продукцию на две стройки С₁ и С₂. Данные о мощностях и расстояния между объектами приведены в табл. 2.6.

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

Таблица 2.6

Исходная таблица мощностей и расстояний

Потребители, поставщики	В1=35	В2=55	В3=60	В4=50	Потребители, поставщики	С1=100	С2=80
А1=50	1	2	3	4	В1=35	1	2
А2=40	3	2	4	5	В2=55	3	4
А3=90	4	7	2	3	В3=60	2	5
					В4=50	3	1

Особого внимания заслуживают клетки, которые находятся на пересечении одноименных строк и столбцов – это клетки фиктивной диагонали. Внутри них оценка затрат равна 0. По экономическому смыслу груз, размещенный в этих клетках, означает неиспользованную мощность предприятия. Все остальные клетки заштриховываются. После этого задача решается методом потенциала. Кратко рассмотрим механизм решения подобных задач на примере (табл. 2.7).

Пример

Таблица 2.7

Исходное распределение поставок многоэтапной задачи

Потребители, поставщики	В1=35		В2=55		В3=60		В4=50		С1=100		С2=80
А1=50	35	1	15	2		3		4
А2=40		3	40	2	0	4		5
А3=90		4		7		2		3
					60		30
В1=35		0								1		2
									35
В2=55				0						3		4
									55
В3=60						0				2		5
					20				10		50
В4=50								0		3		1
											30

После построения опорного плана одним из базовых методов (северо-западного угла или наименьшей стоимости) приступаем к оптимизации. Для этого строим систему потенциалов (табл. 2.8).

Таблица 2.8