Характеристика метода Гомори

Методы отсечений. Метод Гомори

Сущность состоит в следующем. Сначала задача решается без условия целочисленности. Если полученный план целочислен, то задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами (правильное ограничение):

оно должно быть минимальным;

• · должно отсекать найденный оптимальный нецелочисленный план;
• · не должно отсекать ни одного целочисленного плана.

Далее задачу решают с учётом нового ограничения. После этого в случае необходимости добавляют ещё одно ограничение и т. д.

Метод Гомори основан на симплексном методе и использует достаточно простой способ построения правильного отсечения.

Алгоритм метода Гомори:

• 1. Решить задачу симплекс-методом без учёта условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если задача ЛП неразрешима, то и задача ЦЛП неразрешима.
• 2. Если среди компонент оптимального решения есть нецелые, то выбрать компоненту с наибольшей целой частью и для неё сформулировать правильные отсечения.
• 3. Полученное неравенство (6.1) введением дополнительной неотрицательной целой переменной преобразовать в равносильные уравнения:

{i}-{im+1}xm+1-…-{in}xn+хn+1=0,.

и включить его в систему ограничений задачи ЛП.

Расширенную задачу решить симплекс-методом. Если найденный оптимальный план целый, то задача ЦЛП решена, в противном случае вернуться к шагу 2.

Если задача разрешима в целых числах, то после некоторого числа шагов, оптимальное целый план будет найден.

Задача ЛП — это задача выбора таких неотрицательных значений переменных, подчиненных системе ограничений в форме линейных неравенств, при которых достигается максимум или минимум данной линейного функции: гомори симплексный отсечение целочисленность.

F (x)=cxmax max Axb, bi, i=1m,.

x0 xj0, j=1n.

Пусть x=(x1,…, xj,…, xn) — вектор инструментальных переменных, n — n-мерное Евклидово пространство. Допустимое множество решений задачи ЛП Х={xnAxb, x0} представляет собой замкнутое выпуклое многогранное множество, расположенное в неотрицательном ортанте n-мерного Евклидова пространства. Граничные гиперплоскости называют гранями, а точки, в которых пересекаются n или более граней, называют вершинами. Поверхность уровня целевой функции {xncx = const} представляет собой гиперплоскость в n. Если придать этой const различные значения, то получим семейство параллельных гиперплоскостей. Для n=2 примером такого семейства являются параллельные грани. Направление наискорейшего роста задается градиентом, т. е. вектором-строкой из n, ортогональным к поверхности уровня.

С геометрической точки зрения задача ЛП состоит в отыскании точки (или множества точек) в n, принадлежащих допустимому выпуклому многогранному множеству, в которой достигается поверхность наибольшего уровня. Из геометрических представлений ясно, что если решение существует, оно не может быть внутренней точкой, а должно принадлежать границе допустимого множества. В трехмерном случае решением может быть точка вершины (пересечение трех или более граней), отрезок прямой (пересечение двух граней), часть некоторой плоскости (грань). Хотя решение может быть неединственным, максимальное значение целевой функции единственно. Действительно, поскольку допустимое множество выпукло, а целевая функция линейна, то по теореме о достаточных условиях существования максимума локальный максимум является глобальным.

Кроме того, если n>m, то решение непременно достигается в такой вершине допустимого множества, в которой по меньшей мере n-m переменных равны 0.

Поскольку целевая функция непрерывна, а допустимое множество замкнуто, по теореме Вейерштрасса решение существует в том случае, если допустимое множество непусто и ограничено. Следовательно, возможны 2 случая, когда задача ЛП не может иметь решения:

• 1) ограничения являются несовместными и допустимое множество пусто;
• 2) неограниченность допустимого множества.

Итак, задача ЛП либо имеет единственное решение (в вершине), либо бесконечное множество решений, либо не имеет решений (если допустимое множество пусто или не ограничено).