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

 

Искомый элемент равен 3 
Для этого элемента запасы равны 22, потребности 30. Поскольку минимальным является 22, то вычитаем его. 
x22 = min(22,30) = 22.

	В1	В2	В3	В4	Запасы
А1	2	1	3	5	0
А2	4	3	4	4	22-22=0
А3	5	2	3	6	13
А4	3	6	5	2	44
А5	0	0	0	0	5
Потребности	0	30-22=8	22	32

 

Искомый элемент равен 2 
Для этого элемента запасы равны 13, потребности 8. Поскольку минимальным является 8, то вычитаем его. 
x32 = min(13,8) = 8.

	В1	В2	В3	В4	Запасы
А1	2	1	3	5	0
А2	4	3	4	4	0
А3	5	2	3	6	13-8=5
А4	3	6	5	2	44
А5	0	0	0	0	5
Потребности	0	8-8=0	22	32

 

Искомый элемент равен 3 
Для этого элемента запасы равны 5, потребности 22. Поскольку минимальным является 5, то вычитаем его. 
x33 = min(5,22) = 5.

	В1	В2	В3	В4	Запасы
А1	2	1	3	5	0
А2	4	3	4	4	0
А3	5	2	3	6	5-5=0
А4	3	6	5	2	44
А5	0	0	0	0	5
Потребности	0	0	22-5=17	32

 

Искомый элемент равен 5 
Для этого элемента запасы равны 44, потребности 17. Поскольку минимальным является 17, то вычитаем его. 
x43 = min(44,17) = 17.

	В1	В2	В3	В4	Запасы
А1	2	1	3	5	0
А2	4	3	4	4	0
А3	5	2	3	6	0
А4	3	6	5	2	44-17=27
А5	0	0	0	0	5
Потребности	0	0	17-17=0	32

 

Искомый элемент равен 2 
Для этого элемента запасы равны 27, потребности 32. Поскольку минимальным является 27, то вычитаем его. 
x44 = min(27,32) = 27.

	В1	В2	В3	В4	Запасы
А1	2	1	3	5	0
А2	4	3	4	4	0
А3	5	2	3	6	0
А4	3	6	5	2	27-27=0
А5	0	0	0	0	5
Потребности	0	0	0	32-27=5

 
Искомый элемент равен 0 
Для этого элемента запасы равны 5, потребности 5. Поскольку минимальным является 5, то вычитаем его. 
x54 = min(5,5) = 5.

	В1	В2	В3	В4	Запасы
А1	2	1	3	5	0
А2	4	3	4	4	0
А3	5	2	3	6	0
А4	3	6	5	2	0
А5	0	0	0	0	5-5=0
Потребности	0	0	0	5-5=0

 

	В1	В2	В3	В4	Запасы
А1	2 [19]	1 [17]	3	5	36
А2	4	3 [22]	4	4	22
А3	5	2 [8]	3 [5]	6	13
А4	3	6	5 [17]	2 [27]	44
А5	0	0	0	0 [5]	5
Потребности	19	47	22	32

 

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. 
2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным. 
Значение целевой функции для этого опорного плана равно: 
F(x) = 2*19 + 1*17 + 3*22 + 2*8 + 3*5 + 5*17 + 2*27 + 0*5 = 291

 

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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0. 
u1 + v1 = 2; 0 + v1 = 2; v1 = 2 
u1 + v2 = 1; 0 + v2 = 1; v2 = 1 
u2 + v2 = 3; 1 + u2 = 3; u2 = 2 
u3 + v2 = 2; 1 + u3 = 2; u3 = 1 
u3 + v3 = 3; 1 + v3 = 3; v3 = 2 
u4 + v3 = 5; 2 + u4 = 5; u4 = 3 
u4 + v4 = 2; 3 + v4 = 2; v4 = -1 
u5 + v4 = 0; -1 + u5 = 0; u5 = 1

	V1=2	V2=1	V3=2	V4=-1
U1=0	2 [19]	1 [17]	3	5
U2=2	4	3 [22]	4	4
U3=1	5	2 [8]	3 [5]	6
U4=3	3	6	5 [17]	2 [27]
U5=1	0	0	0	0 [5]

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij 
(4;1): 3 + 2 > 3; ∆41 = 3 + 2 - 3 = 2 
(5;1): 1 + 2 > 0; ∆51 = 1 + 2 - 0 = 3 
(5;2): 1 + 1 > 0; ∆52 = 1 + 1 - 0 = 2 
(5;3): 1 + 2 > 0; ∆53 = 1 + 2 - 0 = 3 
max(2,3,2,3) = 3 
Выбираем максимальную оценку свободной клетки (5;1): 0 
Для этого в перспективную клетку (5;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	В1	В2	В3	В4	Запасы
А1	2 [19] [-]	1 [17] [+]	3	5	36
А2	4	3 [22]	4	4	22
А3	5	2 [8] [-]	3 [5] [+]	6	13
А4	3	6	5 [17] [-]	2 [27] [+]	44
А5	0 [+]	0	0	0 [5] [-]	5
Потребности	19	47	22	32

 

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

	В1	В2	В3	В4	Запасы
А1	2 [14]	1 [22]	3	5	36
А2	4	3 [22]	4	4	22
А3	5	2 [3]	3 [10]	6	13
А4	3	6	5 [12]	2 [32]	44
А5	0 [5]	0	0	0	5
Потребности	19	47	22	32