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

                                               22
                                {bi } ≤ ∑ {aij }x j ,                      (7)
                                        j ∈J
где символом {y} обозначена дробная часть числа y. Неравенство (7) верно для
всех допустимых целых точек в задаче (1)-(3). Однако координаты полученного
нецелочисленного решения не удовлетворяют этому ограничению, так как для
него все небазисные переменные x j =0, j ∈J , и , следовательно, {bi } ≤0 , что
невозможно для нецелого числа по определению дробной части .
Неравенство (7) может быть использовано для дополнительного отсекающего
ограничения. В приведенную к канонической форме задачу его вводят в виде
                         ∑ {aij }x j −xn +m +1 ={bi },                      (8)
                          j∈J
где xn +m +1 - дополнительная переменная (После приведения задачи (1)-(3) к ка-
ноническому виду переменных в ней будет n +m ).

Замечание 1. До решения задачи симплекс-методом все исходные данные
должны быть приведены к целым. Иначе, например, неравенство x1 +x2 ≤15 / 2
после приведения к канонической форме примет вид x1 +x2 +x3 =15 / 2 , а это
уравнение неразрешимо в целых числах.

                      Алгоритмическая схема метода

Шаг 1. Найти точку x1 - решение задачи линейного программирования (1)-(3)
(без условия целочисленности). Положить к=1.
Шаг 2. Если x k -целочисленная, то решение найдено, останов. Иначе зафикси-
ровать множества I и J –индексов базисных и небазисных переменных.
Шаг 3. Выбрать номер i ∈I такой, что координата xik - дробная.
Шаг         4.     Добавить     в симплекс-таблицу    новое    ограничение:
 ∑ {aij }x j −xn +m +k ={bi } .
j∈J

Шаг 5. С учетом добавленного ограничения отыскать новое решение x k +1 . По-
ложить k=k+1. Перейти на шаг 2.

Замечание 2. Использование обычного симплекс-метода при решении данной
задачи неудобно, так как добавление нового ограничения каждый раз будет
приводить к необходимости вызова метода искусственного базиса. Более пред-
почтительным в данной ситуации является двойственный симплекс-алгоритм.
В таком случае новое ограничение вводится в систему в виде:
                         −∑ {aij }x j +xn +m +k =−{bi } ,
                           j ∈J
и переменная xn+m+k становится базисной. Согласно двойственному симплекс-
методу, исключению из базиса подлежит та переменная xl , значение которой
отрицательно. (Если все базисные переменные неотрицательны, то имеющееся