Лекция: Метод отсечений
Идею этого метода высказал Г. Данциг. Она заключается в преобразовании невыпуклого множества целочисленной задачи в выпуклое целочисленное путем отсечения от выпуклого множества непрерывной задачи частей, не содержащих целочисленных точек. Тогда использование методов ЛП гарантирует получение оптимального целочисленного решения (при разрешимости задачи).
С этой целью строится выпуклая оболочка допустимого множества целочисленной задачи. Выпуклой оболочкой невыпуклого множества Q называется наименьшее выпуклое множество, содержащее Q. В целочисленной задаче она может быть построена соединением крайних целочисленных точек допустимого множества гиперплоскостями. Пример построения выпуклой оболочки для задачи с двумя переменными показан на рис. 7.2. Здесь соединение крайних точек прямыми позволило получить целочисленное многогранное множество, содержащее все допустимые решения целочисленной задачи. Без требования целочисленности допустимое множество данной задачи представляет собой выпуклый четырехугольник. Как видно, разность этих множеств не содержит целочисленных решений.
Геометрически все выглядит достаточно просто. Но формализовать процедуру построения целочисленного множества долгое время не удавалось. Первым, кто смог это сделать, был Р. Гомори (1958 г.).
Он предложил итерационную процедуру, по которой на каждой итерации отсекается часть множества непрерывной задачи (НЗ), не содержащая целочисленных решений, но включающая оптимальное решение НЗ, и на сокращенном таким способом непрерывном множестве отыскивается новое оптимальное решение одним из методов ЛП. Итерации заканчиваются, когда оптимальное решение очередной НЗ окажется целочисленным или обнаружится неразрешимость НЗ, а значит, и целочисленной задачи. При этом выпуклая оболочка может быть построена только частично.
Рассмотрим пример (рис. 7.3). Оптимальное решение НЗ как по критерию L1, так и по L2находится в вершине A. После первого отсечения нецелочисленной части множества, содержащей точку A, появляется целочисленная вершина B. При решении задачи по критерию L1 в ней будет оптимум НЗ, а значит, и исходной целочисленной задачи. Если же взять критерий L2, то оптимум НЗ окажется в вершине C, которая не является целочисленной. Поэтому потребуется еще одно отсечение, после которого будет получено оптимальное целочисленное решение в точке F. В обоих случаях выпуклая оболочка строится только частично.
Проблема состояла в получении регулярного условия, присоединение которого к ограничениям НЗ приводит к необходимому отсечению. Это условие должно удовлетворять двум требованиям: 1) не выполняться в текущем оптимальном решении НЗ; 2) выполняться во всех допустимых целочисленных решениях. Первое требование обеспечит отсечение части непрерывного множества, второе – неизменность целочисленного множества.
Гомори предложил несколько вариантов получения условий отсечения. Мы покажем вывод условия отсечения, которое применяется в 1-м алгоритме Гомори.
Пусть получено оптимальное решение НЗ. Уравнение, соответствующее строке оптимальной симплекс-таблицы с i-й базисной переменной, записывается следующим образом:
, (7.3)
где ai0 – значение базисной переменной (из столбца А0), aij – коэффициенты при небазисных переменных (из столбцов Аj).
Нас интересуют переменные, которые имеют нецелые значения в полученном оптимальном решении. В этих случаях коэффициент ai0 в (7.3), естественно, не целый, а коэффициенты aij могут быть любыми действительными числами.
Нецелое значение представим в виде целой и дробной частей. Целая часть числа — наибольшее целое, не превосходящее само число. Будем обозначать ее взятием исходной величины в символы ë×û. Например, ë2.1û=2, ë1.9û=1, ë-2.1û= -3.
Применим такое представление к коэффициентам в (7.3). Тогда для дробной части имеем
,
следовательно, для нецелого aij всегда
0 < < 1.
Перепишем (7.3) с выделенными целыми и дробными частями коэффициентов:
(7.4)
Оставим в левой части (7.4) только целые части коэффициентов. Тогда, учитывая неотрицательность и, получаем неравенство
(7.5)
Теперь воспользуемся требованием целочисленности. При целых переменных левая часть неравенства (7.5) может принимать только целые значения. Поэтому, если отбросить, нестрогое неравенство левой и правой частей сохранится:
(7.6)
(В этом легко убедиться на простых примерах: 9£10.3; 9£9.75).
Вычитая (7.6) из равенства (7.3), получаем:
. (7.7)
Это и есть искомое условие отсечения. Действительно, в оптимальном решении НЗ (как и в любом базисном) небазисные переменные равны нулю, а >0, следовательно, неравенство (7.7) в нем не выполняется. Поэтому добавление (7.7) к исходным условиям НЗ приведет к сужению допустимого множества за счет отсечения его части с оптимальной вершиной.