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

Автор идеи - Г. Данциг. Она заключается в преобразовании невыпуклого множества ЦЗ в выпуклое целочисленное путем отсечения от выпуклого множества непрерывной задачи частей, не содержащих целочисленных точек. Тогда использование методов ЛП гарантирует получение оптимального целочисл. решения (при разрешимости задачи). Строится выпуклая оболочка допустимого мн-ва ЦЗ. Выпуклая оболочка невыпуклого мн-ва Q - наименьшее выпуклое мн-во, содержащее Q. В ЦЗ она мб построена соединением крайних целочисл. точек допустимого мн-ва гиперплоскостями. Пример построения выпуклой оболочки для задачи с двумя переменными:

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

Пример: Оптимальное решение НЗ как по критерию L ₁, так и по L ₂находится в вершине A. После первого отсечения нецелочисленной части множества, содержащей точку A, появляется целочисленная вершина B. При решении задачи по критерию L ₁ в ней будет оптимум НЗ, а значит, и исходной целочисленной задачи. Для критерия L ₂ оптимум НЗ окажется в вершине C, которая не является целочисленной. Требуется еще одно отсечение, после которого будет получено оптимальное целочисленное решение в точке F. В обоих случаях выпуклая оболочка строится только частично. Проблема состояла в получении регулярного условия, присоединение которого к ограничениям НЗ приводит к необходимому отсечению. Это условие должно удовлетворять двум требованиям: 1) не выполняться в текущем оптимальном решении НЗ; 2) выполняться во всех допустимых целочисленных решениях. Первое требование обеспечит отсечение части непрерывного множества, второе – неизменность целочисленного множества. Вывод условия отсечения:

Пусть получено оптимальное решение НЗ. Уравнение, соответствующее строке оптимальной симплекс-таблицы с i- й базисной переменной: , где a_i0 – значение базисной переменной (из столбца А ₀), a_ij – коэффициенты при небазисных переменных (из столбцов А _j). Нас интересуют переменные, которые имеют нецелые значения в полученном оптимальном решении. В этих случаях коэффициент a_i0 не целый, а коэффициенты a_ij могут быть любыми действительными числами. Нецелое значение представим в виде целой (ë×û) и дробной частей. Для дробной части: ,

для нецелого a_ij всегда 0 < < 1. Получаем:

Оставим в левой части только целые части коэффициентов. Учитывая неотрицательность и , получаем неравенство Теперь воспользуемся требованием целочисленности. При целых переменных левая часть неравенства может принимать только целые значения. Если отбросить , нестрогое неравенство левой и правой частей сохранится: -> . -условие отсечения. В оптимальном решении НЗ небазисные переменные равны нулю, а >0, следовательно, неравенство в нем не выполняется. Поэтому добавление условия отсечения к исходным условиям НЗ приведет к сужению допустимого множества за счет отсечения его части с оптимальной вершиной.

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

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

L= 2 x ₁ +x ₂ ® max; 15 x ₁ + 30 x ₂ £ 96; " x_j ³ 0, int.

Приводим неравенство к каноническому виду 15 x ₁ + 30 x ₂ + x ₃ = 96 и решаем непрерывную задачу симплекс-методом. Получаем оптимальную симплекс-таблицу:

Графическое решение показано на рис. Записываем уравнение по переменной x ₁: x ₁ + 2 x ₂ + x ₃ = . Дробную часть кроме свободного члена имеет только коэффициент при x₃. Получаем условие отсечения x ₃ ³ или x ₃ ³ 6.

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

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

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

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

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

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

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

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

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

9. Конец.