С.В. Иванов, А.И. Кибзун. Выборочная аппроксимация двухэтапной задачи стохастического линейного программирования с квантильным критерием ... С. 134-143.

УДК 519.856

MSC: 90C15

DOI: 10.21538/0134-4889-2017-23-3-134-143

Работа выполнена при поддержке РФФИ (проект 17-07-00203А).

Рассматривается двухэтапная задача стохастического линейного программирования с квантильным критерием. В данной задаче стратегия первого этапа является детерминированной, а стратегия второго этапа выбирается по факту реализации случайных параметров задачи. Исследованы свойства задачи, доказана теорема о существовании ее решения, и построена для нее выборочная аппроксимация. Выборочная аппроксимация сведена к смешанной целочисленной задаче линейного программирования. Доказана теорема об их эквивалентности. Предложена процедура поиска оптимального решения аппроксимирующей задачи. Приведена теорема о сходимости дискретных аппроксимаций по значению критериальной функции и по стратегии оптимизации. Также рассмотрены случаи, не учитываемые в данной теореме.

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

Список литературы

1. Shapiro A., Dentcheva D., Ruszczynski A. Lectures on stochastic programming: Modeling and theory. MPS/SIAM Series on Optimization. 9. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 2009. 436 p.

2. Кибзун А. И., Наумов А. В. Двухэтапные задачи квантильного линейного программирования // Автоматика и телемеханика. 1995.  № 1. C. 83--93.

3. Норкин В. И., Кибзун А. И., Наумов А. В. Сведение задач двухэтапной вероятностной оптимизации с дискретным распределением случайных данных к задачам частично целочисленного программирования // Кибернетика и системный анализ. 2014. Т. 50, № 5. С. 34-48.

4. Artstein Z., Wets R.J.-B. Consistency of minimizers and the SLLN for stochastic programs // J. Convex Anal. 1996. Vol. 2, iss. 1/2. P. 1-17.

5. 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. doi: http://dx.doi.org/10.1007/s10957-009-9523-6.

6. Kibzun A.I., Ivanov S.V. Convergence of discrete approximations of stochastic programming problems with probabilistic criteria. Proc. 9th Internat. Conf. DOOR 2016 (Vladivostok, 2016), eds. Kochetov, Yu. et all., Ser. Theoretical Computer Science and General Issues, vol. 9869, pp. 525-537, Heidelberg: Springer, 2016. doi: http://dx.doi.org/0.1007/978-3-319-44914-2 .

7. Rockafellar R. T., Wets R.J.-B. Variational analysis. Berlin: Springer-Verlag, 2009. 736 p. doi: http://dx.doi.org/10.1007/978-3-642-02431-3 .

8. Еремин И.И. Линейная оптимизация и системы линейных неравенств. М.: Академия, 2007. 256 с.

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

10. Lepp R. Approximate solution of stochastic programming problems with recourse // Kybernetika. 1987. Vol. 23, iss. 6. P. 476-482.

Поступила 19.05.2017

Иванов Сергей Валерьевич

канд. физ.-мат. наук, доцент

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

e-mail: sergeyivanov89@mail.ru

Кибзун Андрей Иванович

д-р физ.-мат. наук, профессор

заведующий кафедрой теории вероятностей

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

e-mail: kibzun@mail.ru

English

S. V. Ivanov, A. I. Kibzun. Sample average approximation in the two-stage stochastic linear programming problem with quantile criterion.

The two-stage problem of stochastic linear programming with quantile criterion is considered. In this problem, the first stage strategy is deterministic and the second stage strategy is chosen when a realization of the random parameters is known. The properties of the problem are studied, a theorem on the existence of its solution is proved, and a sample average approximation of the problem is constructed. The sample average approximation is reduced to a mixed integer linear programming problem, and a theorem on their equivalence is proved. A procedure for finding an optimal solution of the approximation problem is suggested. A theorem on the convergence of discrete approximations with respect to the value of the objective function and to the optimization strategy is given.

We also consider some cases not covered in the theorem.

Keywords: stochastic programming, quantile criterion, sample average approximation, mixed integer linear programming.

The paper was received by the Editorial Office on May 19, 2017.

Sergei Valer'evich Ivanov, Cand. Sci. (Phys.-Math.), Moscow Aviation Institute (National Research University), Moscow, 125993 Russia, e-mail: sergeyivanov89@mail.ru

Andrei Ivanovich Kibzun, Dr. Phys.-Math. Sci., Prof., Head of a department, Moscow Aviation Institute (National Research University), Moscow, 125993 Russia, e-mail: kibzun@mail.ru