Расширенное математическое программирование

Алгебраические языки моделирования, такие как AIMMS , AMPL , GAMS , MPL и другие, были разработаны для облегчения описания проблемы в математических терминах и для связи абстрактной формулировки с системами управления данными, с одной стороны, и соответствующими алгоритмами для решения, с другой. Надежные алгоритмы и интерфейсы языков моделирования были разработаны для большого разнообразия задач математического программирования, таких как линейные программы (LP), нелинейные программы (NP), смешанные целочисленные программы (MIP), смешанные программы комплементарности (MCP) и другие. Исследователи постоянно обновляют типы задач и алгоритмов, которые они хотят использовать для моделирования в конкретных приложениях предметной области.

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

EMP не зависит от используемого языка моделирования, но в настоящее время он реализован только в GAMS. Новые типы задач, моделируемых с помощью EMP, переформулируются решателем GAMS JAMS в хорошо известные типы задач, а переформулированные модели передаются подходящему решателю GAMS для решения. Ядром EMP является файл emp.info , в котором к модели добавляются аннотации, необходимые для переформулировок.

Проблемы равновесия

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

Примерами использования EMP для решения проблем равновесия являются вычисление равновесий Курно–Нэша–Вальраса, [1] моделирование распределения воды, [2] [3] долгосрочное планирование расширения линий электропередачи электросети, [4] моделирование агентов , не склонных к риску, на рынках гидротермальной электроэнергии с неопределенными притоками в гидрорезервуары [5] и моделирование вариационных неравенств на энергетических рынках [6].

Иерархическая оптимизация

Иерархические задачи оптимизации — это математические программы с дополнительной задачей оптимизации в их ограничениях. Простым примером является задача двухуровневого программирования , которая оптимизирует цель верхнего уровня по ограничениям, которые включают другую задачу оптимизации нижнего уровня. Двухуровневое программирование используется во многих областях. Одним из примеров является проектирование оптимальных налоговых инструментов. Налоговый инструмент моделируется на верхнем уровне, а клиринговый рынок моделируется на нижнем уровне. В общем случае задача нижнего уровня может быть задачей оптимизации или вариационным неравенством . Для облегчения переформулирования задач иерархической оптимизации предоставляется несколько ключевых слов. Задачи двухуровневой оптимизации, моделируемые с помощью EMP, переформулируются в математические программы с ограничениями равновесия (MPEC), а затем решаются с помощью одного из решателей GAMS MPEC (NLPEC или KNITRO ).

Дизъюнктивное программирование

Математические программы, включающие бинарные переменные и определения дизъюнкции для моделирования дискретных выборов, называются дизъюнктивными программами. Дизъюнктивные программы имеют множество применений, включая упорядочивание задач в производственном процессе, организацию сложных проектов с экономией времени и выбор оптимального маршрута в схеме. Процедуры для расширений линейного и нелинейного дизъюнктивного программирования реализованы в EMP. Линейные дизъюнктивные программы переформулируются как смешанные целочисленные программы (MIP), а нелинейные дизъюнктивные программы переформулируются как смешанные целочисленные нелинейные программы (MINLP). Они решаются с помощью решателя LogMIP 2.0 и, возможно, других подрешателей GAMS.

Примеры использования EMP для дизъюнктивного программирования включают задачи планирования в химической промышленности [7]

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

EMP SP — это стохастическое расширение фреймворка EMP. Детерминированная модель с фиксированными параметрами преобразуется в стохастическую модель, в которой некоторые параметры не фиксированы, а представлены распределениями вероятностей. Это делается с помощью аннотаций и определенных ключевых слов. Возможны одиночные и совместные дискретные и параметрические распределения вероятностей . Кроме того, существуют ключевые слова для ожидаемого значения , значения риска (VaR) и условного значения риска (CVaR). Переменные, которые являются мерами риска, могут присутствовать в целевом уравнении или в ограничениях. EMP SP облегчает оптимизацию отдельной меры риска или комбинации мер риска (например, взвешенной суммы ожидаемого значения и CVaR). Кроме того, разработчик модели может выбрать компромисс между мерами риска. Также возможно моделировать ограничения, которые выполняются только с определенными вероятностями (ограничения вероятности). В настоящее время с EMP SP можно использовать следующие решатели GAMS: DE, DECIS, JAMS и LINDO . Для обработки предварительно выбранной детерминированной эквивалентной задачи можно использовать любой решатель GAMS .

Смотрите также

Ссылки

  1. ^ Outrata JV, Ferris MC, Červinka M, Outrata M (2016). «О равновесии Курно–Нэша–Вальраса и его вычислении». Множественно-значный и вариационный анализ . 24 (3): 387– 402. doi :10.1007/s11228-016-0377-4. S2CID  255062482.
  2. ^ Britz W, Ferris MC, Kuhn A (2013). «Моделирование учреждений, распределяющих воду, на основе множественных задач оптимизации с ограничениями равновесия». Environmental Modeling & Software . 46 : 196–207 . doi :10.1016/j.envsoft.2013.03.010.
  3. ^ Bauman A, Goemans C, Pritchett J, McFadden DT (2015). «Моделирование несовершенно конкурентных рынков воды на западе США». Избранная статья, подготовленная для презентации на ежегодном собрании Ассоциации сельскохозяйственной и прикладной экономики и Западной ассоциации сельскохозяйственной экономики 2015 года, Сан-Франциско, Калифорния, 26–28 июля .
  4. ^ Тан, Л.; Феррис, М. К. (2015). «Иерархическая структура для моделей долгосрочного планирования электропитания». Труды IEEE по энергосистемам . 30 (1): 46– 56. Bibcode : 2015ITPSy..30...46T. doi : 10.1109/TPWRS.2014.2328293 .
  5. ^ Филпотт А., Феррис М.К., Ветс Р. (2016). «Равновесие, неопределенность и риск в гидротермальных электрических системах». Математическое программирование, серия B. 157 ( 2): 483– 513. doi :10.1007/s10107-015-0972-4. S2CID  891228.
  6. ^ Габриэль СА, Конехо А. Дж., Фуллер Дж. Д., Хоббс Б. Ф., Руис К. (2013). Моделирование комплементарности на энергетических рынках . Международная серия по исследованию операций и науке управления. Т. 180. Нью-Йорк: Springer. С.  181– 220, 323– 384.
  7. ^ Гроссманн, IE (2012). «Достижения в моделях математического программирования для оптимизации на уровне предприятия». Компьютеры и химическая инженерия . 47 : 2– 18. doi :10.1016/j.compchemeng.2012.06.038.
  • www.gams.com
Взято с "https://en.wikipedia.org/w/index.php?title=Расширенное_математическое_программирование&oldid=1188559118"