Калькулятор транспортной задачи (СЗ-угол, мин. стоимость и метод потенциалов)
Построение начального опорного плана методами северо-западного угла и минимальной стоимости, а также оптимизация методом потенциалов (MODI).
| D1 | D2 | D3 | Запасы | |
|---|---|---|---|---|
| S1 | ||||
| S2 | ||||
| S3 | ||||
| Потребности |
Транспортная задача: метод северо-западного угла, наименьшей стоимости и метод потенциалов (MODI)
Академическое руководство по моделированию сетей распределения, построению опорных планов и нахождению глобального оптимума методом потенциалов.
1. Какую задачу решает транспортная модель?
Транспортная задача — это специальный класс задач линейного программирования, направленный на поиск оптимального плана перевозок однородного груза из m пунктов отправления (склады, заводы) в n пунктов назначения (магазины, потребители). При равенстве суммарного предложения и суммарного спроса (∑ sᵢ = ∑ dⱼ) модель называется закрытой (сбалансированной). Цель — минимизировать общую стоимость перевозок Z = ∑∑ cᵢⱼ xᵢⱼ при соблюдении баланса поставок.
2. Алгоритм решения: от опорного плана к оптимуму
Заполнение начинается с левой верхней клетки (1, 1). Выделяется min(s₁, d₁), строка или столбец закрываются, после чего шаг повторяется вправо или вниз. Тарифы перевозок игнорируются, поэтому план строится быстро, но далек от оптимума.
Жадный алгоритм, распределяющий поставки в клетки с минимальным тарифом cᵢⱼ. Позволяет сразу задействовать наиболее выгодные маршруты и получить начальный план, близкий к оптимальному.
Двойственный метод решения. На основе равенства uᵢ + vⱼ = cᵢⱼ для базисных клеток определяются потенциалы строк uᵢ и столбцов vⱼ. Затем для свободных клеток рассчитываются оценки Δᵢⱼ = cᵢⱼ - (uᵢ + vⱼ). Если все Δᵢⱼ ≥ 0, план оптимален. При наличии отрицательных оценок строится замкнутый цикл пересчета.
3. Разобранный пример: 3 поставщика × 3 потребителя
Сравнение методов построения опорного плана и проверка оптимума.
| Origin / Destination | Destination 1 (D₁) | Destination 2 (D₂) | Destination 3 (D₃) | Supply Capacity |
|---|---|---|---|---|
| Поставщик 1 (S₁) | 8 ₽ | 4 ₽ | 12 ₽ | 100 |
| Поставщик 2 (S₂) | 10 ₽ | 5 ₽ | 6 ₽ | 300 |
| Поставщик 3 (S₃) | 7 ₽ | 8 ₽ | 15 ₽ | 300 |
| Demand Requirement | 300 | 200 | 200 | 700 |
A. Решение методом северо-западного угла
Клетка (S₁, D₁): распределяем min(100, 300) = 100. S₁ исчерпан. Клетка (S₂, D₁): min(300, 200) = 200. D₁ удовлетворен. Клетка (S₂, D₂): min(100, 200) = 100. S₂ исчерпан. Клетка (S₃, D₂): min(300, 100) = 100. D₂ удовлетворен. Клетка (S₃, D₃): распределяем оставшиеся 200 единиц.
Б. Решение методом минимальной стоимости
1. Клетка с минимальным тарифом (S₁, D₂), c = 4: выделяем min(100, 200) = 100. S₁ исчерпан. 2. Следующая клетка (S₂, D₂), c = 5: выделяем min(300, 100) = 100. D₂ удовлетворен. 3. Клетка (S₂, D₃), c = 6: выделяем min(200, 200) = 200. S₂ и D₃ закрыты. 4. Клетка (S₃, D₁), c = 7: выделяем min(300, 300) = 300. S₃ и D₁ закрыты.
В. Проверка метода потенциалов (MODI)
Для базисных клеток (S₁, D₂), (S₂, D₂), (S₂, D₃) и (S₃, D₁) расчет потенциалов uᵢ и vⱼ дает оценки свободных клеток Δᵢⱼ = cᵢⱼ - (uᵢ + vⱼ) ≥ 0. Отрицательных оценок нет, что строго доказывает глобальную оптимальность плана стоимости 4 200 ₽.
Экономия: снижение затрат на 2 900 ₽
Применение метода наименьшей стоимости снижает начальные затраты с 7 100 ₽ до 4 200 ₽ — чистая экономия составляет 2 900 ₽ (снижение на 40,8%) еще до этапа итерационного пересчета циклов.
4. Типичные ошибки при решении
Игнорирование дисбаланса спроса и предложения
Если предложение превышает спрос, необходимо ввести фиктивного потребителя с нулевыми тарифами; если спрос больше предложения — фиктивного поставщика.
Вырожденность плана (менее m + n - 1 занятых клеток)
Опорный план должен содержать ровно m + n - 1 клеток (здесь 3 + 3 - 1 = 5). При вырожденности в независимую клетку заносится нулевая поставка (ε) для вычисления потенциалов.
Ошибки построения замкнутого цикла
Вершины цикла пересчета могут находиться только в занятых (базисных) клетках, а углы поворота должны быть строго под 90 градусов.