- （2）专业课程实践论文
题目：0-1计划隐枚举法
一、算法理论
0—1计划在整数计划中占相关键地位，首先因为很多实际问题，比如指派问题、选地问题、送货问题全部可归结为这类计划，其次任何 有界变量整数计划全部和0—1计划等价，用0—1计划方法还能够把多个 非线性计划问题表示成整数计划问题，所以不少人致力于这个方向研究。求解0—1计划常见方法是分枝定界法，对多种特殊问题还有部分特殊方法。
线性模型中，当变量取值只能是“0”或“1”时，称之为“0-1计划问题”。有种极其简单解法，就是将变量取值为0或1全部组合列出，然后分别代入目标函数，选出其中能使目标函数最优化组合，即为最优解。不过真这么会做很多无用功，浪费大量资源，所以，需要改善方法。本文关键介绍隐枚举法应用原理，意在剖析其“隐”在何处。从而帮助读者愈加好地应用这种方法。
和线性计划问题一样，首先需要将模型标准化。标准化对0-1计划问题提出四点要求：
1.目标函数为最小优化
2.目标函数中变量系数全部为正
3.在目标函数中，变量按系数值从小到大排列，则约束函数中，变量排列次序也做对应改变。
4.全部变量均为0或1
0-1线性计划基础形式是
二、算法框图
三、算法程序
function [intx,intf] = ZeroOneprog(c,A,b,x0)
%目标函数系数向量，c
%不等式约束矩阵，A
%不等式约束右端向量，b
%初始整数可行解，x0
%目标函数取最小值时自变量值，intx
%目标函数最小值，intf
sz = size(A);
if sz(2) < 3
[intx,intf] = Allprog(c,A,b); %穷举法
else
[intx,intf] = Implicitprog(c,A,b,x0); %隐枚举法
end
function [intx,intf] = Allprog(c,A,b)
sz_A = size(A);
rw = sz_A(1);
col = sz_A(2);
minf = inf;
for i=0:(2^(col)-1) %枚举空间
x1 = myDec2Bin(i,col); %十进制转化为二进制
if A*x1 >= b %是否满足约束条件
f_tmp = c*x1;
if f_tmp < minf
minf = f_tmp;
intx = x1;
intf = minf;
else
continue;
end
else
continue;
end
end
function [intx,intf] = Implicitprog(c,A,b,x0)%隐枚举法
sz_A = size(A);
rw = sz_A(1);
col = sz_A(2);
minf = c*x0;
A = [A;-c];
b = [b;-minf]; %增加了一个限制分量
for i=0:(2^(col)-1)
x1 = myDec2Bin(i,col);
if A*x1 >= b
f_tmp = c*x1;
if f_tmp < minf
minf = f_tmp;
b(rw+1,1) = -minf; %隐枚举法和穷举法区分在于此句
intx = x1;
intf = minf;
else
continue;
end
else
continue;
end
end
function y = myDec2Bin(x,n) %十进制转化为二进制
str = dec2bin(x,n);
for j=1:n
y(j) = str2num(str(j));
end
y = transpose(y);
四、算法实现
例1．求解下面0-1计划
解:在MATLAB命令框在输入下列命令：
>> c=[1 2 3 1 1];
>> A=[2 3 5 4 7;1 1 4 2 2];
>> b=[8;5];
>> x0=[1;1;1;1;1];
>> [intx,intf]=ZeroOneprog(c,A,b,x0)
所得结果以下：
例2．求下面0-1线性计划
解：在MATLAB命令框在输入下列命令：
>> 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]=ZeroOneprog(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)