（运筹学与控制论专业论文）多约束二次01背包问题的一个有效算法.pdf

2 0 0 6 年上海大学硕士学位论文 摘要 当前我国正处在经济快速发展时期，与此同时，资源消耗也呈高速增 长的趋势如何最合理地利用有限的资源，使生产的消耗最小，利润最大是 经营管理者所关心的主要问题而现实中的有些资源是只能取整数的，特 别是很多决策变量只能取0 或1 所以对0 - 1 整数规划的研究在理论上和实 践上都有着重大意义本文主要讨论多约束二次0 - 1 背包问题其数学模型 可描述如下： n ( m q k p ) m a xm ) = q l l x l + 蜘q q i = 1 l s i j n st a x b ， z o ，1 ) “， 其中蜘0 ，1 曼i ! j n ，a = ( ) m 。，0 4 j 0 ，i = l ，m ，j = 1 ，n ， b = ( b l ，h ) 7 ，0 b i 整l ，i = 1 ，m 我们根据这类问题的特殊性质，提出一个新的分枝定界算法，该算法 使用分枝定界策略和拉格朗日对偶来寻找问题的最优解在算法中，我们 把拉格朗日松弛问题转化为最大流网络最优化问题，并使用外逼近方法求 解子问题的对偶界我们还使用替代约束技术搜索问题的可行解以进一步 提高算法效率初步的数值试验表明该算法对求解多约束二次背包问题是 有效的 文章共由五部分组成：第一章简单介绍二次0 - 1 背包问题的提出，研究 现状和进展；第二章介绍单约束二次o _ l 背包问题求上界的几种方法；第三 章中我们详细介绍分枝定界算法；第四章我们给出多约束二次o - 1 背包问 题的分枝定界算法；第五章给出了用分枝定界算法求解单约束及多约束二 次0 - 1 背包问题的数值结果 关键词：整数规划；多约束二次。一1 背包问题；分枝定界方法；拉格朗日 松弛；外逼近；替代约束；贪婪算法 2 0 0 6 年上海大学硕士学位论文 i i a b s t r a c t c h i n ai sn o wi nt h ep e r i o do ff a s te c o n o m i cd e v e l o p m e n t m e a n w h i l e ，r & - s o u r c ec o n s u m ei n c r e a s e sd r a m a t i c a l l y h o wt ou s et h el i m i t e dr e s o u r c e se f f i - c i e n t l yi no r d e rt og e tt h em i n i m a lc o s to rm a x i m a lp r o f i ti so n eo ft h em o s t c o n c e r n e dp r o b l e mi ne c o n o m ya n dm a n a g e m e n t i nm a n ya p p h c a t i o n s ，t h er e - s o u r c e sa r en o td i v i d a b l e ，i np a r t i c u l a r ，i ti so f t e nr e q u i r e dt ot a k eb i n a r yv a l u e t h e r e f o r e ，i ti so fs i g n i f i c a n c et os t u d y0 - 1i n t e g e rp r o g r a m m i n gi nt h e o r ya n d p r a c t i c e i nt h i st h e s i sw ea r em a i n l yc o n c e r n e dw i t hq u a d r a t i c0 - 1k n a p s a c k p r o b l e m t h ep 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 q k p ) n l a x ，( z ) = q l i x l + q i j x i x j i = 1 1 兰i j 兰“ s t a x b ， z 0 ，1 p ， w h e r eq l j 0f o r1si j n ，a = ( o 玎) m nw i t ha 0 0f o ri = 1 ，m ， j = 1 ，他，a n db = ( b l ，) r w i t h0 b l ：1 a i jf o r i = 1 ，m b ye x p l o i t i n gt h es p e c i a ls t r u c t u r e so f t h ef u n c t i o n ，w ep r e s e n tab r a n c h - a n d - b o u n dm e t h o df o rs o l v i n gm u l t i d i m e n s i o n a lq u a d r a t i c0 - 1k n a p s a c kp r o b l e m s t h em e t h o di sb a s e do nt h el a g r a n g i a nr e l a x a t i o na n dt h es u r r o g a t ec o n s t r a i n t t e c h n i q u ef o rf i n d i n gf e a s i b l es o l u t i o n s w es o l v et h el a g r a n g i a nr e l a x a t i o n s b yt h em a x i m u m - f l o wa l g o r i t h ma n ds e a r c hf o rt h el a g r a n 百a nb o u n d sb yo u t e r a p p r o x i m a t i o nm e t h o d c o m p u t a t i o n a lr e s u l t sa r er e p o r t e dt os h o wt h ee f f i c i e n c y o ft h ep r o p o s e dm e t h o df o rm u l t i - d i m e n s i o n a lq u a d r a t i c0 - 1k n a p s a c kp r o b l e m s t h es t r u c t u r eo ft h et h e s i si sa sf o l l o w s i nc h a p t e rl w eg i v es o n l eb r i e f i n t r o d u c t i o nt ot h eb a c k g r o u n do ft h eq u a d r a t i c0 - 1k n a p s a c kp r o b l e m sa n dt h e e x i s t i n gs o l u t i o nm e t h o d si nt h el i t e r a t u r e i nc h a p t e r2 ，w eb r i e f l yi n t r o d u c e s o f t i ee x i s t i n gm e t h o d sf o re s t i m a t i n gu p p e rb o u n do ft h eq u a d r a t i c0 - 1k n a p s a c k p r o b l e m s i nc h a p t e r3 ，w ed e s c r i b et h ef r a m e w o r ko fb r a n c h a n d b o u n dm e t h - o d sf o rs o l v i n gt h eq u a d r a t i c0 - 1k n a p s a c kp r o b l e m an e wb r a s m h - a n d b o u n d a l g o r i t h mf o rt h em u l t i d i m e n s i o n a lq u a d r a t i c0 - lk n a p s a c kp r o b l e mi sp r o p o s e d i nc h a p t e r4 w er e p o r ti nc h a p t e r5o u rc o m p u t a t i o n a lr e s u l t so ft h ep r o p o s e d 2 0 0 6 年上海大学硕士学位论文 i i i a l g o r i t h mf o rt w oc l a s s e so fq u a d r a t i c0 - 1k n a p s a c kp r o b l e m s k e yw o r d s ：i n t e g e rp r o g r a m m i n g ，m u l t i - d i m e n s i o n a lq u a d r a t i c0 - 1k n a p s a c k p r o b l e m ，b r a n c h - a n d - b o u n dm e t h o d ，l a g r a n g i a nr e l a x a t i o n ，o u t e ra p p r o x i m a - t i o n ，s u r r o g a t ec o n s t r a i n t ，g r e e d ya l g o r i t h m 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名： 翻：蚤日期盥：形 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：二雌导师签名：够雌日期：羔蚍、乙眵 第一章前言 1 1 参约束二次0 - 1 背包问题的提出及应用 随着经济的快速发展，如何有效的利用现有的人力、物力完成更多的任务，或 者在预定的目标下，如何耗用最少的人力、物力去实现目标已经成为经营管理中的 核心问题将现实中的这类统筹规划问题用数学方法来进行分析就是数学规划在 线性和非线性规划中决策变量一般可以取非整数的实数值，然而在很多情况下决策 变量的取值往往是离散的，例如在研究人力资源分配问题中，如果决策变量表示分 派到某项工作的人数时，就不能取非整数值另外，如果决策变量代表购买大型设 备，如发电机组，轧钢设备，飞机等高值物品时，显然也无法取连续值，在这种情况 下，决策变量只能取离散的整数值或二进制的0 或1 所谓整数规翔就是决策变量 有整数要求的数学规划如果变量的取值被限定为。或1 ，那么就称为o 1 规划整 数规划又有线性和非线性之分，如果整数规划中目标函数及约束函数都是线性的， 称之为线性整数规划；否则其中至少有一个是非线性的，则称为非线性整数规划 如果目标函数是二次的，则为二次整数规划我们研究的多约束二次o 1 背包问题 就是一个特殊的二次整数规划：它是在多个o - 1 背包约束下，最大化一个二次目标 函数而所谓背包约束就是具有非负系数的线性约束二次0 _ l 背包问题可表示为 如下形式： n ( m q k p ) m a x ，( z ) = q i l z i + q l j 2 e l x j i = 1 l g j ! “ s t a x b ， 茁 o ，1 ) ”， 其中兰0 ，11i 兰jsn ，a = ( 。玎) m n ，a l j 兰0 ，i = 1 ，m ，j = 1 ，n ， b = ( b l ，6 仇) 7 ，0 b i t 时，p i j + 功i 表示同时做第i 个项目和第j 个项 目的利润适当的选做项目，使总利润最大为了方便起见。记n ：= 1 ，n ) 代 表项目的集合如果选做第j 个项目，则x j = l ，否则x 1 = 0 那么这个问题就可归 结为如下二次o 1 背包问题： m a xm ) = p l j x l x j i e n j e n s t w j x j c ， ， 。j o ，1 ，j n 在二次背包问题的具体应用中，资源限制往往不止一个，这时就要考虑多约束 问题 1 2 多约束二次。一1 背包问题研究现状及进展 由于在应用及理论方面提出的许多问题都可归结为多约束二次o - 1 背包问题， 所以对此类问题的研究有着重大意义它是一类特殊的整数规划问题，而求解此类 规划问题是相当困难的由于线性0 - 1 背包问题是n p 难的，所以二次背包问题也 是n p - 难的文献中已有的求解方法主要是针对单约束二次o 1 背包问胚就我们 所知，目前还没有求解多约束二次。一l 背包问题的精确算法对问题( q k p ) 的算法 主要是基于不同的定界技术，变量固定技术和启发式算法而构造的分枝定界方法 文 1 0 】通过构造目标函数的上平面来得到问题的上界文【7 用拉格朗日松弛技术 来计算上界文 1 8 】把拉格朗日分解和松弛相结合得到优于拉格朗日松弛的上界 2 0 0 6 年上海大学硕士学位论文 3 文6 】则通过线性规划方法和拉格朗日松弛来得到更好的上界文【1 4 】通过f 2 最 佳逼近来获得上界并提出了变量固定策略另外还有些其他的方法( 见【5 】) 对于 一般的超模( s u p p e r m o d u l a r ) 背包问题的拉格朗日对偶和连续松弛可参见【1 1 ，问题 ( q k p ) 是超模背包问题的一个特例 1 3 本文的工作 本文提出了一个基于拉格朗日对偶和约束规划的解多约束二次o - l 背包问题的 精确算法由于离散问题的特性，对偶方法是整数规划中的一个非常有力的工具和 方法经典的对偶方法只对可分离问题有效为克服对偶间隙问题，文 1 5 2 1 1 中 提出了非线性对偶方法注意到问题( m q k p ) 中的目标函数一般是不可分离的， 幸运的是，对二次背包问题的拉格朗日松弛问题可以设计出多项式时间算法，这就 为建立问题( m q k p ) 的有效精确算法提供了有利条件我们根据这类问题的特殊 性质，提出一个新的分枝定界算法，该算法使用分枝定界策略和拉格朗日对偶来寻 找问题的最优解在算法中，我们把拉格朗日松弛问题转化为最大流网络最优化问 题，并使用外逼近方法求解子问题的对偶界我们还使用替代约束技术搜索问题的 可行解以进一步提高算法效率初步的数值试验表明该算法对求解多约束二次背包 问题是有效的 第二章几种求上界方法 在前面我们提到对( q k p ) 的算法主要是基于不同的定界技术，变量固定技术 和启发式算法而构造的分枝定界方法 1 6 】因此在这一章我们将重点介绍几种求解 上界的方法，在下一章我们再具体介绍分枝定界方法 2 1 上平面方法 这种方法是由g 蛆1 0 ，h a n l l 2 1 e r 和s i m e o n e 在 1 0 l 中提出，它是通过构造二次目 标函数的上平面而得到问题的上界为了方便叙述，( q k p ) 问题可表示为： n ( q k p ) m a x f ( z ) = q l l x i + 。而 l ；1 1 1 t j 三“ s t a t x b ， ( 2 1 1 ) z 0 ，1 p ， 其中锄o ，l i 蔓j n 为维向量， 表示( 2 1 1 ) 的可行集，雪； z o ，1 p 定义2 1 1 函数( x ) 在s 中的上平面 b 为一正数令s ； z o ，1 ) ”：a t e ：b a t z ：n 就是满足下列条件的线性函数9 ( z ) ? 9 ( o ) ，( z ) ， vo s 对于给定的上平面，可以通过解线性背包问题m a x g ( x ) ：z s ) 来得到问题的上界 1 7 j ，还可以用g r e e d y 算法来解如下连续松弛问题获得上界： m a x g ( x ) ：z 雪l ( 2 1 2 ) 其最优解只有两中情况：一种是求出的解恰好是整数解，也为( 2 1 1 ) 的可行解； 另一种情况是只有一个分量为分数，其余都是0 或1 在这种情况下只要令这个分 数为0 便可以得到( 2 1 1 ) 的可行解m 若矿为( 21 1 j 的最优解，则显然有： f ( x o ) ，( 劫兰，( z 4 ) 9 ( ) 因此在分枝定界算法中可以通过求解线性松弛问题( 2 1 2 ) 获得问题的上界和可行 解对应的下界 4 2 0 0 6 年上海大学硕士学位论文 5 对于( q k p ) 问题，可以通过下面的四种简单方法获得上平面9 ( z ) 令h i 。= q l i ， i = 1 ，n ，h i j = ；q i j ，啄= ；，1 兰i j n ，h = ( 6 玎h 。则目标函数可以改写 为 nn ，( z ) = x t h 。= ( h # x d z j j = 1i = 1 令功( z ) = 翟1h l j x i ，显然若为功在s 中的上界，则：1v j x j 便是，( z ) 的上 平面由于h l j 0 ，最简单的功的上界是矩阵日的第j 列元素之和，即 田：妻 l j ：毋j + i 1 i = l l ! i j n 若令m 为( q k p ) 问题的可行解中取1 的分量的最大个数，令d 表示矩阵h 的第 j 列中前m 个晟大元素的指标集，则可以得到比田更优的上界： 丐2 = b i e l j 还有另外两种上界： 哼= m a x 劬j x j + ；lz “ o j 谚：m “+ ：甄lz 研 一t j 它们之间的关系如下： 哼叶2 时 时哼毋 可以看出”；是最紧的上界，可是也是计算量最大的上界为了设计一个有效的分 枝定界算法人们往往采用折中的方案，如用”i 来构造上平面 2 2 拉格朗日松弛法 对a 0 ，定义( q k p ) 问题的拉格朗日松弛函数： n 工( z ，a ) ：= m ) 一 ( 。m - 6 ) 扣= 1 2 0 0 6 年上海大学硕士学位论文 6 则拉格朗日松弛问韪为： ( ) d ( a ) = m a x l ( x ，a ) lz ( o ，1 ) “) 显然，对任意 0 ，弱对偶性成立：d ( a ) ，( z ) 故d ( a ) 是原问题的一个上界，那 么( q p ) 的拉格朗日对偶问题就是求最小的上界： 显然 ( d ) 咖4 ( a ) u ( 工 ) u ( d ) v ( q k p ) 这里我们先说明两个记号：若q y l ，诘1 ，一，m 则记z 兰”；若z sy 且至少 存在一个分量以满足严格不等式 o i ( i i ) d ( a ) 片段线性凸函数，其断点为1 1 ， 2 ， ，且最多有n 个断点； ( 倒) 对于每个k ，扩是拉格朗日函数l ( x ，k ) 在 o ，1 p 上的最大值点； ( i 口) 令r 为满足a t x b 的最大指标k ，则( d ) 的最优值为d ( a ，+ 1 ) = ，( z 1 ) 一 a t + i ( a 7 z ”1 一们 上面的定理刻画了函数d ( a ) 的性质，由此我们可以将对偶函数d ( a ) 的图形描 绘出来令横轴表示a 的值，纵轴表示d ( x ) 的值由性质我们知道d ( ) 为分片线性 函数，在每个区间m + 1 ，1 k 上，d ( a ) 是表达式为d ( a ) = ( b n ( 一) ) a + ，( 一) ，斜率为 ( b n ( 一) ) 的线段，断点坐标为( 扎，工( 扩，札) ) 当 r 时，斜率为正，当k 兰r + 1 时斜率为负斜率的最大值为b ，最小值为b 一n ；1a j 利用上面的性质，我们可以利用外逼近算法找到( d ) 问题的最优解，其中的d ( a ) 可以转化为最小割或最大流问题来求解算法主要是根据函数d ( a ) 的性质，逐步构 造线性函数d ( a k ) ，它与d ( a e 1 ) 所构成的直线相交，再利用交点构造新的d ( a + ，) ， 依次下去，最后“交”出最优解初始的a 可以为，( e ) 加 2 0 0 6 年上海大学硕士学位论文 7 ( 入) 图2 1 ：函数d ( a ) 程序1 ( ( d ) 问题的外逼近算法) 第1 步令1 ：= b 一：10 4 ，岛：= e 翟1 警，n 2 ：= b ，虎：= 0 第2 步a ：= 慨一愚) ( a 一n z ) ，利用最大流算法解d ( a ) ，得最优解x + 令a 3 ：= b a t x + ，胁：= ，( 矿) 第3 步若n 3 a + 岛= 。1 a + 卢1 ，则a ：= a ，停止否则，若蚴 0 ，1 兰i j n ) ， 励= ( j t ) ij = 1 ，n e 中弧的容量定义为： q 【 ) = m a x ( 0 ：蜘一弛) ，( s ，j ) e s i = j ( a ) = q i j ，( i ，j ) e q ， n 印( ) = m i n x ( 0 ，a a j 一蛳) ，( 圳e t 2 - j ( 2 , 2 3 ) ( 2 2 4 ) ( 2 2 5 ) 2 0 0 6 年上海大学硕士学位论文 8 令( 乩可) 表示图g 的一个分割，并且s u ，t 驴弧集扩( 矿) = ( ，j ) i i u ，j 刃 叫做一个s t 割弧的容量矿( c ，) 为) 矿( ，) q 最小割问题就是找一个最小容量 的割令妒( ) 表示最小割的容量，则妒( a ) = m i n u ( ) p ( u ) q 用( 1 ，2 1 ，- ，z 。，o ) 与g 中割矿( v ) 相对应，若i u ，则孔= 1 ，否则孔= 0 下列结果表明拉格朗日松 弛问题可以等价与一个最小割问题 定理2 2 2d ( a ) = 整i 勺( a ) 十a t b 一妒( a ) 证明：有( 2 2 3 ) 一( 2 2 5 ) ，有 似砷= 。黜。争( 卜咖，；黾。蚋( 卜咖p 蜘 2 蚤q h ；船。t 著面n c 0 , a a j - 蓦州q + 蚤，三，孔 一蜘吼+ 妻。a x ( o ，a q 一妻鳓) q = j = l 枷) + 。黜。蚤( 弛 + q 一，( z ) ) 2 j _ _ lc s j ( 1 卅。黜。 善1 ( 弛 、。 = 2 三啪) + 。高。 著1 岣仁= 1i 2 n q j = l n1 蚴) q + q l j x l i = j i = lj = i + l n nn q 3 i ) z # + q j l x j 一，( z ) ) i = jj = l i = j ，( z ) 由于最小割的容量等于最大流，因此，我们就可以用具有多项式时间的最大流 的算法来计算妒( a ) ( 见1 2 】) ，从而求得d ( ) 2 3 拉格朗b 分解法 拉格朗日分解是一种特殊形式的拉格朗日松弛，它比拉格朗日松弛更复杂也更 难于计算，但是可以得到更好的上界通过增加一个相同的变量y ，问题( q k p ) 可 2 0 0 6 年上海大学硕士学位论文 9 以改写为： n m a x f ( x ) = q i i x i + q i j x l x j l = l l s i j n n s t n 。y sb ， i = 1 z = ， z o ，1 ) “， p o ，1 ) “ 用对偶乘子肛对偶化等式约束，得到拉格朗日分解函数： n f ( p ) = m a x 一胁) 戤+ q i j x i x j iz 0 ，1 ) n ) i = 1 l s i 蜥，0 ) ， 则z ；= 1 ，并将脚的值增至+ q i j 一直重复这一过程，直到没有这样的j 存在 这一过程称为p 一更新过程最后我们得到一个新的p 若初始的肛取a * a ，这里”表示( d ) 问题的最优解，则有： 定理2 3 4v ( d ) d ( a + ) 三f ( a + n ) e ( u ) v ( d d ) v ( q k p ) 证明： z ( r a ) = f 1 ( r a ) + e 2 ( a + a ) nn = m a x q i i x 。+ q i j z l x j r n i x i iz o ，1 n i = 1 l i j n i = l nn + m m x a 肛瑚i a i y i 6 ，y o ，1 h b 1 = 1 nn sm a x q i i 引十q l j x l x j a + ( 吼甄一b ) lz o ，1 ) n ) i = l 1 茎t j 茎n i = l = d ( r 1 由上面叙述可以设计如下的启发式算法来找一个比v ( d ) 更好的上界 程序2 ( ( d d ) 问题的启发式算法) 第1 步解拉格朗日松弛问题( d ) 获得最优解a + 令u b = d ( r ) ，k = 0 ，p = a * a 第2 步利用肛一更新过程计算p ，令p = p 第3 步解线性背包问题1 2 ( p ) ，令v 2 = f 2 ( 肛) 第4 步解二次背包问题p 1 ( p ) ，令v l = 1 ( p ) ，矿为g l ( p ) 的最优解 第5 步若u 1 + 口2 0 ，利用p 一更新过程修 改= 1 的分量对应的m ，否则令k ：= + 1 转第3 步 2 4 线性化方法 将( q k p ) 问题中的二次项x j 用新的o 1 变量z i j 替代，则毛z j = x i j 等价于 。玎她，x i j x j ，x i + q 一1 兰。莳，故原问题就转化为一个等价的0 - 1 线性整数规 划 p ) m a x f ( x ) = 蛳锄+ q l j x l x j i = 1 1 型q 9 s t a i x lsb ， z = 1 x i j 至x i ，1 i jsn ， 。巧墨z j ，1 i j n ， 戤+ q l 2 巧，1s i j 兰札， 吼 o ，1 ) ，i = 1 ，n ， x i j o ，1 ) ，1 i i 类似的还可以得到下面约束 + 。j + 。一z 诂一z j k 1 ，1 i n 将趴上两个新的约束代人( i l p ) 便可以得到如下线性规划 ( 工p ) m a x f ( z ) = q i i x i + q i j x l x j i = 1 1 1 t j s ” s t a i ：r i b ， i = 1 x i j 蔓戤，1s i j 他， x i j q ，1 i jsn ， z ? + 巧一1 sx l j ，1 i j 冬“ 0 5 x i 1 ，i = l ，n ， z 玎三0 ，1s i j 定义q l j = 吩，n - - - 次目标函数可以表示为 n 一 ，( z ) = ( q i l x i + ；eq i j x j ) x j i = 1 一j 定义z ( z ) = 圣lc ：c i ，其中q = q i l x i + j 却q i j x j 则有f ( z ) ，( z ) ，对所有 z ( o ，1 ) ” 另外也可以通过如最佳逼近来获得线性逼近函数f ( z ) ，也就是获得满足下列式 子的2 0 ( z ) ： i f ( z ) 一t q ( 。) 缘一俐2 z e o ，1 卜z e o ，1 p 下述引理【4 】说明最佳线性工z 逼近产生的q 与上述定义的q 是一致的 引理3 2 1 ，( z ) 的最佳线性工2 逼近产生的逼近函数t q ( x ) = c o + 冬l 臼劫，其中 c 。一；，募。蜘， 啦= 啦。孔+ ：q ，t = 1 ，n ，判 现在考虑如下线性逼近问题 此o _ l 线性背包问题可以运用下列两种贪婪算法得到理想的可行解贪婪算法是将 所有分量的“利益增量”按从大到小进行排序然后找出满足约束的前k 个“利益 增量”最大的分量，其所对应的值为1 ，其余分量的值为0 程序3 ( 求可行解贪婪算法1 ) 第1 步令k 1 = 1 ，2 ，n ) ，k o = 0 计算p i = c a i ，i = l ，2 ，一，n 妯。 觚 l m & 2 0 0 6 年上海大学硕士学位论文 1 7 第2 步如果 k 。毗b ，则托= i 若i k i ；甄= o 若i k o ，则z = ( z l ，) r 是( q p ) 的一个可行解，结束否则，选取k = a r g m i n p li g l ，令k l ：= k l k o ：= 硒u ” 第3 步对i 1 ，更新m ：= 以一( 1 2 ) q k i , 1 i 返回到第2 步 程序4 ( 求可行解贪婪算法2 ) 第1 步令k o = 1 ，2 ，一，n ) ，k 1 = 0 ，j = k o ，s = b 计算m = c i l a i ，i = 1 ，2 ，一，n 第2 步选取k = a r g m a x p l i n ，如果k 。u f k ) a i b ，令，：= 如果 ，= o ，转第4 步，否则重复第2 步如果谁k ，u ( 女 a l b ，则k 1 ：= k 1u 埘， k o ：= k o ) ，s ：= s a k 第3 步如果s b 一。，哪一x j a j ，则x k = 0 更新蜘，虬和飓并解相应的子问题设成为子问题的拉格朗日对偶界， 如果噶岛，令k 1 ：= k 1 u d ) ，k 2 ：= k 2 ) 若q = o ；令k o ：= k o u d ， k 2 ：= k 2 d 若x j = l 第4 步如果j c ，则令x o p - z ，印f ，( 矿) 如果a z + = b ，转 第7 步 第6 步对j 1 ( 2 ，计算预测系数丹= l ( x ，”) 一l ( y j ，”) ，其中鲥= z ；若 i j ，孵= 1 一z ；选取j = a r g m l n l e k 2p i ，令x j = l 一。；，m ：= m ud ) ，更 新k o ，k 1 和j ，2 ，返回到第2 步 第7 步在m 中从右向左寻找第一个不划线的指标j 如果没有这样的j ，停 止，z 。t 就是最优解否则，将m 中j 右边的所有指标都移到鲍中。令 x j ：= 1 一x j ，并将m 中的j 划线，更新硒，髓和鲍，转第2 步 第四章( m q k p ) 问题的分枝定界方法 本章给出了求解( m q k p ) 问题的一个新的分枝定界算法为了计算多约束问 题的对偶界，我们利用外逼近方法求解子问题的对偶问题拉格朗日松弛问题被转 化为最大流问题，并可用多项式时间算法求解为提高算法的收敛速度，我们用替 代约束和启发式算法搜索可行解 4 1( m q k p ) 问题的拉格朗日松弛和对偶搜索 考虑如下多约束二次o _ 1 背包问题： n ( m q k p )i n a x ，( 。) = q i i x l + q i j x i x j t ；l 1 1 i d ! “ s t ，a x sb ， 其中q l j 0 ，1 i j n ，a = ( o i j ) m n ，a l j 0 ，i = 1 ，- ，m ，j = 1 ，札 b = ( b 1 ，) t ，0 b i ” 肛 a n 皿 蚍 2 0 0 6 年上海大学硕士学位论文 2 3 令( 矿，廿) 表示( l r ) 的最优解 第2 步( 拉格朗日