Калькулятор транспортной задачи (СЗ-угол, мин. стоимость и метод потенциалов)

Построение начального опорного плана методами северо-западного угла и минимальной стоимости, а также оптимизация методом потенциалов (MODI).

3
3
D1D2D3Запасы
S1
S2
S3
Потребности
Оптимизация логистики и транспортных сетей

Транспортная задача: метод северо-западного угла, наименьшей стоимости и метод потенциалов (MODI)

Академическое руководство по моделированию сетей распределения, построению опорных планов и нахождению глобального оптимума методом потенциалов.

1. Какую задачу решает транспортная модель?

Транспортная задача — это специальный класс задач линейного программирования, направленный на поиск оптимального плана перевозок однородного груза из m пунктов отправления (склады, заводы) в n пунктов назначения (магазины, потребители). При равенстве суммарного предложения и суммарного спроса (∑ sᵢ = ∑ dⱼ) модель называется закрытой (сбалансированной). Цель — минимизировать общую стоимость перевозок Z = ∑∑ cᵢⱼ xᵢⱼ при соблюдении баланса поставок.

2. Алгоритм решения: от опорного плана к оптимуму

Построение опорного плана (IBFS)
Метод северо-западного угла (NWC)

Заполнение начинается с левой верхней клетки (1, 1). Выделяется min(s₁, d₁), строка или столбец закрываются, после чего шаг повторяется вправо или вниз. Тарифы перевозок игнорируются, поэтому план строится быстро, но далек от оптимума.

Построение опорного плана (IBFS)
Метод наименьшей стоимости (минимального элемента)

Жадный алгоритм, распределяющий поставки в клетки с минимальным тарифом cᵢⱼ. Позволяет сразу задействовать наиболее выгодные маршруты и получить начальный план, близкий к оптимальному.

Критерий и алгоритм оптимизации
Метод потенциалов (MODI / u-v)

Двойственный метод решения. На основе равенства uᵢ + vⱼ = cᵢⱼ для базисных клеток определяются потенциалы строк uᵢ и столбцов vⱼ. Затем для свободных клеток рассчитываются оценки Δᵢⱼ = cᵢⱼ - (uᵢ + vⱼ). Если все Δᵢⱼ ≥ 0, план оптимален. При наличии отрицательных оценок строится замкнутый цикл пересчета.

3. Разобранный пример: 3 поставщика × 3 потребителя

Сравнение методов построения опорного плана и проверка оптимума.

Supply: Поставщики S₁, S₂, S₃ с мощностями 100, 300 и 300 единиц.
Demand: Потребители D₁, D₂, D₃ с запросами 300, 200 и 200 единиц.
Суммарный объем = 700 единиц (закрытая сбалансированная модель).
Origin / DestinationDestination 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 Requirement300200200700

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 единиц.

Стоимость по методу северо-западного угла = (100×8) + (200×10) + (100×5) + (100×8) + (200×15) = 800 + 2000 + 500 + 800 + 3000 = 7 100 ₽.

Б. Решение методом минимальной стоимости

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₁ закрыты.

Стоимость по методу наименьшей стоимости = (100×4) + (100×5) + (200×6) + (300×7) = 400 + 500 + 1200 + 2100 = 4 200 ₽.

В. Проверка метода потенциалов (MODI)

Для базисных клеток (S₁, D₂), (S₂, D₂), (S₂, D₃) и (S₃, D₁) расчет потенциалов uᵢ и vⱼ дает оценки свободных клеток Δᵢⱼ = cᵢⱼ - (uᵢ + vⱼ) ≥ 0. Отрицательных оценок нет, что строго доказывает глобальную оптимальность плана стоимости 4 200 ₽.

Оптимальная минимальная стоимость = 4 200 ₽ (полностью совпадает с результатом калькулятора).

Экономия: снижение затрат на 2 900 ₽

Применение метода наименьшей стоимости снижает начальные затраты с 7 100 ₽ до 4 200 ₽ — чистая экономия составляет 2 900 ₽ (снижение на 40,8%) еще до этапа итерационного пересчета циклов.

4. Типичные ошибки при решении

⚠

Игнорирование дисбаланса спроса и предложения

Если предложение превышает спрос, необходимо ввести фиктивного потребителя с нулевыми тарифами; если спрос больше предложения — фиктивного поставщика.

⚠

Вырожденность плана (менее m + n - 1 занятых клеток)

Опорный план должен содержать ровно m + n - 1 клеток (здесь 3 + 3 - 1 = 5). При вырожденности в независимую клетку заносится нулевая поставка (ε) для вычисления потенциалов.

⚠

Ошибки построения замкнутого цикла

Вершины цикла пересчета могут находиться только в занятых (базисных) клетках, а углы поворота должны быть строго под 90 градусов.