Сущность метода северо-западного угла

При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного х₁₁ («северо-западный угол») и заканчивается клеткой для неизвестного х_тп, т. е. идет как бы по диагонали таблицы.

Пример. На три базы А₁,А₂, А₃ поступил однородный груз в количествах, соответственно равных 140, 180 и 160 ед. Этот груз требуется перевезти в пять пунктов назначения В₁ В₂, В₃, В₄, В₅ соответственно в количествах 60, 70, 120, 130 и 100 ед. Тарифы перевозок единицы груза из каждого пункта отправления в соответствующие пункты назначения указаны в табл. 2.13.

Требуется найти план перевозок данной транспортной задачи методом северо-западного угла.

Решение. Здесь число пунктов отправления m = 3, а число пунктов назначения n=5. Следовательно, опорный план задачи определяется числами, стоящими в 5+3-1=7 заполненных клетках.

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

Таблица 2.13

Пункты отправления	Пункты назначения	Запасы
В1	B2	В3	В4	В5
А1
A2
Аз
Потребности

Так как запасы пункта А₁ больше, чем потребности пункта В₁, то полагаем х₁₁= 60, записываем это значение в соответствующей клетке табл. 2.14 и временно исключаем из рассмотрения столбец B₁, считая при этом запасы пункта А₁ равными 140 – 60 = 80. Теперь в пункте A₁ осталось 80 единиц груза; этим количеством можно удовлетворить потребности пункта B₂. Положим х₁₂ = 70, запишем это значение в соответствующей клетке табл. 2.14 и временно исключим из рассмотрения столбец В₂. После этого в A₁ остается еще 80 -70=10 единиц груза; отдадим их пункту B₃. Потребности пункта В₃ больше оставшихся запасов пункта А₁. Положим х13=10 и исключим из рассмотрения строку А₁. Значение x1₃=10 запишем в соответствующую клетку табл. 2.14 и считаем потребности пункта В₃ равными 110 ед. Но заявка этого пункта еще не удовлетворена полностью; выделим недостающие 120 - 10=110 единиц из запасов других пунктов отправления.

Теперь перейдем к заполнению клетки для неизвестного x₂₃ и т. д. Через шесть шагов остается один пункт отправления А₃ с запасом груза 100 ед. и один пункт назначения В₅ с потребностью 100 ед. Соответственно, имеется одна свободная клетка, которую и заполняем, полагая x₃₅ = 100 (табл. 2.15).

В результате получаем опорный план

Таблица 2.14

Пункты отправления	Пункты назначения	Запасы
В1	B2	В3	В4	В5
А1
A2
Аз
Потребности

Таблица 2.15

Пункты отправления	Пункты назначения	Запасы
В1	B2	B3	B4	B5
А1
A2
Аз
Потребности

Согласно данному плану перевозок, общая стоимость перевозок всего груза составляет

F=2·60 + 3·70 + 4·10+1·110 + 4·70 +7·60 + 2·100 = 1380.

Дата добавления: 2014-01-07