Skip to content
Назад к результатам поиска

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

Автор метода
George B. Dantzig
Год
1955
Тип
Stochastic optimization model
Семейство
Simulation / optimization

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Стохастическое линейное программирование (SLP) расширяет классическое линейное программирование на случаи, когда некоторые параметры модели — затраты, спрос, доступность ресурсов — неопределенны и моделируются как случайные величины.

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

Интуиция метода

Классическое линейное программирование предполагает, что каждый коэффициент известен точно. На практике будущий спрос, цены и урожайность неопределенны. SLP встраивает эту неопределенность непосредственно в модель: вместо оптимизации для одного фиксированного сценария, планировщик сначала принимает решения первого этапа, затем наблюдает, какой сценарий реализуется, и принимает корректирующие действия для устранения любого дефицита или избытка. Цель минимизирует общие ожидаемые затраты по всем сценариям, балансируя затраты на обязательства с ожидаемыми затратами на корректирующие действия. Это отражает реальную управленческую логику: вы решаете сегодня, что предварительно заказать, а завтра вы можете купить больше с наценкой или продать излишки со скидкой.

История

Стохастическое программирование было пионерски разработано Джорджем Данцигом, который ввел двухэтапную модель в 1955 году вскоре после разработки симплекс-метода. Бил (1955) независимо предложил аналогичные идеи. Область была систематизирована влиятельным учебником Бирже и Луво (1997) и разработкой алгоритма декомпозиции L-образной формы (Бендерса) в 1960–1980-х годах. SLP теперь лежит в основе операционных решений в энергетике, логистике и финансах по всему миру.

Когда применять

Используйте SLP, когда: (1) ключевые входные параметры действительно неопределенны и могут быть охарактеризованы вероятностным распределением или эмпирическим набором сценариев; (2) решения должны быть приняты до разрешения неопределенности, но корректирующие действия возможны после этого с затратами; (3) цель и ограничения линейны относительно переменных решения. Типичные применения включают планирование производства, проектирование цепочек поставок, диспетчеризацию энергии и оптимизацию портфеля. НЕ используйте SLP, когда: неопределенность не может быть количественно оценена вероятностно (вместо этого используйте робастную оптимизацию); связь между решениями и результатами нелинейна или целочисленна (используйте стохастическое ЦП или стохастическое динамическое программирование); набор сценариев слишком велик для перечисления, а декомпозиция вычислительно невозможна; или когда более простого детерминированного анализа чувствительности достаточно для понимания влияния неопределенности.

Ограничения и замечания

  • Требует указания вероятностного распределения или набора сценариев для неопределенных параметров — это предположение о распределении часто трудно проверить.
  • Вычислительная нагрузка быстро растет с увеличением числа сценариев и переменных первого этапа; большие задачи требуют декомпозиции и значительных ресурсов решателя.
  • Ограничено линейной целью и ограничениями; нелинейные или целочисленные структуры требуют расширений, которые добавляют дальнейшую сложность.
  • Цель, основанная на ожидаемом значении, может игнорировать риски в хвосте распределения; варианты с неприятием риска (CVaR, вероятностные ограничения) добавляют накладные расходы на моделирование и вычисления.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Непосредственно учитывает вероятностную неопределенность в оптимизации, вырабатывая решения, устойчивые к сценариям, а не для одного предполагаемого будущего.
  • Двухэтапная структура тесно отражает реальные процессы принятия решений: обязательства сейчас, адаптация позже с помощью корректирующих действий.
  • Ценность стохастического решения (VSS) и EVPI предоставляют принципиальные метрики для сообщения о выгоде моделирования неопределенности.
  • Хорошо поддерживается зрелыми алгоритмами (L-образная / декомпозиция Бендерса) и коммерческими решателями (CPLEX, Gurobi).
  • Масштабируется до больших практических задач с помощью декомпозиции; распараллеливается по сценариям.

Применение

  • Планирование энергосистем и обязательства по unidades при неопределенной возобновляемой генерации и спросе.
  • Проектирование сети цепочек поставок с неопределенным спросом клиентов, сроками поставки или транспортными расходами.
  • Планирование посевов и ирригации при неопределенном количестве осадков и ценах на сырьевые товары.
  • Оптимизация финансового портфеля с неопределенной доходностью активов при бюджетных и регуляторных ограничениях.
  • Управление доходами авиакомпаний и составление расписаний экипажей при неопределенном спросе пассажиров.
  • Предварительное размещение гуманитарных грузов перед неопределенными сценариями бедствий.

Как это работает

Как это работает

1

Сформулируйте двухэтапную модель: переменные первого этапа x представляют решения «здесь и сейчас», принимаемые до разрешения неопределенности; цель минимизирует затраты первого этапа c^T x плюс ожидаемые затраты на корректирующие действия E[Q(x,xi)] по случайному вектору xi. Ограничения Ax = b должны выполняться для решений первого этапа независимо от сценария.

Формула
\min_{x} c^T x + \mathbb{E}_\xi[Q(x, \xi)] \quad \text{s.t. } Ax = b,\; x \geq 0
2

Представьте случайный вектор xi с помощью дискретного набора сценариев {xi_1, ..., xi_S} с вероятностями p_s, сумма которых равна 1. Сценарии могут быть получены из исторических данных, экспертных оценок или методом Монте-Карло. Качество набора сценариев критически определяет качество решения; для сохранения вычислительной сложности проблемы часто применяются методы сокращения числа сценариев (например, кластеризация по Вассерштейновскому расстоянию).

3

Для каждого сценария xi_s решите подзадачу корректирующих действий: при заданном решении первого этапа x найдите самое дешевое корректирующее действие y_s, удовлетворяющее W y_s = h(xi_s) - T(xi_s) x, y_s >= 0. Если допустимое корректирующее действие отсутствует, возникает большой штраф (или недопустимость), сигнализирующий о том, что решение первого этапа было слишком агрессивным.

Формула
Q(x, \xi) = \min_{y} q(\xi)^T y \quad \text{s.t. } W y = h(\xi) - T(\xi) x,\; y \geq 0
4

Решите полную развернутую форму (все сценарии объединены в одну большую задачу ЛП) для малых и средних наборов сценариев или примените декомпозицию Бендерса (метод L-образной формы) для больших наборов. Метод L-образной формы итеративно добавляет ограничения оптимальности и допустимости к мастер-задаче до сходимости, используя блочно-диагональную структуру подзадач сценариев.

5

Оцените качество решения с помощью ценности стохастического решения (VSS) — прироста по сравнению с детерминированным решением, основанным на средних значениях, — и ожидаемой ценности совершенной информации (EVPI) — верхней границы того, сколько стоило бы совершенное предвидение. Сообщите решение первого этапа x*, ожидаемые общие затраты и затраты на корректирующие действия для каждого сценария, чтобы донести профиль риска до лиц, принимающих решения.

Частые ошибки

  • Использование слишком малого числа сценариев приводит к смещенному решению, которое плохо работает вне выборки; всегда проверяйте с помощью тестирования вне выборки.
  • Путаница между детерминированным решением, основанным на средних значениях (подстановка средних значений), и стохастическим решением — VSS может быть большим, даже когда параметры выглядят стабильными.
  • Игнорирование допустимости корректирующих действий: если подзадача второго этапа может быть недопустимой для некоторых сценариев, модель требует ограничений полного возмещения или явных штрафов.
  • Переобучение на историческом распределении сценариев без стресс-тестирования против хвостовых или враждебных сценариев, особенно в приложениях, связанных с цепочками поставок или финансами.
  • Рассмотрение стохастического ЛП как прямой замены робастной оптимизации, когда лицо, принимающее решение, на самом деле неприязненно к неопределенности, а не нейтрально к ожидаемому значению.

Часто задаваемые вопросы

В чем разница между стохастическим линейным программированием и робастной оптимизацией?

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

Сколько сценариев обычно требуется?

Это зависит от размерности задачи и сложности распределения. Десятки или несколько сотен сценариев часто достаточны для задач планирования, если они сгенерированы разумно (например, с помощью согласования моментов или сокращения сценариев). Аппроксимация среднего по выборке (SAA) на основе Монте-Карло может потребовать тысяч сценариев для высокоточных решений, при этом доверительные интервалы направляют сходимость.

Может ли SLP обрабатывать целочисленные или бинарные решения?

Не напрямую — целочисленные переменные требуют стохастического целочисленного программирования (SIP) или стохастического смешанного целочисленного программирования (SMIP), которые значительно сложнее вычислительно. SLP применяется только тогда, когда все переменные решения являются непрерывными.

Что измеряет ценность стохастического решения (VSS)?

VSS = EEV - RP, где EEV — ожидаемые затраты детерминированного решения, основанного на средних значениях, оцененные по всем сценариям, а RP — истинный стохастический оптимум (задача корректирующих действий). Высокий VSS указывает на то, что игнорирование неопределенности и использование средних параметров приводит к существенно худшим результатам.

Какие решатели и программное обеспечение поддерживают стохастическое линейное программирование?

Коммерческие решатели, такие как CPLEX и Gurobi, могут решать развернутую форму напрямую. Фреймворки с открытым исходным кодом включают средства чтения формата SMPS, PySP (часть Pyomo) и пакет Julia StochasticPrograms.jl. Для крупномасштабных задач часто используются пользовательские реализации декомпозиции L-образной формы в исследованиях и промышленности.

Похожие методы

Источники

  1. Dantzig, G. B., & Madansky, A. (1961). On the solution of two-stage linear programs under uncertainty. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, 1, 165–176.

    Открыть ссылку на публикацию
    Скопировано.
  2. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.

    ISBN: 9780387982175
    Скопировано.