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

• Автор: Хромова, Ольга Михайловна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 118 с. : ил.

Оглавление
Введение
1 Алгоритмы решения многоэтапных задач стохастического программирования с квантильным критерием для линейных относительно стратегий систем
1.1. Постановка многоэтапной линейной относительно стратегий задачи стохастического программирования
1.2. Сведение многоэтапной задачи квантильной оптимизации к двухэтапной задаче стохастического программирования в априорной постановке
1.3. Сведение двухэтапной задачи стохастического программирования в априорной постановке к двухэтапной задаче в апостериорной постановке
1.4. Сведение двухэтапной задачи в апостериорной постановке к задаче смешанного целочисленного линейного программирования
1.5. Алгоритм решения многоэтапной линейной по стратегиям задачи стохастического программирования с квантильным критерием
1.6. Результаты численных расчётов
1.7. Выводы по главе
2 Алгоритмы решения двухэтапных задач стохастического программирования с квантильным критерием для билинейных систем
2.1. Постановка двухэтапной билинейной задачи стохастического программирования с квантильным критерием
2.2. Свойства верхней оценки функции квантили двухэтапной билинейной задачи стохастического программирования
2.3. Поиск решения задачи выпуклого программирования в случае дискретизированного распределения случайных параметров
2.3.1. Сведение двухэтапной билинейной задачи стохастического программирования с квантильным критерием к задаче выпуклого программирования
2.3.2. Алгоритм решения задачи выпуклого программирования
2.4. Результаты решения двухэтапной задачи квантильной оптимизации с билинейной функцией потерь
2.5. Выводы по главе
3 Задача выбора оптимальной трассы с учётом случайной стоимости работ на разных участках
3.1. Динамическая модель прокладки трассы
3.2. Задача оптимизации в детерминированной постановке
3.3. Алгоритм решения задачи оптимизации в детерминированной постановке с критерием в форме математического ожидания

3.3.1. Применение метода динамического программирования для решения задачи оптимизации в детерминированной постановке
3.3.2. Алгоритм решения задачи в детерминированной постановке с применением метода ветвей и границ и схемы сценариев
3.3.3. Программная реализация алгоритма
3.4. Задача оптимизации в стохастической постановке
3.5. Алгоритм решения стохастической задачи с квантильным критерием
3.5.1. Применение метода динамического программирования для решения задачи оптимизации в стохастической постановке
3.5.2. Алгоритм решения задачи в стохастической постановке с применением метода ветвей и границ
3.6. Результаты численных расчётов на примере выбора оптимальной трассы до
аэропорта
3.7. Выводы по главе
Заключение
Перечень сокращений и условных обозначений
Список литературы

Введение
Разработка математических моделей, описывающих управление стохастическими системами, является важной задачей системного анализа. В частном случае стохастические системы могут иметь многоэтапную структуру, как и многие практические задачи, например задачи экономики, управления летательными аппаратами. Процесс принятия решения в таких задачах осуществляется, как правило, последовательно на каждом этапе. На первом этапе выбирается некоторая предварительная стратегия, которая корректируется в дальнейшем за счёт выбора стратегий последующих этапов при реализации случайных параметров. Оптимальные стратегии на различных этапах выбираются исходя из одного и того же критерия оптимизации. Сложность анализа отдельных этапов подобных задач обусловлена необходимостью гарантировать существование допустимых решений задачи на всех последующих этапах. Для описания математических постановок и решения подобных систем применяется аппарат многоэтапных и двухэтапных задач стохастического программирования.
Многоэтапные задачи являются одной из форм записи задачи управления динамическими системами, имеющими широкое применение в задачах экономических и авиационно-космических приложений.
Пусть имеется динамическая система
гг+1 = гг - Дм, + м>„ * = 1, N — 1, = (<р, 0, ...,0).

й5,+1 — вектор текущего состояния системы, £>, — матрица раз-
/дг I
мерности (в, + тп) х (т + тг + N — 1) такая, что А)=
(сТ со о>
, 01=

аи№) сЛ
^21(^1) Вх

(с&{ХиХ2)
О о А22(Х1,Х2) в

и т.д.; X = со1(Хх,..., Хм-х) — случайный вектор, X, е И
аь(Х*), X' = со1(Хь..., А',), г = 1, N — 1, — измеримые вектор-функции размерности (т х 1);
со, сг. г = 1, N — 1, — детерминированные вектор-столбцы размерности (т х 1) и (ш, х 1) соответственно;

P. Girodet и др. [80] для решения подобных задач используется метод ветвей и границ, впервые предложенный в 1960 году А.Н. Land and A. G. Doig [121] для решения задач целочисленного программирования. Данный метод является вариацией полного перебора с отсечением заведомо неоптимальных решений. Для решения данных задач также применим метод Гомори, предложенный в работе R. Gomory [102|, и алгоритм на основе метода Вендерса [81], детально изученный в работах A.B. Наумова и С.В. Иванова [17,53].
Кроме того, для решения задач смешанного целочисленного программирования разработаны эффективные программные средства. В частности, задачу (1.37) — (1.38) можно решить программными пакетами оптимизации, например пакетом IBM ILOG CPLEX [107] или программой LPSolve [61].
Существуют различные приёмы для сокращения перебора при нахождении оптимального множества в задаче (1.28), в частности с использованием понятия ядра вероятностной меры, приведённого в монографии А.И. Кибзуна и Ю.С. Кана [25].
Определение 1.2. Множество Ка вида
Ка = Р| {х : lTx < Ьа(1)},

где Ьа{1) — а-квантилъ распределения случайной величины 1ГХ, то есть
Ьа(1) = min{6 : V{lTx < b} > а}, X — п-мерный случайный вектор, а £ (1/2) 1), называется a-ядром вероятностной меры V, порождённой в IR'1 распределением вектора X.
Ядро вероятностной меры уровня а при больших а в случае дискретного распределения совпадает с выпуклой оболочкой всех точек из распределения случайного вектора X за исключением крайних точек. Поэтому в случае квазивыпуклости целевой функции по х достаточно перебрать только крайние точки из множества всех возможных значений.
Стоит отметить, что при фиксированном значении <5*,, k = 1, К задача (1.37) — (1.38) представляет собой задачу линейного программирования. Если бы в критерии вместо матрицы А2(Х) рассматривался просто случайный вектор X, то задача (1.28) принадлежала бы классу портфельных задач, рассматриваемых в многих работах, в частности в монографии А.И. Кибзуна и Ю.С. Кана [25].
Объединяя все сказанное с учётом выполненных ранее эквивалентных переходов, можно сформулировать следующее утверждение.
ТЕОРЕМА 1.4. Многоэтапная задача стохастического программирования в априорной постановке вида (1.6) для дискретного распределения Fk(x) специального вида, сгенерированного на основе плотности р(х), эквивалентна в смысле определения 1.1 задаче (1 37) — (1.38) смешанного целочисленного программирования.