Рішення транспортної задачі методом північно-західного кута

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

Отже, розглянемо метод північно-західного кута. Для цього припустимо, що умова транспортної задачі задана у вигляді наступної транспортної таблиці:

Представлення транспортної задачі у вигляді таблиці

Тоді, згідно з алгоритмом, на першому кроці, із співвідношення знаходимо значення об’єму перевезень від першого постачальника до першого споживача. Зазначимо, що при цьому, можливі три варіанти:

1. Якщо , то , рядок  виключається з подальшого розгляду (запаси постачальника  повністю вичерпані), а потреби першого споживача  (стовпець ) зменшується на величину .
2. Якщо , то , стовпець  виключається з подальшого розгляду (потреби споживача  повністю задоволені), а наявність вантажу у першого постачальника  (рядок ) зменшується на величину .
3. Якщо , то , рядок  і стовпець  виключаються з подальшого розгляду. Даний варіант призводить до виродження вихідного плану.

Потім аналогічні операції проробляють з частиною таблиці, починаючи з її північно-західного кута. На останньому кроці процесу залишиться один рядок і один стовпець. Після заповнення комірки, яка знаходиться на їх перетині, обчислювальний процес методу північно-західного кута завершується.

Після завершення описаного процесу необхідно провести перевірку отриманого плану на вирожденність. Якщо кількість зайнятих комірок дорівнює , то план є невироджених, в іншому випадку – виродженим. Якщо план вироджений, тобто кількість зайнятих комірок виявилася меншою за число , то незаповнені комірки з мінімальними вартостями перевезень заповнюються нулями, щоб загальна кількість зайнятих комірок стала рівною . При цьому слід пам’ятати, що в таблиці не повинно бути жодного прямокутника, всі вершини якого є зайнятими комірками. До прикладу, змінні або не можуть бути одночасно базисними.

Метод північно-західного кута – приклад:

Знайти початковий опорний план перевезень транспортній задачі, заданої наступною таблицею:

Транспортна таблиця задачі

Для цього, на першому кроці, скориставшись співвідношенням  знаходимо значення об’єму перевезень від постачальника до споживача : .  Зазначимо, що в даному випадку, стовпець номер один транспортної таблиці  виключається з подальшого розгляду (потреби споживача номер один задоволені в повному обсязі), а наявність вантажу у першого постачальника зменшується на величину , тобто .

Перейшовши до кроку номер два, задовольняємо потреби другого пункту призначення. В результаті отримаємо: , тобто за рахунок залишку запасів першого пункту відправлення ми також, в повному обсязі, задовольнили потреби і споживача . Отже, стовпець номер два транспортної таблиці  виключається з розгляду, а наявність вантажу у постачальника  знову-таки зменшується: .

На третьому кроці, задовольняємо потреби споживача : (після задоволення потреб пунктів  та  третьому споживачеві від першого відправника дісталось лише одиниць продукції). Рядок  виключається з подальшого розгляду, а потреби третього споживача зменшуються на величину : . Зазначимо, що проробляючи аналогічні операції далі:

Крок 4: , стовпець виключається з подальшого розгляду, а наявність продукції на складі  зменшується на одиниць: .

Крок  5: , рядок виключається з подальшого розгляду, а потреби четвертого споживача зменшуються на одиниць: .

Крок 6: , стовпець виключається з подальшого розгляду, а наявність продукції на складі зменшується на одиниць: .

Крок  7: оскільки в транспортній таблиці залишився один рядок () та один стовпець () – це останній крок процесу, .

на сьомому кроці, отримаємо кінцеву таблицю, у зайнятих комірках якої містяться числа, які приймаємо в якості початкового опорного плану заданої транспортної задачі (з огляду на те, що кількість зайнятих комірок дорівнює являється невиродженим) з сумарними витратами  умовних одиниць.

Транспортна таблиця з опорним планом північно-західного кута

Зауваження: виходячи з того, що при складанні початкового опорного плану методом північно-західного кута вартість перевезення одиниці продукції не враховувалася, то побудований, у такий спосіб, план являється далеким від оптимального.

Блок-схема алгоритму побудови опорного плану транспотрної задачі методом північно-західного кута