Про оптимальні розв’язки транспортної задачі.

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

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

Метод, що пропонується в цій нотатці, має переваги обох згаданих методів і водночас позбавлений їхніх недоліків. Відзначимо, що всі нижче викладені міркування вже втілені авторами у конкретні алгоритми і програми, які працюють і дають необхідні результати.

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

По-друге, потрібна швидкість роботи такої рекурсивної процедури досягається за рахунок того, що на кожному кроці рекурсії є можливість оцінити вартість зафіксованих перевезень, і якщо вона перевищує найменшу з вже відомих, то відповідний напрямок можна не продовжувати, а процедура на відповідному кроці повертає деяке велике (обумовлене заздалегідь) значення. Так, якщо звичайний перебір для контрольного прикладу (закрита транспортна задача розмірності 5х5) потребує кілька днів, то нова рекурсивна функція працює менше секунди, видаючи при цьому всі (!) оптимальні плани перевезень.

Автори вважають, що запропонований метод буде досить корисним на практиці.

Шарапов М.М.,

Ольховик О.Є.