Методы оптимальных решений. ПКЗ мор. Для изготовления продукции двух видовАиВ фирма расходует ресурсы, а от реализации этой продукции получает доход

• Название: Для изготовления продукции двух видовАиВ фирма расходует ресурсы, а от реализации этой продукции получает доход
• Анкор: Методы оптимальных решений
• Дата: 10.11.2021
• Размер: 118.41 Kb.
• Имя файла: ПКЗ мор.docx
• Тип: Документы; #268182
• страница: 4 из 5

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

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

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

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

u₂ + v₅ = 9; 6 + u₂ = 9; u₂ = 3

u₂ + v₁ = 10; 3 + v₁ = 10; v₁ = 7

u₄ + v₁ = 0; 7 + u₄ = 0; u₄ = -7

u₄ + v₂ = 0; -7 + v₂ = 0; v₂ = 7

u₃ + v₂ = 5; 7 + u₃ = 5; u₃ = -2

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

	v1=7	v2=7	v3=6	v4=4	v5=6
u1=0	8	9	7	4[20]	6[47]
u2=3	10[3]	11	8	6	9[9]
u3=-2	7	5[38]	4[55]	4	5
u4=-7	0[35]	0[3]	0	0	0

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

(2;3): 3 + 6 > 8; ∆₂₃ = 3 + 6 - 8 = 1 > 0

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

max(1,1) = 1

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

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

	1	2	3	4	5	Запасы
1	8	9	7	4[20]	6[47]	67
2	10[3][-]	11	8[+]	6	9[9]	12
3	7	5[38][+]	4[55][-]	4	5	93
4	0[35][+]	0[3][-]	0	0	0	38
Потребности	38	41	55	20	56

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

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

	B1	B2	B3	B4	B5	Запасы
A1	8	9	7	4[20]	6[47]	67
A2	10[0]	11	8[3]	6	9[9]	12
A3	7	5[41]	4[52]	4	5	93
A4	0[38]	0	0	0	0	38
Потребности	38	41	55	20	56

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

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

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

u₂ + v₅ = 9; 6 + u₂ = 9; u₂ = 3

u₂ + v₁ = 10; 3 + v₁ = 10; v₁ = 7

u₄ + v₁ = 0; 7 + u₄ = 0; u₄ = -7

u₂ + v₃ = 8; 3 + v₃ = 8; v₃ = 5

u₃ + v₃ = 4; 5 + u₃ = 4; u₃ = -1

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

	v1=7	v2=6	v3=5	v4=4	v5=6
u1=0	8	9	7	4[20]	6[47]
u2=3	10[0]	11	8[3]	6	9[9]
u3=-1	7	5[41]	4[52]	4	5
u4=-7	0[38]	0	0	0	0

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

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

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

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

	1	2	3	4	5	Запасы
1	8	9	7	4[20][-]	6[47][+]	67
2	10[0]	11	8[3]	6[+]	9[9][-]	12
3	7	5[41]	4[52]	4	5	93
4	0[38]	0	0	0	0	38
Потребности	38	41	55	20	56

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

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

	B1	B2	B3	B4	B5	Запасы
A1	8	9	7	4[11]	6[56]	67
A2	10[0]	11	8[3]	6[9]	9	12
A3	7	5[41]	4[52]	4	5	93
A4	0[38]	0	0	0	0	38
Потребности	38	41	55	20	56

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

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

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

u₂ + v₁ = 10; 2 + v₁ = 10; v₁ = 8

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

u₂ + v₃ = 8; 2 + v₃ = 8; v₃ = 6

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

u₃ + v₂ = 5; -2 + v₂ = 5; v₂ = 7

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

	v1=8	v2=7	v3=6	v4=4	v5=6
u1=0	8	9	7	4[11]	6[56]
u2=2	10[0]	11	8[3]	6[9]	9
u3=-2	7	5[41]	4[52]	4	5
u4=-8	0[38]	0	0	0	0

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

Минимальные транспортные затраты составят: F(x) = 4*11 + 6*56 + 8*3 + 6*9 + 5*41 + 4*52 + 0*38 = 871