Теория двухуровневого планирования
Теория двухуровневого планирования (альтернативно, декомпозиция Корнаи–Липтака ) — это метод, который разлагает большие задачи линейной оптимизации на подзадачи. Такая декомпозиция упрощает решение общей задачи. Этот метод также моделирует метод координации экономических решений, позволяющий децентрализованным фирмам вести себя так, чтобы достичь глобального оптимума. Он был введен венгерским экономистом Яношем Корнаи и математиком Тамашем Липтаком в 1965 году. Это альтернатива разложению Данцига – Вольфа .
Описание [ править ]
Задача ЛП должна иметь специальную структуру, известную как блочная угловая структура. Это та же самая структура, которая требуется для разложения Данцига Вульфа:
Существуют некоторые ограничения на общие ресурсы (D), за которые, как предполагается, несет ответственность центральное плановое агентство, а также n блоков коэффициентов (от F1 до Fn), которые являются предметом заботы отдельных фирм.
Центральное агентство начинает процесс, предоставляя каждой фирме предварительное распределение ресурсов, которое удовлетворяет общим ограничениям D. Каждая фирма оптимизирует свои локальные переменные решения, предполагая, что глобальное распределение ресурсов соответствует указанному. Решение проблемы LP фирмы LP дает множители Лагранжа (цены) для глобальных ресурсов, которые фирмы передают обратно плановому агентству.
На следующей итерации центральное агентство использует информацию, полученную от фирм, чтобы разработать пересмотренное распределение ресурсов; например, если фирма i сообщает о высокой скрытой цене на ресурс j, агентство предоставит больше этого ресурса этой фирме и меньше другим фирмам. Пересмотренные предварительные ассигнования отправляются обратно отдельным фирмам, и процесс продолжается.
Было показано, что этот процесс будет сходиться (хотя и не обязательно за конечное число шагов) к глобальному решению всей проблемы. (Напротив, метод Данцига Вульфа сходится за конечное число шагов).
Методы DW и KL двойственны: в DW центральный рынок устанавливает цены (на основе спроса фирм на ресурсы) и отправляет их фирмам, которые затем изменяют объемы спроса, в то время как в KL центральное агентство рассылает информацию о количестве фирмам и получает предложения (т.е. информацию о ценах конкретной фирмы) от фирм.
См. также [ править ]
Ссылки [ править ]
- Дж. Корнаи, Т. Липтак: Двухуровневое планирование , Econometrica, 1965, Vol. 33, стр. 141–169. [1]