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

Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 9*49 + 10*29 + 6*78 + 40*16 + 19*29 + 28*60 + 39*21 + 50*5 = 5139
4. Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=9	v2=-1	v3=-13	v4=10	v5=21
u1=0	9[49]			10[29]
u2=19			6[78]		40[16]
u3=-2					19[29]
u4=29		28[60]		39[21]	50[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij
Выбираем максимальную оценку свободной клетки (4;1): 30
Для этого в перспективную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

						Запасы
	9[49][-]			10[29][+]
			6[78]		40[16]
					19[29]
	30[+]	28[60]		39[21][-]	50[5]
Потребности

Цикл приведен в таблице (4,1; 4,4; 1,4; 1,1;).
Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 4) = 21. Прибавляем 21 к объемам грузов, стоящих в плюсовых клетках и вычитаем 21 из Х _ij, стоящих в минусовых клетках. В результате получим новый опорный план.

						Запасы
	9[28]			10[50]
			6[78]		40[16]
					19[29]
	30[21]	28[60]			50[5]
Потребности

4. Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=9	v2=7	v3=-5	v4=10	v5=29
u1=0	9[28]			10[50]
u2=11			6[78]		40[16]
u3=-10					19[29]
u4=21	30[21]	28[60]			50[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij
Выбираем максимальную оценку свободной клетки (1;5): 18
Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

						Запасы
	9[28][-]			10[50]	18[+]
			6[78]		40[16]
					19[29]
	30[21][+]	28[60]			50[5][-]
Потребности

Цикл приведен в таблице (1,5; 1,1; 4,1; 4,5;).
Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 5) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Х _ij, стоящих в минусовых клетках. В результате получим новый опорный план.

						Запасы
	9[23]			10[50]	18[5]
			6[78]		40[16]
					19[29]
	30[26]	28[60]
Потребности

4. Проверим оптимальность опорного плана. Найдем предварительныепотенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=9	v2=7	v3=-16	v4=10	v5=18
u1=0	9[23]			10[50]	18[5]
u2=22			6[78]		40[16]
u3=1					19[29]
u4=21	30[26]	28[60]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij
Выбираем максимальную оценку свободной клетки (1;2): 5
Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

						Запасы
	9[23][-]	5[+]		10[50]	18[5]
			6[78]		40[16]
					19[29]
	30[26][+]	28[60][-]
Потребности

Цикл приведен в таблице (1,2; 1,1; 4,1; 4,2;).
Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 23. Прибавляем 23 к объемам грузов, стоящих в плюсовых клетках и вычитаем 23 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

						Запасы
		5[23]		10[50]	18[5]
			6[78]		40[16]
					19[29]
	30[49]	28[37]
Потребности

4. Проверим оптимальность опорного плана. Найдем u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=7	v2=5	v3=-16	v4=10	v5=18
u1=0		5[23]		10[50]	18[5]
u2=22			6[78]		40[16]
u3=1					19[29]
u4=23	30[49]	28[37]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.

Минимальные затраты составят:
F(x) = 5*23 + 10*50 + 18*5 + 6*78 + 40*16 + 19*29 + 30*49 + 28*37 = 4870

Дата добавления: 2015-03-29