МЕТОДИ РОЗВ’ЯЗКУ БАГАТОІНДЕКСНИХ ТРАНСПОРТНИХ ЗАДАЧ ВИСОКОЇ РОЗМІРНОСТІ

Анотація

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