【doc】0—1整数规划的枚举算法
0—1整数规划的枚举算法
Ij
1992年第3期计算机应用研究?33? 33.
O一1整数规划的枚举算法
武汉数字
工程
路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理
研究所
华中理工大学
整数规划是数学规划的重要方面之一,许多重 要的组合数学问题实质上都是从属于它,然而目前 求解还存在许多困难,基本上是采用穷举法.0—1 整数规划是整数规划中最简单的一种,即变量只取 0和1两种的整数规划问题.本文只限于讨论0—1 整数规划的一个特例,它是装裁问题整数规划模型 [1]的一般形式.
目标函数.ma】'?cIxI(1)I-l 约柬条件.
fl(X
f(x
x)?0
??
(2)
)90
】【-?{0,1)(i---1…n)(3)
其中,n是整数变量的数量.m是约束条件的数 量.C-(i-----1…n)是非负常系数tfJ(j=卜"m)是计划变 量X-(i…1?n)的函数,它可能是非线性的.
1,分枝定界法图1是深度为3的满二叉 树.
图1深度为3的满二叉树
如果一个深度为(n+1)的满二叉树按上述方法 顺序排列,并对任一节点i存在.
(1)当i----1时,i是根,
(2)当i?时,如果i是偶数,该节点存贮的数据 是0,否则存贮的数据是1.
那么,从根节点到叶子的一条路径(以下简称路 径)是n个0—1整数的组合,因而0—1整数规划的 完全枚举可等价于满二叉树的遗历.
设路径的节点依次为0,1,…,n,节点i对应于 二叉树的节点la(i),并将路径节点i存贮的数据赋 (430074)
(430074)
}
给x,令从路径节点i到i2(i<)的收益为t l2
k(il,i2)=CIXI
I.lI+1
首先定义让h.(i)
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示过二叉树节点la(i)的所 有路径中满足的约束条件(2)的最大收益k(i,n),g.
(i=k(0,i).那么,过节点l丑(i)所能够获得的最大 收益f.(i)可表示成.
f.(i)----g.?(i)+h.(i) 笔者希望估价函数是f是f.的一个估计,此估 计由下式给出.f(i)---s(D+h(i) 式中,g是g.的估计Ih是h的估计.
对于过节点la(i)的路径来说,g.(i)是确定的, -nn
即g-(i)一?ch?(i):?cjxJ??cj,由此可
J-lj--l十1J-I十l
以得到h'的一个上确界.h(i)一厶CJ.由此可以得 到f.的一个上确界f=g+h,其中,S(D----'g'(i).
设遍历到二叉树节点la(i)时,最优目标值为 otirna1.那么,如果op断lal?f,更好的目标值不可能 在通过二叉树节点la(i)的路径中产生,因而可以? 去以la(i)为根节点的子二叉树.分枝定界法的基本 思想正源于此.
假设自顶向下搜索时,人为地规定路径的节点 对应的变量依次为】(-,】(-一-,…,x-,则分枝定界算 法如图2(a)所示.程序用TurboPs~fl语言写成. 2,隐枚拳法穷举法是对如图1的树进行自 上而下,从左向右的搜索过程.隐枚举法只是在这过 程中采用了"碰壁回头的策略,从而设法从此剪去 尽可能多的树枝,枚举的量尽可能的少. "碰壁回头策略的基本思想是.由顶向下搜索 时,如果某个节点的值取0或1时,约束条件得不到 满足,那么,通过该节点的任一路径均不能使约束条 件得到满足,从而可以?去以该节点为根节点的二 叉树.譬如,如果某个)(I=1时,机床刀库容量的约 束条件得不到满足,那么继续沿着该节点向下搜索 就失去了意义.设搜索到节点x】时,某个约束条件 得不到满足,则O一1问题的隐枚算法如图2(b)所 示.将分枝定界法和隐枚举法结合起来,就形成了 (下转44页)
,????????,,??????L
?
ll?计算机应用研究1992年第3期 (上接33页)'
分枝定界——隐枚举算法.详细描述略. fl=0
foril一1tondo
ifxEi]=lthen
fl=t+cEi]
foril=ltondo
ifxD]=0
thenbegin
fl=t+cEi]
iff>optimalthen begin
xEi]t=1I
gotol0I
{gotoexamineconstraints)
endI
end
else
x[i]l=0I
(a)分枝定界法
f0ril—ltondo
if<cEil=O)and(j>j)
thenbegin
x[i]l=lI
gotol0I
{gotoexamineconstraints)
end
x[-i]l=0I
(c)隐枚举算法
图2O-1问题的枚举算法
3,算法的比较无疑,在枚举算法中,完全枚 举法最简单,然而却是最不实用的.因为完全枚举法 需要花费变量数量的指数次数遍历满二叉树,所需 时问过长..
分枝定界法和隐枚举法各走极端t当约束条件 较松时,分枝定界法极有利于删去满二叉树的部分 枝叶,从而减少遍历二叉树的时问,提高速度,反之, 当约束条件较紧时,隐枚举法有利于删去满二叉树 部分枝叶.然而,在最坏的情况下,分枝定界法和隐 枚举法所需的开销和完全枚举法的相同. 分枝定界——隐枚举算法将分枝定界法和隐枚 举结合起来,充分利用了两个算法的优点,使得无论 在约束条件是紧还是松的时候,都能删去满二叉树 的部分枝叶,从而减少了遍历二叉树所需时问,提高 了速度.
'
上述算法的优越性已在文献[1]的工作中得到 验证.
参考文献
1.陶友传,李培根,段正澄等.柔性零件装载 问题的建模及算法,'组合机床与自动化加工技 术),1991,(3).
浙公网安备 33021202002483