Лекция: Метод отсечения, дискретный алгоритм.

Пусть дана задача полностью целочисленного линейного программирования (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 — Конечная симплекс-таблица

Так как полученное решение не является целочисленным, следует расширить данную таблицу путем введения отсечения Гомори на переменную соответствующей на переменную Строке с базисной переменной соответствует равенство

Следовательно, отношение Гомори имеет вид

. (4.8)

Приведем данное неравенство к каноническому виду и добавим к табл. 4.1 (табл. 4.2)

.

Таблица 4.2 —Расширенная симплекс-таблица

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

Покажем на графике (рис. 4.2) отсечение Гомори, выраженное через базисные переменные. Выразим из уравнений канонической формы исходной ЗЛП

переменные и и подставим в (4.8). Получим т.е отсечение Гомори, выраженное через базисные переменные, будет