Стохастическое программирование

Стохастическое программирование (англ. stochastic programming) — раздел математического программирования, разрабатывающий модели и методы решения оптимизационных задач в условиях неопределённости, когда некоторые параметры модели не известны точно, а представлены как случайные величины с известными или оценёнными вероятностными распределениями.

В отличие от детерминированных задач, где все данные считаются заданными константами, стохастическое программирование ставит целью найти решение (или политику принятия решений), которое является оптимальным в некотором статистическом смысле. Чаще всего это означает минимизацию или максимизацию математического ожидания целевой функции. Ключевая идея состоит в том, чтобы найти такую политику принятия решений, которая будет наилучшей «в среднем» по всем возможным реализациям случайных параметров, что особенно актуально для задач, где решения принимаются многократно в схожих условиях (например, в управлении запасами или энергосистемами).

Математическая постановка задачи

В общем виде задача стохастического программирования может быть сформулирована как: $\underset{x\in X}{\min }\mathbb{𝔼}[f(x,\xi )]$ где:

• $x$ — вектор управляющих переменных (решений), которые необходимо определить.
• $X$ — множество допустимых решений для $x$, определяемое детерминированными ограничениями.
• $\xi$ — случайный вектор, представляющий неопределённые параметры задачи (например, спрос, цены, погодные условия).
• $f(x,\xi )$ — целевая функция, значение которой зависит как от принятого решения $x$, так и от реализации случайного вектора $\xi$.
• $\mathbb{𝔼}[\cdot ]$ — оператор математического ожидания, вычисляемый по распределению вероятностей вектора $\xi$.

Важнейшим принципом, лежащим в основе многоэтапных стохастических моделей, является принцип непредвосхищения (англ. non-anticipativity principle). Он гласит, что решения, принимаемые на любом этапе, могут зависеть только от информации, доступной к этому моменту, и не могут «заглядывать в будущее».

Двухэтапная задача с правом компенсации

Наиболее распространённой моделью является двухэтапная задача с правом компенсации (англ. two-stage stochastic program with recourse). Процесс принятия решений разделён на два этапа:

1. Первый этап: Принимается решение «здесь и сейчас» (here-and-now) — определяется вектор $x$. Это решение должно быть принято до того, как станет известна конкретная реализация случайного вектора $\xi$.
2. Второй этап: После того как случайное событие произошло, принимается корректирующее или компенсационное решение (recourse decision) — вектор $y(\xi )$, направленное на минимизацию негативных последствий или использование благоприятных возможностей, возникших в результате сочетания решения первого этапа $x$ и исхода $\xi$.

Математически двухэтапная задача стохастического линейного программирования формулируется следующим образом: $\underset{x\in {\mathbb{ℝ}}^{n_1}}{\min }\{c^{T}x+{\mathbb{𝔼}}_{\xi }[Q(x,\xi )]\}$ при ограничениях первого этапа: $Ax=b,x\ge 0$. Здесь $Q(x,\xi )$ — функция компенсации (recourse function), представляющая собой оптимальное значение задачи второго этапа: $Q(x,\xi )=\underset{y\in {\mathbb{ℝ}}^{n_2}}{\min }\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ где $\xi$ — случайный вектор, включающий в себя параметры $q(\xi ),T(\xi )$ и $h(\xi )$; а $c,A,b$ и $W$ — детерминированные параметры.

Ключевые свойства и теоремы

• Выпуклость: Одним из фундаментальных результатов теории является то, что для двухэтапной задачи стохастического линейного программирования ожидаемая функция компенсации $Q(x)={\mathbb{𝔼}}_{\xi }[Q(x,\xi )]$ является выпуклой функцией. Это свойство имеет огромное значение, так как оно гарантирует, что общая задача первого этапа является задачей выпуклого программирования, для которой существуют эффективные методы решения и глобальный оптимум совпадает с локальным.
• Детерминированный эквивалент: Если случайный вектор $\xi$ имеет конечное число возможных реализаций (сценариев) ${\xi }_1,\dots ,{\xi }_K$ с вероятностями $p_1,\dots ,p_K$, то задачу стохастического программирования можно переформулировать в виде одной большой детерминированной задачи оптимизации. В этом случае математическое ожидание заменяется взвешенной суммой по всем сценариям. Однако размер этой задачи растёт линейно с числом сценариев, что приводит к «проклятию размерности» и делает такой подход вычислительно неразрешимым для большого числа сценариев.

Сравнение с робастной оптимизацией

Стохастическое программирование является одним из нескольких подходов к оптимизации в условиях неопределённости. Его ключевое отличие от робастной оптимизации заключается в способе моделирования неопределённости и критерии оптимальности.

Сравнение подходов к оптимизации в условиях неопределённости

Критерий	Стохастическая оптимизация	Робастная оптимизация
Представление неопределённости	Параметры — случайные величины с известным вероятностным распределением	Параметры принадлежат заданному множеству неопределённости, распределение не требуется
Критерий оптимальности	Оптимизация математического ожидания целевой функции	Оптимизация в наихудшем сценарии (минимакс)
Характер решения	Политика, оптимальная «в среднем», может быть недопустимой для редких сценариев	Решение, гарантированно допустимое для всех реализаций; может быть консервативным

Примеры

• Задача газетчика (англ. newsvendor problem): Классическая задача управления запасами, где продавец должен решить, какое количество товара закупить, не зная точного будущего спроса. Решение балансирует между риском потерь от излишков и риском упущенной выгоды от дефицита.
• Задача фермера: Фермер решает, сколько акров земли выделить под разные культуры на общей площади, не зная будущей погоды, которая влияет на урожайность. После того как погода становится известной, фермер может предпринять корректирующие действия (например, продать излишки или докупить недостающий урожай на рынке).

См. также

• Математическое программирование
• Исследование операций
• Робастная оптимизация
• Динамическое программирование
• Теория управления