Лекция: Метод отсечений. Формулирование верного отсечения. Алгоритм метода

Сущность метода отсекающих плоскостей заключается в следующем:

1. Вначале решается задача с отброшенным условием целочисленности.

2. По полученным результатам делаются следующие выводы:

— если Dнц=0, то на основании того, что область допустимых Dц є Dнц, то делают вывод, что множество Dц=0 тоже пустое.

— если целевая функция задачи неограниченна на множестве Dнц, то делается вывод что она тоже неограниченна на множестве Dц. Объясняется это тем, что в области содержащей бесконечно удаленную точку всегда можно найти аналогичного рода точку принадлежащую Dц.

— Если оптимальное решение задачи на области Dнц является целочисленным, то оно одновременно является также оптимальным решением исходной задачи. Это также следует из того, что Dц є Dнц. При этом максимальное значение целевой функции задачи на области Dнц является всегда верхней границей для значения целевой исходной дискретной задачи.

— Если решение на области Dнц является нецелочисленным, то осуществляется переход к 3-му этапу.

3. Составляется дополнительное ограничение, которое называется правильным

отсечением. Правильное отсечение должно удовлетворять следующим

требованиям:

— быть линейным

— отсекать найденное оптимальное нецелочисленное решение задачи.

4. Осуществляется возращение к задачи линейного программирования с

отброшенным условием целочисленности, но с расширенной системой ограничений, в которую включено дополнительное ограничение полученное на 3-м этапе. Расширенная задача решается если найденное оптимальное решение

будет опять нецелым, то формируем новое дополнительное ограничение и процесс повторяем.

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

— оптимальное решение задачи с расширенной системой ограничений является оптимальным решением исходной задачи.

— из пустоты допустимой области расширенной задачи следует пустота допустимой области исходной задачи.

С геометрической точки зрения, каждому дополнительному ограничению в n-мерном пространстве соответствует определенная гиперплоскость отсекающая от многоугольника решений некоторую его часть, включая и оптимальную на данном этапе нецелочисленную вершину. При этом все точки с целочисленными координатами, в том числе и искомая оптимальная, находятся внутри этого многоугольника. Т. к. множество целых точек усеченного многогранника совпадает с множеством целых точек исходного многогранника – это значит, что если оптимальное решение задачи на усеченном многограннике удовлетворяет условию целочисленности, то оно и является оптимальным целочисленным решением исходной задачи. Через несколько операций отсечения искомая целочисленная точка оказывается сначала на границе области, а затем становится вершиной, неоднократно усеченного многогранника решений. В том случае если многогранник решений не содержит ни одной целочисленной точки, то сколько бы не вводили правильных отсечений целочисленное решение получить нельзя.