6.3 Методи одержання початкового розв’язку транспортної задачі.

Розглянемо два найбільш поширені методи визначення початкового розв’язку ТЗ: метод північно-західного кута та метод мінімальної вартості. 

6.3.1. Метод «північно-західного кута»

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

Спочатку до базису вводиться змінна x11 (розташована в північно-західному куті таблиці). Змінній x11 присвоюють максимальне значення, що допускається обмеженнями на попит і пропозицію, тобто min {a1, b1}. Це значення заноситься до відповідної комірки транспортної таблиці. Після цього викреслюють відповідний рядок або стовпець. Якщо обмеження, які представляють стовпець і рядок, виконуються водночас, то до будь-якої з двох сусідніх комірок таблиці (x12 або x21) слід ввести 0; після цього рядок і стовпець виключаються з подальшого розгляду. В тій частині таблиці, що залишилася, знаходять новий «північно-західний» елемент  (x12, x21 або x22 ) і виконують для нього ті ж дії. Аналогічна процедура виконується для елементів, що залишилися, і повторюється доти, поки не будуть заповнені (m+n-1) комірок транспортної таблиці. 

Змінні, значення яких не записані у відповідні комірки (небазисні змінні), припускаються рівними нулю. Наявність нульових базисних змінних свідчить про виродженість розв’язку. 

Приклад 6.2. Вихідні дані задачі подані в табл. 5.2, а початковий допустимий розв’язок, отриманий методом північно-західного кута - в табл. 6.3.

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

Стовпець G відповідає фіктивному споживачу з нульовою вартістю перевезень та обсягом споживання 10 одиниць ( - =80- 70= =10). 

Таблиця 6.3 – Вихідні дані задачі 5.2

Отриманому початковому опорному плану перевезень відповідає така величина транспортних витрат: Т(1)0=. =153+52+308+202=335 (г.о.).

5.3.2. Метод мінімальної вартості

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

Таблиця 5.5 - Початковий розв’язок транспортної задачі, знайдений методом мінімальної вартості

Початковий план перевезень, представлений у табл. 5.5, потребує витрат у розмірі: Т(2)0. =202+207+151+159=330 (г.о.) І, отже, є кращим від розв’язку, що міститься в табл.5.4. Зазначимо, що в загальному випадку метод мінімальної вартості також забезпечує кращий початковий розв’язок, ніж метод північно-західного кута, оскільки враховує величини вартість одиничних перевезень.