Автоматика и телемеханика, № 2, 2012
© 2012 г. А.В. НАУМОВ, канд. физ.-мат. наук, И.М. БОБЫЛЕВ (Московский авиационный институт)
О ДВУХЭТАПНОЙ ЗАДАЧЕ СТОХАСТИЧЕСКОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С КВАНТИЛЬНЫМ КРИТЕРИЕМ И ДИСКРЕТНЫМ РАСПРЕДЕЛЕНИЕМ СЛУЧАЙНЫХ ПАРАМЕТРОВ1
Рассматривается двухэтапная задача стохастического линейного программирования с дискретным распределением вектора случайных параметров. На основе доверительного метода и теорем двойственности доказывается свойство непрерывности функции квантили по стратегии, формулируются достаточные условия существования решения, строится алгоритм нахождения гарантирующего решения. Для скалярного случая приводится детерминированный эквивалент рассматриваемой задачи в виде задачи линейного программирования.
1. Введение
Двухэтапные задачи стохастического программирования являются предметом активных исследований в последние 30 лет, так как математические модели, построенные на базе двухэтапных задач, хорошо описывают многочисленные прикладные задачи технического и особенно экономического характера.
По сути, двухэтапные задачи являются частным случаем двухуровневых задач математического программирования в оптимистической постановке [1, 2], где критерий задачи лидера является суммой функции, не зависящей от стратегии последователя, и оптимального значения критерия в задаче последователя, являющейся функцией от стратегии лидера.
Однако двухуровневые задачи в стохастической постановке [3] к настоящему времени слабо изучены.
В данной работе рассматривается математическая постановка двухэтапной задачи стохастического программирования с квантильным критерием, которая позволяет получать гарантированный по вероятности результат.
Рассматриваемая постановка задачи моделирует ситуацию, когда необходимо принимать решения до реализации отдельных условий, что заставляет разбивать процесс планирования на два этапа. На первом этапе выбирается предварительный план, позволяющий провести необходимые подготовительные работы. На втором этапе производится корректировка предварительного плана по факту возникновения реализаций случайных параметров.
Важным классом двухэтапных задач стохастического программирования являются линейные двухэтапные задачи.
По виду критериальной функции двухэтапные задачи стохастического программирования можно разделить на два класса: с целевой функцией в форме математического ожидания и с целевой функцией в форме квантили (задачи квантильной оптимизации).
1 Работа выполнена при поддержке Российского фонда фундаментальных исследований (проект №11-07-00315-а) и государственного финансирования целевых программ "Научные и научно-педагогические кадры инновационной России" (Мероприятие 1.2.2 Госконтракт №14.740.11.1128).
Классическая постановка двухэтапной задачи стохастического линейного программирования с критерием в форме математического ожидания выглядит следующим образом:
cju + MX [Ф(и,Х)] ^ min
u
при ограничениях:
A\u = bi, u > 0.
Здесь u G Rn является стратегией первого этапа, ci G Rn, bi G Rl, Ai G Rlxn - детерминированные векторы и матрицы, являющиеся параметрами задачи первого этапа, случайный вектор X является совокупным случайным вектором, состоящим из элементов случайных параметров задачи второго этапа C2(w), A2(w), B2(w), h-2(w), заданных на одном и том же пространстве элементарных событий, имеющих некоторое совместное распределение и реализации соответственно c2 G Rk, B2 G Rmxk, A2 g Rmxn, h2 G Rm. Величина MX [Ф(и,Х)] представляет собой математическое ожидание оптимального значения критерия задачи второго этапа, имеющей вид:
Ф(и, x) = min c^y y
при ограничениях:
В2У = h2 - A2U, У > 0,
где y G Rk - стратегия задачи второго этапа, а вектор x, составленный из элементов c2, A2, В2, h2, является реализацией случайного вектора X.
Если определить функцию ^>(u) = Mx [Ф(и,Х)], то детерминированный эквивалент исходной двухэтапной задачи выглядит следующим образом:
cju + f(u) ^ min,
iu
Ai u = bi , u ^ 0.
Линейные двухэтапные задачи с критерием в форме математического ожидания достаточно хорошо изучены. В [4] исследованы их качественные свойства, там же предложен эффективный метод (L-shaped метод) решения задач в подобной постановке.
Для получения гарантированного по вероятности результата в задачах двухэтапной структуры используют квантильный критерий. Впервые двухэтапные задачи стохастического линейного программирования с квантильным критерием были рассмотрены в [5]. Там же были приведены априорная и апостериорная постановки задач данного класса, доказана их эквивалентность и представлены достаточные условия существования и единственности решения задач с гауссовским распределением вектора случайных параметров.
Эффективным способом решения задач квантильной оптимизации на сегодняшний день является применение доверительного метода [6], позволяющего путем рассмотрения произвольного доверительного множества получать оценку сверху оптимального значения критерия. Качество такой оценки напрямую зависит от структуры доверительного множества, и в случае рассмотрения оптимального доверительного множества метод дает точное решение задачи.
На основе доверительного метода в [7-9] получены гарантирующие решения целого ряда прикладных задач двухэтапной квантильной оптимизации.
Данная работа непосредственно опирается на доверительный метод [6]. Рассматривается двухэтапная задача стохастического линейного программирования с дискретным распределением вектора случайных параметров. Целью работы является исследование свойств этой задачи и разработка алгоритма, позволяющего эффективно находить гарантирующее решение задач рассматриваемого класса, т.е. допустимое решение, на котором достигается качественная верхняя оценка минимального значения критерия.
Полученные результаты могут быть использованы для решения задач авиационной и космической тематики, описанных в [10] ив [11, 12].
2. Постановка задачи
Пусть X - дискретный случайный вектор с конечным числом возможных реализаций х £ Q = {ж* (Е Rm, г = 1,L} и заданными вероятностями реализаций Р{Л" = = ж'} = pi, i = 1, L.
Обозначим через U множество допустимых стратегий первого этапа.
(2.1) U = {и : Avu > Ьь Uj > 0, j =
где Ai G Rlxn, Ъ\ G Rl, u G Rn. В дальнейшем будем считать U выпуклым компактом. Для этого необходимо и достаточно [13, с. 15], чтобы конус рецессивных направлений для множества U состоял только из нулевого вектора:
0 +U = {и g Rn : Аги > 0} = {0},
где 0 £ Rn - нулевой вектор.
Пусть P{-} - вероятностная мера, порожденная распределением случайного вектора X. Рассмотрим функцию вероятности
(2.2) Pv(u) 4 Р{Ф(и,X) < и функцию квантили
(2.3) Фа(и) = min {<f : Pv(u) > а},
которая характеризует минимальный уровень оптимального значения Ф(и,Х) критериальной функции второго этапа, который не может быть превышен с заданной вероятностью а.
Задача второго этапа имеет вид:
{min {¿Ty}, Y '(x, u) = 0,
ver'(x,u) 2
Y'(x, u) = 0,
где У (ж, и) = {у £ Rk : yi Js 0, i = 1, Ar, Boy ;í ж — Aou} - множество допустимых стратегий задачи второго этапа, B2 - детерминированная матрица рекурсии размерности m х k, A2 - детерминированная матрица размерности m х n, c2 G Rk -детерминированный вектор коэффициентов критериальной функции задачи второго этапа.
Пусть c1 G Rn - вектор коэффициентов критериальной функции задачи первого этапа, тогда двухэтапная задача стохастического линейного программирования с квантильным критерием [5] может быть записана следующим образом:
(2.5) Ua = Arg min {cju + Фa(u)} .
ueu
При этом оптимальное значение критерия задачи имеет вид: (2.6) уа = cjua + Фа(иа), где Ua G Ua.
Будем предполагать, что решение этой задачи существует, т.е. Ua = 0. Достаточные условия существования решения этой задачи для дискретного распределения случайного вектора X будут приведены далее.
3. Исследование свойств задачи
Рассмотрим задачу, двойственную к задаче второго этапа (2.4):
) ДГ тах {(х - А2«0М , У = 0,
(3.1) Фци,х) = < ъеУ
I —то, V = 0,
где V = {г' £ Дт, г^ ^ 0, % = 1 , т, В^ у ^ со} - множество допустимых значений двойственных переменных. Из теории двойственности линейного программирования [14, с. 90] известно, что если V = 0 и У'(х, и) = 0 одновременно при заданных и и х, то —то < Ф1(и, х) = Ф(и,х) < то.
Определим множество К следующим образом:
(3.2) К1 = {и : У'(х,и) = 0 Ух е О}.
Согласно [15, с. 85] К есть выпуклое многогранное множество. Определим множество К2:
(3.3) к2 = ] и : тах{(х — А2и)Т«} < то Ух е О I .
уЕУ
Лемма 1. Если V = 0, то K = ссмотрим мно / -1 ... 0
Рассмотрим множество 0+V = {v G Дт, BBv < 0}, где B = ( B^ ), B G ß(m+fc)xm,
Ii
Ii £ Rm ' m. Пусть О1 € Rm - нулевой вектор. Тогда справед-
у 0 ••• —1
ливо следующее утверждение.
Лемма 2. Если 0+У = {о1}., V ^ 0, 0+И = {0}., то V с К\.
Рассмотрим теперь произвольную целевую функцию Ф^и, х). Пусть Ф^(и) = = тт{<^> : Р{Ф1(и,Х) ^ <£>} ^ а}, тогда справедлива следующее утверждение.
Утверждение 1. Если случайный вектор X имеет дискретное распределение с конечным числом реализаций х1 £ Нт, г = 1, Ь, а функция Ф1(ы, х) непрерывна по и £ и С Нп при любом х1, г = 1 ,Ь, то для любого а £ (0; 1) функция квантили Ф^ (и) непрерывна на V.
Данное утверждение является прямым следствием результата, полученного в [6, с. 99], так как в случае дискретного распределения случайного вектора X с конечным числом реализаций дополнительные условия, отличающие теорему [6, с. 99] от сформулированного утверждения, автоматически выполнены. Однако в Приложении приведен более простой, по мнению авторов, способ доказательства утверждения для рассматриваемого частного случая.
Сформулированные утверждения позволяют доказать теорему о существовании решения задачи (2.5).
Теорема 1. Если 0+1/ = {0 }, V ф 0, 0+и = {0} и дискретная случайная величина X имеет конечное число реализаций х1, г = 1, Ь, то для любого а £ (0; 1) справедливо, что V а = 0 и —то < у а < +то.
В случае, когда х е Д1, удается записать детерминированный эквивалент задачи (2.5). Рассмотрим следующую задачу:
^ У1) = а^шп(сТи +
и,У
А2и + В2У > ха, (3.4) А1и > 61, и > 0, У >
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.