6.2. Умови застосування та основні кроки спеціального методу розв’язання ТЗ.

 Оскільки транспортна задача є різновидом задачі лінійного програмування, то вона може бути розв’язана сиплексним методом. Проте специфіка моделі дозволяє використовувати більш ефективний, спеціальний метод пошуку оптимуму. Згаданий метод може застосовуватись тільки по відношщленню до закритої транспотрної моделі, тобто при виконанні умови:  . Проте ця обставина не створює проблеми: відкриту модель завжди можна звести до закритої шляхом введення так званого «фіктивного постачальника» (при < ) або «фіктивного споживача» (при > ), що еквівалентно введенню балансових змінних (відповідно, m залишкових або n надлишкових).

Наведемо короткий опис алгоритму розв’язання транспортної задачі.

Крок 1. Знайти початковий допустимий розв’язок.

Крок 2. Перевірити поточний розв’язок на оптимальність. Якщо умова оптимальності виконується, закінчити процес розв’язання. В протилежному випадку перейти до кроку 3.

Крок 3. Визначити з числа небазисних змінних змінну, що потребує включення до базису.

Крок 4. Серед поточних небазисних змінних визначити змінну, що має бути виключена з базису.

Крок 5. Знайти новий базисний розв’язок. Повернутись до кроку 2.

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

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

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

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

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

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

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

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

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

                                                                   

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

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

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

Початковий план перевезень, представлений у табл. 6.5, потребує витрат у розмірі: Т(2)0. =15×1+20×2+15×8+5×7++15×2+10×0=240 (г.о.) і, отже, є кращим від розв’язку, що міститься в табл.6.4. Зазначимо, що в загальному випадку метод мінімальної вартості також забезпечує кращий початковий розв’язок, ніж метод північно-західного кута, оскільки враховує величини вартість одиничних перевезень.