Метод северо-западного угла

Суть: Заполнение таблицы ТЗ начинается с левого верхнего угла //обычно дает наиболее дальний от оптимального способ решения

Метод аппроксимации Фогеля, построение начального опорного плана тз

	В1		В2			В3			В4		Ai		Разности по строкам
A1		11			5			4		2		80		4-2=2
A2		1			4			5		9		170		1-4=3
A3		9			8			7		10		150		8-7=1
bi	70		60			180			90		(400)
	1-9=8		5-4=1			4-5=1			2-9=7

1. Вычислим разности между соседними мин тарифами в строке и столбце

2. Из всех значений разницы выберем максимальное значение. В данной строке/столбце выберем минимальную стоимость

	В1		В2		В3		В4			Ai		Разности по строкам
A1		11		5		4			2		80		4-2=2
A2		1		4		5			9		170		1-4=3
A3		9		8		7			10		150		8-7=1
bi	70		60		180		90			(400)
	2)1-9=8		5-4=1		4-5=1		2-9=7

3. Вписываем перевозку

	В1		В2		В3		В4		Ai	Разности по строкам
A1		11		5		4		2	80	4-2=2	2	-	-	-	-
							80
A2		1		4		5		9	170-70=100	1-4=3	1
	3)70
A3		9		8		7		10	150	8-7=1	1
bi	70-70=0		60		180		90-80=10		(400)
	1-9=8		5-4=1		4-5=1		2-9=7
	-		1		1		7
	-
	-
	-
	-

	В1		В2		В3			В4			Ai		Разности по строкам
A1		11		5			4			2		80		4-2=2		2		-		-		-		-
									80
A2		1		4			5			9		170-70=100 40 0		1-4=3		1		1		4		-		-
	70		60			40
A3		9		8			7			10		150		8-7=1		1		1		3		3		-
						140			10
bi	70-70=0		60-60=0		180 140			90-80=10			(400)
	1-9=8		5-4=1		4-5=1			2-9=7
	-		1		1			7
	-		4		2			1
	-		-		2			1
	-		-		-			1
	-		-		-			-

Необходимо проверить вырожденность плана (план в котором n+m-1 – число занятых клеток называется невырожденым. Если это не так (число занятых клеток меньше), то план вырожден и тогда выбирают дополнительно свободные клетки с мин тарифами, которые называются условно занятыми, таким образом, чтобы суммарное число занятых клеток было n+m-1)

Набатова Дарья Сергеевна (прикладная математика) nabatova805@mail.ru