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

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

Алгоритм выполнения

Метод северо-западного угла применяется для транспортной задачи, представленной в виде таблицы размером \(m \times n\), где \(m\) — число поставщиков (строки), \(n\) — число потребителей (столбцы). Алгоритм состоит из следующих шагов:

1. Начальная установка. Выбирается ячейка, находящаяся на пересечении первой строки и первого столбца (северо-западный угол таблицы). Задаётся переменная \(i = 1\) (индекс строки) и \(j = 1\) (индекс столбца).
2. Определение объёма перевозки. В выбранную ячейку \( (i, j) \) записывается максимально возможная перевозка, которая равна минимальному из двух значений:

• Остатка запаса поставщика \(i\) (изначально — \(a_i\));
• Остатка потребности потребителя \(j\) (изначально — \(b_j\)).

Формально: \(x_{ij} = \min(a_i, b_j)\).

1. Корректировка остатков. После записи объёма перевозки:

• Из запаса поставщика \(i\) вычитается значение \(x_{ij}\): \(a_i = a_i - x_{ij}\);
• Из потребности потребителя \(j\) вычитается значение \(x_{ij}\): \(b_j = b_j - x_{ij}\);

1. Переход к следующей ячейке.

• Если после корректировки запас поставщика \(i\) полностью исчерпан (\(a_i = 0\)), то строка \(i\) исключается из рассмотрения. Индекс строки увеличивается на 1 (\(i = i + 1\)).
• Если потребность потребителя \(j\) полностью удовлетворена (\(b_j = 0\)), то столбец \(j\) исключается. Индекс столбца увеличивается на 1 (\(j = j + 1\)).
• Случай, когда одновременно исчерпаны и запас, и потребность, обрабатывается переходом на следующую строку и следующий столбец (\(i = i + 1\), \(j = j + 1\)).

1. Повторение шагов 2–4 до тех пор, пока не будут рассмотрены все строки и столбцы. Процесс заканчивается, когда \(i = m+1\) и \(j = n+1\).

В результате заполняется \(m + n - 1\) ячеек (базисные переменные), остальные клетки остаются пустыми (свободные переменные, равные нулю). Это количество обусловлено тем, что в транспортной задаче ранг матрицы ограничений равен \(m + n - 1\).

Пример

Постановка задачи: три поставщика с запасами \(A = (50, 30, 20)\) и четыре потребителя с потребностями \(B = (25, 35, 20, 20)\). Транспортная таблица изначально пуста. Применение метода северо-западного угла даёт последовательность:

1. Ячейка (1,1): \(x_{11} = \min(50, 25) = 25\). Остаток запаса первого поставщика \(50 - 25 = 25\); потребность первого потребителя равна 0. Переход к столбцу 2.
2. Ячейка (1,2): \(x_{12} = \min(25, 35) = 25\). Остаток запаса равен 0; остаток потребности потребителя \(35 - 25 = 10\). Переход к строке 2.
3. Ячейка (2,2): \(x_{22} = \min(30, 10) = 10\). Остаток запаса \(30 - 10 = 20\); потребность равна 0. Переход к столбцу 3.
4. Ячейка (2,3): \(x_{23} = \min(20, 20) = 20\). Остатки запаса и потребности становятся нулевыми. Переход к строке 3 и столбцу 4.
5. Ячейка (3,4): \(x_{34} = \min(20, 20) = 20\). Задача завершена.

Итоговый опорный план: \(X = (25, 25, 0, 0; 0, 10, 20, 0; 0, 0, 0, 20)\).

Особенности и свойства

• Простота реализации. Метод не требует вычисления оценок и сравнения стоимостей, что позволяет получить решение за минимальное число операций. Пригоден для ручного счёта и небольших задач.
• Отсутствие учёта стоимости. Алгоритм полностью игнорирует коэффициенты затрат на перевозку (тарифы). Это главный недостаток: полученный план почти всегда далёк от оптимального по стоимости, особенно при существенных различиях в тарифах.
• Гарантированное построение опорного плана. Метод всегда приводит к допустимому решению, удовлетворяющему балансу между общим запасом и суммарной потребностью (при условии сбалансированности задачи — равенства суммарных запасов и потребностей). Если задача несбалансирована, её предварительно приводят к балансу введением фиктивного поставщика или потребителя.
• Вырождение плана. Возможна ситуация «вырождения», когда на некотором шаге одновременно исчерпываются запас и потребность, а количество заполненных клеток оказывается меньше \(m + n - 1\). В таких случаях в одну из пустых клеток искусственно вписывается нулевая поставка (так называемая «фиктивная» перевозка), чтобы соблюсти условие невырожденности, необходимое для применения методов оптимизации.
• Итеративный характер. План, полученный методом северо-западного угла, является лишь отправной точкой. Для нахождения оптимального решения требуется последующее применение одного из методов улучшения, например, метода потенциалов (модифицированного распределительного метода).

Сравнение с методом минимального элемента

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

Применение

Метод северо-западного угла используется в учебных целях для демонстрации итеративного характера решения транспортной задачи и как базовый инструмент при изучении линейного программирования. В практических задачах логистики и управления цепями поставок он применяется редко из-за неоптимальности; однако в некоторых системах, где стоимость вычислений критична (например, встроенные системы реального времени), скоростью получения допустимого решения можно пренебречь ради экономии вычислительных ресурсов. Также метод может быть полезен как генератор случайных начальных планов для эвристических алгоритмов (например, генетических алгоритмов).

Критика

Основная критика метода связана с его экономической неэффективностью. Игнорирование стоимостей приводит к тому, что на практике он часто порождает планы, требующие большого числа итераций для дальнейшей оптимизации. Кроме того, метод не учитывает возможные логистические ограничения (например, пропускную способность маршрутов), которые могут быть отражены только в тарифах. В современной вычислительной практике с развитием быстрых решателей (симплекс-метод, внутренняя точка) метод северо-западного угла утратил значение как самостоятельный инструмент.

Источники

• Акулич И. Л. Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986.
• Таха Х. А. Введение в исследование операций. — 7-е изд. — М.: Вильямс, 2005.
• Вентцель Е. С. Исследование операций: задачи, принципы, методология. — М.: Наука, 1980.
• Кузнецов А. В., Сакович В. А., Холод Н. И. Высшая математика: Математическое программирование. — М.: Вышейшая школа, 1994.