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

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

Оптимальный план можно записать так:

x₁ = 2, x₂ = 0, x₃ = 2

F(X) = 8∙2 -14∙0 + 9∙2 = 34

5. 
   Найдите оптимальное решение транспортной задачи методом потенциалов
   

23	70	40	30	40
70	6	3	7	6
50	5	6	5	6
60	3	6	6	3

Решение:

Сумма мощностей поставщиков: 70 + 50 + 60 = 180 равна сумме мощностей потребителей: 70 + 40 + 30 + 40 = 180. Модель задачи закрытая. Решаем методом потенциалов.

Составление первого опорного плана методом наименьшей стоимости

Составляем первый опорный план методом наименьшей стоимости. Наименьшая стоимость 3 в клетке (1, 2). Даем в нее наибольшую поставку 40. Потребитель B₂ получил требуемое количество груза: b₂ = 40. Вычеркиваем столбец B₂.

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

Среди не зачеркнутых клеток, наименьшая стоимость 3 в клетке (3, 1). Даем в нее наибольшую поставку 60. Поставщик A₃ реализовал весь имеющийся у него груз: a₃ = 60. Вычеркиваем строку A₃.

	B1 70	B2 40	B3 30	B4 40
A170	6	3 40	7	6
A250	5	6	5	6
A360	3 60	6	6	3

Среди не зачеркнутых клеток, наименьшая стоимость 5 в клетке (2, 1). Даем в нее наибольшую поставку 10. Потребитель B₁ получил требуемое количество груза: b₁ = 10 + 60 = 70. Вычеркиваем столбец B₁.

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

Среди не зачеркнутых клеток, наименьшая стоимость 5 в клетке (2, 3). Даем в нее наибольшую поставку 30. Потребитель B₃ получил требуемое количество груза: b₃ = 30. Вычеркиваем столбец B₃.

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

Среди не зачеркнутых клеток, наименьшая стоимость 6 в клетке (1, 4). Даем в нее наибольшую поставку 30. Поставщик A₁ реализовал весь имеющийся у него груз: a₁ = 40 + 30 = 70. Вычеркиваем строку A₁.

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

Даем наибольшую поставку 10 в оставшуюся не зачеркнутую клетку (2, 4). Получаем первый опорный план.

Таблица 1.1

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

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

F = 3·40 + 6·30 + 5·10 + 5·30 + 6·10 + 3·60 = 740

Построение оптимального плана

Находим потенциалы 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;
Для клетки (2, 4): u₂ = c_2,4 – v₄ = 6 – 6 = 0;
Для клетки (2, 1): v₁ = c_2,1 – u₂ = 5 – 0 = 5;
Для клетки (2, 3): v₃ = c_2,3 – u₂ = 5 – 0 = 5;
Для клетки (3, 1): u₃ = c_3,1 – v₁ = 3 – 5 = -2.
Заносим потенциалы в таблицу 1.2.

Таблица 1.2

	B1 70	B2 40	B3 30	B4 40	u
A170	6	3 40	7	6 30	0
A250	5 10	6	5 30	6 10	0
A360	3 60	6	6	3	-2
v	5	3	5	6

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

Наименьшая оценка Δ_3,4 = -1 в клетке (3,4). Вводим ее в базис. Строим цикл для этой клетки. Изображаем его в таблице 1.3. Расставляем знаки ′+′ и ′–′ в вершинах цикла, чередуя их, начиная со знака ′+′ в клетке (3,4).

Таблица 1.3

	B1 70	B2 40	B3 30	B4 40
A170	6	3 40	7	6 30
A250	+ 5 10	6	5 30	– 6 10
A360	– 3 60	6	6	+ 3