Построенные подзадачи 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);