Релаксация Лагранжа

Релаксация Лагранжа широко используется во многих приложениях ДО. Это связано с возможностью «спрятать» «неудобные» или трудные ограничения в целевую функцию функции Лагранжа, что дает возможность получать хорошие оценки за приемлемое время.

Рассмотрим задачу ЦЛП вида

, (P)

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

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

,

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

Наилучшей из этих нижних границ является , которая получается с помощью решения двойственной задачи Лагранжа:

.

6.2. Применение метода ветвей и границ для решения задач дискретной оптимизации