Метод отсечений

Идею этого метода высказал Г. Данциг. Она заключается в преобразовании невыпуклого множества целочисленной задачи в выпуклое целочисленное путем отсечения от выпуклого множества непрерывной задачи частей, не содержащих целочисленных точек. Тогда использование методов ЛП гарантирует получение оптимального целочисленного решения (при разрешимости задачи).

С этой целью строится выпуклая оболочка допустимого множества целочисленной задачи. Выпуклой оболочкой невыпуклого множества Q называется наименьшее выпуклое множество, содержащее Q. В целочисленной задаче она может быть построена соединением крайних целочисленных точек допустимого множества гиперплоскостями. Пример построения выпуклой оболочки для задачи с двумя переменными показан на рис.2. Здесь соединение крайних точек прямыми позволило получить целочисленное многогранное множество, содержащее все допустимые решения целочисленной задачи. Без требования целочисленности допустимое множество данной задачи представляет собой выпуклый четырехугольник. Как видно, разность этих множеств не содержит целочисленных решений.

Геометрически все выглядит достаточно просто. Но формализовать процедуру построения целочисленного множества долгое время не удавалось. Первым, кто смог это сделать, был Р. Гомори (1958 г.).

Он предложил итерационную процедуру, по которой на каждой итерации отсекается часть множества непрерывной задачи (НЗ), не содержащая целочисленных решений, но включающая оптимальное решение НЗ, и на сокращенном таким способом непрерывном множестве отыскивается новое оптимальное решение одним из методов ЛП. Итерации заканчиваются, когда оптимальное решение очередной НЗ окажется целочисленным или обнаружится неразрешимость НЗ, а значит, и целочисленной задачи. При этом выпуклая оболочка может быть построена только частично.

Рассмотрим пример (рис. 3). Оптимальное решение НЗ как по критерию L ₁, так и по L ₂ находится в вершине A. После первого отсечения нецелочисленной части множества, содержащей точку A, появляется целочисленная вершина B. При решении задачи по критерию L ₁ в ней будет оптимум НЗ, а значит, и исходной целочисленной задачи. Если же взять критерий L ₂, то оптимум НЗ окажется в вершине C, которая не является целочисленной. Поэтому потребуется еще одно отсечение, после которого будет получено оптимальное целочисленное решение в точке F. В обоих случаях выпуклая оболочка строится только частично.

Проблема состояла в получении регулярного условия, присоединение которого к ограничениям НЗ приводит к необходимому отсечению. Это условие должно удовлетворять двум требованиям: 1) не выполняться в текущем оптимальном решении НЗ; 2) выполняться во всех допустимых целочисленных решениях. Первое требование обеспечит отсечение части непрерывного множества, второе – неизменность целочисленного множества.

Гомори предложил несколько вариантов получения условий отсечения. Мы покажем вывод условия отсечения, которое применяется в 1-м алгоритме Гомори.

Пусть получено оптимальное решение НЗ. Уравнение, соответствующее строке оптимальной симплекс-таблицы с i- й базисной переменной, записывается следующим образом:

, (3)

где a_i0 – значение базисной переменной (из столбца А ₀), a_ij – коэффициенты при небазисных переменных (из столбцов А _j).

Нас интересуют переменные, которые имеют нецелые значения в полученном оптимальном решении. В этих случаях коэффициент a_i0 в (7.3), естественно, не целый, а коэффициенты a_ij могут быть любыми действительными числами.

Нецелое значение представим в виде целой и дробной частей. Целая часть числа - наибольшее целое, не превосходящее само число. Будем обозначать ее взятием исходной величины в символы ë×û. Например, ë2.1û=2, ë1.9û=1, ë-2.1û= -3.

Применим такое представление к коэффициентам в (3). Тогда для дробной части имеем

,

следовательно, для нецелого a_ij всегда

0 < < 1.

Перепишем (7.3) с выделенными целыми и дробными частями коэффициентов:

(4)

Оставим в левой части (7.4) только целые части коэффициентов. Тогда, учитывая неотрицательность и , получаем неравенство

(5)

Теперь воспользуемся требованием целочисленности. При целых переменных левая часть неравенства (7.5) может принимать только целые значения. Поэтому, если отбросить , нестрогое неравенство левой и правой частей сохранится:

(6)

(В этом легко убедиться на простых примерах: 9£10.3; 9£9.75).

Вычитая (6) из равенства.3), получаем:

. (7.7)

Это и есть искомое условие отсечения. Действительно, в оптимальном решении НЗ (как и в любом базисном) небазисные переменные равны нулю, а >0, следовательно, неравенство (7) в нем не выполняется. Поэтому добавление (7) к исходным условиям НЗ приведет к сужению допустимого множества за счет отсечения его части с оптимальной вершиной.

Пример 1. Выведем условие отсечения для задачи

L= 2 x ₁ +x ₂ ® max;

15 x ₁ + 30 x ₂ £ 96;

" x_j ³ 0, int.

Приводим неравенство к каноническому виду

15 x ₁ + 30 x ₂ + x ₃ = 96

и решаем непрерывную задачу симплекс-методом. Получаем оптимальную симплекс-таблицу

Базис	А0	А1	А2	А3
А1
D

Графическое решение показано на рис. 4.

Записываем уравнение (3) по переменной x ₁:

x ₁ + 2 x ₂ +x ₃ =.

Дробную часть кроме свободного члена имеет только коэффициент при x₃. Следуя (7), получаем условие отсечения

x ₃ ³ или x ₃ ³ 6.

Очевидно, что в оптимальном решении НЗ оно не выполняется (х ₃ ^*= 0). Условие отсечения можно записать и через основные переменные. Так как х ₃ = 96-15 х ₁ - 30 х ₂, то 96-15 х ₁ - 30 х ₂ ³ 6 и окончательно имеем х ₁ + 2 х ₂ £ 6. Граница по этому ограничению показана на рис. 7.4 пунктирной линией. Легко убедиться, что все вершины усеченного множества целочисленные. ▲

При многих нецелых переменных возникает вопрос выбора переменной, по которой следует строить отсечение. Строгого обоснования выбора не имеется. На основе экспериментальных данных рекомендуется брать переменную с наибольшей дробной частью. Второй вопрос относится к способу учета очередного условия отсечения: его можно добавить к условиям исходной задачи и решать задачу заново или после добавления продолжить симплекс-преобразования с полученного оптимального решения, которое стало недопустимым. В алгоритме Гомори применяется второй вариант как более экономичный.

Перед добавлением условие отсечения приводится к равенству:

. (8)

Так как небазисные переменные равны нулю, то новая дополнительная переменная . Поэтому рекомендуется для последующего решения применять двойственный симплекс-метод.

Таким образом, согласно 1-му алгоритму Гомори необходимо выполнить следующие действия.

1. Преобразовать условия задачи так, чтобы все коэффициенты стали целыми.

2. Решить исходную задачу без учета целочисленности (НЗ) одним из методов линейного программирования. Если непрерывная задача неразрешима, то зафиксировать неразрешимость исходной задачи и перейти на 9.

3. Проверить решение на целочисленность: если решение целочисленное, то зафиксировать получение оптимального решения и перейти на 9.

4. Если не все переменные целые, то из оптимальной таблицы выбрать переменную с наибольшей дробной частью.

5. Выписать из симплекс-таблицы строку с выбранной базисной переменной.

6. Выделить дробные части коэффициентов в полученном уравнении и записать условие отсечения согласно (7).

7. Привести условие отсечения к равенству (8), умножить его на –1 и добавить полученную строку к оптимальной симплекс-таблице. При этом размерность базиса увеличивается на единицу. В качестве недостающей базисной переменной принимается дополнительная переменная из новой строки.

8. Решить расширенную задачу двойственным симплекс-методом. Если задача разрешима, перейти на 3. Иначе зафиксировать неразрешимость целочисленной задачи.

9. Конец.

Гомори доказал сходимость этого алгоритма.

Примечание. Как следует из алгоритма, на каждой итерации увеличивается размер таблицы (число условий) на единицу. Для ограничения размера используется такой прием. Как только дополнительная переменная какого-либо условия отсечения снова становится базисной (но уже положительной!), строка с ней удаляется из таблицы. Если велся столбец этой переменной, то он тоже удаляется. Подобное исключение не отразится на решении, так как условие удаляется после того, как становится неактивным. В результате число строк не превысит

ЗАКЛЮЧЕНИЕ

Кратко подводятся итоги занятия, при этом обращается внимание студентов на цели и содержание дисциплины.

Дать задание на самостоятельную работу (отводимое время 2 часа):

ó с целью более глубокого освоения материала повторить и более подробно изучить линейную оптимизацию. Литература: [3] с. 311…313, конспект лекций,

При необходимости ответить на возникшие вопросы.

Старший преподаватель кафедры программного обеспечения И.Денисова

Дата добавления: 2014-01-11