Объяснить в чем заключается суть метода границ. Методы решения труднорешаемых задач

Общее описание

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

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

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

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

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

Применение

Метод используется для решения некоторых NP-полных задач, таких как:

См. также

Примечания

Wikimedia Foundation . 2010 .

Смотреть что такое "Метод ветвей и границ" в других словарях:

метод ветвей и границ - — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва] Тематики электротехника, основные понятия EN branch and bound method … Справочник технического переводчика

метод - метод: Метод косвенного измерения влажности веществ, основанный на зависимости диэлектрической проницаемости этих веществ от их влажности. Источник: РМГ 75 2004: Государственная система обеспечения еди … Словарь-справочник терминов нормативно-технической документации

Оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных 43 589 145 600. Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр … Википедия

У этого термина существуют и другие значения, см. Перебор. Полный перебор (или метод «грубой силы», англ. brute force) метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных… … Википедия

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

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

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

Книги

Разработка программного средства для поиска оптимального портфеля оптовых закупок торгового предприятия , А. В. Мищенко. В рамках настоящей работы разработано программное средство для решения задачи поиска оптимального портфеля оптовых закупок предприятия розничной торговли. При этом использован метод ветвей и…

Введение

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

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

Одним из широко распространенных методов решения целочисленных задач является метод ветвей и границ, впервые, он был предложен Ленд и Дойг в 1960 г.

ветвь граница линейное программирование

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

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

1. Процесс начинают с решения задачи симплексным или графическим методом без учета требования на целочисленность переменных. Эту задачу называют ЗЛП-0. Если все переменные оптимального плана целые, то этот план также является оптимальными для задач целочисленного программирования.

2. Если некоторая переменная, не получила целочисленного значения, то производится ветвление на две новые задачи ЗЛП-1, ЗЛП-2. Одна из задач ЗЛП-1 представляет собой задачу ЗЛП-0, дополненную ограничением где - целая часть числа. Вторая образуется путем добавления к задаче ЗЛП-0 ограничения. Следует отметить, что выбор целочисленной переменной может быть произвольным определяться следующим образом:

по возрастанию или убыванию индексов;

переменная представляет важное решение принимаемое в рамках данной задачи;

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

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

Процесс решения можно представить в виде дерева, в котором вершина ЗЛП-0 отвечает начальному плану решения задачи, а каждая из соединенных с ней ветвью вершин отвечает оптимальному плану следующей задачи.

Рассмотрим следующий пример. Максимизировать целевую функцию

при ограничениях

Воспользуемся графическим методом решения задачи линейного программирования.

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

Обозначим эту задачу линейного программирования ЗЛП-0.

На рисунке 1.1 штриховкой выделен многоугольник решений данной задачи. Максимальное значение достигается в точке Решение не является целочисленным.

Следующий шаг метода ветвей и границ состоит в ветвлении по одной из целочисленных переменных, имеющих дробное значение, например. Для этого добавим к задаче ЗЛП-0 два новых ограничения и Этими ограничениями удаляется интервал = в котором нет целых значений. Таким образом, в процессе ветвления создаются две новые задачи ЗЛП-1 и ЗЛП-2.

Рисунок 1.1 Решение задачи ЗЛП-0

2. Решим задачу ЗЛП-1 графически.

На рисунке 1.2 изображена допустимая область задачи ЗЛП-1. Максимальное значение достигается в точке. Решение задачи нецелочисленное.

Рисунок 1.2 Решение задачи ЗЛП-1

3. Решим задачу ЗЛП-2 графически.

В данном случае множество допустимых решений пусто (рисунок 1.2). Система ограничений несовместна, и задачу ЗЛП-2 можно исключить из дальнейшего рассмотрения.

Рисунок 1.3 Решение задачи ЗЛП-2

Теперь продолжим исследование задачи ЗЛП-1, поскольку значение нецелое. Произведем еще одно ветвление, путем введения ограничений и. В результате получаем две новые задачи ЗЛП-3 и ЗЛП-4.

Ниже приведено условие задачи и текстовая часть решения. Все решение полностью, в формате 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 сек, кликните

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

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

Алгоритм решения:

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

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

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

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

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

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

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

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

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

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

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

целочисленный программирование задача коммивояжер ранец

Рассмотрим задачу дискретного программирования в общем виде:

Найти -вектор неизвестных, D- конечное

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

Идея метода состоит в разбиении D на непересекающиеся подмножества Di (эта процедура называется ветвлением) и вычислении верхней и нижней границ целевой функции на каждом из подмножеств. Нижнюю границу будем обозначать Н, а верхнюю Е. Соответственно Hi Eo, то это подмножество не содержит точку оптимума и может быть исключено из дальнейшего рассмотрения. Если верхняя граница Ei H заменяем Н на min Hi. Если Е=Н, то задача решена, иначе надо продолжить процедуру ветвления и вычисления верхней и нижней границ. При этом разбиению на очередном шаге могут подвергаться все или только некоторые подмножества до достижения равенства верхней и нижней границ, причём не на отдельном подмножестве, а для допустимой области в целом.

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

Схему динамического программирования при движении от начальной точке к конечной (рис. 5.1) можно представлять как процедуру ветвления.

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

Рис. 5.1.

Теперь подмножествами Di являются множества траекторий, каждая из которых проходит через соответствующую i-ую точку.

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

Эффективность такого подхода зависит от точности получаемых оценок, т.е. от Ei - Hi, и от затрат времени на их вычисление.

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

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