6. Процесс оптимизации полученного опорного плана методом потенциалов.

Проверим оптимальность опорного плана.

В таблице, максимальное количество перевозок опорного плана – во втором столбце. Назначаем второму столбцу нулевую псевдоцену, v2  0. Поскольку в этом столбце все клетки включены в опорный план, можно составить систему, в которой найдем псевдостоимость u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij.

	B1 25		B2 20		B3 25		B4 15			u
A1 30	7	5	14	7	15	3	7	5	7
			8		15		7
A2 28	17	3	10	7	12	8	5	5	7
	17		6				5
A3 27	15	5	8	4	12	6	∞	7	4
	8		6		10		3
v	4		0		4		3

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

	B1 25		B2 20		B3 25		B4 15			u
A1 30	7	5	14	7	15	3	7	5	7
		11	8		15		7
A2 28	17	3	10	7	12	8	5	5	7
	17		6			11	5
A3 27	15	5	8	4	12	6	∞	7	4
	8		6		10		3
v	4		0		4		3

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

p11=6 – Может быть найден цикл переноса с ценой равной -6

p23=3 – Может быть найден цикл переноса с ценой равной -3

В нашей таблице, как видим, таких клеток две: (1,1) и (2,3).

Ищем цикл для ячейки (1,1), но с учётом ограничений. Самый оптимальный цикл: (3,1)→(1,1)→(1,2)→(3,2) с переносом 2 единиц. Выполним перенос перевозок и получим план, представленный в таблице ниже.

	B1 25		B2 20		B3 25		B4 15			u
A1 30	7	5	14	7	15	3	7	5	7
		[+]	8	[-]	15		7
A2 28	17	3	10	7	12	8	5	5	7
	17		6				5
A3 27	15	5	8	4	12	6	∞	7	4
	8	[-]	6	[+]	10		3
v	4		0		4		3

	B1 25		B2 20			B3 25			B4 15
A1 30	7	5		14	7		15	3		7	5
	2			6			15			7
A2 28	17	3		10	7		12	8		5	5
	17			6						5
A3 27	15	5		8	4		12	6		∞	7
	6			8			10			3

Цена плана:

Lф = 2*5+6*7+15*3+7*5+17*3+6*7+5*5+6*5+8*4+10*6+3*7= 393 единиц.

В результате цена плана уменьшилась на 6 единиц.

Если рассчитать потенциал для (2,3), то окажется, что есть ещё другие варианты циклов.

	B1 25		B2 20		B3 25		B4 15			u
A1 30	7	5	14	7	15	3	7	5	0
	2		6		15		7
A2 28	17	3	10	7	12	8	5	5	0
	17		6				5
A3 27	15	5	8	4	12	6	∞	7	3
	6		8		10		3
v	5		7		3		5

Но, учитывая ограничения, все другие вариации распределения будут только увеличивать цену плана. Для достоверности проверим результат в Excel:

Поиск решения в Excel доказал, что это самый оптимальный вариант плана, учитывая ограничения.

Ответ:

Lф (без ограничений) = 319

Lф (с ограничениями + метод мин.стоимости) = 399

Lф (с ограничениями + оптимизация методом потенциалов) = 393