Том 25, номер 4, 2018 г., Стр. 27-45

УДК 519.8
Иванов С. В.
Задача двухуровневого программирования со случайными параметрами в целевой функции последователя

Аннотация:
Изучается двухуровневая задача стохастического программирования с квантильным критерием. Задачи двухуровневого программирования можно рассматривать как формализацию процесса взаимодействия двух сторон. Первой стороной является лидер, принимающий решение первым, а вторая сторона (последователь) принимает решение, зная стратегию лидера и реализацию случайных параметров задачи. Предполагается, что задача последователя при заданной реализации случайных параметров и стратегии лидера линейна. Коэффициенты целевой функции последователя считаются случайными. Целью лидера является минимизация функции квантили потерь, зависящей от его собственной стратегии и оптимальной стратегии последователя. Показано, что задача последователя с вероятностью единица имеет единственное решение, когда случайные параметры имеют абсолютно непрерывное распределение. Доказана полунепрерывность снизу функции потерь, и получены условия существования решения задачи. Приведён пример, демонстрирующий, что непрерывность функции квантили не гарантируется. Сформулирована выборочная аппроксимация задачи. Приведены условия сходимости выборочной аппроксимации задачи к исходной задаче при увеличении объёма выборки по стратегии оптимизации и по значению целевой функции. Показано, что условия сходимости выполнены для почти всех значений уровня надёжности. Рассмотрен модельный пример определения размера налоговой ставки, для которого проведены численные эксперименты.
Табл. 1, ил. 2, библиогр. 13.

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

DOI: 10.17377/daio.2018.25.596

Иванов Сергей Валерьевич ¹
1. Московский авиационный институт (национальный исследовательский университет)
Волоколамское шоссе, 4, 125993 Москва, Россия
е-mail: sergeyivanov89@mail.ru

Статья поступила 16 октября 2017 г.
Исправленный вариант — 19 апреля 2018 г.

Литература

[1] Иванов С. В., Кибзун А. И. О сходимости выборочных аппроксимаций задач стохастического программирования с вероятностными критериями // Автоматика и телемеханика. 2018. № 2. С. 19–35.

[2] Иванов С. В., Морозова М. В. Стохастическая задача конкурентного размещения предприятий с квантильным критерием // Автоматика и телемеханика. 2016. № 3. С. 109–122.

[3] Кибзун А. И., Кан Ю. С. Задачи стохастического программирования с вероятностными критериями. М.: Физматлит, 2009. 372 с.

[4] Ширяев А. Н. Вероятность-1. М.: МЦНМО, 2017. 552 с.

[5] Bard J. F. Practical bilevel optimization: Algorithms and applications. Dordrecht: Kluwer Acad. Publ., 1998. 476 p.

[6] Chen A., Kim J., Zhou Z., Chootinan P. Alpha reliable network design problem // Transp. Res. Rec., J. Transp. Res. Board. 2007. Vol. 2029. P. 49–57.

[7] Dempe S. Foundations of bilevel programming. Dordrecht: Kluwer Acad. Publ., 2002. 309 p.

[8] Dempe S., Ivanov S., Naumov A. Reduction of the bilevel stochastic optimization problem with quantile objective function to a mixed-integer problem // Appl. Stoch. Models Bus. Ind. 2017. Vol. 33, No. 5. P. 544–554.

[9] Dempe S., Kalashnikov V., Pérez-Valdés G. A., Kalashnykova N. Bilevel programming problems: theory, algorithms and applications to energy network. Heidelberg; New York; Dordrecht; London: Springer, 2015. 325 p.

[10] Katagiri H., Uno T., Kato K., Tsuda H., Tsubaki H. Random fuzzy bilevel linear programming through possibility-based value at risk model // Int. J. Mach. Learn. Cybern. 2014. Vol. 5, No. 2. P. 211–224.

[11] Melnikov A., Beresnev V. Upper bound for the competitive facility location problem with quantile criterion // Discrete optimization and operations research. Proc. 9th Int. Conf. DOOR (Vladivostok, Russia, Sept. 19–23, 2016). Cham: Springer, 2016. P. 373–387. (Lect. Notes Comput. Sci.; Vol. 9869).

[12] Pagnoncelli B. K., Ahmed S., Shapiro A. Sample average approximation method for chance constrained programming: theory and applications // J. Optim. Theory Appl. 2009. Vol. 142. P. 399–416.

[13] Rockafellar R. T., Wets R. J.-B. Variational analysis. Heidelberg: Springer, 2009. 736 p.