Общий вид таблицы перевозок

Поставщик		Потребитель
		1	2	3	…	m
	Объем продукции	b1	b2	b3	…	bm
1	а1	x11	x12	x13	…	x1m
		c11	c12	c12		c1m
2	а2	x21 c21	х22 c22	x23 c23	…	x2m c2m
3	a3	x31 c31	x32 c32	x33 c33	…	x3m c3m
…	…	…	…	…	…	…
n	аn	xn1 cn1	xn2 cn2	xn3 cn3	…	xnm cnm

Так клетка с адресом (1,2), например, стоящая на пересечении 1-й строки и 2-го столбца, несет информацию о стоимости перевозки единицы продукта (c₁₂) и об объеме перевозимого груза (x₁₂) от первого поставщика ко второму потребителю.

Методы решения транспортной задачи

Общая схема решения транспортной задачи состоит из трех последовательных этапов:

1. формализация исходных данных (построение математической модели) (см. пункт 2);

2. анализ математической модели;

3. интерпретация результатов исследования математической модели.

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

а) построение первоначального плана перевозок;

б) проверка первоначального плана перевозок на оптимальность;

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

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

Таблица 2

Методы решения транспортной задачи

№ п/п	Наименование	Методы решения
1	Построение первоначального плана перевозок.	Метод северо-западного угла. Метод наименьшей стоимости.
2	Проверка на оптимальность плана перевозок, построение улучшенного Т-плана.	Метод потенциалов. Распределительный метод.

Построение первоначального т-плана методом северо-западного угла

Метод северо-западного угла является самым простым методом построения первоначального Т-плана.

Содержание метода:

1). Построим таблицу перевозок (Таблица 1).

2). Приведем задачу к сбалансированному виду, если это необходимо.

3). Выделим верхнюю левую клетку таблицы (l,k). Присвоим выбранной клетке объем поставкиx_l,k, равный минимальному из значенийа_l(объем продукта, имеющийся уl-го производителя) иb_k (объем продукта, необходимыйk-му потребителю), т.е.x_l,k=minа_l,b_k .

4). Рассмотрим случай, когда а_l > b_{k .} Эта ситуация означает то, что запросыk-гопотребителя полностью удовлетворены, а объем продукта, имеющийся уl-го производителя уменьшились на величину равнуюx_l,k. Следовательно необходимо вычеркнуть из таблицыk-й столбец и значениеа_l уменьшить наb_k.

В случае а_l < b_kпредполагается, что запас продуктаl-го производителя исчерпан, аk-употребителю необходимо доставить еще (b_k - а_l) объема продукта. Следовательно необходимо вычеркнуть из таблицы строку с номеромl, а значениеb_k уменьшить наа_l.

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

Замечание 4: Очевидно, что сумма произведения стоимости перевозки единицы продукта на величину поставки в выделенных клетках определяет общую стоимость перевозок продукта.

Рассмотрим на примере построение первоначального Т-плана методом севере-западного угла.

задача (*): На трех складах А, В, С находится соответственно 100, 130 и 170 усл. ед. одноименного груза, который необходимо доставить в четыре пункта потребления а, в, с, д в объеме 150, 120, 80, 50 усл.ед. соответственно. Затраты на перевозку груза приведены в таблице 3:

Таблица 3

Склады	Пункты - потребители
	а	б	с	д
А	3	5	7	11
В	1	4	6	2
С	5	8	12	7

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

1). Построим исходную таблицу:

Таблица 4

		а	б	с	д
		150	120	80	50
А	100	3	5	7	11
В	130	1	4	6	2
С	170	5	8	12	7

2). Данная задача является сбалансированной, так как объем груза, имеющийся на всех складах равен объему груза необходимому всем поставщикам:

=100+130+170 = 400 и= 150+120+80+50 = 400

3). -Выберем верхнюю левую клетку - (1;1). Укажем величину поставки x₁₁ = minа₁,b₁ =min100, 150 = 100. Это означает, что 100 усл.ед. груза отправили от первого поставщика (склад А) первому потребителю (пункта).

У первого поставщика (склад А) не осталось груза, поэтому первую строку таблицы вычеркнем.

Потребности первого потребителя сократились на 100 усл. ед. груза. Поэтому значение b₁ необходимо уменьшить на 100, т.е.b₁=150-100=50. Все изменения внесем в таблицу 5.

• Следующая клетка – (2;1). х₂₁ = minа₂,b₁=min130,50 = 50. Потребности первого потребителя полностью удовлетворены, поэтому вычеркиваем первый столбец таблицы. У второго поставщика (склад В) осталось еще 80 усл. ед. груза, т.е. а₂ =80 (Таблица 6).

• Выделяем клетку (2;2). х₂₂ = minа₂,b₂=min80, 120= 80. На складе В больше не осталось груза. Поэтому вычеркиваем вторую строку таблицы. Второму поставщику необходимо доставить ещеb₂= 120-80 = 40 усл.ед. груза (Таблица 7).

Таблица 5 Таблица 6

		а	б	с	д				а	б	с	д
		(150)	120	80	50				150	120	80	50
		+50							+0
А	(100) 0	3	5	7	11		А	(100) 0	3	5	7	11
		100							100
В	130	1	4	6	2		В	(130) 80	1	4	6	2
									50
С	170	5	8	12	7		С	170	5	8	12	7

• Следующая выделенная клетка – (3;2). Соответствующая ей величина поставки будет равна х₃₂ = minа₃,b₂=min170, 40=40. Это означает, что второму потребителю (пунктб) доставили 40 усл.ед груза, и его потребность удовлетворена. Это означает, что 2-й столбец таблицы необходимо вычеркнуть. На складе С осталось еще а₃=170-40 = 130 усл.ед. груза (Таблица 8).

Таблица 7 Таблица 8

		а	б	с	д				а	б	с	д
		(150)	(120)	80	50				(150)	(120)	80	50
		+0	+40						+0	+0
А	(100) 0	3	5	7	11		А	(100) 0	3	5	7	11
		100							100
В	(130) 0	1	4	6	2		В	(130) 0	1	4	6	2
		50	80						50	80
С	170	5	8	12	7		С	(170) 130	5	8	12	7
										40

• Выделим верхнюю левую клетку из числа еще не вычеркнутых клеток – (3;3). Ей соответствует поставка х₃₃ = minа₃,b₃=min130, 80=80. В пунктбдоставили весь необходимый груз - вычеркиваем третий столбец таблицы. На складе С осталось а₃=130-80 = 50 усл.ед. груза (Таблица 9).

• В таблице осталась последняя не вычеркнутая клетка – (3;4). Выделим ее. х₃₄ = minа₃,b₄=min50, 50=50.Оставшийся объем груза равен объему, необходимому последнему потребителю (Таблица 10).

Таблица 9 Таблица 10

		а	б	с	д				а	б	с	д
		(150)	(120)	(80)	50				(150)	(120)	(80)	(50)
		+0	+0	+0					+0	+0	+0	+0
А	(100) 0	3	5	7	11		А	(100) 0	3	5	7	11
		100							100
В	(130) 0	1	4	6	2		В	(130) 0	1	4	6	2
		50	80						50	80
С	(170) 50	5	8 40	12 80	7		С	(170) 0	5	8 40	12 80	7 50

Первоначальный Т-план построен. На заключительном этапе построения первоначального плана перевозок полезно проверить его на наличие ошибок. Для этого:

а). Суммируем величины всех поставок в каждой строке, результат должен совпадать с имеющимся объемом груза у соответствующего поставщика:

1 строка (склад А): 100=100;

2 строка (склад В): 130 = 50+80;

3 строка (склад С): 170 = 40+80+50.

б). Суммируем величины всех поставок в каждом столбце, результат должен совпадать с объемом груза, необходимым соответствующему потребителю:

1 столбец (пункт а): 150 =100+50;

2 столбец (пункт б): 120 =80+40;

3 столбец (пункт с): 80 =80;

4 столбец (пункт д): 50 =50.

Проверка показала правильность построения первоначального Т-плана. Сделаем выводы:

1). Построенный план перевозок заключается в доставке 100 и 50 усл.ед. груза со склада А и В соответственно в пункт а; 80 и 40 усл.ед. груза со склада В и С соответственно в пункт б; 80 усл.ед. груза со склада С в пункт с и 50 усл.ед. груза со склада С в пункт д.

2). Суммарные затраты на перевозку груза составляют:

L=3*100+1*50+4*80+8*40+12*80+7*50 = 2300 (ден.ед).

Построенный Т-план необходимо проверить на оптимальность.