Транспортна задача метод апроксимації Фогеля, Галяутдінов
Серед чотирьох, найчастіше застосовуються на практиці, методів формування опорного плану в транспортній задачі найнезвичайніший - метод апроксимації Фогеля. Послідовність дій при його використанні зовсім інша, ніж при заповненні транспортної таблиці методом «Північно-Західного кута» або методом «Мінімального елемента». На перший погляд апроксимація Фогеля складніше, але це помилкове враження. Метод простий і дозволяє отримати опорний план більш наближений до оптимального рішення, ніж в разі застосування інших методів (за винятком хіба що методу «Подвійного переваги»).
Сутність апроксимації Фогеля в знаходженні різниці (по модулю) між парою мінімальних тарифів в кожному рядку і стовпці. Потім рядок або стовпець з найбільшою різницею заповнюються в напрямку від клітини з мінімальним тарифом до клітки з максимальним. Детальніше далі.
ФОРМУВАННЯ опорною ПЛАНУ МЕТОДОМ АПРОКСИМАЦІЇ Фогель
Насамперед додаємо до транспортної таблиці додаткові рядок і стовпець. Далі знаходимо для кожного рядка і кожного стовпця абсолютні різниці (по модулю, тобто без знака) між двома мінімальними тарифами. Якщо в рядку / стовпці дві клітини з однаковими і мінімальними значеннями тарифів, то беремо саме їх. Тоді різниця буде дорівнює 0.
Знайдені різниці виписуємо в додатковий стовпець і додаткову рядок.
Серед обчислених різниць (і по рядках, і по стовпцях!) Вибираємо найбільшу.
Потім в рядку (або стовпці), якій відповідає максимальна різниця, шукаємо клітку з мінімальним тарифом. Заповнюємо її.
Якщо клітин з мінімальним тарифом кілька, то заповнюємо ту з них, якій відповідає найбільша різниця.
Потім повторюємо всі вищеописані дії знову, тільки вже не з огляду на заповнені клітини. І так до тих пір, поки не буде повністю знайдений опорний план.
Решта осередку транспортної матриці вже і так очевидно яким чином слід заповнити:
В результаті ми отримуємо опорний план:
Найчастіше опорний план, отриманий аппроксимацией Фогеля, виявляється або відразу оптимальним (як в цьому прикладі), або дуже близьким до оптимального. Але саме часто, а не завжди!