09-1_0-1规划的隐枚举法

《09-1_0-1规划的隐枚举法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2013-2014（2）专业课程实践论文题目：0-1规划的隐枚举法一、算法理论0—1规划在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整数规划都与0—1规划等价，用0—1规划方法还可以把多种非线性规划问题表示成整数规划问题，所以不少人致力于这个方向的研究。求解0—1规划的常用方法是分枝定界法，对各种特殊问题还有一些特殊方法。线性模型中，当变量的取值只能是“0”或“1”时，称之为“0-1规划问题”。有种极其简单的解法，就是将变量

2、取值为0或1的所有组合列出，然后分别代入目标函数，选出其中能使目标函数最优化的组合，即为最优解。但是真的这样会做很多无用功，浪费大量资源，所以，需要改进方法。本文主要介绍隐枚举法的应用原理，意在剖析其“隐”在何处。从而帮助读者更好地应用这种方法。和线性规划问题一样，首先需要将模型标准化。标准化对0-1规划问题提出四点要求：1.目标函数为最小优化2.目标函数中变量的系数都为正3.在目标函数中，变量按系数值从小到大排列，则约束函数中，变量的排列次序也做相应改变。4.所有变量均为0或10-1线性规划的基本形式

3、是二、算法框图三、算法程序function[intx,intf]=ZeroOneprog(c,A,b,x0)%目标函数系数向量，c%不等式约束矩阵，A%不等式约束右端向量，b%初始整数可行解，x0%目标函数取最小值时的自变量值，intx%目标函数的最小值，intfsz=size(A);ifsz(2)<3[intx,intf]=Allprog(c,A,b);%穷举法else[intx,intf]=Implicitprog(c,A,b,x0);%隐枚举法endfunction[intx,intf]=Allp

4、rog(c,A,b)sz_A=size(A);rw=sz_A(1);col=sz_A(2);minf=inf;fori=0:(2^(col)-1)%枚举空间x1=myDec2Bin(i,col);%十进制转化为二进制ifA*x1>=b%是否满足约束条件f_tmp=c*x1;iff_tmp

5、)%隐枚举法sz_A=size(A);rw=sz_A(1);col=sz_A(2);minf=c*x0;A=[A;-c];b=[b;-minf];%增加了一个限制分量fori=0:(2^(col)-1)x1=myDec2Bin(i,col);ifA*x1>=bf_tmp=c*x1;iff_tmp

6、iony=myDec2Bin(x,n)%十进制转化为二进制str=dec2bin(x,n);forj=1:ny(j)=str2num(str(j));endy=transpose(y);四、算法实现例1．求解下面0-1规划解:在MATLAB命令框在输入下列命令：>>c=[12311];>>A=[23547;11422];>>b=[8;5];>>x0=[1;1;1;1;1];>>[intx,intf]=ZeroOneprog(c,A,b,x0)所得结果如下：例2．求下面0-1线性规划解：在MATLAB命令

7、框在输入下列命令：>>c=[-3,2,-5];>>A=[-1,-2,1;-1,-4,-1;-1,-1,0;-4,0,-1];>>b=[-2;-4;-3;-6];>>x0=[1;0;0];>>[intx,intf]=ZeroOneprog(c,A,b,x0)例3．求解下面0-1规划解:在MATLAB命令框在输入下列命令：>>c=[3,7,-1,1];A=[2,-1,1,-1;1,-1,6,4;5,3,0,1];b=[1;8;5];>>x0=[1;1;1;1];>>[intx,intf]=ZeroOnepr

8、og(c,A,b,x0)例4．求解下面0-1规划解:在MATLAB命令框在输入下列命令：>>c=[-6,-2,-3];A=[-1,-2,-1;3,-5,1;-2,-1,-1];b=[-3;2;-4];x0=[1;0;0];[intx,intf]=ZeroOneprog(c,A,b,x0)