методы оптимальных решений. МОР(5 задач). Решение Рассмотрим уравнения,, и и построим прямые, задающиеся этими уравнениями. 3

• Название: Решение Рассмотрим уравнения,, и и построим прямые, задающиеся этими уравнениями. 3
• Анкор: методы оптимальных решений
• Дата: 25.08.2022
• Размер: 86.07 Kb.
• Имя файла: МОР(5 задач).docx
• Тип: Решение; #653285
• страница: 4 из 4

Переходим к следующему опорному плану. Для этого определяем наименьшее значение поставок в вершинах цикла со знаком ′–′. Оно равно 10 в клетке (2,4). Выполняем сдвиг по циклу на величину 10: в клетках, помеченных знаком ′+′, прибавляем 10; в клетках, помеченных знаком ′–′, вычитаем 10. В результате клетка (3,4) входит в базис со значением 10, а клетка (2,4) выходит из базиса.

Получаем таблицу 2.1.

Таблица 2.1

	B1 70	B2 40	B3 30	B4 40
A170	6	3 40	7	6 30
A250	5 20	6	5 30	6
A360	3 50	6	6	3 10

Целевая функция:

F = 3·40 + 6·30 + 5·20 + 5·30 + 3·50 + 3·10 = 730

Находим потенциалы u_i, v_j. Для этого нам нужно решить приведенную ниже систему уравнений, используя только заполненные клетки:
u₁ = 0;
u_i + v_j = c_ij.
Полагаем u₁ = 0.
Для клетки (1, 2): v₂ = c_1,2 – u₁ = 3 – 0 = 3;
Для клетки (1, 4): v₄ = c_1,4 – u₁ = 6 – 0 = 6;
Для клетки (3, 4): u₃ = c_3,4 – v₄ = 3 – 6 = -3;
Для клетки (3, 1): v₁ = c_3,1 – u₃ = 3 – -3 = 6;
Для клетки (2, 1): u₂ = c_2,1 – v₁ = 5 – 6 = -1;
Для клетки (2, 3): v₃ = c_2,3 – u₂ = 5 – (-1) = 6.
Заносим потенциалы в таблицу 2.2.

Таблица 2.2

	B1 70	B2 40	B3 30	B4 40	u
A170	6	3 40	7	6 30	0
A250	5 20	6	5 30	6	-1
A360	3 50	6	6	3 10	-3
v	6	3	6	6

Находим оценки свободных клеток по формуле:
Δ_ij = c_ij – u_i – v_j.
Δ_1,1 = c_1,1 – u₁ – v₁ = 6 – 0 – 6 = 0;
Δ_1,3 = c_1,3 – u₁ – v₃ = 7 – 0 – 6 = 1;
Δ_2,2 = c_2,2 – u₂ – v₂ = 6 – (-1) – 3 = 4;
Δ_2,4 = c_2,4 – u₂ – v₄ = 6 – (-1) – 6 = 1;
Δ_3,2 = c_3,2 – u₃ – v₂ = 6 – (-3) – 3 = 6;
Δ_3,3 = c_3,3 – u₃ – v₃ = 6 – (-3) – 6 = 3.
Поскольку отрицательных оценок нет, то план оптимален. Поскольку есть оценка, равная нулю, то решение не единственное.

Ответ:

Наименьшее значение целевой функции:

F_min = 730.