Завдання вибору оптимального шляху у транспортній мережі - Економіко-математичне моделювання
2 Завдання вибору оптимального шляху у транспортній мережі
Завдання: У запропонованій транспортній мережі (див. малюнок 1) є кілька маршрутів проїзду з початкового пункту (1) до кінцевого пункту (11). Вартість проїзду між окремими пунктами транспортної мережі подана у таблиці 2.1. Необхідно визначити оптимальний маршрут проїзду з пункту 1 до пункту 11 із мінімальними транспортними витратами.
У цьому є обмеження – рухатися магістралями можна лише зліва направо. Це дає нам можливість розбити всю транспортну мережу на пояси та віднести кожен із десяти пунктів до одного з чотирьох поясів. Будемо говорити, що пункт належить k-му поясу, якщо з нього можна потрапити в кінцевий пункт за k кроків, тобто. заїздом у k-1 проміжний пункт. Таким чином, пункти 8, 9 та 10 належать до першого поясу; 6 та 7 – до другого; 2, 3, 4 та 5 – до третього; 1 – до четвертого. На k-му кроці знаходимо оптимальні маршрути з міст k-го поясу до кінцевого пункту.
Оптимізацію будемо проводити з хвоста процесу, і тому, діставшись k-го кроку, ми не можемо знати, в яке саме з міст k-го поясу ми потрапимо, рухаючись з пункту 1. Тому для кожного з цих міст ми повинні будемо знайти оптимальний маршрут до кінцевого пункту Очевидно, що мінімально можлива вартість проїзду до пункту 11 залежатиме лише від того, в якому з міст цього поясу ми опинилися. Номер S міста, що належить k-му поясу, і називатиметься змінною стану даної системи на k-му кроці. Потрібно пам'ятати, що, діставшись до k-го кроку, ми вже здійснили попередні кроки, зокрема знайшли оптимальні маршрути по переміщенню з будь-якого міста (k-1)-го пояса до кінцевогопункт. Таким чином, перебуваючи в деякому місті S k-го поясу, ми повинні прийняти рішення про те, в яке з міст (k-1)-го пояса слід вирушити, а напрямок подальшого руху вже відомий нам з попередніх кроків. Номер J міста (k-1)-го пояса буде змінною управління на k-му кроці.
Функція Беллмана на k-му кроці розв'язання задачі дає нам можливість розрахувати мінімальну вартість проїзду з міста S (k-го пояса) до кінцевого пункту. Для першого кроку (k=1) цю величину знайти легко – це вартість проїзду з міст 1-го пояса безпосередньо до кінцевого пункту: F1(i)=Ci11. Для наступних кроків вартість проїзду складається з двох доданків – вартості проїзду з міста S k-го поясу до міста J (k-1)-го поясу і мінімально можливої вартості проїзду з міста J до кінцевого пункту, тобто. Fk-1(J).
Таким чином, функціональне рівняння Беллмана на k-му кроці рішення матиме вигляд:
Мінімум вартості досягається на деякому значенні J*, яке є оптимальним напрямком руху з пункту S в бік кінцевого пункту.