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

Общее представление о транспортной задаче

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

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

Строки таблицы закрепляются за поставщиками с определенными товарно-материальными запасами. Столбцы таблицы закрепляются за потребителями с определенными потребностями. В ячейках таблицы на пересечении соответствующего потребителя и поставщика записывается цена перевозки, которая может быть выражена, например, в рублях за 1 килограмм груза).

Искомая (т. е. неизвестная) величина в транспортной задаче - это объем перевозки от поставщиков к потребителям, при котором общие затраты на транспортировку минимизируются. Данная величина может быть определена путем применения различных методов. Так, чаще всего обращаются к таким методам, как:

• метод северо-западного угла;
• метод минимальных тарифов;
• метод Фогеля;
• метод потенциалов;
• симплекс-метод.

Помимо этого, решение транспортной задачи можно быть также найдено в программном продукте Microsoft Office Excel.

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

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

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

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

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

Для того чтобы прояснить суть метода северо-западного угла, распишем пример решения одной транспортной задачи. В качестве начальных вводных условий мы будем предполагать существование поставщиков определенной продукции (поставщик А1 с запасом в 30 кг; поставщик А2 с запасом в 40 кг; поставщик А3 с запасом в 20 кг) и потребителей этой продукции (потребитель В1 с потребностью в 20 кг, потребитель В2 с потребностью в 30 кг, потребитель В3 с потребностью в 30 кг, потребитель В4 с потребностью в 10 кг).

Распределение поставок продукции начинается с первой, «северо-западной» ячейки транспортной таблицы, где пересекаются поставщик А1 и потребитель В1. В ячейку вписывается максимальный объем, который позволяет и запас поставщика, и спрос потребителя. Этот объем соответствует минимуму между заявленными запасами поставщика А1 (30 кг) и потребностями потребителя В1 (20 кг).

Следовательно, в ячейку записывается значение 20 кг. Спрос потребителя В1 полностью удовлетворен, поэтому ячейки соответствующего (первого) столбца заполняться больше не будут.

Переходим в следующую северо-западную ячейку, которая соответствует пересечению поставщика А1 и потребителя В2. В данном случае минимум выбираем между 10 кг запасов поставщика А1 и 30 кг потребностей потребителя В2.

В ячейку записывается значение 10 кг. Запасы поставщика А1 полностью исчерпаны, поэтому ячейки соответствующей (первой) строки заполняться больше не будут.

Следующая «северо-западная» ячейка - это пересечение поставщика А2 и потребителя В2. Здесь в ячейку будет записано значение в 20 кг. После этого спрос потребителя В2 окажется полностью удовлетворенным, в связи с чем в дальнейшем ячейки второго столбца заполняться не будут.

При переходе к следующей «северо-западной» ячейке будут сопоставляться запасы поставщика А2 (20 кг) и спрос потребителя В3 (30 кг). В ячейку запишут значение 20 кг. Это будет свидетельствовать об исчерпании всех запасов у поставщика А2, поэтому вторая строка больше заполняться не будет.

Дальше предметом изучения станет сопоставление данных по поставщику А3 (запасы - 20 кг) и потребителю В3 (спрос - 10 кг). Для заполнения ячейки запишем в нем значение в 10 кг.

И наконец остается последняя ячейка, которая соответствует «столкновению» запасов поставщика А3 и потребностей потребителя В4. Согласно условиям нашего примера, они равны друг другу - по 10 кг. Следовательно, весь груз от поставщиков (продукция) должен быть распределен по потребителям. Если же на данном этапе был зафиксирован недостаток или избыток груза, то это означает, что была допущена арифметическая ошибка, или задача не была приведена к закрытому виду.