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

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

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

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

Основной искомой величиной в данной модели является объем перевозок по каждому из возможных маршрутов (от поставщика к потребителю), который обеспечивает минимизацию общих транспортных расходов. Для нахождения этого решения существует несколько алгоритмов. В академической и практической среде наиболее часто применяются метод северо-западного угла, метод минимальных тарифов (или наименьшей стоимости), аппроксимация Фогеля, метод потенциалов и универсальный симплекс-метод. Также для решения могут использоваться программные средства, например, надстройка «Поиск решения» в Microsoft Office Excel.

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

Метод северо-западного угла — это итерационный алгоритм, который позволяет найти первоначальный допустимый (опорный) план для транспортной задачи. Этот план не обязательно является оптимальным по затратам, но служит отправной точкой для дальнейшей оптимизации с помощью более сложных методов, таких как метод потенциалов. Алгоритм был предложен американским математиком Джорджем Бернардом Данцигом в 1951 году. Свое характерное название он получил позже благодаря работам экономистов Абрахама Чэрнса и Уильяма Вейджера Купера.

Название метода является метафорой: верхняя часть распределительной таблицы условно принимается за «север», а левая — за «запад». Алгоритм предполагает строго последовательный перебор ячеек таблицы, начиная с самой верхней левой, то есть с «северо-западного угла». В каждую текущую ячейку записывается максимально возможный объем поставки, ограниченный либо запасом поставщика, либо потребностью потребителя.

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

Алгоритм применения метода: пошаговый пример

Чтобы детально разобрать сущность данного подхода, рассмотрим его применение на конкретном примере. Предположим, имеются следующие исходные данные:

• Три поставщика (склада): А1 с запасом 30 кг, А2 с запасом 40 кг, А3 с запасом 20 кг.
• Четыре потребителя (магазина): В1 с потребностью 20 кг, В2 с потребностью 30 кг, В3 с потребностью 30 кг, В4 с потребностью 10 кг.

Перед началом решения необходимо убедиться, что задача является закрытой, то есть суммарные запасы поставщиков равны суммарным потребностям потребителей. В нашем случае: 30 + 40 + 20 = 90 кг (запасы) и 20 + 30 + 30 + 10 = 90 кг (потребности). Условие выполняется.

1. Шаг 1. Начинаем заполнение с левой верхней («северо-западной») ячейки, находящейся на пересечении поставщика А1 и потребителя В1. В эту ячейку необходимо вписать максимальный объем поставки, который определяется как минимум из запаса поставщика (30 кг) и потребности потребителя (20 кг). Минимальное значение равно 20 кг. Записываем 20 в ячейку (А1, В1). Потребность потребителя В1 полностью удовлетворена, поэтому остальные ячейки в первом столбце (для В1) больше не заполняются. У поставщика А1 остается запас: 30 - 20 = 10 кг.
2. Шаг 2. Перемещаемся к следующей незаполненной «северо-западной» ячейке. Это будет ячейка (А1, В2). Сравниваем оставшийся запас поставщика А1 (10 кг) и потребность потребителя В2 (30 кг). Минимальное значение — 10 кг. Записываем 10 в ячейку (А1, В2). Теперь запасы поставщика А1 полностью исчерпаны, следовательно, оставшиеся ячейки в первой строке (для А1) больше не заполняются. У потребителя В2 остается неудовлетворенная потребность: 30 - 10 = 20 кг.
3. Шаг 3. Следующая по алгоритму ячейка — (А2, В2). Сопоставляем полный запас поставщика А2 (40 кг) и остаточную потребность потребителя В2 (20 кг). Минимальное значение — 20 кг. Записываем 20 в ячейку (А2, В2). Потребность потребителя В2 полностью закрыта, значит, второй столбец далее не заполняется. У поставщика А2 остается запас: 40 - 20 = 20 кг.
4. Шаг 4. Двигаемся дальше. Новая «северо-западная» ячейка — (А2, В3). Сравниваем остаток запаса у А2 (20 кг) и полную потребность В3 (30 кг). Минимальное значение равно 20 кг. Вносим 20 в ячейку (А2, В3). Запас поставщика А2 исчерпан, вторая строка полностью заполнена. У потребителя В3 остается потребность: 30 - 20 = 10 кг.
5. Шаг 5. Переходим к ячейке (А3, В3). Сравниваем запас поставщика А3 (20 кг) и остаточную потребность В3 (10 кг). Минимальное значение — 10 кг. Записываем 10 в ячейку (А3, В3). Потребность потребителя В3 полностью удовлетворена. У поставщика А3 остается запас: 20 - 10 = 10 кг.
6. Шаг 6. Остается последняя незаполненная ячейка (А3, В4). Остаточный запас поставщика А3 равен 10 кг, и потребность потребителя В4 также равна 10 кг. Записываем 10 в эту ячейку.

На этом этапе все запасы поставщиков полностью распределены, и все потребности потребителей полностью удовлетворены. Если бы на последнем шаге возник избыток или недостаток, это указывало бы на арифметическую ошибку в расчетах или на то, что задача изначально не была приведена к закрытому типу. Таким образом, метод северо-западного угла позволил нам построить первоначальный опорный план перевозок.