УДК 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 соответственно.

Построенные подзадачи P0 и P1 помещаются в список подзадач и осуществляется переход к шагу 2.

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

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

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

      Входными  данными является стоимость и прибыль каждого из наименований рюкзака, которые считываются из файла, или вводятся непосредственно при работе программы. (Рис. 4.1). 

                  

                  Рисунок 4.1 Формат файла  входных данных 
 

2. Работа программы:

При запуске  открывается окно с двумя вкладками:

Первая с  описанием программного продукта и  реализации метода

                                                     Рис. 4.2 

Вторая с  различными окнами для ввода значений

                              Рис. 4.3 
 
 

Значения пунктов, максимальной цены, цены каждой вещи и  прибыли можно ввести самостоятельно

            Рис. 4.4 

 

        Рис. 4.5 

А можно рандомно случайными числами

            Рис. 4.6 
 

Выбираем наш  алгоритм «Branch and bound» (ветвей и границ) и нажимаем Go 

            Рис. 4.7 

Выходными данными – это оптимальное решение данной задачи:

            Рис. 4.8 

      Рис. 4.9

Также мы можем  вывести путь по которому это оптимальное решение появилось (первые 50 шагов)

                    Рис. 4.10 

Значение мы можем вывести из файла и сохранить  в файл

      Рис. 4.11 
 
 
 
 
 
 
 
 
 
 

И вот полный окончательный результат программы  готов:

                              Рис. 4.12 
 
 
 
 
 
 
 
 
 
 
 
 

ВЫВОДЫ

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

      Разработана и проанализирована математическая модель, а также алгоритм решения задачи. Были проанализированы входные данные и требования задачи.

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

-  В худшем случае работает как  полный перебор.

Плюсы Метода ветвей и границ

-  Возможно значительное сокращение времени работы.

-  Простота реализации.

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

 

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

1. http://www.ipu.rssi.ru/sites/default/files/publications/book.pdf

2. [Minu_M.]_Matematicheskoe_programmirovanie._Teoriy(BookFi.org)

3.Ковалёв М.М. Дискретная оптимизация. Целочисленное программирование (1977) 
 
 
 
 
 
 
 
 
 

     ПРИЛОЖЕНИЕ  А

     (Листинг  программы)

unit U_BranchAndBound; 

interface 

uses

  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

  Menus, StdCtrls, Math, Grids, ComCtrls, ShellAPI; 

const

    CR = #13#10; 

type

  TItem = record

    Cost   : Integer;

    Profit : Integer;

  end;

  TItemArray = array of TItem;

  //PItemArray = ^TItemArray; 

  TBoolArray = array of Boolean;

  //PBoolArray = ^TBoolArray; 

  TBandBForm = class(TForm)

    PageControl1: TPageControl;

    TabSheet1: TTabSheet;

    TabSheet2: TTabSheet;

    Label7: TLabel;

    Label8: TLabel;

    Label9: TLabel;

    Label10: TLabel;

    NodesLabel: TLabel;

    VisitedLabel: TLabel;

    Label11: TLabel;

    Label12: TLabel;

    BestCostLabel: TLabel;

    BestProfitLabel: TLabel;

    SearchtimeLbl: TLabel;

    Label14: TLabel;

    Label3: TLabel;

    Label6: TLabel;

    GroupBox1: TGroupBox;

    Label1: TLabel;

    Label2: TLabel;

    Label4: TLabel;

    Label5: TLabel;

    MinCostText: TEdit;

    MaxCostText: TEdit;

    MaxProfitText: TEdit;

    MinProfitText: TEdit;

    RandomBtn: TButton;

    GroupBox2: TGroupBox;

    OptBranchAndBound: TRadioButton;

    GoBtn: TButton;

    ScrollBox2: TScrollBox;

    SolutionLabel: TLabel;

    ShowStepsBox: TCheckBox;

    Memo1: TMemo;

    ItemsGrid: TStringGrid;

    Memo2: TMemo;

    NumItemsText: TEdit;

    AllowedCostText: TEdit;

    NumItemsUD: TUpDown;

    AllowedCostUD: TUpDown;

    //StaticText1: TStaticText;

    Memo3: TMemo;

    Button1: TButton;

    Button2: TButton;

    OpenDialog1: TOpenDialog;

    SaveDialog1: TSaveDialog;

    procedure FormCreate(Sender: TObject);

    procedure RandomBtnClick(Sender: TObject);

    procedure GoBtnClick(Sender: TObject);

    procedure ShowResults;

    procedure Search(b_and_b : Boolean);

    procedure BranchAndBound(item_num : Integer);

    //procedure ExhaustiveSearch(item_num : Integer);

    procedure NumItemsUDChangingEx(Sender: TObject;

      var AllowChange: Boolean; NewValue: Smallint;

      Direction: TUpDownDirection);

    procedure NumItemsTextChange(Sender: TObject);

    procedure Button1Click(Sender: TObject);

    procedure Button2Click(Sender: TObject); 

    //procedure StaticText1Click(Sender: TObject);

  public

    NumItems         : Integer;

    Items            : TItemArray;

    AllowedCost      : Integer; 

    {Search variables}

    PathsChecked     : Longint;

    UnassignedProfit : Integer;    // Total of unassigned profits.

    BestSolution     : TBoolArray; // True for items in best solution.

    BestCost         : Integer;

    BestProfit       : Integer;

    TestSolution     : TBoolArray; // True for items in test solution.

    TestCost         : Integer;    // Cost of test solution.

    TestProfit       : Integer;    // Profit of test solution.

    startTime:extended;

    procedure resetLabels;

    procedure loaddefaultcase;

  end; 

var

  BandBForm: TBandBForm; 

implementation 

{$R *.DFM} 

var

  {Data for testing }

  (*

  defaultdata:array[1..5,1..2] of integer =

    ((56,8),(12,4),(70,7),(49,7),(37,5));

  *)

  defaultdata:array[1..5,1..2] of integer =

    ((51,1),(11,5),(19,7),(27,7),(47,1)); 

{************* FormCreate **************}

procedure TBandBForm.FormCreate(Sender: TObject);

var i:integer;

begin

  Randomize;

  with Itemsgrid do

  begin

    cells[0,0]:='Item';

    cells[1,0]:='Cost';

    cells[2,0]:='Profit';

    for i:=1 to numitemsUD.position + 1 do cells[0,i]:=inttostr(i);

  end;

  loaddefaultCase;

  opendialog1.initialdir:=extractfilepath(application.exename);

  savedialog1.initialdir:=opendialog1.initialdir;

end; 

{************* LoadDefaultCase *********}

Procedure TBandBForm.LoadDefaultCase;

var  i:integer;

begin

  NumItemsUD.position:=high(defaultdata);

  NumItems := NumItemsUD.position;

  //NumItemsText.text:=inttostr(NumItems);

  AllowedCostUD.position:=100;

  Allowedcost:=allowedCostUD.position;

  itemsgrid.rowcount:=NumItems+1;

  {add one extra entry for dynamic array since existing code starts from 1}

  Setlength(Items, (NumItems+1) * SizeOf(TItem));

  setlength(TestSolution, (NumItems+1) * SizeOf(Boolean));

  setlength(BestSolution, (NumItems+1) * SizeOf(Boolean)); 

  with itemsgrid do

  for i:=1 to NumItems do

  with Items[i] do

  begin

    Cost := defaultdata[i,1];

    Profit := defaultdata[i,2];

    cells[1,i]:=Format('%6d', [Cost]);

    cells[2,i]:=Format('%6d', [Profit]);

  end; 

  ResetLabels;     // Clear the previous solution.

end; 

{************ ResetLabels ********}

Procedure TBandBForm.ResetLabels;

begin

  SolutionLabel.Caption := '0';

  BestCostLabel.Caption := '0';

  BestProfitLabel.Caption := '0';

  VisitedLabel.Caption := '0';

  SearchtimeLbl.Caption:='0.000 seconds';

  NodesLabel.Caption := format('%.0n',[Power(2, NumItems) - 1]);

  memo1.Clear;

  Refresh;

end; 
 

{*********** CmdmakeDataClick ************}

procedure TBandBForm.RandomBtnClick(Sender: TObject);

{Generate some random data.}

var

  min_cost, max_cost, min_profit, max_profit : Integer;

  i, cost_range, profit_range                : Integer;

begin

  min_cost := StrToInt(MinCostText.Text);

  max_cost := StrToInt(MaxCostText.Text);

  min_profit := StrToInt(MinProfitText.Text);

  max_profit := StrToInt(MaxProfitText.Text);