Оптимизация решений 5й вариант. Оптимизация решений. Решение Необходимо найти максимальное значение целевой функции f 2x 1 4x 2

• Название: Решение Необходимо найти максимальное значение целевой функции f 2x 1 4x 2
• Анкор: Оптимизация решений 5й вариант
• Дата: 18.08.2020
• Размер: 55.86 Kb.
• Имя файла: Оптимизация решений.docx
• Тип: Решение; #135741
• страница: 2 из 4

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

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

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3
u₁ + v₄ = 4; 0 + v₄ = 4; v₄ = 4
u₃ + v₄ = 7; 4 + u₃ = 7; u₃ = 3
u₃ + v₃ = 5; 3 + v₃ = 5; v₃ = 2
u₂ + v₃ = 2; 2 + u₂ = 2; u₂ = 0
u₂ + v₁ = 1; 0 + v₁ = 1; v₁ = 1

	v1=1	v2=3	v3=2	v4=4
u1=0	4	3[25]	6	4[15]
u2=0	1[30]	6	2[0]	8
u3=3	2	4	5[15]	7[5]

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

(3;1): 3 + 1 > 2; ∆₃₁ = 3 + 1 - 2 = 2 > 0

(3;2): 3 + 3 > 4; ∆₃₂ = 3 + 3 - 4 = 2 > 0

max(2,2) = 2

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

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

	1	2	3	4	Запасы
1	4	3[25]	6	4[15]	40
2	1[30][-]	6	2[0][+]	8	30
3	2[+]	4	5[15][-]	7[5]	20
Потребности	30	25	15	20

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

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

	B1	B2	B3	B4	Запасы
A1	4	3[25]	6	4[15]	40
A2	1[15]	6	2[15]	8	30
A3	2[15]	4	5	7[5]	20
Потребности	30	25	15	20

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

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3
u₁ + v₄ = 4; 0 + v₄ = 4; v₄ = 4
u₃ + v₄ = 7; 4 + u₃ = 7; u₃ = 3
u₃ + v₁ = 2; 3 + v₁ = 2; v₁ = -1
u₂ + v₁ = 1; -1 + u₂ = 1; u₂ = 2
u₂ + v₃ = 2; 2 + v₃ = 2; v₃ = 0

	v1=-1	v2=3	v3=0	v4=4
u1=0	4	3[25]	6	4[15]
u2=2	1[15]	6	2[15]	8
u3=3	2[15]	4	5	7[5]

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

(3;2): 3 + 3 > 4; ∆₃₂ = 3 + 3 - 4 = 2 > 0

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

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

	1	2	3	4	Запасы
1	4	3[25][-]	6	4[15][+]	40
2	1[15]	6	2[15]	8	30
3	2[15]	4[+]	5	7[5][-]	20
Потребности	30	25	15	20

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

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

	B1	B2	B3	B4	Запасы
A1	4	3[20]	6	4[20]	40
A2	1[15]	6	2[15]	8	30
A3	2[15]	4[5]	5	7	20
Потребности	30	25	15	20

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

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3
u₃ + v₂ = 4; 3 + u₃ = 4; u₃ = 1
u₃ + v₁ = 2; 1 + v₁ = 2; v₁ = 1
u₂ + v₁ = 1; 1 + u₂ = 1; u₂ = 0
u₂ + v₃ = 2; 0 + v₃ = 2; v₃ = 2
u₁ + v₄ = 4; 0 + v₄ = 4; v₄ = 4

	v1=1	v2=3	v3=2	v4=4
u1=0	4	3[20]	6	4[20]
u2=0	1[15]	6	2[15]	8
u3=1	2[15]	4[5]	5	7

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

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

F(x) = 3∙20 + 4∙20 + 1∙15 + 2∙15 + 2∙15 + 4∙5 = 235.