Начало развитию подхода, получившего название метод ветвей и границ, положила работа Ленд и Дойг (1960). Это, скорее, даже не метод, а концепция или процедурная оболочка, на основе которой стали разрабатывать алгоритмы решения целочисленных задач различной природы. Ценность предложенной идеи стала особенно заметна после появления первого точного алгоритма решения задачи коммивояжера, построенного по схеме ветвей и границ (Литтл с соавторами, 1963). Метод можно применять как к полностью, так и частично целочисленным задачам.

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

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

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

Очевидно, что если, например,V 22 окажется хуже рекорда илиD 22 =, правая ветвь обрывается (говорят также, что она прозондирована). Если же оценкаV 22 будет лучше Z , производится ветвление: множествоD 22 разбивается на 2 подмножества. Решение завершится, когда все ветви будут прозондированы.

Вид оценки зависит от направленности критерия: при максимизации используется верхняя оценка, при минимизации – нижняя. Последующее изложение метода будет относиться к задаче на максимум.

Для алгоритмической реализации схемы ветвей и границ необходимо решить два основополагающих вопроса:

Каким образом разбивать перспективное множество на подмножества;

Как определять верхнюю оценку критерия на рассматриваемом множестве.

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

Пусть известен диапазон возможных значений j -й переменной

0  х j  d j ,

которая в непрерывном оптимальном решении оказалась нецелочисленной и равной x j * . Тогда целочисленное значение этой переменной может достигаться либо в интервале 0  х j 
,либо в интервале
+1 х j  d j , где
- целая часть (рис. 7.6).

Это соответствует разбиению непрерывного множестваD н на два непересекающихся подмножества D 1 н и D 2 н , объединение которых не равно D н . В то же время такое разбиение целочисленного множества удовлетворяет соотношениям (7.9). При этом целочисленные множества, как исходное, так и порожденные, включены в соответствующие непрерывные множества. Следовательно, поиск целочисленного решения на непрерывном множестве даст тот же результат, что и на целочисленном. Легко увидеть, что приведенное выделение подинтервалов по одной переменной приводит к разбиению исходного множества на два подмножества при любом числе переменных.

Теперь перейдем ко второму вопросу. Так как целочисленное множество является подмножеством соответствующего непрерывного, оптимальное значение критерия на непрерывном множестве всегда будет не меньше, чем на целочисленном. Поэтому в качестве верхней оценки V можно брать оптимальное значение критерия L * непрерывной задачи.

Выбор начального значения рекорда зависит от ситуации:

если известно какое-либо целочисленное значение, то рекорд принимается равным критерию в этом решении;

при положительности всех коэффициентов критерия можно взять нулевое значение рекорда;

в иных случаях за начальное значение рекорда берется –М , где М- максимально представимое в компьютере число.

По ходу разбиения формируются порождаемые задачи, которые помещаются в список задач. Первоначальный список содержит только одну задачу – исходную задачу без условий целочисленности. И в последующем список будет содержать только непрерывные задачи.

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

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

Пример 7.3 . Применим алгоритм ветвей и границ к задаче

L= 9x 1 + 5x 2  max;

3x 1 - 6x 2  1;

5x 1 +2x 2  28;

 x j  0 , целые.

Отбрасывая условие цедочисленности, получаем непрерывную задачу, которую помещаем в список задач. Так как коэффициенты критерия положительны, начальное значение рекорда принимаем равным нулю. Берем из списка единственную задачу и решаем ее. Получаем оптимальное решение в вершине А (рис. 7.7):x 1 * =4,72; x 2 * =2,19 . Ветвление производим по переменнойx 1 . Добавляя к решенной задаче ограничение x 1 4, образуем задачу 2, а добавление x 1 5 дает задачу 3. Допустимые множества новых задач покзаны на рис. 7.7. Эти задачи помещаем в список задач. Решение задачи 2 достигается в точке В, а задачи 3 – в С. Весь ход решения исходной задачи представлен в виде дерева решений на рис. 7.10. Порядок решения задач из списка отражает счетчик итераций k . На 3-й итерации (задача 4) получено целочисленное решение со значением критерия 41 (точка D нарис. 7.8). Поэтому изменяется рекорд: Z =41.Задача 6 имеет нецелочисленное решение (вершина Е на рис. 7.9), задача 8 – целочисленное решение в точкеF. В результате после 7-й итерации рекорд становится равным 50.

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

Из приведенного дерева решений видно, что число задач в списке могло быть меньше при другом порядке решения задач. Действительно, если бы сначала были решены задачи правой ветви с рекордом Z= 50, то после решения задачи 2 не произошло бы ветвления, так как верхняя оценка оказалась бы ниже рекорда (V=L * =45,17<50).

Естественно возникает вопрос: а как на числе задач и дереве решений может отразиться выбор другой переменной для ветвления? Так, в нашем примере если после 1-й итерации произвести ветвление по переменнойx 2 , то получим дерево, показанное на рис. 7.11. Оно содержит на 2 задачи больше, чем на рис. 7.10. Конечно, оно может быть также другим при ином порядке решения задач.

Таким образом, число решаемых задач существенно зависит от выбора задачи из списка и переменной для ветвления.

Из алгоритма и приведенного примера следует, что ветвь обрывается по одной из трех причин:

неразрешимость задачи;

задача имеет целочисленное решение;

верхняя оценка не больше рекорда.

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

Метода ветвей и границ имеет преимущества в сравнении с методом отсечений:

накопление ошибок менее значительное, так как решение идет по разным ветвям;

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

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

Недостатки метода ветвей и границ:

Нельзя оценить число задач, которые придется решать. Чем ближе снизу начальное значение рекорда и сверху оценка критерия задачи к искомому оптимальному значению критерия, тем меньше вершин будет иметь дерево решений, а значит, и затрат ресурсов. Однако завышение начального рекорда может привести к неразрешимости задачи, что всегда следует иметь в виду.

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

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

Требуется решить следующую задачу:

max 2х 1 + х 2

5х 1 + 2х 2 10

3х 1 + 8х 2 13

Вначале решим эту задачу графически без ограниченийцелочисленности. Решение может быть найдено как симплекс-методом, так и графически. Найдем его графически (рисунок 4). Координаты точки оптимума можно найти, решив систему уравнений: 5х 1 + 2х 2 = 10 х 1 =27/17

3х 1 + 8х 2 = 13 х 2 =35/34

Х G = (27/17;35/34), z G =143/34

Рисунок 4 - Графическое решение задачи без ограничений целочиелейности

Начнем строить дерево, первая вершина которого будет соответствовать всей ОДП нецелочисленной задачи (G), а ее оценка будет равна z G (рис.5).

Рисунок 5 - Схема метода ветвей и границ

Полученный план не является целочисленным, поэтому возьмем его произвольную нецелочисленную компоненту, например, первую (х 1 Z; [х 1 ] = = 1) и разобьем ОДП на две части следующим образом:

G 1 ={XG: х 1 1}

G 2 ={XG: х 1 2}

Это означает, что в область G 1 войдут все точки из G, у которых абсцисса не больше 1, а в G 2 - у которых она не меньше 2. Точки с дробными значениями абсциссы от 1 до 2 исключены из рассмотрения.

Изобразим эти области на графике (рисунок 6).

Из рисунка 6 видно, что G 2 представляет собой одну точку Х G 2 =(2;0), следовательно, на этом множестве оптимум задачи равен 4 ( 2 =4).

План Х G 2 является целочисленным, следовательно, решение целочисленной задачи уже, возможно, найдено. Однако, следует еще найти оценку множества G 1 |. Она может оказаться не менее 4 (но обязательно не более 143/34). Если это так, то нужно проверить, не является ли целочисленным решение задачи на G 1. Если оно целое, то является решением задачи, а если нет, то процесс решения необходимо продолжить, разбивая G 1

Рисунок 6 - Разбиение множества на части

На G 1 точку оптимума можно найти, решив систему уравнений:

х 1 = 1 х 1 =1

3х 1 + 8х 2 = 13 х 2 =5/4

Х G 1 = (1; 5/4), z G =13/4

Оценка меньше 4, следовательно, решением задачи является Х * =Х G 2 =(2;0),z * =4.

3.4 Решение задачи целочисленного линейного программирования методом ветвей и границ с помощью ппп «Система деловых задач»

ЗЦЛП можно решить с помощью пакета прикладных программ “Quantitative Systems for Business” ("Система деловых задач") . Соответствующая программа запускается файлом intlprog.ехе. Она решает как частично, так и полностью целочисленные задачи линейного программирования с числом переменных и ограничений до 20, используя метод ветвей и границ. В том числе решаются и задачи с булевыми переменными (т.е. с переменными, которые могут принимать одно из двух значений - 0 или 1; как, например, в задаче о назначениях ). По умолчанию все переменные неотрицательны. Программа позволяет ввести целочисленные границы для переменных, не включая их в общее число ограничений. По умолчанию нижняя граница 0, а верхняя 32000. Если необходимо установить нецелочисленные границы, их вводят, как обычные ограничения.

Если в задаче имеется несколько оптимальных планов, из них находится только один. Информация о наличии множественного решения не выводится.

Режим 2 (ввод новой задачи) включает три этапа. На первом этапе осуществляют ввод информации о размерности задачи, направлении экстремизации и именах переменных (по умолчанию XI, Х2,..., Хn).

На втором этапе необходимо определить, являются ли все переменные целочисленными, являются ли все переменные булевыми, и будут ли вводиться границы для переменных. При ответе «нет» на первый вопрос или «да» на третий, выводится таблица (рисунок 7):

Введите предел и границы для переменных

(По умолчанию значения нижней границы 0 и верхней границы 32000)

№ перем. Имя Предел (I/C) Нижняя гр. Верхняя гр.

1 X 1 <0 > <0 >

2 X 2 <0 > <0 >

Рисунок 7 - Определение пределов и границ

Установив I (integer) в столбце «Предел», на переменную накладывают ограничение целочисленности. В противном случае (С, continuous) -переменная может принимать и нецелые значения, т.е. является непрерывной.

Значения границ округляются до целых. Если нижняя больше верхней, выдается сообщение об ошибке.

На третьем этапе вводятся коэффициенты при переменных и знаки в ограничениях.

В меню решений имеется возможность исправить целочисленную погрешность (по умолчанию она 0,001).

Решение задачи методом ветвей и границ не сопровождается графической иллюстрацией (изображением дерева) в программе, но для пояснения алгоритма приведем такую иллюстрацию на рисунок 8.

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

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

При этом на каждой итерации выводится информация о текущих целочисленных границах (определяющих рассматриваемое подмножество), оптимальном плане нецелочисленной задачи, о том, является ли он целочисленным, о значении целевой функции (ЦФ) на нем и о величинах ZL или ZU. Для задачи на максимум выводится значение нижней границы ZL, а на минимум верхней ZU. До тех пор, пока не найдено какое-нибудь целое решение, ZL =-1*10 20 , а ZU = 1*10 20 .

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

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

Поясним это на примере (рис.8):

max 3х 1 + 2х 2

7х 1 + 5х 2 35

9х 1 + 4х 2 36

На первой итерации найдено нецелочисленное решение Х=(2,353; 3,706). Вся ОДП (множество G) разбивается на два подмножества - G 1 и G 2 следующим образом:

G 1 ={XG: х 1 3}

G 2 ={XG: х 1 2}.

На второй итерации решают задачу на подмножестве G 1 . Полученное решение также нецелочисленно. Далее, вместо того, чтобы рассмотреть подмножество G 2 , продолжают рассматривать G 1 . В соответствующем плане выбирают первую по счету нецелочисленную компоненту (это х 2) и разбивают G 1 на G 3 и G 4 . На третьей итерации рассматривают G 3 - на этом подмножестве допустимых планов нет. Только после этого на четвертой итерации рассматривается вторая ветвь, выходящая из G 1 - подмножество G 4 . Далее аналогично.

На пятой итерации на подмножестве G 5 найдено целочисленное решение, которому соответствует значение целевой функции 12. На следующей итерации это значение присваивается величине ZL, которая до этого была равна -1*10 20 . Соответствующий план запоминается - он может оказаться оптимальным. Но на шестой итерации снова получен целочисленный план, целевая функция на котором равна 13 (больше 12) - ZL снова изменяется, запоминается новый план.

После этого, на седьмой итерации, переходят к рассмотрению подмножества G 2 , которое разбивают на G 7 и G 8 .

На тринадцатой итерации (подмножество G 14) снова найдено целочисленное решение Х=(0; 7), целевая функция на нем равна 14. Снова изменяется ZL и запоминается соответствующий план.

План, найденный на четырнадцатой итерации, также является целочисленным, но его не запоминают, так как 13<14 (ZL=14). План, найденный на пятнадцатой итерации, тоже, к сожалению, не запоминается, так как 1414, а программа ставит своей целью найти хотя бы одно решение.

Наличие других оптимальных планов здесь игнорируется.

Таким образом, решение Х=(0; 7) получено за 15 итераций.

Отметим, что если бы использовался более эффективный вариант метода ветвей и границ, схема которого описана в методических указаниях, то после второй итерации произошел бы сразу переход к седьмой. В самом деле, если рассматривать значения целевой функции на соответствующих планах в качестве оценки подмножеств, то оценка G 2 выше. Поэтому итерации с 3-ей по 6-ю оказываются лишними, и общее число итераций могло быть равно 11.

Метод ветвей и границ − один из комбинаторных методов. В отличие от метода Гомори применим как к полностью, так и частично целочисленнным задачам.

Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам полезными для нахождения оптимального решения.

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

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

или
, или

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

Очевидно, что возможен один из следующих четырех случаев.

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

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

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

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

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

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

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

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

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

Пример . Найти методом ветвей и границ решение задачи целочисленного программирования

Решение . Находим оптимальный план сформулированной задачи симплексным методом без учета целочисленности переменных, а именно решаем задачу 1.

Оптимальный план задачи 1 линейного программирования

при
.

Для исходной задачи, с учетом целочисленности переменных, полученное решение не является оптимальным.

Для поиска целочисленного оптимального решения разделим интервал изменения переменной x 1 на две области, а именно x 1  и x 1 = 10 , и разобьем заданную задачу на две новые задачи.

Нижняя граница линейной функции не изменилась: Z 0 = 0. Решаем одну из задач, например задачу 3, симплексным методом. Получаем, что условия задачи противоречивы.

Решаем задачу 2 симплексным методом. Получаем оптимальный целочисленный план поставленной задачи 2, который является также оптимальным планом задачи 1:

при
.

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

ВВЕДЕНИЕ.................................................................................................. 3

1. ..…………….4

2. МЕТОД ВЕТВЕЙ И ГРАНИЦ ………………………………………..6

2.1 Алгоритм метода ветвей и грани ц…………………………………....10

ЗАКЛЮЧЕНИЕ………………………………………………………….14

СПИСОК ЛИТЕРАТУРЫ………………………………………… ………….15

ВВЕДЕНИЕ

Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его “второе рождение” связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче комивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера.

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

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

1. МЕТОД ВЕТВЕЙ И ГРАНИЦ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ. ОСНОВНЫЕ ПОНЯТИЯ

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

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

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

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

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

3. Если нет острой необходимости в нахождении точного оптимального целочисленного решения, отличающегося от непрерывного решения, например, 3%. Тогда реализацию метода ветвей и границ для задачи максимизации можно заканчивать, если отношение разницы между верхней и нижней границ к верхней границы меньше 0,03.

Метод ветвей и границ можно применять для решения задач нелинейного программирования.

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

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

2. МЕТОД ВЕТВЕЙ И ГРАНИЦ

Одним из широко распространенных методов решения целочислен­ных задач является метод ветвей и границ, который может быть ис­пользован как для задач линейного программирования, так и для задач, не сводимых к задачам линейного программирования. Рассмотрим идею метода ветвей и границ на примере общей задачи дискретного про­граммирования

f(X) -> max,

Х€D,

где D - конечное множество.

Сначала найдем оценку £(D) (границу) функции f(X), X е D: f(X) ≤ £(D) для V X е D. Если для некоторого плана Х° задачи справедливо равенствоf(X0) = £(D), то Х° = X* является решением задачи. Если указанное условие не выполняется, то возмож­но разбиение (ветвление) множества D на конечное число непересека­ющихся подмножеств D1i: ỤD1i. = D, ∩D1i = Ө, и вычисление оценки £(D1i) (границ), 1≤i≤m (Рисунок 2.1)

Рисунок 2. 1

Если для некоторого плана X1i е Di1, 1 ≤ / ≤ m выполняется условие f(Xkl)= £(D1k)≥ £(D1i), 1≤i≤m то Xk1=X* является оптимальным планом (решением) задачи (7.9)-(7.10).

Если такого плана нет, то выбирается подмножество Dkl с наиболь­шей оценкой £(D1i) и разбивается на конечное число непересекающихся подмножеств D2kj: UD2kj=D1k, ∩D2kj=Ө. Для каждого подмножества находится оценка £(D2kj), 1≤j≤n (Рисунок 2.2)

Рисунок 2.2

Если при этом найдется план X2j е D2kJ, 1 ≤j ≤n, такой, что f(X2r)= £(D2kr)≥ £(D2kj), 1≤j≤n, то X2r= X* является решением задачи. Если такого плана нет, то процедуру ветвления осуществля­ют для множества D2kj с наибольшей оценкой £(D2kj) , 1≤j≤n. Способ ветвления определяется спецификой конкретной задачи.

Рассмотрим задачу, которую можно свести к задаче целочисленного линейного программирования.

Пример.

Контейнер объемом 5 м3 помещен на контейнеровоз грузо­подъемностью 12 т. Контейнер требуется заполнить грузом двух наиме­нований. Масса единицы груза mj (в тоннах), объем единицы груза Vj (в м3), стоимости Cj (в условных денежных единицах) приведены в таблице 2.1.

Таблица 2.1

Вид груза у			С j

Требуется загрузить контейнер таким образом, чтобы стоимость пе­ревозимого груза была максимальной.

Решение. Математическая модель задачи имеет вид

Z(X) = 10x1+12x2→max,

3x1+x2≤12,

x1+2x2≤5

x1≥0

x2≥0

x1, x2- целые числа

где x1, x2 - число единиц соответственно первого и второго груза.

Множество планов этой задачи обозначим через D - это множество целых точек многогранника ОАВС (Рисунок 2.3).

Рисунок 2. 3

Сначала решаем задачу без условия целочисленности, получим оценку множества D - значение функции Z(X) на оптималь­ном плане Х° = (19/5, 3/5).

Точка X не является оптимальным планом задачи. По­этому в соответствии с методом ветвей и границ требуется разбить множество D на непересекающиеся подмножества. Выберем первую нецелочисленную переменную x1=19/5=34/5 и разобьем множество D на два непересекающихся подмножества D11 и D22. Линии x1=3 (L3) и x4= (L3) являются линиями разбиения.

Рисунок 2. 4

L \

Найдем оценки £(D11) и £(D12), для чего решим задачи линейного программирования.

Z(X)=10x1+12x2→max,

3x1+x2≤12

x1+2x2≤5

x1≤3

x1≥0, x2 – целые числа

Z(X)=10x1+12x2→max,

3x1+ x2≤12

x1+2x2≤5

x1≥4

x1≥0, x2 – целые числа

Например, графическим методом:

X11eD11→X01= (3,1); £(D11)=42; X12eD12→X02= (4,0); £(D12)=40.

Результат ветвления приведен на Рисунок 2.5

Рисунок 2. 5

План X01 удовлетворяет условиям задачи, и для него выполняется условие: Z(X11)= £(D11)=42 > £(/)/) = 42 >£(D12) = 40. Следовательно, план X°1= (3, 1) является решением задачи (7.11)-(7.13), т. е. надо взять три единицы первого груза и одну единицу второго груза.

2.1 Алгоритм метода ветвей и границ

· Находим решение задачи линейного программирования без учета целочисленности.

· Составляет дополнительные ограничения на дробную компоненту плана.

· Находим решение двух задач с ограничениями на компоненту.

· Строим в случае необходимости дополнительные ограничения, согласно возможным четырем случаям получаем оптимальный целочисленный план либо устанавливаем неразрешимость задачи.

Алгоритм действия метода ветвей и границ

Первоначально находим, к примеру, симплекс-методом оптимальный план задачи без учета целочисленности переменных. Пусть им является план X0. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и Fmax = F(X0).

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

Предполагая, что найденный оптимальный план X0 не удовлетворяет условию целочисленности переменных, тем самым считаем, что среди его компонент есть дробные числа. Пусть, например, переменная приняла в плане X0 дробное значение. Тогда в оптимальном целочисленном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу, либо больше или равно ближайшему большему целому числу font-size:14.0pt">font-size:14.0pt">Найдем решение задач линейного программирования (5) и (6). Очевидно, здесь возможен один из следующих четырех случаев:

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

2. Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам (5) и (6).

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

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

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

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

Общий алгоритм решения задач с помощью метода границ и ветвей, его суть

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

Итак, процесс нахождения решения задачи целочисленного программирования методом ветвей и границ включает следующие основные этапы:

1. Находят решение задачи линейного программирования.

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

3. Находят решение задач (5) и (6), которые получаются из задачи (1)-(3) в результате присоединения дополнительных ограничений.

4. В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам (5) и (6), и находят их решение.

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

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

Пример использования метода ветвей и границ

В качестве примера к методу ветвей и границ рассмотрим функцию z=4х1+х2+1®max при ограничениях:

font-size:14.0pt">Пусть Х0 = (0; 0), z0 = 1 - «оптимальное» решение. Выполним 1-й этап общего алгоритма и найдем с помощью симплекс-метода, а затем и двойственного симплекс-метода (см. Приложение 1) X1, исходя из ограничений Итак, X1 = (3; 0,5; 0; 1; 0; 2,5), z1= 13,5. Так как z1 дробное, то «оптимальным» так и остается план Х0,

Согласно 2-му пункту нашего плана, составим 2 новых системы ограничений для:

https://pandia.ru/text/79/453/images/image012_25.gif" alt="Описание: http://*****/images/paper/93/79/4327993.png" width="108" height="98"> .

Выполним 3-й пункт алгоритма. Для начала, решим задачу с помощью табличного процессора Microsoft Excel (Приложение 2) и получим X2 = (2; 1) z2= 10. Так как z2 ≥ z0, «оптимальным» становится план Х0.

Решим задачу. Из последнего уравнения очевидно, что x2 = 0. Отсюда следует, что x1 = 3 (максимально возможное). Тогда Х3 = (3; 0), z3 = 13, а следовательно, данный план является оптимальным (теперь уже без кавычек).

Нам не пришлось выполнять 4-й пункт нашего алгоритма в связи с тем, что оптимальное решение найдено, переменные целочисленные. Пример, в котором всё складывается не так просто, приведен в Приложении 3.

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ЛИТЕРАТУРЫ

1. А. Схрейвер. Теория линейного и целочисленного программирования: в 2-х томах.; перевод с английского. 1991г. 360с.

2. Т. Ху. Целочисленное программирование и потоки в сетях.; перевод с английского. 1974г.

3. , . Высшая математика: Математическое программирование. Ученик - 2-е издание. 2001г. 351с.

4. . Математическое программирование: Учебное пособие – 5-е издание, стереотип-М:ФИЗМАТ, 2001г.-264с.

5. , .: Экономико-математические методы и прикладные модели: Учеб. пособие для вузов/ЮНИТИ, 1999г.-391с.

6. , ; под ред. Проф. . : Исследование операций в экономике; учеб. Пособие для вузов.

Приложение 2

Решение задачи z = 4х1 + х2 +1 ® max при ограничениях:

с помощью табличного процессора Microsoft Excel.

Ниже приведено условие задачи и текстовая часть решения. Все решение полностью, в формате doc в архиве, вы можете скачать. Некоторые символы могут не отображаться на странице, но документе word все отображается. Еще примеры работ по ЭМММ можно посмотреть

ПОСТАНОВКА ЗАДАЧИ

Издательское предприятие должно выполнить в течении недели (число дней m = 5) работу по набору текста с помощью работников n категорий (высокая, средняя, ниже средней, низкая). Требуются определить оптимальную численность работников по категориям, при которой обеспечивается выполнение работы с минимальным расходом фонда зарплаты при заданных ограничениях. Исходные данные приведены в таблице 1 и 2.

Таблица 1

Таблица 2

Задача должна решаться методом целочисленного линейного программирования в Mathcad 2000/2001.

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ
РЕШЕНИЯ ЗАДАЧИ

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

Решение задачи целочисленного программирования выполняется в два этапа.

На первом этапе выполняется задача линейного программирования без учета целочисленности.

На втором этапе производится пошаговый процесс замены нецелочисленных переменных ближайшими верхними или нижними целыми значениями.

Сначала решается, задача без учета условия целочисленности.

Целевая функция определяется по формуле:

где Q - общий фонд зарплаты на выполнение работы;

x 1 , x 2 , …, x n - численность работников по категориям;

n - число категорий работников;

c 1 , c 2 ,…, c n - дневная тарифная ставка одного работника по категориям;

m - число рабочих дней в неделю, m = 5.

Целевую функцию можно записать в векторной форме:

При решении задачи должны выполняться следующие ограничения. Ограничение сверху

x ≤ d (1)

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

В ограничении

учтено, что общая численность работников не должна превышать k max .

В ограничении снизу

р × х≥Р (3)

отражается, что все работники вместе должны выполнить заданный объем работ Р .

В качестве последнего ограничения записывается условие неотрицательности вектора переменных

x ≥0 (4)

Математическая модель решения задачи без учета условия целочисленности включает следующие выражения:

x ≤ d

р × х≥Р ,

x ≥ 0 .

Модель целочисленного программирования должна включать выражения (5), а также дополнительные ограничения, с помощью которых нецелочисленные переменные х заменяются целочисленными значениями. Конкретные выражения модели с целочисленными переменными рассмотрены в следующем подразделе.

РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ В MATHCAD

Исходные данные для примера даны в табл. 1 и 2.

Для решения задачи используется пакет Mathcad с функцией Minimize. Данная функция определяет вектор решения задачи:

х := Minimize (Q , x ),

где Q — выражение целевой функции, определяющей минимальный фонд зарплаты, х - вектор переменных.

Сначала задача решается без учета условия целочисленности. Это решение приведено в Приложении 1. В первой строке введены нулевые начальные значения вектора х и целевая функция Q (x ) . После слова Given и перед функцией Minimize указаны ограничения. В результате получена нецелочисленная оптимальная численность по категориям:

х =

с фондом зарплаты Q = 135 у. е.

Из данного решения находится целочисленное решение методом ветвей и границ.

Сначала в полученном решении анализируется дробная величина х 4 =
= 1,143. Для нее можно задать два целочисленных значения: х 4 = 1 и х 4 = 2. Начинается построение дерева решений (Приложение 2). На дереве решений откладывается начальный нулевой узел. Затем он соединяется первым узлом х 4 , и из этого узла проводятся две ветви, соответствующие ограничениям: х 4 = 1 и х 4 = 2.

Для ветви с ограничением х 4 = 1 решается задача линейного программирования, данная в Приложении 1, с учетом этого ограничения.

В результате получено решение этой задачи. Переменная х 1 стала целочисленная, но переменная х 2 стала дробной х 2 = 0,9.

Для продолжения ветви создается узел х 3 и ветвь х 3 = 1. Снова выполняется задача линейного программирования со всеми тремя ограничениями: x 4 = 1, х 2 = 1, х 3 = 1. С этими ограничениями задача имеет решение х Т =
= (1,938 1 1 1).

Для продолжения ветви создается узел х 1 и ветвь х 1 = 2. Снова выполняется задача линейного программирования со всеми тремя ограничениями: x 4 = 1, х 2 = 1, х 3 = 1, х 1 = 2. С этими ограничениями задача имеет решение х Т = = (2 1 1 1).

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

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

Из результативных выбирается наилучшее и оно принимается как оптимальное целочисленное решение всей задачи с минимальной величиной Q (x ) . В нашем случае мы имеем два оптимальных целочисленных решения

Q (х) = 140,

x T = (2 1 1 1),

x T = (1 1 2 2).

Следовательно, издательская организация должна привлечь для набора текста двух работников высокой категории, одного работника средней категории, одного работника ниже средней категории и одного работника низкой категории. Возможен так же другой равнозначный вариант привлечения работников: один работник высокой категории, один работник средней категории, два работника категории ниже средней и два работника низкой категории. В обоих вариантах затраты будут минимальными и составят 140 ден. ед.

Скачать решение задачи:

Имя файла: 2.rar
Размер файла: 24.99 Kb

Если закачивание файла не начнется через 10 сек, кликните