unit Unit2;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, Grids, StdCtrls, Buttons,IdGlobal,Math;
const long=250;
type
  TForm2 = class(TForm)
    StringGrid1: TStringGrid;
    BitBtn1: TBitBtn;
    BitBtn2: TBitBtn;
    BitBtn3: TBitBtn;
    Label1: TLabel;
    procedure BitBtn1Click(Sender: TObject);
    procedure BitBtn3Click(Sender: TObject);
    procedure BitBtn2Click(Sender: TObject);
    procedure FormActivate(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form2: TForm2;
 var
  VarNum,ConNum:integer;
  //定義整形變量，存放變量個數(shù)和約束條件個數(shù)相當(dāng)于n，m
  leixing:String;//存放目標(biāo)函數(shù)類型
  x:array[1..long] of integer;//存放變量的值
  z:real;//存放最優(yōu)目標(biāo)函數(shù)值
  zuiyouzhi:real;//存放最優(yōu)目標(biāo)函數(shù)值
  fangsuo:real;//c存放目標(biāo)函數(shù)的放大，縮小量
  meijucishu:integer;
  biaoshi:array of char;
  a:array[1..long,1..long] of real;//存放系數(shù)矩陣
  b:array[1..long] of real;//存放限定向量
  c:array[1..long] of real;//存放目標(biāo)函數(shù)系數(shù)
  c0:array[1..long] of real;//保留原始目標(biāo)函數(shù)系數(shù)
  paixu:array[1..long] of Integer;
  fuxishu:set of 1..250;//自定義集合
  opt:array[1..long] of integer;//存放操作符
  bins:string;//以字符方式存放整數(shù)轉(zhuǎn)化而來的二進(jìn)制數(shù)
implementation

{$R *.dfm}
uses unit1;

procedure bianhuanxishu;
var i,j:integer;
    k:Integer;
    yipai:set of 1..250;
    max:real;
    maxj:Integer;
begin
if leixing='Min' then
  for j:=1 to VarNum do
    c[j]:=-c[j];
    //為了便于求解將所有問題都轉(zhuǎn)化為最大化問題
fangsuo:=0;
fuxishu:=[];
for j:=1 to VarNum do
  if c[j]<0 then
    begin
      fuxishu:=fuxishu+[j];
      fangsuo:=fangsuo+c[j];//更新目標(biāo)函數(shù)值
      c[j]:=-c[j];//負(fù)的系數(shù)變?yōu)檎?      for i:=1 to ConNum  do
        begin
          b[i]:=b[i]-a[i,j];//更新限定向量
          a[i,j]:=-a[i,j];//更新系數(shù)矩陣
        end;
    end;
k:=0;
yipai:=[];

while k<varnum do
  begin
    k:=k+1;
    max:=-1;
    for j:=1 to VarNum do
      if (c[j]>max) and not (j in yipai) then
        begin
         max:=c[j];
         maxj:=j;
        end;
      yipai:=yipai+[maxj];
      paixu[k]:=maxj;
  end;
end;
{----------將目標(biāo)函數(shù)中系數(shù)為負(fù)的項全部用1-x代替，并作以標(biāo)識-------}

function  lookbest:boolean;//函數(shù)值返回是否有可行解
var   i,j,k:Integer;
      temp:Boolean;
      hangzhi:real;
      temp_z:real;
begin
Result:=False;
zuiyouzhi:=0;
temp_z:=0;
for k:=meijucishu-1 downto 0 do
  begin
    bins:=IntToBin(k);
    for j:= 1 to VarNum do
      x[paixu[j]]:=StrToInt(copy(bins,32-VarNum+j,1));
    temp_z:=0;
    for j:=1 to VarNum do
      begin
       if j in fuxishu then
         temp_z:=temp_z+(1-x[j])*c0[j]
       else
       temp_z:=temp_z+x[j]*c0[j];
      end;
    if temp_z>zuiyouzhi then
      begin
        temp:=True;
        for i:=1 to ConNum do
          begin
            hangzhi:=0;
            for j:=1 to VarNum do
              hangzhi:=hangzhi+a[i,j]*x[j];
            if (Sign(hangzhi-b[i])<>opt[i]) and (hangzhi<>b[i]) then
              begin
               temp:=False;
               Break;
             end;
         end;
        if temp then
          begin
           Result:=true;
           zuiyouzhi:=temp_z;
           z:=0;
           for j:=1 to VarNum do
            z:=z+x[j]*c[j];//通過全局變量z傳遞最優(yōu)值，注意這里的最優(yōu)值不包含放縮值
         end;
      end;
  end;
end;
{----------算法的核心尋找最優(yōu)值--------------------}

procedure TForm2.BitBtn1Click(Sender: TObject);
var i,j,k:Integer;
    num:Integer;//最優(yōu)解的個數(shù)
    zl:real;
    hangzhi:real;
    temp:Boolean;
begin
bianhuanxishu;//調(diào)整目標(biāo)函數(shù)系數(shù)全部為非負(fù)
meijucishu:=1;
for j:=1 to VarNum do
  meijucishu:=meijucishu*2;//計算枚舉次數(shù)2的n次方次，n代表變量個數(shù)
if lookbest then
  begin
    num:=0;//初值為0
    for k:=meijucishu-1 downto 0 do
      begin
         zl:=0;
         bins:=IntToBin(k);
         for j:= 1 to VarNum do
           begin
             x[j]:=StrToInt(copy(bins,32-VarNum+j,1));
             zl:=zl+x[j]*c[j];
           end;
         if abs(zl-z)<0.000001 then //檢驗?zāi)繕?biāo)函數(shù)值是否是最優(yōu)值
           begin
             temp:=true;
             for i:=1 to ConNum do//檢驗是否滿足約束條件
               begin
               hangzhi:=0;
               for j:=1 to VarNum do
                 hangzhi:=hangzhi+a[i,j]*x[j];
               if (sign(hangzhi-b[i])<>opt[i]) and (hangzhi<>b[i]) then
                 begin
                  temp:=False;
                  Break;
                 end;
               end; //檢驗是否滿足約束條件
             if  temp then
             begin
              //不能滿足所有的約束條件，則跳出循環(huán)，進(jìn)行下一個枚舉的判斷
             num:=num+1;
             StringGrid1.RowCount:=num+1;
             StringGrid1.Cells[0,StringGrid1.RowCount-1]:='最優(yōu)解 '+IntToStr(num);
              //動態(tài)調(diào)整文本框的行數(shù)，來顯示所有最優(yōu)解
             for  j:=1 to VarNum do
               begin
                 if j in fuxishu then
                    x[j]:=1-x[j];
                 StringGrid1.Cells[j,StringGrid1.RowCount-1]:=FloatToStr(x[j]);                      //顯示最優(yōu)解
               end;
             end;
           end;// 對應(yīng)if abs(zl-z)<0.000001 then
       end;//對應(yīng)for k:=qidian to zhongdian do

    if leixing='Min' then
      zuiyouzhi:=-zuiyouzhi;//求最小化問題時目標(biāo)函數(shù)為相反數(shù)
    Label1.Caption:='該0－1規(guī)劃的'+leixing+'值為:';
    Label1.Caption:=Label1.Caption+FormatFloat('0.######',zuiyouzhi);
    Label1.Caption:=Label1.Caption+#13+'共有 '+IntToStr(num)+' 個最優(yōu)解如下表所示';
    StringGrid1.SetFocus;
  end
else
  begin
     Label1.Caption:='該0－1規(guī)劃無可行解';
    // FormActivate(Sender);
  end;
end;


procedure TForm2.BitBtn3Click(Sender: TObject);
begin
Form2.Close;
Form1.Close;
end;

procedure TForm2.BitBtn2Click(Sender: TObject);
begin
Form1.Show;
end;

procedure TForm2.FormActivate(Sender: TObject);
var i,j:Integer;
begin
Label1.Caption:='隱枚舉法求解0－1整形規(guī)劃';
StringGrid1.RowCount:=5;
StringGrid1.ColCount:=VarNum+1;
for j:=1 to VarNum do
  StringGrid1.Cells[j,0]:='x'+IntToStr(j);
//設(shè)置文本框
with StringGrid1 do
  begin
    for i:=1 to RowCount-1 do
      for j:=1 to ColCount-1 do
        cells[j,i]:='';
  end;
StringGrid1.SetFocus;
end;

end.