28. Метод отсечения, дискретный алгоритм.
Пусть дана задача полностью целочисленного линейного программирования (4.1)—(4.4). Алгоритм метода отсечений состоит из следующих этапов:
1) решается ЗЛП (4.1)—(4.3) с отброшенными условием целочисленности (4.4); если она не разрешима, то задача (4.1)—(4.4) тоже решения не имеет;
2) если условие целочисленности выполняется по всем переменным, то найденное решение есть решение задачи (4.1)—(4.4), иначе — на этапе 3;
3) строится дополнительное отсекающее ограничение, включается в систему ограничений (4.2)—(4.3) и на этап 1.
Для решения полностью целочисленной задачи ЛП Гомори предложено делать каждый раз на этапе 3 дополнительное ограничение для нецелой переменной с наибольшей дробной частью.
Предположим, что задача с отброшенным
условием целочисленности решена.
Рассмотрим i-ю строку
оптимальной симплексной таблицы, которой
соответствует нецелое решение
базисной переменной
Пусть R — множество
индексов j, которые
соответствуют небазисным переменным.
Тогда переменная
может быть выражена через небазисные
переменные
— нецелое. (4.5)
Обозначим наибольшую целую часть числа
a, его не превосходящую,
через [a],
,
а дробную положительную часть — через
Очевидно
Например, если
то
если
то
Выразим базисную переменную в (4.5) в виде суммы целой и дробной частей.
(4.6)
Выражение в левых круглых скобках (4.6)
целое число, и чтобы
было целым, необходимо, чтобы выражение
в правых круглых скобках (4.6) тоже было
целым. Когда выражение
будет целым? Так как
а
то
будет целым числом, если
т.е.
.
(4.7)
Соотношение (4.7) определяет правильное отсечение Гомори.
Задача (4.1)—(4.4) не будет иметь полностью
целочисленного решения, если встретится
в симплекс-таблице уравнение, такое,
что
— дробное число, а
— целые.
Пример 4.1
Решить задачу ЛП
при ограничениях:
— целые.
Без учета целочисленности оптимальной симплекс-таблицей будет следующая табл. 4.1.
Таблица 4.1 — Конечная симплекс-таблица
-
Базис
Значение
Z
0
0
0
1
0
0
0
1
0
0
0
1
Так
как полученное решение не является
целочисленным, следует расширить данную
таблицу путем введения отсечения Гомори
на переменную
соответствующей
на переменную
Строке с базисной переменной
соответствует равенство
Следовательно, отношение Гомори имеет вид
.
(4.8)
Приведем данное неравенство к каноническому виду и добавим к табл. 4.1 (табл. 4.2)
.
Таблица 4.2 — Расширенная симплекс-таблица
-
Базис
Значение
Z
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
Далее
опять применим симплекс-алгоритм
(двойственный, выводя из базиса
)
и до тех пор, пока базисные значения
и
не станут целыми. Решением задачи будет
вектор
Покажем на графике (рис. 4.2) отсечение Гомори, выраженное через базисные переменные. Выразим из уравнений канонической формы исходной ЗЛП
переменные
и
и подставим в (4.8). Получим
т.е отсечение Гомори, выраженное через
базисные переменные, будет
