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

Двухэтапная задача (1.19) в апостериорной постановке эквивалентна в смысле определения 1.1 двухэтапной задаче (1.16) в априорной постановке.Доказательство теоремы 1.2. В основу доказательства данной теоремы положеноиспользование доверительного метода. Суть данного метода заключается в оценке истинного значения функции квантили с помощью некоторой верхней границы, представляющейсобой доверительную оценку. Такая оценка является функцией максимума на некоторомдоверительном множестве.

Поэтому исходная задача минимизации функции квантили может быть заменена минимаксной задачей, решение которой можно получить аналитическиили численно. При этом в минимаксной задаче предполагается оптимизация доверительного28множества для получения улучшенной доверительной оценки функции квантили. Даннаяидея была впервые предложена в работах А.И.

Кибзуна, А.А. Лебедева, В.В. Малышева [27]и А.И. Кибзуна и В.В. Малышева [28] применительно к задаче минимизации функции квантили. В указанных работах данный метод был назван обобщённым минимаксным подходом. Дальнейшие исследования данного подхода, позволившие выделить некоторые классызадач, для которых удаётся сразу предложить «хорошее» доверительное множество илиосуществить его замену другим множеством, отражены в монографиях В.В. Малышева иА.И. Кибзуна [49], А.И. Кибзуна и Ю.С. Кана [117] и в работах А.И.

Кибзуна, В.В. Малышева и К.А. Карпа [118] и Ю.С. Кана [108]. Для таких задач уже не требуется оптимизациядоверительного множества, поэтому в монографиях А.И. Кибзуна и Ю.С. Кана [25, 117]обобщённый минимаксный подход был переименован в доверительный метод.ΔПусть – доверительное множество, то есть () ≥ и ℱ = { : () ≥ } — семейство доверительных множеств уровня . Согласно доверительному методу двухэтапныезадачи (1.16) и (1.19) эквивалентны следующим обобщённым минимаксным задачам, записанным при условии существования решений задач (1.16) и (1.19).

В случае, если одна иззадач (1.16) или (1.19) не имеет допустимых решений, то по определению 1.1 эквивалентнаяей задача также не имеет допустимых решений.Запишем согласно монографии А.И. Кибзуна и Ю.С. Кана [25] эквивалентные обобщённые минимаксные задачи для двухэтапных задач (1.16) и (1.19):Δ =minΔmin (, , (·)), ( , , (·)) = arg∈ℱ , ∈ (·)∈min(, , (·))(1.20)∈ℱ ,∈ ,(·)∈при ограничениях0 ≥ sup[3 () − (, ) − 2 ()],(1.21)∈где sup в неравенстве (1.21) понимается построчно и функция (, , (·)), стоящая подзнаком минимума в выражении (1.20), имеет вид:ΔTT(, , (·)) = T0 + sup[1 () + 1 (, )],(1.22)∈а такжеΔΔ¯ = min min ¯ (, ), (¯ , ¯ ) = arg∈ℱ ∈min∈ℱ ,∈¯ (, ),(1.23)где функция, стоящая под знаком минимума в выражении (1.23) представима в виде:ΔTT¯ (, ) = T0 + sup[1 () + min{1 |2 () + (, ) ≥ 3 ()}].∈∈(1.24)29Отметим, что здесь пара ( , ) — оптимальное решение задачи (1.16), а (¯ , ¯ ) —оптимальное решение задачи (1.19), причем задача (1.16) эквивалентна в смысле приведённого в разделе 1.2 определения 1.1 задаче (1.20), а задача (1.19) — задаче (1.23).

Поэтомудля доказательства эквивалентности двухэтапной задачи (1.16) стохастического программирования в априорной постановке и двухэтапной задачи (1.19) в апостериорной постановкесогласно монографии А.И. Кибзуна и Ю.С. Кана [25] достаточно показать, что эквивалентны задачи (1.20) и (1.23). Для доказательства данного утверждения достаточно показать,что для любого доверительного множества ∈ ℱ из семейства доверительных множеств истратегии первого этапа ∈ выполняются равенства(, , (·)) = (, , ¯ (·)) = ¯ (, ),(1.25)где под (, ) понимаются оптимальные стратегии второго этапа, а именно:¯ (, ) = arg min{T1 |2 () + (, ) ≥ 3 ()}, ∈ IR , ∈ IR ,∈(1.26) (·) — измеримая по Борелю функция.Заметим, что согласно (1.24) и (1.22) выполняется равенство ¯ (, ) = (, , ¯ (·)).Теперь покажем, что верно равенство (, , (·)) = (, , ¯ (·)).

С этой целью рассмотрим следующую задачуΔΔ(, , (·)) = min (, , (·)); (·) = arg min (, , (·))(·)∈(1.27)(·)∈при ограничениях (1.21). Рассмотрим три случая: первый, когда величина (, , (·)) равняется +∞, второй, когда ¯ (, ) = +∞, и третий, когда обе эти величины меньше +∞.Случай 1.Пусть (, , (·)) = +∞ и не существует плана (·) ∈ второго этапа такого, чтовыполняются ограничения (1.21). Покажем, что при данном предположении также выполняется равенство ¯ (, ) = +∞.Пусть это не так, то есть ¯ (, ) ̸= +∞. Тогда при фиксированных стратегиях первого этапа и доверительном множестве для всех реализаций ∈ случайного вектора, принадлежащих доверительному множеству , существует оптимальный план второгоэтапа ¯ (, ) в задаче (1.26). Это означает, что величина ¯ (·) принадлежит множеству допустимых планов второго этапа, то есть ¯ (·) ∈ .

При этом выполняется неравенство¯ (, ) < +∞ и ограничения в задаче (1.26) выполнены для всех реализаций ∈ . Тоесть для ¯ (·) выполнены ограничения (1.21) обобщённой минимаксной задачи (1.20). Сле-30довательно, ¯ (·) есть допустимый план в задаче (1.20) и при этом выполняется неравенство (, , ¯ (·)) < +∞. Это противоречит выдвинутому предположению, следовательно,¯ (, ) = +∞.Случай 2.Предположим, что (, ) = +∞ и существует реализация ∈ такая, что не существует плана ∈ второго этапа, удовлетворяющего ограничениям в задаче (1.26).

Покажем, что тогда выполняется (, , (·)) = +∞.Пусть это не так, тогда существует измеримая функция (·) ∈ с значениями в такая, что выполнены ограничения (1.21). Следовательно, для этой функции (·) выполненыограничения 0 ≥ 3 () − (, ) − 2 () для всех реализаций ∈ . Таким образом, дляΔвсех ∈ существует план второго этапа = (, ) ∈ . Это противоречит выдвинутомупредположению, что (, ) = +∞. Следовательно, (, , (·)) = +∞.Случай 3.Пусть для фиксированной стратегии ∈ первого этапа и доверительного множества ∈ ℱ для каждой реализации ∈ существуют оптимальные планы (·), (·) вторыхэтапов в задачах (1.27) и (1.26) соответственно.

Тогда выполняются неравенства0 ≥ sup[3 () − (, ) − 2 ()]∈и2 () + (, ) ≥ 3 () для всех ∈ .Таким образом, (·) является допустимым планом для задачи (1.27), но не обязательнооптимальным, то есть (, , (·)) ≤ (, , (·)).Предположим, что (, , (·)) < (, , (·)). ТогдаTsup[T1 () + {1 (, )|2 () + (, ) ≥ 3 ()}] <∈T< sup[T1 () + {1 (, )|2 () + (, ) ≥ 3 ()}].∈Это противоречит предположению о том, что для каждой реализации ∈ IR случайного вектора план (, ) является оптимальным в задаче второго этапа (1.26). Поэтому(, , (·)) ≥ (, , (·)).Объединяя полученные соотношения, получаем, что они непротиворечивы только вслучае равенства (, , (·)) = (, , (·)).Ранее было показано, что (, , (·)) = (, ). Таким образом, равенства (1.25) выполнены.31Теорема 1.2 доказана.

2Доказательство эквивалентности двухэтапных задач стохастического программирования в априорной и апостериорной постановке рассматривалось в работе А.И. Кибзуна иА.В. Наумова [35]. Однако в диссертационной работе рассматривается более общий случайдвухэтапной задачи (1.14) — (1.17), чем в указанной работе, в частности, матрица 2 () ивектор 3 () могут зависеть от случайного вектора . Схема доказательства эквивалентности двухэтапных задач стохастического программирования в апостериорной и априорнойпостановках осталась прежней. Она основана на применении доверительного метода, в соответствии с которым задачи квантильной оптимизации в априорной и апостериорной постановках оказываются эквивалентными в смысле определения 1.1 некоторым обобщённым минимаксным задачам. Далее, в свою очередь, устанавливается эквивалентность между этимиминимаксными задачами.

Таким образом, используя свойство транзитивности понятия эквивалентности, устанавливается эквивалентность между рассматриваемыми двухэтапнымизадачами в априорной и апостериорной постановках. Напомним, что метод динамического программирования для многоэтапной задачи квантильной оптимизации в общем случаенеприменим. Но в частном случае двухэтапная задача квантильной оптимизации в априорной постановке оказывается эквивалентной задаче в апостериорной постановке, то есть вэтом случае метод динамического программирования применим.321.4.Сведение двухэтапной задачи в апостериорной постановке к задачесмешанного целочисленного линейного программированияВ данном разделе рассматривается процедура сведения двухэтапной задачи стохастического программирования с квантильным критерием в априорной постановке для случаядискретного распределения специального вида к задаче смешанного целочисленного линейного программирования.

Для этого применяется переход к двойственным переменным с последующим введением булевых переменных, характеризующих принадлежность реализациислучайного вектора некоторому доверительному множеству.Согласно доверительному методу, изложенному в монографии А.И. Кибзуна иЮ.С. Кана [25], суть которого была приведена в предыдущем разделе, задача (1.19) эквивалентна в смысле определения 1.1 следующей задаче:T = min min {T0 + sup[1 () + Φ(, )]},∈ ∈ℱ( , ) = argmin∈,∈ℱ∈{T0+sup[T1 ()∈(1.28)+ Φ(, )]},где задача второго этапа Φ(, ) определяется согласно (1.18), ∈ ℱ – доверительное мноΔ˜жество из семейства доверительных множеств ℱ = { ∈ ℱ : ()≥ }, ℱ — борелевскаясигма-алгебра, вероятностная мера ˜ соответствует дискретизированному распределению˜вектора .Зафиксируем доверительное множество ∈ ℱ и рассмотрим подзадачу из (1.28)T() = min{T0 + sup[1 () + Φ(, )]},∈(1.29)∈где Φ(, ) находится из решения задачи (1.18).Для подзадачи (1.18) запишем согласно теории двойственности, изложенной в монографии Е.Г.