Автоматика и телемеханика, № 6, 2019

Стохастические системы

А.И. КИБЗУН, д-р физ.-мат. наук (kibzun@mail.ru)

(Московский авиационный институт

(национальный исследовательский университет))

ОБЩИЕ СВОЙСТВА ДВУХЭТАПНЫХ ЗАДАЧ СТОХАСТИЧЕСКОГО

ПРОГРАММИРОВАНИЯ С ВЕРОЯТНОСТНЫМИ КРИТЕРИЯМИ¹

Рассматриваются двухэтапные задачи стохастического программиро-

вания с вероятностным и квантильным критериями в общей постановке.

Приводятся достаточные условия измеримости функции потерь и полу-

непрерывности критериальных функций. Сформулированы достаточные

условия существования оптимальных стратегий. Доказывается эквива-

лентность априорной и апостериорной постановок изучаемых задач. Опи-

сывается и обосновывается применение доверительного метода, заклю-

чающегося в переходе к детерминированной минимаксной задаче. Стро-

ятся выборочные аппроксимации задач и приводятся условия сходимо-

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

стратегии в исходной задаче. Полученные результаты иллюстрируются на

примере линейной двухэтапной задачи. Двухэтапная задача с вероятност-

ным критерием сводится к смешанной целочисленной задаче.

Ключевые слова: стохастическое программирование, двухэтапная задача,

вероятностный критерий, квантильный критерий.

DOI: 10.1134/S0005231019060047

1. Введение

Двухэтапные задачи стохастического программирования описывают ши-

рокий класс экономических и технических систем, в которых процедура при-

нятия решения осуществляется последовательно на двух этапах. На первом

этапе выбирается детерминированная стратегия. На втором этапе по факту

реализации случайных параметров выбирается стратегия второго этапа.

Линейные двухэтапные задачи с критерием в форме математического ожи-

дания широко освещены в [1-5], где описаны свойства выпуклости множества

допустимых стратегий и целевой функции, описаны подходы к построению

эквивалентной детерминированной задачи и приведены различные методы

решения задачи. Общая постановка двухэтапной задачи с критерием в фор-

ме математического ожидания описана в [4, 6, 7].

Помимо критерия в форме математического ожидания, в стохастическом

программировании рассматриваются вероятностные критерии. Наиболее из-

вестными из них являются вероятностный и квантильный критерии, а также

¹ Работа поддержана Российским фондом фундаментальных исследований (проект

№ 17-07-00203А).

критерий в форме интегральной квантили [8, 9]. Вероятностный критерий

представляет собой вероятность непревышения функцией потерь некоторо-

го фиксированного уровня. Квантильный критерий (также известный как

Value-at-Risk) является минимальным уровнем функции потерь, непревыше-

ние которого гарантируется с заданной вероятностью. Критерий в форме ин-

тегральной квантили отображает средние потери при превышении целевой

функции значения квантили.

Двухэтапные задачи с вероятностными критериями менее изучены, чем с

критерием в форме математического ожидания. Двухэтапная линейная зада-

ча с квантильным критерием была сформулирована в [10], где были предло-

жены методы поиска верхней оценки критериальной функции задачи. Двух-

этапная линейная задача с критерием в форме интегральной квантили изу-

чалась в [11], где были исследованы свойства задачи и предложен алгоритм

ее решения. В настоящей статье изучаются двухэтапные задачи стохасти-

ческого программирования с вероятностным и квантильным критериями в

общей постановке. Двухэтапные задачи с квантильным критерием в случае

дискретного распределения случайных параметров изучались в [12], где пред-

ложен подход к их сведению к детерминированным задачам смешанного це-

лочисленного программирования. Ранее подобные методы были предложе-

ны для задач стохастического программирования с вероятностными ограни-

чениями [13-16]. Среди прикладных задач, описываемых с помощью двух-

этапных оптимизационных моделей с квантильным критерием, можно отме-

тить логистическую задачу оптимизации бронируемого фрахта компанией,

занимающейся доставкой грузов [17], и задачу оптимизации энергоснабжения

участка железной дороги [18]. В данных задачах оптимизация осуществля-

ется за счет выбора на первом этапе объемов приобретаемых ресурсов и их

последующей корректировки на втором этапе в зависимости от реализации

случайного спроса.

Традиционно рассматриваются двухэтапные задачи в априорной поста-

новке. Это значит, что при принятии решения на первом этапе учитывается

минимальное значение целевой функции второго этапа как функции страте-

гии первого этапа. Также могут быть рассмотрены двухэтапные задачи стоха-

стического программирования в апостериорной постановке, когда стратегией

второго этапа является функция реализации случайных параметров задачи.

Условия эквивалентности априорной и апостериорной постановок двухэтап-

ной задачи с критерием в форме математического ожидания приведены в [4],

в [10] доказана эквивалентость данных постановок для линейной задачи с

квантильным критерием. В настоящей статье показывается эквивалентность

априорной и апостериорной постановок двухэтапных задач с вероятностными

критериями в общей постановке.

В статье демонстрируются два подхода к решению сформулированных за-

дач: доверительный метод и метод выборочных аппроксимаций. Для задач

с квантильным критерием может быть применен доверительный метод, за-

ключающийся в переходе от исходной задачи к эквивалентной детермини-

рованной минимаксной задаче. Данный метод сформулирован в [8, 9], но он

был обоснован только для целевых функций, принимающих конечные значе-

ния. В настоящей статье обосновывается применение доверительного метода

в случае возможности бесконечных значений целевых функций. Это позво-

ляет его применять для решения двухэтапных задач, в которых функция по-

терь определяется как оптимальное значение целевой функции второго этапа

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

задачи второго этапа.

Метод выборочных аппроксимаций заключается в построении выборочных

оценок критериальных функций и их дальнейшей оптимизации. Для задач

стохастического программирования с критерием в форме математического

ожидания данный метод был обоснован в [19], а для задач с вероятностными

ограничениями — в [20]. Допустимость в задачи стохастического программи-

рования решений аппроксимирующей задачи изучалась в [21]. В [22] метод

выборочных аппроксимаций применяется совместно с декомпозиционными

алгоритмами для двухэтапных линейных задач с критерием в форме мате-

матического ожидания. В статье авторов [23] метод обосновывается для од-

ноэтапных задач с вероятностными критериями. В настоящей статье метод

применяется для двухэтапных задач с вероятностными критериями в общей

постановке.

В качестве примера в статье рассматривается линейная двухэтапная за-

дача стохастического программирования для вероятностного и квантильного

критериев.

2. Постановки задач

Сформулируем сначала двухэтапные задачи оптимизации с вероятностны-

ми критериями в апостериорной постановке.

Пусть задано вероятностное пространство (X , F, P), где X ⊂ R^m — некото-

рое замкнутое множество. Пусть X — случайный вектор с значениями в R^m,

определенный на вероятностном пространстве (X , F, P). Будем считать, что

вероятностное пространство является полным, т.е. любое подмножество мно-

жества вероятностной меры нуль содержится в сигма-алгебре F. Например,

можно взять лебегову сигма-алгебру в качестве сигма-алгебры F. Будем

предполагать, что для всех x ∈ X выполнено X(x) = x, т.е. P{X ∈ B} = P(B)

для любого борелевского множества B ⊂ R^m.

Через U ⊂ R^r обозначим множество стратегий первого этапа. Множество

стратегий второго этапа обозначим через Y ⊂ R^s. Стратегия первого эта-

па u ∈ U выбирается, когда реализация случайного вектора X неизвест-

на, а стратегия второго этапа y ∈ Y

— по реализации случайного векто-

ра X. Будем считать, что множества U и Y являются замкнутыми. Пусть

Φ₂(·): U × Y × X → R∗ — функция потерь второго этапа, где R∗ ≜ R1 ∪

∪ {-∞} ∪ {+∞} — расширенная действительная прямая.

Целевая функция потерь Φ(·): U × X → R^∗ определяется как минималь-

ное значение функции потерь второго этапа при известных стратегии первого

этапа u ∈ U и реализации случайных факторов x ∈ X :

(1)

Φ(u, x) ≜ inf

{Φ₂

(u, y, x) | Q(u, y, x) ≤ 0},

y∈Y

где Q(·): U × Y × X → R^∗ — функция, задающая дополнительные ограниче-

ния задачи второго этапа. Если при заданных (u, x) ∈ U × X для всех y ∈ Y

выполнено Q(u, y, x) > 0, то по определению полагается Φ(u, x) = +∞.

Замечание 1. Введенное определение функции потерь позволяет без

ограничения общности считать, что U = R^r, а Y = R^s. В случае если, напри-

мер, U = R^r, можно положить Φ₂(u, y, x) = +∞ для всех u ∈ U, поскольку по

определению функция Φ₂(·) принимает значения из расширенной действи-

тельной прямой.

Замечание 2. Введенная функция потерь определена на множестве реа-

лизаций случайного вектора X. По этой причине можно отождествить ис-

ходное вероятностное пространство и пространство реализаций случайного

вектора, снабженное борелевской сигма-алгеброй. Известно, что борелевская

сигма-алгебра не является полной. Причины, по которым целесообразно рас-

сматривать полное вероятностное пространство, будут объяснены далее. От-

метим, что в более общей постановке задачи функция потерь может зависеть

непосредственно от элементарного события. Многие результаты статьи мо-

гут быть обобщены на этот случай, но его детальное рассмотрение выходит

за рамки статьи.

Определим функцию вероятности P_ϕ(·): U → [0, 1] так:

(2)

P_ϕ

(u) ≜ P{Φ(u, X) ≤ ϕ},

где ϕ ∈ R^∗ — фиксированный уровень функции потерь. Таким образом,

P_ϕ(u) — вероятность такого события, что значение функция потерь Φ(u,X)

не превысит фиксированный порог ϕ.

Пусть задан уровень надежности α ∈ (0, 1]. Введем в рассмотрение функ-

цию квантили ϕ_α(·): U → R^∗, определенную по правилу

(3)

ϕα(u) ≜ min{ϕ ∈ R^∗ | Pϕ(u) ≥ α}.

Функция квантили — это минимальный уровень потерь, который не будет

превышен с заданной вероятностью α.

Замечание 3. Заметим, что из-за наличия ограничения Q(u,y,x) ≤ 0

при некоторых u ∈ U может оказаться, что P_ϕ(u) < α для всех ϕ ∈ R¹. Поэто-

му если для всех ϕ ∈ R¹ выполнено P_ϕ(u) < α, то по определению полагаем,

что ϕ_α(u) = +∞.

Замечание 4. В определении (2) предполагается, что функция x →

→ Φ(u,x) является измеримой. Достаточные условия измеримости данной

функции будут приведены далее.

Будем рассматривать задачу максимизации функции вероятности

(4)

α^∗ϕ ≜ sup

P_ϕ(u), U^∗ϕ ≜ Arg maxPϕ

(u)

u∈U

и задачу минимизации функции квантили

(5)

ϕ∗α ≜ inf

ϕα(u), U^α ≜ Arg min

ϕα

(u).

u∈U

Множества U^∗ϕ и U^∗α будем называть множествами оптимальных стратегий

в соответствующих задачах. Если ϕ^∗α = +∞, то, как принято в теории оп-

тимизации, будем считать, что множество U^∗α пусто. Допустимой стратегией

в задаче минимизации функции квантили будем называть такую стратегию

u ∈ U, что ϕ_α(u) = +∞. Задачи (4) и (5) сформулированы в апостериорной

постановке, т.е. оптимальная стратегия второго этапа y ∈ Y выбирается при

уже известных стратегии первого этапа u ∈ U и реализации случайных па-

раметров x ∈ X .

3. Свойства задачи

Для того чтобы задачи (4) и (5) были сформулированы корректно, необ-

ходима измеримость целевой функции потерь x → Φ(u, x). Для исследова-

ния данного вопроса может быть применена теория нормальных интегран-

тов [24, 25].

В случае полной сигма-алгебры F можно дать следующее определение

нормального интегранта.

Определение 1. Функция f(·): R^r × X → R^∗ называется нормальным

интегрантом, если f(·) является B(R^r) × F-измеримой и для всех x ∈ X

функция u → f(u, x) полунепрерывна снизу.

Здесь и далее через B(R^r) × F обозначено произведение борелевской

сигма-алгебры B(R^r) и сигма-алгебры F. Определение нормального инте-

гранта для произвольной (вообще говоря, неполной) сигма-алгебры F слож-

нее и дается в терминах измеримости многозначных отображений [25].

Напомним определение полунепрерывной функции.

Определение 2. Функция f(·): R^r → R^∗ называется полунепрерывной

снизу (сверху), если все ее нижние (верхние) множества уровня

(6)

{u ∈ R^r | f(u) ≤ a}

({u ∈ R^r

: f(u) ≥ a})

замкнуты для всех a ∈ R^∗.

Известно следующее утверждение.

Теорема 1

[25, теорема 14.37]. Пусть функция f(·): R^r × X → R^∗ явля-

ется нормальным интегрантом,

a(x) ≜ inf

f (u, x), A(x) ≜ Arg min f(u, x).

u∈R^r

Тогда функция x → a(x) измерима. При этом множество B =

= {x ∈ X | A(x) = ∅} измеримо, а также для каждого x ∈ B можно

выбрать точку минимума u(x) ∈ A(x) такую, что функция x → u(x)

измерима.

Сформулируем достаточные условия измеримости целевой функции по-

терь x → Φ(u, x).

Теорема 2. Пусть для каждого u ∈ U функции (y,x) → Φ₂(u,y,x) и

(y, x) → Q(u, y, x) являются нормальными интегрантами. Тогда для всех

u ∈ U функция x → Φ(u,x) является измеримой.

Доказательство теоремы 2 и всех последующих теорем вынесено в Прило-

жение.

Замечание 5. Отметим, что в случае неполной сигма-алгебры F при по-

лунепрерывности по стратегии и измеримости по совокупности аргументов

функций (y, x) → Φ₂(u, y, x) и (y, x) → Q(u, y, x) нельзя гарантировать изме-

римость функции x → Φ(u, x) относительно F. Поэтому в случае борелевских

функций (y, x) → Φ₂(u, y, x) и (y, x) → Q(u, y, x) функция x → Φ(u, x) может

не быть борелевской, но будет измеримой по Лебегу.

Далее приведем условия того, что минимум в (1) является нормальным

интегрантом. Для этого понадобится следующее определение.

Определение 3

[25, определение 1.16]. Говорят, что функция f(·):

: R^r × R^s → R^∗ с значениями f(u,y) обладает ограниченными множествами

уровня, причем локально-равномерно по u, если для любых ũ ∈ R^r и a ∈ R¹

существует открытое множество V ⊂ R^r, содержащее точку ũ, такое,

что множество {(u, y) | u ∈ V, f(u, y) ≤ a} ограничено в R^r × R^s.

Очевидно, что условия определения 3 выполнены для ограниченного мно-

жества Y допустимых значений y.

Справедливо следующее утверждение.

Теорема 3

[25, утверждение 14.47]. Пусть функция g(·): (R^r × R^s)×

×X → R^∗ является нормальным интегрантом,

f (u, x) = inf g(u, y, x).

y∈R^s

Если для всех x ∈ X функция u → f(u, x) полунепрерывна снизу, то функ-

ция f(·) является нормальным интегрантом.

Замечание 6. Как отмечено в [25], условия теоремы 3 выполнены, на-

пример, когда для всех x ∈ X нормальный интегрант (u, y) → g(u, y, x) об-

ладает ограниченными множествами уровня, причем локально-равномерно

по u.

Из данной теоремы следует утверждение.

Теорема 4. Пусть функция потерь (u,y,x) → Φ₂(u,y,x) является нор-

мальным интегрантом и при каждом x ∈ X функция (u, y) → Φ₂(u, y, x) об-

ладает ограниченными множествами уровня, причем локально-равномерно

по u, функция (u,y,x) → Q(u,y,x) — нормальный интегрант. Тогда функция

потерь (u,x) → Φ(u,x) является нормальным интегрантом.

Сформулируем утверждения о полунепрерывности функций вероятности

и квантили. Известен следующий результат.

Теорема 5

[9, теорема 2.2]. Если U — замкнутое подмножество R^r,

функция потерь (u, x) → Φ(u, x) принимает только конечные значения, по-

лунепрерывна снизу по u ∈ U для почти всех x по мере P и измерима по x

для всех u ∈ U, то для любого ϕ ∈ R¹ функция u → P_ϕ(u) полунепрерывна

сверху по u ∈ U, а функция u → ϕ_α(u) полунепрерывна снизу по u ∈ U для

любого α ∈ (0, 1).

Аналогичный результат сформулирован в [8, лемма 2.11].

Основываясь на теореме 5, докажем следующий результат.

Теорема 6. Пусть функция (u,x) → Φ(u,x) является нормальным ин-

тегрантом. Тогда функция вероятности u → P_ϕ(u) является полунепрерыв-

ной сверху для всех ϕ ∈ R^∗, а функция квантили u → ϕ_α(u) — полунепрерыв-

ной снизу для всех α ∈ (0,1].

Из теоремы 6 получаем утверждение о существовании оптимальных стра-

тегий в задачах (4) и (5).

Следствие 1. Пусть множество U является компактом, функции

(u, y, x) → Φ₂(u, y, x) и (u, y, x) → Q(u, y, x) являются нормальными инте-

грантами и при каждом x ∈ X функция (u, y) → Φ₂(u, y, x) обладает огра-

ниченными множествами уровня, причем локально-равномерно по u. Тогда

для всех ϕ ∈ R^∗ множество U^∗ϕ задачи максимизации функции квантили

непусто. Если существует точка u ∈ U, в которой ϕ_α(u) < +∞, то и мно-

жество U^∗α непусто.

4. Об эквивалентности априорной и апостериорной постановок задач

Теперь сформулируем двухэтапные задачи стохастического программиро-

вания с вероятностными критериями в априорной постановке.

Через Y обозначим множество (F, B(Y ))-измеримых функций. Для фик-

сированного ϕ ∈ R^∗ определим функционал вероятности P_ϕ(·): U ×Y → [0, 1]

по правилу

P_ϕ(u,y(·)) ≜

{

P{Φ₂(u, y(X), X) ≤ ϕ, Q(u, y(X), X)) ≤ 0}, если ϕ < +∞,

(7)

≜

если ϕ = +∞,

{

}

Φ₂(u,y(X),X) + δ[-∞,0](Q(u,y(X),X)) ≤ ϕ

где

{

если q ∈ A;

δ_A(q) =

+∞,

если q ∈ A.

Поскольку для всех u ∈ U функции (y, x) → Φ₂(u, y, x), (y, x) → Q(u, y, x)

и x → y(x) являются измеримыми, то функции x → Φ₂(u,y(x),x) и x →

→ Q(u,y(x),x)) являются измеримыми для всех u ∈ U как композиции из-

меримых отображений, а значит, и функция

(8)

x → Φ₂(u,y(x),x) + δ[-∞,0]

(Q(u, y(x), x))

измерима. Таким образом, определение (7) является корректным при указан-

ных предположениях.

Для фиксированного уровня вероятности α ∈ (0, 1] определим функционал

квантили

ϕα(u, y(·)): U × Y → R^∗ по правилу

{

}

(9)

ϕα(u, y(·)) ≜ min

ϕ ∈ R^∗ | P_ϕ(u,y(·)) ≥ α

Будем рассматривать задачу максимизации функционала вероятности

(10)

P_ϕ(u,y(·)) → sup

u∈U, y(·)∈Y

и задачу минимизации функционала квантили

(11)

ϕα(u, y(·)) →

inf

u∈U, y(·)∈Y

Сформулируем утверждение об эквивалентности задач (4) и (10), а также

(5) и (11).

Теорема 7. Пусть для каждого u ∈ U функция потерь (y,x) →

→ Φ₂(u,y,x) является нормальным интегрантом и для всех x ∈ X облада-

ет ограниченными множествами уровня по y, функция (y,x) → Q(u,y,x) —

нормальный интегрант. Тогда для любого u ∈ U выполнено:

(12)

P_ϕ(u) = max P_ϕ

(u, y(·)),

y(·)∈Y

(13)

ϕα(u) = min

ϕα

(u, y(·)).

y(·)∈Y

5. Применение доверительного метода

Введем функцию Ψ(·): U × F → R^∗ по правилу

(14)

Ψ(u, S) ≜ sup Φ(u, x) = sup

inf

{Φ₂

(u, y, x) | Q(u, y, x) ≤ 0}.

x∈S

y∈Y

Рассмотрим минимаксную задачу

(15)

Ψ(u, S) → inf

u∈U, S∈Fα

где F_α ≜ {S ∈ F | P{S} ≥ α}. Множества из семейства F_α называются дове-

рительными.

В [9] показано, что для одноэтапной задачи стохастического программиро-

вания с квантильным критерием минимаксная задача вида (15) эквивалентна

задаче вида (5). Метод сведения задачи квантильной минимизации к мини-

максной задаче назван в [8, 9] доверительным методом. Покажем, что этот

метод применим и для двухэтапной задачи квантильной оптимизации.

Теорема 8. Пусть для каждого u ∈ U функции (y,x) → Φ₂(u,y,x) и

(y, x) → Q(u, y, x) являются нормальными интегрантами. Тогда

(16)

ϕα(u) = min

Ψ(u, S).

S∈Fα

Заметим, что решение задачи

(17)

Ψ(u, S) → inf

u∈U

для фиксированного множества S обеспечивает верхнюю оценку оптималь-

ного значения функции квантили в задаче (5). Если функция u → Φ(u, x)

выпукла для всех x ∈ X , то задача (17) является задачей выпуклой оптими-

зации.

6. Исследование выборочных аппроксимаций задачи

Рассмотрим последовательность {X_k}∞k=1 независимых случайных векто-

ров, распределения которых совпадают с распределением случайного век-

тора X. Согласно теореме Колмогорова [26, гл. 2, § 3, теорема 3] такая по-

следовательность всегда существует и может быть определена на вероятност-

ном пространстве (X^∞, F^′, P^′). Процедура построения данного вероятностно-

го пространства описана в доказательстве теоремы Колмогорова [26]. В каче-

стве пространства элементарных событий рассматривается пространство X^∞

реализаций последовательности {X_k}∞k=1. Сигма-алгебра F^′ строится как бес-

конечное произведение сигма-алгебр F, а вероятностная мера P^′ согласована

с вероятностной мерой P, т.е. для всех последовательностей борелевских мно-

жеств {B_k}∞k=1 и всех n ∈ N справедливо равенство

(

)

⋂

∏

(18)

P′

{X_k ∈ B_k}

= P{X ∈ B_k

k=1

Конечно, последовательность {X_k}∞k=1 можно определять и на другом веро-

ятностном пространстве, если это возможно.

Построим оценки функции вероятности

∑

(19)

P(n)ϕ(u) ≜

χ[-∞,ϕ](Φ(u,X_k

)), n ∈ N,

k=1

где

{

1, если q ∈ A;

(20)

χ_A(q) ≜

0, если q ∈ A,

и ф ункции квантили

{

}

(21)

ϕ(n)α(u) ≜ min ϕ ∈ R^∗ | P(n)ϕ(u)

≥ α, n ∈ N.

Рассмотрим задачи оптимизации:

(22)

α_n ≜ sup

P(n)ϕ(u), U(n)ϕ ≜ Arg minP(n)ϕ

(u),

u∈U

(23)

ϕn ≜ inf

ϕ(n)α(u), U(n)α ≜ Arg minϕ(n)α

(u).

u∈U

Справедлива следующая теорема [23].

Теорема 9

[23, теорема 7]. Пусть функция (u, x) → Φ(u, x) является

нормальным интегрантом, множество U компактно и непусто. Тогда

(24)

lim

α_n = sup P_ϕ(u) (P^′

-п.н.) (п.н. — почти наверное)

n→∞

u∈U

и любая предельная точка u^ϕ последовательности {uⁿ}n∈N, в которой для

всех n ∈ N выполнено uⁿ ∈

, оптимальна в задаче (4) P^′-п.н., т.е.

(25)

u^ϕ ∈ Arg maxPϕ(u) (P′

-п.н.).

u∈U

Из теоремы 9 получаем следствие 2.

Следствие 2. Пусть функции (u,y,x) → Φ₂(u,y,x) и (u,y,x) →

→ Q(u,y,x) являются нормальными интегрантами и при всех x ∈ X

функция (u, y) → Φ₂(u, y, x) обладает ограниченными множествами уровня,

причем локально-равномерно по u, множество U компактно и непусто.

Тогда выполнены соотношения (24) и (25).

Для задачи стохастического программирования с квантильным критерием

справедлив следующий результат, аналогичный теореме 9.

Теорема 10. Пусть выполнены условия:

(i) множество U компактно и непусто;

(ii) функция (u, x) → Φ(u, x) является нормальным интегрантом и

Φ(u, x) > -∞ для всех (u, x) ∈ U × X ;

(iii) если ϕ^∗α = +∞, то для всех ε > 0 существует пара (ũ,

ϕ) такая, что

ϕ-ϕ^∗α|≤ε и

ϕ(ũ) > α.

Тогда lim_n→∞ ϕ_n = ϕ^∗α (P^′-п.н.) и если ϕ^∗α = +∞, то любая предельная

точка u последовательности {u_n}n∈N, в которой u_n ∈

α для всех доста-

точно больших n ∈ N, оптимальна в задаче (5) (P^′-п.н.).

Замечание 7. Утверждается, что для всех достаточно больших n ∈ N

выполнено u_n ∈

α по той причине, что в случае ϕn = +∞ множество стра-

тегий в аппроксимирующей задаче считается пустым. Если ϕ^∗α < +∞, то из

сходимости lim_n→∞ ϕ_n = ϕ^∗α (P^′-п.н.) следует, что существует номер N ∈ N,

такой что для всех n > N выполнено ϕ_n < +∞, а значит, множество опти-

мальных стратегий

α в аппроксимирующей задаче становится непустым

начиная с номера N. Конечно, N зависит от реализации выборки, но номер N

определен для почти всех реализаций выборки.

Замечание 8. Условие (iii) выполнено, например, в том случае, когда

при всех u ∈ U функция ϕ → P_ϕ(u) является строго возрастающей. Тогда

указанное неравенство выполняется при ũ = u^∗ и

ϕ = ϕ^∗α + ε/2. Условия мо-

нотонности функции вероятности можно найти в [9].

7. Линейные двухэтапные задачи

Проиллюстрируем полученные в статье результаты на примере линей-

ных двухэтапных задач стохастического программирования с вероятностны-

ми критериями. Данный класс задач с квантильным критерием был введен

в [10], где для частного случая линейной задачи доказана эквивалентность

априорной и апостериорной постановок. Распространим этот результат на бо-

лее общий случай. Поиск оптимальной оптимизационной стратегии в данной

задаче затруднителен, поэтому разработан ряд алгоритмов для поиска гаран-

тирующих стратегий в непрерывном [10] и дискретном случае [27]. В [28] для

задачи с квантильным критерием, близкой к рассматриваемой в данном раз-

деле, предложены два алгоритма. Один из них основан на сведении задачи

к задаче смешанного целочисленного программирования, а второй — на све-

дении задачи к последовательности задач выпуклой оптимизации. Данные

алгоритмы используют доверительный метод, однако обоснование его при-

менимости в случае, когда целевые функции могут принимать бесконечные

значения, ранее проведено не было. В данном разделе описан общий под-

ход к использованию доверительного метода для решения задачи в линейном

случае. Построение выборочных аппроксимаций двухэтапной задачи с кван-

тильным критерием в линейном случае подробно описано в [29], где выбороч-

ная аппроксимация вида (23) сведена к задаче смешанного целочисленного

линейного программирования и приведены сходимости решений аппрокси-

мирующих задач к решению исходной задачи. В данном разделе строится

выборочная аппроксимация для аналогичной задачи с вероятностным крите-

рием.

7.1. Измеримость целевой функции и существование решения

Пусть целевая функция потерь имеет вид

{

}

(26)

Φ(u, x) = c^⊤(x)u + inf q^⊤(x)y | A(x)u + B(x)y ≥ b(x)

y∈Y

где Y = {y ∈ R^s | y ≥ 0},

(27)

x = col(c(x),q(x),A(x),B(x),b(x)) ∈ Rr+s+l(r+s+1)

— вектор, составленный из векторов и матриц c(x) ∈ R^r, q(x) ∈ R^s, A(x) ∈

∈ R^l×r, B(x) ∈ R^l×s и b(x) ∈ R^l.

Для функции потерь вида (26) рассмотрим задачу максимизации функции

вероятности (4) и задачу минимизации функции квантили (5).

Функция потерь (26) может быть представлена в форме (1), если

(28)

Φ₂(u,y,x) = c^⊤(x)u + q^⊤

(x)y,

(29)

Q(u, y, x) = - min(A(x)u + B(x)y - b(x))i .

i=1,l

Функции (u, y, x) → Φ₂(u, y, x) и (u, y, x) → Q(u, y, x) непрерывны, поэтому

являются нормальными интегрантами, а значит, по теореме 2 задачи (4) и (5)

сформулированы корректно. Более того, в [5] доказано, что функция

{

}

(30)

u → inf q^⊤(x)y | A(x)u + B(x)y ≥ b(x)

y∈Y

является выпуклой полиэдральной на замкнутом множестве значений u, для

которых множество {y ∈ Y | A(x)u + B(x)y ≥ b(x)} непусто. Таким образом,

функция (30) является полунепрерывной снизу, а значит, согласно теореме 3

функция (u, x) → Φ(u, x) является нормальным интегрантом.

Нормальность интегранта (u, x) → Φ(u, x) в силу теоремы 6 гарантирует

полунепрерывность сверху функции вероятности и полунепрерывность сни-

зу функции квантили, что обеспечивает существование оптимальных страте-

гий в задачах максимизации функции вероятности и минимизации функции

квантили на компактном множестве.

Изучим вопрос эквивалентности априорной и апостериорной постановок

задачи стохастического программирования с вероятностными критериями

для линейной функции потерь. Заметим, что функция потерь (26) в общем

случае не обладает ограниченными множествами уровня. По этой причине

теорема 7 не может быть применена непосредственно. Приведем условия эк-

вивалентности задач (4) и (10).

Теорема 11. Пусть ϕ > -∞. Тогда для функций Φ₂(·) и Q(·) вида (28)

и (29) выполнено равенство

P_ϕ(u) = max P_ϕ(u,y(·)).

y(·)∈Y

При этом если U — непустое компактное множество, то множества оп-

тимальных стратегий в задачах (4) и (10) непусты.

Замечание 9. В случае ϕ = -∞ можно гарантировать лишь оценку

(31)

P_-∞(u) ≥ sup P_-∞

(u, y(·)) ≡ 0

y(·)∈Y

для всех u ∈ U.

Теперь приведем условия эквивалентности задач (5) и (11).

Теорема 12. Пусть функции Φ₂(·) и Q(·) определены согласно

(28)

и (29). Тогда

1) для u ∈ U равенство

ϕα(u) = min

ϕα(u, y(·))

y(·)∈Y

выполнено, если справедливо ϕ_α(u) > -∞;

2) если в некоторой точке u ∈ U выполнено ϕ_α(u) = -∞, то

inf

ϕα(u, y(·)) = -∞,

y(·)∈Y

причем данный инфимум не достигается;

3) в случае компактного множества U оптимальная стратегия в зада-

че (11) существует при ϕ^∗α < +∞.

Замечание 10. В [10] аналогичная теорема доказана для случая, когда

только значение b(X) случайно, а A(X) и B(X) являются детерминирован-

ными.

7.2. Применение доверительного метода

При применении доверительного метода для решения задачи (5) для функ-

ций (28) и (29) выражение (14) примет вид

Ψ(u, S) ≜ sup Φ(u, x) =

x∈S

{

(32)

{

}}

= sup

c^⊤(x)u + inf q^⊤(x)y | A(x)u + B(x)y ≥ b(x)

x∈S

y∈Y

Как следует из теоремы 8, значение Ψ(u, S) при всех допустимых значениях

u и S является верхней оценкой ϕ^∗α. Поэтому при удачном выборе S решение

задачи минимизации функции u → Ψ(u, S) обеспечивает близкое к оптималь-

ному значение критериальной функции.

Преобразуем выражение (14). Если множество {y ∈ Y | A(x)u + B(x)y ≥

≥ b(x)} непусто, то, вводя двойственные переменные v ∈ R^l, можно получить

равенство

{

}

inf q^⊤(x)y | A(x)u + B(x)y ≥ b(x)

y∈Y

(33)

{

}

= sup (b(x) - A(x)u)^⊤v | B^⊤(x)v ≤ b(x), v ≥ 0

v∈R^l

Подставляя (33) в (32) и переставляя супремумы, получаем

{

}

(34) Ψ(u, S) = sup sup c^⊤(x)u + (b(x) - A(x)u)^⊤v | B^⊤(x)v ≤ b(x), v ≥ 0

v∈R^l x∈S

В зависимости от вида задачи представление Ψ(u, S) в форме (34) может

оказаться удобней, чем его исходное определение в форме (32). Например, в

случае многогранного доверительного множества S внутренняя задача мак-

симизации является задачей линейного программирования.

7.3. Построение выборочных аппроксимаций задачи

с вероятностным критерием

Построим выборочную аппроксимацию задачи (4) для функций (28), (29).

Согласно теореме 9 последовательность решений задачи (22) сходится к оп-

тимальному решению задачи (4) как по стратегии, так и по значению крите-

риальной функции.

Рассмотрим задачу (22) при фиксированной реализации {x_k}nk=1 выборки

{X_k}nk=1:

(

)

∑

(35)

χ[-∞,ϕ] c^⊤(x_k)u+ inf

{q^⊤(x_k)y | A(x_k)u + B(x_k)y ≥ b(x_k)}

→ sup .

y∈Y

u∈U

k=1

Докажем, что задача (35) эквивалентна смешанной целочисленной задаче.

Теорема 13. Пусть ϕ ∈ R¹ и множество U непусто и ограничено. То-

гда любая оптимальная стратегия uⁿ в задаче (35) является оптимальным

значением переменной u в задаче

∑

(36)

δ_k →

sup

k=1

u∈U, y₁,...,yn∈Y, δ∈{0,1}ⁿ

при ограничениях

(37)

c^⊤(x_k)u + q^⊤(x_k)y_k ≤ ϕ + L₁(1 - δ_k)

(38)

A(x_k)u + B(x_k)y_k ≥ b(x_k) - L₂(1 - δ_k)e_l,

где e_l — вектор, составленный из l единиц,

L₁ ≥ max sup |c^⊤(x_k)u - ϕ|,

k=1,N u∈U

L₂ ≥ max sup ∥b(x_k) - A(x_k)u∥_∞,

k=1,N u∈U

и любое оптимальное значение u в задаче (36) является оптимальной стра-

тегией в задаче (35).

Замечание 11. В случае когда множество U является выпуклым мно-

гогранником, задача (36) является смешанной целочисленной задачей линей-

ного программирования.

8. Заключение

В статье представлен общий подход к исследованию двухэтапных задач

стохастического программирования с вероятностным и квантильным крите-

риями, показана эквивалентность априорной и апостериорной постановок за-

дачи. Продемонстрировано применение доверительного метода и метода вы-

борочных аппроксимаций. Данные методы могут быть детально проработаны

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

методов, например выпуклого программирования. В дальнейшем планирует-

ся предложенные подходы распространить на такие классы задач стохасти-

ческого программирования, как многоэтапные и двухуровневые задачи.

ПРИЛОЖЕНИЕ

Доказательство теоремы 2. Для доказательства теоремы проверим

условия теоремы 1. Заметим, что целевую функцию потерь при дополнитель-

ном соглашении -∞ + ∞ = +∞ можно представить в виде

{

}

(Π.1)

Φ(u, x) = inf

Φ₂(u,y,x) + δ[-∞,0](Q(u,y,x))

y∈Y

где

{

если q ∈ A;

(Π.2)

δ_A(q) =

+∞,

если q ∈ A.

Заметим, что δ[-∞,0](Q(u, y, x)) ≤ 0 тогда и только тогда, когда Q(u, y, x) ≤ 0.

Поэтому нижнее множество уровня функции (y, x) → δ[-∞,0](Q(u, y, x)) для

всех a ∈ [0, +∞) совпадает с множеством

(Π.3)

{(y, x) ∈ Y × X | Q(u, y, x) ≤ 0},

которое является измеримым и сечение которого при каждом x ∈ X является

замкнутым. При a ∈ [-∞, 0) нижнее множество уровня пусто, а при a = +∞

нижнее множество уровня совпадает с Y × X . Поэтому по определению функ-

ция (y, x) → δ[-∞,0](Q(u, y, x)) является нормальным интеграном. А значит,

и функция

(Π.4)

(y, x) → Φ₂(u, y, x) + δ[-∞,0]

(Q(u, y, x))

— нормальный интегрант. Таким образом, согласно теореме 1 функция x →

→ Φ(u,x) является измеримой. Теорема 2 доказана.

Доказательство теоремы 4. Как было отмечено при доказательстве

теоремы 2,

δ[-∞,0](Q(u,y,x)) ≤ 0

тогда и только тогда, когда Q(u, y, x) ≤ 0. Поэтому нижнее множество уровня

a ∈ [0,+∞) функции (u,y,x) → δ[-∞,0](Q(u,y,x)) совпадает с множеством

(Π.5)

{(u, y, x) ∈ Y × X | Q(u, y, x) ≤ 0},

которое является измеримым и сечение которого при каждом x ∈ X являет-

ся замкнутым. Измеримость и замкнутость множеств уровня a ∈ [-∞, 0) ∪

∪ {+∞} проверяется тривиально. Таким образом, функция (u, y, x) →

→ δ[-∞,0](Q(u,y,x)) — нормальный интегрант. Поэтому и функция

(Π.6)

(u, y, x) → Φ₂(u, y, x) + δ[-∞,0]

(Q(u, y, x))

— также нормальный интегрант. Теорема 4 доказана.

Доказательство теоремы 6. Заметим, что

{

}

(Π.7)

P_ϕ(u) ≜ P{Φ(u,X) ≤ ϕ} = P

[-∞,ϕ](Φ(u,X)) ≤ 0

где

{

0, если q ∈ A;

(Π.8)

δA(q) =

1, если q ∈ A.

Построим нижние множества уровня функции (u, x) →δ[-∞,ϕ](Φ(u, x)):

{

}

(u, x) ∈ U × X |δ[-∞,ϕ](Φ(u, x)) ≤ a

⎧

⎨∅,

если a < 0;

(Π.9)

{(u, x) ∈ U × X | Φ(u, x) ≤ ϕ},

если 0 ≤ a < 1;

^⎩U × X ,

если a ≥ 1.

Таким образом, нижние множества уровня содержатся в сигма-алгебре

B(R^r) × F, и их сечения при фиксированных x ∈ X являются замкнутыми.

Отсюда следует, что функция (u, x) →δ[-∞,ϕ](Φ(u, x)) является нормальным

интегрантом, а значит, является полунепрерывной снизу по u ∈ U для всех

x ∈ X и измеримой по x для всех u, при этом согласно (Π.8) она принимает

только конечные значения. Поэтому согласно теореме 5 функция вероятности

u → P_ϕ(u) является полунепрерывной сверху для всех ϕ ∈ R^∗.

Для доказательства полунепрерывности функции квантили проверим ра-

венство

(Π.10)

U_P ≜ {u ∈ U | P_ϕ(u) ≥ α} = U_Φ ≜ {u ∈ U | ϕ_α

(u) ≤ ϕ}

для всех ϕ ∈ R^∗ и α ∈ (0, 1]. Равенство (Π.10) известно как лемма Розен-

блатта, ее доказательство для случая, когда функция потерь принимает

лишь конечные значения, можно найти в [9, лемма 2.10]. Пусть u ∈ U_P ,

т.е. выполнено неравенство P_ϕ(u) ≥ α. По определению квантили ϕ_α(u) =

= min

ϕ∈R^∗ |

ϕ(u) ≥ α}, а значит, ϕα(u) ≤ ϕ. Заметим, что данное нера-

венство выполнено и при бесконечных значениях ϕ или α = 1, так как

функция квантили всегда определена (но может принимать бесконечные

значения). Таким образом, u ∈ U_Φ и U_P ⊂ U_Φ. Пусть теперь u ∈ U_Φ. Тогда

ψ ≜ ϕ_α(u) ≤ ϕ. Заметим, что ψ ∈ R^∗ для любых ϕ ∈ R^∗, α ∈ (0,1]. Из моно-

тонности функции вероятности получаем, что α ≤ P_ψ(u) ≤ P_ϕ(u), поэтому

U_Φ ⊂ U_P . Равенство U_P = U_Φ доказано.

При полунепрерывности функции вероятности множества уровня U_P за-

мкнуты. Из равенства (Π.10) следует, что множества уровня функции кван-

тили также замкнуты. А значит, функция квантили полунепрерывна снизу.

Теорема 6 доказана.

Доказательство следствия 1. Из теоремы 4 следует, что функция

(u, x) → Φ(u, x) является нормальным интегрантом. Тогда по теореме 6 функ-

ция u → P_ϕ(u) полунепрерывна сверху, а функция u → ϕ_α(u) полунепрерыв-

на снизу. Таким образом, утверждение следует из теоремы Вейерштрасса.

Следствие 1 доказано.

Доказательство теоремы 7. Пусть (u,y(·)) ∈ U × Y. Заметим, что

Φ₂(u,y(x),x) + δ[-∞,0](Q(u,y(x),x)) ≥

{

}

≥ inf

Φ₂(u,y,x) + δ[-∞,0](Q(u,y,x))

= Φ(u,x)

y∈Y

для всех x ∈ X . Поэтому P_ϕ(u, y(·)) ≤ P_ϕ(u), а

ϕα(u, yu(·)) ≥ ϕα(u), откуда

следует, что

sup

P_ϕ(u,y(·)) ≤ P_ϕ(u),

inf

ϕα(u, yu(·)) ≥ ϕα(u).

y(·)∈Y

Покажем, что полученые неравенства выполнены как равенства. Так как

функции (y, x) → Φ₂(u, y, x) и (y, x) → Q(u, y, x) — нормальные интегранты и

в силу предположения об ограниченности множеств уровня функции потерь

справедливо, что

(Π.11)

Y ∗(u,x) ≜ Arg min{Φ2

(u, y, x) | Q(u, y, x) ≤ 0} = ∅,

y∈Y

если Φ(u, x) < +∞. По теореме 1 существует измеримая функция x → y_u(x)

такая, что y_u(x) ∈ Y^∗(u, x) при Φ(u, x) < +∞. Доопределим функцию x →

→ y_u(x) для случая Φ(u,x) = +∞ так, чтобы y_u(x) ∈ Y . Легко видеть, что

P_ϕ(u) = P_ϕ(u,y_u(·)) и ϕ_α(u) =

ϕα(u, yu(·)). Таким образом, выполнены дока-

зываемые равенства (12) и (13). Теорма 7 доказана.

Доказательство теоремы 8. Согласно теореме 2, при выполнении

условия теоремы функция x → Φ(u, x) является измеримой, поэтому зада-

ча (5) сформулирована корректно.

Пусть u ∈ U и S ∈ F_α. Справедливо, что

PΨ(u,S)(u) = P{Φ(u,X) ≤ Ψ(u,S)} ≥ P(S) ≥ α.

Поэтому

(Π.12)

Ψ(u, S) ≥ min{ϕ ∈ R^∗ | P_ϕ(u) ≥ α} = ϕ_α

(u).

Покажем, что равенство в (Π.12) достигается. Определим множество

(Π.13)

S_u ≜ {x ∈ X : Φ(u,x) ≤ ϕ_α

(u)}.

Легко видеть, что

ϕα(u) = min{ϕ ∈ R^∗ | P{Φ(u, X) ≤ ϕ} ≥ α} = sup Φ(u, x) = Ψ(u, Su).

x∈Su

Таким образом, доказываемое равенство (16) выполнено. Теорема 8 дока-

зана.

Доказательство следствия

2. По теореме

функция (u, x) →

→ Φ(u,x) является нормальным интегрантом. Отсюда по теореме 9 следу-

ет выполнение соотношений (24) и (25). Следствие 2 доказано.

Доказательство теоремы

10. Для ϕ^∗α ∈ R¹ теорема 10 доказана

в [23]. Заметим, что условие Φ(u, x) > -∞ и полунепрерывность снизу функ-

ции u → Φ(u, x) исключают возможность ϕ^∗α = -∞.

Проведем доказательство для случая ϕ^∗α = +∞. Рассмотрим последова-

тельность {ϕ_n}∞n=1 и последовательность {u_n}∞n=1, в которой u_n ∈

, если

ϕn < +∞, и un ∈ U, если ϕn = +∞. Введем обозначение

(Π.14)

ϕ ≜ liminf

ϕn.

n→∞

При доказательстве аналогичной теоремы в [23] показано, что

ϕ > -∞ и при

конечном значении

ϕ существует бесконечное множество индексов K, для

которого

(Π.15)

lim supP(n)ϕ(un) ≤

ϕ(u) (P^′-п.н.),

n→∞

n∈K

где u — предельная точка последовательности {u_n}∞n=1. Заметим, что нера-

венство (Π.15) остается верным при

ϕ = +∞, так как P+∞(u) = 1.

Так как

ϕn (un) ≥ α для любого n ∈ N, то для предельной точки выпол-

нено соотношение

ϕ(u) ≥ α, откуда следует, что

(Π.16)

ϕ = liminf

ϕn ≥ ϕ^∗ = +∞ (P^′-п.н.),

n→∞

а значит, lim_n→∞ ϕ_n = ϕ^∗α (P^′-п.н.). Теорема 10 доказана.

Доказательство теоремы 11. В случае ϕ = +∞ утверждение три-

виально. Будем считать, что ϕ ∈ R¹.

Пусть u ∈ U и y(·) ∈ Y. Проверка неравенства P_ϕ(u, y(·)) ≤ P_ϕ(u) произ-

водится так же, как и при доказательстве теоремы 7. Теперь покажем, что

в этом неравенстве может быть достигнуто равенство. Выберем измеримую

функцию x → y_u(x), удовлетворяющую условиям:

y_u(x) ∈ Y^∗(u,x), если Y^∗(u,x) = ∅;

y_u(x) ∈ Y, если Φ(u,x) = +∞;

q^⊤(x)y_u(x) ≤ ϕ и A(x)u + B(x)y_u(x) ≥ b(x), если Φ(u,x) = -∞,

для всех x ∈ X . По теореме 1 существует измеримая функция x → y_u(x) та-

кая, что y_u(x) ∈ Y^∗(u, x). Существование измеримой функции y_u(x), опреде-

ленной для x, при которых Φ(u, x) = -∞, и удовлетворяющей сформулиро-

ванным условиям, следует также из теоремы 1, если в качестве функции f(·)

рассмотреть нормальный интегрант

(

)

(Π.17) (y, x) → δ[-∞,0](q^⊤(x)y - ϕ) + δ[0,+∞] min(A(x)u + B(x)y - b(x))i

i=1,l

Нетрудно видеть, что P_ϕ(u) = P_ϕ(u, y_u(·)). Таким образом, доказываемое ра-

венство получено.

Существование оптимальной стратегии в задаче (4) в случае непустого

компактного множества U следует из полунепрерывности сверху критериаль-

ной функции и теоремы Вейерштрасса, а существование оптимальной стра-

тегии в задаче (10) — из доказанной эквивалентности задач (4) и (10). Тео-

рема 11 доказана.

Доказательство теоремы

12. Пусть u ∈ U и ϕ^∗u ≜ ϕ_α(u) = -∞.

Неравенство ϕ_α(u) ≤

ϕα(u, y(·)) для всех y(·) ∈ Y проверяется так же, как

и при доказательстве теоремы 7. Выберем измеримую функцию x → y_u(x),

удовлетворяющую условиям:

y_u(x) ∈ Y^∗(u,x), если Y^∗(u,x) = ∅;

y_u(x) ∈ Y, если Φ(u,x) = +∞;

q^⊤(x)y_u(x) ≤ ϕ^∗u и A(x)u + B(x)y_u(x) ≥ b(x), если Φ(u,x) = -∞,

для всех x ∈ X . Существование указанной функции x → y_x(u) следует из тео-

ремы 1. Для случая Φ(u, x) = -∞ теорему 1 следует применить к нормаль-

ному интегранту

(Π.18) (y, x) → δ[-∞,0](q^⊤(x)y - ϕ^∗u) + δ[0,+∞] min(A(x)u + B(x)y - b(x))i .

i=1,l

Легко видеть, что ϕ_α(u) =

ϕα(u, yu(·)).

Рассмотрим случай, когда ϕ_α(u) = -∞ в некоторой точке u ∈ U. Выби-

рая ϕ^∗u сколь угодно малым, можно построить решение задачи (11) со сколько

угодно малым значением критериальной функции, поэтому

inf

ϕα(u, y(·)) = -∞.

y(·)∈Y

Поскольку в силу определения ϕ_α(u, y(·)) > -∞ для всех u ∈ U и y(·) ∈ Y, то

инфимум в задаче (11) не достигается.

Существование оптимальной стратегии в задаче (5) в случае компактно-

го множества U следует из полунепрерывности снизу функции квантили и

теоремы Вейерштрасса. Теорема 12 доказана.

Доказательство теоремы 13. Пусть uⁿ — оптимальная стратегия в

задаче (35). Обозначим оптимальное значение целевой функции задачи (36)

через P^∗ и покажем, что P^∗ = P_ϕ(uⁿ). Для этого построим вектор допусти-

мых стратегий в задаче (36). Пусть y_k — некоторый элемент множества

{

}

(Π.19)

y ∈ Y | c^⊤(x_k)u + q^⊤(x_k)y ≤ ϕ, A(x_k)u + B(x_k)y ≥ b(x_k)

если оно непусто, и yk = 0, если данное множество пусто. Если множе-

ство (Π.19) при заданном k непусто, то определимδk = 1 иδk = 0, если

при заданном k множество (Π.19) пусто. В силу определения констант L₁

и L₂ вектор стратегий (uⁿ, y₁,..., y_n, δ) является допустимым в задаче (36) и

обеспечивает значение P_ϕ(uⁿ) критериальной функции. Таким образом, P^∗ ≥

≥ P_ϕ(uⁿ).

Пусть теперь (u, y₁, . . . , y_n, δ) — оптимальная стратегия в задаче (36). Если

δ_k = 1, то

(Π.20)

c^⊤(x_k)u + q^⊤(x_k)y_k

≤ϕ

(Π.21)

A(x_k)u + B(x_k)y_k ≥ b(x_k

поэтому

{

}

c^⊤(x_k)u + inf

q^⊤(x_k)y | A(x_k)u + B(x_k)y ≥ b(x_k)

≤ ϕ.

y∈Y

∑

Таким образом, P^∗ =1n δ_k ≤ P_ϕ(uⁿ), а значит, P^∗ = P_ϕ(uⁿ). Из полу-

k=1

ченного равенства и первой части доказательства видно, что значение uⁿ яв-

ляется оптимальным значением u в задаче (36). Для доказательства того, что

оптимальное значение u в задаче (36) оптимально в (35), предположим про-

тивное, а именно: P_ϕ(u) < P_ϕ(uⁿ). Но из неравенств (Π.20) и (Π.21) следует,

что P_ϕ(u) ≥ P^∗ = P_ϕ(uⁿ). Полученное противоречие доказывает теорему 13.

СПИСОК ЛИТЕРАТУРЫ

Birge J.R., Louveaux F. Introduction to Stochastic Programming. N.Y.: Springer,

2011.

Kall P., Mayer J. Stochastic Linear Programming: Models, Theory and

Computation. N.Y.: Springer, 2011.

Prékopa A. Stochastic Programming. Boston: Kluwer Acad. Publishers, 1995.

Shapiro A., Dentcheva D., Ruszczynski A. Lectures on Stochastic Programming.

Modeling and Theory. Philadelphia: Society for Industrial and Applied Mathematics

(SIAM), 2009.

Wets R.J.-B. Stochastic Programs with Fixed Recourse: the Equivalent Deterministic

Program // SIAM Rev. 1974. V. 16. No. 3. P. 309-339.

Frauendorfer K. Stochastic Two-Stage Programming. Berlin—Heidelberg: Springer,

1992.

Kulkarni A.A., Shanbhag U.V. Recourse-Based Stochastic Nonlinear Programming:

Properties and Benders-SQP Algorithms // Comput. Optim. Appl. 2012. V. 51.

No. 1. P. 77-123.

Kibzun A.I., Kan Y.S. Stochastic Programming Problems with Probability and

Quantile Functions. Chichester—N.Y.—Brisbane—Toronto—Singapore: John Wiley

& Sons, 1996.

Кибзун А.И., Кан Ю.С. Задачи стохастического программирования с вероят-

ностными критериями. М.: Физматлит, 2009.

10.

Кибзун А.И., Наумов А.В. Двухэтапные задачи квантильного линейного про-

граммирования // АиТ. 1995. № 1. С. 83-93.

Kibzun A.I., Naumov A.V. Two-Stage Quantile Linear Programming Problem //

Autom. Remote Control. 1995. V. 56. No. 1. P. 68-76.

11.

Schultz R., Tiedemann S. Conditional Value-at-Risk in Stochastic Programs with

Mixed-Integer Recourse // Math. Program. Ser. B. 2006. V. 105. P. 365-386.

12.

Норкин В.И., Кибзун А.И., Наумов А.В. Сведение задач двухэтапной вероят-

ностной оптимизации с дискретным распределением случайных данных к зада-

чам частично целочисленного программирования // Кибернетика и системный

анализ. 2014. Т. 50. № 5. С. 34-48.

Norkin V.I., Kibzun A.I., Naumov A.V. Reducing Two-Stage Probabilistic

Optimization Problems with Discrete Distribution of Random Data to Mixed-Integer

Programming Problems // Cybernet. Syst. Anal. 2014. V. 50. No. 5. P. 679-692.

13.

Sen S. Relaxation for Probabilistically Constrained Programs with Discrete Random

Variables // Oper. Res. Lett. 1992. V. 11. P. 81-86.

14.

Ruszczynski A. Probabilistic Programming with Discrete Distributions and

Precedence Constrained Knapsack Polyhedra // Math. Program. 2002. V. 93. P.

195-215.

15.

Luedtke J., Ahmed S., Nemhauser G. An Interger Programming Approach for Linear

Programs with Probabilistic Constraints // Math. Program. 2010. V. 122. P. 247-272.

16.

Saxena A., Goyal V., Lejeune M.A. MIP Reformulations of the Probabilistic Set

Covering Problem // Math. Program. 2010. V. 121. P. 1-31.

17.

Богданов А.Б., Наумов А.В. Решение двухэтапной задачи логистики в кван-

тильной постановке // АиТ. 2006. № 12. С. 36-42.

Bogdanov A.B., Naumov A.V. Solution to a Two-step Logistics Problem in a Quantile

Statement // Autom. Remote Control. 2006. V. 67. No. 12. P. 1893-1899.

18.

Кибзун А.И., Тарасов А.Н. Стохастическая модель функционирования системы

закупки электроэнергии на участке железной дороги // АиТ. 2018. № 3. С. 44-60.

Kibzun A.I., Tarasov A.N. Stochastic Model of the Electric Power Purchase System

on a Railway Segment // Autom. Remote Control. 2018. V. 79. No. 3. P. 425-438.

19.

Artstein Z., Wets R.J.-B. Consistency of Minimizers and the SLLN for Stochastic

Programs // J. Convex Anal. 1996. V. 2. P. 1-17.

20.

Pagnoncelli B.K., Ahmed S., Shapiro A. Sample Average Approximation Method for

Chance Constrained Programming: Theory and Applications // J. Optim. Theory

Appl. 2009. V. 142. P. 399-416.

21.

Campi M.C., Garatti S. A Sampling-and-Discarding Approach to Chance-

Constrained Optimization: Feasibility and Optimality // J. Optim. Theory Appl.

2011. V. 148. P. 257-280.

22.

Higle J.L., Sen S. Statistical Approximations for Stochastic Linear Programming

Problems // Ann. Oper. Res. 1999. V. 85. P. 173-192.

23.

Иванов С.В., Кибзун А.И. О сходимости выборочных аппроксимаций задач сто-

хастического программирования с вероятностными критериями // АиТ. 2018.

№ 2. С. 19-35.

Ivanov S.V., Kibzun A.I. On the Convergence of Sample Approximations for

Stochastic Programming Problems with Probabilistic Criteria // Autom. Remote

Control. 2018. V. 79. No. 2. P. 216-228.

24.

Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач. М.: Наука, 1974.

Ioffe A.D., Tihomirov V.M. Theory of Extremal Problems. Amsterdam: North-

Holland, 1979.

25.

Rockafellar R.T., Wets R.J.-B. Variational Analysis. Berlin: Springer, 2009.

26.

Ширяев А.Н. Вероятность. М.: МЦНМО, 2017.

Shiryaev A.N. Probability-1. N.Y.: Springer, 2016.

27.

Женевская И.Д., Наумов А.В. Метод декомпозиции для решения двухэтапных

задач стохастического линейного программирования с квантильным критери-

ем // АиТ. 2018. № 2. С. 36-50.

Zhenevskaya I.D., Naumov A.V. The Decomposition Method for Two-Stage

Stochastic Linear Programming Problems with Quantile Criterion // Autom. Remote

Control. 2018. V. 79. No. 2. P. 229-240.

28.

Kibzun A.I. Comparison of Two Algorithms for Solving a Two-Stage Bilinear

Stochastic Programming Problem with Quantile Criterion // Appl. Stochast. Models

Business Industry. 2015. V. 31. No. 6. P. 862-874.

29.

Иванов С.В., Кибзун А.И. Выборочная аппроксимация двухэтапной задачи сто-

хастического линейного программирования с квантильным критерием // Тр.

Ин-та матем. и мех. УрО РАН. 2017. Т. 23. № 3. С. 134-143.

Ivanov S.V., Kibzun A.I. Sample Average Approximation in a Two-Stage Stochastic

Linear Program with Quantile Criterion // Proc. Steklov Institut. Math. 2018.

V. 303. Suppl. 1. P. 107-115.

Статья представлена к публикации членом редколлегии М.М. Хрусталевым.

Поступила в редакцию 27.08.2018

После доработки 21.01.2019

Принята к публикации 07.02.2019