Контрольная работа по "Математике"

 

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

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

	1	2	3	4	5	Запасы
1	23	21	11[2]	8	3[220]	222
2	7	17	5[188]	2	4	188
3	2[125]	16	8	4[85]	3	210
4	3	9[75]	21[10]	8[295]	4	380
Потребности	125	75	200	380	220

Проверим оптимальность  опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₃ = 11; 0 + v₃ = 11; v₃ = 11

u₂ + v₃ = 5; 11 + u₂ = 5; u₂ = -6

u₄ + v₃ = 21; 11 + u₄ = 21; u₄ = 10

u₄ + v₂ = 9; 10 + v₂ = 9; v₂ = -1

u₄ + v₄ = 8; 10 + v₄ = 8; v₄ = -2

u₃ + v₄ = 4; -2 + u₃ = 4; u₃ = 6

u₃ + v₁ = 2; 6 + v₁ = 2; v₁ = -4

u₁ + v₅ = 3; 0 + v₅ = 3; v₅ = 3

	v1=-4	v2=-1	v3=11	v4=-2	v5=3
u1=0	23	21	11[2]	8	3[220]
u2=-6	7	17	5[188]	2	4
u3=6	2[125]	16	8	4[85]	3
u4=10	3	9[75]	21[10]	8[295]	4

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

(3;3): 6 + 11 > 8; ∆₃₃ = 6 + 11 - 8 = 9

(3;5): 6 + 3 > 3; ∆₃₅ = 6 + 3 - 3 = 6

(4;1): 10 + -4 > 3; ∆₄₁ = 10 + -4 - 3 = 3

(4;5): 10 + 3 > 4; ∆₄₅ = 10 + 3 - 4 = 9

max(9,6,3,9) = 9

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

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

	1	2	3	4	5	Запасы
1	23	21	11[2]	8	3[220]	222
2	7	17	5[188]	2	4	188
3	2[125]	16	8[+]	4[85][-]	3	210
4	3	9[75]	21[10][-]	8[295][+]	4	380
Потребности	125	75	200	380	220

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

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

	1	2	3	4	5	Запасы
1	23	21	11[2]	8	3[220]	222
2	7	17	5[188]	2	4	188
3	2[125]	16	8[10]	4[75]	3	210
4	3	9[75]	21	8[305]	4	380
Потребности	125	75	200	380	220

 

Проверим оптимальность  опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₃ = 11; 0 + v₃ = 11; v₃ = 11

u₂ + v₃ = 5; 11 + u₂ = 5; u₂ = -6

u₃ + v₃ = 8; 11 + u₃ = 8; u₃ = -3

u₃ + v₁ = 2; -3 + v₁ = 2; v₁ = 5

u₃ + v₄ = 4; -3 + v₄ = 4; v₄ = 7

u₄ + v₄ = 8; 7 + u₄ = 8; u₄ = 1

u₄ + v₂ = 9; 1 + v₂ = 9; v₂ = 8

u₁ + v₅ = 3; 0 + v₅ = 3; v₅ = 3

	v1=5	v2=8	v3=11	v4=7	v5=3
u1=0	23	21	11[2]	8	3[220]
u2=-6	7	17	5[188]	2	4
u3=-3	2[125]	16	8[10]	4[75]	3
u4=1	3	9[75]	21	8[305]	4

 

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

(4;1): 1 + 5 > 3; ∆₄₁ = 1 + 5 - 3 = 3

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

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

	1	2	3	4	5	Запасы
1	23	21	11[2]	8	3[220]	222
2	7	17	5[188]	2	4	188
3	2[125][-]	16	8[10]	4[75][+]	3	210
4	3[+]	9[75]	21	8[305][-]	4	380
Потребности	125	75	200	380	220

 

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

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

	1	2	3	4	5	Запасы
1	23	21	11[2]	8	3[220]	222
2	7	17	5[188]	2	4	188
3	2	16	8[10]	4[200]	3	210
4	3[125]	9[75]	21	8[180]	4	380
Потребности	125	75	200	380	220

Проверим оптимальность  опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₃ = 11; 0 + v₃ = 11; v₃ = 11

u₂ + v₃ = 5; 11 + u₂ = 5; u₂ = -6

u₃ + v₃ = 8; 11 + u₃ = 8; u₃ = -3

u₃ + v₄ = 4; -3 + v₄ = 4; v₄ = 7

u₄ + v₄ = 8; 7 + u₄ = 8; u₄ = 1

u₄ + v₁ = 3; 1 + v₁ = 3; v₁ = 2

u₄ + v₂ = 9; 1 + v₂ = 9; v₂ = 8

u₁ + v₅ = 3; 0 + v₅ = 3; v₅ = 3

	v1=2	v2=8	v3=11	v4=7	v5=3
u1=0	23	21	11[2]	8	3[220]
u2=-6	7	17	5[188]	2	4
u3=-3	2	16	8[10]	4[200]	3
u4=1	3[125]	9[75]	21	8[180]	4

 

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

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

F(x) = 11*2 + 3*220 + 5*188 + 8*10 + 4*200 + 3*125 + 9*75 + 8*180  = 4992

Ответ: Минимальные затраты составят: F(x) = 4992

 

Литература

 

1. Беляев А.А., Артамонов., Фомин Г.П.  Прикладная математика ч.1. РГТЭУ, 2002.
2. Кузнецов Ю.П. Математическое программирование . - М.: Высшая школа, 1980.
3. Спирин А.А., Фомин Г.П.  Экономико-математические методы и модели в торговле  М.: Экономика, 1988.
4. Фомин Г.П. Математические методы и модели в коммерческой деятельности. Учебник. М.: Финансы и статистика. 2004.