Стохастическое программирование: двухэтапные модели и оптимизация с учетом рисков

Наиболее фундаментальной и широко применяемой концепцией в стохастическом программировании является двухэтапная модель с recourse (корректирующими действиями). Логика этой модели идеально отражает реальный процесс принятия управленческих решений. На первом этапе (здесь и сейчас) лицо, принимающее решение, должно зафиксировать базовые параметры системы до того, как случайные факторы станут известны. Например, фермер должен решить, сколько гектаров засеять пшеницей, кукурузой и свеклой до того, как он узнает, каким будет летний сезон (дождливым или засушливым) и какими будут осенние закупочные цены. Эти первоначальные переменные называются переменными первого этапа и не могут зависеть от исходов случайных величин.

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

Для оценки эффективности применения сложных стохастических алгоритмов математики используют два ключевых аналитических показателя: Ценность стохастического решения (Value of Stochastic Solution, VSS) и Ожидаемая ценность идеальной информации (Expected Value of Perfect Information, EVPI). VSS вычисляется как разница между ожидаемыми затратами при использовании решения детерминированной задачи (где случайные величины заменены их средними арифметическими) и затратами при использовании истинного стохастического оптимума. Чем выше VSS, тем опаснее игнорировать дисперсию данных. EVPI показывает максимальную сумму денег, которую корпорации было бы выгодно заплатить за абсолютный прогноз будущего (например, за идеальный прогноз погоды на год вперед).

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