Диссертация (786272), страница 16
Текст из файла (страница 16)
Среди полученных значений требуется определить минимальное.Данная последовательность действий повторяется для точек 1 ,1 , , , где вместо 1рассматривается 1 + 1, удовлетворяющее соотношению 1 ≤ . Новые полученные значения стоимостей трасс сравниваются со значениями, полученными в п. 2), если стоимостьнайденной трассы оказывается больше, то точка , исключается из рассмотрения.4) Присваиваем := +1 и повторяем п.п. 1)-3) до тех пор, пока выполняетсяусловие ≤ .5) Присваиваем := − 1 и повторяем п. 3 до тех пор, пока > 1 .4. В ходе выполнения алгоритма на шаге = 1 +1 останется малое количество точек , , а, следовательно, и возможных трасс для прокладки.
Найдем трассу с наименьшейстоимостью. Сравним ее со стоимостью трассы, предложенной экспертом:1) если стоимость найденной трассы совпадает со стоимостью трассы, предложеннойэкспертом, то в качестве оптимальной выбирается любая из них;2) если стоимость найденной трассы меньше стоимости прокладки трассы, предложенной экспертом, то найденная траектория является оптимальной.Предложенное решение задачи существенно зависит от размеров ячеек и угла наклона сетки.
На практике размер ячеек можно выбирать переменным в зависимости от рельефаместности, а также по совету эксперта. Угол наклона сетки можно выбрать оптимальным,чтобы минимизировать стоимость трассы, причем угол может меняться на 90 градусов.Предложенная схема движения (вправо, вверх и по диагонали по направлению к конечнойточке) имеет определенный недостаток, так как не позволяет огибать препятствия.
Этотнедостаток можно несколько исправить путём изменения угла наклона сетки. Поэтому предложенный алгоритм является эвристическим, не позволяющим в общем случае найти оптимальное решение. Например, в горной местности дороги прокладываются часто в формесерпантина. Применить предложенный алгоритм, чтобы минимизировать стоимость работ,в такой ситуации нельзя, так как в нем запрещено движение по спирали. Область применения данного алгоритма — относительно ровная местность с большим числом разнородныхнебольших препятствий, не требующих их огибания. Отметим, что предложенный алго-85ритм позволяет значительно сократить количество анализируемых вариантов. Например,если сетка имеет размеры 42 × 7, как в рассматриваемом в разделе 3.6 примере, то толькопри движении по горизонтали и вертикали, без учёта движения по диагонали, при полномпереборе необходимо проанализировать более 742 ≈ 5 × 1035 вариантов.
Если учесть еще движение по диагонали, то количество возможных вариантов станет просто астрономическим,что исключает возможность нахождения оптимального решения. Предложенный алгоритмприводит к необходимости анализа лишь 6, 4 × 109 вариантов, количество которых сокращается за счет использования метода динамического программирования совместно с методомветвей и границ, что позволяет получить решение прикладной задачи, рассматриваемой вразделе 3.6.863.3.3.Программная реализация алгоритмаДля программной реализации алгоритма был разработан макетный вариант программы под операционнную систему семейства Windows. Программа написана на языке C++,объём кода составляет 400 строк.Входными данными для программы являются:— размеры сетки разбиения и ;— матрица трудоёмкостей;— параметры и 1 сетки разбиения;— наименьшее значение стоимости трассы, среди всех предложенных экспертом.Выходными данными являются:— значения стоимостей для первой и третьей подзадач алгоритма;— минимально возможные стоимости трассы для каждой из конечных точек второйподзадачи;— преобразованные матрицы трудоёмкостей для каждой из конечных точек второйподзадачи.
Каждый элемент матрицы соответствует точке, через которую проходит либоне проходит проектируемая трасса. Элемент состоит из нулевых компонент в случае, еслитрасса не проходит через данную точку, иначе — среди компонент данного элемента будетприсутствовать единица, стоящая на месте компоненты, которая соответствует дальнейшемунаправлению движения по сетке разбиения от данной точки.873.4.Задача оптимизации в стохастической постановкеВ системе (3.3), рассмотренной в разделе 3.2, предполагалось, что все параметры,оказывающие воздействие на суммарные затраты по прокладке трассы, — детерминированные. В реальности же затраты на строительство трассы существенно зависят от природныхфакторов.
Опыт, данные исследования местности и основанные на них расчёты позволяютполучить лишь некоторые статистические характеристики параметров, определяющих влияние природных факторов на исходные данные для планирования трассы. Поэтому затраты,связанные с прокладкой различных участков трассы, оказываются случайными.Таким образом, параметры , , , = 1, из (3.4), определяющие добавкик текущей стоимости в зависимости от управления, — случайные величины, зависящие отнепредсказуемых локальных особенностей местности.
Поскольку добавки случайны, то случайна трудоёмкость (3.1), (3.2) прокладки трассы на каждом участке и управление ( , ).Управление определяет текущее положение системы (3.3) на сетке разбиения, поскольку онослучайно, то координаты , тоже случайны. Возникает задача управления стохастической системой. Поскольку добавки случайны, то в силу (3.10) случайна и стоимость +1 .Поэтому необходимо рассмотреть стохастическую постановку задачи.Рассмотрим задачу управления стохастической системой (3.3), в которой , , —случайны. Предположим, что данные параметры независимы и имеют нормальное распре)). Это предположение оправ), ∼ ( , ), ∼ ( , деление ∼ ( , дано, так как затраты определяются множеством мелких случайных факторов, влияющихна стоимость прокладки каждого участка трассы, например, расходы на наземные работы,сложность трассы, климатические условия и т.д.Поскольку стоимость прокладки трассы случайна, рассмотрим в качестве критерияоптимальности квантильный критерий:ΔΔ[ +1 ] = (, ) = min{ : (, ) ≥ }, ∈ (0, 1),где управление (, ) является программным и определяется выражением (3.7).Здесь функция вероятностиΔ (, ) = { +1 ≤ }характеризует вероятность такого события, что затраты не превысят допустимый порог > 0.88Под решением задачи будем понимать такое программное управление ( , ), котороеминимизирует гарантированные с заданной вероятностью потери:( , ) = arg min (, ),, ∈ (3.33)где , определены в (3.7), а в (3.8).Метод динамического программирования для решения задачи (3.33) формально применить нельзя, так как согласно работе В.В.
Малышева и А.И. Кибзуна [49] условия марковости для квантильного критерия не выполняются. Преобразуем полученную стохастическую задачу в детерминированную. С этой целью получим детерминированный эквивалентзадачи (3.33).Поскольку управление, определяемое выражением (3.33), программное, то на каждом шаге = 1, добавка к текущей стоимости трассы определяется, согласно (3.4), однойиз нормально распределенных независимых случайных величин , , , , , . Тогда суммарные затраты +1 , являющиеся согласно (3.3) суммой нормально распределенных независимых случайных величин, также имеют нормальное распределение с математическиможиданиемΔ +1 = M[ +1 ](3.34)и дисперсиейΔΣ +1 = D[ +1 ].(3.35)Согласно (3.3) получаем[︃M[ +1 ] = M∑︁]︃∑︁( , , , ) =[︃D[ +1 ] = D∑︁M[( , , , )],(3.36)D[( , , , )].(3.37)=1=1]︃( , , , ) =∑︁=1=1Тогда квантильный критерий может быть представлен в виде:[ +1 ] = +1 + √︀Σ +1 ,[ +1 ] → min ,, ∈(3.38)где — квантиль уровня .Таким образом, получен детерминированный эквивалент задачи (3.33).Заметим, что если бы управление (·), (·) выбиралось в классе позиционных стратегий, зависящих от текущего значения вектора состояния системы, то нельзя было бы89гарантировать нормальность случайной величины +1 из-за нелинейной зависимости ( ), ( ), несмотря на нормальность случайных величин , , .
Тем не менее, длярешения задачи (3.38) может быть применен метод динамического программирования. Сэтой целью искусственно погружаем задачу (3.38) в класс позиционных стратегий, учитывая, что полученное решение должно быть не хуже решения в программных стратегиях.Это обусловливается тем, что класс программных стратегий уже, чем класс позиционныхстратегий, так как формально включен в него. Основываясь на системе (3.3), запишем рекуррентную систему, позволяющую вычислить +1 и Σ +1 :⎧⎪+1 = + , 1 = 0,⎪⎪⎪⎪⎪⎪⎨+1 = + 1 − + , 1 = 0,(3.39)⎪⎪+1 = + ( , , , ), 1 = 0,⎪⎪⎪⎪⎪⎩Σ+1 = Σ + ∆( , , , ), Σ1 = 0,где = 1, , +1 — средние затраты до -го шага включительно, Σ+1 — дисперсия затратдо -го шага включительно,⎧⎪⎪⎪ ,⎪⎪⎨( , , , ) = , ⎪⎪⎪⎪⎪ ⎩ ,⎧⎪⎪⎪ ,⎪⎪⎨∆( , , , ) = , ⎪⎪⎪⎪⎪⎩ , если = 1, = 0,если = 0,(3.40)если = 1, = 1,если = 1, = 0,если = 0,(3.41)если = 1, = 1.Введем расширенный вектор состояния системы:Δ = col( , , , Σ ).Критерий (3.38) полностью определяется системой (3.39), которая не является стохастической.
Поэтому вместо задачи (3.33) получаем задачу√︀ +1 + Σ +1 → min ,(3.42)(·),(·)∈ гдеΔΔ(·) = col(1 (·), . . . , (·)), (·) = col( 1 (·), . . . , (·)),Δ = {(·) : ( ) ∈ ∀ , = 1, }.Применим метод динамического программирования для решения задачи (3.42). Описание алгоритма решения приведено в следующем разделе.903.5.3.5.1.Алгоритм решения стохастической задачи с квантильным критериемПрименение метода динамического программированиярешения задачи оптимизации в стохастической постановкедляПроверим условия применимости метода динамического программирования, изложенные в работе Д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
