Диссертация (Оптимизация стохастических линейных относительно стратегий систем по квантильному критерию), страница 12

Время счёта 1 и2 указано в секундах.Таблица 2.2. Результаты сравнения алгоритмов первой и второй главыАлгоритм 1Алгоритм 2K () 1 ()2 ()t1ˆu1u2t20,9102,3500,7990,81035,6833,020 0,691 0,738 11,5610,991003,5570,7280,73940,8074,058 0,698 0,724 11,6020,9910004,4530,7050,748122,4214,797 0,695 0,738 12,2350,99910006,1420,7500,751134,6516,412 0,702 0,716 11,0870,999100006,2730,7150,7011392,5396,280 0,704 0,718 11,9930,999 1000006,2850,7050,71223791,425 6,286 0,702 0,716 19,732Из таблицы 2.2 видно, что решение, полученное с помощью первого алгоритма (алгоритма, описанного в первой главе), оказывается лучше, чем решение, полученное путёмприменения алгоритма, описанного в данной главе (алгоритм 2). Следует отметить, чторешение, получаемое с помощью алгоритма, описанного в данной главе, является гарантирующим, то есть представляет собой некоторое допустимое решение, на котором достигаетсяверхняя оценка оптимального значения критерия.

При этом данное решение оказывается нелучше приближённого решения, получаемого путём применения алгоритма, описанного впервой главе.Время счёта первого алгоритма в несколько раз превышает время счёта второго алгоритма. Это связано с тем, что во втором алгоритме применяется процедура сокращенияперебора точек, образующих доверительное множество. Поскольку с ростом количества точек дискретизации алгоритм стабилизируется, то можно предполагать, что при больших он сходится к точному решению задачи.642.5.Выводы по главе 2В данной главе рассмотрена двухэтапная задача стохастического программированияс квантильным критерием и билинейной функцией потерь при нормальном распределениислучайных параметров. Предложен алгоритм получения гарантирующего решения исходнойстохастической задачи, основанный на доверительном методе и решении задачи выпуклогопрограммирования, которая параметризована скалярным параметром, выбираемым с помощью метода дихотомии.

Основная трудоёмкость предложенного алгоритма заключаетсяв процедуре подсчёта вероятностной меры многогранного множества. Однако за счёт дискретизации меры нормального распределения и введения процедуры сокращения перебораточек, которые образуют доверительное множество, удаётся сократить время счёта алгоритма.Основные результаты главы 21. Исследованы свойства верхней оценки функции квантили для билинейной двухэтапной системы.2. Разработан алгоритм поиска гарантирующего решения двухэтапной задачи квантильной оптимизации с билинейной функцией потерь при нормальном распределении случайных параметров задачи. Алгоритм основан на переходе от исходной билинейной задачик задаче выпуклого программирования, параметр которой может быть найден с помощьюметода дихотомии.653.Задача выбора оптимальной трассы с учётом случайнойстоимости работ на разных участкахВ данном разделе рассматривается задача выбора оптимальной трассы до аэропортас учётом случайной стоимости работ на разных участках.

Актуальность рассматриваемойзадачи обусловлена обострением проблемы эффективности логистики в современных условиях высокого трафика.Эффективное функционирование аэропортов возможно только в случае обеспеченияих транспортной доступности. Но дорожные трассы, ведущие к аэропортам, прокладывались более полувека назад, когда автомобильное движение не было столь насыщенным посравнению с текущей ситуацией. Решением данной проблемы может стать комплексная реконструкция трасс. Но, к сожалению, расширение уже имеющихся трасс, ведущих к аэропортам, не всегда возможно. Всему виной различные объекты, построенные вдоль дорог, например, дома, торговые центры. Кроме того, расширение имеющихся трасс может оказатьсяневозможным вследствие специфических особенностей местности.

Поэтому существующаяпроблема может быть решена путём прокладки новых трасс, причем крайне желательнообеспечить прокладку новых трасс с наименьшими затратами.Выбор траектории автомобильной трассы, соединяющей между собой два разныхпункта, представляет собой сложную математическую задачу, поскольку должен учитывать различную, имеющую стохастическую природу стоимость прокладки трассы на разных участках. Можно ввести разбиение карты района прокладки трассы на конечное числоучастков, тогда задача может быть описана на языке стохастического программирования.Поскольку строительство трассы в большинстве случаев ведется поэтапно, то задача выбора оптимальной трассы может быть записана в классе многоэтапных задач стохастическогопрограммирования.Стохастические модели, как правило, более адекватно описывают реальные процессыи явления, чем детерминированные модели, так как многие параметры в исследуемых задачах имеют стохастическую природу.

Поэтому оптимальные стратегии, полученные на основерешения задач стохастического программирования, являются практически более адекватными, чем стратегии, полученные в детерминированных постановках. Задачам стохастического программирования посвящены работы Ю.М. Ермольева [15], А.И.

Кибзуна и Ю.С. Кана [25, 117], Э. Райка [58, 59], Д.Б. Юдина [76], J. Birge и F. Louveaux [85], A. Charnes и66W.W. Cooper [95–97], P. Kall [109], P. Kall и S.W. Wallace [111], A. Prékopa [138] и многихдругих авторов.Критерием оптимальности трассы вряд ли может служить такой традиционный критерий, как усреднение затрат, поскольку этот критерий не учитывает возможные отклонениявеличины стоимости при реальной прокладке трассы. В данной ситуации более адекватнымрешением является получение гарантированных с заданной вероятностью затрат, то естьприменение квантильного критерия.

Задачи стохастического программирования, особеннопри оптимизации по вероятностному критерию или с вероятностными ограничениями, являются достаточно сложными. Это объясняется в основном сложностью нахождения аналитического вида вероятностного или квантильного критериев, а также, при отсутствии аналитического вида критерия, сложностью методов решения подобных задач, детально рассмотренных в монографии А.И. Кибзуна и Ю.С. Кана [25].

Согласно указанной работе однимиз наиболее эффективных путей аналитического решения задач стохастического программирования является построение детерминированных эквивалентов — детерминированныхзадач математического программирования, решения которых совпадают с решениями соответствующих задач стохастического программирования. Данные эквиваленты не зависят отслучайных величин, что позволяет свести исходную задачу стохастического программирования к эквивалентной ей детерминированной задаче, которую можно решать стандартнымиметодами математического программирования, рассмотренными в монографии Б.Т.

Поляка [57].Рассматриваемая в данной главе задача относится к задачам оптимального управления. В задачах этого типа требуется найти закон изменения некоторых управляющих воздействий для динамической системы так, чтобы минимизировать некоторый критерий оптимальности. Процесс минимизации можно проводить по шагам, причем пошаговое управление должно выбираться с учётом всех его последствий. Следует отметить, что двухэтапнаязадача стохастического программирования в априорной постановке по сути представляетсобой задачу управления стохастической системой. Многие многошаговые, и в частностидинамические задачи, имеют структуру, которая согласно работе Р.

Беллмана, И. Глицксберга и О. Гросса [2] позволяет получить решение на основе принципа индукции. В 1952 годуРичард Беллман первым обратил внимание на важность для программирования индуктивного метода, который он назвал принципом оптимальности, и раскрыл его потенциальныевозможности в своей работе [1]. Принцип оптимальности составляет суть метода динамического программирования. Изложению метода динамического программирования были по-67священы работы Р. Беллмана [1], Р. Беллмана, И. Гликцсберга, О.

Гросса [2], Р. Беллманаи С. Дрейфуса [3], Е.С. Вентцель [8] и других исследователей.Рассматриваемая в данной главе задача может быть решена с помощью алгоритмов поиска наикратчайших путей в графе, исследованных в работах таких авторов, какЕ.С. Вентцель [8], А.И. Житенёва [18], Н. Кристофидеса [46], E.W. Dijkstra [99].

В данной главе предлагается один из традиционных способов решения задачи целочисленногостохастического программирования на основе динамического программирования. C цельюсокращения количества рассматриваемых вариантов перебора предлагается использоватьдополнительно метод сценариев, исследованный в работе P. Kall [111], в сочетании с методом ветвей и границ, предложенным впервые в работах A.H. Land и A.G. Doig [121] иJ.D.C. Little, K.G. Murty и др. [123].В данной главе осуществляется разработка математической модели выбора оптимальной трассы, учитывающей случайную стоимость работ на разных участках пути, связаннуюс разнообразным рельефом местности.

Для полученной модели предлагается алгоритм, основанный на методе динамического программирования, схеме сценариев и методе ветвей играниц. Эффективность предложенного алгоритма демонстрируется на примере прикладнойзадачи.Для корректного учёта множества случайных факторов, влияющих на стоимость прокладки трассы, задача рассматривается в двух постановках — детерминированной и стохастической. Алгоритм, разработанный для задачи в детерминированной постановке, положенв основу алгоритма решения задачи в стохастической постановке.Исследуемая в данной главе задача также, как и задачи в первых двух главах, будетрассмотрена с квантильным критерием.