Опорный план транспортной задачи: три метода построения

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

Что такое опорный план транспортной задачи

Транспортная задача - это задача о минимальных затратах на перевозку однородного груза от $m$ поставщиков с запасами $a_1, \dots, a_m$ к $n$ потребителям со спросом $b_1, \dots, b_n$, если тариф перевозки единицы груза от поставщика $i$ к потребителю $j$ равен $c_{ij}$. Задача решается только когда она сбалансирована - суммарный запас равен суммарному спросу:

$\sum_{i=1}^m a_i = \sum_{j=1}^n b_j.$

Если это равенство не выполняется, в таблицу сначала вводят фиктивного поставщика или потребителя с нулевыми тарифами, который забирает или отдаёт разницу, - и только потом строят план.

Опорным (начальным допустимым) называют план перевозок $x_{ij}$, в котором вывезен весь запас каждого поставщика, удовлетворён весь спрос каждого потребителя и число занятых (базисных) клеток таблицы равно ровно $m + n - 1$. Меньше клеток означает вырожденный план, больше - избыточность и цикл в структуре перевозок. Опорный план сам по себе почти никогда не оптимален: у него нет обязанности минимизировать стоимость, только не нарушать баланс. Дальше его улучшают методом потенциалов, но стартовая точка сильно влияет на то, сколько итераций до оптимума потребуется.

Как метод выбирает путь по таблице перевозок

Рассчитать для своей задачи

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

Метод северо-западного угла

Это самый механический способ: он не смотрит в таблицу тарифов вообще, только на объёмы. Алгоритм стартует в клетке $(1,1)$ и на каждом шаге:

1. записывает в текущую клетку $x_{ij} = \min(a_i, b_j)$;
2. вычитает эту величину из остатка запаса $a_i$ и остатка спроса $b_j$;
3. если обнулился запас строки - сдвигается на строку вниз; если обнулился спрос столбца - сдвигается на столбец вправо.

Метод гарантированно закрывает баланс за $m + n - 1$ шагов и никогда не требует проверки на допустимость - в этом его главное достоинство. Подробный разбор с отдельным калькулятором под таблицы разного размера - в статье про метод северо-западного угла.

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

Этот метод уже учитывает тарифы, но жадно и локально. На каждом шаге среди всех ещё открытых клеток (строка и столбец которых не закрыты) выбирается та, где тариф $c_{ij}$ минимален, и в неё записывается $x_{ij} = \min(a_i, b_j)$ - максимум, который туда поместится. Строка закрывается, если исчерпан запас, столбец - если исчерпан спрос; если оба исчерпались одновременно, закрывают только одну из них, чтобы не потерять базисную клетку. Метод обычно даёт план дешевле северо-западного угла, но его слабость - локальность: дешёвая клетка, выбранная рано, может вынудить дорогие клетки позже, когда выбора уже не остаётся. Развёрнутый алгоритм с примером - в статье про метод минимального элемента.

Метод Фогеля: штрафы за отказ от лучшей ставки

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

1. выбирают строку или столбец с максимальным штрафом (если максимум одновременно у нескольких - берут любую строку раньше столбца);
2. в выбранной строке или столбце заполняют клетку с минимальным тарифом на весь возможный объём;
3. закрывают исчерпанную строку или столбец и пересчитывают штрафы заново для оставшейся части таблицы.

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

Проверка на вырожденность и сравнение стоимости

Рассчитать для своей задачи

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

$Z = \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij}$

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

Пример решения типовой задачи

Возьмём задачу с тремя поставщиками и тремя потребителями. Запасы $a = (50, 60, 90)$, спрос $b = (80, 70, 50)$ - баланс сходится, обе суммы равны 200 единицам груза. Тарифы заданы таблицей:

$$\begin{aligned} &c_{11}=4,\ c_{12}=6,\ c_{13}=8 \\ &c_{21}=3,\ c_{22}=5,\ c_{23}=2 \\ &c_{31}=9,\ c_{32}=1,\ c_{33}=7 \end{aligned}$$

Северо-западный угол заполняет клетки по диагонали: $x_{11}=50$ (запас поставщика 1 исчерпан), $x_{21}=30$ (спрос потребителя 1 закрыт), $x_{22}=30$ (запас поставщика 2 исчерпан), $x_{32}=40$ (спрос потребителя 2 закрыт), $x_{33}=50$. Занято ровно 5 клеток при $m+n-1=5$ - план невырожденный. Стоимость:

$Z_{СЗУ} = 50\cdot4 + 30\cdot3 + 30\cdot5 + 40\cdot1 + 50\cdot7 = 830.$

Метод минимального элемента сразу цепляется за тариф $c_{32}=1$: $x_{32}=70$, дальше $x_{23}=50$, $x_{21}=10$, $x_{11}=50$, $x_{31}=20$. Стоимость этого плана $Z_{МЭ} = 70\cdot1 + 50\cdot2 + 10\cdot3 + 50\cdot4 + 20\cdot9 = 580$. Метод Фогеля на этих же данных приходит к тому же набору занятых клеток и той же стоимости 580 - оба метода, учитывающих тариф, обходят северо-западный угол почти на треть. Разница между 830 и 580 - это не мелочь, а прямое следствие того, что метод северо-западного угла в принципе не видит таблицу тарифов при построении плана.

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

• Путают опорный план с оптимальным. Это только допустимая стартовая точка, а не ответ задачи - минимум стоимости доказывается методом потенциалов.
• Не проверяют баланс перед построением. Если сумма запасов не равна сумме спроса, все три метода дадут несбалансированный план - сначала вводят фиктивного поставщика или потребителя.
• Забывают проверить план на вырожденность. Если занятых клеток меньше $m+n-1$, метод потенциалов не запустится без нулевой базисной клетки - это упускают чаще всего после метода минимального элемента, где строка и столбец могут закрыться одновременно.
• В методе Фогеля пересчитывают штрафы не для всей оставшейся таблицы. После каждого шага их нужно считать заново, а не переиспользовать с предыдущей итерации.
• Останавливаются на первом построенном плане. Даже невырожденный и сбалансированный план не гарантирует оптимальность - без метода потенциалов это неизвестно.

FAQ

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

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

Что делать, если опорный план получился вырожденным? Добавить недостающие базисные клетки с нулевым объёмом перевозки - обычно берут свободную клетку с наименьшим тарифом так, чтобы не образовался замкнутый цикл среди уже занятых. После этого число базисных клеток равно $m+n-1$, и можно запускать метод потенциалов.

Коротко

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