Глава 2.Определение оптимального плана транспортных задач

2.1.Решение транспортной задачи методом моди

Для решения транспортной задачи разработано несколько методов. Наиболее широкое применение находят методы потенциалов (метод МОДИ), Хичкока, Креко. Идея метода потенциалов была высказана Л. В. Канторовичем в 1940 г. В 1951 г. американский ученый Дж. Д. Данциг предложил ту же идею, назвав ее модифицированным распределительным методом (МОДИ). Идея метода потенциалов или метода МОДИ, заключается в том, что для проверки допустимого базисного плана на оптимальность вводятся числа, называемые потенциалами.

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

(2.1)

где – значение потенциала строки;

– значение потенциала столбца.

Потенциалы незагруженных (свободных) клеток определяются по формуле (2.2).

(2.2)

где d_ij – потенциал свободной клетки.

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

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

Каждому поставщику поставим в соответствие потенциал (i = 1,..,m), каждому потребителю поставим в соответствие потенциал (j = 1,..,n). Число базисных переменных в опорном плане n+m-1, а число неизвестных потенциалов n+m. Для нахождения потенциалов, один потенциал нужно принять за свободный равный, например, нулю. За свободный можно принять потенциал строки (или столбца), в которой имеется наибольшее число базисных переменных.

Алгоритм метода: Найти опорный план задачи любым методом (минимальной стоимости, северо – западного угла, двойного предпочтения, методом Фогеля). Принять любой потенциал равным любому произвольному значению, например нулю. По базисным переменным хij рассчитать потенциалы из системы уравнений (2.3). (2.3) Для свободных переменных xpq (пустых клеток) рассчитать оценки по формуле (2.4). (2.4) Оценки записываются в левом нижнем углу транспортной таблицы. Если все оценки неотрицательны, то есть выполняется условие (2.5), (2.5) то план является оптимальным и осуществляется переход на пункт 11. Если условие (2.5) не выполняется, перейти на пункт 6. В базис вводится свободная переменная , которой соответствует наименьшая отрицательная оценка (наибольшая по модулю среди отрицательных) (2.6) помечаем клетку АkВl значком ˝+˝ – это начало цепочки перераспределения. Строим замкнутую цепочку, в которую входит по две базисные переменные в каждой строке и каждом столбце. Направление обхода цепочки не влияет на решение, т.е. мы можем в начале перемещаться по строке базисной переменной, либо по столбцу . Так как переменная хkl вводится в базис, то ее значение будет увеличиваться на х. Чтобы не нарушить ограничение по k-ой строке ( ), выбранную базисную переменную в строке k надо будет уменьшить на х, поэтому данную клетку помечают ˝˝. Находим величину перераспределения по цепочке х, из переменных, помеченных знаком ˝˝ в цепочке по формуле (2.7). (2.7) К переменным, помеченным ˝+˝, прибавляем х, из переменных, помеченных ˝˝, вычитаем х. Уменьшаемая переменная, значение которой совпадает с х, исключается из базиса, так как она стала равной нулю, т.е. небазисной переменной. Если таких переменных несколько, исключаем только одну. Переход на пункт 2. Расчет транспортных расходов.

Пример 2.0:

Таблица 19

Поставщики	Ui Vj	Потребители										ai
		В1		В2		В3		В4		В5
		V1=3		V2=8		V3=12		V4=13		V5=13
А1	U1=-12		10		7		4		1		4	100
								100
		19		11		4				3
А2	U2=-1		2	Ө	7		10		6		11	250
		200		50
						-1		-6		-1
А3	U3=-11		8		5		3	Ө	2		2	200
								0		200
		16		8		2
А4	U4=0		11		8		12		16	Ө	13	300
				150		100				50
		8						3
bj		200		200		100		100		250		850

Получим опорный план методом минимальной стоимости (см. раздел 1.4.2).

Рассчитаем затраты на перевозку опорного плана доставки:

=100· 1 + 200· 2 + 150·7 + 50·7 + 100·3 + 200· 2 + 150· 8 + 100·12 +50· 13 = 4300 (ед. стоимости).

Примем потенциал U₄=0, так как строке А₄ соответствует наибольшее число базисных переменных. Зная u₄, по переменной х₄₂ можно определить потенциал v₂ из уравнения (2.1): U₄+V₂=8  V₂=8  0 = 8;

для х₄₃ можно составить уравнение:

U₄+V₃=12  V₃=12  0=12;

для х₄₅: U₄+V₅=13  V₅=13  0=13;

для х₃₅: U₃+V₅=2  U₃=2 V₅=213=11;

для х₃₄: U₃+V₄=2  V₄=2  U₃=2+11=13;

для х₂₂: U₂+V₂=7  U₂=7V₂=7  8=1;

для х₂₁: U₂+V₁=2  V₁=2U₂=2+1=3;

для х₁₄: U₁+V₄=1  U₁=1V₄=113=12;

для х₃₅: U₃+V₅=2  U₃=2V₅=213=11.

Рассчитываем оценки для свободных переменных по формуле (2.2)

т.е. х₂₄ вводится в базис. Клетку А₂В₄ помечаем знаком ˝+˝. Клетку А₃В₄ помечаем ˝˝, клетку А₃В₅ помечаем ˝+˝, А₄В₅ помечаем ˝˝, А₄В₂ помечаем ˝+˝, А₂В₂ помечаем ˝˝. Получаем замкнутую цепочку:

Наименьшее значение из переменных, помеченных знаком ˝˝ является 0 в клетке А₃В₄, его вычитаем из клеток помеченных ˝˝, прибавляем к клеткам, помеченным ˝+˝ .

Получаем новое закрепление, приведенное в табл. 20. Далее следует вводить переменную , которой соответствует максимальное по модулю значение среди отрицательных оценок.

Таблица 20

Поставщики	Ui Vj	Потребители
		В1		В2		В3		В4		В5
		V1=3		V2=8		V3=12		V4=7		V5=13
А1	U1=-6		10		7		4	Ө	1		4
								100
		13		5		-2				-3
А2	U2=-1		2	Ө	7		10		6		11
		200		50				0
						-1				-1
А3	U3=-11		8		5		3		2		2
										200
		16		8		2		6
А4	U4=0		11		8		12		16	Ө	13
				150		100				50
		8						9

Получаем замкнутую цепочку:

Таблица 21

Поставщики	Ui Vj	Потребители
		В1		В2		В3		В4		В5
		V1=-3		V2=0		V3=4		V4=1		V5=4
А1	U1=0		10		7		4		1		4
						0		50		50
		13		7
А2	U2=5		2		7		10		6		11
		200						50
				2		1				2
А3	U3=-2		8		5		3		2		2
										200
		13		7		1		3
А4	U4=8		11		8		12		16		13
				200		100
		6						7		1

Данный план является оптимальным, так как выполняется условие 2.5, все оценки являются неотрицательными.

Затраты на перевозку составляют:

= 50·1 + 50·4 + 200·2 + 50·6 + 0·4 + 200·2 + 200·8 + 100·12 = 4150 (ед. стоимости).

Пример 2.0:

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

Рис. 2.3. Сеть

Чтобы учесть транзитные перевозки, в каждом исходном пункте назначе­ния предусмотрен дополнительный буфер емкостью В. По определению, емкость буфера должна быть не меньше суммарного объема производства (или спроса) стандартной (сбалансированной) транспортной задачи, т.е.

Стоимости в расчете на единицу груза оцениваются на основании данных о маршрутах, соединяющих исходные пункты с пунктами назначения в модели с промежуточными пунктами. Очевидно, что коэффициенты стоимости перевозки между первоначально заданными исходными пунктами и пунктами назначения (см. заштрихованную область сети на рис. 2.1) остаются такими же, как и в при­мере рассмотренном выше. Заметим также, что стоимость перевозки из некото­рого пункта в него же (скажем, из Денвера в Денвер) равна нулю, и стоимость перевозки может меняться в зависимости от направления движения (например, маршрут Детройт - Денвер может отличаться по стоимости от маршрута Денвер - Детройт, если используются различные режимы перевозок).

Таблица 22

	Лос-Анджелес	Детройт	Новый Орлеан	Денвер	Майами	ai
Лос-Анджелес	0	130	90	80	215	4700
	3700			1000
Детройт	135	0	101	100	108	5200
		3700	200	1300
Новый Орлеан	95	105	0	102	68	4900
			3700		1400
Денвер	79	99	110	0	205	3700
				3700
Майами	200	107	72	205	0	3700
					3700
bj	3700	3700	3700	6000	5100

На табл. 22 представлено оптимальное решение рассмотренной выше зада­чи с промежуточными пунктами, в которой емкость буфера В равна 3700 авто­мобилям. Заметим, что коэффициенты стоимости перевозок между первоначаль­но заданными исходными пунктами (Лос-Анджелес, Детройт и Новый Орлеан) и пунктами назначения (Денвер и Майами). Предполагается, что остальные коэф­фициенты оцениваются в зависимости от расстояния и режима перевозок.

Рис. 2.4. Схема распределения

Из табл. 22 видно, что диагональные элементы получены в результате ис­пользования буфера. Они не дают никакой информации об окончательном реше­нии. Недиагональные элементы обеспечивают получение решения, представ­ленного на рис. 2.2. Из Детройта в Майами перевозка производится через проме­жуточный пункт в Новом Орлеане, куда поступает 200 автомобилей. Все другие перевозки осуществляются непосредственно с заводов в центры распределения.

Помимо рассмотренной выше возможны ситуации, при которых имеет место транзитная перевозка продукции. Например, в задаче фирмы MG (пример 1.1) конечные пункты назначения, куда поступают автомобили, могут представлять отдельных продавцов, а не крупные центры распределения. В целях упрощения предположим, что имеется лишь пять продавцов, которые получают свои заказы из центров распределения в Денвере и Майами. На рис. 2.3 центры распределения изображены в виде временных складов, из которых автомобили попадают в конечные пункты назначения. Соответствующие величины, характеризующие спрос пяти продавцов, составляют 800, 500, 750, 1000 и 50 автомобилей.

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

Рис. 2.5

Поскольку центры распределения (вершины 4 и 5 на рис. 2.3) являются единственными промежуточными пунктами, и каждый из них может рассматриваться и как пункт назначения, и как исходный пункт. С другой стороны, заводы играют роль исходных пунктов, а продавцы - пунктов назначения. Построенная с учетом этого модель с промежуточными пунктами приведена в табл. 23.

Таблица 23

	4	5	6	7	8	9	10
1								1000
2								1500
3								1200
4								3700
5								3700
	3700	3700	800	500	750	1000	650

Заметим, что в центрах распределения (вершины 4 и 5) емкость буфера В, равная 3700 автомобилей, прибавляется к соответствующим величинам объема производства и спроса. Очевидно, что никакой буферной емкости не требуется добавлять к величине объема производства того или иного завода или величине, характеризующей спрос продавцов. Напомним, что буфер вводится в тех пунктах, которые могут рассматриваться и как исходные пункты, и как пункты назначения, т.е. в ситуации, когда перевозка осуществляется через эти пункты транзитом. На рис 2.3 видно, что прямые перевозки с завода продавцу не разрешены. В табл. 23 это ограничение представлено запрещенными (заштрихованными) ячейками. При численном решении задачи запрещенному маршруту соответствует очень большая стоимость С_ij=М, записанная в соответствующей ячейке.

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

Таблица 24

	1	2	3	4	5	6	7	8	9	10
1											1000
2											1500
3											1200
4											3700
5											3700
	3700	3700	3700	3700	3700	800	500	750	1000	650