Введение

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

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

Распределение

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

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

Стохастическая линейная программа является частным случаем классической двухэтапной стохастической программы. Стохастический LP строится на основе набора многопериодных линейных программ (LP), каждая из которых имеет одинаковую структуру, но несколько иные данные. Двухпериодная LP, представляющая сценарий, может быть представлена в следующем виде: векторы и содержат переменные первого периода, значения которых необходимо определить сразу. Вектор содержит все переменные последующих периодов. Ограничения включают только переменные первого периода и одинаковы для всех сценариев. Остальные ограничения включают переменные более поздних периодов и в некоторой степени различаются в зависимости от сценария, отражая неопределенность относительно будущего. Важно отметить, что решение двухпериодной LP эквивалентно принятию сценария во втором периоде без учета неопределенности. Для учета неопределенностей во втором этапе необходимо присвоить вероятности различным сценариям и решить соответствующую детерминированную задачу.

Детерминированный эквивалент стохастической задачи

При конечном числе сценариев двухэтапные стохастические линейные программы могут быть смоделированы как большие задачи линейного программирования. Эта формулировка часто называется детерминированным эквивалентом линейной программы или сокращенно – детерминированным эквивалентом. (Строго говоря, детерминированный эквивалент – это любая математическая программа, которую можно использовать для вычисления оптимального решения на первом этапе, поэтому они существуют и для непрерывных распределений вероятностей, когда стоимость второго этапа можно представить в замкнутой форме.) Например, чтобы сформировать детерминированный эквивалент вышеуказанной стохастической линейной программы, мы присваиваем вероятность каждому сценарию. Затем мы можем минимизировать математическое ожидание целевой функции, при соблюдении ограничений для всех сценариев: у нас есть различный вектор переменных последующих периодов для каждого сценария. Переменные первого периода x и y одинаковы во всех сценариях, однако, поскольку решение для первого периода необходимо принять до того, как станет известен реализовавшийся сценарий. В результате ограничения, включающие только x и y, нужно задавать лишь однажды, а остальные ограничения – отдельно для каждого сценария.

Строительство сценария

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

Биологические применения

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

Экономические применения

Стохастическое динамическое программирование — полезный инструмент для понимания процесса принятия решений в условиях неопределенности. Накопление фондов капитала в условиях неопределенности — один из примеров; его часто используют экономисты, специализирующиеся на природных ресурсах, для анализа биоэкономических задач, где неопределенность проявляется, например, в погодных условиях.