Дискретная оптимизация - 21 стр.

                                             21
                         МЕТОДЫ ОТСЕЧЕНИЙ

                        § 6. Первый алгоритм Гомори

Рассмотрим целочисленную задачу линейного программирования в следующей
форме:
                                         n
                               ϕ( x) =∑ c j x j → min                         (1)
                                         j =1
                                  n
                                 ∑ aij x j ≤bi , i =1, m,                     (2)
                                  j =1
                                 x j ≥0,                                      (3)
                              x j ∈Ζ, j =1, n.                          (4)
Идея методов отсечений состоит в следующем. Процесс получения решения за-
дачи начинается с решения соответствующей ей оценочной задачи линейного
программирования (1)-(3) с отброшенным условием целочисленности. Если по-
лученная при этом оптимальная точка x 0 имеет только целые координаты, то
она является решением задачи (1)-(4). Если полученное решение нецелочис-
ленное, то вводится добавочное ограничение, которое отсекает часть области
допустимых решений задачи (1)-(3) вместе с найденным нецелочисленным ре-
шением, сохраняя при этом все целочисленные точки. Затем рассматривается
решение исходной задачи (1)-(3) с учетом нового ограничения. Если оно неце-
лочисленное, то вводится новое ограничение и так до тех пор, пока не будет
найдено целочисленное оптимальное решение. Правила формирования отсе-
кающих ограничений были разработаны американским ученым Р. Гомори.
Идея метода, названного первым алгоритмом Гомори, заключается в следую-
щем. Пусть в результате решения задачи (1)-(3) симплекс-методом получена
нецелочисленная оптимальная точка. Заключительная симплекс-таблица со-
держит уравнения вида:
                               bi =xi + ∑ aij x j ,                     (5)
                                                j∈J
i ∈I , где I- множество базисных переменных, J- множество небазисных пере-
менных задачи, bi и aij - пересчитанные к данному шагу значения bi и aij .
Выберем индекс i ∈I , такой что базисная координата xi =bi - дробная. По оп-
ределению целой части числа имеем: y ≥[ y ] . Так как          x j ≥0, ∀j , то
 ∑ aij x j ≥ ∑ [aij ]x j . Следовательно, с учетом равенства (5) имеем:
j∈J       j∈J

bi ≥xi + ∑ [aij ] x j . Если переменные x j ∈Ζ, j =1, n , то последнее неравенство
        j∈J
можно переписать так:
                             [bi ] ≥xi + ∑ [ aij ]x j                         (6)
                                           j∈J
Вычитая из равенства (5) неравенство (6), получаем неравенство