Диссертация (786272)
Текст из файла
министвРство оБРА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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
