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

Гольштейна [13], эквивалентную двойственную подзадачуΦ̄(, ) = max{(3 () − 2 ())T },∈где ∈ IR — вектор двойственных переменных задачи Φ̄(, ) второго этапа, — множестводвойственных переменных, имеющее структуру выпуклого многогранника вида = { : T ≤ 1 , ≥ 0, = 1, }.(1.30)Пусть векторы 1 и матрица таковы, что множествоΔ = { ∈ IR : T ≤ 1 , ≥ 0, = 1, }(1.31)33компактно.Таким образом, подзадача (1.29) преобразуется к следующему виду:TT() = min{T0 + sup[1 () + max{(3 () − 2 ()) }]}.∈∈∈(1.32)Аналогичный прием перехода от исходной задачи стохастического программированияк двойственной задаче применялся, например, в работе А.В.

Наумова и С.В. Иванова [54] длясведения двухэтапной задачи стохастического линейного программирования к одноэтапнойзадаче квантильной оптимизации.Поскольку — ограниченное множество согласно теории двойственности, изложенной в монографии Е.Г. Гольштейна [13], и функция (3 () − 2 ())T , стоящая под знакомmax в задаче (1.32), линейна по вектору двойственных переменных для всех реализаций и стратегий первого этапа , то максимум данной функции достигается в вершинах , = 1, , многогранного множества , — количество вершин множества двойственных переменных. Поэтому задача (1.32) может быть записана в эквивалентном виде:T T() = min{T0 + sup[1 () + max {(3 () − 2 ()) }]}.∈(1.33)=1,∈После применения к случайному вектору процедуры дискретизации меры, описанной в˜ принимает лишь конечное число значений , = 1, ,разделе 1.2, случайный вектор где — количество реализаций случайного вектора.

С учётом этого факта, задача (1.33)трансформируется в следующую задачу:T T () = min{T0 + max max [1 ( ) + (3 ( ) − 2 ( )) ]},∈(1.34)=1, =1,где доверительное множество состоит из векторов , = 1, .T Поскольку функция T1 ( ) + (3 ( ) − 2 ( )) , стоящая под максимумом в вы-ражении (1.34), линейна по стратегии первого этапа, а поиск максимума осуществляется по конечному набору векторов реализации { }=1 и двойственных переменных { }=1 , тофункция, стоящая под знаком минимума в выражении (1.34), оказывается кусочно-линейнойи выпуклой по стратегиям ∈ первого этапа.Поскольку множество допустимых стратегий первого этапа — выпуклый многогранник, то задача (1.34) трансформируется в задачу линейного программирования → min∈ ,≥0(1.35)c ограничениямиT T T0 + 1 ( ) + (3 ( ) − 2 ( )) ≤ , = 1, , = 1, .(1.36)34˜Ранее доверительное множество , ()≥ , было зафиксировано.

Выберем оптимальное доверительное множество в задаче (1.28). С этой целью введём булевы пере˜менные, характеризующие принадлежность точек реализации случайного вектора доверительному множеству по следующему правилу:⎧⎨ 1, если ∈ ,Δ =⎩ 0, иначе.Δ˜ ˜ = } = 1/, = 1, .Обозначим = {Пусть известна величина >−∞, являющаяся оценкой снизу функцийT T1 ( ) + (3 ( ) − 2 ( )) , = 1, , = 1, , то естьT ≤ T1 ( ) + (3 ( ) − 2 ( )) , = 1, , = 1, .(1.37)Тогда задача (1.35) — (1.36) преобразуется в задачу смешанного целочисленного линейного программирования→min∈,1 ,..., ,≥0при ограничениях⎧T T ⎪T⎪0 + + [1 ( ) + (3 ( ) − 2 ( )) − ] ≤ , = 1, , = 1, ,⎪⎪⎪⎪⎨ ∑︁ ≥ ,⎪⎪=1⎪⎪⎪⎪⎩ ∈ {0, 1}, = 1, .(1.38)(1.39)Согласно работе А.И. Кибзуна, А.В. Наумова и В.И.

Норкина [36] задача (1.38) —(1.39) линейного целочисленного программирования смешанного типа эквивалентна задаче (1.19) стохастического программирования в смысле определения 1.1.Таким образом, объединяя сказанное, можно сформулировать следующее утверждение.Теорема 1.3. Двухэтапная задача (1.19) в апостериорной постановке эквивалентна в смысле определения 1.1 задаче (1.38) — (1.39) смешанного целочисленного линейногопрограммирования.Техника сведения задачи стохастического программирования в квантильной постановке к задаче смешанного целочисленного линейного программирования, используемая вданном разделе, изложена в работе А.И. Кибзуна, А.В. Наумова и В.И.

Норкина [36], гдеизучаются задачи квантильной оптимизации с дискретным распределением случайных векторов. Эту технику удалось применить для исследуемой в данной главе многоэтапной задачи стохастического программирования для случая дискретного распределения специального35вида. Полученную задачу смешанного целочисленного линейного программирования предлагается решать стандартными методами. Например, в работе M. Benichou, J.M. Gauthier,P.

Girodet и др. [80] для решения подобных задач используется метод ветвей и границ,впервые предложенный в 1960 году A.H. Land and A. G. Doig [121] для решения задач целочисленного программирования. Данный метод является вариацией полного перебора сотсечением заведомо неоптимальных решений. Для решения данных задач также применим метод Гомори, предложенный в работе R. Gomory [102], и алгоритм на основе методаБендерса [81], детально изученный в работах А.В.

Наумова и С.В. Иванова [17, 53].Кроме того, для решения задач смешанного целочисленного программирования разработаны эффективные программные средства. В частности, задачу (1.38) — (1.39) можнорешить программными пакетами оптимизации, например пакетом IBM ILOG CPLEX [107]или программой LPSolve [61].Существуют различные приемы для сокращения перебора при нахождении оптимального множества в задаче (1.28), в частности с использованием понятия ядра вероятностноймеры, приведённого в монографии А.И. Кибзуна и Ю.С.

Кана [25].Определение 1.2. Множество следующего вида:⋂︁Δ ={ : T ≤ ()},||||=1где ()—-квантильраспределенияслучайнойвеличиныT ,т.е.ΔT () = min{ : { ≤ } ≥ }, — -мерный случайный вектор, ∈ (1/2, 1), называется -ядром вероятностной меры , порождённой в IR распределением вектора .Ядро вероятностной меры уровня при больших в случае дискретного распреде˜ления совпадает с выпуклой оболочкой всех точек из распределения случайного вектора за исключением крайних точек.

Поэтому в случае квазивыпуклости целевой функции по ˜достаточно перебрать только крайние точки из множества всех возможных значений.Стоит отметить, что при фиксированном значении , = 1, задача (1.38) — (1.39)представляет собой задачу линейного программирования. Если бы в критерии вместо мат˜ рассматривался просто случайный вектор ,˜ то задача (1.28) принадлежала бырицы 2 ()классу портфельных задач, рассматриваемых в многих работах, в частности в монографииА.И. Кибзуна и Ю.С. Кана [25].Объединяя все сказанное с учётом выполненных ранее эквивалентных переходов,можно сформулировать следующее утверждение.Теорема 1.4.

Многоэтапная задача стохастического программирования в априорной постановке вида (1.6) для дискретного распределения () специального вида, сге-36нерированного на основе плотности (), эквивалентна в смысле определения 1.1 задачесмешанного целочисленного программирования (1.38) — (1.39).Решение задачи (1.38) — (1.39) является приближённым для многоэтапной задачи (1.6) стохастического программирования в априорной постановке. Но согласно теоремеГливенко и Кантелли, приведённой в работе А.Н. Ширяева [71, C. 482], выборочная функцияраспределения ˆ () сходится почти наверное к исследуемой функции распределения ()c плотностью ().

Поэтому можно надеяться, что и решение задачи (1.38) — (1.39) будетсходиться к решению задачи (1.6).371.5.Алгоритм решения многоэтапной линейной по стратегиям задачи стохастического программирования с квантильным критериемДля решения многоэтапной задачи стохастического программирования с линейнойотносительно стратегий функцией потерь предлагается следующий алгоритм:1) задаём уровень доверительной вероятности ∈ (0, 1);2) задаём объём выборки и генерируем выборку , = 1, на основе схемы дискретизации, предложенной в разделе 1.2;3) определяем вершины , = 1, , выпуклого многогранника — множества двойственных переменных из решения (1.30);4) определяем точки, лежащие вне -ядра вероятностной меры, определяем булевы переменные , = 1, .5) осуществляем поиск минимального значения величины из решения набора задач (1.37) линейного программирования на каждом элементе выборки , = 1, .6) определяем начальное приближение, например, дополнением точек доверительногошара ближайшими точками для получения меры множества, равной ;7) составляем задачу (1.38) — (1.39), являющуюся при каждом наборе булевых переменных , = 1, , задачей линейного программирования;8) используя метод ветвей и границ, определяем оптимальный набор булевых переменных , = 1, , при котором значение критерия в получаемой задаче линейногопрограммирования будет минимально;9) осуществляем поиск субоптимальной стратегии ¯ и оценки квантили ¯ .Сложности при реализации алгоритма могут возникнуть при моделирование плотности () распределения -мерного случайного вектора с зависимыми компонентами.В этом случае требуется воспользоваться разложением плотности распределения в произведение условных вероятностей.

Последующая техника моделирования изложена в работеA.В. Войтишека [11]. Также можно воспользоваться методом аппроксимации плотности вероятности некоторой кусочно-постоянной функцией. Полученную плотность можно моделить в плане получения реализаций.38Основной трудоёмкостью данного алгоритма является применение метода ветвей играниц, верхняя оценка сложности которого согласно монографии Ю.Ю. Финкельштей√на [67] имеет порядок 2 / , определяемый количеством рассматриваемых в процессе решения подзадач.