автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Оптимизация стохастических линейных относительно стратегий систем по квантильному критерию

На правах рукописи

Хромова Ольга Михайловна

ОПТИМИЗАЦИЯ СТОХАСТИЧЕСКИХ ЛИНЕЙНЫХ ОТНОСИТЕЛЬНО СТРАТЕГИЙ СИСТЕМ ПО КВАНТИЛЬНОМУ КРИТЕРИЮ

Специальность 05.13.01 — системный анализ, управление и обработка информации (авиационная и ракетно-космическая техника)

Автореферат

диссертации на соискание учёной степени кандидата физико-математических наук

00554 ми«

г; ; / П ? " 1 <

Москва — 2014 год

005547706

Работа выполнена на кафедре теории вероятностей

Московского авиационного института (национального исследовательского университета)

Научный руководитель: доктор физико-математических наук,

профессор Кибзун Андрей Иванович

Официальные оппоненты: Валишин Анатолий Анатольевич,

доктор физико-математических наук, профессор кафедры «Высшая и прикладная математика» Московского государственного университета тонких химических технологий им. М.В. Ломоносова;

Вишняков Борис Ваисович,

кандидат физико-математических наук, начальник лаборатории «Анализ динамических сцен» Федерального Государственного Унитарного Предприятия «Государственный Научно-Исследовательский Институт Авиационных систем»

Ведущая организация: ФГБУН Институт проблем управления

им. В.А. Трапезникова РАН

Защита состоится 16 мая 2014 года в 10 часов на заседании диссертационного совета Д 212.125.04 Московского авиационного института по адресу: 125993, Москва, А-80, ГСП-3, Волоколамское шоссе, 4

С диссертацией можно ознакомиться в библиотеке Московского авиационного института по адресу: 125993, Москва, А-80, ГСП-3, Волоколамское шоссе, 4, Учёный совет МАИ

Автореферат разослан ^ ^_

Отзывы просим отправлять в 2-х экземплярах, заверенных печатью, по адресу: 125993, Москва, А-80, ГСП-3, Волоколамское шоссе, 4, Учёный совет МАИ

Учёный секретарь

диссертационного совета Д 212.125.04

кандидат физико-математических наук ¿—ьъ' д (j Северина

Общая характеристика работы

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

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

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

Многоэтапные задачи рассматривались в работах таких авторов, как D. Barro п Е. Canestrelli, J. Dupacová, G. Consigli н S.W. Wallace, К. Frauendorfer, F.V. Louveaux, P. Olsen, R.T. Rockafellar и R.J.-B. Wets, S.W. Wallace и Т. Yan. В практических приложениях, например в финансовом планировании, экономике, применяются, как правило, линейные постановки многоэтапных задач стохастического программирования. Многоэтапные задачи стохастического

линейного программирования с критерием в форме математического ожидания рассматривались в работах J.R. Birge, С. Beltran-Royo, L.F. Escudero и др., M.S. Casey и S. Sen, Р. Fúsek, P. Kall, J. Mayer и др., С. Swamy и D.B. Shmoys.

В авиационной и ракетно-космической технике наиболее адекватными являются постановки задач стохастического программирования с вероятностными критериями качества для обеспечения гарантированного по вероятности результата. Вероятностный критерий представляет собой вероятность непревышення допустимого уровня потерь, связанных с реализацией оптимизируемой стратегии. Квантильный критерий представляет собой уровень потерь при реализации стратегии, непревышение которого гарантируется с заданной вероятностью. Квантильный критерий впервые был введён в рассмотрение в работе S. Kataoka. Дальнейшее изучение задач с квантпльным критерием связано с именами Р. Леппа, Э. Райка, Э. Тамма, Э. Юби.

Несмотря на наличие большого количества работ в области многоэтапных стохастических задач, класс многоэтапных задач стохастического программирования с квантпльным критерием ранее не рассматривался.

Многоэтапные задачи стохастического программирования являются естественным обобщением двухэтапных задач. Двухэтапные и многоэтапные задачи стохастического программирования рассмотрены в работах Е. Schweitzer и M. Avriel, A. Shapiro, A. Shapiro и A. Nemirovski.

Аппарат двухэтапных задач стохастического программирования можно применить для решения экономических задач планирования и управления. Модели двухэтапных задач впервые были рассмотрены в работах E.M.L. Beale и G.B. Dantzig. Дальнейшее изучение постановок двухэтапных задач отражено в работах A. Madansky, R. Wets, М.А.Н. Dempster, J. Wessels и других авторов.

Двухэтапные задачи стохастического программирования с квантпльным критерием впервые были рассмотрены А.И. Кибзуном и A.B. Наумовым. В их работе была установлена эквивалентность априорной и апостериорной постановок задач, кроме того, была получена верхняя оценка квантильного критерия для двухэтапной задачи, основанная на решении задачи линейного программирования. Результаты дальнейших исследований двухэтапной задачи стохастического программирования с квантпльным критерием отражены в работах A.B. Наумова и И.М. Бобылёва, А.И. Кибзуна, A.B. Наумова и В.И. Норкина. Возможность дискретной аппроксимации линейной двухэтапной задачи стохастического программирования с квантпльным критерием исследовалась в работе А.И. Кибзуна и И.В. Никулина.

Прикладные двухэтапные задачи стохастического программирования с критерием в форме квантили применялись для оптимизации экономических систем. Например в работах A.B. Наумова исследовалась задача оптимизации бюджета госпиталя и задача оптимального инвестирования по квантильному критерию, в работе А.Б. Богданова и A.B. Наумова рассмотрена логистическая задача, в работе A.B. Наумова и C.B. Уланова исследована задача оптимального распределения ресурсов, а в работе А.И. Кибзуна, A.B. Наумова и C.B. Уланова рассмотрена задача оптимизации лётного парка авиакомпании.

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

Для достижения выбранной цели необходимо решить следующие задачи.

1. Разработать эффективные алгоритмы поиска решений многоэтапных линейных по стратегиям задач стохастического программирования с квантильным критерием.

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

Методы исследования. В диссертации используются методы системного анализа, методы стохастического программирования, математического моделирования, теории оптимизации, теории вероятностей.

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

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

1. Доказана эквивалентность многоэтапной линейной относительно стратегии задачи стохастического программирования с квантильным критерием и дискретизированным распределением случайных параметров и двухэтапной задачи квантильной оптимизации.

2. Разработан алгоритм поиска решения многоэтапной линейной по стратегии задачи стохастического программирования с квантильным критерием и дискретизированным распределением, основанный на переходе к эквивалентной задаче смешанного целочисленного линейного программирования.

3. Разработан алгоритм поиска решения двухэтапной задачи квантильной оптимизации с билинейной функцией потерь и нормальным распределением, основанный на переходе к задаче выпуклого программирования, параметризованной скалярным параметром, выбор которого осуществляется методом дихотомии.

4. Для задачи управления линейной стохастической системой специального вида с нормальным распределением случайных параметров и квантильным критерием получен детерминированный эквивалент.

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

Соответствие диссертации паспорту научной специальности.

В диссертации методы системного анализа применены для исследования сложных стохастических систем, проведено исследование задачи оптимизации, разработаны методы и алгоритмы их решения (области исследования 1, 4, 5 специальности 05.13.01).

Апробация работы. Результаты диссертации выносились на обсуждение научного сообщества в ходе научных семинаров кафедры теории вероятностей Московского авиационного института (рук. проф. Кибзун А.И.), 3-й и 4-й Традиционной молодёжной Школы «Управление, информация н оптимизация» (Россия, Ярополец, 2011 г.; Россия, Звенигород, 2012 г.), научного семинара лаборатории Л'2 7 Института проблем управления РАН (рук. проф. Поляк Б.Т.).

Материалы диссертации были представлены на следующих конференциях: 16-я международная конференция -«Системный анализ, управление и навигация» (Украина, Евпатория, 2011 г.), научно-техническая конференция молодых учёных и специалистов «Молодёжь и будущее авиации и космонавтики» (Россия, Москва, 2009 г.), XLIX международная научная студенческая конференция «Студент и научно-технический прогресс» (Россия, Новосибирск, 2011 г.), научно-практическая конференция студентов и молодых ученых МАИ «Инновации в авиации и космонавтике — 2011», 12-ая Международная конференция «Авиация и космонавтика-2013» (Россия, Москва, 2013 г.).

Работа поддержана грантами РФФИ (11-07-90407-Укр-ф-а, 11-07-00315-а, 12-07-00191-а) и государственным финансированием ФЦП «Научные и научно-педагогические кадры инновационной России» (мероприятие 1.2.2, госконтракт № 14.740.11.1128).

Публикации. Основные результаты диссертации опубликованы в 3 научных статьях [1-3] в журналах, входящих в перечень ВАК, в 5 статьях [4-8] в различных сборниках и материалах конференций. Общее число публикаций — 8.

Структура и объём диссертации. Диссертация содержит введение, три главы, заключение, перечень сокращений и условных обозначений и список используемой литературы. Работа состоит из 118 страниц, включая 7 рисунков, 3 таблицы и список литературы, содержащий 169 наименований.

Содержание диссертации

Во введении дано обоснование актуальности выбранной автором темы диссертации, сформулирована цель работы, аргументирована её научная новизна

и практическая значимость, а также в сжатом виде изложено содержание глав диссертации и сформулированы результаты, представляемые к защите.

В первой главе рассматривается многоэтапная линейная по стратегиям задача стохастического программирования с квантильным критерием в априорной постановке.

Целевая функция потерь имеет следующий вид:

Ф'у(и, у(-),Х) = cjw + a£(Xi)u + cfyi(u, Хг) + aJ2(XuX2)u -

n-1 лг-1

+ с?y2{u, A'i, X2) + ... = cjw + аи(х')и + cIu(u>

i-1 i—X

(1)

где и € Н'т - план первого этапа; у(-) = со\(ух(-),..., улг-1 (•)) ~ вектор-функция планов последующих N — 1 этапов, выбираемая в классе измеримых по Борелю функций со значениями в X = со1(Хх,..., Л'дг-1),

-X"' = со1(АГа,..., -Тг), г = 1,Лг —1, - наборы случайных векторов Х{ € М"4; 11г(Х!), г = 1,ЛГ — 1,-заданные измеримые вектор-функции размерности (тх 1); со, с*, г = 1, N — 1, - заданные детерминированные вектор-столбцы размерности (?тг х 1) и (тх х 1) соответственно.

Предполагается, что случайный вектор X имеет плотность распределения р(х), где х 6 К", п = щ + п2 + ... + пЛ'-1.

Набор из N — 1 ограничения имеет вид:

Ф,(и, у'(-). А") = A2i(X')u + BiV\u., X•) > ci3i(X'), i = 1, N - 1, (2)

где y'(-) = col(vi(-),-, t/i(-)) - наборы вектор-функций у{{-) <= Ж'"'; Ац{Хг): г = l,N — 1, - заданные измеримые матричные функции размерности (sj х m); Bi, i = 1,7V —1, - заданная матрица размерности (s; х ?n;); ац(Х'), г = 1, N — 1, - заданные измеримые вектор-функции размерности (sj х 1). Рассмотрим функцию вероятности

Р,,(и,у(-))=Г{Ф"(и,у(-),Х) <<р, ФМ{-),Х')>аы(Х*), i = l,N-l}, (3)

где V — вероятностная мера, порожденная распределением случайного вектора X; а также функцию квантили, представляющую собой минимальное пороговое значение 93, при котором выполняется вероятностное ограничение:

Va(u,y(-))= min{v>: ТУи, !/(•)) > a}, a е (0,1). (4)

Аг-этапная задача стохастического программирования с квантильным критерием в априорной постановке формулируется в следующем виде:

Ра = min <ра(и, у{-)), и» = arg min[ min ipa(u, y(-))], (5)

ueu, у( )еУ ueu y(-)ey

где U - заданное множество допустимых стратегий первого этапа, а у - множество допустимых стратегий последующих N — 1 этапов, имеющее вид

У ={»(•): А")>0, » = 1,ЛГ-1}.

Под решением задачи (5) понимается пара (<р£', и^). Если не существует то есть минимум в задаче (5) не достигается, то считается, что решение в задаче (5) не существует.

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

Предположим, что вероятностная мера V, порождённая распределением случайного вектора X, абсолютно непрерывна относительно меры Лебега н существует плотность р(х) случайного вектора X. Дискретизнруем вероятностную меру V следующим образом. Пусть хк, к = 1 ,К,- точки, сгенерированные случайным образом согласно плотности р(х). Определим меры

этих точек как Рк = Р{X = а^} = 1/К, к = 1, К. ~ д ~ ~

Пусть X = со1(А'1,.... Хп-г) - случайный вектор, соответствующий этим мерам, то есть Р{Х = хк} = рк, где случайные подвекторы Х{ имеют ту же размерность, что и А',, г = 1,^ — 1. Пусть Рц(х) - функция распределения случайного вектора X. Рассмотрим выборочную функцию распределения соответствующую случайному вектору X, реализация которой есть -Ря(а-). Имеет место сходимость ^а-(-г) ' при К оо для всех х (п.н. - почти наверное),

где Р(х) - функция распределения случайного вектора X.

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

Лемма 1.1. Пусть случайный вектор X = со1(Аь..., имеет

дискретное распределение Гк(х) специального вида. Тогда существуют детерминированные функции /¡(Ах) такие, что

Г{ = Д(Х1)} = 1,1 = 2, ЛГ — 1,

где V - вероятностная мера, аппроксимирующая меру V.

Благодаря описанной схеме дискретизации меры все компоненты случайного вектора X определяются первой компонентой Х\, поэтому удаётся свести многоэтапную задачу стохастического программирования к двухэтапной задаче.

Далее эквивалентность задач будет пониматься в смысле следующего определения.

определение 1.1. Две задачи оптимизации будем считать эквивалентными, если:

1) либо обе эти задачи имеют допустимые решения (с конечными значениями целевых функций), либо обе не имеют таких решений;

2) если эти задачи имеют допустимые решения, то оптимальные значения их целевых функций (конечные или бесконечные) совпадают;

3) если оптимальные значения их целевых функций конечны, то эти значения в обеих задачах либо достигаются, либо не достигаются;

4) если оптимальные значения целевых функций достигаются, то по оптимальному решению одной задачи с полющью явно описанного алгоритма указывается оптимальное решение другой задачи;

5) если оптимальные значения целевых функций конечны, но не достигаются, то по оптимизирующей последовательности стратегий одной задачи по явно описанному алгоритму указывается оптимизирующая последовательность для другой задачи.

Верна следующая теорема об эквивалентности многоэтапной линейной относительно стратегий задачи стохастического программирования и двухэтапиой задачи в априорных постановках.

теорема 1.1. N-этапная задача в априорной постановке (5) с дискретизированным распределением ^д-(.т) случайного вектора X эквивалентна в смысле определения 1.1 двухэтапной задаче стохастического программирования специального вида.

Доказательство основано на сведении трёхэтапной задачи в априорной постановке к двухэтапной задаче с последующим обобщением на случай сведения ЛГ-этапной задачи к двухэтапной по индукции. Структура ограничений полученной двухэтапной задачи повторяет структуру ограничений исходной задачи, кроме того, совпадают значения функций потерь обеих задач.

Сформулируем двухэтапную задачу квантильной оптимизации в апостериорной постановке. Пусть известны реализация х € И" случайного вектора X и стратегии и £ V С Ит первого этапа, а множество допустимых стратегий второго этапа задается как У = {у : у е Ш,щ,у > 0}. Сформулируем задачу второго этапа в виде:

Ф(и,х) = тт{с^г/|А>(.г)г( + Ву(х) > а3(ж)}, (6)

уег

где с\ - вектор размерности т\, матрица В имеет размерность (й х т\).

Если для некоторого и £ С/ н х из множества допустимых реализаций не существует у £ У, удовлетворяющего (6), будем полагать, что Ф(и, х) = +оо.

Следует отметить, что матрица .^(Х) и вектор аз(А') могут зависеть от случайного вектора X.

Определим функцию вероятности

Р^(и) = Р{а[(Х)и + Ф(и, X) < V?}

и функцию квантили

Фа(и) = min{<p : PJu) > а}.

'•р

Тогда задача первого этапа в апостериорной постановке имеет следующий вид:

= mi,n[coи + . йа = argmin[cju + lpa(u)\. (7)

neu ueu

Далее задача (7) сводится к задаче смешанного целочисленного линейного программирования.

Согласно доверительному методу, предложенному А.И. Кибзуном и В.В. Малышевым, задача (7) эквивалентна следующей задаче

Тра = min mm{cgм + sup[af(x)u + Ф(и. х)]}, _ ueU SeJ7° zes _

(wa, Sa) = arg min {cJu + sup[a^(a;)u + Ф(и, x)]}, uel•'.SeJ'c xgÄ

где Ф(и, x) определяется согласно (6), S € Ta - доверительное множество из семейства доверительных множеств Та = {S € Т: P(S) > а}, Т - борелевская сигма-алгебра, вероятностная мера Р соответствует дискретизированному распределению вектора X.

Если зафиксировать доверительное множество S € Та и рассмотреть эквивалентную двойственную задачу для подзадачи (6), то есть

Ф(м,х) = тах{(аз(х) — Л2(х)ы)Ти},

где v 6 Rs - вектор двойственных переменных, V - множество двойственных переменных, имеющее структуру выпуклого многогранника вида

К={»еК':Втв<сь»(>0,! = П}, (9)

получим

•0(S) = mm{c?u + supfaiYx)« + тах{(аз(х) — j4i(.t)m)tu}]}. (10)

ШЕ U xeS veV

Пусть векторы с\ и матрица В таковы, что множество V - компактно.

Поскольку V — ограниченное множество согласно теории двойственности и функция (аз(х) — A(x)m)tv линейна по v для всех х и и, то её максимум достигается в вершинах i'3 , j = 1, J, многогранного множества V, J -количество вершин множества V двойственных переменных. Поэтому задача (10) трансформируется в задачу

■0(S) = min{cg и + sup[aj(x)ii + max-f (пз(х) — ,42(x)it)TV}]}. (11) и е(/ xeS j=i. J

Учитывая, что после дискретизации меры случайный вектор X принимает лишь конечное число значений хк, к = 1, К, то задача (11) трансформируется в задачу

t!>(S) = min{cj« + max тах[а^(хг)и + (a3(xr) - A2(a:r)u)Ti)J']}, (12) «ее г=1Я j=i,j

где множество S состоит из векторов хг, г = 1. R,

Поскольку функция, стоящая под максимумом в выражении (12), линейна по и, а максимум находится по конечному набору векторов {xr}f=1, {V}j=1, то функция, стоящая под знаком min в выражении (12), оказывается кусочно-линейной и выпуклой по и € U.

В случае если U - выпуклый многогранник, задача (12) трансформируется в задачу линейного программирования

гЬ min (13)

иеи,Ф> О

при линейных ограничениях

с$и + aj(xr)u + {a3(xr) - A2{xr)u)Tvj < ф, г = lji, j = l77. (14)

Ранее множество S, V(S) > а, было зафиксировано. Выберем оптимальное множество Sa в задаче (8). С этой целью введём булевы переменные, характеризующие принадлежность точек хк доверительному множеству S по правилу:

j Д Г 1, если хк € S, к ~~ \ 0 иначе.

Обозначим рк = V{X = хк} = 1 /К, к = М?.

Пусть известна величина у > —оо, такая, что

7 < aj(xl)u + (а3(хк) - A2(xk)u)TvJ, к = 1J?, j = T7J-

Рассмотрим задачу смешанного целочисленного линейного программирования

ib —> min (15)

при ограничениях

' cju + 7 + ^[aJVju + (аъ{тк) - Л2(х1Мт^ - 7] < Ф, к = Т^К, j = Т77, к

< (16) *= 1

4 е {o,i}, k = 177?.

Верно следующее утверждение.

Теорема 1.3. Двухэтапная задача (7) в апостериорной постановке эквивалентна задаче (15) - (16) смешанного целочисленного линейного програлширования.

Полученную задачу смешанного целочисленного линейного программирования предлагается решать с помощью стандартных программных пакетов оптимизации с применением приёмов для сокращения перебора точек при нахождении оптимального множества й'а, в частности с использованием понятая ядра меры. Ядро меры уровня а при больших а в случае дискретного распределения совпадает с выпуклой оболочкой всех точек из распределения случайного вектора X за исключением крайних точек. Поэтому в случае квазнвыпуклости целевой функции по х достаточно перебрать только крайние точки из множества всех возможных значений. Стоит отметить, что при фиксированном ¿к, к = 1 ,К, задача (15) — (16) представляет собой задачу линейного программирования. В случае если в критерии задачи вместо матрицы Л2(А') рассмотреть просто случайный вектор X, то задача (8) оказывается принадлежащей классу портфельных задач, рассматриваемых в многих работах, в частности, в монографии А.И. Кибзуна и Ю.С. Кана.

Основным результатом главы является следующая теорема.

ТЕОРЕМА 1.4. Многоэтапная задача стохастического программирования в априорной постановке вида (5) для дискретного распределения Рк(х) специального вида, сгенерированного на основе плотности р(х), эквивалентна в смысле определения 1.1 задаче (15) - (16) смешанного целочисленного программирования.

В главе приводятся результаты численных расчётов, демонстрнрущне применение разработанного алгоритма.

Во второй главе рассматривается двухэтапная задача стохастического программирования следующей структуры. Пусть случайный вектор X с реализациями х £ К" имеет нормальное распределение Л/"(0,1). Введем функцию потерь, зависящую от стратегии первого этапа и € II С ИГ" и от реализаций х случайного вектора X и учитывающую оптимальную стратегию у второго этапа:

Ф(и, х) = с$и + хТА1и + ш£ с[у, (17)

у€У(и,х)

где

У (и, х) = {у € У : хтА21и + с%{и + Ъ?у > а^х + г = М}, (18)

У = {у € И™1 : У} > 0,j = М^},

со и с\ - заданные детерминированные вектор-столбцы размерности т и т1 соответственно; матрицы А\ и Ац имеют размерность (п х т); С2г, Ь; и аз,- -вектор-столбцы размерности т, тх и п соответственно, а с^ - константа.

Отметим, что часть матриц Лгг и векторов аз;, г = 1, в, определяющих множество У(и, х) допустимых стратегий у второго этапа, могут быть нулевыми. И тогда часть ограничений с теми л« номерами г, соответствующими этим матрицам и векторам в множестве У(и,х), будут детерминированными.

Пусть векторы С1 и 6г-, г = 1, в, таковы, что множество

ВТУ < сь VI > 0, г = М} (19)

компактно, где

ьГ

Bà

пусть ограничения на допустимые стратегии и первого этапа являются линейными:

1Г = {и <£ И"': Аии < &„},

где вектор Ъи имеет размерность к\, матрица Аи имеет размерность кх хт, причем являются такими, что II С - выпуклое компактное многогранное множество. Рассмотрим функцию вероятности:

Р^и) = Р{Х : + ХтА1и + Щи, X) < <р}, (20)

где V - вероятностная мера, порожденная распределением Л/"(0,1),

Ф{и, X) = ^

I оо ,У(и,Х) = 0,

и функцию квантили

¥>а(") = min{y> : Pv(u) > a}, a G (0, Р*), (22)

где

Р*= supV{X -.у(и,Х)ф0}.

■ueU

Сформулируем задачу первого этапа

¡Ра = inf Ifa(u),ua = arg min <pa{u). (23)

ueu ueu

Задача (17) - (18), (20) - (23) - двухэтапная билинейная задача квантильной оптимизации.

Согласно доверительному методу задача (23) эквивалентна следующей

задаче

= „ейЦ ^(S'u)'(üa,Stt) = arg jm ip{S,u), (24)

где введена функция максимума

У'(S, и) = Cqu + sup[zT Aiu + Щи, а-)], (25)

x€S

a S - доверительное множество, то есть V(S) > a, S € Та, где - семейство доверительных множеств S уровня а.

При этом выполняется ipa = ~ïpa, иа = ûa, причем под допустимым решением задачи (23) понимается пара (и, сра(и)), для которой ipa < <ра(и), и € U,

а для задачи (24) — тройка (и, S,i/>(S,u)), для которой <рп < ф(Б,и), S € Та, и е U.

Рассмотрим подзадачу (21), для которой эквивалентная двойственная задача с вектором v 6 Rs двойственных переменных будет иметь вид:

Ф(и, х) = sup ciT(u, x)v, (26)

l>€ v

где

а^х — uTAoiX + di — c^и \ a{u,x) = AT(u)x + b{u)= _ "... " , (27)

1 — uTAo X + ds — c£.u )

b (u) = (di — ..., da — cisiб),

V - выпуклый ограниченный многогранник, введенный выше в (19).

Пусть vi,j = 1, J, - вершины многогранника V, являющегося выпуклым компактом. Тогда в связи с линейностью по v функции в (26) её максимум на V будет достигаться в вершинах множества V:

Ф(и, х) = maxäT(w, x)vj. (28)

jel.J

Рассмотрим подзадачу задачи (24) для фиксированного множества S, в качестве которого выбирается доверительный шар SRa с радиусом Ra и центром в нуле, 'P(Sfi) = о. Для простоты обозначений далее будем использовать р = ра, R = Ra, где ра - радиус ядра вероятностной меры уровня а для случая нормального распределения случайного вектора X, а ядро вероятностной меры представляет собой множество, содержащееся во всех полупространствах меры больше, чем а.

Рассмотрим следующую задачу для шара Sr с центром в нуле н переменным радиусом г 6 [р, Д]:

фт = inf ip(Sr, u), иг = arg min ip(Sr, и), (29)

u&U ueU

где функция ip{Sr, и) определяется согласно (25) для множества Sr, то есть

ф(Бг, и) = с£и + sup [xTAiu + Ф(и, х)]. (30)

xesr

Поскольку функция под знаком sup в (30) согласно (27) и (28) кусочно-линейна и выпукла по х для каждого и € U, а шар Sr - компактное множество, то знак sup можно заменить на знак max. Таким образом, функция ф{Зг,и) в задаче (29) преобразуется к виду

Ф(Бг, и) = с£и + max[xTAiu + Ф(и, ж)]. (31)

геЬ'г

Исследуем задачу (29) с функцией максимума (31). Верно следующее утверждение.

ЛЕММА 2.4. Задача (29) является задачей выпуклого программирования и иТ существует для всех г 6 [р, Я].

Следующая лемма устанавливает свойство критериальной функции.

ЛЕММА 2.5. Функция фТ монотонно возрастает и непрерывна по ге\р,Щ.

Рассмотрим теперь задачу (31) для двух случаев г = р и г = Я, где р - радиус ядра гауссовской меры Р, а й - радиус доверительного шара

6 77(5Л) = о.

Для нормального распределения А/"(0,7) радиус Я может быть найден как решение трансцендентного уравнения:

я

2(-»>/>Г(п/2) / ^ 6ХР^^ = (32)

о

где Г(') - гамма-функция.

Следующая лемма устанавливает связь между решением задачи (24) и его верхней и нижней оценками.

Лемма 2.6. Для решения задачи (24) имеет .место следующая двусторонняя оценка

<¥а< <А*(и/г0) < Фка, (33)

приче.м, фца — фРа —>• 0 при а 1.

Улучшим верхнюю оценку оптимального значения функции квантили <ра, выбрав значение г 6 [р, Я) в задаче (29) такое, что <ра < фг < фк. Рассмотрим для этой цели следующее множество

Сг = {ж : с^и + хТА\иг + тах[йг(иГ)х^} < фг} (34)

з=и

и определим такое гд, что

г0 = Ы {г:Р(Сг)>а}. (35)

Заметим, что го существует, поскольку при г = Я верно, что Т(Сц) > а, так как Сд Э ¿д и 7'(^я) = а. Кроме того, при г = р выполняется Т{Ср) < а, поскольку Ср содержится в одном из полупространств с вероятностной мерой а, которые образуют ядро

Для размерности п > 2 справедлива следующая теорема.

ТЕОРЕМА 2.1 Для задачи (29) справедливы следующие утверждения

(i) го < R, где

го á inf {г : V(Cr) > а};

''£[/>,Я]

(И) существует г 6 [í'o,-ñ) такое, что V{C,) > а и

4>а < <fa(ur) < Фг < Фп]

(Иг) если < Г2, где Г\,Г2 £ [?"o,.fi) и V{GT¡) > a, V(CT2) > а, то <Л, < Фгх < фг2-

Для более общего случая, когда случайный вектор А' имеет нормальное распределение вида ЛГ(то, К), где К - невырожденная ковариационная матрица, рассмотрим вектор

Z = K~l/2(X - т),

который имеет распределение Aí(0, /). При такой замене переменных X на Z ограничения, задающие множество У(и, х), преобразуются в множество У(и,г), ограничения которого будут иметь точно такую же структуру, как и ограничения, описывающие множество У(и,х). Таким образом, случай X ~ Af(m, К) сводится к случаю X ~ Aí(0, /), рассмотренному выше.

Далее предлагается вычислительный алгоритм решения задачи (29). Рассмотрим вначале способ поиска точки tq, используя алгоритм дихотомии в следующей модификации. Выберем точки г = р и г = R, для которых 'Р{Ср) < се и V{Cr) > а. Рассмотрим точку г = (р+ R)/2 и найдем V{Cr) (алгоритм вычисления меры V(Cr) приводится далее). Если V{Cr) > а, то оставляем точки р и г. Если же V(Cr) < а, то далее оставляем точки г и R. И так далее производим деление пополам текущих отрезков неопределённости. Алгоритм сходится, поскольку V{CP) < а и V[Cr) > о. Скорость сходимости алгоритма равна 1/2А, где к - количество делений отрезков неопределённости пополам.

Предложим теперь алгоритм вычисления V(Cr) для произвольного r£[p,R], С этой целью дискретизируем меру так, как это предложено в первой главе. Пусть x/;¡ к = 1, К, - точки, сгенерированные на основе плотности нормального распределения vV(0,1). Пусть pk = 1/К - вероятностная мера, приписанная к точке Xk-k = 1 ,К. Таким образом, получаем меру "Р, аппроксимирующую гауссову меру V. Заменим меру V на меру V при вычислении V{Cr). Пусть для некоторого г 6 [р, Д] найдены иг и фГ в результате решения задачи выпуклого программирования

фг = 1шпф{3г,и), иТ = argminф(Зг,и).

u€U ueU

Для решения данной задачи можно использовать какие-либо эффективные методы выпуклого программирования, например метод внутренней точки.

Найдем вероятностную меру Р(СГ) множества

Сг = {х: с£иг + хтА\иг + тах[аг(ц,-, х)гР\ < фг}

Поскольку с Сг, то исключим из рассмотрения точки х^ £ б',.. Отметим, что вероятностная мера Р(БГ) множества Бг известна н вычисляется по формуле (32), в которой нужно заменить Я на г, а а на получаемую меру Р(5Г). Тогда

Г(Сг) = Р(СГ\5Г) + Р(5Г) « Р(СД5Г) + Р(5Г).

При этом мера Т[С^г\5г) может быть найдена за счёт перебора лишь точек Хк, лежащих вне Таким образом, вычисление вероятностной меры "Р(СГ) множества Сг резко упрощается.

По сути, описанная процедура вычисления Р(СГ) является реализацией метода Монте-Карло, из которой исключены точки, принадлежащие шару Бг. Алгоритм решения задачи выпуклого программирования основан на том факте, что случайный вектор X имеет нормальное распределение, но класс распределений случайного вектора может быть расширен, в частности, вектор случайных факторов может иметь сферически симметричное распределение. В этом случае почти все приведённые выше рассуждения остаются верными, изменяются только размеры доверительного шара и ядра вероятностной меры.

Основная трудоёмкость предложенного алгоритма заключается в процедуре подсчёта вероятностной меры многогранного множества. Однако за счёт дискретизации меры нормального распределения и введения процедуры сокращения перебора точек, которые образуют доверительное множество, удаётся сократить время счёта алгоритма.

В главе приводятся результаты численных расчётов, демонстрирующие применение разработанного алгоритма.

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

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

Решение поставленной задачи осуществляется следующим образом. Рассматривается участок местности для предполагаемой прокладки трассы. На карту местности накладывается сетка разбиения на мелкие прямоугольники, где г = 1, = 1, Л/ - число частей, на которые делятся стороны сетки разбиения по горизонтали и по вертикали соответственно; ау - стоимость прокладки трассы по горизонтали от точки (г,]) до точки (г + 1, 6у - стоимость прокладки трассы по вертикали от точки (г,до точки (г,+ 1); c¡j - стоимость прокладки трассы

по диагонали от точки (i,j) до точки (г + 1 ,j + 1). Если г = L, то а^ = Су = 0; а если j = М, то Ьц = сц = 0. Текущее значение стоимости работ по прокладке трассы до точки Xikjk = col(ik.jk) обозначим через dk, причем dk > 0.

Рассмотрим динамическую систему, описывающую изменение текущего положения точки на сетке разбиения и текущее значение стоимости работ:

ü+i = к + щ, к = 0, < Зк+\ = jk + 1 - Щ + ukvk, ji = 0, (36)

^ dfc+i = dk + S(ik,jk,uk,vk),di = 0,

где гк = 0,L,jk = 0,М - координаты точки на к—м шаге по горизонтали и по вертикали соответственно; к - номер шага, к = 1,N; N - общее число шагов, max{L,A/} < N < L+М; Жхд = со1(г'х,к),где ц = 0,ji = 0, - начальная точка; агл'+i..v+i = со1(глг+1:7лг+1))Где i.v+i = £,j.v+1 = М, - конечная точка; ик< Vk ~ управление, которое выбирается из множества U = {0,1} допустимых управлений, uk.vk € U; d.k - стоимость прокладки трассы до к—го участка включительно; S(ik,jk,uk,vk) - добавка к текущему значению стоимости работ.

Система (36) описывает движение по трём направлениям сетки разбнення, а применение особой комбинации управлений ик, vk позволяет описать движение посредством всего двух управляющих переменных uk,vk € {0,1}.

В зависимости от выбранного управления добавка к текущей стоимости трассы будет определяться величиной:

{aikjk, если ик = l,vk = 0,

bikh, если ик = 0, (37)

cikjk, если ик = 1, vk = 1.

Таким образом, текущее положение системы полностью описывается вектором текущего состояния системы:

zk = col(ik,jk, dk), к = 1,N+ 1.

Суммарная стоимость работ по прокладке трассы от начальной точки \ до конечной точки жл'+i..v+i равна dy+i-

Предположим, что параметры aikjb>hkjk,Cikjk,k = 1 ,N из (37), определяющие добавки к текущей стоимости в зависимости от управления, -случайные величины, зависящие от непредсказуемых локальных особенностей местности. Предполагается, что параметры независимы и имеют

нормальное распределение Oy ~ Л/"(т^, ~ Л/"(ту, D^), Cij ~ Л/"(т^-, £)?•).

Поскольку стоимость прокладки трассы случайна, рассмотрим в качестве критерия оптимальности квантильный критерий:

[dN+1]a = <Ра(u,v) = min{<£> : P<f{u.v) > а}, а в (0,1).

(38)

Задача оптимизации заключается в следующем

В работе получен детерминированный эквивалент стохастической задачи

ха - квантиль уровня а.

Для решения полученной задачи применяется алгоритм, основанный на методе динамического программирования и методе ветвей и границ.

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

1. Для случая дискретного распределения специального вида, полученного путём дискретизации непрерывного распределения, доказана эквивалентность многоэтапной линейной относительно стратегии задачи стохастического программирования с квантильным критерием и двухэтапной задачи квантильной оптимизации [3].

2. Для случая дискретного распределения специального вида, полученного путём дискретизации непрерывного распределения, разработан алгоритм поиска решения многоэтапной линейной по стратегии задачи стохастического программирования с квантильным критерием, основанный на переходе к эквивалентной задаче смешанного целочисленного линейного программирования [3].

3. Разработан алгоритм поиска гарантирующего решения двухэтапной задачи квантильной оптимизации с билинейной функцией потерь и нормальным распределением, основанный на последовательном решении задач выпуклого программирования и методе Монте-Карло [2].

4. Многошаговая задача управления линейной стохастической системой специального вида с гауссовскими помехами и квантильным критерием сведена к детерминированной задаче, для решения которой предложен алгоритм, основанный на методе динамического программирования и методе ветвей и границ [1].

Публикации в изданиях, входящих в перечень ВАК

1. Кибзун А.И., Хромова О.М. Выбор оптимальной трассы с учетом случайной стоимости работ на разных участках // Автоматика и телемеханика. —

[^ЛГ-ц]а = ¿Лг+1 + Жа\/£лг+1,

где

с1м+1 = М[^+1],Е,у+1 =

(40)

Основные результаты, выносимые на защиту

2012. - № 7. - С. 89-108.

2. Кибзун А.И., Хромова О.М. О коррекции положения стохастической системы по квантильному критерию // Электронный журнал «Труды МАИ». - 2014. - № 72.

3. Кибзун А.И., Хромова О.М. О сведении многоэтапной задачи стохастического программирования с квантнльным критерием к задаче смешанного целочисленного линейного программирования // Автоматика и телемеханика. — 2014. — № 4. — С. 120-133.

Публикации по теме диссертации в других изданиях

4. Хромова О.М. Модель прокладки трассы до аэропорта // Конкурс научно-технических работ и проектов молодых ученых и специалистов «Молодежь и будущее авиации и космонавтики». Москва. Аннотации работ. — Изд-во МАИ-ПРИНТ, 2009. - С. 72-73.

5. Хромова О.М. Оптимизация прокладки трассы, учитывающей случайную стоимость работ на разных участках пути, связаную с разнообразным рельефом местности // Материалы XLIX международной научной студенческой конференции «Студент и научно-технический прогресс»: Математика / Новосиб. Гос. Ун-т, Новосибирск, 16-20 апреля 2011 г. — С. 308.

6. Хромова О.М. Задача оптимальной прокладки автомобильной трассы с учетом случайной стоимости работ до места визирования авиационных систем // Научно-практическая конференция студентов и молодых ученых МАИ «Инновации в авиации и космонавтике - 2011». 26-30 апреля 2011 года. Москва. Сборник тезисов докладов. - М.: МЭЙЛЕР, 2011. - С. 117.

7. Кибзун А.И., Хромова О.М. Выбор оптимальной трассы с учетом случайной стоимости работ // 16-я международная научная конференция «Системный анализ, управление и навигация», Крым, Евпатория, 3-10 июля 2011 года. Сборник тезисов докладов. — М.: Изд-во МАИ-ПРИНТ, 2011. — С. 135-136.

8. Кибзун А.И., Хромова О.М. О сведении двухэтапной задачи квантильной оптимизации к задаче выпуклого программирования // Автоматика и телемеханика. — 2014. — № 5. — С. 67-82.

Подписано в печать: 12.03.14

Объем: 1,0 усл.п.л. Тираж: 100 экз. Заказ № 1093 Отпечатано в типографии «Реглет» г. Москва, Ленинградский проспект, д. 74 (495)790-47-77; www.reglet.ru