О решении задачи оптимизации методом динамического программирования

About decision of optimization problem by the method of dynamic programming
Цитировать:
Аблялимов О.С. О решении задачи оптимизации методом динамического программирования // Universum: технические науки : электрон. научн. журн. 2020. № 9(78). URL: https://7universum.com/ru/tech/archive/item/10670 (дата обращения: 26.09.2021).
Прочитать статью:

 

АННОТАЦИЯ

Приводится теоретическое обоснование метода динамического программирования, основанного на критерии оптимальности Р. Беллмана и алгоритм реализации этого математического метода в решении задачи оптимизации, связанной с выбором оптимального режима ведения грузового поезда локомотивами дизельной тяги на виртуальном участке железной дороги.

ABSTRACT

The theoretical substantiation of the dynamic programming method based on the R. Bellman optimality criterion and the algorithm for the implementation of this mathematical method in solving the optimization problem associated with the choice of the optimal mode of driving a freight train by diesel - powered locomotives on a virtual section of the railway are given.

 

Ключевые слова: исследование, оптимизация, метод, динамическое программирование, принцип оптимальности, решение, выбор, режим, теория.

Keywords: investigation, optimization, method, dynamic programming, optimality principle, decision, choice, mode, theory.

 

Метод динамического программирования основан на двух гипотезах [3] - о наличии оптимального процесса при переходе объекта из начального состояния Оо в некоторое конечное О1 и наличии непрерывности всюду, кроме точки О1 и дифференцируемости функции B(О) в частных производных, то есть

Из рассмотрения процесса перехода из точки Оо фазового пространства в точку О1 с учётом промежуточного состояния О(Оа) можно получить

                                                                     (1)

А затем, переходя к пределу при Oа = Oао находим

                                                                             (2)

Производная левой части аналитического выражения (2) действительно существует, так как функции В(О) и О(Оа) дифференцируемы и вычисляются по формуле полной производной, а именно:

и неравенство (2) принимает такой вид

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

                                     (3)

Если взять оптимальный процесс O(Oа), Р(Oа) перевода объекта из Oо в O1 и Oio , учитывая вышеизложенное, получим следующие равенство

                            (1.9)

Вводя в рассмотрение функцию

                               (4)

Получим

                                                                          (5)

для всех точек О  1 и Р

                                                           (6)

для любого оптимального процесса О(Оа), Р(Оа).

Для Оа = Оао получим А(Оо, Р(Оао) = 1; в сопоставлении с неравенством (6) получим соотношение maxA(O,P) = 1 для любой точки О  1 или что тоже самое

                                               (7)

для любой точки  О  1.

Соотношение (7) называется уравнением Ричарда Беллмана. Метод динамического программирования (ДП) или что то же самое (7) содержит некоторую информацию об оптимальных процессах и поэтому может быть использован для их отыскания.

Однако применение этого метода требует нахождения не только оптимальных управлений Р(Оа), но и функций В О), так как эта функция входит в соотношение (7), а само уравнение Беллмана представляет собой уравнение в частных производных относительно функции В, осложнённой ещё знаком максимума. Главным же недостатком этого метода является предположение о возможности выполнения вышеуказанных гипотез, хотя оптимальные управления и функции В нам заранее неизвестны. Указанные выше гипотезы содержат предположение о неизвестной функции, а проверить выполнение этих гипотез по уравнениям движения объекта невозможно.

Кроме того, после решения оптимальной задачи методом динамического программирования не всегда оказывается, что функция В(О) действительно является непрерывно дифференцируемой, в связи с чем применение изложенного метода становится необоснованным. Однако, во многих случаях, методом динамического программирования можно пользоваться, как эвристическим средством с применением численных методов решения, что и было сделано в работах [4-7 и другие].

Ниже приводим методику и результат решения задачи по выбору оптимального режима вождения грузовых поездов тепловозами серии 3ТЭ10М на виртуальном участке железной дороги протяженностью 37,5 километров с учётом исходных данных, обозначенных в [1], а именно: масса состава грузового поезда Q = 3750 т, нагрузка на ось колёсной пары qo = 20,0 т/ось и время хода грузового поезда по участку tх = 38,5 мин.

Решение поставленной задачи осуществляем графическим методом [2], опираясь на принцип оптимальности [3], из которого вытекает, что независимо от способа, приводимого объект в данное начальное состояние, дальнейшее его поведение должно быть оптимальным относительно первоначального состояния и управления.

Тогда, условие оптимальности процесса по выбору режима ведения поезда для N - го шага варьирования упомянутого режима можно записать в виде

                                 (8)

где Е – эффективность процесса, то есть расход натурного дизельного топлива тепловозом на шаге варьирования режима ведения поезда, кг.

Для расчёта допустимую область фазовых координат (S,V) каждого перегона заданного участка пути разбиваем на узловую решётку, в которой допустимый диапазон скоростей движения представляем в виде скоростной сетки с шагом варьирования по скорости движения ΔV = 5…10км/ч.

Допустимый диапазон по координате путь S - в виде сетки, разделённой на шаги варьирования режимов ln, равные длине элемента профиля пути.

Расчёт начинаем с конца заданного участка пути на последнем N - м шаге варьирования режимов. Из каждой начальной точки узловой решетки N - го шага строим траектории с попаданием в конечную  точку узловой решётки этого же N - го шага с координатами (Sk,Vk), подсчитываем величину расхода топлива (критерий оптимальности) Е для всех траекторий N - го шага. Запоминаем величину критерия оптимальности Е и позиции контроллера машиниста, соответствующие этим траекториям. Затем из начальных точек узловой решетки N-1 - го шага строим траектории с попаданием в конечные точки узловой решётки этого шага, что будет идентично начальным точкам узловой решетки N-1 - го шага и, далее, подсчитываем величину расхода топлива Е для всех траекторий N-1 - го шага. Траектории, полученные на N-1 - м и N - м шаге, удовлетворяющие условию оптимальности (7), оставляем и соответственно, запоминаем критерий оптимальности (расход топлива) Е и позиции контроллера машиниста для вновь полученной условно - оптимальной траектории. Аналогичным образом выполняем расчёты на последующих шагах варьирования режимов и получаем столько условно – оптимальных траекторий, сколько точек в «базовой» узловой решётке фазовых координат (S,V). Затем, в качестве оптимальной траектории (режима ведения поезда) для всего перевозочного процесса в целом и на каждом шаге варьирования, принимаем ту, которая имеет минимальное значение критерия оптимальности Е и удовлетворяет условию выполнения времени хода поезда по перегонам (в противном случае, весь процесс расчёта повторяется вновь).

В процессе решения поставленной задачи и сказанного выше автором были получены следующие значения параметров оптимального режима ведения грузового поезда на участке счёта: касательная механическая работа локомотива Ак = 2576,5 кН км, затраты механической работы на торможения Ат = 466,3 кН км и общий расход натурного дизельного  топлива (критерий оптимальности) Е = 243,7 кг. При этом показатели, характеризующие оптимальный режим ведения грузового поезда, составили: η = 0,302 - к.п.д. силовой цепи; α = 1,08 - показатель совершенства траектории скорости движения; β = 0,181 - показатель затрат энергии на торможения.

В результате проведённого исследования автором изложено теоретическое толкование одного из математических методов оптимального управления – динамическое программирование и показан пример практической реализации этого метода при выборе оптимального режима вождения грузовых поездов тепловозами серии 3ТЭ10М на виртуальном участке железной дороги.

 

Список литературы:

  1. Аблялимов О.С., Кудряшов В.С., К исследованию режимов вождения грузовых поездов электровозами [Текст] / О. С. Аблялимов, В. С. Кудряшов // IX межвузовская научно - практическая конференция ТашИИТ / Ташкентский ин-т. инж. ж-д транспорта. – Ташкент, 2011. – С. 35 – 38.
  2. Аблялимов О. С. О методах исследования перевозочной работы локомотивов [Текст] / О. С. Аблялимов // Республиканская научно – техническая конференция с участием зарубежных учёных, посвящённая 80-летию ТашИИТ «Ресурсосберегающие технологии на железнодорожном транспорте» / Ташкентский ин-т. инж. ж-д транспорта. – Ташкент, 2011. – С. 79 – 85.
  3. Беллман Р. Динамическое программирование [Текст] / Р. Беллман. - М.: Иностранная литература, 1960, 400 с.
  4. Босов А. А. Методы решения некоторых задач оптимальных тяговых расчётов на ЭЦВМ. Автореферат диссертации на соискание учёной степени кандидата технических наук. ДИИТ, Днепропетровск, 1968.
  5. Ерофеев Е. В. Определение оптимального режима движения поезда при заданном времени хода [Текст] / Е. В. Ерофеев // «Вестник ВНИИЖТ» / Всесоюзный науч-иссл. ин-т. ж-д транспорта. – М.: Трансжелдориздат, 1969, № 1. – С. 54 – 57.
  6. Почаевец Э. С. Расчёт оптимальных программ автоматического ведения поезда. Автореферат на соискание учёной степени кандидата технических наук. МИИТ, М., 1967.
  7. Сидельников В. М. Выбор оптимальных режимов управления локомотивом с использованием ЭЦВМ [Текст] / В. М. Сидельников // Научный журнал «Вестник ВНИИЖТ» / Всесоюзный науч-иссл. ин-т. ж-д транспорта. – М.: Трансжелдориздат, 1965, № 2. – С. 52 – 58.
Информация об авторах

канд. техн. наук, старший научный сотрудник, и.о. профессора кафедры «Локомотивы и локомотивное хозяйство» Ташкентский институт инженеров железнодорожного транспорта, Узбекистан, Ташкент

doctor of philosophy, chief scientific worker, acting professor of the chair «Loсomotives and locomotive economy» Tashkent institute of railway transpоrt engineering, Uzbekistan, Tashkent

Журнал зарегистрирован Федеральной службой по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор), регистрационный номер ЭЛ №ФС77-54434 от 17.06.2013
Учредитель журнала - ООО «МЦНО»
Главный редактор - Ахметов Сайранбек Махсутович.
Top