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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

F(x) = 2*40 + 2*80 + 3*10 + 1*60 + 3*20 + 2*80  = 550.

1. Используя метод северо-западного  угла, построим первый опорный  план транспортной задачи.

	1	2	3	4	5	Запасы
1	7[20]	3[20]	5	4	2	40
2	6	2[60]	3[90]	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) = 7*20 + 3*20 + 2*60 + 3*90 + 6*60 + 4*40  = 1110

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