Математическое обоснование структурной модели транспортной системы. Алгоритм решения задачи моделирования транспортной системы. Программная реализация алгоритма вычисления оптимального пути. Анализ результатов решения поставленной транспортной задачи.
Аннотация к работе
Структурное моделирование представляет собой особый аппарат, позволяющий осуществлять оптимальное планирование управляемых процессов. И это внимание абсолютно обоснованно, ведь детальное моделирование отдельных систем впоследствии дает Вам возможность извлечь максимальную выгоду из управления данной системой. Одним из математических аппаратов структурного моделирования является динамическое программирование - недавно возникший и интенсивно развивающийся раздел математики, дающий методы для решения важных практических задач. Целью данной работы является разработка модели транспортной системы, представляющей топологическую схему дорожных участков, перекрестков и развязок с заданными среднестатистическими временами задержек или простоев, для вычисления оптимального пути между назначенными пунктами. Необходимость достижения указанной цели обусловила постановку и решение следующих задач: - проведение анализа топологической схемы дорожных участков;Действительно; если трудно оптимизировать управление сразу на протяжении всей операции, то разумно разбить ее на ряд последовательных шагов и оптимизировать отдельно каждый шаг. Напротив, управление на каждом шаге должно выбираться с учетом всех его последствий в будущем. Напротив, управление на каждом шаге выбирается исходя из интересов операции в целом. Планируя многоэтапную операцию, мы должны выбирать управление на каждом шаге, исходя не из узких интересов именно этого шага, а из более широких интересов операции в целом, и далеко не всегда эти две точки зрения совпадают. Уже было сформулировано общее правило: в процессе поэтапного планирования управление на каждом шаге должно приниматься с учетом будущего.В ходе реализации задач данной работы целесообразно руководствоваться следующим алгоритмом: 1) Проанализировав предоставленную топологию автомобильных дорог, разбить участок S0 - Sкон на оптимальное значение m шагов. 2) Исходя из принципа оптимальности, учесть, что путь из S0 в Sкон разбит на m шагов, в каждом из которых машина перемещается с одной из опорных прямых (i) - (i) на следующую по порядку. Найти условное оптимальное управление для каждой точки на (6)-ом шаге, т.е. такой путь на предыдущий шаг, который, совместно с уже оптимизированным последним шагом, дает возможность достигнуть следующей опорной точки за минимальное время. Деля процесс на шаги таким образом, мы, естественно, должны условиться, что перемещение от шага к шагу допускается только в положительном направлении (т. е. от S0 к Sкон, а не обратно); иными словами, после того как определенный шаг пройден, возвращение обратно, в ту же полосу между двумя опорными прямыми, не допускается. Такое ограничение представляется достаточно приемлемым для нашей задачи (в итоге каждого шага перемещаться только «туда», по направлению S0 - Sкон, а не «обратно»), так как оно действует только от шага к шагу, не внутри шага, и к тому же только по одной оси (в случае надобности от этого ограничения можно освободиться, но при этом решение сильно усложняется).Реализация алгоритма вычисления оптимального пути для операционных систем Windows XP / 7 / 8 / 10 была организована с помощью математического пакета MATHCAD. MATHCAD - система компьютерной алгебры из класса систем автоматизированного проектирования , ориентированная на подготовку интерактивных документов с вычислениями и визуальным сопровождением, отличается легкостью использования и применения для коллективной работы. Выбор этой системы во многом обусловлен интуитивным и простым для использования интерфейсом среды, а также широким применением MATHCAD в проектах, с целью визуализации результатов математического моделирования путем использования распределенных вычислений и традиционных языков программирования . Используя временную таблицу и схему дорог вычисляется время, затрачиваемое на прохождение каждого участка. При помощи функции min находятся минимальные значения для каждого последующего шага, путем складывания значения минимального пути, приводящего в данную точку с предыдущего шага и непосредственно времени, затрачиваемого на прохождение данного пути.Итогом реализации программы по нахождению оптимального пути из точки S0 в Sкон является приведенная ниже строка кода: Исходя из этого, начинаем разворачивать процесс в обратную сторону. На данном этапе получаем, что условное оптимальное управление для отрезка (0) - (1) будет путь Так как в точку A1 из S0 ведут два пути, с помощью функции min определяем кратчайший из них. Переходим к точке A1, единственный путь к которой лежит из точки В точку A2 также следует одна-единственная дорога - черезБыл исследован метод динамического программирования в контексте решения простейшей транспортной задачи по критерию времени с единственными начальным и конечным пунктами.Полный код программы, реализующей алгоритм нахождения оптимального пути между точками S0 и Sкон.
План
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1. МАТЕМАТИЧЕСКОЕ ОБОСНОВАНИЕ СТРУКТУРНОЙ МОДЕЛИ ТРАНСПОРТНОЙ СИСТЕМЫ
2. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ МОДЕЛИРОВАНИЯ ТРАНСПОРТНОЙ СИСТЕМЫ
3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ВЫЧИСЛЕНИЯ ОПТИМАЛЬНОГО ПУТИ
4. АНАЛИЗ РЕЗУЛЬТАТОВ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ
ЗАКЛЮЧЕНИЕ
ПРИЛОЖЕНИЕ А транспортный математический модель задача