транспортная задача

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

Выбираем максимальную оценку свободной клетки (3;3): 3

Для этого в перспективную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	3	4	3[200]	1[100]	5	300
2	2[200]	3	5	6	8	200
3	1[100][-]	2	3[+]	3	4	100
4	4[0][+]	5[200]	7[0][-]	9	9	200
5	5	6	8	4	7[300]	300
6	0	0	0[100]	0	0[100]	200
Потребности	300	200	300	100	400

Цикл приведен в таблице (3,3; 3,1; 4,1; 4,3; ).

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

	1	2	3	4	5	Запасы
1	3	4	3[200]	1[100]	5	300
2	2[200]	3	5	6	8	200
3	1[100]	2	3[0]	3	4	100
4	4[0]	5[200]	7	9	9	200
5	5	6	8	4	7[300]	300
6	0	0	0[100]	0	0[100]	200
Потребности	300	200	300	100	400

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

	v1=1	v2=2	v3=3	v4=1	v5=3
u1=0	3	4	3[200]	1[100]	5
u2=1	2[200]	3	5	6	8
u3=0	1[100]	2	3[0]	3	4
u4=3	4[0]	5[200]	7	9	9
u5=4	5	6	8	4	7[300]
u6=-3	0	0	0[100]	0	0[100]

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

Выбираем максимальную оценку свободной клетки (5;4): 4

Для этого в перспективную клетку (5;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	3	4	3[200][+]	1[100][-]	5	300
2	2[200]	3	5	6	8	200
3	1[100]	2	3[0]	3	4	100
4	4[0]	5[200]	7	9	9	200
5	5	6	8	4[+]	7[300][-]	300
6	0	0	0[100][-]	0	0[100][+]	200
Потребности	300	200	300	100	400

Цикл приведен в таблице (5,4; 5,5; 6,5; 6,3; 1,3; 1,4; ).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (6, 3) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	3	4	3[300]	1[0]	5	300
2	2[200]	3	5	6	8	200
3	1[100]	2	3[0]	3	4	100
4	4[0]	5[200]	7	9	9	200
5	5	6	8	4[100]	7[200]	300
6	0	0	0	0	0[200]	200
Потребности	300	200	300	100	400

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

	v1=1	v2=2	v3=3	v4=1	v5=4
u1=0	3	4	3[300]	1[0]	5
u2=1	2[200]	3	5	6	8
u3=0	1[100]	2	3[0]	3	4
u4=3	4[0]	5[200]	7	9	9
u5=3	5	6	8	4[100]	7[200]
u6=-4	0	0	0	0	0[200]

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

Минимальные затраты составят:

F(x) = 3 ∙ 300 + 2 ∙ 200 + 1 ∙ 100 + 5 ∙ 200 + 4 ∙ 100 + 7 ∙ 200 + 0 ∙ 200 = 4200