Контрольная работа по курсу «Экономико-математическое моделирование»

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

 Строим новый план.

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

F(x) = 3*40 + 6*20 + 2*40 + 3*90 + 6*60 + 4*40  = 1110

	1	2	3	4	5	Запасы
1	7	3	5[40]	4	2	40
2	6[20]	2[80]	3[50]	1	7	150
3	3	5	2	6[60]	4[40]	100
Потребности	20	80	90	60	40

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

 Строим новый план.

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

F(x) = 5*40 + 6*20 + 2*80 + 3*50 + 6*60 + 4*40 = 1150

	1	2	3	4	5	Запасы
1	7	3	5	4[40]	2	40
2	6[20]	2[80]	3[50]	1	7	150
3	3	5	2[40]	6[20]	4[40]	100
Потребности	20	80	90	60	40

 В результате получен первый  опорный план, который является  допустимым, так как все грузы  из баз вывезены, потребность  магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

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

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

F(x) = 4*40 + 6*20 + 2*80 + 3*50 + 2*40 + 6*20 + 4*40  = 950

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

	v1=3	v2=-1	v3=0	v4=4	v5=2
u1=0	7	3	5	4[40]	2
u2=3	6[20]	2[80]	3[50]	1	7
u3=2	3	5	2[40]	6[20]	4[40]

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

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

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

	1	2	3	4	5	Запасы
1	7	3	5	4[40]	2	40
2	6[20]	2[80]	3[50][-]	1[+]	7	150
3	3	5	2[40][+]	6[20][-]	4[40]	100
Потребности	20	80	90	60	40

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

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

	1	2	3	4	5	Запасы
1	7	3	5	4[40]	2	40
2	6[20]	2[80]	3[30]	1[20]	7	150
3	3	5	2[60]	6	4[40]	100
Потребности	20	80	90	60	40

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

	v1=9	v2=5	v3=6	v4=4	v5=8
u1=0	7	3	5	4[40]	2
u2=-3	6[20]	2[80]	3[30]	1[20]	7
u3=-4	3	5	2[60]	6	4[40]

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

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

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

	1	2	3	4	5	Запасы
1	7	3	5	4[40][-]	2[+]	40
2	6[20]	2[80]	3[30][-]	1[20][+]	7	150
3	3	5	2[60][+]	6	4[40][-]	100
Потребности	20	80	90	60	40

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

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

 

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

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

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

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

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

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

	1	2	3	4	5	Запасы
1	7	3	5	4[10][-]	2[30][+]	40
2	6[20][-]	2[80]	3	1[50][+]	7	150
3	3[+]	5	2[90]	6	4[10][-]	100
Потребности	20	80	90	60	40

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

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

	1	2	3	4	5	Запасы
1	7	3	5	4[0]	2[40]	40
2	6[10]	2[80]	3	1[60]	7	150
3	3[10]	5	2[90]	6	4	100
Потребности	20	80	90	60	40