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

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

Автор метода
Contini, B. (building on Charnes & Cooper's chance-constrained programming)
Год
1968
Тип
Stochastic multi-goal optimization
Семейство
Simulation / optimization

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

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

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

Стохастическое целевое программирование (SGP) расширяет классическое целевое программирование для учета неопределенности в целевых показателях, коэффициентах ограничений или параметрах правой части.

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

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

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

История

Целевое программирование было введено Чарнсом и Купером в конце 1950-х годов. Контини (1968) формально расширил его на стохастические ситуации, используя идеи программирования с вероятностными ограничениями. В последующие десятилетия росло его применение в финансах, сельском хозяйстве и государственной политике. Метод получил дальнейшее теоретическое обоснование благодаря связям с робастной оптимизацией, разработанной в 1990-х и 2000-х годах.

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

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

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

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

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

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

  • Одновременно обрабатывает множественные конфликтующие цели в рамках единой структуры оптимизации.
  • Позволяет явно указывать приемлемые уровни риска (доверия) для каждой цели или ограничения.
  • При предположении нормальности вероятностные ограничения сводятся к разрешимым ограничениям второго порядка конуса, решаемым стандартными решателями.
  • Предоставляет лицам, принимающим решения, вероятность достижения целей, предлагая более богатую информацию, чем решение для одного сценария.
  • Включает детерминированное целевое программирование как частный случай (уровень доверия = 1 при фиксированных параметрах).
  • Теоретически обосновано, связывается с литературой по программированию с вероятностными ограничениями и робастной оптимизации.

Применение

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

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

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

1

Определите переменные решения, множественные желаемые цели (целевые значения) и любые жесткие ограничения. Каждая цель i выражается как: f_i(x) + d_i^- - d_i^+ = g_i, где d_i^- и d_i^+ — переменные отрицательных и положительных отклонений от целевого значения g_i. Назначьте весовые коэффициенты приоритета, отражающие относительную важность достижения каждой цели.

2

Определите, какие параметры неопределенны: целевые значения g_i, коэффициенты ограничений или коэффициенты целевой функции могут быть смоделированы как случайные величины с известными или оцененными распределениями (например, нормальным, равномерным, эмпирическим). Укажите предположения о распределении на основе исторических данных или экспертных оценок.

3

Преобразуйте неопределенные ограничения в вероятностные (chance) ограничения. Для стохастического ограничения, включающего случайный параметр b_i с распределением F, требуйте P(g_i(x) <= b_i) >= alpha_i, где alpha_i — заданный пользователем уровень доверия (например, 0.90 или 0.95). При предположении нормальности эти ограничения могут быть переформулированы как детерминированные ограничения второго порядка конуса.

Формула
P(g_i(x) \leq b_i) \geq \alpha_i
4

Решите полученную (возможно, переформулированную) задачу оптимизации: минимизировать взвешенную сумму отклонений min sum_i (w_i^+ d_i^+ + w_i^- d_i^-) при условии детерминированных эквивалентов вероятностных ограничений и любых оставшихся жестких ограничений. Используйте решатели ЛП, ЦЛП или нелинейных задач в зависимости от структуры задачи.

Формула
\min \sum_{i} (w_i^+ d_i^+ + w_i^- d_i^-)
5

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

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

  • Предположение нормальности неопределенных параметров без эмпирической проверки может привести к вводящим в заблуждение гарантиям доверия.
  • Установка чрезмерно высоких уровней доверия (например, 0.999) фактически сводит модель к консервативной детерминированной формулировке, обесценивая цель стохастического моделирования.
  • Смешение целевого программирования с вероятностными ограничениями и робастного целевого программирования — эти два подхода по-разному обрабатывают неопределенность и не являются взаимозаменяемыми.
  • Неспособность проверить стохастическое решение с помощью имитации Монте-Карло оставляет фактический риск нарушения целей неизвестным.
  • Игнорирование корреляции между неопределенными параметрами может привести к невыполнимым или излишне оптимистичным решениям.

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

Чем стохастическое целевое программирование отличается от классического целевого программирования?

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

Какое предположение о распределении используется наиболее часто?

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

Как выбрать уровни доверия alpha_i для каждого вероятностного ограничения?

Уровни доверия отражают толерантность к риску лица, принимающего решения, для каждой цели. Значения 0.90–0.95 являются обычными на практике. Более высокие значения делают задачу более консервативной и могут потребовать ослабления других целей; более низкие значения допускают больший риск, но могут привести к неприемлемым результатам.

Может ли стохастическое целевое программирование обрабатывать целочисленные переменные решения?

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

Следует ли использовать стохастическое целевое программирование или робастную оптимизацию, когда у меня есть неопределенные параметры?

Если у вас есть надежная информация о распределении и вы хотите вероятностные гарантии, SGP подходит. Если вы знаете только множества неопределенности (границы) и хотите гарантии наихудшего случая без предположений о распределении, робастная оптимизация лучше. Когда оба подхода возможны, рекомендуется сравнивать решения, полученные обоими методами.

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

Источники

  1. Contini, B. (1968). A stochastic approach to goal programming. Operations Research, 16(3), 576–586.

    Открыть ссылку DOI
    Скопировано.
  2. Charnes, A., Cooper, W. W. (1959). Chance-constrained programming. Management Science, 6(1), 73–79.

    Открыть ссылку DOI
    Скопировано.