Транспортная задача

 

,

.

Так как , то имеем закрытую транспортную задачу, n = 3, m = 5.

1 метод. Метод «северо-западного угла»

Таблица 2 заполняется, начиная с «северо-западного» угла, то есть с левой верхней клетки.

Дадим переменной x11 максимально возможное значение или, иными словами, максимально возможную поставку в клетку (1; 1) – «северо-западный» угол таблицы поставок: x11 = min{30, 20} = 50. После этого спрос первого потребителя полностью удовлетворён, в результате чего первый столбец таблицы поставок исключается из дальнейшего рассмотрения (до тех пор, пока опорный план не будет составлен полностью). Заполненные клетки будем перечёркивать по диагонали сплошной линией, а исключённые из дальнейшего рассмотрения – пунктирной линией; при этом предложение первого поставщика уменьшается на 30 ед. и составит 20 ед.

 

Таблица 2-Таблица метода «северо-западного» угла

База	Магазин										Запасы   продукции, ai
	В1		В2		В3		В4		В5
А1	30		20								50/20
		7		6		8		10		12
А2					55		5				60
		9		5		7		4		6
А3							15		25		40
		6		8		4		9		7
Спрос   на продукцию, bj	30		20		55		20		25		150

Теперь в таблице поставок 2 находим новый «северо-западный» угол – клетку (1; 2) и отправляем в неё максимально возможную поставку x11 = min{30, 20} = 50 и клетка (1; 2) перечёркивается сплошной линией. После этого мощность первого поставщика полностью использована, то есть клетки (2; 3), (2; 4), (3; 4), и (3;5) исключаются из рассмотрения и перечёркиваются пунктиром. В оставшейся таблице вновь находим «северо-западный» угол и отправляем туда максимально возможную поставку. И так далее.

В результате получаем опорный план, в котором заполненными (базисными) являются n + m – 2 = 5 + 3 – 2 = 6 клеток.

 

 

 

 

Таблица 3-Таблица метода «северо-западного» угла

База	Магазин										Запасы   продукции, ai
	В1		В2		В3		В4		В5
А1	30		20								50/20/-
		7		6		8		10		12
А2					55		5				60/5/-
		9		5		7		4		6
А3							15		25		40/25/-
		6		8		4		9		7
Спрос   на продукцию, bj	30/-		20/-		55/-		20/15/-		25/-		150

Этому плану соответствует значение целевой функции:

Fсз = 30·7+20·6+55·7+5·4+15·9+25·7 = 1045.

2 метод. Метод наименьших затрат

Согласно этому методу на каждом шаге заполняется клетка с минимальным коэффициентом затрат.

В таблице поставок 4 находим клетку с наименьшим коэффициентом затрат. Это клетка (3; 3) с коэффициентом затрат, равным 4 (если таких клеток несколько, то выбираем ту, в которую возможна максимальная поставка), причём x33 = min{40} = 0.

Таблица 4-Таблица метода наименьших затрат

База	Магазин										Запасы   продукции, ai
	В1		В2		В3		В4		В5
А1	30				15				5		50
		7		6		8		10		12
А2			20				20				60
		9		5		7		4		6
А3					40				20		40/-
		6		8		4		9		7
Спрос   на продукцию, bj	30		20		55		20		25		150

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

 

Таблица 5- Таблица метода наименьших затрат

База	Магазин										Запасы   продукции, ai
	В1		В2		В3		В4		В5
А1	30				15				5		50
		7		6		8		10		12
А2			20				20				60/40
		9		5		7		4		6
А3					40				20		40/-
		6		8		4		9		7
Спрос   на продукцию, bj	30/-		20/-		55		20		25		150

 

В оставшейся таблице 5 наименьший коэффициент затрат равен 4 и находится в клетке (2; 4), x24 = min{20, 60} = 40. При этом из рассмотрения выбывает второй столбец.

Продолжая заполнение таблицы шаг за шагом (табл. 6), получаем x22 = min{20, 40} = 20, x25 = min{20, 20} = 0, x11 = min{30} = 20, x13 = min{20, 15} = 5, x15{5}=0. В результате получаем опорный план, в котором заполненными (базисными) являются 6 клеток.

Таблица 6- Таблица метода наименьших затрат

База	Магазин										Запасы   продукции, ai
	В1		В2		В3		В4		В5
А1	30				15				5		50/20/-
		7		6		8		10		12
А2			20				20				60/40/20/-
		9		5		7		4		6
А3					40				20		40/-
		6		8		4		9		7
Спрос   на продукцию, bj	30/-		20/-		55/15/-		20/-		25/5/-		150

Соответствующее значение целевой функции равно:

Fнз = 30·7+20·5+ 15·8+40·4+20·4+5·12+20·6 = 850.

3 метод. Метод аппроксимации Фогеля

При определении опорного плана транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем строкам и всем строкам находим разность между двумя минимальными коэффициентами затрат. Эти разности записываем в специально отведённые для этого строку и столбец таблицы поставок 3. Среди полученных разностей выбираем максимальную. В строке (или столбце), которой данная разность соответствует, заполняем клетку с минимальным коэффициентом затрат.