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

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

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

Транспортная задача - это задача линейного программирования: есть $m$ поставщиков с запасами $a_1, a_2, \dots, a_m$ и $n$ потребителей с потребностями $b_1, b_2, \dots, b_n$. Стоимость перевозки единицы груза от поставщика $i$ к потребителю $j$ равна $c_{ij}$. Нужно найти объёмы перевозок $x_{ij} \ge 0$, при которых все запасы вывезены, все потребности закрыты, а суммарная стоимость

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

минимальна. Задача называется сбалансированной (закрытой), когда сумма запасов равна сумме потребностей: $\sum a_i = \sum b_j$. Только для такой задачи метод северо-западного угла применяется напрямую; несбалансированную сначала закрывают фиктивным поставщиком или потребителем с нулевыми стоимостями.

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

Алгоритм метода северо-западного угла

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

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

Пошагово алгоритм выглядит так:

1. Встаём в северо-западную (левую верхнюю) клетку $(1,1)$.
2. В текущую клетку $(i,j)$ записываем перевозку $x_{ij} = \min(a_i, b_j)$ - сколько можно реально перевезти, ограничено меньшим из остатков.
3. Вычитаем эту величину из остатка запаса строки и остатка потребности столбца: $a_i \leftarrow a_i - x_{ij}$, $b_j \leftarrow b_j - x_{ij}$.
4. Если исчерпан запас строки ($a_i = 0$) - переходим на клетку ниже, в следующую строку. Если исчерпана потребность столбца ($b_j = 0$) - переходим вправо, в следующий столбец.
5. Повторяем, пока не дойдём до правой нижней клетки и не распределим весь груз.

Из-за этого правила движения заполненные клетки складываются в характерную ступенчатую линию - ту самую лесенку из северо-западного угла в юго-восточный.

Формула и баланс m + n - 1

Главная проверка корректности опорного плана - число занятых клеток. Для невырожденного плана оно равно

$N = m + n - 1,$

где $m$ - число строк (поставщиков), $n$ - число столбцов (потребителей). Для задачи $3 \times 4$ это $3 + 4 - 1 = 6$ клеток, для $3 \times 3$ - пять, для $2 \times 3$ - четыре.

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

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

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

Возьмём базовый сценарий калькулятора. Запасы поставщиков: $a = (30, 40, 20)$, потребности потребителей: $b = (20, 30, 25, 15)$. Сумма запасов $30 + 40 + 20 = 90$ равна сумме потребностей $20 + 30 + 25 + 15 = 90$ - задача сбалансирована. Матрица стоимостей:

$C = \begin{pmatrix} 4 & 6 & 8 & 5 \\ 3 & 5 & 7 & 6 \\ 2 & 4 & 3 & 7 \end{pmatrix}.$

Идём по лесенке:

• Клетка $(1,1)$: $\min(30, 20) = 20$. Столбец 1 закрыт, остаток строки 1 равен $10$.
• Клетка $(1,2)$: $\min(10, 30) = 10$. Строка 1 закрыта, остаток столбца 2 равен $20$.
• Клетка $(2,2)$: $\min(40, 20) = 20$. Столбец 2 закрыт, остаток строки 2 равен $20$.
• Клетка $(2,3)$: $\min(20, 25) = 20$. Строка 2 закрыта, остаток столбца 3 равен $5$.
• Клетка $(3,3)$: $\min(20, 5) = 5$. Столбец 3 закрыт, остаток строки 3 равен $15$.
• Клетка $(3,4)$: $\min(15, 15) = 15$. Всё распределено.

Заполнено шесть клеток - ровно $m + n - 1 = 3 + 4 - 1 = 6$, план невырожденный. Считаем стоимость, перемножая объёмы на стоимости занятых клеток:

$Z = 4\cdot20 + 6\cdot10 + 5\cdot20 + 7\cdot20 + 3\cdot5 + 7\cdot15.$

$Z = 80 + 60 + 100 + 140 + 15 + 105 = 500.$

Стоимость опорного плана равна $500$. Это не минимум - метод северо-западного угла игнорирует стоимости, и почти всегда найдётся план дешевле. Но как стартовая точка для метода потенциалов он годится: дальше план улучшают, перераспределяя груз по циклам пересчёта.

Чем северо-западный угол отличается от метода минимального элемента

Метод северо-западного угла - не единственный способ получить опорный план. Часто рядом изучают метод минимальной стоимости (минимального элемента) и метод Фогеля. Разница в том, какую клетку загружать первой:

• Северо-западный угол заполняет клетки строго по географии таблицы - сверху-слева вниз-вправо, не глядя на $c_{ij}$. Самый быстрый и механический, но даёт самый дорогой стартовый план.
• Метод минимального элемента на каждом шаге выбирает свободную клетку с наименьшей стоимостью. План получается ближе к оптимуму, но строится дольше.
• Метод Фогеля учитывает штрафы (разности двух минимальных стоимостей в строке и столбце) и обычно стартует почти от оптимума.

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

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

• Забыли проверить баланс. Если $\sum a_i \ne \sum b_j$, метод напрямую не работает. Сначала добавьте фиктивного поставщика или потребителя с нулевыми стоимостями, закрыв разницу.
• Загрузили не минимум, а произвольное число. В клетку всегда пишется ровно $\min(a_i, b_j)$, иначе либо запас уйдёт в минус, либо потребность будет превышена.
• Двинулись по диагонали. После заполнения клетки можно уйти только вправо (закрылся столбец) или вниз (закрылась строка), но не сразу по диагонали - так теряется базисная клетка.
• Пропустили вырожденность. Если занятых клеток меньше $m + n - 1$, план вырожден. Метод потенциалов на таком плане сорвётся, пока не поставите нулевую базисную перевозку.
• Считают, что это и есть ответ. Северо-западный угол даёт лишь опорный план. Минимальную стоимость находят уже методом потенциалов, улучшая полученное распределение.

FAQ

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

Даёт ли метод северо-западного угла оптимальный план? Нет. Метод не использует стоимости перевозок, поэтому полученный план почти всегда дороже оптимального. Его роль - быстро дать допустимый опорный план, который затем улучшают методом потенциалов до минимальной стоимости.

Что делать, если транспортная задача не сбалансирована? Ввести фиктивного участника. Если запасов больше, чем потребностей, добавляют фиктивного потребителя с потребностью, равной излишку, и нулевыми стоимостями. Если потребностей больше - фиктивного поставщика. После этого задача становится закрытой и метод применяется как обычно.

Коротко

Метод северо-западного угла строит опорный план транспортной задачи, заполняя таблицу от левой верхней клетки к правой нижней: в каждую клетку пишут $x_{ij} = \min(a_i, b_j)$, закрывают исчерпанную строку или столбец и сдвигаются вправо-вниз. Корректный невырожденный план содержит ровно $m + n - 1$ занятых клеток, а его стоимость считается как $Z = \sum c_{ij} x_{ij}$. Это лишь стартовый план: оптимум находят дальше методом потенциалов.