（运筹学与控制论专业论文）非线性资源分配问题的分枝定界算法.pdf

2 0 0 4 年上海大学硕士学位论文 非线性资源分配问题是一类特殊而重要的整数规划问题，它可以定义 为在有限整数集上极小化一个可分离非线性函数的单约束( 可分离) 最优化 问题由于它在现实生活中有着十分广泛的应用，因此研究非线性资源分 配问题的算法就具有十分重要的现实意义本文所讨论的单约束非线性资 源分配问题可以表示为： “z 。乱：，z 。是整数， = 1 ，礼 这里对任意的i = 1 ，n ， ( 劫) 和9 ( 粕) 都是定义在实数集r 上的连 续可微函数，1 ，和蛳为整数，分别表示整数变量双的下界和上界，b 是常 数项不妨假设问题的可行域是有界非空的 本文主要讨论用分枝定界算法求解上述非线性资源分配问题，并把该 方法的计算效率和特点与拉格朗日对偶和区域分割方法以及0 1 线性化 方法进行比较首先，我们简单地介绍了非线性整数规划问题现有的一些 解法，以及求解凸资源分配问题的连续松弛闯题的乘子搜索法和p e g g i n g 算 法然后，我们介绍了求解整数规划问题的分枝定界算法，并且用分枝定界 算法求解了凸资源分配问题最后，我们讨论了凹资源分配问题的线性下 逼近和连续松弛的方法，在某些情况下，这样得到的松弛同题仍然能用乘 子搜索法或p e g g i n g 算法求解在此基础上，我们对分枝定界算法进行了修 改，并把乘子搜索法( 或p e g g i n g 算法) 与修改后的分枝定界算法相结合， 成功地求解了单约束的凹资源分配问题此外，我们还对来自实际应用中 的非线性资源分配问题进行了大量的数值实验 本文总共分为六章，其中第一章简单地介绍了非线性背包问题与整数 规划问题算法的研究现状和研究进展第二章主要讨论凸资源分配问舾连 续松弛后的两种不同解法第三章主要给出了整数规划问题分枝定界算法 的一般思想和几种求更好的可行解的启发式算法第四章主要研究如何用 线性下逼近方法和分枝定界算法求解凹资源分配问题第五章是我们的数 z 。 nm 6 b 成立 动态规划1 当所有的q 都是正整数时，令 t 坪0 ) = r a i n o 胁 k = 1 则我们有递归关系式： z 。) 7 b 2 只( j ) = r a i n 只一1 u q ) + a i ，只一1 ( j ) ) i = l ，2 ，n ，( i21 ) 这里，对任意的i = 1 ，2 ，一，n 和j = 1 ，2 ，定义毋( o ) = o ，当j q 0 时，定 义e ( j c 。) = + o 。 由( 1 2 1 ) 我们可以得到： f 1 ( 1 ) ，见( 1 ) ，r ( 1 ) ；n ( 2 ) ，f 2 ( 2 ) ，r ( 2 ) ； 当找到最大的j o 使得f n ( j o ) sb 成立时，算法就可以结束如就是问题( l k p ) 的 最优值，而它的最优解。= ( 。”。) 7 可以按下列方式得到： 一r 耄地“吼 当i = n 一1 ，- ，1 时， 、j0 当( j o ：h 】c k $ c k ) = 鼻一1 ( j 。? ；h i z ) 时 “一11 ，否妣 b 一 瓢 盘 毗 。 x眦 吨 如 z j = k卯 。 2 0 0 。1 年上海大学硕士学位论文 6 由上面的分析可知，该动态规划算法总的运行时闾为o ( ，。j o ) 动态规划2 当所有的啦和b 都是正整数时，令 对k = 1 ，2 n 和d = 0 1 一，b ，令 = c k + z k 一1 ( d a k ) 若( 1 2 2 ) 中的一个最优解中z k = o ，则 z k ) 7 b ) ， ， ( 1 2 2 ) d o ( 。1 ，。2 ，x k - 1 ) 丁b “一1 一l 叫。曼d ，( 吣1 ) 7 b “1 ) z k - 1 ( d ) i = 1 因此，对k = 2 ，3 t t 和d = 0 ，1 ，b ，我们有 引垆 裂h m ，喜删 如果当d 0 时，定义函( d ) = 0 ，当d 0 时，定义z k ( d ) = 一。e ，则对任意的 k = 1 ，2 ，一，n 和d = 0 1 ，b ， 磊( d ) = m a x ( z k i ( d ) ，c k + z k l ( d d k ) ) ( 1 2 - 3 ) 成立由递归关系( 123 ) 也可以得到问题( l k p ) 的最优值z 。( 6 ) ，它的最优解。= ( x l ，z 2 ，x n ) 7 可以这样确定： b 厂 。 现 b 一 z o 。 oc 。 【 心 = bz zzd 一 虬 ， 一 时 n d m q 纠 则 虮则 当否 = ， n 仉中，i解 | i 比 妨 最 盈 卟 且 铲 一二 中 引 = h 若 z ， ， 到 然 意 显 注 z z 岛 ( 雠n十 “ i | d 反 zc 觚 = d 级 2 0 0 4 年上海大学硕士学位论文 i0 ，当z n ( b ) = 磊一l ( b ) 时 i1 ，否则 当i = n 一1 ，l 时， z ：= j o ，当五( 6 一：= 件l n z ) = z i - 1 ( b 一：件1n z k ) 时， i1 ，否则 该动态规划算法总的运行时间为o ( n b ) 1 2 2 非线性背包问题的0 1 线性化算法 对于非线性资源分配问题( p ) ，当所有的 ( ) 都是单调非增的凸函数，所有 的g i ( ) 是单调非降的凸函数时，h o c h b a u m 在【1 3 】和m a t h u r 在 1 6 】中提出可以 通过等价变换把它变成0 1 线性背包问题因此，我们可以把问题( p ) 等价地变 换成0 1 缉i 生背包问题，然后再用动态规划算法或者分枝定界算法进行求解 若对任意的i = 1 ，2 ，n 和j = 1 ，2 ，一“，令 p o = ( k + j ) 一， ( f 。+ j 一1 ) ，w i j = 虮( h + j ) 一g i ( 1 t + j 1 ) ， 则问题( p ) 可以转化成如下的0 1 线性背包问题( k p ) ： n “- l i n ( p ) m i n p i j x i j + ( 2 ；) 显然，问题( k p ) 是0 1 线性背包问题，我们可以用分枝定界算法或动态规划方法 去解它，而且( p ) 的最优解z ；可以由( k p ) 的最优解z 0 表示，z ；= f t + 篙“。i ， i = 1n 1 2 3 非线性背包问题的拉格朗日对偶和区域分割方法 考虑非线性背包问题： n ( n k p ) m a x ，( z ) = ， ( 置) 2 = 1 s t g ( z ) = 玑( 蚴蔓b ， x 戈= 扛i f ：孔u ，x i 是整数i = 1 n ) 一 也 | i n ” j长麓 一 一 d l 6 ) ( i ) 若n _ ：j 和n 5 o 成立，则停止，a 就是( d ) 的最优解 舞 = h 2 0 0 4 年上海大学硕士学位论文 1 0 ( i i ) 若f ! o 且n l = o ，则选一个y n f ，使得g ( y ) = m c 啵如( ) i 口n f ) 成立令 瓜l = y ( y 。) 培。= 站， 9 4 1 = 9 ( 矿) ，9 + + l = 9 ， z + 1 ；一。+ 1 = ( 蚴若嘴= 叫n l o ，则选一个矿n 5 ，使得9 ( 矿) = m i n 9 ( 目) lg n 1 ) 成立并令 氟：= 庀，聪。= ，( 矿) ， 9 西1 = g i ，g 矗l = 9 ( 矿) ， 一+ 1 = 扩。+ 1 ；y s t e p4 ：= k + 1 转s t e p2 引理1 _ 2 1 拉格朗日对偶乘干搜索法能在有限步内求到拉格朗日对偶问题( d ) 的最 优解a + 为了便于叙述区域分割方法，当o l z ”，口z ”时，我们记h 纠= 扣| n 我觑，i = 1 ，n ) ，( 。，口) = 扣l 啦粕屁，x i 为整数，i = 1 ，n ) 并把区域 h 例上所有的整数点( a ，卢) 记为 ( n ，卢) = 坠1 ( a t ，屈) = ( o l ，卢1 ) x ( 0 2 ，应)x ( o n 阮) 特别地，当存在n 。 岛时，定义b ，硎= ( n 口) = o 由 和9 。在区间u i 】上都是单调非降的连续函数可知，( i ) 若。是问题 ( n k p ) 在区问l z ，叫上的可行解，则任意的i i j ，z 】有，( i ) s ，净) ( n ) 若y 是问题 ( n k p ) 在区间限“】上的不可行解，则任意的i u 】有9 ( 口) g ( f ) 因此，我们可 以把可行点左下角的点和不可行点右上角的点统统去掉 号l 理1 2 2 ( i ) 若五；( a ，卢) ，亩= q ，7 ) ，其中n z “、卢z ”、1 z “、 1 z ”，且2sa 1 卢，凡1 j i 亩= u 坠l ( j ( o k ，1 ) ( m + 1 ，岛) n 嚣： + l ( n k ，凤) ) ( 1 2 4 ) ( i i ) 若i = n ，p ) ，亩= ( 1 ，t t ) ，其中n z “、 卢z “、z “、z ”， 且o 。n 时，令x b = 卢， 。“= i ( 8 ) ； ( b ) 若n 是问题( p ) 的不可行解，则把( 。，_ 8 ) 割去； ( c ) 若m a 2 k 。 。，鄙l ( z ，妒) ，瓣，尉把 q p ) 割去 s t e p 且令k = k + 1 转s t e p l 定理1 2 1 由上述算法得到的拉格朗日对偶问题的最优值 驴( ”) ) 是单调下降的， 且上述算法能在有限步内求到非线性背包问题( k p ) 的最优解和最优值 证明。请参考【2 6 】 1 2 4 一般整数规划问题的分枝定界和动态规刘混合算法 考虑下面的一般整数规划问题： m a x i j ( x j ) s t 鲫( 码) b 。 j = l x j 岛、j = 1 ( 1 2 6 ) 其中s j = o ，1 ，a 3 是有限整数集，y j ( x j ) 是定义在s j 上的非降函数， j = 1 - 一，n 为了便于导出问题( 1 2 6 ) 的分枝定界和动态规划算法，我们先假设下列条件成 立： 抚0 ，1 i m ， 厶( ) 0 ，1sjsn ，z j 昌， 9 u ( z ，) 0 1 i m ，1 j 礼x j 岛 ( 1 _ 2 7 ) ( 1 2 8 ) ( 1 2 9 ) 2 0 0 4 年上海大学硕士学位论文1 3 令 最( 6 ) = 巧s ，1sj sk ，= 1 ，n ， ( 1 2 1 0 ) x 。表示问题( 1 2 i o ) 所有可行解组成的集合若存在。1 和x 2 x f 使得 kk 矗( 弓) 办( 司) j = 1j = 1 成立，且至少有一个不等式严格成立，则称一被z 1 占优如果z ，且。不 被任何x 。f 中的可行解占优，则称z 为的有效可行廨若把问题( 1 2 1 0 ) 的所 有有效可行解记为雄，问题( 1 2 ，6 ) 的所有有效可行解记为群，则糍可以通过 下面的关系来计算， 其中 x f x f x ? = s l ， 雄x o = 雄一1 s k ，k = 2 ，n 础= ( z 1 一，z ，x k ) ti ( z l ，z 2 ，。) t x 却t k 鼠) x f = 缸x 2i 鲫( q ) 茎也，扛1 ，m ) ， j = 1 鬣= z x f i 。是的有效可行解) 由有效可行解的定义可知，如果i 焉，且对任意的i = 1 ，2 ，n i ，譬1 ( 奶) = 6 。 成立，则i 就是问题( 1 2 6 ) 的最优解 求群的动态规划算法： s t e p1 令k = 1 ，x 2 = s 1 s t e p2 求x f ，即去掉x 2 中的不可行点 s t e p3 求雄，即去掉x f 中被占优的可行解 勺疗 。皿 耋苫m m1 = k 一 # 9 。同 ts 仃 = ； z j 吼 。州 一； z ， g 。州 2 0 0 4 年上海大学硕士学位论文 s t e p4 若k = n 停止否则，令k = k + 1 ，础= 磺l 瓯，转s t e p2 当该算法结束时就能求到碟，丽问题( 1 2 6 ) 的最优解满足 【司此，求x ：的动态规划算法实际上就是求解问题( 126 ) 的动态规划算法，上述求 解问题( 1 2 6 ) 的动态规划算法有一个缺陷就是：当变量个数7 9 , 很大时，霹可能会 包含太多的元素因此，可以用分枝定界算法的剪枝技巧来弥补这一缺陷 设。= ( x l ，x 2 ，一，z ) 7 雄，p = _ ；= 1 矿( q ) ，其中 ，( q ) = ( 9 1 j ( q ) ，9 2 j ( 。j ) ，蜘( ) ) 7 即芦表示到第阶段已消耗的资源，则第k 阶段的剩余问题定义为 n 瓦，( 6 一卢) = l a x 力( ) j = k + 1 假设u b 是问题( 1 2 6 ) 最优值的一个上界 z 雄是有效可行解，u b k + l 是p 的函数， 则当 ( 1 2 1 1 ) “是当前最优解的目标函数值 且对任意的0 s p b 满足 晟十l ( 6 一卢) u 。巩+ j ( 6 一口) 成立时，把z 从雄中删去不会丢掉问题( 12 6 ) 的最优解因此，如果令 碓= 。霹 x 2 = 雄 则我们可以得到求解问题( 1 2 6 ) 的如下算法 分枝定界和动态规划的混合算法： m2 i | 风 卢 一b + b u + ) ，j z 3 ( 疗 2。州k 2 0 0 4 年上海大学硕士学位论文 s t e pj 令k = 1 ，x p = s l ，u b = u b l ( b ) ，选e ( 0 ，1 ) ，l = l o 1 ，利用启 发式算法找一个好的可行饵作为当前最优解，并计算它的目标函数值血“若 u b = 。“停止 s t e p2 求碟，即去掉x 2 中的不可行点 s t e p3 求x ，即去掉x f 中被占优的可行勰， s t e p4 若i 雄i s 三，令x = 雄，转s t e p 9 s t e p5 求x ，使x 满足 k x z = z x l i 厶( q ) + u b + i ( b 一，( q ) ) s c ) j = lj = l s t e p6 求u b 和u b 7 ，使得 kk u b 7 = m a x ，j ( 如) + u b 。+ d b 一矿( 巧) ) 1z x ) j = lj = l u b = m i n u b ，u b ，) s t e p7 利用启发式算法找一个好的可行解，并更新当前最优值氐。t s t e p8 如果她旁鲁一 s ，停止当前最优解就可以作为最优解 s t e p9 若k = n ，停止，或者雄中存在一个可行解是最优解，或者当前最优解就 是最优解否则，令k = k + 1 ，x 2 = 雄一l s k ，转s t e p 2 一般地，上述u b k + 1 ( 6 一p ) 可以定义为： n u b k + 1 ( 6 一p ) = m a x 疗( q ) ( 1 ，2 1 2 ) 即当0 p b 时，问题( 121 2 ) 是问题( 1 2 1 0 ) 的连续松弛问题若在问题( 126 ) 中f a z j ) 和蛔( ) 都是线性函数，即疗( q ) = r j x i ，蚰( q ) = a l j x j ，则问题( 1 21 2 ) 是一个线性规划问题，它的对偶问题又可以写成： mn u b k + l ( 6 一仂= m i n u i ( b l = 1 m 随) + v j l 0 ( 1 2 1 3 ) j = k + 1 u l g i j + 码七+ 1 j s n 札0 1s i m 、 u ，0 + 1 曼js “ 一 = 一 鲰 m 啪 玛 “ 0 1 7 ( 2 1 2 ) ( 2 13 ) ( 2 14 ) ( 2 15 ) ( 2 16 ) ( 2 1 7 ) ( 2 18 ) ( 2 1 9 ) 订 n n n n n 1 1 1 i 1 | | 一一 = | | | | | l z z z z z 1 2 0 0 4 年上海大学硕士学位论文1 8 五( a ) s “， f i 黾( ) k - 毗( a ) ：” 函( 1 ) ( 2 1 1 2 ) l 一爿( “t ) 一a 鲥( ；) ，孟；( a ) “， 可以证明，对任意的a 0 由( 2 1 1 0 ) 、( 2 11 1 ) 、( 2 1 1 2 ) 给出的解( a ) 、u ( ) 、 撕( a ) 满足除( 2 1 1 ) 和( 21 4 ) 外所有的k k t 条件 定理2 1 1 对任意的 0 ，以( ) 、q ( ) 、i ( ) 满足k k t 条件俾j 甜 证明：( i ) 当i 。( a ) “时，由( 2 1 1 0 ) ，( 2 1 1 1 ) 、( 2 1 1 2 ) 知道x i ( a ) = f ，、 地( ) = 一( ) + 幻；( ) 、蛳( a ) = 0 ，因此 + 一饥+ 训。= 一( 如) + 9 ；( “) ( 一( f 。) + a “( 如) ) + 0 = 0 ， k k t 条件( 2 1 3 ) 成立 ( i i ) 当“ 磊( ) u i 时，( a ) = 磊( a ) 、q ( a ) = 0 、u ( ) = 0 ，因此 一+ a g ：一“+ 叫；= 一( 或( ) + a 9 ： i ( ) 一0 + 0 = 0 ， k k t 条件( 2 13 ) 成立 ( i i i ) 当。( a ) “；时同理可证综上所述定理成立 定理2 1 2 对任意的a 0 ，。( ) 、讪( a ) 、w ；( ) 满足k k t 条件俾1 印 证明：( i ) 当，( a ) k 时，由( 2 1 1 0 ) 、( 21 1 1 ) 、( 211 2 ) 知道2 。( a ) = b ，所以 v 。( 丑一“) = 0 ，k k t 条件( 2 1 - 5 ) 成立 ( i i ) 当 嚣( a ) 时，蛆( a ) = 0 ，因此q ( 孔一z ，) = 0 ，即k k t 条件( 2 1 5 ) 成立 综上所述定理成立 定理2 1 3 对任意的a 0 ，矗( a ) 、 证明：具体证明方法同上 定理2 1 4 对任意的 0 ，嗣( ) 、 “( a ) 、 。( ) 满足k k t 条件阳1 鲫 “( ) 、 ：( a ) 满足k k t 条件偿j7 j 令 u 觚 k 氧吨的，l?l o = f i ” 吲 烈 + 程方示表 x 两没 2 0 0 4 年上海大学硕士学位论文 证明：( i ) 当函( a ) z 。时，由( 2 1 1 1 ) 得q ( ) = 一( f 。) + a 反( “) ，由于k ( x 。) 和 g i ( x i ) 都是凸函数，所以爿与毹是单调递增的， u 。n ) = f i ( 1 i ) + a 鲥( “) ( i ( a ) ) + “( 磊( ) ) = 0 所以k k t 条件( 2 1 7 ) 成立 ( i i ) 当k 0 。由k k t 条件( 2 1 4 ) 知道 n f g d x ，( ) ) = 6( 2 11 3 ) t = 1 成立首先，解方程爿( 孔) + 口：( 矗) = 0 ( i = 1 ，2 ，n ) 情形1 ：假设所得到的解噩能写成a 的显式表达式，即磊= a ，则可 以将矗( a ) 代入( 2i 1 0 ) 计算：r i ( a ) ，然后，由( 2 1 1 3 ) 求出拉格朗日乘子a 再 根据( 2 1 1 0 ) 计算( c p ) 的最优解z ：( a ) 由于( 2 1 1 3 ) 是关于a 的非线性方程可 以用二分法、迭代法、牛顿法等很多方法求解 情形2 ：假设所得到的解孔不能写成a 的显式表达式，就只好用数值解法 对于任意非负的a = ”，由一( 孔) + a g ( x 1 ) = 0 可以计算出2 。( ”) 和托( ”) ，然 后，将( a + ) 代入( 2 11 3 ) 左端，如果( 2 1 1 3 ) 成立，则( c p ) 的最优解为x i ( + ) 在许多实际问题中，约束函数矾( ) 往往具有某种单调性，而且方程( ) + 磁( 。) = 0 的解氟能写成 的显式表达式因此，用乘子搜索法解连续松弛问题 ( c p ) 就容易多了 2 0 0 4 年上海大学硕士学位论文 例2 1 1 用乘子搜索法求解下面问题的连续松弛问题 m i l l ( 。；+ 6 m ) l = l s t c i x i d ， t = l l 。s 戤曼，甄是整数变量，i = 1 ，n 其中a i 、机、q 都是正数，d 是常数，而且假设问题的可行域非空 s t e p1 令a = 0 ，解( 劫) = 0 ，即2 a i x i + b i = 0 ，得到疵( a ) = 一且2 a l ，将黾( ) 代 入( 2 1 1 0 ) 计算却( ) ： | 2 ， 孔( a ) = 一矗 i 一是s “， “ 一基 0 ，由k k t 条件( 2 1 4 ) 知道 n e i z i ( a ) = d ( 2 1 1 4 ) = 1 成立首先，解方程一( q ) + a 彬( 孔) = 0 ，即2 a i x + 6 f + a c i = 0 所得到的解x i 能 写成a 的显式表达式，即函( ) = 一丝2 a 盐l ，计算霸( ) ： a 曼二呈警二h ， 半 0 ，解方程一+ , k g ：= 0 ，不妨设所得 到的解为磊( a ) ，利用( 2 1 1 0 ) 计算蛳( a ) ，如果g ( a ) ! b 则a = 0 ，x c = ( x l ( ”) ，z 2 ( ”) ，z 。( ”) ) 就是( c p ) 的最优解，停止否则a 0 转s t e p2 s t e p2 令k = 1 ，1 = 1 ，2 、m ，l 1 = o ，u 1 = 0 s t e p3 解松弛问题( r p ) ，假设解是x 。= ( 。f ，z 1 - ，z ：) s t e p4 把x 中不满足约束“兰。? 曼的变量找出来，并计算破、鸡、戡、 碴，如果破= o 和玷= 口成立，则转s t e p 最 s t e p5 。如果硝s a ，则令i 1 = ，一破，u “1 = u 。u 破，l 抖1 一l ；如果 s g s 盖，盟0 令i + 1 = j 一碹，l + 1 = l u ，各，u + 1 = u ，转s t e p 童 0 脚彬 渺卜 ， 基f 彬 彬卜 + i | z 茁 吼 时舻 2 0 0 4 年上海大学硕士学位论文 吼印6 求问题( c p ) 的最优解x 。，对所有的i n 计算 f “，i 驴， z 净 z ；，i p ， ( 2 _ 2 2 0 ) 【t 泸 对于情形( i i ) ，只需将s t e p5 改为下面的s t e p5 7 即可 s t e p5 7 如果璐破，则令，+ 1 = p 一咭，l + 1 = l u 咭，u 抖1 = u ，如果 璐 s ，则令，+ 1 = j 一砖，u + 1 = u 。u 珐， l + 1 = 胪，转 s t e p 只 如果方程一+ 吲= 0 的解毛能写成显式表达式磊= 磊( ) ，则由p e g g i n g 算法 可知，在每次迭代中至少可以固定一个变量，因此，最多经过”次迭代就能求到连 续松弛问题的最优解至于该算法可行性与合理性的证明清参考阱 假如p e g g i n g 算法经过护步迭代停止，即( c p ”) 的解x ”= ( z nz 扎，z ：+ ) 满足2 x ! “令 - “一描，ie i k gj t t ， ( 2 22 1 ) ( 2 2 2 2 ) 州胪删呐触a 涎篡o ( 2 22 3 ) 10 ，i ，”u u ”- 酬： o涎p j 山”， ( 2 22 4 ) 4 i 一一( “t ) 一1 9 ：( n f ) ， u 。， 定理2 2 1 在情形例一计的条件下，由( 2 2 2 1 ) - - ( 2 2 2 4 ) 给出的解满足k k t 条件 ( 2 1 3 ) 。 证明：( i ) 若i 驴则有噩= f ：，妒= 一象翁，”- f ，, ( 1 k ) + ”或( 2 ) ，蚴= o ， 即( ) + 舻目。le ，k ) ( 爿( ) + 小+ “( ) ) + 0 = 0 满足k k t 条件( 2 1 3 ) ( i i ) 若 u 护，则有戤= a k = 一黼，驴o ，哪= 一( u ；) 一舻g 埘+ ) ， 沙m ? 忡 1 1 0 k ，rjr、l 2 0 0 4 年上海大学硕士学位论文 即一( u ? ) + a k 疵( “? ) + 0 + ( 一州tu ：k ) 一 ”9 知。k ) ) + 0 = 0 满足k k t 条件( 2 1 3 ) ( i i i ) 若i ，”，则有爿( z ；) + h k 9 ：( 。? ) 条件( 2 1 3 ) 满足 定理2 2 2 在情形俐r i 妙的条件下，由 ( 21 5 ) 和( 2 , 1 6 ) 证明：与定理( 2 1 2 ) 的证明类似 0 满足k k t 条件( 2 1 3 ) 综上所述k k t ( 2 2 2 1 ) - - ( 2 22 4 ) 给出的解满足k k t 条件 定理2 2 3 由( 2 2 2 1 ) - - ( 2 2 2 4 ) 给出的解满足k k t 条件( 217 ) 和( 21 8 ) 证明：请参考【2 】的相关部分 定理2 2 4 在情形俐o i ) 的条件下，由( 2 2 2 1 ) 一( 2 2 2 4 ) 给出的解满足k k t 条件 ( 2 1 ) 0 、 证明：对所有的i i 有一( z ) + 小9 。t q k ) = 0 ，即”= 一考写，k = 1 ，2 ，k + 在 情形( i ) 的条件下，有 ( 乩) 单调上升和乳( 戤) 单调下降，即( ) 0 、( 翰) o ，j = 1 ，- 一，n ) ， 扩哪搿 鬻，卜1 ( 3 。) 其中e ，黔表示第j 个分量为1 ，其它分量为0 的单位向量 h e u r i s t i ca ( 当m ( ) 单调递增时) s t e p1 令矿表示松弛同题的最优解现在对矿向下取整，即令z = 【矿j ，则z 就 是一个可行解 s t e p2 如果存在j o 1 ，n ) 使得( 3 , 2 1 ) 成立，令x = x + e y 。，否则，停止 s t e p 乱转s t e p 2 如果吼( ) 单调下降且z 是一个可行解，则( 3 , 2 1 ) 可以改为 一。= a r g 搿 鬻渊z 刊a ) ，慨。， 其中g = ix j 一1 0 ，f j ( z j ) 一y j ( = j 一1 ) 0 ，j = 1 ，n ) h e u r i s t i cb ( 当9 i ( z 。) 单调下降时) s t e p1 设。+ 是松弛问题的最优解，对r 向上取整，令。= 陋1 ，则x 是一个可行 解 s t e p2 如果存在j o t 1 ，n ，使得( 3 2 2 ) 成立，令z = x e j o ，否则，停止 s t e p 只转s t e p2 例3 2 1 求解下面的凸资源分配问题： m i n ，( 。) ：妻( ；螂；“) t = l 3 s t 9 ( z ) = q q d ， l ；1 x x = 扣孔曼。是整数，i = 1 ，3 ) 2 0 0 4 年上海大学硕士学位论文 其中 a = ( 2 0 0 0 4 ，1 6 2 6 5 8 ，1 0 2 3 9 6 ) 。 c = ( 2 3 8 5 1 4 82 0 8 2 ，1 09 9 0 4 ) 7 “= ( 5 ，5 ，5 ) 1 ，d = 1 6 35 9 0 2 b = ( 6 3 4 1 3 ，8 02 8 6 5 ，3 8 8 6 9 7 ) 7 k ( 1 ，1 ，1 ) 7 ， 该问题的最优解是x = ( 3 ，5 ，4 ) 7 ，最优值为f ( z + ) = 一2 8 1 6 9 用分枝定界算法解该 问题是从解第一个子问题( p 1 ) 的连续松弛问题开始的由乘子搜索法可得( 只) 的 连续松弛问题的最优解为= ( 3 1 7 0 1 ，49 3 5 9 ，3 7 9 6 0 ) 7 ，最优值为丘= 一2 8 89 7 ，用启 发式算法h e u r i s t i ca 可得当前最优解的目标函数值为 。n = 一2 8 1 6 9 由于松弛 问题的最优解不是整数解，选取值离整数最远的变量。3 为分枝变量将( p 1 ) 分为两 个子问题( p 2 ) 和( p 3 ) 接下来按深度优先搜索的方法选左边的一枝( p 2 ) 为分枝结 点，并解它的连续松弛问题，从连续松弛问题的最优值厶= 一2 7 8 7 3 。“可知， 最优解不会在这一枝出现，可以将其剪去然后，再从问题集中选一个下界最小的 子问题( p 3 ) 来解它的连续松弛同题从分枝定界示意图3 1 可知，( 忍) 的连续松弛 问题的解仍然不是整数解，因此，还要继续分技，接下来按深度优先选左边的一枝 ( 只) 解它的连续松弛问题一直这样做下去，直到出现下列情形为止： ( i ) 子问题的下界比原问题最优值的上界亿“要大，如( 忍) 、( p 5 ) 和( p 6 ) ； ( i i ) 子问题的连续松弛问题的解是整数解，如( p 7 ) ； ) 子问题不可行 如果所选的子问题出现上面三种情形之一，就将该子问题删除，并从未解的子问题 中选下界最小的子问题解它的连续松弛问题当所有的问题都已经解过，或者剪枝 后问题集为空集时，算法就可以结束当前最优解就是原问题的最优解从分枝定 界的示意图31 中可知，只要解7 个子问题的连续松弛问题，就能求到最优解为 。+ = ( 3 ，5 ，4 ) 7 ，最优值为，( 矿) = 一2 8 16 9 在分枝定界的示意图3 1 中 数字1 2 ，一，7 表示所解子问题的序号； t b u b 表示所对应子闫题的下界和上界； z 表示连续松弛问题的最优解； 厶表示连续松弛问题的最优值； 。表示当前最优解x b 。的目标函数值， 2 0 0 4 年上海大学硕士学位论文 3 0 1 b = ( 1 1 i ) u b = ( 5 ，5 5 ) ( 31 7 0 1 ，49 3 5 9 ，37 9 6 0 ) ( - 2 8 89 7 2 8 16 9 一矗口 ( 3 4 ，4 ) ：一2 7 46 0 ，- 2 8 1 6 9 ) ( 3 ，5 ，4 ) - 2 8 16 9 - 2 8 l6 9 ) 图3 1 ：例3 2 1 的示意图 第四章凹非线性资源分配问题的算法 对于凹非线性资源分配问题( p ) ，由于所有的，i ( 戤) 是凹函数，所有的或( ) 是凸函数，因此问题( p ) 的连续松弛问题不能直接用乘子搜索法和p e g g i n g 算法求 解，在本章我们主要讨论对凹资源分配问题取线性下逼近和连续松弛的分枝定界算 法 4 1 线性下逼近方法 凹资源分配问蹶( p ) 的子问题( s b p ) 可以表示为 ( s b p )r a i n ，( ) = f i ( z i ) i = 1 s t g ( x = ) 吼( 毛) b ， 黾戤“，戤是整数，i = 1 ，。，n 其中。；、是整数且满足1 。茎乳t i ”子问题( s b p ) 取线性下逼近后的连续松 弛问题( l p r ) 可以表示为： ( l r 尸)工( z ) = 厶( 而) g ( ) = 9 。( 训曼b ， 5 i z ：“，i = 1 ，一，“ 这里姚是实变量，s 。和是整数且满足“曼s 。st i 曼m 如( 研) 是对 ( 如) 取线性 下逼近得到的线性函数，即厶( 训= o m + 扇，且当s ， l ( x 。) ，则选一 个上界和下界不相等的变量q 。( s j 。z j 。st j ，) 为分枝变量，分别将约束x j ，b ；，j 和约束x j ，iz ；，l + 1 加到子问题( s b p ) 的约束中去，从而产生两个新的整数规划 问题否则，至少存在一个变量z ，。取分数值，这时就以x j 。为分枝变量，分别将 约束x j 。【z 是j 和约束x j 。b 乞j + 1 加到子问题( s b p ) 的约束中去，从而产生两 个新的整数规划问题然后和凸资源分配问题的分枝定界算法一样，再从这两个子 问题中选一个解它的松弛问题( l r p ) ，如果得到的解是整数勰就把它和当前最优 解比较，如果该整数解更好就更新当前最优解和当前最优值如果松弛问题的最优 解还是子问题的最优解，则该子问题就不再分枝否则，不管所得到的解是整数解 还是分数解都得继续分枝一直这样做下去，直到所有的子问题都已经解过，或者 剩下的子问题都不可行为止为了防止子问题数目增加过快，我们必须把已经解过 的子问题和出现下列情形之一的予问题从问题集中删去( 剪枝) ( i ) 子问题不可 行；( i i ) 子问题的下界比原始问题最优值的上界氐。要大；( i i i ) 子问题和松弛问题 ( l r p ) 的最优值相等如果剪枝后问题集为空集，或者当j 。n 一， 。 ss 时，算法 就可以结束，当前最优解( z