Теоретические основы методов отсечения

Обозначим через N совокупность небазисных переменных и на основании  последней симплексной таблицы  запишем разложение x_i по небазисным переменным x_i, jÎN

(16)

Так как x_i – нецелая величина, обозначим ближайшее целое число, не превосходящее x_i, через [x_i] и определим дробную часть: {x_i}= x_i - [x_i]. Очевидно, (x_i)>0.

Покажем, что по i-и строке симплексной таблицы (£, C) – задачи (в которой стоит нецелая координата решения) можно определить дополнительное линейное ограничение, обладающее свойствами правильности.

Теорема. Пусть - допустимое решение (£^ц, C) – задачи, тогда соотношения

, (17)

, - целое,

определяют правильное отсечение.

Доказательство.

Запишем выражение (16) в виде:

Используя для этого  выражения формулу (17), получим:

или

На основании предположений  теоремы о допустимости решения

(£^ц, C) – задачи x_i – целое. Величины [x_io], - целые по определению, следовательно, z_i – тоже целое.

Итак, z_i определенное формулой (17), целое. Докажем что . Доказательство будем вести от противного. Пусть .-

Это значит, что  . По определению дробной части . По условию теоремы x – допустимое решение (£^ц, C) – задачи, поэтому . Следовательно,

Тогда должно выполняться:

Итак, из предположения  отрицательности z_i, сразу же получаем т.е. z_i – нецелое. Поскольку ранее было показано, что z_i, определенное формулой (17), является целым, то тем самым мы пришли к противоречию. Следовательно, предположение, что z_i < 0, неверное. Теорема доказана.

Следствие. Любое оптимальное решение x(£, C) (£, C) – задачи, не являющееся допустимым решением (£^ц, C) – задачи, не удовлетворяет условию правильного отсечения (17).

Доказательство. Пусть х (£, C) – оптимальное решение (£, C) – задачи, x_i0 – дробное.

Покажем, что х (£, C) не удовлетворяет условию отсечения. Поскольку план оптимален, все небазисные переменные x_i, для jÎN равны нулю. Поэтому . Учитывая это, подставим x_io в формулу (17):

z_i(x (£, C))= – {x_i0}+0<0,

что противоречит условию  неотрицательности z_i. Следствие доказано.

Очевидно, что количество дополнительных ограничений будет  нарастать по мере решения вспомогательных (£, C) – задач, оптимальные планы которых будут содержать нецелые координаты, т.е. возникает проблема размерности.

Р. Гомори предложил прием, позволяющий ограничить размеры рассматриваемых симплексных таблиц вспомогательных задач величиной (n+2) (k+1), где n – количество переменных (£, C) – задачи, k – число небазисных переменных ее. Этот прием основывается на том, что нас интересует дополнительное ограничение лишь как способ отсечения нецелочисленного оптимального решения вспомогательной задачи, полученной на данном шаге, и перехода к следующей задаче.

Последовательность (£, C) – задач пометим индексом k=0,1,…, соответствующим номеру итерации в последовательном приближении к решению исходной (£^ц, C) – задачи, и обозначим (£_k, C). При этом (£₀, C) – задача соответствует (£, C) – задаче (задаче без требования целочисленности).

Переменную z_i, которая определяется дополнительным линейным ограничением (7) и строится по некоторой нецелочисленной координате оптимального решения (£_k, C) – задачи (k =0, 1, 2,…) обозначим x_n+k+l.

Чтобы размерность последовательности (£_k, C) – задач не возрастала, вычеркнем из симплекс-таблицы переменную, по которой построено дополнительное линейное ограничение.

После сделанных замечаний  перейдем непосредственно к изложению  вычислительной схемы.

1. Решим (£_k, C) – задачу (вначале k = 0) методом последовательного улучшения плана.

Пусть в базис оптимального решения вошли векторы A_s1,…, A_sm. Параметры последней симплексной таблицы обозначим через x_ij:

.

Если, все базисные составляющие оптимального решения x(£_k, C) (£_k, C) – задачи целые, то x(£_k, C) = x(£^ц, C). Если некоторая координата x_io оптимального решения x(£_k, C) нецелая, то перейдем к п. 2.

2. Если среди совокупности координат оптимального решения x(£_k, C) имеется единственная нецелая координата, то дополнительное линейное ограничение (17) строится по этой координате. Если нецелых координат в x(£_k, C) более одной, то выберем координату с наименьшим номером. Пусть ею оказалась x_i0. Составим дополнительное линейное ограничение

(18);  (19)

3. Добавим условия (18, 19) к условиям (£_k, C) – задачи. Получим новую (£_k+1, C) – задачу. Так как оптимальное решение x(£_k, C) (£_k, C) – задачи определяло одну из вершин многогранника условий, то оно может быть выбрано в качестве первоначального опорного решения для вновь полученной задачи. А это означает, что последнюю симплексную таблицу (£_k, C) – задачи можно взять в качестве исходной для (£_k+1, C) – задачи, дополнив ее условием (18).

Итак, симплексная таблица  для (£_k+1, C) – задачи получается из последней симплексной таблицы для (£_k, C) – задачи путем окаймления (i+1) – й строкой с элементами:

 

где – небазисные переменные (£_k, C) задачи.

 

Получим новую задачу, переменными которой являются . Условия этой задачи разрешены относительно x_sl,…, x_sm переменных и новой переменной x_n+k+1, а линейная форма выражена через небазисные переменные (£_k, C) – задачи. Так как мы занимаемся максимизацией F(x) и решение х* для (£_k, C) – задачи оптимально, то все D_i > 0. Поэтому процесс перехода к новому решению (£_k+1, C) – задачи не может быть осуществлен по методу уточнения плана. В то же время и поэтому вектор А₀ симплексной таблицы не является опорным решением для (£_k+1, C) – задачи, так как решением называется вектор, все координаты которого неотрицательны и удовлетворяют условию принадлежности области £_k+l. Поэтому назовем полученный вектор псевдорешением задачи (£_k+1, C) и перейдем к дальнейшему преобразованию симплекс-таблицы.

Обозначим через k номер псевдорешения (£_k, C) – задачи; тогда направляющей строкой является i+k+1-я строка, k =0, 1, 2,…. Поэтому на каждом этапе преобразования таблицы вектор A_i+k+i будет выводиться из таблицы. Можно доказать, что через конечное число шагов либо будет найдено целочисленное решение, либо будет обнаружена ее неразрешимость, а тем самым неразрешимость (£^ц, C) – задачи.

Если решение (£_k, C) – задачи завершается построением оптимального целочисленного решения x*, то m, первых его компонент определяют решение целочисленной задачи; если среди координат х* есть дробные, то одна из дробных компонент (ранее определенным правилом) порождает дополнительное ограничение и процесс решения должен быть продолжен с новой окаймляющей строкой. Строка, используемая ранее для окаймления, вычеркивается и больше для построения расширенных задач не восстанавливается.

Процедуру решения (£_k, C) – задачи (k=0, 1,…) и анализа полученного решения назовем большой итерацией. Номер большой итерации совпадает с номером решаемой (£_k, C) – задачи.

Результатом большой  итерации является переход к новой (£_k+1, C) – задаче либо окончание решения задачи.

Теорема. Пусть множество оптимальных планов задачи (£₀, C) ограничено и выполняются следующие условия:

1) с_i – целые коэффициенты целевой функции F(x) (i =1,2,…, n), строка целевой функции в симплексной таблице учитывается при выборе строки для построения правильного отсечения;

2) справедливо одно  из двух утверждений: либо целевая  функция  ограничена снизу на С_o, либо задача (£^ц, C) имеет хотя бы один план х'.

Тогда первый алгоритм Гомори требует конечного числа больших  итераций.

 

 

2.2 Второй алгоритм Гомори

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

Пусть в области, определенной условиями:

(20); (21)

 – целые,  (22)

требуется максимизировать функцию

(23)

Метод решения задачи (20–23) основывается на той же идее, что и метод решения полностью целочисленных задач. А именно: строится область £_k, которая при k = 0 определяется условиями (20–21); решается полученная при этом задача линейного программирования (20–21, 23). Если задача (20–21, 23) оказывается разрешимой, то полученное оптимальное решение ее анализируется на допустимость для исходной задачи целочисленного программирования (20–23). Если найденное решение оказывается целочисленным, то одновременно оно будет оптимальным для (20–23). Если оптимальное решение (£_k, C) – задачи оказывается недопустимым для исходной задачи (20–23), то осуществляется построение правильного отсечения и переход к решению новой задачи,

Второй алгоритм Р. Гомори формулируется в виде следующей теоремы:

Теорема. Пусть х(£_k, C) – оптимальное решение (£_k, C) – задачи, – элементы соответствующей ему симплексной таблицы. Если – нецелое , то (24); – целое, (25)

где

  (26)

определяет правильное отсечение. Блок-схема второго алгоритма Р. Гомори аналогична блок-схеме первого алгоритма Р. Гомори и отличается лишь правилом построения коэффициентов правильного отсечения.

Правило построения правильного отсечения

Пусть x(£_k, C) не удовлетворяет условию целочисленности, – элементы симплексной таблицы, соответствующей полученному оптимальному решению (£_k, C) – задачи. Выберем i₀=min {i | i Î (1, 2,…, n), x_i0^k – нецелое} и строим правильное отсечение по формулам (24 – 26).

Условия конечности второго  алгоритма Гомори:

1) Целевая функция F(x) удовлетворяет условию целочисленности. Это учитывается при выборе строки k для построения правильного отсечения.

2) Выполнено по крайней  мере одно из двух условий:

2') целевая функция ограничена снизу на многогранном множестве £= £₀;

2») задача (£₀^ц, C) имеет по крайней мере один план.

С помощью второго  алгоритма Гомори можно (в случае n₁=n) решать и полностью целочисленную задачу линейного программирования. Однако в этом случае нет оснований для сравнения эффективности второго и первого алгоритмов Гомори.

 

 

 

Заключение

 

Попробуем охарактеризовать поведение алгоритмов метода отсечения  при решении задач целочисленного линейного программирования. В качестве меры продолжительности вычислений могут рассматриваться количество симплексных итераций I и количество правильных отсечений (дополнительных линейных ограничений) D.

Для первого алгоритма  Гомори и различных его обобщений I и D также тесно связаны между собой (как показывает эксперимент, в большинстве случаев решение отдельной задачи (£, С) требует сравнительно небольшого количества симплексных итераций).

Переходим к изложению  отдельных свойств алгоритмов метода отсечения.

Числа I и D имеют (в среднем) тенденцию к возрастанию с увеличением числа переменных и ограничений, ростом порядка коэффициентов задачи и увеличением заполненности матрицы .

Это явление кажется  естественным, но опыт показывает, что в дискретном программировании «естественное» и «правдоподобное» не всегда оказывается правильным. Точнее говоря, опыт, накопленный на задачах линейного программирования, нельзя механически переносить на задачи целочисленного линейного программирования.

Прежде всего, обращает на себя внимание «нерегулярность», «непредсказуемость»  поведения алгоритмов метода отсечения. Для ряда задач оптимальное решение  не удавалось получить после многих тысяч итераций, в то время как  другие задачи решались за несколько десятков итераций.

Большое влияние на число  итераций оказывает правило выбора порождающей строки. Здесь также  имеет место «нерегулярность» – в то время как одно правило приводит к успеху за десятки итераций, другое не дает решения после тысяч итераций.

В настоящий момент отсутствует  исчерпывающее объяснение удач или  неудач различных вычислительных экспериментов. Все же для задачи коммивояжера и  задачи теории расписаний является правдоподобным следующее соображение.

Формулировка этих задач на языке целочисленного программирования является «неестественной». Для задачи сравнительно небольшой в «естественной» формулировке, в модели целочисленного линейного программирования фигурирует большое количество ограничений и переменных. Возможно, что для этих задач более перспективными являются комбинаторные методы (например, метод ветвей и границ для задачи коммивояжера). Впрочем, последнее утверждение является спорным, так как комбинаторные методы очень чувствительны к специфике задач, введению дополнительных условий и т.п.