Прикладная математика. Решить транспортную задачу, методом потенциалов.
Добрый день! Помогите решить. СПАСИБО!
ТРАНСПОРТНАЯ ЗАДАЧА
метод потенциалов
Введите запасы поставщиков (a) и потребности потребителей (b)
через запятые по образцу, изменяя этот образец
a - Запасы поставщиков: 180,300,60,120,180
b - Потребности потребителей: 240,120,180,180,240
А что в ней транспортного?
Решение транспортной задачи методом потенциалов:
1. Формулировка задачи:
Имеем 5 поставщиков с запасами a = (180, 300, 60, 120, 180) и 5 потребителей с потребностями b = (240, 120, 180, 180, 240). Необходимо найти оптимальный план перевозок, минимизирующий суммарные транспортные расходы.
2. Матрица транспортных расходов (C):
Предположим, у нас есть следующая матрица транспортных расходов на единицу продукции:
| B1 | B2 | B3 | B4 | B5
---|-----|-----|-----|-----|-----
A1 | c11| c12| c13| c14| c15
A2 | c21| c22| c23| c24| c25
A3 | c31| c32| c33| c34| c35
A4 | c41| c42| c43| c44| c45
A5 | c51| c52| c53| c54| c55 Важно: Для решения задачи необходимо знать значения cij (стоимость перевозки единицы груза из пункта Ai в пункт Bj).
3. Нахождение начального опорного плана:
Для нахождения начального опорного плана можно использовать метод "северо-западного угла" или метод "минимального элемента".
4. Метод потенциалов:
Шаг 1: Вводим потенциалы поставщиков (ui) и потребителей (vj). Для удобства полагаем u1 = 0.
Шаг 2: Для каждой базисной клетки (i, j) вычисляем потенциал vj = cij - ui.
Шаг 3: Для каждой свободной клетки (i, j) вычисляем оценки Δij = cij - ui - vj.
Шаг 4: Если все оценки Δij ≥ 0, то найден оптимальный план.
Шаг 5: Если есть отрицательные оценки, выбираем клетку с наименьшей оценкой и строим цикл перераспределения.
Шаг 6: Перераспределяем груз по циклу, минимизируя суммарные транспортные расходы.
Шаг 7: Возвращаемся к шагу 2 и повторяем итерации до тех пор, пока не будут выполнены условия оптимальности (все Δij ≥ 0).
5. Оптимальный план:
В результате итераций метода потенциалов получим оптимальный план перевозок, который будет представлен в виде значений xij (объем перевозок из пункта Ai в пункт Bj).
Важно:
Без указания конкретных значений транспортных расходов (матрица C) невозможно получить числовое решение задачи.
Алгоритм решения методом потенциалов предполагает знание начального опорного плана.
Рекомендации:
Уточните значения транспортных расходов (матрица C).
Выберите метод нахождения начального опорного плана.
Последовательно выполните шаги метода потенциалов.
После этого вы сможете получить оптимальный план перевозок и минимальные суммарные транспортные расходы.