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

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

,

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

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

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

Введение

Математические модели, основанные на задачах двухуровневого программирования, адекватно описывают экономические системы, процесс принятия решения в которых имеет иерархическую структуру. В таких системах предполагается участие двух игроков: лидера и последователя. Последователь выбирает свою стратегию, зная стратегию лидера. Лидер учитывает оптимальную стратегию при выборе своей стратегии. Классическая постановка задачи описана в [1]. Изучению данных задач посвящено большое количество работ, среди которых можно выделить [2–3].

Стохастическая постановка двухуровневой задачи с критериальной функцией в форме математического ожидания описана в [4]. В [5] приведены прикладные задачи, основанные на указанной постановке, а также показано, что двухуровневые задачи в стохастической постановке являются обобщением двухэтапных задач [6] стохастического программирования.

Для адекватного учёта риска в двухуровневой задаче стохастического программирования может быть применён квантильный критерий. Квантильный критерий [7] представляет собой потери, непревышение которых гарантируется с заданной вероятностью.

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

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

Предполагается участие на рынке двух игроков: собственника производства (лидера) и конкурента, производящего аналогичную продукцию (последователя).

Будем считать, что производство состоит  из отраслей, выпускающих различную продукцию. Пусть – случайный вектор размерности , каждая координата вектора , , является случайным спросом на продукцию соответствующей отрасли производства. Пусть – реализация , –  координаты реализации, .

Лидер принимает решение в два этапа. Для моделирования принятия решения лидером используется двухэтапная задача стохастического линейного программирования с квантильным критерием [8].

Переменной первого этапа (стратегией лидера на первом этапе) является  вектор , с координатами , , где является объёмом инвестирования в -ю отрасль производства.

Пусть – оптимальное значение критериальной функции задачи второго этапа (доход лидера, взятый с обратным знаком, или потери). Функция квантили оптимального значения критериальной функции задачи второго этапа имеет вид

                       (1)

где – вероятностная мера, порождённая распределением случайного вектора , – выбранный уровень надёжности.

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

       (2)

где – минимальный объём инвестирования, необходимый для поддержания производства  -й отрасли на прежнем уровне, – максимально возможный объём инвестирования, – доходность безрискового финансового актива. Таким образом, критериальная функция в (2) показывает, насколько эффективней вложение инвестиций в производство по сравнению с альтернативными возможностями вложения инвестиций.

Переменной второго этапа (стратегией лидера на втором этапе) является вектор с координатами , , где является ценой на продукцию -й отрасли лидера. Пусть –  максимально допустимая цена на продукцию -й отрасли; – объём производства лидером продукции -й отрасли, где – некоторые константы; – объём производства последователем продукции -й отрасли.

Пусть – цена на продукцию -й отрасли, установленная последователем, – множество оптимальных решений задачи последователя.

Потери -й отрасли производства лидера имеют следующий вид:

       (3)

В (3) предполагается, что в случае  равенства цен покупатель предпочитает продукцию конкурента, то есть рассматривается наихудший для лидера сценарий.

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

       (4)

Задача лидера (4) сформулирована в оптимистической постановке [1]. Это значит, что последователь из своих оптимальных стратегий выбирает  наиболее благоприятную для лидера. К сожалению, решение задачи лидера в пессимистической постановке не существует.

Потери -й отрасли производства последователя имеют следующий вид:

       (5)

где – цена на продукцию, установленная последователем (стратегия последователя).

Сформулируем задачу последователя:

                       (6)

Методы решения задачи

Структура целевых функций задачи второго этапа для лидера и задачи последователя позволяет в аналитическом виде найти решения этих задач. Значит, задача (2) может быть сведена к одноэтапной задаче стохастического программирования с квантильным критерием. Для поиска её решения могут быть применены методы, основанные на вычислении квазиградиента критериальной функции [7]. Верхние оценки решения могут быть найдены с помощью доверительного метода [7].

В случае одной отрасли производства свойства монотонности и непрерывности оптимального значения критериальной функции задачи второго этапа позволяют построить детерминированный эквивалент задачи (2) и найти точное решение.

В работе [9] рассматривалась аналогичная задача. В предположении о постоянных ценах и дискретного распределения спроса, задача была сведена к смешанной задаче линейного программирования большой размерности.

Выводы

Рассмотрена математическая модель распределения инвестиций в развитие производства. Для математического моделирования применён новый класс задач двухуровневого стохастического программирования с квантильным критерием. Приведены подходы к решению поставленной задачи.

Литература

1. Dempe S. Bilevel Programming - A Survey // Preprint TU Bergakademie Freiberg Nr. 2003-11, Fakultдt fьr Mathematik und Informatik, 2003.

2. Bard J. Practical Bilevel Optimization: Algorithms and Applications, Kluwer Academic Publishers, Dordrecht, 1998.

3. Верхние оценки для целевых функций дискретных задач конкурентного размещения предприятий // Дискретн. анализ и исслед. опер. 2008. Т. 15. № 4. С. 3–24.

4. Werner A. S. Bilevel Stochastic programming problems: analysys and application to telecommunications // Dr. ing. thesis, 2004. Section of Investment, Finance and Accounting, Dept of Industrial Economics and Technology Management, NUST, Norway.

5. Kleywegt A. J. Challenging Applications of Stochastic Programming // Stochastic Programming SPXII Conference Halifax, 2010.

6. Birge J. R., Louveaux F. Introduction to stochastic programming. - Springer-Verlag, N. Y., 1997.

7. , Задачи стохастического программирования с вероятностными критериями. – М.: Физматлит, 2009.

8. , Двухэтапные задачи квантильного линейного программирования // Автоматика и телемеханика. 1995. №1. С. 83-93.

9. , Задача распределения инвестиций в развитие отраслей наземного космического комплекса // Электронный журнал «Труды МАИ». 2012. №50.

on quantile formulation of bilevel programming problem for The problem of the investment distribution

Ivanov S. V., Naumov A. V.

Moscow Aviation Institute (National Research University), *****@***ru, *****@***ru

We consider the problem of the investment distribution in bilevel stochastic formulation with the quantile criteria.

Кеу words: stochastic programming, bilevel problem, quantile criteria.