Многоуровневое математическое программирование: двухуровневые модели и игры Штакельберга

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

Для решения двухуровневых задач используются методы сведения их к одноуровневым задачам математического программирования с ограничениями равновесия (MPEC - Mathematical Programs with Equilibrium Constraints). Поскольку задача Ведомого часто является выпуклой, ее можно заменить эквивалентными условиями оптимальности Каруша-Куна-Таккера (ККТ). В результате задача Лидера превращается в одноуровневую задачу оптимизации, но она содержит специфические ограничения дополняющей нежесткости, которые нарушают регулярность допустимой области и требуют применения специализированных методов штрафов или сглаживания.

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

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

Список литературы:
1. Dempe S. Foundations of Bilevel Programming. — Kluwer Academic Publishers, 2002.
2. Барда Дж. Двухуровневое программирование. — М.: Наука, 1998.
3. Фиакко А. Теория и приложения многоуровневой оптимизации. — М.: Мир, 1985.