Метод потенциалов.

Имея опорный план перевозок, в методе потенциалов выполняют анализ клеток матрицы плана перевозок. Все заполненные клетки матрицы перевозок называются базисными, незаполненные- свободными. За опорный план перевозок возьмем план, полученный методом «северо-западного угла».

Стоимость перевозки				производство
6	5	8	7	14
3	6	4	2	12
9	1	3	6	8
10	14	6	4
потребление

10	4			14
	10	2		12
		4	4	8
10	14	6	4

Суммарная стоимость перевозок опорного плана = 184.

Базисные клетки опорного плана – а11 а12, а22, а23, а33, а34; свободные- а13,а14,а21,а24,а31,а32. Для каждой свободной клетки можно построить замкнутый контур и перераспределить ресурсы между поставщиками и потребителями. Отличие этого метода состоит в том, что определяется потенциал каждой клетки и в зависимости от значения этого потенциала, выполняется перемещение только по одному контуру.

	Потенциалы vj				производство
Потенциалы ui	6	5	8	7		14
	3	6	4	2		12
	9	1	3	6		8
	10	14	6	4
	потребление

Для вычисления потенциалов в матрицу плана перевозок добавляют строку сверху и столбец слева.

Для определения потенциалов строк и столбцов используют формулу cij=ui+vj, подставляя в нее значения из базисных клеток. Для начала выполнения расчетов надо потенциал одной строки = 0. Затем, используя указанную формулу, выполнить остальные вычисления. Примем за 0 потенциал первой строки. U1=0 Тогда v1=c11-u1=6-0=6. Далее выбираем те базисные клетки, для которых уже имеется один потенциал и определяем следующий потенциал. Можно определить потенциал второго столбца v2=c12-u1=5-0=5

	6	5		8		7		14
	3	6		4		2		12
	9	1		3		6		8
	10	14		6		4

	6		5		3		6
0	10	4						14
1		10		2				12
0				4		4		8
	10	14		6		4

	6		5		3		6
0				-5		-1		14
1	4					5		12
0	-3	4						8
	10	14		6		4

Матрица стоимостей опорный план оценки свободных клеток

	10	4						14
		10		2				12
				4		4		8
	10	14		6		4

	6		5		-2		1
0	10	4						14
1		10				2		12
5				6		2		8
	10	14		6		4

Для свободных клеток оценки вычисляются по формуле ui+vj-cij<=0. Если оценки всех свободных клеток отрицательны или =0 , то опорный план оптимальный. Если хотя бы одна оценка >0, то относительно этой свободной клетки строят замкнутый контур и выполняют перераспределение ресурсов. Если несколько свободных клеток имеют оценки >0, то замкнутый контур строят для свободной клетки с наибольшим значением оценки. Для нашего примера наибольшая положительная оценка принадлежит а24. Составим для нее замкнутый контур а24 а34 а33 а23 и переместим ресурсы. Заново определим потенциалы и оценки

Опорный план перераспределение ресурсов оценки свободных клеток

	6		5		-2		1
0				-10		-6		14
1	4			-5				12
5	2	9						8
	10	14		6		4

	10	4						14
		10				2		12
				6		2		8
	10	14		6		4

	6		5		7		1
0	10	4						14
1		8				4		12
-4		2		6				8
	10	14		6		4

	6		5		7		1
0				-1		-6		14
1	4			4				12
-4	-7					-9		8
	10	14		6		4

Наибольшая положительная оценка принадлежит а32, поэтому строим замкнутый контур а32 а22 а24 а34 и переместим ресурсы. Заново определим потенциалы и оценки

Опорный план перерасределение ресурсов оценки свободных клеток