Введение. 
Нахождение оптимального пути

Структурное моделирование представляет собой особый аппарат, позволяющий осуществлять оптимальное планирование управляемых процессов. Под «управляемыми» разумеются процессы, на ход которых мы можем в той или иной степени влиять. Общеизвестно пристальное внимание, уделяемое современной наукой вопросам планирования во всех областях человеческой деятельности. И это внимание абсолютно обоснованно, ведь детальное моделирование отдельных систем впоследствии дает Вам возможность извлечь максимальную выгоду из управления данной системой. И эффективность такой модели будет прямо пропорциональна количеству рассмотренных факторов, взятых из всего того множества условий, определяющих состояние этой системы.

Одним из математических аппаратов структурного моделирования является динамическое программирование — недавно возникший и интенсивно развивающийся раздел математики, дающий методы для решения важных практических задач. Динамическое программирование — это дальновидное планирование, планирование с учетом перспективы.

Целью данной работы является разработка модели транспортной системы, представляющей топологическую схему дорожных участков, перекрёстков и развязок с заданными среднестатистическими временами задержек или простоев, для вычисления оптимального пути между назначенными пунктами. Необходимость достижения указанной цели обусловила постановку и решение следующих задач:

• — проведение анализа топологической схемы дорожных участков;
• — разбиение топологической схемы на простые участки или подзадачи;
• — сопоставление полученной схемы с конкретной структурной моделью;
• — вычисление оптимального пути методом динамического программирования на основе составленной модели;
• — составление итоговой схемы оптимального маршрута.

В качестве среды разработки была выбрана математическая среда программирования MathCAD.

Полное условие задачи данной работы предполагает анализ топологии дорог автомобильных грузоперевозок, изображенной на рисунке 1 и вычисление методом динамического программирования (динамического планирования) наименее затратного по времени пути из пункта S₀ в пункт S_кон.

Рисунок 1 Топология автомобильных дорог Время проезда отрезка пути указано на рисунке рядом с интересующим отрезком, а время, затрачиваемое при простое на перекрёстке или в очереди к переправе или переезду, указано в кружке рядом с интересующим перекрёстком, переездом или переправой.

Таблица 1.

Распределение времени (в минутах) проезда отрезков дорог, перекрёстков, переездов или переправ для заданной топологии.

Времена, затрачиваемые на каждом отрезке автомобильных дорог и при простое на перекрёстках или в очередях, обозначены как t_{i, j}, где i = 1, 2, …, 7 — номер шага или этапа планирования, j — номер обозначенного на топологии участка дороги для i-го шага. Числовые значения времён t_{i, j} (в минутах) были назначены преподавателем и занесены в вышеуказанную таблицу 1.