Диссертация (786272), страница 4
Текст из файла (страница 4)
В этом случае наиболееадекватными являются постановки задач стохастического программирования с квантильным критерием. Методам решения задач квантильной оптимизации посвящена монографияА.И. Кибзуна и Ю.С. Кана [25]. Однако известные к настоящему времени методы не охватывают многоэтапные модели c квантильным критерием, возникающие во многих прикладныхзадачах.Многоэтапные задачи стохастического программирования оказываются очень близки к динамическим задачам управления, учитывающим воздействие случайных факторов.Подобные задачи были рассмотрены в монографии В.В.
Малышева и А.И. Кибзуна [49]. Вмногоэтапных задачах выбирается стратегия первого этапа, которая в зависимости от реализации случайных факторов корректируется на последующих этапах (шагах). Как ужеотмечалось, многоэтапные задачи являются обобщением двухэтапных задач стохастического программирования. Впервые двухэтапная задача стохастического программирования сквантильным критерием была рассмотрена в работе А.И.
Кибзуна и А.В. Наумова [35], гдебыла получена верхняя оценка квантильного критерия для двухэтапной задачи, основаннаяна решении задачи линейного программирования.В работах С.В. Иванова и А.В. Наумова [17] и А.И. Кибзуна, А.В. Наумова и В.И. Норкина [36] рассмотрены линейные одноэтапные задачи квантильной оптимизации с дискретным распределением, которые сводятся к задачам смешанного целочисленного линейногопрограммирования. В работе А.И. Кибзуна, А.В. Наумова и В.И.
Норкина [37] рассмотрен общий случай двухэтапной задачи квантильной оптимизации, которая сведена к задачесмешанного целочисленного программирования большой размерности.В данной главе исследуется многоэтапная линейная относительно стратегий задачастохастического программирования с квантильным критерием. Такая постановка многоэтап-17ной задачи рассматривается впервые. С помощью эквивалентных преобразований исследуемая задача сводится к двухэтапной задаче стохастического программирования, которая, всвою очередь, сводится к задаче смешанного целочисленного линейного программирования.В разделе 1.1 приводится постановка многоэтапной линейной относительно стратегийзадачи стохастического программирования с квантильным критерием.В разделе 1.2 описывается процедура сведения рассматриваемой задачи с помощьюэквивалентных преобразований к двухэтапной задаче стохастического программирования ваприорной постановке.В разделе 1.3 описывается процедура сведения двухэтапной задачи стохастического программирования в априорной постановке к двухэтапной задаче в апостериорной постановке.
Доказывается эквивалентность двухэтапных задач с квантильным критерием ваприорной и в апостериорной постановках, записанных для общего случая.В разделе 1.4 для случая дискретного распределения специального вида, полученного путём дискретизации непрерывного распределения, двухэтапная задача стохастическогопрограммирования с квантильным критерием сводится к задаче смешанного целочисленноголинейного программирования.В разделе 1.5 предлагается алгоритм решения многоэтапной задачи стохастическогопрограммирования с квантильным критерием.Раздел 1.6 содержит результаты численных расчётов применения предложенного вразделе 1.5 алгоритма.181.1.Постановка многоэтапной линейной относительно стратегий задачистохастического программированияМногоэтапные задачи стохастического программирования обычно рассматриваются вапостериорной постановке, когда оптимальный план на текущем этапе выбирается в зависимости от реализации случайных факторов на предыдущих этапах.
По сути это означаетприменение метода динамического программирования для решения задачи стохастическогопрограммирования. Но, как известно из работы Д. Бертсекаса и С. Шрива [4], метод динамического программирования для решения задачи стохастического управления применимлишь тогда, когда критерий оптимизации обладает аддитивным и марковским свойствами.Именно такими свойствами обладает математическое ожидание от функции случайных потерь. Согласно монографии В.В. Малышева и А.И. Кибзуна [49] квантильный критерий необладает ни марковским, ни аддитивным свойствами, вследствие чего записать многоэтапную задачу стохастического программирования с квантильным критерием в традиционнойапостериорной постановке невозможно в принципе.
В данной главе диссертации исследуетсязадача квантильной оптимизации записанная в априорной постановке, когда оптимальныепланы на всех этапах, кроме первого, выбираются в классе функций, зависящих от всейпредыдущей информации.Сформулируем -этапную задачу стохастического программирования в априорнойпостановке. Введём функцию потерьΔTTTΦ (, (·), ) = T0 + 11 (1 ) + 1 1 (, 1 ) + 12 (1 , 2 ) ++T2 2 (, 1 , 2 )+ ... =T0+−1∑︁T1 ( )=1+−1∑︁(1.1)T (, ),=1где = col(1 , ..., −1 ), = col(1 , ..., ), = 1, − 1, — наборы случайных векторов ∈ IR ; ∈ ⊂ IR — план первого этапа, где — множество допустимых стратегий первого этапа,являющееся выпуклым компактным многогранником;(·) ∈ , (·) = col(1 (·), ..., −1 (·)) — вектор-функция планов последующих − 1 этапов,выбираемая в классе измеримых по Борелю функций со значениями в IR ; – множество допустимых стратегий последующих − 1 этапов, имеющее вид:Δ = {(·) : (, ) ≥ 0, = 1, − 1}.1 ( ), = 1, − 1, — заданные измеримые вектор-функции размерности ( × 1);(1.2)190 , , = 1, − 1, — заданные детерминированные вектор-столбцы размерности ( × 1) и( × 1) соответственно.В работе В.В.
Подиновского и В.Д. Ногина [56, С. 205] показано, что для того, чтобымножество допустимых стратегий первого этапа являлось выпуклым компактным многогранным множеством, необходимо, чтобы конус рецессивных направлений множества состоял только из нулевого вектора:Δ0+ = { ∈ IR : ≤ 0} = ⃗0,где ⃗0 ∈ IR — нулевой вектор, матрица имеет размерность (1 × ).Пусть ∈ IR , = 1 + 2 + ...
+ −1 , — реализации случайного вектора . Предположим, что случайный вектор имеет плотность распределения ().Пусть имеется набор из − 1 ограниченияΔΦ (, (·), ) = 2 ( ) + (, ) ≥ 3 ( ), = 1, − 1,(1.3)где (·) = col(1 (·), ..., (·)) — наборы вектор-функций (·) ∈ IR ;2 ( ), = 1, − 1, — заданные измеримые матричные функции размерности ( × ); , = 1, − 1 — заданная матрица размерности ( × );3 ( ), = 1, − 1, — заданные измеримые вектор-функции размерности ( × 1).Рассмотрим функцию вероятности (, (·)) = {Φ (, (·), ) ≤ , Φ (, (·), ) ≥ 3 ( ), = 1, − 1},(1.4)характеризующую вероятность такого события, что целевая функция потерь не превосходитнекоторый уровень при выполнении ограничений задачи, где — вероятностная мера,порождённая распределением случайного вектора .Рассмотрим функцию квантили, характеризующую значение, которое заданная случайная величина не превышает с некоторой фиксированной вероятностьюΔ (, (·)) = min{ : (, (·)) ≥ }, ∈ (0, 1),(1.5)где — требуемый уровень вероятности.Как правило, в прикладных задачах требуемый уровень вероятности оказываетсявыше 1/2, поэтому здесь и далее без ограничения общности будем считать, что выбираетсяиз диапазона ∈ (1/2, 1).20Сформулируем -этапную задачу стохастического программирования c квантильнымкритерием в априорной постановке =min∈, (·)∈ (, (·)), = arg min[ min (, (·))],∈ (·)∈(1.6)где — заданное множество допустимых стратегий первого этапа, а — множество допустимых стратегий последующих − 1 этапов, структура которого определена выражением (1.2).
Под решением задачи (1.6) понимается пара ( , ). Если не существует оптималь-ной стратегии первого этапа , то есть минимум в -этапной задаче (1.6) не достигается,то считается, что решение в задаче (1.6) не существует.Для простоты дальнейших рассуждений рассмотрим многоэтапную задачу квантильной оптимизации, в которой количество этапов = 3. Тогда функция вероятности трёхэтапной задачи стохастического программирования примет вид: (, (·)) = {Φ3 (, (·), ) ≤ , Φ (, (·), ) ≥ 3 ( ), = 1, 2},(1.7)где функция потерь трёхэтапной задачи представима в виде:TTTTΦ3 (, (·), ) = T0 + 11 (1 ) + 1 1 (, 1 ) + 12 (1 , 2 ) + 2 2 (, 1 , 2 ),(1.8)при ограниченияхΦ2 (, 2 (·), 2 ) = 22 (1 , 2 ) + 2 2 (, 1 , 2 ) ≥ 32 (1 , 2 ),1(1.9)1Φ1 (, (·), ) = 21 (1 ) + 1 1 (, 1 ) ≥ 31 (1 ),где = col(1 , 2 ), 1 = 1 , 2 = col(1 , 2 ); ∈ ⊂ IR — план первого этапа;(·) ∈ , (·) = col(1 (·), 2 (·)) — вектор-функция планов второго и третьего этапов,1 (·), 2 (·) имеют размерности (1 × 1) и (2 × 1) соответственно;11 ( 1 ), 12 ( 2 )— заданные измеримые вектор-функции размерности ( × 1);0 , 1 , 2 — заданные детерминированные вектор-столбцы размерности ( × 1), (1 × 1),(2 × 1) соответственно;21 ( 1 ), 22 ( 2 ) — заданные измеримые матричные функции размерности (1 × ) и(2 × ) соответственно;1 , 2 — заданные матрицы размерности (1 × 1 ) и (2 × 2 ) соответственно;31 ( 1 ), 32 ( 2 ) — заданные измеримые вектор-функции размерности (1 × 1) и (2 × 1)соответственно.Данная трёхэтапная задача стохастического программирования может быть сведенак двухэтапной задаче, что будет показано в следующем разделе.211.2.Сведение многоэтапной задачи квантильной оптимизации кдвухэтапной задаче стохастического программирования в априорнойпостановкеПредположим, что вероятностная мера , порождённая распределением случайного вектора , абсолютно непрерывна относительно меры Лебега и существует плотность() случайного вектора .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
