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

министвРство оБРА3овАния и нАуки Российской ФвдвРАциимоско в ский АвиАщионнь1й институт(национальньтй исследовательский университет)Ёа правах рукописи{,.ромова Фльга Р[ихайловна1Р|оптими3Ация стохАстичвскихлинпйнь1х относитвльно стРАтпо квАнтильномуР'гу1у\сиотвмкРитвРию{6пециальностьсистемньтйана^г{и3'(авиацион Ё{ая|[_05.

13.01_управление и обработка информацииу[ракетно-космическая техника)!иссертация па соискапие утёной степеникандидата физико-математическ|о( наукЁаутньтй руководитель|_доктор физико-математических }1аук'профессор А.1'1. 1(ибзун!!ь:\{осква-2014год2ОглавлениеВведение1 Алгоритмы решения многоэтапных задач стохастического программирования с квантильным критерием для линейных относительно стратегийсистем1.1. Постановка многоэтапной линейной относительно стратегий задачи стохастического программирования . . .

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

. . . . . . . .1.4. Сведение двухэтапной задачи в апостериорной постановке к задаче смешанного целочисленного линейного программирования . . . . . . . . . . . . . . . .1.5. Алгоритм решения многоэтапной линейной по стратегиям задачи стохастического программирования с квантильным критерием . .

. . . . . . . . . . . . .1.6. Результаты численных расчётов . . . . . . . . . . . . . . . . . . . . . . . . . . .1.7. Выводы по главе 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 Алгоритмы решения двухэтапных задач стохастического программирования с квантильным критерием для билинейных систем2.1. Постановкадвухэтапнойбилинейнойзадачистохастическогопрограммирования с квантильным критерием .

. . . . . . . . . . . . . . . . . .2.2. Свойства верхней оценки функции квантили двухэтапной билинейной задачистохастического программирования . . . . . . . . . . . . . . . . . . . . . . . . .2.3. Поиск решения задачи выпуклого программирования в случаедискретизированного распределения случайных параметров . . .

. . . . . . . .2.3.1. Сведениедвухэтапнойбилинейнойзадачистохастическогопрограммирования с квантильным критерием к задаче выпуклогопрограммирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3.2. Алгоритм решения задачи выпуклого программирования . . . . . . . .2.4. Результаты решения двухэтапной задачи квантильной оптимизации с билинейной функцией потерь . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.5. Выводы по главе 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 Задача выбора оптимальной трассы с учётом случайной стоимости работна разных участках3.1. Динамическая модель прокладки трассы . .

. . . . . . . . . . . . . . . . . . . .3.2. Задача оптимизации в детерминированной постановке . . . . . . . . . . . . . .3.3. Алгоритм решения задачи оптимизации в детерминированной постановке скритерием в форме математического ожидания . . . . . . . . . . .

. . . . . . .4161821263237394041444648485961646569707333.4.3.5.3.6.3.7.3.3.1. Применение метода динамического программирования для решения задачи оптимизации в детерминированной постановке . . . . . . . . . . .3.3.2. Алгоритм решения задачи в детерминированной постановке сприменением метода ветвей и границ и схемы сценариев . .

. . . . . . .3.3.3. Программная реализация алгоритма . . . . . . . . . . . . . . . . . . . .Задача оптимизации в стохастической постановке . . . . . . . . . . . . . . . . .Алгоритм решения стохастической задачи с квантильным критерием . . . . .3.5.1. Применение метода динамического программирования для решения задачи оптимизации в стохастической постановке . . . . . .

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

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

Оптимальные стратегии на различных этапах выбираются исходя из одного и того жекритерия оптимизации. Сложность анализа отдельных этапов подобных задач обусловленанеобходимостью гарантировать существование допустимых решений задачи на всех последующих этапах. Для описания математических постановок и решения подобных систем применяется аппарат многоэтапных и двухэтапных задач стохастического программирования.Многоэтапные задачи являются одной из форм записи задачи в терминах управления динамическими системами, имеющими широкое применение в задачах экономическихи авиационно-космических приложений.Пусть имеется динамическая система+1 = − ˜ + , = 1, − 1, 0T = (, 0, ..., 0),где ∈ +1— вектор текущего состояния системы, — ⎛ матрица⎞⎛T11 (1 )T⎜0 0⎜⎜⎟⎜21 (1 )⎜ ..

.. ⎟мерности ( + ) × ( + + − 1) такая, что 0 =⎜ . . ⎟, 1 =⎜⎜..⎠⎝⎜.⎝0 00⎛⎞T ( , ) T2 ⎟⎜ 12 1 2⎜⎟⎜00⎟⎜⎟⎜⎟2 =⎜22 (1 , 2 ) 2 ⎟ и т.д.; = col(1 , ..., −1 ) — случайный вектор, ∈ IR ,⎜⎟⎜.... ⎟⎜.. ⎟⎝⎠00раз⎞T1⎟⎟1 ⎟⎟.. ⎟,. ⎟⎠01 ( ), = 1, − 1, — измеримые вектор-функции размерности ( × 1);0 , , = 1, − 1, — детерминированные вектор-столбцы размерности ( × 1) и ( × 1)соответственно;52 ( ), = 1, − 1, — заданные измеримые матричные функции размерности ( × ); , = 1, − 1 — заданная матрица размерности ( × );˜T = (, (, 1 , ..., )) — векторы управления на текущем шаге , = 1, ,˜T˜ ∈ IR( + ), ∈ ⊂ IR ;0 = (, 0, ..., 0), (·) — выбирается в классе измеримых по Борелю функций со значениями в IR ;((++1)×1) — векторы случайных,⎞ системы, ∈ IR⎛ возмущений⎛⎞0⎟⎜0⎟⎜⎜⎟⎟⎜0⎜⎟⎟⎜⎜31 (1 )⎟⎟⎜⎜⎟⎜32 (1 , 2 )⎟⎜⎟⎟, 1 = ⎜ 0 ⎟, 2 = ⎜⎟⎜⎜⎟⎟⎜0⎜ .. ⎟⎟⎜⎜ .

⎟⎟⎜..⎝⎠⎟⎜.⎠⎝00где 3 ( ), = 1, − 1, — измеримые вектор-функции размерности ( × 1).Путем очевидных преобразований можно убедиться, что записанная динамическаясистема может быть представлена в виде многоэтапной задачи стохастического программирования в априорной постановке с функцией потерьΔTTTΦ (, (·), ) = T0 + 11 (1 ) + 1 1 (, 1 ) + 12 (1 , 2 ) ++T2 2 (, 1 , 2 )+ ... =T0+−1∑︁=1T1 ( )+−1∑︁T (, )=1и набором из − 1 ограниченияΔΦ (, (·), ) = 2 ( ) + (, ) ≥ 3 ( ), = 1, − 1.Многоэтапные задачи рассматривались в работах таких авторов, как D. Barro иE. Canestrelli [77], J. Dupa˘ová, G. Consigli и S.W. Wallace [93], K. Frauendorfer [100],F.V.

Louveaux [125], P. Olsen [136], R.T. Rockafellar и R.J.-B. Wets [143, 144], S.W. Wallaceи T. Yan [163].В практических приложениях, например в финансовом планировании, экономике,применяются, как правило, линейные постановки многоэтапных задач стохастического программирования. Многоэтапные задачи стохастического линейного программирования c критерием в форме математического ожидания рассматривались в работах J.R. Birge [84],C. Beltran-Royo, L.F.

Escudero и др. [79], M.S. Casey и S. Sen [88], P. Fúsek, P. Kall, J. Mayer идр. [101], C. Swamy и D.B. Shmoys [158]. Прикладная задача оптимизации инвестиционного6портфеля, записанная в форме многоэтапной задачи стохастического линейного программирования рассмотрена в работе G.B. Dantzig и G. Infanger [90].Различные методы решения многоэтапных задач стохастического программирования с дискретным распределением случайных параметров рассмотрены в работах P.

Fúsek,P. Kall, J. Mayer и др. [101], F.V. Louveaux [124].Случай гауссовского распределения исследован в работах P. Parpas, B. Ustin,M. Webster и Q.K. Tran [137], E. Schweitzer и M. Avriel [149], где предложены алгоритмыполучения верхней оценки оптимального решения задачи.Различные постановки линейных многоэтапных задач целочисленного стохастического программирования и условия оптимальности решений исследуются в работе W. R¨misch иR. Schultz [145], а в работе Y. Guan, S. Ahmed и G.L. Nemhauser [103] для решения многоэтапной задачи стохастического целочисленного программирования предлагается использоватьметод генерации секущих плоскостей.

Эффективность данного метода продемонстрированана примере задачи о ранце в стохастической постановке и стохастической задачи большойразмерности.В работах J.L. Higle и S. Sen [105], W. R¨misch и R. Schultz [145] для решения многоэтапных задач стохастического программирования применяется теория двойственности.Нелинейный случай многоэтапных задач стохастического программирования рассмотрен в работах J. Blomvall и P.O. Lindberg [87], V.

Kaˇková [112], G. Zhao [169].Несмотря на наличие большого количества работ в области многоэтапных стохастических задач, класс многоэтапных задач стохастического программирования с квантильнымкритерием ранее не рассматривался.Многоэтапные линейные относительно стратегий задачи стохастического программирования с квантильным критерием позволяют учитывать возможность коррекции выбираемой стратегии при реализации случайных параметров. В ходе решения таких задач получается гарантированный по вероятности результат, что позволяет применять алгоритмырешения данных задач в приложениях авиационной и космической техники.Многоэтапные задачи стохастического программирования являются естественнымобобщением двухэтапных задач.

Двухэтапные и многоэтапные задачи стохастического программирования рассмотрены в работах E. Schweitzer и M. Avriel [149], A. Shapiro [153, 154],A. Shapiro и A. Nemirovski [156].Аппарат двухэтапных задач стохастического программирования можно применитьдля решения экономических задач планирования и управления. Решение двухэтапной за-7дачи представляется в виде детерминированного и случайного векторов — планов первогои второго этапов соответственно.

Стратегии первого и второго этапов выбираются в рамках общей цели задачи. При этом при выборе стратегии первого этапа учитывается лишьоптимальное значение критериальной функции задачи второго этапа.Модели двухэтапных задач впервые были рассмотрены в работах Е.M.L. Beale [78] иG.B. Dantzig [89]. Дальнейшее изучение постановок двухэтапных задач отражено в работахA. Madansky [127, 128], R. Wets [166, 167], а различные обобщения постановок данных задачприведены в работах M.A.H. Dempster [92], J. Wessels [165]. Исследованиями, связанными сопределением и оценкой распределения компонент оптимального плана и условного экстремума критериальной функции, занимались M.M.