задачи / 17

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

	v1=8	v2=7	v3=5	v4=2	v5=7	v6=1
u1=0	8[130]	7[100]	5[130]	10	13	12
u2=5	13	8	10	7[170]	11	6[10]
u3=-3	12	4[120]	11	9	140	10
u4=6	14[50]	6	12	130	13	7[100]
u5=1	9[50]	12	14	15	8[190]	8

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

	1	2	3	4	5	6	Запасы
1	8[130][+]	7[100][-]	5[130]	10	13	12	360
2	13	8	10	7[170]	11	6[10]	180
3	12	4[120]	11	9	140	10	120
4	14[50][-]	6[+]	12	130	13	7[100]	150
5	9[50]	12	14	15	8[190]	8	240
Потребности	230	220	130	170	190	110

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

	1	2	3	4	5	6	Запасы
1	8[180]	7[50]	5[130]	10	13	12	360
2	13	8	10	7[170]	11	6[10]	180
3	12	4[120]	11	9	140	10	120
4	14	6[50]	12	130	13	7[100]	150
5	9[50]	12	14	15	8[190]	8	240
Потребности	230	220	130	170	190	110

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

	v1=8	v2=7	v3=5	v4=9	v5=7	v6=8
u1=0	8[180]	7[50]	5[130]	10	13	12
u2=-2	13	8	10	7[170]	11	6[10]
u3=-3	12	4[120]	11	9	140	10
u4=-1	14	6[50]	12	130	13	7[100]
u5=1	9[50]	12	14	15	8[190]	8

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

	1	2	3	4	5	6	Запасы
1	8[180][+]	7[50][-]	5[130]	10	13	12	360
2	13	8	10	7[170]	11	6[10]	180
3	12	4[120]	11	9	140	10	120
4	14	6[50][+]	12	130	13	7[100][-]	150
5	9[50][-]	12	14	15	8[190]	8[+]	240
Потребности	230	220	130	170	190	110

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

	1	2	3	4	5	6	Запасы
1	8[230]	7	5[130]	10	13	12	360
2	13	8	10	7[170]	11	6[10]	180
3	12	4[120]	11	9	140	10	120
4	14	6[100]	12	130	13	7[50]	150
5	9[0]	12	14	15	8[190]	8[50]	240
Потребности	230	220	130	170	190	110

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

	v1=8	v2=6	v3=5	v4=8	v5=7	v6=7
u1=0	8[230]	7	5[130]	10	13	12
u2=-1	13	8	10	7[170]	11	6[10]
u3=-2	12	4[120]	11	9	140	10
u4=0	14	6[100]	12	130	13	7[50]
u5=1	9[0]	12	14	15	8[190]	8[50]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij. Минимальные затраты составят: F(x) = 8*230 + 5*130 + 7*170 + 6*10 + 4*120 + 6*100 + 7*50 + 8*190 + 8*50 = 7090.