Метод ветвей и границ для задач о рюкзаке

УДК 512.25/19

Інв. № 

Міністерство освіти і науки, молоді і спорту України

Національний аерокосмічний університет ім. М.Є. Жуковського

«Харківський авіаційний інститут» 
 
 

Кафедра 304 
 
 
 
 

ПОЯСНЮВАЛЬНА ЗАПИСКА  

до курсової роботи

з дисципліни: «Методи оптимізації і дослідження операцій»

                                        Тема:

                       «Метод ветвей и границ для задач о рюкзаке» 
 

     Виконала:

студентка 345а гр.

Борисенко А.В.

«__»_____________2011г. 

Перевірив:

канд. фіз.-мат. наук, доцент каф.304 Карташов А. В.

«___»__________    2011г. 

Нормоконтролер:

асистент  каф. 304

Пудло Р.А.

«___»__________    2011г. 
 
 
 

     Харків 2011

     РЕФЕРАТ 

    Пояснительная записка состоит из 37 листов, включает 12 иллюстраций, 1 приложение. При ее составлении использовалось 3 источника литературы.

    Темой разработки является «метод ветвей и границ для решения задач о рюкзаке (ранце)» с использованием современных средств программирования в среде Delphi. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ВВЕДЕНИЕ 3

1 ТЕХНИЧЕСКОЕ ЗАДАНИЕ 4

2 ПОСТРОЕНИЕ И АНАЛИЗ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ЗАДАЧИ О РЮКЗАКЕ 5

   2.1 Формализация предметной области 6

3 Алгоритм ПРИМЕНЕНИЯ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ ЗАДАЧ О РЮКЗАКЕ 7

4 ПРОЕКТИРОВАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ. ОПИСАНИЕ ПРОГРАММНОГО ПРОДУКТА 10

   4.1. Формат входных/выходных данных 10

   4.2 Работа программы 10

ВЫВОДЫ 15

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 16

ПРИЛОЖЕНИЕ А 21 
 
 
 
 
 
 
 
 

     ВВЕДЕНИЕ

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

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

1. Рассмотреть метод ветвей и границ;
2. Решить задачу о рюкзаке, опираясь на принципы метода ветвей и границ.

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

     1 ТЕХНИЧЕСКОЕ ЗАДАНИЕ

 

     Исходные данные: стоимость и вес рюкзака.

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

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

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

     Объект  исследования: задача о рюкзаке.

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

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

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

1. Формализация  предметной области

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

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

Метод Ветвей и  Границ широко используется для нахождения точного (оптимального) решения задач дискретной оптимизации.

Нам понадобится  следующее определение: 

Подзадачей задачи f(x0) = min (x∈G) f(x) называется задача f(x0) = min (x∈G`) f(x), где G` ⊆ G. 

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

• Ветвление. Множество G разбивается на подмножества Gi ⊆ G, i = 1, 2, . . . , r, причем U (i = 1..r) Gi = G. Таким образом, исходная задача разбивается на подзадачи, определенные подмножествами допустимых решений Gi, i = 1, 2, . . . , r. Этот процесс называется ветвлением. Ветвление – это рекурсивный процесс, т.е. каждая подзадача Gi в свою очередь является базисом для другого ветвления. В процессе ветвления образуется дерево поиска оптимального решения. При этом задача G называется корнем, а подзадачи Gi – ветками или потомками;

• Верхняя оценка (граница). Верхней оценкой для  позадачи Gi называется значение U Bi ≥ min (x∈Gi) f(x). Верхняя оценка используется в алгоритме, чтобы предварительно оценить перспективность той или иной подзадачи, т.е. оценить возможность того, что подзадача содержит оптимальное решение исходной задачи;

• Нижняя оценка (граница). Нижней оценкой для позадачи Gi называется значение LBi ≤ min (x∈Gi) f(x). В процессе работы алгоритма Ветвей и Границ последовательно строится несколько допустимых решений. В памяти компьютера мы храним лучшее из построенных допустимых решений (лучшее, с точки зрения целевой функции).  Этому лучшему решению соответствует значение целевой функции, которые мы называем текущим РЕКОРДом. Пусть в процессе работы алгоритма для некоторой подзадачи Gi мы вычислили нижнюю оцену LBi. Если LBi больше текущего РЕКОРДа, значит подмножество Gi не содержит оптимальное решение исходной задачи, а следовательно, не имеет смысла рассматривать подмножество Gi в дальнейшем. Таким образом ветку, соответствующую подмножеству Gi, в дереве поиска можно отсечь. 
 
 
 

3. АЛГОРИТМ РАЗМЕЩЕНИЯ МНОГОУГОЛЬНИКОВ МЕТОДА СЛУЧАЙНОГО ПОИСКА

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

При реализации алгоритма существенным является вопрос: в каком порядке рассматривать “висячие” ветви в дереве поиска? Обычно для продолжения ветвления выбирается подзадача с наименьшей нижней оценкой (или верхней оценкой U Bi) или подзадача с наименьшим значением |Gi|. Как правило, трудоемкость алгоритма ветвей и границ растет экспоненциально с ростом размерности задачи.

Алгоритм Ветвей и Границ для ЗАДАЧИ О РАНЦЕ

Способ ветвления  зададим следующим образом. Множество  G разбивается на два подмножества G0 и G1. В подмножестве G0 находятся все решения, соответствующие x1 = 0, то есть первый предмет в рюкзак не кладется, а в подмножестве G1 решения, соответствующие x1 = 1. Аналогичным образом разбиваются на подмножества G0 и G1, исходя из двух возможных значений x2 = 0 или x2 = 1 и т.д.

Каждой подзадаче  G` в этом дереве поиска соответствует ситуация, когда значения некоторых переменных x1, x2, . . . , xj−1 уже фиксированы. Перед очередным ветвлением, т.е. перед выбором значения для переменной xj необходимо проверить, “помещается” ли предмет j в рюкзак. Если сумма (j−1 k=1) wkxk +wj > C, тогда для этой ветки (подзадачи) фиксируется xj = 0, и работа продолжается только по ветке G0 = G`.

Теперь опишем алгоритм вычисления верхней оценки для некоторой подзадачи, где значения переменных x1, x2, . . . , xj−1 уже фиксированы. В качестве нижней оценки мы будем рассматривать сумму оптимального решения релаксированной (упрощенной) ЗАДАЧИ О РАНЦЕ и значения сумма (j−1 k=1) pk xk. В этой упрощенной задаче 0 ≤ xi ≤ 1, i = 1, 2, . . . , n, т.е. xi может принимать любое значение из интервала [0, 1]. Стоит отметить, что все известные алгоритмы Ветвей и Границ для ЗАДАЧИ О РАНЦЕ имеют экспоненциальную трудоемкость.

Простейший  алгоритм:

Шаг 1. В список подзадач помещается исходная задача. Рекорд полагается равным 0.

Шаг 2. Если список подзадач пуст,  то алгоритм завершается.  В противном случае

выбирается подзадача P из списка подзадач. Подзадача P удаляется  из списка.

Шаг 3. Проверяется, выполнены ли для выбранной подзадачи P условия отсева.

Правила отсева:

1. суммарный  вес предметов, положенных в  ранец, превосходит ограничение; 

2. вес оставшихся  предметов не больше ограничения; 

3. решение оценочной  задачи линейной релаксации не  больше чем рекорд.

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

Шаг 4. Выбранная  подзадача подвергается декомпозиции.  Для этого выбирается переменная b x , называемая переменной ветвления. Подзадача P разбивается на  две подзадачи P0 и P1,  получаемые присваиванием переменной b x значений 0 и 1 соответственно.