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

УЧЕБНЫЕ ВОПРОСЫ И РАСЧЕТ ВРЕМЕНИ

УЧЕБНЫЕ И ВОСПИТАТЕЛЬНЫЕ ЦЕЛИ

Занятие № 16. Метод ветвей и границ решения ЗЦЛП.

Тема № 4. Целочисленные задачи ТПР.

Теория принятия решений

По учебной дисциплине

ЛЕКЦИЯ

Обсуждено на заседании ПМК

"___" августа 2009 г.

Протокол № 1

1. Изучить алгоритм метода ветвей и границ.

2. Рассмотреть алгоритм Литтла решения задачи коммивояжера.

3.. Воспитывать творческий подход и настойчивость при изучении дисциплины

Время: 2 часа. Место: Аудитория.

МАТЕРИАЛЬНОЕ ОБЕСПЕЧЕНИЕ:

Литература : Орлов А.И. Теория принятия решений. Учебник. М., «Экзамен», 2006.

Наглядные пособия: дидактический материал (слайды).

Технические средства обучения: “Лектор–2000”.

I.	Введение		мин.
II.	Учебные вопросы
	1. Общая схема метода ветвей и границ.		мин.
	2. Алгоритм Литтла решения задачи коммивояжера		мин.
III.	Заключение		мин.

ВВЕДЕНИЕ

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

Объявить студентам о том, что они продолжают изучение темы «Линейные задачи ТПР», играющей важнейшую роль в понимании сущности дисциплины. Довести до студентов, что данная тема включает 16 часов аудиторных занятий, из которых 8 часов лекций, 6 часов практических занятий и 2 часа лабораторных работ.

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ИЗЛОЖЕНИЮ УЧЕБНЫХ ВОПРОСОВ

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

При изложении второго вопроса рассмотреть алгоритм Литтла решения задачи коммивояжера. Изложение учебного материала проводится с элементами диалогового метода, при этом студентам задается следующий вопрос: ´ Является ли алгоритм Литтла частным случаем метода ветвей и границ?.

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

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

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

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

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

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

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

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

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

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

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

0 £ х_j £ d_j,

которая в непрерывном оптимальном решении оказалась нецелочисленной и равной x_j^*. Тогда целочисленное значение этой переменной может достигаться либо в интервале 0 £ х_j £, либо в интервале +1£ х_j £ d_j, где - целая часть .

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

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

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

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

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

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

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

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

1. Задается начальное значение рекорда и в список задач помещается исходная задача без требования целочисленности переменных.

2. Анализируется список задач: если он пуст, то переход на шаг 6. Иначе выбирается одна из задач с удалением ее из списка.

3. Выбранная задача решается одним из методов линейного программирования. Если задача неразрешима или оптимальное значение критерия L* £ Z, ветвь обрывается (задача прозондирована). Переход на шаг 2.

4. Полученное решение анализируется на целочисленность. Если решение целочисленное, оно фиксируется, рекорду присваивается оптимальное значение критерия решенной непрерывной задачи (Z:= L*), ветвь обрывается и осуществляется переход на шаг 2.

5. Выбирается одна из переменных, имеющих нецелочисленные значения. По ней производится ветвление: порождаются 2 задачи, одна образуется присоединением к решенной (родительской) задаче условия х_j £, другая – добавлением к родительской ограничения х_j³ +1. Эти задачи заносятся в список задач. Переход на шаг2.

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

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

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

L= 9 x ₁ + 5 x ₂ ® max;

3 x ₁ - 6 x ₂ ³ 1;

5 x ₁ +2 x ₂ £ 28;

" x_j ³ 0, целые.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

Дать задание на самостоятельную работу (отводимое время 4 часа):

ó с целью более глубокого освоения материала повторить и более подробно изучить линейную оптимизацию. Литература: [2] с. 25…36, конспект лекций,

При необходимости ответить на возникшие вопросы.

Старший преподаватель кафедры программного обеспечения И.Денисова

Дата добавления: 2014-01-11