Задача№1 (стр. 6 )

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

	1	2	3	4	Запасы
1	15	7[100]	8	10	100
2	11	18[201]	16	29	201
3	9[0]	15	3[300]	15	300
4	5	8[1]	14	4[200]	201
5	10[501]	16[199]	10	15	700
Потребности	501	501	300	200

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

	v1=1	v2=7	v3=-5	v4=3
u1=0	15	7[100]	8	10
u2=11	11	18[201]	16	29
u3=8	9[0]	15	3[300]	15
u4=1	5	8[1]	14	4[200]
u5=9	10[501]	16[199]	10	15

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

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

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

	1	2	3	4	Запасы
1	15	7[100]	8	10	100
2	11[+]	18[201][-]	16	29	201
3	9[0]	15	3[300]	15	300
4	5	8[1]	14	4[200]	201
5	10[501][-]	16[199][+]	10	15	700
Потребности	501	501	300	200

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

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

	1	2	3	4	Запасы
1	15	7[100]	8	10	100
2	11[201]	18	16	29	201
3	9[0]	15	3[300]	15	300
4	5	8[1]	14	4[200]	201
5	10[300]	16[400]	10	15	700
Потребности	501	501	300	200

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

	v1=1	v2=7	v3=-5	v4=3
u1=0	15	7[100]	8	10
u2=10	11[201]	18	16	29
u3=8	9[0]	15	3[300]	15
u4=1	5	8[1]	14	4[200]
u5=9	10[300]	16[400]	10	15

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