 |
Общие идеи методов отсечения
|
|
|
|
Введение
Большой класс прикладных задач оптимизации сводится к задачам целочисленного линейного программирования. Для решения этих задач широко применяются методы отсечения, предназначенные для решения общей целочисленной задачи, сопоставляя ей некоторую нецелочисленную задачу, по решению которой и позволяет найти решение.
Первый методов решения целочисленной задачи линейного программирования отсечением был предложен Гомори и получил название алгоритма Гомори.
Постановка задачи
Метод Гомори предназначен для решения целочисленных задач линейного программирования. При рассмотрении метода Гомори будем решать данную задачу в канонической форме.
Каноническая форма
Будем рассматривать каноническую задачу целочисленного программирования с n переменными и m условиями, дополненную условием целочисленности:
Где c = (c1, c2, …, cn), x = (x1, x2, …, xn) - вектора размерности n, <c, x> - их скалярное произведение (
), называемое так же целевой функцией, A - матрица размерности n ´ m, b - вектор-столбец размерности m.
Условие целочисленности существенно осложняет задачу линейного программирования (1.1), (1.2). Так может случиться, что задача (1.1)-(1.3) обладает допустимыми (целочисленными) планами, целевая функция ограничена на допустимом множестве, однако ее максимум не достигается. Например в задаче:
не существует целочисленных решений, в то время как без этого условия решением служит любой вектор вида
.
В связи со сказанным, при обосновании численных алгоритмов решения задач типа (1.1)-(1.3) приходится накладывать различные дополнительные условия.. Будем считать, что множество X планов задачи (1.1), (1.2) (без условия целочисленности) ограничено, то есть является многогранником.
|
|
|
Из этого условия вытекает, что множество X* всех целочисленных планов задачи (1.1)-(1.3) конечно.. Будем предполагать, что все коэффициенты cj, j=1, 2, …, n, целевые функции - целые числа.
Из условия II вытекает, что для всякого целочисленного плана x Î X * значение < c, x > максимизируемой линейной формы - целое число. В этом случае говорят, что гарантирована целочисленность целевой функции.
Хотя условия I и II на задачу (1.1) - (1.3) довольно жесткие, ослабить их, для получения необходимых результатов, можно лишь немного.
Приведение к канонической форме
Задача целочисленного линейного программирования может формулироваться несколько иначе, нежели это было приведено выше. Так, например, вместо условия (1.2) может иметь место другая форма записи ограничений
От подобной записи к (1.2) можно перейти, прибавив к каждому уравнению по одной новой переменной, тогда ограничения примут вид
Добавленные переменные будут иметь нулевой вес в целевой функции.
Отметим, что для получения, в зависимости от вида неравенства, следует не только прибавлять, но и вычитать переменную в зависимости от знака неравенства, учитывая условие (1.3).
Если в исходной задаче не для некоторой переменной xi не выполнено условие положительности, то ее следует заменить на разность двух новых, положительных, переменных.
Общие идеи методов отсечения
Существует принципиальная возможность свести решение задачи (1.1) - (1.3) к нахождению оптимального плана некоторой задачи линейного программирования (без условия целочисленности переменных). Пусть X - многогранное множество, определяемое условиями (1.1), (1.2). Через X* обозначим множество всех целочисленных векторов x*, лежащих в X. Другими словами X* задается условиями (1.1)-(1.3), т.е.
По определению X* Í X. Будем обозначать через Xz выпуклую оболочку множества X*. Тогда Xz Í X.
|
|
|
Таким образом, мы сопоставили многогранному множеству X некоторое выпуклое множество Xz Í X согласно следующему правилу: Xz есть минимальное выпуклое множество, содержащие все целочисленные векторы из X.
По предположению I, X является многогранником, следовательно множество X* конечно. Тогда выпуклое множество Xz так же является многогранником, а следовательно, имеем, что Xz можно задать конечным числом линейных неравенств.
Чтобы подчеркнуть основное отличие множества Xz от множества X, дадим следующее определение.
Определение 1. Многогранник, все крайние точки которого целочисленны (т.е. все их координаты целые числа), называются целочисленным многогранником.
Очевидно, что многогранник Xz - целочисленный, по скольку его крайними точками являются лишь точки множества X* целочисленных планов.
Оправданием для изучения соответствия X ® Xz является следующий простой факт.
Теорема 1. Любой оптимальный опорный план задачи линейного программирования является решением задачи (1.1)-(1.3).
Доказательство. Пусть ` x* - оптимальный опорный план задачи (2.1), x* - какое то решение исходной задаячи (1.1)-(1.3). ` x* Î Xz Í X, то
< c,` x* > £ < c, x* >.
С другой стороны, так как x* - целочисленный план, то x* Î X* Í Xz, и поэтому
< c,` x* > ³ < c, x* >,
откуда
< c,` x* > = < c, x* >.
Доказательство теоремы закончено.
Подчеркнем, что теорема 1 утверждает лишь принципиальную возможность сведения решения задачи целочисленного линейного программирования к поиску опорных планов задачи линейного программирования вида (2.1). Основная трудность в использовании этой возможности состоит в явном задании многогранника Xz системой линейных неравенств с тем, что бы затем применить для решения задачи (2.1) численные методы линейного программирования. Вероятнее всего, что в вычислительном отношении эта проблема столь же сложна, как и исходная задача поиска оптимального целочисленного плана.
Несмотря на это, идея «сужения» множества X оказалась полезной и привела к созданию нескольких алгоритмов решения целочисленных задач линейного программирования, носящих название «методы отсечения».
|
|
|
Изложим идею методов отсечения. Допустим, что удалось построить последовательность { Lr }, r = 0, 1, 2, …, задач линейного программирования, каждая из которых определяется своим многогранником Xr и одной для всех целевой функцией < c, x >:
при чем эта последовательность задач обладает следующими свойствами:
) X0=X, т.е. в качестве X0 берется множество планов задачи (1.1),(1.2);
) Xrz = Xz, r=1,2, …;
) если при решении задачи Lr полученный оптимальный вектор xr* не удовлетворяет условию целочисленности, то он не является планом задачи Lr+1, т.е. xr* Ï Xr+1.
Отметим, что если на каком то шаге r вектор xr* - решение задачи Lr - оказался целочисленным, то он является решением исходной задачи (1.1)-(1.3) в силу свойства 2) последовательности Lr.
Интуитивно ясно, что последовательное построение задач Lr, r=1,2, …, дает в некотором смысле аппроксимацию множества Xz с помощью множества Xr.
Способы построения последовательности { Lr }, обеспечивают конечность процесса решения задачи (1.1)-(1.3), были впервые предложены Гомори.
Описание метода Гомори
Рассмотрим теперь алгоритм Гомори для решения целочисленных задач линейного программирования. Этот метод принадлежит к числу методов отсечения и реализует идеи, изложенный в предыдущем пункте.
|
|
|
