Как решить транспортную задачу: пошаговое решение

Дано: три склада с запасами 120, 100 и 80 т, три магазина со спросом 90, 130 и 80 т, тарифы перевозки одной тонны по строкам 2, 3, 6; 9, 7, 5; 4, 8, 10. Найти: план перевозок минимальной стоимости.

Запас равен спросу (300 = 300), значит модель закрытая и решается в два приёма: сначала любой допустимый опорный план, затем метод потенциалов, который улучшает его до оптимума. Ответ: минимальная стоимость перевозок 1210 ден. ед. при плане $x_{11} = 10$, $x_{12} = 110$, $x_{22} = 20$, $x_{23} = 80$, $x_{31} = 80$. Калькулятор сверху пересчитает обе таблицы под ваши запасы, спрос и тарифы.

Решение по шагам

Дано. Транспортная таблица: в клетках тарифы $c_{ij}$, справа запасы $a_i$, снизу потребности $b_j$.

Найти: объёмы перевозок $x_{ij} \ge 0$, при которых суммарная стоимость $Z = \sum c_{ij} x_{ij}$ минимальна.

Шаг 1. Проверка баланса. Складываем запасы и потребности:

$$\sum_{i=1}^{3} a_i = 120 + 100 + 80 = 300, \qquad \sum_{j=1}^{3} b_j = 90 + 130 + 80 = 300.$$

Суммы совпали, задача закрытая: фиктивных пунктов не нужно, можно строить план.

Шаг 2. Опорный план методом минимального элемента. Занимаем самую дешёвую свободную клетку и вывозим по ней максимум, который позволяют остатки запаса и спроса.

1. Минимальный тариф $c_{11} = 2$. Кладём $x_{11} = \min(120; 90) = 90$. Спрос B1 закрыт, у A1 осталось 30 т.
2. Из оставшихся минимален $c_{12} = 3$. Кладём $x_{12} = \min(30; 130) = 30$. Запас A1 исчерпан, у B2 осталось 100 т.
3. Дальше минимален $c_{23} = 5$. Кладём $x_{23} = \min(100; 80) = 80$. Спрос B3 закрыт, у A2 осталось 20 т.
4. Минимален $c_{22} = 7$. Кладём $x_{22} = \min(20; 100) = 20$. Запас A2 исчерпан, у B2 осталось 80 т.
5. Осталась одна клетка: $x_{32} = 80$.

Стоимость опорного плана:

$$Z_0 = 2 \cdot 90 + 3 \cdot 30 + 7 \cdot 20 + 5 \cdot 80 + 8 \cdot 80 = 180 + 90 + 140 + 400 + 640 = 1450.$$

Шаг 3. Проверка на вырожденность. Занятых клеток должно быть ровно $m + n - 1 = 3 + 3 - 1 = 5$. У нас занято пять: (1,1), (1,2), (2,2), (2,3), (3,2). План невырожденный, метод потенциалов применим.

Шаг 4. Потенциалы строк и столбцов. Для каждой занятой клетки должно выполняться $u_i + v_j = c_{ij}$. Уравнений пять, неизвестных шесть, поэтому одно значение задаём произвольно: пусть $u_1 = 0$.

$$\begin{aligned} (1,1): \; & u_1 + v_1 = 2 &&\Rightarrow\; v_1 = 2, \\ (1,2): \; & u_1 + v_2 = 3 &&\Rightarrow\; v_2 = 3, \\ (2,2): \; & u_2 + v_2 = 7 &&\Rightarrow\; u_2 = 4, \\ (2,3): \; & u_2 + v_3 = 5 &&\Rightarrow\; v_3 = 1, \\ (3,2): \; & u_3 + v_2 = 8 &&\Rightarrow\; u_3 = 5. \end{aligned}$$

Шаг 5. Оценки свободных клеток. Считаем $\Delta_{ij} = c_{ij} - (u_i + v_j)$ для каждой незанятой клетки:

$$\begin{aligned} \Delta_{13} &= 6 - (0 + 1) = 5, & \Delta_{21} &= 9 - (4 + 2) = 3, \\ \Delta_{31} &= 4 - (5 + 2) = -3, & \Delta_{33} &= 10 - (5 + 1) = 4. \end{aligned}$$

Оценка $\Delta_{31} = -3$ отрицательна: каждая тонна, переброшенная в клетку (3,1), удешевляет план на 3 ден. ед. Значит опорный план не оптимален.

Шаг 6. Цикл пересчёта. Из клетки (3,1) строим замкнутый цикл, все остальные вершины которого лежат в занятых клетках: (3,1) → (3,2) → (1,2) → (1,1) → (3,1). Расставляем знаки, начиная с плюса в клетке ввода: $+(3,1)$, $-(3,2)$, $+(1,2)$, $-(1,1)$.

Величина сдвига $\theta$ равна наименьшей перевозке в клетках со знаком минус:

$$\theta = \min(x_{32};\, x_{11}) = \min(80;\, 90) = 80.$$

Прибавляем 80 в клетках со знаком плюс и вычитаем в клетках со знаком минус:

$$x_{31} = 80, \quad x_{32} = 80 - 80 = 0, \quad x_{12} = 30 + 80 = 110, \quad x_{11} = 90 - 80 = 10.$$

Клетка (3,2) обнулилась и выходит из базиса, её место занимает (3,1). Новая стоимость:

$$Z_1 = Z_0 + \theta \cdot \Delta_{31} = 1450 - 80 \cdot 3 = 1210.$$

Шаг 7. Проверка нового плана на оптимальность. Пересчитываем потенциалы для нового набора занятых клеток (1,1), (1,2), (2,2), (2,3), (3,1): $u_1 = 0$, $v_1 = 2$, $v_2 = 3$, $u_2 = 4$, $v_3 = 1$, $u_3 = 4 - 2 = 2$. Оценки свободных клеток:

$$\Delta_{13} = 5, \quad \Delta_{21} = 3, \quad \Delta_{32} = 8 - (2 + 3) = 3, \quad \Delta_{33} = 10 - (2 + 1) = 7.$$

Все оценки строго положительны, улучшить план больше нечем.

Ответ. Оптимальный план перевозок: $x_{11} = 10$, $x_{12} = 110$, $x_{22} = 20$, $x_{23} = 80$, $x_{31} = 80$, остальные перевозки нулевые. Минимальная стоимость $Z_{\min} = 1210$ ден. ед. Метод минимального элемента дал 1450, одна итерация потенциалов сэкономила 240 ден. ед., то есть около 17 % затрат.

Из чего состоит решение транспортной задачи

В общем виде дано $m$ поставщиков с запасами $a_i$, $n$ потребителей с потребностями $b_j$ и тариф $c_{ij}$ на перевозку единицы груза из пункта $i$ в пункт $j$. Нужны объёмы перевозок, которые вывозят весь запас, закрывают весь спрос и стоят дешевле всего:

$$Z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \to \min, \qquad \sum_{j=1}^{n} x_{ij} = a_i, \qquad \sum_{i=1}^{m} x_{ij} = b_j, \qquad x_{ij} \ge 0.$$

Формально это задача линейного программирования, но с особой структурой: все коэффициенты ограничений равны нулю или единице, поэтому симплекс-таблица вырождается в обычную таблицу перевозок. Отсюда схема решения из двух частей: первая даёт стартовый допустимый план, вторая его улучшает.

Стартовый план называют опорным: он занимает ровно $m + n - 1$ клеток и соответствует базисному решению задачи ЛП. Способы его построить разобраны в статье про построение опорного плана; минимальный элемент здесь компромисс между скоростью и качеством стартовой точки.

Метод потенциалов отвечает на вопрос, выгодно ли пустить груз через пустующую клетку. Потенциалы $u_i$ и $v_j$ распределяют тариф каждого занятого маршрута между поставщиком и потребителем, а разность $\Delta_{ij} = c_{ij} - (u_i + v_j)$ показывает, насколько клетка дороже такого справедливого тарифа: отрицательная разность значит, что клетка дешевле и в неё нужно направить груз. Разбор процедуры есть в статье про метод потенциалов.

Проверка ответа через двойственную задачу

Потенциалы с последнего шага это не служебные числа, а решение двойственной задачи, поэтому у ответа есть независимая проверка: стоимость оптимального плана обязана совпасть со значением двойственной целевой функции.

$$\sum_{i=1}^{3} a_i u_i + \sum_{j=1}^{3} b_j v_j = (120 \cdot 0 + 100 \cdot 4 + 80 \cdot 2) + (90 \cdot 2 + 130 \cdot 3 + 80 \cdot 1) = 560 + 650 = 1210.$$

Сошлось с $Z_{\min} = 1210$ из прямого суммирования. Это следствие теоремы двойственности, а проверка занимает одну строку: если числа разошлись, ошибка либо в потенциалах, либо в плане.

Вторая проверка обязательна всегда: суммы по строкам итоговой таблицы должны дать запасы, суммы по столбцам потребности. В ответе $10 + 110 = 120$, $20 + 80 = 100$, $80 = 80$ по строкам и $10 + 80 = 90$, $110 + 20 = 130$, $80 = 80$ по столбцам.

Чем заменить метод минимального элемента

Опорный план строят и по-другому: от выбора зависит число итераций, но не ответ. Метод северо-западного угла не смотрит на тарифы и заполняет таблицу лесенкой от левой верхней клетки: на наших данных он даёт $Z = 1770$ и вдобавок вырожденный план с нулевой перевозкой в клетке (3,2).

Метод Фогеля тратит время на подготовку: в каждой строке и столбце считают штраф, разность двух наименьших тарифов, и груз идёт туда, где штраф максимален. На этих же числах он даёт 1240 ден. ед., а при другом разрешении ничьей в штрафах попадает прямо в оптимум 1210. Если метод в задании не назван, минимальный элемент остаётся безопасным выбором: он короче Фогеля и ближе к оптимуму, чем северо-западный угол.

Открытая модель и вырожденный план

Первая ловушка: суммы запасов и спроса не равны, модель открытая. Её закрывают фиктивным пунктом с нулевыми тарифами. Если запас больше спроса на $d$, добавляют фиктивного потребителя с потребностью $d$, и остаток груза остаётся на складах; если больше спрос, добавляют фиктивного поставщика с запасом $d$. Нулевые тарифы гарантируют, что фиктивные перевозки не изменят стоимость, а дальше задача решается как закрытая. Калькулятор сверху добавляет такой пункт сам и подсвечивает его серым.

Вторая ловушка: занятых клеток меньше $m + n - 1$. Так бывает, когда очередная перевозка исчерпывает сразу и запас строки, и потребность столбца, а уравнений для потенциалов становится меньше, чем нужно. Лечится это формально: в любую свободную клетку, не образующую замкнутого цикла с занятыми, ставят нулевую перевозку. Она считается занятой, добирает недостающее уравнение и на стоимость не влияет.

Частые ошибки

• Не проверяют баланс. Метод потенциалов работает только на закрытой модели: без фиктивного пункта план не сойдётся ни с запасами, ни со спросом.
• Считают опорный план ответом. Метод минимального элемента даёт допустимый, но обычно не оптимальный план: у нас 1450 против 1210. Без проверки оценок решение неполное.
• Забывают правило $m + n - 1$. При меньшем числе занятых клеток система для потенциалов недоопределена; нужна нулевая перевозка, а не «пропуск» неизвестного потенциала.
• Строят цикл через свободные клетки. Свободной в цикле может быть только клетка ввода, все остальные вершины обязаны быть занятыми.
• Берут $\theta$ по всем клеткам цикла. Сдвиг ограничивают только клетки со знаком минус: именно из них груз вычитается, а уйти в отрицательные перевозки нельзя.
• Останавливаются на первой отрицательной оценке. После пересчёта плана оценки считают заново: пока среди них есть отрицательная, решение не закончено.

FAQ

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

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

Чем транспортная задача отличается от задачи о назначениях? Задача о назначениях это её частный случай: таблица квадратная, запасы и потребности равны единице. Её быстрее решает венгерский алгоритм, хотя потенциалы тоже дадут верный ответ.

Можно ли запретить перевозку по конкретному маршруту? Да, такой клетке ставят заведомо большой тариф, в учебниках его обозначают буквой M. Метод потенциалов обойдёт её стороной: оценка останется положительной.

Коротко

1. Проверьте баланс: $\sum a_i = \sum b_j$. Если суммы не равны, закройте модель фиктивным поставщиком или потребителем с нулевыми тарифами.
2. Постройте опорный план методом минимального элемента и убедитесь, что занято ровно $m + n - 1$ клеток; при нехватке добавьте нулевую перевозку.
3. Найдите потенциалы из условия $u_i + v_j = c_{ij}$ для занятых клеток, приняв $u_1 = 0$.
4. Посчитайте оценки $\Delta_{ij} = c_{ij} - (u_i + v_j)$ для свободных клеток: все неотрицательны, план оптимален; иначе стройте цикл из клетки с самой отрицательной оценкой и сдвигайте по нему $\theta$ единиц.
5. В задаче из условия опорный план стоит 1450 ден. ед., а оптимальный после одной итерации 1210 ден. ед. при перевозках $x_{11} = 10$, $x_{12} = 110$, $x_{22} = 20$, $x_{23} = 80$, $x_{31} = 80$.