Решение одномерной и многомерной задачи о ранце методом ветвей и границ

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

3

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

КУРСОВАЯ РАБОТА

по дисциплине «Методы оптимизации»

на тему

Решение одномерной и многомерной задачи о ранце

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

Выполнил

Тюнин Р.В.

Воронеж 2012

Содержание

Введение

1. Постановка задачи о рюкзаке

2. Методы решения задач о рюкзаке

2.1 Классификация методов

2.2 Метод ветвей и границ в общем виде

2.3 Стратегии метода ветвей и границ в решении задач

2.4 Примеры решения задач

Заключение

Список использованной литературы

Введение

Классическая задача о рюкзаке (о загрузке) известна очень давно, ниже приведена ее формализация. Пусть есть N разных предметов, каждый предмет имеет вес w_i и полезность p_i , так же имеется максимальный вес W, который можно положить в рюкзак. Требуется собрать такой набор предметов P, чтобы полезность их была наибольшей, а суммарный вес не превышал W.[6]. Конечно, никто не собирается писать программу, чтобы наилучшим образом загрузить рюкзак, отправляясь в поход или в путешествие, тут все слишком просто, и никто не задумывается об этом, но существует и более широкое применение.

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

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

1. Каждый предмет можно брать только один раз.

2. Каждый предмет можно брать сколько угодно раз.

3. Каждый предмет можно брать определенное количество раз

4. На размер рюкзака имеется несколько ограничений.

5. Некоторые вещи имею больший приоритет, чем другие

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

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

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

1. Постановка задачи о рюкзаке

Задача о ранце - одна из задач комбинаторной оптимизации. Классическая задача о ранце известна очень давно. Вот её постановка: Имеется набор из N предметов, каждый предмет имеет массу Wi и полезность Vi, i=(1,2..N), требуется собрать набор с максимальной полезностью таким образом, чтобы он имел вес не больше W, где W - вместимость ранца. Традиционно полагают что W_i , V_i , W, P - целые неотрицательные числа, но встречаются и другие постановки, условия в которых могут отличаться[6]. Возможны следующие вариации задачи:

Каждый предмет можно брать только один раз. Формализуем. Пусть задано конечное множество предметов

,

для каждого значения определена стоимость p_i и вес w_i , тогда нужно максимизировать , при ограничениях , где W-вместимость ранца, а x_i=1, если предмет взят для загрузки и x_i=0 если не взят. Если на размер рюкзака имеется только одно ограничение, то задача называется одномерной, в противном случае - многомерной.

Каждый предмет можно брать m раз. Формализация аналогична, разница лишь в том, что x_i принимает значения на интервале (0..m).

Каждый предмет можно брать неограниченное количество раз. Очевидно, что x_i лежит в диапазоне (0..[W/w_i]) квадратные скобочки означают целую часть числа [6].

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

2. Методы решения задачи о рюкзаке

2.1 Классификация методов

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

2.2 Метод ветвей и границ в общем виде

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

По существу данный метод - это вариация полного перебора, с исключениями заведомо не оптимальных решений. Для полного перебора можно построить дерево решений. Если у нас есть какое то оптимальное решение P, мы пытаемся улучшить его, но если на рассматриваемой в текущий момент ветви решение заведомо хуже чем P то следует остановить поиск и выбрать другую ветвь для рассмотрения. Тогда используя метод ветвей и границ можно сократить дерево перебора до такого, рис. 1. Видно сразу, что количество вариантов для перебора уменьшилось сразу. А именно осталось 8 вариантов исхода, вместо 24 ранее. Но не всегда получается отсеять достаточно много вариантов чтобы скорость работы была заметно увеличена, всегда можно подобрать такие входные данные, для которых метод ветвей и границ даст оценку по времени идентичную полному перебору.

Рис 1. Использование метода ветвей и границ

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

При построении дерева в алгоритме ветвей и границ для задачи целочисленного программирования (ЦЛП) требуются две вещи:

1. Ветвление. Множество решений, представляемое вершиной, можно разбить на попарно непересекающиеся множества. Каждое подмножество в этом разбиении представляется сыном исходной вершины.

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

Рис. 2. Основной алгоритм ветвей и границ

2.4 Стратегии метода ветвей и границ в решении задач

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

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

Во-вторых, нужно вычислять нижние границы. При этом часто имеется выбор между границами, которые относительно точны, но требуют относительно большего времени вычисления, и границами, которые не столь точны, но которые можно быстро вычислить.

Аналогичные противоречия могут существовать и при выборе отношения доминирования.

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

Примеры задач, при решении которых применяется метод ветвей и границ:

а) задача о ранце;

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

в) задача коммивояжера.

Возможно применение метода в решении самых сложных задач, когда неприменимы классические математические методы, а также линейное, нелинейное и динамическое программирование.

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

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

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

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

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

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

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

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

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

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

2.5 Примеры решения задач

Рассмотрим следующий пример.

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

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

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

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

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

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

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

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

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

ЗЛП-1

ЗЛП-2

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

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

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

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

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

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

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

ЗЛП-3

ЗЛП-4

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

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

Рисунок 6. Решение задачи ЗЛП-3

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

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

Таким образом, ветвление всех задач закончено. Получено 2 целочисленных решения:

· в задаче ЗЛП-3 - точка ;

· в задаче ЗЛП-4 - точка .

Рисунок 7. Решение задачи ЗЛП-4

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

Информацию, полученную из задач ЗЛП-0 - ЗЛП-4, можно отметить на дереве решений рисунок 7.

Рисунок 8. Дерево решений задачи

Заключение

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

Литература

1. Вирт, Н. Алгоритмы и структуры данных [Текст] / Н. Вирт. - Пер. с англ.-М.Мир, 1989.-360 с., ил.

2. Визгунов, Н.П. Динамическое программирование в экономических задачах с применением системы MATLAB [Текст] / Н.П. Визгунов. - Н.Новгород.: ННГУ, 2006. - 48 с.

3. Кузюрин, Н.Н Сложность комбинаторных алгоритмов. Курс лекций [Текст] / Н.Н. Кузюрин, С.А.Фомин. - 2005. - 79 с.

4. Гери, М. Вычислительные машины и труднорешаемые задачи [Текст] / М. Гери, Д. Джонсон. - М.: Мир, 1982 - 416 с.

5. Окулов, С. М - Программирование в алгоритмах [Текст] / С.М. Окулов. - М.: БИНОМ. Лаборатория знаний, 2004. - 341 с.: ил.

6. Окулов, С.М. Информатика в задачах [Текст] / С.М. Окулов, А.А, Пестов, О.А. Пестов. - Киров: Изд-во ВГПУ, 1998. -- 343с.

7. Царев, В.А. Проектирование, анализ и программная реализация структур данных и алгоритмов: Учебное пособие [Текст] / В.А. Царев, А.Ф. Дробанов. - Череповец., 2007. - 169 с.

8. Акулич, И.Л Динамическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов [Текст] / И.Л. Акулич. - М.: Высш. шк., 1986. - 319 с., ил.

9. Хаггари, Р. Дискретная математика для программистов [Текст] / Р. Хаггари. - М.: Техносфера, 2003. - 320с.

10. Кормен, Т. Алгоритмы: построение и анализ [Текст] / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. -- Под ред. И. В. Красикова. -- 2-е изд. -- М.: Вильямс, 2005. -- 1296 с.

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