Автоматика и телемеханика, № 1, 2014
Стохастические системы, системы массового обслуживания
© 2014 г. С.В. ИВАНОВ
(Московский авиационный институт)
ДВУХУРОВНЕВЫЕ ЗАДАЧИ СТОХАСТИЧЕСКОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С КВАНТИЛЬНЫМ КРИТЕРИЕМ1
Предлагается постановка двухуровневой задачи стохастического линейного программирования с квантильным критерием. Исследуется свой-ствс> непрерывности критериальной функции. Доказывается теорема существования решения. Предлагается детерминированный эквивалент задачи для случая скалярного случайного параметра. Приводится эквивалентная задача в виде двухэтапной задачи стохастического программирования с равновесными ограничениями и квантильным критерием. Для случая дискретного распределения случайных параметров задача сводится к смешанной задаче линейного программирования. Приводятся результаты численных экспериментов.
1. Введение
Задачи двухуровневой оптимизации возникают при моделировании систем, процесс принятия решения в которых имеет многоуровневую структуру. Предполагается участие двух игроков: лидера и последователя. Последователь принимает решение, зная стратегию лидера. Лидер учитывает оптимальную стратегию последователя при выборе своей стратегии. Впервые данная задача была рассмотрена Штакельбергом при изучении моделей рынка [1], однако интенсивное изучение данных задач приходится на последние три десятилетия. Основные результаты теории двухуровневых задач содержатся в [2-6].
Среди приложений задач двухуровневого программирования можно выделить иерархические модели экономики [7], транспортную задачу [8], задачу размещения предприятий [9] и модели алюминиевой промышленности [10].
Линейная задача двухуровневого программирования в оптимистической постановке имеет вид
(1) cfu + fTy* — min ,
u&U, y*€Y*(u)
1 Работа выполнена при поддержке Российского фонда фундаментальных исследований (проекты №№ 11-07-00315а, 12-07-13108-офи-м-РЖД) и государственного финансирования целевых программ «Научные и научно-педагогические кадры инновационной России» (Мероприятие 1.2.2, Госконтракт № 14.740.11.1128).
Y*(u) = Arg min {c?y | A2u + B2y ^ g, y ^ 0} ,
y
u € Rn — стратегия лидера, y* € Rk — оптимальная стратегия последователя, A2 € Rmxn, B2 € Rmxk, ci € Rn, c2 € Rk, f € Rk, g € Rm, U = {u € Rn | Aiu < ^ bi} — множество допустимых стратегий лидера, A1 € R1xn, b1 € R1. Оп-тимистичность постановки (1) заключается в том, что лидер ориентируется на наилучшую для себя оптимальную стратегию последователя. Также возможна пессимистическая постановка задачи, в которой лидер принимает во внимание наихудшую для себя оптимальную стратегию последователя.
С помощью условий дополняющей нежесткости задача (1) может быть сведена к задаче математического программирования с равновесными ограничениями:
cTu + f Ty — min
u€U,y€Rk, AeRm
при ограничениях
А2п + Б2у ^ д, ВТЛ < С2, ХТ(А2п + В2У - д)= 0, уТ(вТЛ - С2) = 0, у ^ 0, Л ^ 0.
Решение данной задачи требует привлечения методов невыпуклой оптимизации. Однако при некоторых предположениях полученная задача может быть сведена к смешанной задаче линейного программирования [11].
В [12] предлагался метод сведения задачи (1) к параметрической задаче линейного программирования с дальнейшей оптимизацией по скалярному параметру.
Разработке численных методов решения задачи (1), основанных на методах невыпуклой оптимизации, посвящены работы [13-15].
Стохастическая постановка задачи двухуровневого программирования была предложена в [16]. Там же предложен алгоритм поиска локального оптимума. В [17] изучены свойства данной задачи. Изучению стохастической двухуровневой задачи, в которой стратегия последователя выбирается, исходя из условия минимума критериальной функции в форме математического ожидания, посвящена и работа [18]. В [18] приведены достаточные условия существования решения поставленной задачи, разработан алгоритм поиска локального оптимума и даны приложения стохастической постановки задачи двухуровневого программирования к задачам телекоммуникации.
Для поиска стратегии, обеспечивающей гарантированный по вероятности результат, в стохастическом программировании используется квантильный критерий [19], являющийся уровнем целевой функции, непревышение которого гарантируется с заданной вероятностью. Частный случай двухуровневой задачи с квантильным критерием рассматривался в [20] в контексте задачи проектирования сетей с заданным уровнем надежности. Для решения задачи был предложен генетический алгоритм. В [21] изучена двухуровневая зада-
5* 131
ча в стохастической постановке с квантильным критерием для гауссовского распределения с неопределенным математическим ожиданием.
Комбинированная двухэтапная двухуровневая постановка задачи стохастического программирования с квантильным критерием использовалась для моделирования сложных экономических систем. На основе такой постановки разработаны модель для оптимизации железнодорожных перевозок [22] и модель для планирования инвестиций в развитие отраслей производства [23].
В данной работе изучается двухуровневая задача стохастического линейного программирования с квантильным критерием для произвольного распределения случайных параметров. В случае дискретного распределения случайных параметров предлагается метод сведения данной задачи к смешанной задаче линейного программирования. Методы сведения одноэтапных и двухэтапных задач стохастического программирования с квантильным критерием к задачам смешанного линейного программирования рассматривались в [24-27].
Оказывается, что класс двухуровневых задач стохастического программирования с критерием в форме математического ожидания может рассматриваться как расширение класса двухэтапных задач стохастического программирования [28, 29]. Аналогично класс двухуровневых задач стохастического программирования с квантильным критерием может рассматриваться как расширение класса двухэтапных задач стохастического программирования с квантильным критерием [30].
2. Постановка задачи
Пусть X — случайный вектор с реализациями x € Rm, u — стратегия лидера. Задача последователя формулируется в виде
(2) cjy ^ min
y£Y (u,x)
где Y(u, x) = {y € Rk | A2u + B2y ^ x, y ^ 0} — множество допустимых стратегий задачи последователя, A2 € Rmxn — технологическая матрица, B2 € Rmxk — матрица рекурсии, c2 € Rk — вектор коэффициентов линейной функции потерь последователя. Обозначим через Y*(u, x) = Arg min cTy
y€Y (u,x)
множество оптимальных решений задачи (2). Если для пары (u, x) не существует решения задачи (2), т.е. Y(u, x) = 0 либо оптимальное значение целевой функции в (2) не ограничено снизу, то будем предполагать, что Y*(u, x) = = 0.
Определим функцию потерь лидера при реализации стратегии последователя:
( min fV, если Y*(u,x)= 0,
(3) $(u,x) й) y*6Y*(u,x)
если Y*(u, x) = 0,
где f € Rk — вектор коэффициентов линейной функции потерь лидера, связанных со стратегией последователя.
Рассмотрим функцию квантили
(4) $«(u) 4 min{^> | P{$(u, X) < ^ a},
где a — фиксированный уровень надежности, P{-} — вероятностная мера, порожденная распределением случайного вектора X.
Двухуровневая задача стохастического линейного программирования с квантильным критерием в оптимистической постановке формулируется в виде
(5) c?u + $a(u) — min,
v 7 1 aw ueu
где ci € Rn — вектор коэффициентов линейной функции потерь лидера, U = 4 {u € Rn | A1u ^ bi} — множество допустимых стратегий лидера, A1 € R1xn, bi € R1.
Заметим, что если целевые функции лидера и последователя совпадают (т.е. c2 = f), то задача (5) является двухэтапной задачей стохастического программирования с квантильным критерием [30, 31].
Класс прикладных задач, описываемых данной моделью, достаточно широк. Приведем одну из возможных экономических интерпретаций.
Рассмотрим задачу планирования производства. Лидером является компания, которая производит n различных типов продукции. Лидер определяет объем производства каждого типа продукции. Для производства продукции требуется т видов ресурсов. Объемы ресурсов Xj, г = 1, т, доступных лидеру, предполагаются случайными и неизвестными лидеру во время выбора стратегии. В случае нехватки имеющихся ресурсов лидер обращается к последователю, который может произвести дополнительные ресурсы по более высокой цене. Пусть uj — объем производства j-го типа продукции; yi — объем производства последователем г-го ресурса; A-2{i,j) — объем г-го ресурса, требуемый для производства единицы продукции j-го типа, г = 1, т, j = 1, щ cij — стоимость единицы продукции j-го типа; fi — стоимость дополнительно произведенной последователем единицы i-го ресурса; c2i — издержки последователя при производстве единицы i-го ресурса. Тогда задачу планирования производства можно записать в виде
—c?u + $a(u) — min,
1 ueu
где $a(u) задается формулами (2)-(4), а Y(u,ж) = {y € Rk | A2u ^ x + + y, A3y ^ Ьз, y ^ 0}. Матрица A3 и вектор b3 задают возможные дополнительные ограничения на стратегию последователя. Первое слагаемое в целевой функции данной задачи представляет собой доход, взятый с обратным знаком, а второе слагаемое — издержки, непревышение которых гарантируется с заданным уровнем вероятности a.
3. Свойства задачи
Введем обозначение
W = {(и, ж) | У (и, ж) = 0}.
Так как множество W является проекцией выпуклого замкнутого полиэдрального множества {(и, ж, у) | А2и + В2у ^ ж, ж ^ 0} на подпространство переменных (и,ж), то W — выпуклое замкнутое полиэдральное множество.
Справедлива следующая теорема.
Теорема 1. Если существует пара (и,ж) € W такая, что |Ф(и, ж)| < < , то |Ф(и, ж)| < для всех (и,ж) € W и функция Ф(-) — липшицева на множестве W,
Доказательство теоремы 1 приведено в Приложении.
В доказанной теореме 1 утверждается свойство Липшица для функции на множестве W. Явный вид данного множества указать сложно. Поэтому получим следствие из теоремы 1, обеспечивающее свойство Липшица для функции Ф(-) на всем пространстве Мга х Мт.
Следствие 1. Пусть V = { Л € Мт+1 | (-С2 | ^2)Т Л < /, Л ^ 0} = 0, 0+У 4 { Л € Мт+1 | (-С2 | В2)Т Л < 0, Л ^ 0} = {0}, VI = { Л € Мт | ВТ Л < ^ с2, Л ^ 0} = 0, где 0 — нулевой
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.