Режущая плоскость

Метод плоскостных разрезов (cut-plane)

Метод секущих плоскостей был разработан Шрайвером, он предназначен для решения задач комбинаторной оптимизации (POC), которые формулируются в виде линейной программы (PL):

секущая плоскость

В случае, когда POC имеет большой размер, чтобы представить его явно в памяти или чтобы он соответствовал решателю линейное программирование, мы используем технику, которая состоит в снятии части этих ограничений и решении ослабленной задачи (POCR). Оптимальное решение (PL) содержится в множестве допустимых решений этой релаксации. Для проблемы минимизация оптимальное решение задачи (POCR) меньше или равно оптимальному решению (POC)

секущая плоскость

Этот метод состоит из решения упрощенной задачи и итеративного добавления ограничений к исходной задаче. Определим ограничение для задачи минимизации парой (s,s0) где s находится в Rнет и с0 в R говорят, что это ограничение нарушается текущим решением x(bar), если для всех:

Эти ограничения затем называются плоскими разрезами. Алгоритм останавливается, когда больше нет ограничений, нарушаемых текущим решением, таким образом получается оптимальное решение для исходной задачи.

Метод плоских разрезов не очень эффективен, но его эффективность повышается при сочетании с методом филиал и связаны.

Делиться
ru_RURU
%d такие блоггеры, как: