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

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0. 
u1 + v1 = 2; 0 + v1 = 2; v1 = 2 
u5 + v1 = 0; 2 + u5 = 0; u5 = -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

	V1=2	V2=1	V3=2	V4=-1
U1=0	2 [14]	1 [22]	3	5
U2=2	4	3 [22]	4	4
U3=1	5	2 [3]	3 [10]	6
U4=3	3	6	5 [12]	2 [32]
U5=-2	0 [5]	0	0	0

 

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

	В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

 

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

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

 

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

	V1=2	V2=1	V3=4	V4=1
U1=0	2 [11]	1 [25]	3	5
U2=2	4	3 [22]	4	4
U3=-1	5	2	3 [13]	6
U4=1	3 [3]	6	5 [9]	2 [32]
U5=-2	0 [5]	0	0	0

 

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

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

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

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

 

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

	V1=2	V2=1	V3=2	V4=1
U1=0	2 [2]	1 [34]	3	5
U2=2	4	3 [13]	4 [9]	4
U3=1	5	2	3 [13]	6
U4=1	3 [12]	6	5	2 [32]
U5=-2	0 [5]	0	0	0

 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij. 
Минимальные затраты составят: 
F(x) = 2*2 + 1*34 + 3*13 + 4*9 + 3*13 + 3*12 + 2*32 + 0*5 = 252

 

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 1-й магазин (2), в 2-й магазин (34) 
Из 2-го склада необходимо груз направить в 2-й магазин (13), в 3-й магазин (9) 
Из 3-го склада необходимо весь груз направить в 3-й магазин 
Из 4-го склада необходимо груз направить в 1-й магазин (12), в 4-й магазин (32) 
Потребность 1-го магазина остается неудовлетворенной на 5 ед. 
Оптимальный план является вырожденным, так как базисная переменная x51=0.

Ответ: Минимальные затраты F(x) = 252 у.е.