X Международная студенческая научная конференция Студенческий научный форум - 2018

Цель исследования: выбрать оптимальный маршрут движения железнодорожного состава.

Для достижения поставленной цели нам необходимо решить следующие задачи:

познакомиться с методом динамического программирования;

изучить принцип оптимальности Беллмана;

составить рекуррентные соотношения для задачи;

привлечь элементы программирования и сделать вывод по проведенной работе.

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

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

В соответствии с вычислительной схемой метода динамического программирования фактическое формирование искомого оптимального управления данным процессом состоит из двух процедур: условной оптимизации и безусловной оптимизации. Условная оптимизация осуществляется в результате попятного движения от последнего шага исследуемого явления к его первому шагу; в процессе этого движения находятся шаговые условно-оптимальные управления. Безусловная оптимизация осуществляется в процессе движения в прямом направлении от первого шага к последнему; при этом из найденных ранее шаговых условно-оптимальных управлений формируется безусловное оптимальное управление всем данным процессом.

Математический аппарат динамического программирования, основанный на пошаговой оптимизации, может быть использован при нахождении кратчайших расстояний, например, на географической карте, представленной в виде железнодорожной сети.

Рассмотрим задачу. Пусть имеется транспортная сеть, состоящая из нескольких узлов, соединённых железнодорожными путями. Необходимо определить кратчайший маршрут движения поезда от станции Кузино до станции Богданович, если известны расстояния (в км) между станциями (узлами). Рис.1.

Рис. 1. Фрагмент транспортной сети

Для составления рекуррентных соотношений Беллмана введем следующие обозначения:

k – номер этапа,

i – название станции, из которой отправляется ж. д. состав,

j – название станции, в которую прибывает ж. д. состав,

С_i,j – расстояние от станции i до станции j,

- минимальное расстояние на k-м этапе решения задачи от текущей станции до конечной станции.

Таким образом, рекуррентные соотношения для этапов решения нашей задачи будут иметь вид: .

Поиск оптимального решения включает в себя девять этапов.

Условная оптимизация. I этап

Рекуррентные соотношения для 1го этапа будут иметь вид:

На станцию БОГДАНОВИЧ попадают со станций Каменск-Уральский, Косулино и Егоршино (рис. 2).

Рис. 2. Цветовое выделение I этапа (красным)

.

II этап Рекуррентные соотношения имеют вид: .

На станцию Каменск-Уральский попадают со станции Арамиль (рис.3)

=

Рис. 3. Цветовое выделение II этапа (оранжевым)

Следовательно, минимальное расстояние на втором этапе от станции Арамиль до станции БОГДАНОВИЧ составляет 112 км.

III этап Рекуррентные соотношения имеют вид: , при этом, на станции Арамиль и Косулино попадают со станций Керамик и Путевка (рис. 4).

136

Рис. 4. Цветовое выделение III этапа (желтым)

IV этап Рекуррентные соотношения имеют вид: .

На станцию Керамик попадают со станций Шарташ и Решеты, на станцию Путевка попадают со станций Шарташ и Аппаратная, а на станцию Егоршино попадают со станции Аппаратная (рис.5). Для удобства путь от станции Решеты до станци Керамик посчитаем на 7ом этапе.

Рис. 5. Цветовое выделение IV этапа (зеленым)

=

V этап Рекуррентные соотношения имеют вид:

На станцию Аппаратная попадают со станций Восточная и Шарташ (рис.6)

Рис. 6. Цветовое выделение V этапа (голубое)

VI этап

Рис. 7. Цветовое выделение VI этапа (синий)

Рекуррентные соотношения для VI этапа будут иметь вид:

На станции Восточная и Шарташ попадают со станции Екатеринбург-Сортировочный (рис.7).

VII этап Рекуррентные соотношения имеют вид:

.

На станцию Екатеринбург-Сортировочный попадают со станций Решеты и Хрустальная, а на станцию Керамик – со станции Решеты (рис.8).

(для удобства путь от ст. Хрустальная до ст. Екатеринбург-Сортировочный вычислим на 8ом этапе).

Рис. 8. Цветовое выделение VII этапа (фиолетовый)

VIII этап Рекуррентные соотношения имеют вид:

.

На станции Екатеринбург-Сортировочный и Решеты попадают со станции Хрустальная (рис.9)

Рис. 9. Цветовое выделение VIII этапа (малиновый)

IX этап

Рекуррентные соотношения для заключительного этапа будут иметь вид:

.

На станцию Хрустальная попадают со станции Кузино (рис. 10).

Рис. 9. Цветовое выделение VIII этапа (св. зеленый)

=

Таким образом, минимальное расстояние от станции КУЗИНО до станции БОГДАНОВИЧ составляет 187 км.

Определим оптимальный маршрут, используя безусловную оптимизацию.

Поднимаемся снизу вверх.

Рассмотрим IX этап как сумму расстояния от Кузино до Хрустальной и минимального расстояния на VIII этапе от станции Хрустальная до станции Богданович: .

Аналогично поступим с остальными этапами:

,

,

Итак, + + + +

Следовательно, оптимальным является следующий маршрут: Кузино – Хрустальная – Екатеринбург-Сортировочный – Шарташ – Путёвка – Косулино – Богданович, а его длина составляет 187 км (рис. 10)

Рис. 10. Оптимальный маршрут

С помощью программирования (язык программирования – Паскаль) была составлена программа, которая составляет оптимальный маршрут и вычисляет кратчайшее расстояние.

Также мы ввели расстояние между каждыми двумя станциями.

Результат был таков: самый короткий путь между станцией Хрустальная и Косулино проходит через станции Екатеринбург- Сортировочный, Шарташ, Путевка. Далее была добавлена ветвь Кузино-Хрустальная и Косулино-Богданович. Кратчайшее расстояние между этими станциями и надо было найти по условию задачи. Оно составило 187 км, тем самым, подтвердив расчеты, полученные методом динамического программирования.

Таким образом, с привлечением программы PascalАВС была составлена экспериментальная модель, которая наглядно подтвердила расчёты, полученные аналитическим методом.

Литература:

Акулич И.Л. Математическое программирование в примерах и задачах. СПб: Изд-во «Лань», 2011. 352 с.

Завьялова Т. В. Методы принятия управленческих решений: учеб.пособие/ Т. В. Завьялова, И. Н. Пирогова, Е. Г. Филиппова, - Екатеринбург: Изд-во УрГУПС, 2014 г. – 89 с.

Хэмди А.Таха. Введение в исследование операций. М., СПб, Киев: Изд. дом «Вильямс», 2001. 912 с.

Эддоус М. Методы принятия решений/М. Эддоус, Р. Стэнфилд. М.:ЮНИТИ, 1997. 500 с.

13

Код для цитирования: Скопировать