Диссертация (786272), страница 14
Текст из файла (страница 14)
. . , 1, , ∈(3.11)74 +1 ( +1 ) = +1 ,(3.12)где зависимость +1 ( , , ) определяется системой (3.3).Соотношения (3.11) − − − (3.12) на каждом шаге представляют собой задачу математического программирования, при решении которой для каждого значения вектора состояния определяется управление ( , ), = 1, , принимающее значение из множества {0, 1}.При = задача оптимизации состоит в минимизации стоимости прокладки последнего участка трассы: ( ) =min , ∈ +1 ( +1 ( , , )),при = 1 задача имеет вид1 (1 ) = min 2 (2 (1 , 1 , 1 )).1 , 1 ∈ При этом, согласно работе А.И. Кибзуна [23] и в соответствии с методом динамического программирования выполняется +1 (* (·), * (·)) = 1 (1 ).Разрешая рекуррентные соотношения динамического программирования (3.11) −(3.12) от конца к началу, получаем на каждом шаге = 1, зависимость оптимальногоуправления * ( ), * ( ) на этом шаге от текущего состояния .
Подставляя эти зависимости в систему (3.3), найдем вектор оптимального состояния * для каждого шага = 1, .Подставляя найденные значения * в оптимальные управляющие функции, находим оптимальное программное управление* = * (* ), * = * (* ), = 1, .При этом выполняется +1 (* (·), * (·)) = +1 (* , * ) = 1 (1 ).Решение задачи (3.9) основано на применении метода динамического программирования.
Согласно работе Е.С. Вентцель [8] специфика этого метода состоит в разбиении исходной задачи на ряд последовательных «шагов» или «этапов». На практике, как правило,рассматриваются задачи с достаточно большим количеством этапов. В связи с этим возникает проблема, называемая в работе Р. Беллмана [1] «проклятием размерности». Данная75проблема влечёт за собой трудоёмкость вычислений и необходимость хранения большогоколичества данных. Для устранения «проклятия размерности» необходимо предложить алгоритм решения, основанный на методе динамического программирования, например, с использованием метода ветвей и границ, рассмотренного в работах A.H.
Land и A.G. Doig [121],J.D.C. Little, K.G. Murty и др. [123], а также метода сценариев, рассмотренного в работеP. Kall и S.W. Wallace [111].763.3.2.Алгоритм решения задачи в детерминированной постановке сприменением метода ветвей и границ и схемы сценариевМодифицируем решение задачи (3.11), основанное на методе динамического программирования, с использованием схемы сценариев, а также метода ветвей и границ.Согласно работе P. Kall и S.W. Wallace [111] схема сценариев заключается в определении некоторого набора предварительных решений задачи.
Из этого набора выбираетсярешение, наилучшим образом удовлетворяющее критерию оптимизации, которое в дальнейшем используется для сравнения с решениями, полученными в результате примененияалгоритма. В ходе сравнения часть найденных, заведомо неоптимальных решений исключается из рассмотрения, а оставшиеся — уточняются. В результате находится оптимальноерешение, которое либо лучше предварительно найденных решений, либо совпадает с однимиз них.Глядя на карту района прокладки трассы, можно заметить, что на местности существуют участки с одинаковым рельефом, следовательно, и с одинаковой стоимостью работпо прокладке трассы на этих участках. Предлагается воспользоваться помощью эксперта —человека, имеющего длительный опыт работы в области прокладки автомобильных трасс,с целью определения нескольких трасс для прокладки с наименьшими затратами. Пустьэкспертом были эвристически выбраны траекторий, которые обозначим 1 , 2 , .
. . , , состоимостью прокладки 1 , 2 , . . . , соответственно. Из предложенных траекторий выбираем траекторию с наименьшей стоимостью прокладки o = min{1 , 2 , . . . , }, обозначим этутраекторию через o .Будем осуществлять поиск оптимальной траектории для прокладки трассы с помощью метода ветвей и границ, рассмотренного в работах A.H.
Land и A.G. Doig [121],J.D.C. Little, K.G. Murty и др. [123].Основные принципы метода ветвей и границ для решения задачи минимизации (3.11)состоят согласно работе Б.Т. Поляка [57] в следующем.1. Ветвление. Для нахождения оптимальной трассы исходная задача (3.11) разбивается на несколько подзадач таким образом, что решение исходной задачи является решениемхотя бы одной из подзадач. Каждая из подзадач, в свою очередь, ветвится на более мелкиеподзадачи.
Процесс может повторяться до тех пор, пока получаемая подзадача не становитсятривиальной и её решение может быть легко получено.2. Построение нижних оценок для минимального значения критериальной функции.Для любой из подзадач может быть найдена нижняя оценка минимального значения стои-77мости работ по прокладке трассы между двумя точками сетки разбиения. Нижняя оценкаможет быть получена в результате решения релаксированной или ослабленной задачи, когдатрудоёмкости прокладки трассы по одному направлению движения заменяются минимальновозможным значением трудоёмкости прокладки в данном направлении.3. Отсеивание вариантов. Если для некоторой подзадачи нижняя оценка значениястоимости прокладки всей трассы превосходит либо равна стоимости o трассы, предложенной экспертом, то такую задачу можно дальше не ветвить, так как её решение будетзаведомо хуже либо не лучше решения, предложенного экспертом.4. Оптимальное решение.
Процесс вычислений прекращается, когда нет ни однойподзадачи, которая может продолжать ветвиться. В этом случае оптимальное решение соответствует текущему найденному минимальному значению стоимости либо совпадает с решением, предложенным экспертом.Введем два параметра которые позволят уменьшить размеры исходной задачи и сведут её к решению трёх подзадач. Предположим, что > . Выберем два параметра разбиения сетки — 1 и таким образом, чтобы выполнялись ограничения1 < /2, < /2.(3.13)Данные параметры позволят разделить сетку разбиения на три части, на каждой изкоторых будет прокладываться участок искомой оптимальной трассы, соединяющей точки1,1 и +1, +1 . Тем самым исходная задача может быть сведена к решению трёх подзадачменьшей размерности.Рассмотрим три подзадачи. Причем сначала будем рассматривать первую и третью,так как их решение определяет начальные условия для второй подзадачи.Первая подзадача.В первой подзадаче рассматривается часть исходной сетки разбиения, находящаясямежду и .
Применяя метод динамического программирования, находим оптимальныетрассы, соединяющие точки , , имеющие координаты ( , ), где = 0, , с конечной точкой +1, +1 , то есть считая , начальными точками первой подзадачи, определяем минимальную стоимость прокладки трассы ( , , +1, +1 ) от каждой начальнойточки до +1, +1 и оптимальное управление.Третья подзадача.Используя введённый параметр 1 , искусственно уменьшаем сетку разбиения до размеров 1 × . Применяя метод динамического программирования, находим оптимальные78трассы третьей подзадачи, считая начальной точкой 1,1 , а конечными — все точки 1 ,1 ,имеющие координаты (1 , 1 ), где 1 = 0, , то есть для каждой конечной точки определяемминимальную стоимость прокладки (1,1 , 1 ,1 ) трассы от 1,1 до этой точки и оптимальноеуправление.В ходе решения первой и третьей подзадач получаем два несоединённых оптимальных участка трассы.
Для того, чтобы оптимально выбрать трассу на всей сетке разбиения,необходимо соединить конечные точки третьей подзадачи с начальными точками первойподзадачи трассой с минимально возможной стоимостью.Вторая подзадача.Рассмотрим часть исходной сетки разбиения между 1 и . Будем считать конечными точками прокладки трассы второй подзадачи все точки , , являющиеся начальнымиточками для первой подзадачи. До каждой конечной точки можно проложить = + 1трасс, причем начальными точками этих трасс являются точки 1 ,1 , имеющие координаты (1 , 1 ), где 1 = 0, , = 0, .
Найдем стоимости (1 ,,1 , , ) прокладки всехвозможных трасс второй подзадачи до каждой точки , , = 0, .Любая траектория, соединяющая точки 1 ,1 и , , представляет собой последовательность проложенных участков трассы, каждый из которых определяется одним из трёхвозможных направлений движения по сетке разбиения. Трудоёмкость прокладки трассы покаждому из направлений определяется выражением (3.4). Будем решать релаксированнуюзадачу, в которой вместо стоимостей прокладки трассы на каждом участке будем учитыватьминимально возможную стоимость прокладки по каждому направлению в пределах сеткиразбиения между начальной и конечной точкой прокладываемой части трассы:(1 ,1 , , ) =(1 ,1 , , ) =(1 ,1 , , ) =min ,(3.14)=1 , ,=1 ,min ,(3.15)=1 , ,=1 ,min ,(3.16)=1 , ,=1 ,где величины , , определяются выражением (3.4).Используя (3.14) — (3.16), можно оценить снизу величину (1 ,1 , , ) — стоимостьпрокладки трассы между точками 1 ,1 и , второй подзадачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
