Постановка классической задачи о рюкзаке, ее формализация, точные и приближенные алгоритмы решения. Классификация подходов метода ветвей и границ в общем виде. Стратегия его использования в решении задач линейного программирования графическим методом.
Аннотация к работе
КУРСОВАЯ РАБОТА по дисциплине «Методы оптимизации» на темуКлассическая задача о рюкзаке (о загрузке) известна очень давно, ниже приведена ее формализация. Пусть есть N разных предметов, каждый предмет имеет вес wi и полезность pi , так же имеется максимальный вес W, который можно положить в рюкзак. Конечно, никто не собирается писать программу, чтобы наилучшим образом загрузить рюкзак, отправляясь в поход или в путешествие, тут все слишком просто, и никто не задумывается об этом, но существует и более широкое применение. Задача о загрузке (задача о рюкзаке) и различные ее модификации широко применяются на практике в прикладной математике, криптографии, экономике, логистике, для нахождения решения оптимальной загрузки различных транспортных средств: самолетов, кораблей, железнодорожных вагонов и т.д. Рассматриваемая нами задача является NP - полной, то есть для нее не существует полиномиального алгоритма , решающего ее за разумное время, в этом и есть проблема.Задача о ранце - одна из задач комбинаторной оптимизации. Вот ее постановка: Имеется набор из N предметов, каждый предмет имеет массу Wi и полезность Vi, i=(1,2..N), требуется собрать набор с максимальной полезностью таким образом, чтобы он имел вес не больше W, где W - вместимость ранца. Возможны следующие вариации задачи: Каждый предмет можно брать только один раз. , для каждого значения определена стоимость pi и вес wi , тогда нужно максимизировать , при ограничениях , где W-вместимость ранца, а xi=1, если предмет взят для загрузки и xi=0 если не взят. Если на размер рюкзака имеется только одно ограничение, то задача называется одномерной, в противном случае - многомерной.На практике очень часто возникают NP-полные задачи, задач о рюкзаке - одна из них . Во первых, очень часто удается построить полиномиальный алгоритм для NP - полной задачи, конечно он даст приближенное, а не точное решение, но зато будет работать за реальное время. К точным методам относятся: Полный перебор, метод ветвей и границ, ДП - программирование.Метод ветвей и границ основан на идее разумного перечисления всех допустимых точек комбинаторной задачи оптимизации. Слово «ветвей» в названии «метод ветвей и границ» относится к процессу разбиения; слово «границ» относится к нижним оценкам, которые используются при построении доказательства оптимальности без полного перебора. Если у нас есть какое то оптимальное решение P, мы пытаемся улучшить его, но если на рассматриваемой в текущий момент ветви решение заведомо хуже чем P то следует остановить поиск и выбрать другую ветвь для рассмотрения. Тогда используя метод ветвей и границ можно сократить дерево перебора до такого, рис. Но не всегда получается отсеять достаточно много вариантов чтобы скорость работы была заметно увеличена, всегда можно подобрать такие входные данные, для которых метод ветвей и границ даст оценку по времени идентичную полному перебору.Имеется много вариантов применения алгоритма ветвей и границ к данной задаче. Во-первых, имеются варианты в самом ветвлении - может существовать много способов разбиения пространства решений, как, например, в общей задаче ЦЛП. Примеры задач, при решении которых применяется метод ветвей и границ: а) задача о ранце; В методе ветвей и границ две составляющие: ветви и границы. Если не отсекать ветви до полного их анализа, метод ветвей и границ сведется к полному перебору всех возможных вариантов.На рисунке 3. штриховкой выделен многоугольник решений данной задачи. Максимальное значение достигается в точке Решение не является целочисленным. Для этого добавим к задаче ЗЛП-0 два новых ограничения и Этими ограничениями удаляется интервал = в котором нет целых значений . Решим задачу ЗЛП-1 графически Решим задачу ЗЛП-2 графическиВ ходе исследования задачи о рюкзаке были выявлены три основных алгоритма решения. Так же был рассмотрен Метод ветвей и границ, но как сокращение полного перебора. Первая группа - точные методы, сюда входят ДП - алгоритмы, Полный перебор и Метод ветвей и границ. Вторая группа - приближенные методы, к таким методам относится Жадный алгоритм. Если требуется найти точное решение, то конечно нужно использовать точные методы, при небольшом наборе входных данных (предметов до 10-20), подойдет перебор или метод ветвей и границ в силу простоты реализации, при больших, следует использовать ДП - алгоритм.
План
Содержание
Введение
1. Постановка задачи о рюкзаке
2. Методы решения задач о рюкзаке
2.1 Классификация методов
2.2 Метод ветвей и границ в общем виде
2.3 Стратегии метода ветвей и границ в решении задач