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

Рассмотрим транспортную задачу по следующим исходным данным, представленным в виде таблицы:

 

ПН ПО	В 1	В 2	В 3	В 4	В 5	Запасы а i
А 1
А 2
А 3
Потребнос- ти bj

 

В методе северо-западного угла, или диагональном, заполнение транспортной таблицы всегда начинается с клетки (А ₁, В ₁), т.е. “северо-западного угла” таблицы. Далее заполнение идет вокруг диагонали таблицы и всегда заканчивается в правом нижнем углу (клетка (А ₃, В ₅ )). В каждой клетке объем перевозки определяется как наименьшее значение из двух чисел: остатка запаса на базе и остатка заявки потребителя. Отсюда:

х ₁₁ = min { a ₁, b ₁ } = { 200; 70 } = 70.

Таким образом, заявка первого потребителя выполняется в полном объеме, поскольку на базе имелся больший запас товара. Поэтому остальные клетки первого столбца не нужны и остаются пустыми.

Далее наступает очередь второго заказчика, который со своей заявкой приходит на первую базу, где еще остался товар:

х ₁₂ = min { 200 - 70; 80 } = { 130; 80 } = 80.

Он также получает всё, и остальные клетки второго столбца также будут пустыми.

Теперь на первой базе осталось только 50 т груза. Поэтому третий заказчик получит только эти 50 т, хотя ему требуется 150 т.

х ₁₃ = min { 200 – 70 – 80; 150} = 50.

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

Остальную часть своего заказа второй заказчик получит на второй базе:

х ₂₃ = min { 200; 150 – 50 } = 100.

Далее поцесс повторяется для остальных заказчиков, в результате чего получаем опорный план:

 

ПН ПО	В 1	В 2	В 3	В 4	В 5	а i
А 1				¾	¾
А 2	¾	¾
А 3	¾	¾	¾
b j

 

В этом опорном плане семь занятых клеток. Поскольку их должно быть m +n – 1, где m – число баз, n - число заказчиков, план является невырожденным. Если бы клеток было меньше, чем m +n – 1, план был бы вырожденным.

Осталось подсчитать общую стоимость перевозок. Она складывается из произведений объемов перевозок и тарифов по всем занятым клеткам, т.е.:

F (X ₁ ) = 70 × 4 + 80 × 11 + 50 × 5 + 100 × 9 + 100 × 13 + 10 × 7 + 90 × 20 = 5530.

Как видим, при распределении грузов совсем не учитывается стоимость перевозок. Поэтому, как правило, метод северо-западного угла дает опорный план, далекий от оптимального.