1.1.Метод хичкока

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

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

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

Наибольшая потенциальная клетка получает загрузку, чтобы это сделать, необходимо перераспределить груз в таблице. Это выполняется следующим образом: количество загруженных клеток в предыдущем шаге должно равняться m+n-1, если количество загруженных клеток менее m+n-1, то недостающее число клеток получают путем загрузки соответствующего количества клеток нулями. Клетка, в которой поставлена загрузка равная 0, считается загруженной. Для наиболее потенциальной клетки строится контур. Строится контур так, чтобы все углы кроме одного располагались в загруженных клетках, а один единственный находился в свободной наиболее потенциальной клетке. При соблюдении этого правила для каждой свободной клетки можно построить только один единственный контур. Определяются положительные и отрицательные углы контура, считается, что первый положительный угол лежит в свободной клетке, для которой построен контур, отрицательные и положительные углы чередуются, и их количество должно быть равно. Выявляется наименее загруженная клетка, занятая отрицательным углом в нашем контуре. Количество груза указанное в этой клетке отнимается из всех клеток с отрицательными углами и прибавляется во все клетки с положительными углами. В результате одна или несколько ранее загруженных клеток становятся свободными, а наиболее потенциальная клетка становится загруженной.

Таблица № 4

ГО	ГП														вывоз,т	потенциал
	Б1		Б2		Б3		Б4		Б5		Б6		Б7
А1	1	7	9	14	0	5	6	9		5		9		4	60	0
										60			0
А2		5	3	7		4		2	3	7		2		3	210	1
	60				10		20				60		60
А3	2	7		4	4	8		2	5	9	2	4	4	7	110	1
			40				70
А4	7	15	1	8		7	5	10	10	17	7	12	8	14	40	-2
					40
ввоз, т	60		40		50		90		60		60		60
потенциал	-6		-5		-5		-3		-5		-3		-4

L(x)= 60*5+4*0+60*5+10*4+20*2+60*2+60*3+40*4+70*2+40*7=1560 т*км

Условие m+n-1 соблюдается- 7+4-1=10.

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