Метод ветвей и границ. Метод отсечения

Размещено на http://www.allbest.ru/

Метод ветвей и границ. Метод отсечения

1. Целочисленное линейное программирование

линейный программирование целочисленный базисный

Под задачей целочисленного линейного программирования (ЦЛП) понимается задача линейного программирования, в которой некоторые (а возможно, и все) переменные должны принимать целые значения.

Задача ЦЛП называется полностью целочисленной, если все её переменные должны быть целочисленными. Для смешанной задачи ЦЛП лишь некоторые переменные предполагаются целочисленными, а остальные могут принимать произвольные (нецелые) значения.

Задачу ЦЛП можно решить, например, как задачу ЛП без учёта условий целочисленности переменных, а затем округлить полученное решение. Использование такого подхода требует проверки допустимости полученного решения. Таким методом часто пользуются при решении практических задач, особенно когда значения переменных настолько велики, что можно пренебречь ошибками округления. Однако при решении задач, в которых целочисленные переменные принимают малые значения, округление может привести к далёкому от истинного оптимума целочисленному решению. Кроме того, при решении задач большой размерности такой метод требует слишком много машинного времени. Например, пусть оптимальное решение соответствующей задачи ЛП имеет вид x1 = 2,4; x2 = 3,5. Для получения приближённого оптимального решения необходимо рассмотреть четыре точки (2;3); (2;4); (3;3); (3;4) и выбрать среди них допустимую точку с наилучшими значениями целевой функции. Если в задаче имеются 10 целочисленных переменных, то следует рассмотреть 210 = 1024 варианта целочисленного решения. Но даже рассмотрение всех вариантов не гарантирует получения оптимального целочисленного решения задачи.

2. Метод ветвей и границ

Одним из методов решения как полностью целочисленных, так и смешанных задач ЦЛП является метод ветвей и границ. Он представляет собой эффективную процедуру перебора всех целочисленных допустимых решений.

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

Для определения переменной, по которой производится начальное ветвление, разработан ряд правил:

1. Выбор целочисленной переменной, значение которой в оптимальном решении ЛП-1 имеет наибольшее дробное значение.

2. Приоритетной является переменная, коэффициент которой в целевой функции превосходит остальные.

3. Выбор переменной с наименьшим номером.

Для дальнейшего ветвления выбираются следующие вершины.

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

Произвольным образом выбирается задача ЛП, решавшаяся последней.

Промежуточная вершина является прозондированной в том случае, если она удовлетворяет хотя бы одному из следующих условий:

1. Оптимальное решение, соответствующее данной вершине целочисленно.

2. Задача ЛП, соответствующая рассмотренной вершине, не имеет допустимых решений.

3. Оптимальное значение f (x) соответствующей задачи ЛП не превосходит текущей нижней границы.

При использовании метода ветвей и границ выбор вершины для дальнейшего ветвления происходит до тех пор, пока остаётся хотя бы одна не прозондированная вершина. Прозондированная вершина с наилучшим значением f (x) даёт оптимальное решение исходной задачи ЦЛП. Получение перед реализацией метода ветвей и границ допустимого целочисленного решения задачи ЦЛП может оказаться весьма полезным, так как оно даёт начальную нижнюю границу, используемую до получения лучшей нижней границы по методу ветвей и границ.

Анализ опыта решения практических задач привёл к выработке ряда рекомендаций который можно использовать для уменьшения времени вычислений.

1. Количество целочисленных переменных следует уменьшить насколько возможно. Например, целочисленные переменные, значения которых должны быть не меньше 20, можно рассматривать как непрерывные.

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

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

4. Можно заканчивать реализацию метода ветвей и границ, если для задач максимизации выполняется соотношение:

.

5. Рекомендуется выбирать для ветвления целочисленные переменные в порядке убывания их приоритета, назначаемого в соответствии с технико-экономической интерпретацией переменных и опытом пользователя.

3. Метод отсечения

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

При решении многих задач (планирование мелкосерийного производства, распределение кораблей по путям сообщения, выработка суждений типа "да-нет" и т.п.) нецелочисленное решение не имеет смысла. Попытка тривиального округления до целых значений приводит либо к нарушению ограничений задачи, либо к недоиспользованию ресурсов. Как мы имели возможность убедиться, для произвольной линейной программы (за исключением программ типа классической транспортной задачи, где коэффициенты матрицы ограничений равны 1 или 0) гарантировать целочисленность решения невозможно.

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

B общем случае выдвигается идея последовательного отсечения нецелочисленных оптимальных планов: обычным симплексным методом отыскивается оптимальный план и, если он нецелочисленный, строится дополнительное ограничение, отсекающее найденный оптимальный план, но не отсекающее ни одного целочисленного плана.

Эта идея, принадлежащая Д. Данцигу и Р. Гомори, впервые была представлена в форме дополнительного ограничения:

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

К сожалению, для абсолютного большинства задач скорость сходимости процесса таких отсечений мала. Потому Р. Гомори предложена другая форма дополнительного ограничения. Так, если компонента плана, определяемая k-ым уравнением системы ограничений, нецелочисленна, то добавляется ограничение

где fk - дробная часть компоненты плана (правой части ограничения) и fkj - дробная часть коэффициента при Xj (целая часть числа - наибольшее целое, не превышающее это число; дробная часть числа равна разности между числом и его целой частью), S* - новая дополнительная переменная.

Например, если ограничение имеет вид

то дополнительное ограничение принимает вид

Можно уменьшить объем преобразований, если руководствоваться следующими правилами:

1. выбирать в качестве базового для построения дополнительного ограничения уравнение, определяющее компоненту плана с наибольшей дробной частью;

2. для ввода в базис опорного плана расширенной задачи выбирать переменную, для которой достигается минимум из отношений абсолютных значений j к значениям fkj;

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

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

Заметим, что для целочисленных программ может обнаружиться отсутствие целочисленных планов (противоречивость ограничений).

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

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

Размещено на Allbest.ru