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

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

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

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

Н. МЛАДЕНОВИЧ (nenad@mi.sanu.ac.rs)

(Технологический колледж Эмиратов, Абу-Даби, ОАЭ,

Уральский Федеральный университет, Екатеринбург)

ПОИСК С ЧЕРЕДУЮЩИМИСЯ ОКРЕСТНОСТЯМИ ДЛЯ

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

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

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

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

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

с квантильным критерием. Применяется метод выборочных аппроксима-

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

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

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

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

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

доверительное множество является стратегией оптимизации. Для поиска

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

редующимися окрестностями. Для решения задачи разработан комбини-

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

доверительном методе и поиске с чередующимися окрестностями.

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

ная аппроксимация, поиск с чередующимися окрестностями, доверитель-

ный метод.

DOI: 10.1134/S0005231019010045

1. Введение

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

ются для моделирования ситуации, когда лицо, принимающее решение, опре-

деляет стратегию оптимизации последовательно на двух этапах. Стратегия

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

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

при моделировании системы, а выбор стратегии второго этапа зависит от

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

Как правило, двухэтапные задачи возникают в экономике. Например, при

планировании производства необходимо принять решение об объеме произ-

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

¹ Работа Кибзуна А.И. выполнена в рамках Государственного задания Минобрнау-

ки №2.2461.2017/4.6. Работа Младеновича Н. выполнена в рамках проекта программно-

целевого финансирования BR05236839 «Разработки информационных технологий и систем

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

вого Казахстана».

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

ным, принимается решение о ценах на выпущенную продукцию и, возможно,

о выпуске дополнительной партии продукции. Другим примером являются

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

размер парка транспортных средств, а на втором этапе по факту спроса на

перевозки принимается решение о распределении транспортных средств.

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

ные функции, выражающие качество функционирования системы. Двухэтап-

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

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

нировании системы. Квантильный критерий выражает потери, которые не

могут быть превышены с заданной вероятностью, что делает возможным его

применение при необходимости учета рисков.

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

но связаны с задачами с вероятностными ограничениями [2, 3]. Нетрудно за-

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

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

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

квантили. Свойства непрерывности и выпуклости функции квантили иссле-

дованы в [4].

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

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

рием [5]. Два алгоритма для решения данной задачи были предложены и

исследованы в [5]. Первый алгоритм основан на сведении задачи к задаче

смешанного целочисленного программирования. Второй алгоритм использу-

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

ко с его помощью может быть найдена только верхняя оценка оптимального

решения задачи. Оба предложенных алгоритма испытывают трудности при

решении задач большой размерности.

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

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

случайных параметров. В этом случае может быть построена выборочная

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

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

ций при увеличении объема выборки доказана в [6] для задач с критерием

в форме математического ожидания и в [7] — для задач с вероятностными

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

тильным критерием были получены в [8], а для двухэтапных задач — в [9].

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

них и нижних границ оптимального значения критериальной функции [10].

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

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

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

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

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

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

ной задаче смешанного целочисленного программирования [13-15]. Однако

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

ся затруднительным. Для решения задач с квантильным критерием также

применяется доверительный метод [4]. В случае дискретного распределения

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

в которой выбирается множество реализаций случайного вектора. Следует

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

решение смешанной целочисленной задачи.

По указанным причинам часто для решения задач получаемого типа ис-

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

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

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

можно найти в [17-19]. Метод основан на использовании различных окрестно-

стей решения и процедуры локального поиска. Отметим, что для локального

поиска используется некоторая фиксированная окрестность. Для применения

метода нужно выбрать некоторое начальное решение, а в качестве текущей

окрестности решения установить наименьшую окрестность. Итерация метода

начинается с поиска локально-оптимального решения задачи. Если в резуль-

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

заменяется на более широкую, в которой выбирается новое решение; в про-

тивном случае найденное решение становится текущим и в качестве текущей

окрестности устанавливается наименьшая. После этого осуществляется сле-

дующая итерация.

В статье предлагается способ конструирования семейства окрестностей до-

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

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

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

доверительном методе и поиске с чередующимися окрестностями.

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

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

с квантильным критерием [5].

Пусть случайный вектор X определен на вероятностном пространстве

(R^m, L(R^m), P), где L(R^m) — лебегова σ-алгебра подмножеств R^m. Предпола-

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

закону, т.е. X ∼ N (0, I), где I — единичная ковариационная матрица. Для

упрощения считаем, что X(x) = x для всех x ∈ R^m.

Пусть множество U допустимых стратегий u первого этапа является вы-

пуклым полиэдром, т.е.

U ≜ {u ∈ Rⁿ : A₀u ≤ b₀},

где A₀ ∈ R^k×n — матрица и b₀ ∈ R^k — вектор. Будем предполагать, что мно-

жество U ограничено.

Определим функцию потерь (u, x) → Φ(u, x), зависящую от стратегии пер-

вого этапа u ∈ U ⊂ Rⁿ и от реализации x случайного вектора X, так:

(1)

Φ(u, x) ≜ c⊤0u + x^⊤A₁u + inf

c⊤₁

y∈Y (u,x)

где y — стратегия второго этапа, принадлежащая множеству

{

}

(2)

Y (u, x) ≜ y ∈ R^l : x^⊤A2iu + c⊤2iu + b⊤i y ≥ a⊤3ix + d_i, i = 1, s, y ≥ 0

c₀ ∈ Rⁿ, c₁ ∈ R^l, c2i ∈ Rⁿ, b_i ∈ R^l, a3i ∈ R^m — детерминированные векто-

ры, A₁, A2i ∈ R^m×n — матрицы, d_i ∈ R¹. Если Y (u, x) = ∅ для пары (u, x) ∈

∈ Rⁿ × R^m, то по определению полагаем, что Φ(u,x) = +∞.

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

по правилу

{

}

(3)

P_ϕ(u) ≜ P c⊤0u + X^⊤A₁u + Φ(u,X) ≤ ϕ

где

{

inf

c⊤₁y, если Y (u, x) = ∅,

(4)

Φ(u, x) ≜y∈Y(u,x)

+∞,

если Y (u, x) = ∅.

Функция квантили ϕ_α(·): U → (-∞, +∞] определяется как

{

}

(5)

ϕα(u) ≜ min

ϕ ∈ R¹ : P_ϕ(u) ≥ α

где α ∈ (0, P^∗) — фиксированная вероятность, где

P^∗ ≜ sup P{Y (u,X) = ∅}.

u∈U

Сформулируем задачу первого этапа в виде

(6)

ϕα ≜ inf

ϕα(u), Uα ≜ Arg min

ϕα

(u).

u∈U

Задача (6) является двухэтапной задачей стохастического программирования

с квантильным критерием.

Будем считать, что выполнено следующее предположение.

Предположение 1. Векторы c₁ и b_i, i = 1,s, являются такими, что

множество

(7)

V ≜ {v ∈ R^s : B^⊤v ≤ c₁, v_i

≥ 0, i = 1, s}

компактно, где

⎛

⎞

b⊤1

B≜⎝ ...

⎠_.

b^⊤

3. Сведение к одноэтапной задаче

Рассмотрим задачу второго этапа (1). Используя обозначение

⎛

⎞

a⊤31x - u^⊤A⊤21x + d₁ - c⊤21u

(8)

a(u, x) ≜⎝

⎠_,

a⊤3sx - u^⊤A⊤2sx + d_s - c⊤2su

множество (2) может быть представлено как

{

}

Y (u, x) ≜ y ∈ R^l : By ≥ a(u, x), y ≥ 0

Согласно теории двойственности [1] справедливо, что

{

}

(9)

Φ(u, x) = max

a^⊤(u,x)v : B^⊤v ≤ c₁, v ≥ 0

если максимум в (9) конечен, где через v ∈ R^s обозначена двойственная пере-

менная. Для каждой фиксированной пары (u, x) ∈ U × R^m задача (9) явля-

ется задачей линейного программирования. Заметим, что предположение 1

гарантирует конечность Φ(u, x). Кроме того, максимум в (9) достигается в

некоторой вершине V . Таким образом, при выполнении предположения 1 зна-

чение Φ(u, x) может быть записано в форме

(10)

Φ(u, x) = max a^⊤(u, x)v^j ,

j=1,J

где v^j , j = 1, J, — вершины выпуклого ограниченного полиэдра V .

Подставляя (10) в (1), получаем

Φ(u, x) = max Φ_j(u, x),

j=1,J

где

Φ_j(u,x) ≜ c⊤0u + x^⊤A₁u + a^⊤(u,x)v^j.

Данное представление Φ(u, x) не содержит в явном виде стратегии второго

этапа. Это значит, что задача (6) сведена к одноэтапной задаче стохастиче-

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

{

}

(11)

ϕα = inf min ϕ ∈ R¹ : P max Φj (u, x) ≤ ϕ

≥α

u∈U

j=1,J

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

на по u для всех x, то минимумы в (11) и в (6) достигаются, если множество U

компактно [4]. Отсюда следует, что U_α = ∅.

4. Выборочная аппроксимация

Пусть дана последовательность {X^ν }ν∈N независимых стандартных нор-

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

ность определена на некотором вероятностном пространстве (Ω, F, P^′), кото-

рое существует по теореме Колмогорова.

Функция вероятности может быть оценена как частота события

{Φ(u, X) ≤ ϕ}:

∑

P(N)ϕ(u) ≜

χ(-∞,0](Φ(u,X^ν) - ϕ),

ν=1

где χ_A(x) = 1, если x ∈ A, и χ_A(x) = 0, если x ∈ A.

Используя оценку функции вероятности, так же можно оценить функцию

квантили

{

}

(12)

ϕ(N)α(u) ≜ min ϕ: P(N)ϕ(u) ≥ α

Таким образом, выборочная аппроксимация задачи (6) записывается в ви-

де:

(13)

ϕN ≜ inf

ϕ(N)α

(u), N ∈ N,

u∈U

U_N ≜ Arg minϕ(N)α(u), N ∈ N.

u∈U

Теорема о сходимости почти наверное (п.н.) решений аппроксимирующих

задач для более общей задачи была доказана в [8].

Теорема 1

[8]. Пусть выполнены условия:

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

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

ментов и полунепрерывной снизу по u ∈ U;

(iii) для всех ε > 0 существует пара

(ũ,

ϕ) такая, что

ϕ-ϕ_α|≤ε

ϕ(ũ) > α.

Тогда lim

ϕN = ϕα (P^′-п.н.), и каждая предельная точка u последователь-

N→∞

ности {u_N }N∈N, где u_N ∈ U_N, N ∈ N, является оптимальным решением (6),

где u ∈ U_α (P^′-п.н.).

Условие (ii) теоремы 1 выполнено, если выполнено предположение 1.

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

нормального распределения строго положительна.

Рассмотрим задачу (13) для фиксированной реализации {x^ν }Nν=1 выборки

{X^ν }Nν=1. В этом случае задача (13) может быть рассмотрена как одноэтап-

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

дискретным распределением случайных параметров:

{

(

)

}

(14)

ϕN = min min

ϕ∈R¹ :P

u, ξ^N

≤ϕ

≥α

u∈U

{

(

)

}

U_N = Arg min min

ϕ∈R¹ :P

u, ξ^N

≤ϕ

≥α

u∈U

где дискретный случайный вектор обозначен через ξ^N . Распределение слу-

чайного вектора ξ^N сосредоточено на множестве X ≜ {x^ν : ν = 1, N }. По-

скольку случайный вектор X распределен непрерывно, то Xν1 = Xν2 (P^′-п.н.)

для ν₁ = ν₂. Поэтому будем считать, что xν1 = xν2 для ν₁ = ν₂. Тогда

P{ξ^N = x^ν } = 1/N , ν = 1, N. В (14) можно написать min вместо inf, пото-

му что минимум достигается в случае компактного множества U [4].

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

Рассмотрим семейство множеств

{

}

F_α ≜

S ∈ L(R^m) : P{ξ^N ∈ S} ≥ α

и функцию максимума ψ(·): L(R^m) × U → (-∞, +∞], определенную услови-

ем

(15)

ψ(S, u) ≜ sup

Φ(u, x).

x∈S

Множества, принадлежащие семейству F_α, называются доверительными.

Согласно доверительному методу, описанному в [4], задача минимизации

функции квантили (14) эквивалентна минимаксной задаче

(16)

ϕN = min

ψ(S, u), (u_N , S_N ) = arg min

ψ(S, u).

u∈U,S∈Fα

u∈U, S∈Fα

Введем обозначение

(17)

ψ(S) ≜ inf

ψ(S, u), u^S ≜ arg min

ψ(S, u).

u∈U

Поскольку распределение ξ^N дискретно, хотя бы одно оптимальное до-

верительное множество содержится в семействе всех подмножеств X с ме-

рой меньшей или равной α. Обозначим данное семейство множеств через

X_α ≜ {S ∈ F_α : S ⊂ X}.

Таким образом, можно сформулировать задачу (16) в виде

(18)

ϕN = min

ψ(S), S_N ≜ arg minψ(S).

S∈Xα

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

ψ(S) и u^S для S ∈ X_α могут быть найдены как реше-

ние (ϕ, u) задачи линейного программирования

(19)

ψ(S) = min

{ϕ : Φ_j

(u, x) ≤ ϕ, x ∈ S, j = 1, J}.

ϕ∈R¹,u∈U

Поиск точного решения задачи (18) требует вычисления

ψ(S) для всех

S ∈ X_α. Однако, учитывая структуру оптимального доверительного множе-

ства, количество перебираемых множеств может быть сокращено. Структура

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

подстановки неизвестного оптимального решения (ϕ_N , u_N ) в ограничения за-

дачи (19). Совершив указанную подстановку, можно заключить, что опти-

мальное доверительное множество имеет форму

S_N = {x ∈ X : Φ_j(u_N ,x) ≤ ϕ, j = 1,J}.

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

вию Conv(S_N ) ∩ X = S_N . Это значит, что никакие точки из X \ S_N не принад-

лежат выпуклой оболочке (Conv) множества S_N . Поэтому можно перебирать

только множества, обладающие данным свойством.

Известно, что так называемое α-ядро вероятностной меры является под-

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

чи (6) [4]. Для стандартного нормального распределения α-ядро может быть

определено как

K_α ≜ {x : ∥x∥ ≤ ρ_α},

где ρ_α — квантиль уровня α стандартного нормального распределения и ∥·∥ —

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

ные множества, удовлетворяющие условию K_α ⊂ S.

α-Ядро также позволяет найти нижнюю оценку оптимального значения

критериальной функции исходной задачи (6). Доказано в [4], что

ψ(K_α) ≤ ϕ_α.

6. Поиск с чередующимися окрестностями

Даже принимая во внимание структуру оптимального доверительного

множества, поиск точного решения задачи (18) требует значительных вычис-

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

метаэвристики. Предлагается использовать модификацию поиска с чередую-

щимися окрестностями [16, 17].

6.1. Поиск начального решения

Для успешного применения поиска с чередующимися окрестностями по-

лезно иметь хорошее начальное решение. Опишем процедуру, предлагаемую

для поиска начального решения.

Известно [4, теорема 3.13], что верхняя оценка

ψ(S_R), соответствующая

доверительному шару S_R ≜ {x: ∥x∥ ≤ R} с мерой α, стремится к оптималь-

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

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

ляется стандартным нормальным.

Предлагается следующий алгоритм поиска начального решения задачи.

Алгоритм 1.

1. Найти ϕ^R

S_R) и

S_R как решение задачи линейного программиро-

вания (19), гд

S_R ≜ S_R ∩ X.

2. Вычислить

ϕ≜ϕαN)(

S_R ).

3. Найти начальное доверительное множество S⁰ и начальную страте-

гию u⁰, обеспечивающие значение критериальной функции ϕ⁰, как

{

(

)

}

S⁰ ≜ x ∈ X : Φ

S_R ,x

≤

u⁰ ≜ arg minψ(S⁰,u), ϕ⁰

ψ(S⁰).

u∈U

Несмотря на то что множество S_R обычно обеспечивает хорошую верхнюю

оценку ϕ_N , алгоритм 1 позволяет улучшить эту границу, поскольку множе-

ство S⁰ лучше, чем S_R, и поэтому ϕ⁰ ≤ ψ

S_R).

6.2. Алгоритм

Для применения поиска с чередующимися окрестностями необходимо

определить структуру окрестностей. Рассмотрим некоторое доверительное

множество S ⊂ X . Определим следующие множества:

{

(

)

}

S^- ≜

x∈S :Φ

u^S,x

ψ(S)

{

}

⋃

S⁺ ≜

Arg min

Φ_j(u^S,x) : max Φ_j′(u^S,x)

ψ(S)

x∈X \S

j^′=1,n, j^′=j

j∈J

Множество S^- состоит из реализаций x ∈ S, максимизирующих Φ(u^S , x).

Чтобы получить новое доверительное множество, исключим из доверитель-

ного множества точку, принадлежащую S^-, и включим точку, принадлежа-

щую S⁺. Чтобы минимизировать следующее значение ψ(S), в доверительное

множество включаются точки, минимизирующие Φ_j(u^S , x).

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

ного множества S:

{

}

O₁(S) ≜

S^′ : S^′ = (S \ {x}) ∪ {x}, x ∈ S^-, x ∈ S⁺

⋃

Or+1(S) ≜

O₁(S^′), r ∈ N.

S^′∈Or(S)

Доверительное множество S называется локально-оптимальным, если

ψ(S)

ψ(S^′) для всех S^′ ∈ O₁(S).

Опишем поиск с чередующимися окрестностями для задачи (18).

Алгоритм 2.

1. Выбрать начальное доверительное множество S, например S := S⁰.

Установить r := 1.

2. Пока r < r_max, повторять следующие шаги:

а) случайным образом получить множество S^′ ∈ O_r(S);

б) установить S^′′ ≜ {x ∈ X : Φ(uS′ , x)

ψ(S^′)};

в) найти локальный оптимум S^′′′, применяя локальный поиск с S^′′ в каче-

стве начального решения;

г) есл

ψ(S^′′)

ψ(S), то установить S := S^′′ и r := 1, иначе r := r + 1.

Применяя алгоритм 2, получаем доверительное множество S. Страте-

гию u^S можно взять в качестве приближенного решения задачи (13).

Для поиска решения, близкого к оптимальному решению исходной зада-

чи (6), предлагается следующий алгоритм, основная идея которого состоит в

увеличении объема выборки.

Алгоритм 3.

1. Выбрать начальное значение N ∈ N и шаг Δ ∈ N. Получить реализации

x¹,... ,x^N.

2. Найти стратегию u_N , ϕ_N , применяя алгоритмы 1 и 2.

3. Получить реализации xN+1, . . . , xN+Δ. Установить N := N + Δ.

4. Найти решение u_N , ϕ_N задачи (13), применяя алгоритм 2 с начальным

доверительным множеством

{

}

x ∈ X : Φ(uN-Δ,x) ≤ ϕ(N)α(uN-Δ)

5. Найти оценку значения ϕ_α(u_N ) функции квантили (5) в виде

ϕα(uN ) ≜ ϕαM)(uN ),

где M ≫ N.

6. Если выполнен критерий остановки, считать u_N приближенным реше-

нием (6). В противном случае перейти к шагу 3.

В приведенном алгоритме 3 различные критерии остановки могут быть

использованы, например |ϕα(uN ) -

ϕα(uN-Δ)| ≤ ε или N ≥ Nmax.

7. Численный эксперимент

Рассмотрим задачу для следующих данных:

⎛

⎞

-0,4

)

⎜

⎟

⁽6

c₀ =

⎝ -6

⎠, c1 =

C2i = 0, i = 1,s, s = 2,

(

)

⁽1 0 0

⁽1 -1 1⁾

-2 3 -1

A₁ = 0,1

A₂₁ =

A₂₂ =

-4 2

)

(

)

⁽2,5

a₃₁ =

a₃₂ =

2,5

(

)

-2,5

d₁ = 0, d₂ = 0, α = 0,8.

-2

Вычисления проводились на ЭВМ AMD Athlon (tm) 64 Processor 3500+,

2,21 ГГц, 512 МБ ОЗУ. Результат применения алгоритма 3 представлен

в табл. 1.

Таблица 1. Результаты применения поиска с чередующимися окрестностями

Начальное решение

N = 500

N = 1000

N = 1500

(N = 500)

ϕ_N

10,0545

6,5185

7,5775

8,1310

ϕ_α(u_N )

10,5598

8,1974

8,5239

8,2136

uN1

0,1699

0,0121

uN2

1,1438

1,2813

1,3774

1,2618

uN3

1,0492

0,2912

0,1041

0,2741

Время, с

0,16

70,71

220,53

2072,95

Таблица 2. Результаты применения метода имитации отжига

Начальное решение

N = 500

N = 1000

N = 1500

(N = 500)

ϕ_N

10,0545

6,5185

7,5775

8,1178

ϕ_α(u_N)

10,5598

8,1974

8,5239

8,4959

uN1

0,1699

0,0483

uN2

1,1438

1,2813

1,3774

1,1891

uN3

1,0492

0,2912

0,1041

0,5515

Время, с

0,16

447,93

1537,63

2739,04

На каждом шаге оценивалось значение исходной функции квантили

ϕα(u^N ) по выборке {X^ν }ν=1 объема M = 10⁶. Можно заметить по табл. 1, что

лучшее решение было получено для выборки объема 500. Появлению данно-

го результата способствовали две причины. Во-первых, решалась не исходная

задача, а ее аппроксимация. Во-вторых, в случае большого объема выборки

точное решение задачи становится затруднительным.

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

аналогичной алгоритму 3, но в которой аппроксимирующая задача (14) реша-

лась с помощью метода имитации отжига. Детальное описание этого метода

выходит за рамки статьи. Полученные результаты приведены в табл. 2, из

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

стями позволяет найти решение за меньшее время. При этом для N = 500 и

N = 1000 найдено то же решение, а при N = 1500 — близкое решение, что

косвенно свидетельствует о возможности поиска близкого к оптимальному

решения с помощью разработанного алгоритма.

Чтобы найти точное решение аппроксимирующей задачи, задача (14) бы-

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

с помощью метода, предложенного в [14]. Для увеличения скорости поиска

использовалось описанное выше свойство α-ядра. Эквивалентная задача ре-

шалась с помощью CPLEX. Было получено решение с значением критериаль-

ной функции ϕ_N = 8,1138 при N = 1500. Вычисления длились 7502 секунды.

Таким образом, видно, что с помощью предложенного алгоритма может

быть найдено хорошее решение задачи. При этом алгоритму требуется мень-

шее время, чем время вычислений с помощью CPLEX и метода имитации

отжига.

Кроме того, найдена нижняя оценка ϕ_α, равна

ψ(K_α) = 5,7352.

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

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

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

ложен алгоритм решения задачи. Данный алгоритм основан на доверитель-

ном методе, поиске с чередующимися окрестностями и методе выборочных

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

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

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

являются адаптация поиска с чередующимися окрестностями для более ши-

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

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

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

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

Verlag, 1997.

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

Modeling and Theory. Philadelphia: Society for Industrial and Appl. Math. (SIAM),

2009.

Beraldi P., Ruszczynski A. A Branch and Bound Method for Stochastic Integer

Problems under Probabilistic Constraints // Optim. Method. Softw. 2002. V. 17.

No. 3. P. 359-382.

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

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

Wiley & Sons, 1996.

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

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

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

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

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

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.

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

хастического программирования с вероятностными критериями // АиТ. 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.

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

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

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

10.

Guigues V., Juditsky A., Nemirovski A. Non-asymptotic Confidence Bounds for the

Optimal Value of a Stochastic Program // Optim. Method. Softw. 2017. V. 32. No. 5.

P. 1033-1058.

11.

Lepp R. Approximate Solution of Stochastic Programming Problems with

Recourse // Kybernetika. 1987. V. 23. No. 6. P. 476-482.

12.

Lepp R. Approximation of the Quantile Minimization Problem with Decision

Rules // Optim. Method. Softw. 2002. V. 17. No. 3. P. 505-522.

13. Benati S., Rizzi R. A Mixed Integer Linear Programming Formulation of the Optimal

Mean/Value-at-Risk Portfolio Problem // Eur. J. Oper. Res. 2007. V. 176. No. 1.

P. 423-434.

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

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

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

анализ. 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. Ana. 2014. V. 50. No. 5. P. 679-692.

15. Ruszczynski A. Probabilistic Programming with Discrete Distributions and

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

93.

P. 195-215.

16. Mladenović N., Hansen P. Variable Neighborhood Search // Comput. Oper. Res.

1997. V. 24. No. 11. P. 1097-1100.

17. Hansen P., Mladenović N., Pérez J.A.M. Variable Neighbourhood Search: Methods

and Applications // Ann. Oper. Res. 2010. V. 175. No. P. 367-407.

18. Hansen P., Mladenović N. Variable Neighborhood Search / Mart´ı R., Pardalos P.,

Resende M. (eds.), Handbook of Heuristics. Cham: Springer, 2016.

19. Hansen P., Mladenović N., Todosijević R., Hanafi S. Variable Neighborhood Search:

Basics and Variants // EURO J. Comput. Optim. 2017. V. 5. No. 5. P. 423-454.

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

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

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

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