（系统分析与集成专业论文）多约束非线性背包问题的拉格朗日对偶方法.pdf

2 0 0 5 年上海大学硕士学位论文 摘要 多约束非线性背包问题是一类特殊而重要的整数规划问题，它可以定 义为在有限整数集上极大化一个可分离非线性函数的多约束( 可分离) 最优 化问题由于这类问题在资源分配，工业生产及计算机网络的最优化模型 中有着十分广泛的应用，因此研究非线性背包问题的算法具有十分重要的 现实意义本文所讨论的多约束非线性背包问题可以描述如下： n ! t l a x ( x ) = ：，j ( ) j = l n s t 仇( z ) = ，g i j ( x j ) s 晚，i = 1 ，m ， j = l x x = l j q 茎u j ，x j 整数，j = 1 ，n ) ， 其中乃，为定义在哟 上的单调递增函数，b 和啦为整数，分别表示 整数变量z f 的下界和上界，b ：是常数 本文根据背包问题的结构特点，提出了拉格朗日对偶和区域分割方法， 并用此算法求解了多约束非线性背包问题利用外逼近方法求解对偶问题 以得到上界，为了消除对偶间隙以保证算法的收敛性，我们利用区域割技 术丢掉某些整数箱子，并把剩下的区域划分为一些整数箱子的并集，以便 使拉格朗日松弛问题能有效求解，并使算法在有限步内收敛到最优解算 法的特色和创新之处是把外逼近方法用于求解对偶问题并与区域分割有效 结合起来解决多约束非线性背包问题本文还将传统的次梯度方法运用到 算法中，并将得到的数值结果与外逼近方法进行了比较，我们的数值结果 揭示了外逼近方法在求解多约束非线性背包问题的对偶问题时明显优于次 梯度方法此外，我们还对来自实际应用中的多约束非线性背包问题进行 了大量的数值试验 本文总共分为五章，第一章简单地介绍了非线性背包问题的模型，以 及它与整数规划问题算法的研究现状和研究进展第二章简单介绍了求解 非线性背包问题( 单约束) 的现有的算法，以及求解多约束非线性背包问题 的研究进展，如：分枝定界算法，约束替代松弛算法以及动态规划与分枝 定界的混合算法第三章是我们的主要结果，提出了一种新的拉格朗日对 偶和区域割算法求解多约束非线性背包问题第四章是我们的数值试验部 2 0 0 5 年上海大学硕士学位论文 分，主要介绍一些数值试验的结果另外，我们还把拉格朗日和区域割算法 中使用外逼近方法求上界的数值结果与传统的次梯度方法进行了比较，并 将此算法与基于分枝定界和动态规划的混合算法进行了比较第五章是结 论部分，是对本文结果的总结以及对未来研究的展望 关键词：非线性整数规划，非线性背包问题，拉格朗日对偶，区域割，外 逼近方法，次梯度方法，约束替代松弛算法，分枝定界法，动态规划和分枝 定界混合算法 2 0 0 5 年上海大学硕士学位论文 i i i a b s t r a c t m u l t i d i m e n s i o n a ln o n l i n e a rk n a p s a c kp r o b l e mi sa ni m p o r t a n tc l a s so fn o n 1 i n e a ri n t e g e rp r o g r a m m i n gp r o b l e m sw h i c hc a nb ed e f i n e da st h em a x i m i z a t i o n o fas e p a r a b l ef u n c t i o ns u b j e c tt om u l t i p l es e p a r a b l ec o n s t r a i n t sa n db o u n d e d i n t e g e rv a r i a b l e s b e c a u s eo fi t sw i d ea p p l i c a t i o n si nr e s o u r c ea i l o c a t i o n ，i n d u s t r i a lp l a n n i n ga n dc o m p u t e rn e t w o r k ，i ti so fg r e a ti n t e r e s tt os t u d yt h em u l t i - d i m e n s i o n a ln o n l i n e a rk n a p s a c kp r o b l e m s am u l t i d i m e n s i o n a ln o n l i n e a rk n a p s a c kp r o b l e mc a nb ee x p r e s s e da sf o l l o w s ： n m a xm ) = f j ( x j ) ，= 1 n s t g g x ) = e ( 唧) 5b l ，i = 1 ，一，m ， ，= 1 z x = 0 茁j u j ，x ji si n t e g e r ，j = 1 ，n ) ， w h e r e 如a n dg i ja r ec o n t i n u o u sn o n d e c r e a s i n gf u n c t i o n so n z j ， ，l ja n du ja r e t h el o w e rb o u n da n dt h eu p p e rb o u n do ft h ea r g u m e n tx jo nt h ei n t e g e rv a r i a b l e s r e s p e c t i v e l y ，b ii sac o n s t a n t ，f o ri = 1 ，m t h em a i np u r p o s eo ft h i st h e s i si st op r o p o s ean e w c o v e r g e n tl a g r a n g i a n a n dd o m a i nc u tm e t h o df o rs o l v i n gt h em u l t i - d i m e n s i o n a ln o n l i n e a rk n a p s a c k p r o b l e m s o u t e ra p p r o x i m a t i o nm e t h o di su s e dt os o l v et h ed u a lp r o b l e m i n o r d e rt oe l i m i n a t et h ed u a l i t yg a pa n dt h u st og u a r a n t e et h ec o n v e r g e n c eo ft h e a l g o r i t h m ) w eu s ed o m a i nc u tt e c h n i q u et or e m o v ec e r t a i ni n t e g e rb o x e sa n d p a r t i t i o nt h er e v i s e dd o m a i nt oau n i o no fi n t e g e rb o x e s t h u s ，t h el a g r m l g i a n r e l a x a t i o np r o b l e m sc a nb es o l v e de f f i c i e n t l ya n dt h ea l g o r i t h mi sg u a r a n t e e d t oc o n v e r g et oa no p t i m a ls o l u t i o ni naf i n i t en u m b e ro fi t e r a t i o n sn u m e r i c a i r e s u l t sr e v e a lt h a tt h eo u t e ra p p r o x i m a t i o nm e t h o ds i g n i f i c a n t l yo u t p e r f o r m st h e s u b g r a d i e n tm e t h o da sad u a ls e a r c hp r o c e d u r e f i n a l l y , e x t e n s i v en u m e r i c a l r e s u l t ss h o wt h a tt h i sm e t h o di se f f i c i e n tf o rt h en o n l i n e a rk n a p s a c kp r o b l e m s t h i st h e s i si so r g a n i z e da sf o l l o w s i nc h a p t e r1 ，w eg i v es o m eb r i e fi n t r o - d u c t i o no fn o n l i n e a rk n a p s a c kp r o b l e m sa n ds o r t i ee x a m p l e so fi t sa p p l i c a t i o n s r e c e n tr e s e a r c hp r o g r e s s0 2n o n l i n e a rk n a p s a c kp r o b l e m si sa l s o i n t r o d u c e d i nc h a p t e r2w ed i s c u s ss o m eo ft h ee x i s t i n gm e t h o d sf o r s o l v i n gt h em u l t i 。 2 0 0 5 年上海大学硕士学位论文 i v d i m e n s i o n a ln o n l i n e a rk n a p s a c kp r o b l e m s ，s u c ha 8b r a n c h - a n d b o u n dm e t h o d ， s u r r o g a t er e l a x a t i o na l g o r i t h m a n dah y b r i dm e t h o db a s e do nd y n a m i cp r o g r a m r n i n ga n db r a n c h - a n d b o u n d an e wc o n v e r g e n tl a g r a n g i a nd u a la n dd o m a i nc u t m e t h o di sp r e s e n t e di nc h a p t e r3f o rs o l v i n gt h em u l t i - d i m e n s i o n a ln o n l i n e a r k n a p s a c kp r o b l e m s i nc h a p t e r4 ，w er e p o r to u rc o m p u t a t i o n a lr e s u l t sa n dc o r n p a r et h ep e r f o r m a n c eo ft w od u a ls e a r c hm e t h o d s ：o u t e ra p p r o x i m a t i o nm e t h o d a n ds u b g r a d i e n tm e t h o d m o r e o v e r ，w ec o m p a r eo u rp r o p o s e dm e t h o dw i t ht h e h y b r i dm e t h o do fd y n a m i cp r o g r a m m i n ga n db r m m h - a n d - b o u n dm e t h o d f i n a l l y , c h a p t e r5c o n t a i n ss o i i l ec o n c l u d i n gr e m a r k s w es u m m a r i z et h em a i nr e s u l t so f t h et h e s i sa n ds u g g e s ts o m ef u t u r er e s e a r c hd i r e c t i o n s k e yw o r d s ：n o n l i n e a ri n t e g e rp r o g r a m m i n g ，n o n l i n e a rk n a p s a c kp r o b l e m ) l a g r a n g i a nd u a l ，d o m a i nc u t ，o u t e ra p p r o x i m a t i o nm e t h o d ，s u b g r a d i e n tm e t h o d ， b r a n c l l _ a r i d b o u n dm e t h o d ，h y b r i dm e t h o d 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：溢鱼日期：2 堂：生 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：醒鲺导师签名：左塾：! 鱼量日期： 力- j 6 z 第一章前言 1 1多约束非线陛背包问题的定义 多约束非线性可分离整数规划问题可表示为 ， ( ，) i n e l c m ) = ，7 ( q ) j = l s t 肌( 。) = g i j ( z j ) 6 。 ，= 1 。x = f j 曼x ：i 1 q ， 0 = l ，一，m ， z 。整数，j = 1 ， ， ) 其中疗，9 。为定义在，屯= 】上的连续实函数，0 和嘶为整数，分别表示整数变量 跏的下界和上界，b 。是常数，这里j = 1 ，t ，i = 1 ， 线性整数规划白2 ( 1 世纪5 0 年代以来得到了深入的研究和广泛的应用，特别是线 性背包问题已有非常有效的算法( 见【1 5 】 2 4 1 ) 然而在实际情况下，许多问题的模型都 是非线陆帆由此产生的最优化问题就是非线性背包问题非线性背包问题有着广泛 的应用：其r f l 包括生产计划( p 1 0 d u c t i o np l a n n i n g ) ( 【3 7 1 ) ，市场生产( m a r k e t i n g ) ( 2 2 1 ) ， 分层抽样( s t , r a t i s c ds a m p l i n g ) ( 5 1 ) ，网络中系统可靠性( s y s t e mi e l i a b i l i t y ) ( 4 】 3 3 3 5 ) 制造业中容量计划( c a p a c i t yp l a n n i n g i n m a n u f a c t u r i n gn e t | w o r k s ) ( ) 等 尽管非线性背包问题有着重耍应用，由于问题的困难性和复杂性，这类问题在文献 中没有受到足够的重视，缺乏有效的算法或算法的实现经验，因此求解非线性背包 问题仍然是整数规划中最具有挑战性的课题之一 背包问题是整数规划中的一类特殊的有重要应用的问题，问题可描述如下：一 个徒步旅行者带了一个背包，他要用背包装入尽可能多的物品而不能超过这个背 包的容量如聚有几种不同的物品可以装进背包，且每种物品都有一定的价值和体 积下面的问题就产生了：如何从这几种物品中选择才能使得放入背包的物品的价 值最大这就是著名的背包问题( kr a a l ) s a c kp r o b l e m ) 令n 表示背包的最大容量，整数1 、2 ，：t z 表示，t 种可以选择的物品，p ，n 。分 2 0 0 5 年上海大学硕士学位论文2 别表示第j 种物品的价值和体积背包问题的数学模型可以表示为： t ( k p ) i t l 3 x p # x j j = l s ，t a j x j 曼6 ， j = l x j 0 ，哟整数，= 1 ，t j 其中x j 代表第j 种物品被选择的数目当( o ，1 ) 时，问题( k p ) 就是我们所熟 悉的0 - 1 线性背包问题 如果我们再加入背包最大容许的重量为c ，且设装入背包的第j 种物品的重量 为q ，则上述问题就变为二维背包问题 如果上述问题中目标函数或约束条件中至少有一个是非线性的，则为非线性背 包问题它的一般形式可表示为： ( f 户) - l - l a x ，( 。) = i ( q ) l j 曼u j ，x j 整数，j 一1 ，n 其中，g ，( z ，) 是z ，的单调递增函数 当约束条件v n 兰2 时，上述问题就是多约束背包问题 其。 j g ( 一) = ( 9 l ( z j ，现( 。) ，( m ) ) 7 ，b = ( b l ，b 2 ，d 。) 7 矗，是孽调递增函数 本文在叙述的时候用到了一些概念，我们给出简单的描述： 定义1 1 1 如果对vm r 2 d 和 r ，( ) 1 ，有 6 一q 盼 。岸 f f o “ s f 疗 。衄 | | = m 躐 扣 巧 。埘血 | | 町 旬 g 0 2 0 0 5 年上海大学硕士学位论文 3 则称dc 掰。是一凸集 定义1 l 2 如果dcr 6 为一凸集，如果对vz l ，x 2 d 和 琏，0 1 ，有 ，( 。1 + ( 1 一a ) x 2 ) ( ) a ，( 0 1 ) + ( 1 一a ) ，( 。2 ) 则称f d 一碇为凸r 凹j 函数 定义l 1 3 若规划中目标函数及约束函数都是线性函数，称它为线性规划；否则， 若其中至少有一个是非线性函数，则称它为非线性规划特别地，若目标函数为二 次函数，且约束函数是线性函数，这种非线性规划为二次规划 定义l - 1 4 假设函数，是定义在集合d 上的函数，如果对v 。i ，x 2 d ，且0 1 $ 3 2 ， 都有凡 1 ) 曼( 。2 ) ，则称函数，在d 上是单调递增缄非减j 的 定义1 ，l | 5 若非线性整数规划问题( p ) 中所有的f j ( z j ) 和g f ( z ) 都是单调递增函 数，则问题( p ) 就叫作背包问题；若厶( 畸) 和乳( z ) 0 = 1 ， z ，j = 1 ，n ) 都是 线性函数，则问题( 尸) 叫线性背包问题；若 j ( x j ) 或m ( z ) 中存在非线性函数，则 问题( p ) 叫非线性背包问题；在背包问题中，若决策变量z ，只能取0 或1 ，则问题 f ，) 称作0 1 背包问题 定义1 l 6 如果一个函数可以写成若干个一元函数和的形式，则称其为可分离的， 即：若，( 2 5 i ，2 5 2 ，2 5 ) = ，1 ( 。1 ) + ，2 ( 。2 ) + + ，。( 2 5 。) ，则称函数，是可分的 定义1 1 7 所有次策变量均要求为整数的整数规划称为纯整数规划；部分决策变量 要求为整数的整浆规划称为混合整数规划；所有决策变量均要求为口的整数规划 称为纯口一整数规划；部分次策变量要求为口一的整数规划称为混合o - 1 规划 定义1 1 8 在本文的问题( m n k p ) 中，约束函数是凸函数，如果目标函数是凹函 数，则称此规划为多约束凸背包问题；否则，如果目标函数是凸函数，则称此规划 为多约束凹背包问题 1 2多约束非线性背包问题的应用模型 我们知道，在许多情况下，无论经济生产还是工业生产中，许多问题的模型都 是非线性的，因此非线性背包问题有着重要的应用例如，m a t h u r 等( 2 s l 介绍了它 在资金预算中的应用，z i e g l e r ( 3 7 1 ) 和5 u s s ( 2 2 1 ) 介绍了它在生产计划和市场经营中 的应用，至于在样本分层抽样的应用可参考文献 5 1 另外，在网络可靠性系统( 3 5 1 ) 中也提到了非线性背包问题的应用本节介绍三个模型 2 0 0 5 年上海大学硕士学位论文4 1 2 _ 1 制造业中容量计划问题 许多制造业系统都可以看作是一个排队的网络模型其中，网络中的一个结点 代表一台机器或者一个工作站，制造业容量计划问题就是给定一个总的费用约束 值，使得工作站的服务耗用最小这个问题可描述成下面的形式： 厶( q ) ，= l m ( z ) = g i j ( 。j ) o ) ； m u ：第i 个系统中的第，个工作站等待顾客的时问方差的平方项系数； 。第z 个系统中的第j 个工作站服务时间方差的平方项系数； b i l r 和t i - u p a t i ( 2 ) 用下面的函数来近似工巧( q ) ，并证明了三”( 巧) 是的凸函 数： l i j ( 。，) = y i j x j + ( ( c n u + c s q ) 1 为( 2 ( q 一1 巧) ) ) ( ，町，c “小c s 。) ， 其中 n c ，”，z ，c ，c s ”，= ；。p ( 一2 ( 1 c “订) ( z j 一7 。) 3 m ，( c “玎+ c s 订) 喜萧i 1 n t s pe， 2 0 0 5 年上海大学硕士学位论文5 1 2 2 分层抽样中的最优样本配置 我们来考虑如何估计人口均值p 的值口一个解决此问题的方法就是把人口分 成n 类，从每类中抽样，人口均值就可以描述为这，z 类中抽样平均值的加权和从 每类中抽取样本的数量问题就可以形成一个非线性背包问题的模型，其中整数决策 变量表示每类中样本的规模这类问题可以表述为在给定的抽样费用预算下使得估 算值口的方差最小抽样费用函数可以为线性函数也可以为非线性函数( 1 卅) 我 们这里考虑约束函数为线性函数的情况 这里我们记： m 分成类的数目； ：每类中样本的大小即决策变量0 = 1 ，n ) ； m ：第7 类中抽样单元的数目； 所有类中抽样单元的数目( = ) ； j = l ，q ：第，类的实际均值大小； q ：第类的标准方差； f ，第j 类的样本均值； 人口均值； b 所有可用的抽样赀用； b ，+ 在第，类中凋查一个单元所需的费用 c o c h 一，! 指出，“的无偏估计量f 可以由所有类的样本均值的加权来计算 也就是f = 现方差估计由下面的公式给出： v ( 口) = 0 n 2 ) 孵砖( ，一，) ( ) j = 1 数整 吁 饥 叶 一 一墨皿渤 m 2 0 0 5 年上海大学硕士学位论文 令d ，= ( ，一，川) 2 ，d = c o 屿问题( s a m p ) 可以写成 ，= 1 ( s a m p 7 ) m i n “j d j = 1 t l s t b f f ：9sb ， 3 = 1 f j x js 1 ，z j 整数，j = 1 ，n 注意到在( s a m p 7 ) 中，目标函数是一个可分的凸函数，约束函数是一个线性函数， 所以它是一个凸背包问题 1 2 3 系统可靠性问题 对于一个n 级串联模型，问题在于如何进行最优的冗余分配，使得在给定费用 约束下系统的可靠度最大如图( 11 ) r lr 。 数学模型可表示为： f s h l 图1 1 串并可靠性系统示意图 n a x r 。= 1 1 1 一( 1 一吗) s t p j z ；p ， 勺( 町+ 叫，d ) ) 兰c u ，。，c x p ( q 4 ) 毗 f j s x j 1 0 ，。j 整数，j = l ，n 2 0 0 5 年上海大学硕士学位论文 7 这里我们记： t 。整个部件的可靠度； 且，) ：第j 级上部件的可靠度； 功：第j 级上每个部件的重量和体积的乘积； 勺：第j 级上每个部件的费用； c ：每个部件的最大费用； p 产品的重量和体积乘积； “o ：第级上的每个部件的重量； w ：重量的约束值； ，：第j 级上最少部件数； q ：用在笫j 级上的部件数； t q 第j 级上最多的部件数 如果我们把( s r ) 的目标函数取对数，这样它就可以转化成一个( n k p ) 问题；注意 到该问题的特殊性，我们可以通过等价变换把( s r ) 写成下面的非线性资源分配问 题； ( 上s _ r ) m a x 宄。= i n f l 一( 1 一吩) 。】 i = 1 t p j x ；s p ， j = 1 c j ( x j + e x p ( x j 4 ) ) c ， j = 1 w j z j 。x p ( x s 4 ) s ， j = 1 2 ，兰q 1 0 ，叼整数，j = 1 于是目标函数就变为可分离函数了 1 3 多约束非线性背包问题的研究现状和研究进展 由于现实生活中许多问题的数学模型都是非线性的，因此多约束非线性背包问 题的应用较为广泛但是由于多约束非线性问题的复杂性，缺乏有效的算法和算法 的实现经验，相应的文献并不多见现有的算法主要是分枝定界算法和动态规划算 法或它们的混合算法 2 0 0 5 年上海大学硕士学位论文 8 在求解一般的整数规划问题时，传统曲方法是分枝定界算法此外还有动态规 划算法、约束替代松弛算法、以及动态规划与分枝定界的混合算法例如：求解连续 松弛问题的分枝定界算法( 见【3 , 1 8 1 1 3 1 1 2 5 】【2 6 1 1 3 3 ) ；如何利用动态规划来求解整数 规划( 见l s i l t ? ) 如何利用替代约束松弛算法可参考1 8 】8 ；文献【2 3 】介绍了动态规划和 分枝定界算法相结合求解整数规划的混合算法对偶方法也是整数规划算法中一类 常用方法，但由于对偶间隙的存在，一般把对偶方法和分枝定界结合起来( 1 s l 1 9 ) ， 在文【1 7 1 【2 0 3 2 中还提出了整数规划的非线性对偶公式当然，不同的问题具备不 同的特点，因此相应的有不同的算法例如，文【3 6 中介绍了含等式约束的线性背 包问题的解法；而文f 3 0 则讨论了带不等式约束的0 l 线性背包问题的分枝定界 算法“e x p a n d i n gc o i ：- e ”算法；b i l i o n n e t 在文 1 j 中研究了分数背包问题的解法 ( 非线性背包问题) ：当非线性背包问题的目标函数和约束函数都是变量可分离时， h o c h b a u m 和m a t l m r 等人在文i 1 3 ) 【2 5 】中提出先通过等价变换把它变成o 1 线性 背包问题，然后再用动态规划去求解等价的0 1 线性背包问题，从而达到求解非 线性背包问题的方法；如果非线性背包问题只含一个不等式约束，当非线性资源分 配问题( p ) 中似z ：) 和吼( 。) 都为凸函数时，b r e t t h a u e r 和s h e r r y 于1 9 9 5 年在文【3 1 中提出了解连续松弛问题的乘子搜索法和解非线性凸资源分配问题) 的分枝定界 卿：法，当非线陆资源分配问题的目标函数 ( 她) 为凹函数时，他们还建议用线陛下 逼近方法来求解非线性凹资源分配问题，但是在文章中没有给出实现算法的具体途 径，也没给出有关的数值结果；2 0 0 2 年，他们又在文 4 】中提出了解连续松弛问题 的p e g g i n g 算法，并用分枝定界算法求解了非线性资源分配问题( 尸) ，由于p e g g i n g 算法能通过有限步迭代求出连续松弛问题的最影c 解，因此，在解连续松弛问题时， 该方法相对于乘子搜索法具有更高的效率文1 1 9 1 首次提出了求解单约束非线性背 包问题的拉格朗日对偶和区域分割方法这种方法相对于一般的分枝定界算法来讲 有更高的效率，能解上千个变量的问题这是因为，一方面由于拉格朗日对偶能给 出一个很好的界，而且原问题的拉格朗日松弛问题能分解成n 个无约束的一维极值 问题；另一方而由于利用了目标函数和约束函数的单调性可以将大量的可行点和不 可行点去掉，从而大大缩小了解的搜索范围。并且这样去掉一些点以后的搜索区域 仍然可以表示成整数箱子的并集，同样有利于拉格朗日对偶问题快速求解文f 1 8 1 还给出了求解非线性背包问题的等高线割方法 1 o d i a l a i n 和m e h n a n 分别在e 1 6 】和 2 7 】中介绍了连续变量单约束非线性资源分 配问题的解法另外，所有能解多约束非线性整数规划问题的方法都可以用来解相 2 0 0 5 年上海大学硕士学位论文 9 应的非线陆背包问题当目标函数和约束函数都是凸函数时，r i h u 和w a l k e r 在【3 1 】 中讨论r 带多个约束的非线性背包问题的拉格朗日对偶解法c d t t l ) t , a 在文【u 中 对论了含多个约束的一般非线性整数规划问题的分枝定界算法d j e r d j o u r 等在文 8 l 中讨论了运用约束替代松弛算法求解二次多约束背包问题 第二章多约束非线性背包问题的现有算法 2 1 非线性凸整数规划的分枝定界算法 分枝定界是l a n d 和d o i g ( 1 9 6 0 ) 提出经d a k i n 修正的一种方法，它的基本思想是 根据某种规则将原整数模型的可行域分解为越来越小的子区域，并检查某个子区域 冈整数解的情况，直到找到最优的整数解或探明整数解不存在根据整数规划模型 性质的不同，存在许多不同的分枝定界方法以及分枝定界技巧，分枝将连续问题的 解空间分解成两个互相排斥的子空间，目的在于消去不存在所求的整数解的部分 饿地。一个非线性t 昆合整数规划( n l m i p ) 问题如下形式： m i n ，( z )( 2 1 1 ) s t m ( o ) 0 ，i = 1 ， 0 ) 、二o ，= 1 ，。， q 整数，j 1，m n 这里，m 是凸函数，饥是线性函数 分枝定界通过松弛整性的条件变成连续最优化问题，从而求得连续问题的一个 全局最优解，若这个解为整数，则它为( n l m i p ) 的一个整数解若不是整数，则至 少有一个变量x j 是连续的，可以将的值分为整数部分b 1 和分数部分。：，即 q = h + z j ，其中b 】为整数，o ； 1 ，于是形成了两个子问题，每个子问题中 分别增加一个上界约束。j ：m ， 和下界约束q h l + l ，我们称原问题为父问题， 这种由父问题产生子问题的过程就称作分枝，变量z ，为分枝变量，因此求解父问 题的连续松弛转化为求解这两个子问题的连续松弛问题一般地，每个结点的造代 都给目标函数值提供一个上界和下界，且原问题的下界就是所有子问题中下界最小 的一个，继续进行l 面的分枝及求解连续司题的算法，直到我们找到某个连续司题 的个可行的整数解，则它所对应的目标函数值为问题( n l m i p ) 的目标函数的上 界为防止子问题数目增加太快，我们必须把已经解过出现下列情形之一的子问题 从问题集中删去( 剪枝) ( ，) 子问题不可行， 了刚题的r 界比原始问题最优值的上男要大； ( u ) 子问题的下界比原始问题最优值的上界要大； 1 0 第二章多约束非线性背包问题的现有算法 2 1非线性凸整数规划的分枝定界算法 分枝定界是l a n d 和d o i g ( 1 9 6 0 ) 提出经d a k i n 修正的一种方法，它的基本思想是 根据某种规则将原整数模型的可行域分解为越来n l , 的q ：k 域，并检查某个子区域 内整数解的情况，直到找到最优的整数解或探明整数解不存在根据整数规划模型 性质的不同，存在许多不同的分枝定界方法以及分枝定界技巧，分枝将连续问题的 解空问分解成两个互相排斥的子空间，目的在于消去不存在所求的整数解的部分 一般地，一个非线性混合整数规划( n l m i p ) 问题如下形式： t n l m i p 、m i n ，( 。) ( 2 1 1 ) s , t m ( z ) 0 ，i = 1 ，册， ) = o ，b = 1 ， 奶整数，j = l ， 这里f ，m 是凸函数，是线性函数 分枝定界通过松弛整性的条件变成连续最优化问题，从而求得连续问题的一个 全局最优解，若这个解为整数，则它为( n l m i p ) 的一个整数解若不是整数，贝0 至 少有一个变量。，是连续的，可以将q 的值分为整数部分 x 3 和分数部分。j ，即： z ，：14 - g ；，其中1 为整数，o 0 ，j = 1 ，一，n ) ， z = a r g 嘴 糍矧胚。) 1 皿， 其中勺r ”表示第j 个分量为1 ，其它分量为0 的单位向量 h e u r i s t i ca ( 当9 i ( ) 单调递增时) 第一步令矿表示松弛问题的最优解现在对z + 向下取整，即令z = 妒1 ，则z 就 是一个可行解 第二步如果存在7 0 1，n ) 使得( 21 6 ) 成立，令= z + e j 。；否则，停止 第三步转第二步 如果m ( ”。) 单调下降且z 是一个可行解，则( 2 16 ) 可以改为 ：“, - - e j u s 搿 糍糍躯。) ，皿， 其中g = jz j 一1 如，办( 。j ) 一h ( x j 一1 ) 0 ，= 1 ，一，n ) i i e u r i s t i cb ( 当9 i ( 跏) 单调下降时) 第一步设r + 是松弛问题的最优解，对x + 向上取整，令z = 妒】+ 1 ，则。是一个 可行解 第二步如果存在，o ( 1 ， ，n ) 使得( 2 1 7 ) 成立，令z = z e j o ；否则，停止 第三步转第二步 从上面启发式思想中我们可以知道，当问题的维数比较小时，启发式算法是比较快 的，然而，如果增加维数，此算法变得比较差如果原问题有一个整数可行解，则 我们可以在算法中找到这个可行解因此对于一个给定的问题，如果存在可行解， 启发式算法# l i 自a 保证找到这个整数可行解 2 0 0 5 年上海大学硕士学位论文 1 4 22二次多约束非线性背包问题的约束替代松弛算法 考虑如下二次整数规划： ( q p ) i t l a x ( c j x j 一吗豸) z ，岛，j = l ，一，? l ， ( 228 ) 其扣c j 0 ，d j 0 ，a i j x j 0 ，b l 0 ，2 0 矗( 保证目标函数单调递增) 上述问题中 的变量可以取任何整数值，目标函数可以看作可分离二次函数，这里模型主要用于 资金预算( 见f 2 叫) 固为q 为整数，目标函数勺q 一屿z ；可以用分片线性晒数疗( 勺) 代替，断点在= 1 ，2 ，q ，疗( ) = c ，一d j k 2 因此上述( 2 2 8 ) 等价于下面的问 题 ( q p l ) i i i i l x b ( x j ) ( 22o ) 町曼b i j = 1 0 z j 7 0 ，。j 整数，j = 1 ， ，n 2 2 1 约束替代松弛 设w = 1 4 1 , ( i = 1 ，2 ，。) 为非负向量，则不等式 为( 22o ) 的一个替代松弛约束而且，问题转化为如下形式 ( s q p ) m a x f a 巧) 0s j 1 0 ，z j 整数，j 则( 22 1 1 j 为( 229 ) 替代( 更新) 松弛问题 ( 22 1 1 ) 砺 m “ 一、”_ = “ 0 ， 眨：。) = 、】= l 、uj lo 。，否则， f 翌业幽等墅型g ，。( d ) ，b ( d ) 一警1p j g j ( d ) 一9 j ，( d ) o ， 吻：引一，p j y s ( d ) ( 222 1 ) h ”1 否则 ( ) 选取n 。，( 即选择满足最优解j + ，p j ，j = 1 ，2 ，n 的n 的最大值) 即：连续 背包问题的基变量”即+ l 以及缩减成本y j e ( y 2 k 聊；巩b 0 ，k 曼p j ) 则 “3 = m m f ( 吣1 _ ( t 3 2 ) 其1 d 2 ， 0 否则， d 句 o ( 2 2 2 3 、 否则， 口】，= ( 疗一疗一1 ) g j - ( w ) 一( j ，。+ + l 一厶+ p ，。) 卯( w ) 0 2 ，5 ( 如，p ；+ l 一，7 + + ) 珊( d ) 一( 矗，一办曲一1 ) a + ( d ) ， o 句5 ( 乃+ ，巧+ 】一疗，) 毋( w ) 一( f 5 ，+ 1 一疗，p ，) ，( w ) 钆j = ( 乃，p ，+ l 一办扔) 耵+ ( d ) 一( 乃* ，p ，。+ 。一厅+ 曲+ ) ( d ) 根据上述结果，我们可以利用下述算法求w 4 第一步：令w = w o ( 0 ) 为替代乘子的初始集 第二步，利用m a t h u r 等( 2 g 1 ) 中的算法来求解上述相应的连续背包问题，且1 i i 】定指 玎 p 鸭 ，、i 努 f f o 4 西 ，f，、l 匀 ； = 皿 2 0 0 5 年上海大学硕士学位论文 1 8 标j4 和l 整数蜥( j = 1 ，2 ，r 。) 第三步：利用式子( 2 2 1 8 ) 找方向d ，若d = 0 ，停止；否则，转第四步 第网步：利用式子( 221 0 ) 一( 22 2 3 ) 找最大步长0 = ，情形如下： ( i ) 若n = 0 ，停止，不能保证z ( w ) 有最优解，但是提供式子( 2 ，2 9 ) 的一个上 界 ( i i ) 若n 0 ，w = w + a d ，转第二步 2 2 3 隐枚举算法 在介绍求解旧p ) 算法之前，我们先来介绍枚举算法中广泛应用的一种枚举迭 代 定理2 ，2 1 如果为一替代乘子向量俅自于上述算法j ，目标函数值z ( s q p ：) 的相应连续解为j + 和p j ( j = 1 ，2 ，n ) ，则对( q p ) 的任何一个最优解满足： 若( - 一l ) 2 屿( 止一1 ) ( 勺一s 3 g ，( w + ) ) ( z s q p , w + 卜z o ) ( 勺功吗聊2 一岛- p ，毋( 1 矿) ) 或i ，z ii