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

Искомый элемент равен 3

Для этого элемента запасы равны 222, потребности 220. Поскольку минимальным является 220, то вычитаем его.

x₁₅ = min(222,220) = 220.

x	21	11	8	3	222 - 220 = 2
x	x	x	2	x	0
2	16	8	4	x	85
x	9	21	8	x	380
0	75	200	192	220 - 220 = 0	0

Искомый элемент равен 4

Для этого элемента запасы равны 85, потребности 192. Поскольку минимальным является 85, то вычитаем его.

x₃₄ = min(85,192) = 85.

x	21	11	8	3	2
x	x	x	2	x	0
2	x	x	4	x	85 - 85 = 0
x	9	21	8	x	380
0	75	200	192 - 85 = 107	0	0

Искомый элемент равен 8

Для этого элемента запасы равны 2, потребности 107. Поскольку минимальным является 2, то вычитаем его.

x₁₄ = min(2,107) = 2.

x	x	x	8	3	2 - 2 = 0
x	x	x	2	x	0
2	x	x	4	x	0
x	9	21	8	x	380
0	75	200	107 - 2 = 105	0	0

Искомый элемент равен 8

Для этого элемента запасы равны 380, потребности 105. Поскольку минимальным является 105, то вычитаем его.

x₄₄ = min(380,105) = 105.

x	x	x	8	3	0
x	x	x	2	x	0
2	x	x	4	x	0
x	9	21	8	x	380 - 105 = 275
0	75	200	105 - 105 = 0	0	0

Искомый элемент равен 9

Для этого элемента запасы равны 275, потребности 75. Поскольку минимальным является 75, то вычитаем его.

x₄₂ = min(275,75) = 75.

x	x	x	8	3	0
x	x	x	2	x	0
2	x	x	4	x	0
x	9	21	8	x	275 - 75 = 200
0	75 - 75 = 0	200	0	0	0

Искомый элемент равен 21

Для этого элемента запасы равны 200, потребности 200. Поскольку минимальным является 200, то вычитаем его.

x₄₃ = min(200,200) = 200.

x	x	x	8	3	0
x	x	x	2	x	0
2	x	x	4	x	0
x	9	21	8	x	200 - 200 = 0
0	0	200 - 200 = 0	0	0	0

 

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

 

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

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

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

F(x) = 8*2 + 3*220 + 2*188 + 2*125 + 4*85 + 9*75 + 21*200 + 8*105  = 7357

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

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

u₁ + v₄ = 8; 0 + v₄ = 8; v₄ = 8

u₂ + v₄ = 2; 8 + u₂ = 2; u₂ = -6

u₃ + v₄ = 4; 8 + u₃ = 4; u₃ = -4

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

u₄ + v₄ = 8; 8 + u₄ = 8; u₄ = 0

u₄ + v₂ = 9; 0 + v₂ = 9; v₂ = 9

u₄ + v₃ = 21; 0 + v₃ = 21; v₃ = 21

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

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

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

(1;3): 0 + 21 > 11; ∆₁₃ = 0 + 21 - 11 = 10

(2;3): -6 + 21 > 5; ∆₂₃ = -6 + 21 - 5 = 10

(3;3): -4 + 21 > 8; ∆₃₃ = -4 + 21 - 8 = 9

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

max(10,10,9,3) = 10

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

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

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

 

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

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

	1	2	3	4	5	Запасы
1	23	21	11[2]	8	3[220]	222
2	7	17	5	2[188]	4	188
3	2[125]	16	8	4[85]	3	210
4	3	9[75]	21[198]	8[107]	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₃ = 21; 11 + u₄ = 21; u₄ = 10

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

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

u₂ + v₄ = 2; -2 + u₂ = 2; u₂ = 4

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=4	7	17	5	2[188]	4
u3=6	2[125]	16	8	4[85]	3
u4=10	3	9[75]	21[198]	8[107]	4

 

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

(2;3): 4 + 11 > 5; ∆₂₃ = 4 + 11 - 5 = 10

(2;5): 4 + 3 > 4; ∆₂₅ = 4 + 3 - 4 = 3

(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(10,3,9,6,3,9) = 10

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

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

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