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

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

 

Таблица 7-Исходнаяя таблица метода аппроксимации Фогеля

	Пункты назначения										ai	Разности по строкам
ПО	В1		В2		В3		В4		В5			I	II	III	IV	V	VI
А1											50
		7		6		8		10		12
А2											60
		9		5		7		4		6
А3											40
		6		8		4		9		7
bj	30		20		55		20		25		150
Разности по столбцам

Первый этап. Для каждой строки и каждого столбца вычисляем разности между минимальными коэффициентами затрат (табл. 8).

 

Таблица 8-Таблица метода аппроксимации Фогеля

	Пункты назначения										ai	Разности по строкам
ПО	В1		В2		В3		В4		В5			I	II	III	IV	V	VI
А1											50	1
		7		6		8		10		12
А2											60/40	1
		9		5		7		4		6
А3					40						40/-	2
		6		8		4		9		7
bj	30		20		55		20		25		150
Разности по столбцам	1		1		3		5		1

 

В строке А3 минимальный коэффициент затрат равен 4, а следующий за ним равен 5, разность между ними 5 – 4 = 1. В строке А3 разность равна 9 – 4 = 2, и так далее. Вычислив все разности, видим, что наибольшая из них соответствует строке А2. В этой строке минимальный коэффициент затрат находится в клетке (2; 4) и равен 4. Отправим в эту клетку максимально возможную поставку x24 = min{20;60} = 40. При этом потребности пятого потребителя полностью удовлетворены, и он исключается из рассмотрения, а запасы пункта А1 равны 40 – 40 = 0.

Второй этап. Снова вычисляем разности между минимальными коэффициентами затрат (табл. 9) и видим, что наибольшая из них соответствует строке А2. В этой строке минимальный коэффициент затрат находится в клетке (2; 4) и равен 4. Отправим в эту клетку максимально возможную поставку x24 = min{20, 60} = 40. При этом потребности первого потребителя полностью удовлетворены, и он исключается из рассмотрения, а запасы пункта А2 равны 60 – 20 = 40.

 

Таблица 9-Таблица метода аппроксимации Фогеля

	Пункты назначения										ai	Разности по строкам
ПО	В1		В2		В3		В4		В5			I	II	III	IV	V	VI
А1											50	1	2
		7		6		8		10		12
А2							20				60/40	1	1
		9		5		7		4		6
А3					40						40/-	2	-
		6		8		4		9		7
bj	30		20		55		20		25		150
Разности по столбцам	1		1		3		5		1
	1		1		3		-		6

 

Продолжая итерационный процесс (табл. 10), последовательно заполняем клетки (2; 2), (2; 5), (1; 1), (1; 3), (1; 5) поставками x22 = min{40, 20} = 20, x25 =min{40, 20} = 20, x11 = min{50,30} = 20, x13 = min{20, 15} = 5, x15 {5}= 0.

Отметим, что на этапе V появляются строка и столбец, у которых разности максимальны. Поэтому выбирает клетку с минимальным коэффициентом затрат. В данном случае таких клеток две – (3; 3) и (2; 4). Нас интересует та, в которую можно отправить максимально возможную поставку, то есть клетка (1; 1).

 

 

 

 

Таблица 10-Таблица метода аппроксимации Фогеля

	Пункты назначения										ai	Разности по строкам
ПО	В1		В2		В3		В4		В5			I	II	III	IV	V	VI
А1	30				15				5		50/20/5/-	1	2	1	1	2
		7		6		8		10		12							-
А2			20				20		20		60/40 /-	1	1	1	1	1
		9		5		7		4		6							-
А3					40						40/-	2	-	-	-	-	-
		6		8		4		9		7
bj	30		20		55		20		25		150
Разности по столбцам	1		1		3		5		1
	1		1		3		-		6
	2		1		1		-		6
	1		-		1		-		-
	-		-		1		-		12
	-		-		-		-		-

 

В результате получаем опорный план, в котором заполненными (базисными) являются 6 клеток.

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

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

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

Методом наименьших затрат получен опорный план:

,   Fo =850 .

Согласно методу потенциалов каждой строке i и каждому столбцу j ставятся в соответствие числа ui, vj (потенциалы). Для каждой базисной переменной xij потенциалы ui, vj удовлетворяют уравнению:

cij + ui + vj = 0.

 

Так как базисных переменных n + m – 1 = 7, а потенциалов  n+m = 8, то присвоим одному из потенциалов произвольное значение (например, u1 = 0) и вычислим значения остальных потенциалов:

Результаты вычислений занесём в таблицу 11.

 

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

ПО	ПН										ui
	В1		В2		В3		В4		В5
А1	30				15				5		0
		7		6		8		10		12
А2			20				20		20		-6
		9		5		7		4		6
А3					40						-4
		6		8		4		9		7
vj	7		11		8		10		12