Автоматика и телемеханика, № 4, 2014
© 2014 г. А.И. КИБЗУН, д-р физ.-мат. наук, О.М. ХРОМОВА (Московский авиационный институт)
О СВЕДЕНИИ МНОГОЭТАПНОЙ ЗАДАЧИ СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ С КВАНТИЛЬНЫМ КРИТЕРИЕМ К ЗАДАЧЕ СМЕШАННОГО ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ1
Рассматривается многоэтапная задача стохастического программирования с квантильным критерием в априорной постановке, которая сводится к двухэтапной задаче. Доказывается эквивалентность двухэтапных задач с квантильным критерием в априорной и в апостериорной постановках, записанным для общего случая. Двухэтапная задача в апостериорной постановке, в свою очередь, сводится к эквивалентной задаче смешанного целочисленного линейного программирования. Рассматривается пример.
1. Введение
Традиционно в задачах стохастического линейного программирования в качестве критерия оптимизации используется математическое ожидание [1]. В авиационной и космической технике особое внимание уделяется вопросам надежности систем [2], поэтому достаточно часто требуется найти гарантированное по вероятности решение. В этом случае наиболее адекватными являются постановки задач стохастического программирования с квантильным критерием. Методам решения задач квантильной оптимизации посвящена работа [3]. Однако в многих прикладных задачах [1] возникают многоэтапные задачи стохастического программирования.
Многоэтапные задачи стохастического программирования оказываются очень близки к динамическим задачам управления, учитывающим воздействие случайных факторов [2]. В этих задачах выбирается стратегия первого этапа, которая в зависимости от реализации случайных факторов корректируется на последующих этапах (шагах). Многоэтапные задачи стохастического программирования являются обобщением двухэтапных задач стохастического программирования. Двухэтапная задача с квантильным критерием рассмотрена в [4], где была установлена эквивалентность двухэтапных задач в априорной и апостериорной постановках. Кроме того, в [4] была получена верхняя оценка квантильного критерия для двухэтапной задачи, основанная на решении задачи линейного программирования.
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект № 11-07-00315-а) и Государственного финансирования целевых программ «Научные и научно-педагогические кадры инновационной России» (мероприятие 1.2.2, Госконтракт № 14.740.11.1128).
В [5,6] рассмотрены линейные одноэтапные задачи квантильной оптимизации с дискретным распределением, которые сводятся к задачам смешанного целочисленного линейного программирования. В [7] рассмотрен общий случай двухэтапной задачи квантильной оптимизации, которая сведена к задаче смешанного целочисленного программирования большой размерности.
В данной статье исследуется многоэтапная задача стохастического программирования с квантильным критерием. С помощью эквивалентных преобразований она сводится к двухэтапной задаче, которая, в свою очередь, сводится к задаче смешанного целочисленного линейного программирования. Рассматривается пример.
2. Многоэтапная задача стохастического программирования в априорной постановке
Сформулируем Ж-этапную задачу стохастического программирования в априорной постановке. Введем функцию потерь
ФN (и,у(0,Х) = сти + а^Х^и + ^1(^X1) + а^ХьХг)« +
(2 1) N-1 N-1
+ С|у2(и,Х1,Х2) + ... = С^ и + ^ а!г (X * )и + ^ СЪг(и,Х*),
*=1 *=1
где и € И™ — план первого этапа; у() = со1 (у1(^),...,yN-1(^)) — вектор-функция планов последующих N — 1 этапов, выбираемая в классе измеримых функций со значениями в Е1тг; X = со1 (Х\,..., Хг = = со\ (Х\,..., Х^, г = 1, АГ — 1, — наборы случайных векторов ё ац{Хг), г = 1, N — 1, — заданные измеримые вектор-функции соответствующих размерностей; с^, г = О, N — 1, — заданные детерминированные вектор-столбцы.
Предположим, что случайный вектор X имеет плотность распределения р(х), где х € Нга, п = п1 + п2 + ... + nN-1. Пусть имеется набор из N — 1 ограничений
(2.2) Фг(и, уг(-),Хг) 4 А2г(Хг)и + Вгу\и, Хг) > а3г(Хг), i = 1, N - 1,
где уг(-) = col (yi(-),..., y¿(-)); A-2í{X%), i = 1,N — 1, — заданные измеримые матричные функции размерности (s¿ х m); а-ц{Хг), i = 1,N — 1, — заданные измеримые вектор-функции размерности s¿, Bj — заданная матрица размерности (si х mi).
Рассмотрим функцию вероятности
(2.3) Р^и, у(-)) = Г{Ф(и, у(-),Х) < <р, Фг(и, уг(-),Хг) > а3г(Хг), i = 1, N - 1}. Рассмотрим также функцию квантили
(2.4) 4>a(u,y(V = min{^ : Pv(u,y() > a}, a € (0,1).
Сформулируем Ж-этапную задачу стохастического программирования в априорной постановке
(2.5) <а = шт <а(и,у(-)), иа = argmin «еи, у(-)еу иеи
тт <а(и,у(-)) у(-)еу
где и — заданное множество допустимых стратегий первого этапа, а У — множество допустимых стратегий последующих этапов:
У±{у(-) : Уг(и,Хг)>0, 1 = 1,ЛГ-1}.
Под решением задачи (2.5) понимается пара (<а,иа). Если не существует иа, т.е. минимум (2.5) не достигается, то считается, что решение в задаче (2.5) не существует.
Для примера рассмотрим трехэтапную задачу стохастического программирования. Функция вероятности примет вид
(2.6) Р„(и, у()) = Р{Ф3(и, у(-), Х) < Фг(и, уг(■), Хг) ^ а3г(Хг), г = 1,2},
где
Ф3(и, у('), X) = сти + а^Х^и + сту1 (и, Х1) + а^^, Х2)и + ^(и, Х1, Х2), (2.7) $2(и,у2(-),Х2) = А22(Х1,Х2)и + В2у2(и,Х1 ,Х2) ^ аз2(Х1,Х2), $1(и,у1(-),Х1) = А21(Х1)и + £ш(и,Х1) ^ аз1(Х1).
Замечание 1. В качестве критерия оптимизации в многоэтапных задачах стохастического программирования чаще всего рассматривается математическое ожидание [1]. Многоэтапные задачи стохастического программирования обычно рассматриваются в апостериорной постановке, когда оптимальный план на текущем этапе выбирается в зависимости от реализации случайных факторов на предыдущих этапах. По сути, это означает применение метода динамического программирования для решения задачи стохастического программирования. Но, как известно из [8], метод динамического программирования для решения задачи стохастического управления применим лишь тогда, когда критерий обладает аддитивным и марковским свойствами. Именно такими свойствами обладает математическое ожидание от функции случайных потерь. Квантильный критерий не обладает ни марковским, ни аддитивным свойствами [2], вследствие чего записать многоэтапную задачу стохастического программирования с квантильным критерием в традиционной апостериорной постановке невозможно в принципе. Поэтому в данной работе исследуемая задача записана в априорной постановке, когда оптимальные планы на всех этапах, кроме первого, выбираются в классе функций, зависящих от всей предыдущей информации. Заметим, что впервые на связь двухэтапных задач в априорной и апостериорной постановках было обращено внимание в [4].
3. Сведение многоэтапной задачи в априорной постановке к двухэтапной задаче
Предположим, что вероятностная мера абсолютно непрерывна относительно меры Лебега и существует плотность р(х) случайного вектора X. Дис-кретнзнруем вероятностную меру следующим образом. Пусть хк, к = 1, К, — точки, сгенерированные случайным образом согласно плотности p(x). Определим меры этих точек как рд. = V{X = хк} = 1 /К, к = 1, К.
Пусть X = col (Xi,..., Xn-i) — случайный вектор, соответствующий этим мерам, т.е. V{X = хк} = рд., где случайные иодвекторы X имеют ту же размерность, что и X¿, i = 1, N — 1. Пусть Fk(x) — функция распределения случайного вектора X. Рассмотрим выборочную функцию распределения Fk (x), соответствующую случайному вектору X, реализация которой есть Fk (x). В соответствии с теоремой Гливенко - Кантелли [9] имеет место сходимость
FK(x) п'н'>F(x) при K — оо для всех x (п.н. — почти наверное), где F(x) — функция распределения случайного вектора X.
Докажем следующее утверждение.
Лемма. Пусть случайный вектор X = col (Xi,...,Xn -1) имеет дискретное 'распределение Fk(x). Тогда существуют детерминированные функции /¿(Xi) такие, что
Г{Хг = МХг)} = 1, i = 2,N — 1.
Доказательство леммы приведено в Приложении.
Сформулируем утверждение, в соответствии с которым N-этапная задача сводится к двухэтапной задаче. С этой целью будем пользоваться определением, введенным в [6].
Определение 1. Две задачи оптимизации будем считать эквивалентными, если:
1) либо обе эти задачи имеют допустимые решения (с конечными значениями целевых функций), либо обе не имеют таких решений;
2) если эти задачи имеют допустимые решения, то оптимальные значения их целевых функций (конечные или бесконечные) совпадают;
3) если оптимальные значения их целевых функций конечны, то эти значения в обеих задачах либо достигаются, либо не достигаются;
4) если оптимальные значения целевых функций достигаются, то по оптимальному решению одной задачи с помощью явно описанного алгоритма указывается оптимальное решение другой задачи;
5) если оптимальные значения целевых функций конечны, но не достигаются, то по оптимизирующей последовательности стратегий одной задачи по явно описанному алгоритму указывается оптимизирующая последовательность для другой задачи.
Далее везде будем понимать эквивалентность в смысле определения 1.
Теорема 1. N-этапная задача в априорной постановке (2.5) с дискретным распределением Fk (x) случайного вектора X эквивалентна в смысле
определения 1 двухэтапной .задаче стохастического программирования специального вида.
Доказательство теоремы 1 приведено в Приложении.
Замечание 2. Поскольку критерием в поставленной задаче является квантиль функции потерь, то получение решения такой задачи в пространстве функций оказывается достаточно сложным. А как уже отмечалось, метод динамического программирования, сводящий задачу оптимизации в функциональном пространстве к последовательному решению задач математического программирования в конечномерном пространстве, для квантиль-ного критерия неприменим [2]. Благодаря описанной схеме дискретизации меры удается свести многоэтапную задачу стохастического программирования к двухэтапной задаче, которая уже изучена в [4], правда, в более частном случае. Структура ограничений полученной двухэтапной задачи повторяет структуру ограничений исходной задачи, кроме то
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.