Диссертация (786272), страница 13
Текст из файла (страница 13)
Кроме того, рассматриваемая в данной главе задачаотносится к динамическим задача, на связь которых с линейными относительно стратегийсистемами было показано во введении.В разделе 3.1 приведена общая постановка задачи, а также краткое описание предположений, на основании которых будет осуществляться дальнейшее решение.В разделе 3.2 рассматривается задача оптимизации прокладки трассы в детерминированной постановке. Задача предполагает поиск программного управления. Показанаэквивалентность задач в классе программных и позиционных стратегий.Алгоритм решения стохастической задачи с критерием в форме математического ожидания, основанный на методе динамического программирования, а также модифицированный алгоритм решения с применением метода ветвей и границ и схемы сценариев рассмат-68риваются в разделе 3.3.В разделе 3.4 рассматривается задача оптимизации в стохастической постановке.
Вкачестве критерия оптимальности выбирается квантильный критерий. Для задачи в стохастической постановке получен детерминированный эквивалент, а сама задача решена впрограммных стратегиях.В разделе 3.5 предлагается алгоритм решения задачи оптимизации в стохастическойпостановке, основанный алгоритме, предложенном в разделе 3.3.В разделе 3.6 приведены результаты численных расчётов на примере прикладнойзадачи прокладки автомобильной трассы от пересечения МКАД и Каширского шоссе доаэропорта Быково. Вычислительная эффективность предлагаемых в главе алгоритмов показана на основе решения задачи с учётом средних значений и дисперсий стоимости работпо прокладке трассы.693.1.Динамическая модель прокладки трассыПредположим, что требуется проложить некоторую трассу из пункта в пункт .Стоимость прокладки трассы различна на каждом участке пути в связи с неоднородностьюгрунта, особенностями рельефа, естественными препятствиями и т.д.
Необходимо проложитьтрассу из пункта в пункт таким образом, чтобы суммарные затраты на её прокладкубыли минимальны.Решение поставленной задачи будем осуществлять следующим образом. Рассмотримучасток местности для предполагаемой прокладки трассы. Наложим на карту рельефа местности сетку разбиения на мелкие прямоугольники. Расположим сетку так, чтобы левыйнижний угол сетки совпал с точкой начала строительства трассы, а правый верхний — сконечной точкой трассы.Допустим, что весь процесс прокладки трассы разделён на ряд последовательныхшагов (этапов) и за каждый шаг мы можем проложить часть трассы по сторонам прямоугольника разбиения вправо и вверх, а также по диагонали по направлению к конечнойточке . Движения по сетке влево, вниз и по диагонали в направлении от конечной точкиисключены из рассмотрения для избежания зацикливания алгоритма прокладки трассы идля существенного уменьшения перебора возможных вариантов трасс.Каждому участку трассы соответствует своя стоимость прокладки.
Любая трасса,связывающая начальную и конечную точки, будет представлять собой некоторую ломануюлинию. Существует множество таких трасс, каждая из которых связана с определеннойстоимостью работ и характеризует управление процессом прокладки трассы в трёх направлениях. Из всех возможных трасс необходимо выбрать оптимальную, стоимость работ попрокладке которой будет минимальной. Можно было бы, разумеется, перебрать все возможные трассы и, в конечном счете, найти оптимальную, но это очень трудоёмкий в вычислительном плане процесс. Гораздо быстрее можно решить задачу с использованием методадинамического программирования, рассмотренного в работе Р.
Беллмана [1].Разделим длину каждой из сторон сетки разбиения на равных частей по горизонтали и на равных частей по вертикали. Число частей и , на которые делятся сторонысетки, может быть выбрано исходя из требований к точности и к трудоёмкости решениязадачи. Размер ячеек сетки выбирается переменным или постоянным в зависимости от рельефа района прокладки. Угол наклона сетки по отношению к карте местности выбираетсяпеременным. Этот угол в дальнейшем оптимизируется.703.2.Задача оптимизации в детерминированной постановкеПредположим, что стоимость работ на всех участках известна и является неслучайнойвеличиной.
Пусть общее число шагов многоэтапного процесса прокладки трассы равно ,причем очевидно, что max{, } ≤ ≤ + . Заметим, что в пределах каждого прямоугольника из нижнего левого угла в правый верхний можно перейти и за 2 шага «вверх —вправо» и «вправо — вверх»), и за 1 шаг — по диагонали.Каждый прямоугольник разбиения имеет 4 вершины. Назовем каждую из этих верΔшин узловой точкой , = col(, ), = 0, , = 0, . Текущий участок прокладки трассыΔбудем характеризовать узловой точкой , = col( , ) прямоугольника с номером линийразбиения сетки по вертикали и горизонтали ( , ), = 0, , = 0, , = 1, + 1.ΔПричем точка 1,1 = col(1 , 1 ), где 1 = 0, 1 = 0, соответствует начальной точке трассыΔ(пункт ), а +1, +1 = col( +1 , +1 ), где +1 = , +1 = , — конечной точке трассы(пункт ).
Начальная и конечная точки и трассы известны.Пусть трудоёмкость прокладки трассы описывается трёхмерной матрицей: = || ||,(3.1) = col( , , ),(3.2)гдеΔ = 1, , = 1, — число частей, на которые делятся стороны сетки разбиения по горизонтали и по вертикали соответственно; — стоимость прокладки трассы по горизонтали от точки (, ) до точки ( + 1, ); — стоимость прокладки трассы по вертикали от точки (, ) до точки (, + 1); — стоимость прокладки трассы по диагонали от точки (, ) до точки ( + 1, + 1).Если = , то = = 0, а если = , то = = 0.ΔТекущее значение стоимости работ по прокладке трассы до точки , = col( , )обозначим через , причем > 0.Рассмотрим динамическую систему, описывающую изменение текущего положенияточки на сетке разбиения и текущее значение стоимости работ:⎧⎪⎪+1 = + , 1 = 0,⎪⎪⎨+1 = + 1 − + , 1 = 0,⎪⎪⎪⎪⎩ +1 = + ( , , , ), 1 = 0,(3.3)71где = 0, , = 0, — координаты узловой точки на −м шаге по горизонтали и повертикали соответственно; — номер шага, = 1, ; — общее число шагов, max{, } ≤ ≤ + ;Δ1,1 = col(1 , 1 ), где 1 = 0, 1 = 0, — начальная точка;Δ +1, +1 = col( +1 , +1 ), где +1 = , +1 = , — конечная точка;Δ , — управление, которое выбирается из множества = {0, 1} допустимых управлений, , ∈ ; — стоимость прокладки трассы до −го участка включительно;( , , , ) — добавка к текущему значению стоимости работ.Система (3.3) описывает движение по трём направлениям сетки разбиения: по горизонтали (при = 1, = 0), по вертикали (при = 0) и по диагонали ( = 1, = 1).Применение в системе (3.3) особой комбинации управлений , позволяет не вводить третью управляющую переменную и описывать движение по трём направлениям сетки разбиения посредством всего двух управляющих переменных , ∈ {0, 1}.
Выбранная модельдвижения и управления позволяет двигаться только вверх, вправо и вверх по диагонали,исключая движение вниз, влево и вниз по диагонали. Такая схема движения позволяет исключить зацикливание алгоритма и значительно сократить количество рассматриваемыхвариантов движения.В зависимости от выбранного управления, определяющего движения по сетке разбиения по горизонтали, вертикали или по диагонали, добавка к текущей стоимости трассыбудет определяться величиной:⎧⎪⎪⎪ , если = 1, = 0,⎪⎪⎨( , , , ) = , если = 0,⎪⎪⎪⎪⎪⎩ , если = 1, = 1.(3.4)Таким образом, текущее положение системы полностью описывается вектором текущегосостояния системы:Δ = col( , , ), = 1, + 1.Суммарная стоимость работ по прокладке трассы от начальной точки 1,1 до конечной точки +1, +1 равна +1 .72Задача оптимизации состоит в минимизации суммарных затрат на прокладку трассы: +1 (1 , .
. . , , 1 , . . . , ) → min . , ∈ =1, (3.5)Задача (3.5) предполагает поиск программного управления, то есть управления, прикотором последовательность управляющих воздействий выбирается из множества {0, 1} доначала процесса движения системы (3.3).Оптимальное программное управление (* , * ) должно удовлетворять следующемуусловию:(* , * ) = arg min +1 (, ),,∈ (3.6)где управлениеΔΔ = col(1 , . . . , ), = col(1 , . . . , )(3.7)выбирается из множества допустимых программных управленийΔ = ⏟ × . .⏞. × .(3.8)В разделе 3.4 планируется осуществить переход к стохастической постановке задачивыбора оптимальной трассы.
Поэтому рассмотрим задачу оптимизации (3.5) в классе позиционных стратегий, то есть таких стратегий, что управление выбирается в зависимости отреализовавшихся значений вектора состояния системы:(* (·), * (·)) = argmin(·), (·)∈ +1 ((·), (·)),(3.9)гдеΔ(·) = col(1 (·), . . . , (·)),Δ = {(·) : ( ) ∈ ∀ , = 1, }.Данную задачу предлагается решать с помощью метода динамического программирования. Алгоритм решения рассмотрен в следующем разделе.733.3.3.3.1.Алгоритм решения задачи оптимизации в детерминированнойпостановке с критерием в форме математического ожиданияПрименение метода динамического программирования длярешения задачи оптимизации в детерминированной постановкеВ работе В.В.
Малышева [48] показано, что в силу детерминированности системы (3.3)оптимальное значение критерия (3.9) в классе позиционных стратегий совпадает с оптимальным значением критерия (3.6) в классе программных стратегий: +1 (* (·), * (·)) = +1 (* , * ).Применим для решения задачи (3.9) метод динамического программирования.
С этойцелью проверим условия применимости для данного случая метода динамического программирования, приведенные в работе Д. Бертсекаса и С. Шрива [4]:1) cистема (3.3) является марковской, так как она рекуррентна и ее поведение в будущемполностью определяется текущим состоянием;2) критерий оптимизации (3.6) является аддитивным, его можно представить в виде суммы: +1 =∑︁( , , , ),(3.10)=1а следовательно, критерий (3.6) является монотонным;3) целевая функция +1 ограничена снизу +1 > 0, так как стоимость работ на каждомучастке трассы не может быть отрицательной или равняться нулю.Поскольку перечисленные условия выполнены, то, согласно монографии Д. Бертсекаса иC. Шрива [4], для решения задачи (3.9) можно воспользоваться методом динамическогопрограммирования.Введем функцию будущих потерьΔ ( ) =min{ (·)}= , { (·)}= ∈ +1 ,гдеΔ = {{ (·)}= : ( ) ∈ ∀ , = , }.В соответствии с методом динамического программирования получаем следующиерекуррентные соотношения ( ) = min +1 (+1 ( , , )), = , − 1, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
