0-1规划的隐枚举法
-
2013-2014
（
2
）
专业课程实践论文
题目：
0-1
规划的隐枚举法
一、算法理论
0
—
1
规划在整数规划中占有重要地位，一方面因为许多实际
问题，例如指派
问题、
选地问题、
送货
问题都可归结为此类规划，
另一方面任何有界变量的整
数规划都
与
0
—
1
规划
等价，
用
0
—
1
规划方法还可以把多种非线性规划问题表
示成整数规划问题，
所以不少人致力于这个方向的研究。求解
0
—
< br>1
规划的常
用方法是分枝定界法，对各种特殊问题还有一
些特殊方法。
线性模型中，
当变量的
取值只能是“0”或“1”时，
称之为“0
-1
规划问题”。
有种极其简单的解法，
就是将变量取值为
0
或
1
的所有
组合列出，
然后分别代
入目标函数，
选
出其中能使目标函数最优化的组合，
即为最优解。
但是真的这<
/p>
样会做很多无用功，浪费大量资源，所以，需要改进方法。本文主要介绍隐枚
举法的应用原理，
意在剖析其“隐”在何处。
从而帮
助读者更好地应用这种方
法。
和线性
规划问题一样，
首先需要将模型标准化。
标准化对
0-1
规划问题提出四
点要求：
1.
目标函数为最小优化
2.
目标函数中变量的系数都为正
<
/p>
3.
在目标函数中，
变量按系数值从小到
大排列，
则约束函数中，
变量的排列次
序也做相应改变。
4.
所有变量均为
0
或
1
0-1
线性规划的基本形式是
n
min
Z
c
j
x
j
j
1
x
j
0
或
1
< br>j
1,
2,
< br>
,
m
s
< br>.
t
.
a
i
j
x
j
b<
/p>
j
i
1,
2,
,
n<
/p>
二、算法框图
三、算法程序
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