0-1规划的隐枚举法
- 格式：doc
- 大小：96.00 KB
- 文档页数：10
2013—2014（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线性规划的基本形式是
1minnjjjZcx 011,2,,..1,2,,jijjjxjmstaxbin或
二、算法框图
三、算法程序
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规划
105224287453232min54321543215432154321或,x,x,x,xxxxxxxxxxxx,s.t.xxxxxxf
解:在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线性规划
1231231231213123max3252244..346,,01zxxxxxxxxxstxxxxxxx为或
解:在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规划
123412341234124min3721648..53501,1,2,3,4jzxxxxxxxxxxxxstxxxxj或
解：在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规划
123123123123max62323352..2401,1,2,3jzxxxxxxxxxstxxxxj或
解：在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）
