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

2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 8*100 + 18*201 + 9*100 + 3*200 + 5*1 + 4*200 + 10*400 + 16*300 = 15523

Этап II. Улучшение опорного плана.

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

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

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

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

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

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

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

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (1, 3) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Х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[1]	8	14	4[200]	201
5	10[500]	16[200]	10	15	700
Потребности	501	501	300	200

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

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

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

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

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

	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[1][-]	8[+]	14	4[200]	201
5	10[500][+]	16[200][-]	10	15	700
Потребности	501	501	300	200

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