Розв’язання транспортної задачі методом потенціалів у Excel з прикладом

Розв'яжемо транспортну задачу методом потенціалів. Нам відомі торгові запаси, споживчі запити та вартість доставки за одиницю продукції. Зробимо три вихідні таблиці.

Побудуємо опорний план транспортного завдання за допомогою інструмента «Пошук рішень». Поруч складемо такі самі за обсягом таблиці з порожніми осередками. Таблиця А - аналог вартісної, Б - "запасів", В - "попиту".

Елементи таблиці Б – сума відповідних рядків у таблиці А. Елементи таблиці У – сума відповідних стовпців у таблиці А.

Окремо складемо результуючу таблицю Г. У ній відіб'ються оптимальні транспортні витрати. Кожен елемент таблиці Р – добуток елемента і відповідного елемента вартісної таблиці.

В окремому місці листа введемо формулу функції: = СУММПРОИЗВ (A1: C3;

Перший масив – вартісна таблиця, другий – діапазон А.

Ставимо курсор у комірку зі значенням функції. Викликаємо інструмент «Пошук рішення». Заповнюємо діалогове вікно:

У відкритому діалоговому вікні натискаємо кнопку «Параметри» та встановлюємо наступні налаштування:

Тиснемо ОК - "Виконати". Отримуємо опорний план транспортного завдання:

Він залитий блідо-зеленим кольором. Осередки зі значеннями вище нуля називаються «базисними», «зайнятими». Осередки зі значенням 0 – «вільними».

Далі діємо за планом:

Порахуємо число зайнятих клітин за допомогою функції РАХУНКИ.

Оскільки результат дорівнює 5, опорний план не виродженим. Перевіримо оптимальність опорного плану – знайдемо потенціали із зайнятих клітин.

Потрібно скласти систему рівнянь. Передбачається, що αj = 0, а αi + βj = сij (вартість доставки одиниці вантажу). Викликаємо команду «Пошук рішення». Вносимо умовисистеми рівнянь як обмеження.

Заповнене діалогове вікно:

Результат роботи інструменту «Пошук рішення»:

Порахуємо оцінки вільних клітин. Формула: сij - (αi + βj). Беремо вільну клітину з таблиці А. Дивимося її значення у вартісній таблиці. Це буде сij. Далі дивимося, які потенціали відповідають цій клітині. Вставляємо їх значення у формулу.

У програмі Excel знайдемо оцінки за допомогою математичних операторів та посилань на відповідні осередки.

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

Знаходимо, якій клітині таблиці А відповідає мінімальна оцінка. Будуємо для цієї клітини цикл – замкнуту ламану лінію. Умови: обов'язкове чергування вертикального та горизонтального напряму, лише за базисними клітинами.

У вихідній клітині (з мінімальною оцінкою) ставимо знак "+". Далі чергуємо: "-", "+" і т.д.

У таблиці вартості знаходимо мінімальне значення зі знаком "-".

У нашому прикладі – це «5», комірка В1. Цю клітину треба прибрати з базису. А комірку з мінімальною оцінкою зробити базисною.

З урахуванням даних, що змінилися, знову будуємо опорний план транспортного завдання. Застосовуємо інструмент "Пошук рішення". Перерахований план перевезень виглядає так:

Зверніть увагу: осередок I1 (де була мінімальна оцінка) став базисним, зайнятим.

Проводимо ті ж самі розрахунки для нового плану (з пункту №1): знаходимо потенціали, оцінки вільних клітин для перевірки оптимальності. І так до тих пір, поки оцінки вільних клітин не будуть більшими або рівні 0.

---