Диссертация (786272), страница 18
Текст из файла (страница 18)
Васильева, Б.С. Марышева, В.В. Силкина и др. [6] наименьшей для перечисленных характеристик является стоимость прокладкивдоль шоссе путём его расширения. Самой дорогой считается прокладка трассы через реку. Это связано с тем, что необходимо учитывать большое количество факторов таких, какглубина и ширина реки, осуществление судоходности, тип дна реки и т.д.Начальные данные для фиксированных стоимостей прокладки трассы были взяты изгазеты «Информационные технологии в строительстве» [12], справочника стоимостных показателей [62] и строительных норм и правил (автомобильные дороги) [63,64]. В ходе анализаэтих данных были получены следующие оценки средних значений и дисперсий стоимости работ для различных типов местности: среднее значение стоимости прокладки участка трассы97протяженностью 0,5 км путём расширения существующего шоссе составляет 51 млн.
рублей, через поле — 92 млн. рублей, через лес — 150 млн. рублей, через поселок, озеро, шоссе,железную дорогу (за счет возведения эстакад) — 300 млн. рублей, через реку — 400 млн.рублей; дисперсии — 100, 125, 335, 450, 424 млн. рублей соответственно.Решение задачи c учётом средних значений стоимости работ.Экспертом эвристически были выбраны 3 трассы, из которых стоимость прокладки трассы 3 наименьшая, o = min{1 , 2 , 3 } = 7048, 8 млн.
рублей. Трассы, выбранныеэкспертом представлены на рисунке 3.3.Рис. 3.3 Трассы, выбранные экспертомПоскольку > , были заданы следующие значения параметров разбиения сетки:1 = 16, = 26. Решение, найденное с помощью алгоритма, представлено на рисунке 3.4.Рис. 3.4 Трасса, полученная в ходе применения алгоритмаСтоимость прокладки трассы, найденной с помощью предложенного в данной главе алгоритма, составила 6406,6 млн. рублей, что на 642,2 млн. рублей меньше стоимостипредложенной экспертом трассы.
При этом некоторые участки найденной трассы и трассы,предложенной экспертом, совпадают.На рисунке 3.5 представлены трасса наименьшей стоимости, предложенная экспертом(обозначена цифрой 1), и трасса, полученная с помощью предложенного алгоритма (обозначена цифрой 2).
Цифрой 3 обозначены совпадающие участки трасс.98Рис. 3.5 Полученная в ходе применения алгоритма и предложенная экспертом трассыВ ходе применения алгоритма удалось сократить количество вариантов переборовтрасс для первой и второй подзадач алгоритма в 25 раз по сравнению с общим количествомвозможных переборов.Решение задачи с учётом средних значений и дисперсий стоимости работ.В ходе решения задачи c учётом средних значений и дисперсий стоимости работ была найдена оптимальная трасса, стоимость прокладки которой с вероятностью = 0, 95не превысит 7638 млн.
рублей. Гарантированная с той же вероятностью стоимость трассы,найденной на основе решения задачи, учитывающего только средние затраты, составила8558 млн. рублей. Как видно из данного примера, учитывая при решении задачи возможный разброс значений стоимости работ на разных участках, можно достичь значительнойэкономии.На рисунке 3.6 представлены оптимальные трассы, найденные в ходе решения детерминированной (обозначена цифрой 1) и стохастической (обозначена цифрой 2) задач.Совпадающие участки трасс обозначены цифрой 3.Рис.
3.6 Трассы, полученные в ходе решения детерминированной и стохастической задачРассмотренный пример оптимизации прокладки трассы до аэропорта Быково показывает эффективность предложенного алгоритма.Следует отметить, что трасса, полученная при решении детерминированной задачи,может рассматриваться в качестве опорной траектории для процесса реальной прокладкитрассы между двумя точками и .
А трасса, полученная при решении задачи в стохастической постановке учитывает различные стохастические факторы, которые могут иметьместо в ходе реального строительства трассы.993.7.Выводы по главе 3В данной главе рассмотрена задача выбора оптимальной трассы в детерминированной и стохастической постановках. Предложена динамическая модель процесса прокладкитрассы, учитывающая случайную стоимость работ на разных участках.Для задачи в стохастической постановке удалось получить детерминированный эквивалент. Для решения рассмотренной задачи предложен алгоритм, основанный на методединамического программирования, схеме сценариев и методе ветвей и границ.
Спецификавыбора определенных направлений движения по сетке разбиения местности помогает существенно сократить число анализируемых вариантов допустимых решений и применить схемуотсечения точек для уменьшения размерности задачи при поиске оптимального решения.Проведена оценка количества переборов возможных вариантов решения при использованиипредложенного алгоритма. Однако данная оценка является оценкой сверху, так как не удаётся априорно определить количество анализируемых вариантов, поскольку оно существеннозависит от конкретной местности для предполагаемой прокладки трассы.Основные результаты главы 31. Разработана математическая модель выбора оптимальной трассы с учётом случайной стоимости работ на разных участках.2.
Для задачи в детерминированной постановке предложен алгоритм поиска решения,основанный на методе динамического программирования, схеме сценариев, а также методеветвей и границ.3. Для задачи управления линейной стохастической системой специального вида снормальным распределением и квантильным критерием получен детерминированный эквивалент.4. Разработан алгоритм решения задачи оптимизации в стохастической постановке,основанный на применении метода динамического программирования.100ЗаключениеВ диссертационной работе разработаны алгоритмы поиска решений для линейных постратегиям задач стохастического программирования с квантильным критерием.В первой главе исследованы многоэтапные задачи стохастического программирования с квантильным критерием, в которых функция потерь линейна относительно стратегий.Показано, что данные задачи при дискретном распределении специального вида, полученном при дискретизации непрерывного распределения, могут быть сведены к двухэтапнымзадачам квантильной оптимизации.
Разработан алгоритм поиска решения многоэтапной линейной относительно стратегий задачи стохастического програмирования с квантильнымкритерием и дискретизированном распределении случайных параметров, основанный на переходе к эквивалентной задаче смешанного целочисленного линейного программирования.Во второй главе исследованы свойства верхней оценки функции квантили для билинейной задачи стохастического программирования. Предложен алгоритм решения двухэтапной задачи с билинейной функцией потерь, основанный на переходе к задаче выпуклогопрограммирования, в которой функция потерь записывается в аналитическом виде.
Даннаязадач параметризована скалярным параметром, поиск которого можно осуществить при помощи метода дихотомии. Для сокращения объёма перебора при использовании метода статистического моделирования на этапе проверки вероятностного ограничения используетсяпонятие ядра вероятностной меры.В третьей главе рассматривается задача управления линейной стохастической системой специального вида. Данная задача рассмотрена в двух постановках. Многошаговая задача квантильной оптимизации сводится к детерминированной задаче оптимальногоуправления целочисленной системой, для решения которой применяется метод динамического программирования и метод ветвей и границ.Исследования, проведённые в диссертационной работе, могут быть продолжены в направлении изучения вопросов сходимости решений, получаемых в ходе сведения исходныхмногоэтапных задач квантильной оптимизации к задачам смешанного целочисленного и выпуклого программирования.Алгоритм сведения двухэтапной билинейной задачи разрабатывался для случая нормального распределения случайных параметров, поэтому дальнейшие исследования такжемогут быть направлены на распространение полученных результатов на случай произволь-101ных распределений с последующим изучением вопросов сходимости получаемых при этомрешений к точному решению исходной задачи.Указанные направления позволят существенно расширить область приложений линейных относительно стратегий систем, поэтому требуют дальнейшего изучения.102Перечень сокращений и условных обозначений, — равенство по определению;∅ — пустое множество;× — прямое произведение множеств;T — операция транспонирования вектора ;T — операция транспонирования матрицы ;6, > — покомпонентные неравенства;|||| — евклидова норма вектора x;mes — мера Лебега;IR — евклидово пространство;⃗0 — нулевой вектор соответствующей размерности в евклидовом пространстве; (⃗0, ) — нормальное распределение; — вектор случайных параметров рассматриваемой задачи стохастического программирования; — размерность случайного вектора; — реализация случайного вектора ; ∈ ⊂ IR – план первого этапа; – множество допустимых стратегий первого этапа;(·) ∈ , (·) = col(1 (·), ..., −1 (·)) – вектор-функция планов последующих − 1 этапов,выбираемая в классе измеримых функций со значениями в IR ; – множество допустимых стратегий последующих − 1 этапов;Φ (, (·), ) — функция потерь -этапной задачи стохастического программирования ваприорной постановке;Φ (, (·), ), = 1, − 1, − − −;0+ — конус рецессивных направлений множества ;{·} — вероятностная мера, порождённая распределением случайного вектора;() — плотность вероятности случайного вектора ; ∈ (0, 1) — уровень надёжности; — значения уровня целевой функции, непревышение которого требуется по условию задачи; () — функция квантили уровня ;103[] — -квантиль распределения случайной величины ; () — функция вероятности; — оптимальная стратегия задачи стохастического программирования с квантильным критерием; , = 1, , — точки, сгенерированные случайным образом согласно плотности случайноговектора; — количество реализаций дискретного случайного вектора; = 1/ — меры сгенерированных точек , = 1, ;˜ — случайный вектор, соответствующий мерам ; () — функция распределения случайного вектора ;˜ () — функция распределения случайного вектора ;ˆ () — выборочная функция распределения, соответствующая случайному вектору ; — доверительное множество;ℱ — семейство доверительных множеств; — множество допустимых значений переменных задачи, двойственной к задаче второгоэтапа; ∈ R — вектор двойственных переменных; — вершина многогранного множества , = 1, ; — булевы переменные, характеризующие принадлежность точек реализации случай˜ доверительному множеству ;ного вектора Φ(, ) — целевая функция задачи стохастического программирования; ∈ R1 – вектор оптимизационных переменных задачи второго этапа;Φ̄(, ) — задача второго этапа; — -ядро вероятностной меры; — доверительный шар;, — радиусы доверительного шара;Г(·) — гамма-функция; — многогранное множество;¯ — правильный многогранник, симметричный относительно нуля, имеющий граней,касающихся доверительного шара .104Список литературы1.Беллман Р.
Динамическое программирование. — М.: Иностранная литература, 1960. —400 с.2.Беллман Р., Глицксберг И., Гросс О. Некоторые вопросы математической теории процессов управления. — М.: Иностранная литература, 1962. — 336 с.3.Беллман Р., Дрейфус С. Прикладные задачи динамического программирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
