规划的隐枚举法

2023-2023(2)专业课程实践论文

题目：0・1规划的隐枚举法

一、算法理论

0—1规划在整数规划中占有重要地位，一方面由于许多实际问题，例如指派

问题、选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整

数规划都与0—1规划等价，用0—1规划方法还可以把多种非线性规划问题表

达成整数规划问题，所以不少人致力于这个方向的研究。求解0—1规划的常

用方法是分枝定界法，对各种特殊问题尚有一些特殊方法。

线性模型中，当变量的取值只能是“0”或“I”时，称之为"0-1规划问题”。

有种极其简朴的解法，就是将变量取值为0或1的所有组合列出，然后分别代

入目的函数，选出其中能使目的函数最优化的组合，即为最优解。但是真的这

样会做很多无用功，浪费大量资源，所以，需要改善方法。本文重要介绍隐枚

举法的应用原理，旨在剖析其“隐”在何处。从而帮助读者更好地应用这种方

法。

和线性规划问题同样，一方面需要将模型标准化。标准化对0-1规划问题提出

四点规定：

1.目的函数为最小优化

2.目的函数中变量的系数都为正

3.在目的函数中，变量按系数值从小到大排列：则约束函数中，变量的排列

顺序也做相应改变。

4.所有变量均为0或1

0-1线性规划的基本形式是

minZ=ZK

;=i

Xj=0或1j=m

2^aijxj<bjZ=1,2,---,H

二、算法框图

三、算法程序

function[intx,intf]=ZeroOneprog(czA,bzxO)

2目的函数系数向量，c

当不等式约束矩阵，A

%不等式约束右端向量，b

学初始整数可行解，xO

%目的函数取最小值时的自变量值，intx

%目的函数的最小值，intf

sz=size(A);

ifsz(2)<3

[intx,intf]=Allprog(c,A,b);%穷举法

else

[intx,intf]=Implicitprog(c,AzxO);%隐枚举法

end

function[intx,intf]=Allprog(c,A,b)

sz_A=size(A);

rw=sz_A(1);

colszA(2)；

ninf=inf;

fori=0:(2A(col)-1)%枚举空间

xl=myDec2Bin(i,col);%十进制转化为二进制

ifA*xl>=b超是否满足约束条件

f_tmp=c*xl;

iff_tmp<minf

minf=f_tmp;

intx=xl;

intf=minf;

else

continue;

end

else

continue;

end

end

function[intx,intf]=工mplicitprog(c,A,b,xO)也隐枚举法

szA=size(A);

rw=sz_A(1);

col=sz_A(2);

ninf=c*xO;

A=[A;-c];

b=[b;-minf];%增长了一个限制分量

fori=0:(2人(col)-1)

xl=myDec2Bin(izcol);

ifA*xl>=b

f_tmp=c*xl;

iff_tmp<minf

minf=f_tmp;

b(rw+l,l)=-minf;%隐枚举法与穷举法的区别在于此句

intx=xl;

intf=minf;

else

continue;

end

else

continue;

end

end

functiony=myDec2Bin(x,n)》十进制转化为二进制

str=dec2bin(x,n);

forj=1:ri

y(j)=str2num(str(j));

end

y=transpose(y);

四、算法实现

例1.求解下面0”规划

2X(+3X2+5X3+4X4+lx5>8

min/(x)=%+2x2+3x3+x4+x5fs.tA%+2x2+4x3+2x4+2x5>5

$=oMi

解:在MATLAB命令框在输入下列命令:

»c=[l2311];

»A=[23547;11422];

»b=[8;5];

»[intx,intf]=ZeroOneprog(c,A,b,xO)

所得结果如下：

»c=[l,2,3,1,1]：

»A=[2,3,5,4,7:1,1,4,2,2];

»b=[8;5]

b=

8

5

»xO=[l：l：l：l：l]：

»[intx,intf]=ZeroOneprog(c,A,b,xO)

intx=

1

0

0

1

1

intf=

3

例2.求下面线性规划

maxz=3xx-2x2+5.

x,+2X2-X3<2

%+4X2+x3<4

s.t.<x,+x2<3

4%+£V6

内,工2，欠3为0或1

解：在MATLAB命令框在输入下列命令：

>>c=[-3,2,-5];

»A=[-1,-2,11,-4,-111,0;-4,0,-1];

»b=[-2;-4;-3;-6];

»xO=[l;O;O];

»[intx,intf]=ZeroOneprog(c,A,b,xO)

»c=[-3,2,-5]:

»A=[-l,-2,1;-1,-4,-1：-1,-1,0;-4,0,-1];

»b=[-2：-4：-3;-6]：

»x0=[l;0;0]：

»[intx,intf]=ZeroOneprog(c,A,b,xO)

intx=

1

0

1

intf=

-8

例3.求解下面0・1规划

minz=3%+7x2一刍十%

2x}-x2+-x4>1

x(-x24-6X3+4X4>8

5%1+3x2+x4>5

x.=0^1J=l,2,3,4

解:在MATLAB命令框在输入下列命令:

»c-[3,7,-l,l];

b=[l；8;5];

»xO=[l;l;l;l];

»[intx,intf]=ZeroOneprog(c,A,b,xO)

»c=[3,7,-1,1]：

A=[2,-l,1,-1;1,-1,6,4;5,3,0,1];

b=[l：8;5]:

»x0=[l;l;l;l]:

»[intx,intf]=ZeroOneprog(c,A,b,xO)

intx=

1

0

1

1

intf=

3

例4.求解下面0・1规划

maxz=6Xj4-2x2+3x3

%+2X2+x3<3

33-5x2+x3>2

2xt+x2+x3<4

X.=0^1,j=1,2,3

解:在MATLAB命令框在输入下列命令:

>>c=[-6,-2,-3];

b二卜3;2;-4];

x()=[l;();()];

[intx,intf]=Z