Метод секущих плоскостей позволяет находить решение задачи целочисленного программирования как задачи линейного программирования путём добавления дополнительных ограничений. Главная идея метода — добавление ограничений, которые нарушаются для оптимума задачи линейного программирования, но остаются верными для оптимума исходной задачи.
Описание Пусть решается задача целочисленного программирования minimize c'x subject to Ax = b, x >= 0, x - integer. (1)
Для решения методом ЛП-релаксации minimize c'x subject to Ax = b, x >= 0. (2)
Основная идея метода секущих плоскостей — решение задачи целочисленного программирования путём решения последовательности задач линейного программирования. Сначала решается задача (2) и находится оптимальное решение x*. Если x* числовое, тогда оно является решением задачи (1) целочисленного программирования. Если нет, то производится поиск неравенства, которому все целочисленный решения задачи (1) удовлетворяют, а решение x* нет. Добавляя такое неравенство к задаче линейного программирования и решая его, выполняем шаг итерации метода секущих плоскостей.
Формальное описание Более формальное описание метода секущих плоскостей может быть записано следующим образом. 1. Решить линейную задачу (2). Пусть x* - оптимальное решение. 2. Если x* числовое, то задача решена. 3. В противном случае добавляем неравенство к задаче (2), которому не удовлетворяет x*, но удовлетворяет любое другое целочисленное решение.
Пример
См. также Алгоритм Гомори
Литература Bertsimas В., Tsitsiklis J. N. Introduction to Linear Optimization, p480
Категория:Алгоритмы оптимизации