Прикладная математика. Задания контрольной работы Задания 1 10

Название	Задания контрольной работы Задания 1 10
Дата	13.06.2022
Размер	225.26 Kb.
Формат файла
Имя файла	Прикладная математика.docx
Тип	Отчет #588781
страница	5 из 7

1 2 3 4 5 6 7

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

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

u₁ + v₁ = 15; 0 + v₁ = 15; v₁ = 15

u₃ + v₁ = 14; 15 + u₃ = 14; u₃ = -1

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

u₁ + v₆ = 25; 0 + v₆ = 25; v₆ = 25

u₄ + v₆ = 29; 25 + u₄ = 29; u₄ = 4

u₄ + v₂ = 45; 4 + v₂ = 45; v₂ = 41

u₂ + v₂ = 15; 41 + u₂ = 15; u₂ = -26

u₂ + v₅ = 14; -26 + v₅ = 14; v₅ = 40

u₄ + v₄ = 35; 4 + v₄ = 35; v₄ = 31

	v₁=15	v₂=41	v₃=10	v₄=31	v₅=40	v₆=25
u₁=0	15[900]	56	10[420]	35	15	25[540]
u₂=-26	52	15[1420]	22	51	14[940]	35
u₃=-1	14[540]	57	59	25	54	53
u₄=4	28	45[820]	15	35[240]	45	29[500]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(1;5): 0 + 40 > 15; ∆₁₅ = 0 + 40 - 15 = 25 > 0

(3;4): -1 + 31 > 25; ∆₃₄ = -1 + 31 - 25 = 5 > 0

max(25,5) = 25

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

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

	1	2	3	4	5	6	Запасы
1	15[900]	56	10[420]	35	15[+]	25[540][-]	1860
2	52	15[1420][+]	22	51	14[940][-]	35	2360
3	14[540]	57	59	25	54	53	540
4	28	45[820][-]	15	35[240]	45	29[500][+]	1560
Потребности	1440	2240	420	240	940	1040

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

	B1	B2	B3	B4	B5	B6	Запасы
A1	15[900]	56	10[420]	35	15[540]	25	1860
A2	52	15[1960]	22	51	14[400]	35	2360
A3	14[540]	57	59	25	54	53	540
A4	28	45[280]	15	35[240]	45	29[1040]	1560
Потребности	1440	2240	420	240	940	1040

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

u₃ + v₁ = 14; 15 + u₃ = 14; u₃ = -1

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

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

u₂ + v₅ = 14; 15 + u₂ = 14; u₂ = -1

u₂ + v₂ = 15; -1 + v₂ = 15; v₂ = 16

u₄ + v₂ = 45; 16 + u₄ = 45; u₄ = 29

u₄ + v₄ = 35; 29 + v₄ = 35; v₄ = 6

u₄ + v₆ = 29; 29 + v₆ = 29; v₆ = 0

	v₁=15	v₂=16	v₃=10	v₄=6	v₅=15	v₆=0
u₁=0	15[900]	56	10[420]	35	15[540]	25
u₂=-1	52	15[1960]	22	51	14[400]	35
u₃=-1	14[540]	57	59	25	54	53
u₄=29	28	45[280]	15	35[240]	45	29[1040]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(4;1): 29 + 15 > 28; ∆₄₁ = 29 + 15 - 28 = 16 > 0

(4;3): 29 + 10 > 15; ∆₄₃ = 29 + 10 - 15 = 24 > 0

max(16,24) = 24

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

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

	1	2	3	4	5	6	Запасы
1	15[900]	56	10[420][-]	35	15[540][+]	25	1860
2	52	15[1960][+]	22	51	14[400][-]	35	2360
3	14[540]	57	59	25	54	53	540
4	28	45[280][-]	15[+]	35[240]	45	29[1040]	1560
Потребности	1440	2240	420	240	940	1040

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

	B1	B2	B3	B4	B5	B6	Запасы
A1	15[900]	56	10[140]	35	15[820]	25	1860
A2	52	15[2240]	22	51	14[120]	35	2360
A3	14[540]	57	59	25	54	53	540
A4	28	45	15[280]	35[240]	45	29[1040]	1560
Потребности	1440	2240	420	240	940	1040

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

u₃ + v₁ = 14; 15 + u₃ = 14; u₃ = -1

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

u₄ + v₃ = 15; 10 + u₄ = 15; u₄ = 5

u₄ + v₄ = 35; 5 + v₄ = 35; v₄ = 30

u₄ + v₆ = 29; 5 + v₆ = 29; v₆ = 24

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

u₂ + v₅ = 14; 15 + u₂ = 14; u₂ = -1

u₂ + v₂ = 15; -1 + v₂ = 15; v₂ = 16

	v₁=15	v₂=16	v₃=10	v₄=30	v₅=15	v₆=24
u₁=0	15[900]	56	10[140]	35	15[820]	25
u₂=-1	52	15[2240]	22	51	14[120]	35
u₃=-1	14[540]	57	59	25	54	53
u₄=5	28	45	15[280]	35[240]	45	29[1040]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(3;4): -1 + 30 > 25; ∆₃₄ = -1 + 30 - 25 = 4 > 0

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

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

	1	2	3	4	5	6	Запасы
1	15[900][+]	56	10[140][-]	35	15[820]	25	1860
2	52	15[2240]	22	51	14[120]	35	2360
3	14[540][-]	57	59	25[+]	54	53	540
4	28	45	15[280][+]	35[240][-]	45	29[1040]	1560
Потребности	1440	2240	420	240	940	1040

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

	B1	B2	B3	B4	B5	B6	Запасы
A1	15[1040]	56	10	35	15[820]	25	1860
A2	52	15[2240]	22	51	14[120]	35	2360
A3	14[400]	57	59	25[140]	54	53	540
A4	28	45	15[420]	35[100]	45	29[1040]	1560
Потребности	1440	2240	420	240	940	1040

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

u₃ + v₁ = 14; 15 + u₃ = 14; u₃ = -1

u₃ + v₄ = 25; -1 + v₄ = 25; v₄ = 26

u₄ + v₄ = 35; 26 + u₄ = 35; u₄ = 9

u₄ + v₃ = 15; 9 + v₃ = 15; v₃ = 6

u₄ + v₆ = 29; 9 + v₆ = 29; v₆ = 20

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

u₂ + v₅ = 14; 15 + u₂ = 14; u₂ = -1

u₂ + v₂ = 15; -1 + v₂ = 15; v₂ = 16

	v₁=15	v₂=16	v₃=6	v₄=26	v₅=15	v₆=20
u₁=0	15[1040]	56	10	35	15[820]	25
u₂=-1	52	15[2240]	22	51	14[120]	35
u₃=-1	14[400]	57	59	25[140]	54	53
u₄=9	28	45	15[420]	35[100]	45	29[1040]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.
Минимальные затраты составят: F(x) = 15*1040 + 15*820 + 15*2240 + 14*120 + 14*400 + 25*140 + 15*420 + 35*100 + 29*1040 = 112240

1 2 3 4 5 6 7