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

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

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

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

	1	2	3		Запасы
1	1[90]	9[10][-]	4[+]	0	100
2	4	3[80]	3	0	80
3	2	1[10][+]	2[40][-]	0	50
4	6	2	9[40]	0[10]	50
Потребности	90	100	80	10

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

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

	1	2	3	4	Запасы
1	1[90]	9	4[10]	0	100
2	4	3[80]	3	0	80
3	2	1[20]	2[30]	0	50
4	6	2	9[40]	0[10]	50
Потребности	90	100	80	10

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

	v1=1	v2=3	v3=4	v4=-5
u1=0	1[90]	9	4[10]	0
u2=0	4	3[80]	3	0
u3=-2	2	1[20]	2[30]	0
u4=5	6	2	9[40]	0[10]

Перейти на страницу: 1 2 3 4 5 6 7 8

Поиск оптимальных условий

Производственная деятельность

Кадровый потенциал

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

Основные разделы