（应用数学专业论文）多个约束变为一个约束的整数规划问题的新算法.pdf

多个约束变为一个约束的整数规划问题的新算法 一 v9 8 7 2 2 摘要 本文将抽象代数中循环群的理论引入至整数线性规划问题( 下面简记为 i l p 问题) 将多个约束变量的p 问题转化为一个约束条件的背包问题同时提 出了求解背包的改进方案全文共分三章 第一章介绍了整数规划问题产生的背景及当前的主流算法第二章提出了求 解i l p 问题的新算法，并对新算法中的关键问题给出了证明第三章对具体问题进 行了数值实验，进一步从实例上验证了该算法的可行性并提出了新算法的改进方 向 关键词：i l p 问题，取整，背包问题，循环群，次优解 江西师范大学2 0 0 6 届硕十研究生学位论文 a b s t r a c t i nt h i sp a p e r m ea u t h o ri n t r o d u c e st h et h e o r yo fc y c y l i cg r o u pi n t oi m e g e rl i n e a r p r o g r a m m i n g ( i l p ) p r o b l 锄i h n s f e rt t l em u l t i p l ec o n s t m i n t s jp r o b l e mi n t oo n e d i m e n s i o nk n a p s a c kp r o b l 啪ni n d u d e s f o u o w i gt h r e ec h a p t e r s i nc h a p t e r1 ，a u t h o ri n t r o d u c e st h eb a c k g r o u n do f 出ei l pp r o b l e ma n dt h e c u r r e n ta l g o r i t l l i l la tn a w i nc h a p t e r2 ，p r o p o s et h en e wa l g o r i t h mf o rs o l v i n gt h ei l p p r o b l e m ，a n dp r o v e st h ec a r d i n a lp r o b l e m so ft h en e wa l g 硎t h m h lc h a p t e r3 ，a u t l l o r m a k e sm a t h e m a t i c a lc h e c kf o rc o n c r e t ep r o b l e m s ，p m v e st h e f c a s i b i l i t yo fn e w a l g c 盯i t l l l l l a dp r o p o s et h em o d i f i e dm e t h o df o rn e wa l g o r i t m n k e yw o r d ：i l pp r o b l e m ，f e t c h 丘a c t i o n ，| 【i l a p s a c kp r o b l e m ，r e l a x e dp r o b l e m ，c y c l i c g r o u p ，s u b o p t i m u m 2 第一章预备知识 1 1 引言 整数规划( i n t e g e rp r o g r a m m i n g 简记i p ) 是近四十多年来发展起来的规划 论的一个分支整数规划是要求决策变量取整数值的线性或非线性规划问题 它是在凸区间内部或边界上的某些离散的点上寻找最优整数解本文将着重讨 论整数线性规划( i i l t e g e r u n e a r p r 0 謦a m m i n g 筒记口l p ) 问题 1 9 5 8 年g o m o r y 提出了割平面法及随后k m d d o i l ；等人提出的分枝定界法 为整数线性规划的解法奠定了基础至今，我们求解i l p 问题通常采用的是分 枝定界法或是分枝定界法与割平面法这两种方法的结合然而这两种算法的收 敛速度都较为缓慢，求得最优解往往需要花费大量的时问，求解方法难以令人 满意这在一定程度上制约了p 问题在实际中的应用 近年来国内外不少科研工作者都对求解i 廿问题的算法进行了深入的研 究，但并没有令人满意的新算法出现所做的工作不过是对这两种经典算法的 补充或结合多年来，求解p 问题的方法并没有得到实质性的进展 本文利用i 问题对应的l p 问题的最优解中等式二边分数部分必须相等 的重要特性，对l p 问题的最优表中约束条件的系数的去整( 目标函数除外) ， 则整数可行解代入式中等式两边分数部分相等是此整数解可行的必要条件再 利用各约束条件中各列系数去整后组成一个定义循环群子集的特性，将多个约 束条件的i l p 问题转化成为一个约束条件的j 问题( 即一维的背包问题) 通 过求解背包问题，得到在放弃松驰变量的符号约束下的一个或多个可行解然 后找出其中对应目标函数值最大的原问题的可行解，从而得到原问题的撮优整 数解 经反复数值实验，此方法在绝大多数情况下能提高i l p 问题的求解速度， 其复杂程度及计算量远低于分枝定界法是求解i l p 问题的一种新的行之有效 的算法 另外，本文在求解一维背包问题时引入贪心算法，提高了求解背包问题的 效率 兰尘丝塞銮塑二全丝壅鲍墼塑塑型塑墅盟堑蔓鎏 1 2 分枝定界法简介及其改进 一、分枝定界法简介 分枝定界法可用于全整数线性规划、混合整数线性规划问题和o 一1 规划问 题下面我们用一个例子来介绍这种方法 例：求下面皿p 问题的最优解： m i n 厂= 一为一5 工2 1 一x 2 一2 ( 甄) 5 墨箸3 。 l t 、o ，t 、x 2 整数 解：我们将上面的问题记作问题( 如) 为了求出它的最优解，我们首先去 掉整数约束条件，得到问题： m l n ，2 一一5 f 鼍一z 2 一2 ( 峨) 5 _ 箸3 。 【_ 、工2 o 整数 并将问题( 戤) 称为( ) 的松驰问题显然，问题( 砜) 的任何一个可行解一 定是问题( 瑶) 的可行解 我们首先利用单纯形方法求得松驰问题的最优解求之得：五：坚， 2 署对应的目标函数值为矗= 一箬这是问题( 巩) 喇一 个下界 因为问题( 瓯) 的最优解不为整数值而在问题( 见。) 中葺必须取整数，所 江两师范大学2 0 0 6 届硕士研究生学位论文 以葺必须取小于等于1 或大于等于2 的整数值利用这一明显的结果，我们可 以把问题( 如) 划分为两个子问题： m i n ，= 一一5 屯 一x 2 一2 5 十缸2s3 0 墨s 4 s 1 五、z 2 0 ，、z 2 整数 m i n 厂一一一5 工2 五一砭一2 5 墨+ 3 0 s 4 薯2 邓工2 苫0 ，郦t 整数 这样划分，并未丢掉问题( z l 0 ) 的任何一个可行解这一过程，我们称为分 謦- i 三臻观，我们用树形图来表示这一分枝过程，这个树形图称之为枚举树 ( 见下图) 要求问题( 砜) 的最优解，只要分别求出子问题( 皿) 和子问题( 乜2 ) 的最 优解即可 对于子问题( 皿) ，我们可求出其对应的p 问题的最优解为： 薯。1 ，恐23 ，对应目标函数值为：五= 一1 6 由于两个变量都为整数，这 已经是予问题( 皿) 的最优解，这个可行解称为活点这时称子问题( 玛) 已被 多个约束变为一个约束的整数规划问题的新算法 探明，不必继续分枝了在树形图上扪上记号“# ”，表不于】叫题已珠明 同时，子问题( 皿) 的最优解也是原问题( 如) 的可行解因此，子问题 ( 皿) 的最优值是原问题的目标函数值的一个上界，记z = = 一1 6 如果能 求得原整数规划问题的上界，则称之为定界 我们再考虑子问题( 见2 ) ，类似地，先求解其松驰问题( 嗄) 松驰问题 ( 鹏) 的最优解为：_ = 2 ，z ：= ! 孚，对应目标函数值为：，2 = 一1 8 吾因为 ，2 小于现有的上界一1 6 ，所以原问题可能有比一1 6 更小的最优值 因为x 2 ：掣不是整数，利用3 s 婴蔓4 ，我们可以在子问题( 见2 ) 中分别加入 气气 、7 约束条件恐s 3 或z ：4 ，就把子问题( 肛2 ) 划分为子问题( 如) 和( 皿。) ： m i n ，= 一五一5 x 2 置一屯一2 5 t + 6 3 0 2s s4 屯s3 葺、x 2 0 ，、戈2 整数 m i n ，= 一葺一5 x 2 一x 2 一2 5 + 6 也s 3 0 2s s4 x 2 4 、工2 0 ，、x 2 整数 子问题( 如) 对应的松驰问题的最优解为：一2 2 詈，屯2 3 ，对应目标 函数值为：，2 = 一1 7 詈仍小于现有上界同时_ 22 詈不是整数，所以必须 7 )， 江西师范大学2 0 0 6 届硕士研究生学位论文 将问题( 如) 继续分枝利用2 s 娶s 3 ，我们可以将_ s 2 和而3 分别加 入子问题( 如) 的约束条件中去，得到子问题( 以) 和子问题( 玩) 在求解子问题( 如) 的同时对子问题( 如) 进行求解结果我们发现其对 应的松驰问题无可行解，当然子问题( 巩) 也无可行解，则子问题( z 己4 ) 也已 探明 m i n ，= 一一5 x 2 一石2 一2 5 + 鸣s 3 0 2 s 4 鼍2 x 2s3 【_ 、z 2 o ，五、戈2 整数 m i n ，= 一鼍一5 2 2 鼍一镌一2 5 墨+ 舐2 3 0 2 五s4 置3 艺s 3 耶z 2 0 ，邙整数 这一分枝过程可以用下面的枚举树表示： 8 多个约束变为一个约束的整数规划问题的新算法 子问题( 如) 对应的松驰问题的最优解为：五= 2 ，= 3 ，对应目标函数 值为：，5 = 一1 7 显然这是子问题( 如) 的可行解因此子问题( 如) 已被探 明，同时兀；一1 7 小于现有上界一1 6 ，可重新定界z ；六；一1 7 再考虑子问题( 玩) ，其对应的松驰问题松驰问题的最优解为： 五= 3 ，z ：= 2 丢，对应目标函数值为：丘= 一1 5 丢五是子问题( 玩) 的最 小值的下界但，6 z = 一1 7 ，所以即使将予问题( 玩) 分枝，其子问题也决 不会小于( 一1 5 三) 这时，子问题( 玩) 也已探明我们称子问题( 玩) 被剪枝 至此，所有的子问题都已经探明，求解结束原问题( 砜) 的最优解为： = 2 ，= 3 ，最小值为：，= ，5 = 一1 7 。整个的求解过程用枚举树表示如 下图： 江西师范人学2 0 0 6 届硕士研究生学位论文 掸桦 利用分枝定界法求解全整数线性规划问题应注意以下几点： ( 1 ) 松驰问题的选择我们把整数约束去掉阻后，得到松驰问题，这是一 个普通的线性规划问题，可以用单纯形方法求解在求解原整数规划或其子 问题时，我们都是求解其松驰问题 ( 2 ) 分枝规划如果某个松驰问题的最优解全取整数值，则它对应的整数 规划就已探明否则，如果某变量以取分数值口，则求得不超过口的最大 整数和大于a 的最小整数a 2 ，分别将甄s 口1 和芑口2 添加到该皿p 的约束条件中，就可将此尼p 问题分枝为两个子问题 ( 3 ) 定界方法如果某个子问题的最优解( 整数) 已经求得，这一最优解 是原尼p 问题的可行解因此，它对应的目标函数值是原整数规划问题最 优值的上界，其值记为z 每求得一个子问题的最优值之后，都应与现有上 界比较，取其中较小者作为新的上界 子问题探明的判定当我们求解某子问题的松驰问题时，只要出现下述 情况之一，该子问题就己探明： ( 1 ) 松驰问题没有可行解，则原子问题也没有可行解； ( 2 ) 松驰问题的最优解恰好全取整数值，则该最优解也是其对应的子问题的 最优解： 1 0 多个约束变为一个约束的整数规划问题的新算法 ( 3 ) 松驰问题的最小值大于现有的上界z ，则无论其最优解是否取整数值， 都将对应的子问题剪枝 已探明的子问题就不用再分枝了，如果所有的子问题都已经探明，则原整 数规划的最优解就一定可以求出，或可以判定它无解 二、分枝定界法的改进( 以下假定目标函数求m a x ) 我们在前面给出的分枝定界算法，分枝后得到的子问题还是比较多的，我 们可以进行改造，得到更有效的分枝、划分与定界的方法 ( 一) 分枝策略 有两种分枝策略可以采用 第一、为了简化在计算机内对于表的搜索，向新的活点进行分枝比较有利 第二、将，的所有后代顶点的上界都求出来，向上界最大的后代顶点v i 进 行分枝因为一旦，f 的最优解是整数解，则其他的后代点都可以剪枝( 1 1 ) ( 二) 计算较好的界 1 、假设给出了枚举树的某个松驰问题的顶点的相应典式为： 一_ y o o 一荟r 磊“， 吨p 。铋。一荟_ 一渺“， l即“户。 如果薯。= 咒。 + 五。不是整数， 表1 增加约束薯s 咒。 ，让t 出基， 式确定： 即0 正o 1 ，则对葺进行分枝，对 出基后取上界值 y i o ，进基变量由下 m i n 晋( 詈，驴0 ) ，爱尝嘞 0 ) ，曾皆，) ， 啪z 。 猁 称d f _ m i n 曾尝妒o ) ，呀皆嘞 o ，_ r 茸鸲 0 ) ，警皆， = d 。，则首先向毛芑 y ；。 + 1 分技； 如果m 9 x d f ，u = 眈，则首先向一s 【) ，i oj 分枝 ( 四) 简单约束的划分 如果存在简单约束荟碗2 1 在枚举树的顶点_ 处需要划分时，我们 考虑q 的任一划分q = ( q 1 ，q 2 ) 而令： 耻s ，n i 荟墨2 1 ) 书，n l 荟五2 1 ) 如果我们选用基数近似相等的q 1 ，q 2 可能更好些 多个约束变为一个约束的整数规划闷望笪堑笺鲨 1 3 在紧约束下求解一维背包问题的贪心算法 一、背包问题简介 有一个人带一背包上山，其可携带物品重量的限度为口千克。设有以种物 品可供选择，其编号分别为1 ，2 ，n ，已知第f 种物品每件重彬千克。上山 过程中的作用价值为e 件，问此人应如何选择携带物品，使总作用价值最大。 这就是著名的背包问题，其可应用在货物运输、人造卫星内物品的装载等。 设置为第f 种物品装入的件数，则问题的数学模型为： m a x ，2 c j 墨 善彬墨s 口( 彬0 ) l 墨o 且为整数( f = 1 ，2 ，1 ) 若问题的“”变为“= ”，则此问题变为紧约束的背包问题，则模型变 为： m a x 厂2 g 置 j荟联置= 口( 彬o ) l x f o 且为整数( i = 1 ，2 ，1 ) 此问题的求解通常采用动态规划的方法，计算量较大，这里引入贪心算 法，将二种方法结合，以提高求解效率。 二、贪心算法简介 第f 种物品重量为彬千克件，其作用价值为c f 件，故第z 种物品的单 位作用价值为【q 嘶j 千克。由于物品总重量必须为口千克，要使作用价值最大， 根据“贪心算法”，我们就应优先选择单位重量作用价值最大的物品，然后再考 虑单位作用价值次大的物品，只有这样才最有可能使总的作用价值最大。 贪心算法的基本思想是从局部的最优出发，即：首先让作用价值最大的 物品尽可能的多放，然后再考虑作用价值次大的物品，以此类推若此时无整 数可行解，则将作用价值次大的物品减少一件，再来考虑问题的最优解如此 反复，直至求出最优解该算法的特点是：简单而快捷，特别当问题的最优解 扛西师范大学2 0 0 6 届硕士研究生学位论文 只能用穷举法得到时，用贪心法是寻找问题最优解的较好算法 本文的算法对贪心法进行了改进并引入了分级处理方法对求解步骤进 行分解，每次利用贪心算法都是一步一步地进行根据某个优化测度( 可能是 目标函数，也可能不是目标函数) ，每一步都要保证能获得局部最优解每一步 只考虑一个数据，它的选取应满足局部优化条件若下一个数据与部分最优解 连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚 举完，或者不能再添加时为止这是能够得到某种度量意义下的最优解的分级 处理的贪心法 选择能产生问题最优解的最优度量标准是使用贪心算法的核心问题 假定有甩个物体和一个背包，物体i 有质量彬千克，价值为c ，而背包的 载荷能力为m 若将物体f 的一部分置( 1 f s 甩，0 s z 。s 1 ) 装入背包中， 则有价值c f 玉。在约束条件( 瞩墨+ 孔+ + 形以) s 肘下使目标 c 。置+ c 2 置+ e 以达到极大，此处o s 置s 1 ，g ) o ，1 i s 门这个问题称 为背包问题( k n a p s a c kp r o b l e m ) 要想得到最优解，就要在效益增长和背包容量消耗两者之间寻找平衡。 也就是说，总应该把那些单位效益最高的物体先放入背包。 在寻找最优度量标准时，大致方向是用冒泡排序算法也就是根据c 彬 的大小来对彬来排序 例1 ： m a ) ( 厂= 4 墨+ 5 x 2 + 锻3 + 7 x 4 f 3 x 1 + 4 x 2 + 5 j r 3 + 6 x 4 = 1 7 i 墨o 且为整数( f = 1 ，2 ，3 ，4 ) 解：首先对c f 彬进行排序得：c 1 啊，c 2 ，g ，c 4 彤 故令墨一f 警1 = 5 ，则问题变为： m a x 六一2 0 + 5 x 2 + 6 墨+ 7 2 4 f4 x 2 + 5 x 3 + 6 x 4 = 2 i 置o 且为整数( f = 2 ，3 ，4 ) 此时无可行解 令置= 4 ，问题变为： 多个约束变为一个约束的整数规划问题的新算法 m a x 厶= 1 6 + 5 胃r 2 + 6 丑r 3 + 7 x 4 f4 x 2 + 5 x 3 + 6 x 4 = 5 i 鼍o 且为整数( f = 2 ，3 ，4 ) 此时的最优解为：墨= 4 ，盖：t 0 ，蜀= 1 ，工。= o 此时对应的最优值为： 厶= 2 2 ，这是求解过程中求出的第一组可行解，令，8 = ，2 = 2 2 令x 。= 3 ，问题变为： m a x = 1 2 + 5 x 2 + 6 x 3 + 7 x 4 f4 x 2 + 5 x 3 + 6 x 4 = 8 1 置o 且为整数( f = 2 ，3 ，4 ) 若去掉对变量的整数约束，对应的凹问题的最优值为：，3 = 2 2 ，由于 芑，8 此时有可能产生新的最优解 问题的最优解为：x ，= 3 ，x ：一l 墨= 1 ，石。= o 此时对应的最优值为： 厶= 2 2 令墨= 2 ，问题变为： m a x 厶= 8 + 5 五+ 6 x 3 + 7 x 4 f4 x 2 + 5 x 3 + 6 x 4 = 1 1 1 置o 且为整数( f = 2 ，3 ，4 ) 若去掉对变量的整数约束，对应的尸问题的最优值为：厶= 8 7 4 ，由 于一 ，4 ，此时已不可能产生新的最优解求解结束 原问题有二组最优解： x 1 = 4 ，x 2 = 0 ，盖j l z j = 0 或 x l 一3 ，盖2 ；1 j j 。1 ，x 4 = o 最优值，4 ；2 2 江西师范大学2 0 0 6 届硕士研究生学位论文 1 4 循环群简介及相关结论 定义1 ：记石= n 1 ，其中 口 为包括口在内的最大整数部分，即i 为口的小数 部 分称云为去整函数 定义2 ：设g ，t ) 为群，若在g 中存在一个元素口，使得g 中的任意元素都由口的 幂组成，则称该群为循环群，元素口称为循环群g 的生成元 定义3 ：彳。 q n 2 ： 口月 捌= 七 口 妇1 加2 幻。 ，七r 4 i q 坐j ，砑，甄，咧构成一循环群，称o ，五- ，甄， ( 一1 ) 彳可由j 生成其中j 为生成元，阶数为其中。为幺元 引理1 ：任何一个循环群的子群必定是循环群 引理2 ：设( g ，+ ) 是个由元素口g 生成的有限循环群如果g 的除数是一，即 l g5 栉，则n ”；p ，且g = 口，口2 ，口3 ，口”1 ，。“；e 1 其中，已是( g ，+ ) 中 的幺元，以是使“= e 的最小正整数( 称以为元素盯的阶) 引理3 ：设g 是，z 阶循环群，j 詈i = o ，则存在且仅存在一个阶数为d 的子群 l j 引理4 ：某一向量是原问题的可行解，则它一定是对应松驰问题的可行解 即：原问题的可行域是对应松驰问题可行域的一个子集 引理5 ：若4 ： 口1 1 2 1 ： 盯h 1 ，4 = 口1 2 口2 2 ： 0 2 ，a = n l m 口2 ： 口月m ，可由口= 一： 4 2 岛b ，4 = 七2 口，。，4 。；吒曰，( 丘、刀z + ，f ：1 ，2 ，m ) ，则有 即成 生 、li， 岛如；阮 多个约束变为一个约束的整数规划问题的新算法 ( 1 ) 4 = ( 2 ) 4 = ( 3 ) 4 = 口1 1 口n + 以n 口们 ，4 = ，4 = ，4a q 2 口i 2 + f 2 口月2 引 卜 i 以i ： 由引理5 容易得出下面定理1 的结论 定理1 ：若4 ： 口1 1 g 口n + q 1 口月1 口1 1 口2 1 ： 口n 1 ，4 = 口1 2 4 2 2 ： 口h 2 g 口，2 + q 2 a 2 ，4 ，4 = d l m ，l 口抽 - 口n n l m n 拥+ 抽 口肭 可由b 。= ，可由曰。= i 砘 q 。 n 2 m ： 口黼 牙扭加+ 口蛔 口删 1 9 可由b ”； 。可由b = 。可由 生成 ! 厶f ? 一 吒 岛 ： 玩 岛 和f + 岛 _ k 岛 - 岛+ 阢 瓦 生成 生成，则 生成国q ) 生成 ，飞厅 ，1。 第二章多个约束变为一个约束的整数 规划新算法 2 1 算法的基本思想 定义1 ：若上l p 问题为： m a xz = c 。曰一培一( c 。曰一1 一c 。) 五r 趴瞄雾二荨 则m a xz = g 曰一场一( c 。口一1 一c v ) 丑0 趴jo 。8 b 廿1 麒” i 羁芑o ，整数 称之为对应的松驰问题 定义2 ：在z 卯( l p ) 问题中，对应目标函数值仅比最优解小的可行解称之为 次优解 定理1 ：线性规划问题单纯形表中约束条件各列按定义1 取整后各列所组成的 元素构成定义2 中所定义的某个循环群的子集即：各列( 假设为 4 ，4 ，a ，) 按定义1 取整后( 假设为4 ，4 ，4 ，) ，则总可以找 出一生成元爿使：4 一q 爿，4 ；口2 一，a 。口爿( q ) 证明：假设初始约束方程为： 1o - o1 t ： 4 1 埘+ 1 露2 m + 1 ： 口1 _ 卅+ 2 口1 + 2 口1n 口1 _ 0 o 1 1 ，爪+ 2 4 1 ，。 五 也 ： k 扫1 如 若以为旋转元进行迭代，变换后的约束方程变为： 。) 垒全塑壅銮塑二全塑壅塑墼塑塑型回墼塑堑蔓生一 oo 上o 口* 0 o 而 由于： o 0 口1 口1 女 吒一“一 口【m + 1 口2 t 一“一；：_ 0 0 竺业 l 口 一 h 州一警。口m 口* 盘i 埘十1 口 q 一1 一 i m + 1 n 2 如t m 十1 一：_ q 埘+ 1 口* 一1 一：_ i m + 一时 ，显然 口f m + 1 口仕 n * 口f m + 一2 i 口m 口f 1 n 担fj ，f + 1 口腑 口m n l ，m + l n l i 吩一“一：_ 盘im + 1 口2 如一“一：_ i ! 业 口* ，一坠墨堕 口* 口l n 1 i n 1 一 n * 口 口甜 吒一一：- 口f “ 4 q 。口地 一一i 口in 口仆 口1 m 一 口 口i m 口2 i 2 n 一 口* 口e 月 以* f 口础 口m n 一一 口* 。一生 口m 口e h 口甜 屯一一i n i 口* 口f 月口础 一一i 结合2 2 命题1 及定理1 的结论，定理2 显然成立 可由 x 2 靠 口i m 4 1 女 口n 口f 口2 女 拉* 口f m * 口fn 口时 n m n 1 i 口* 口2 口* 1 n * 口m t 口* 生成， 设整数线性规划为： m a xz = 倒 删= 6 ，x 苫o ，整数) 并假定其中的c 、4 、6 中的元素都为整数，在去掉对x 的整数约束后， 2 1 q 也 ： 岛 ： o o ，一一； 一 一 o 1 1 o ； 江西师范大学2 0 0 6 届硕士研究生学位论文 变为了对应的线性规划问题，其最优解司表不为： m a xz = q b 。1 6 ( o 占。一g ) “ s t 。i x b 钿飞_ b 。n x n 【苫o ，。o 其中、x ，分别是基变量和非基变量，曰是基矩阵， 4 = ( b 、) ，c 。、c ，分别为基变量和非基变量的系数。c ；( e 、c j ) 当取得 最优解时h = 0 ，此时= b 4 扫 据此我们设想在取得整数最优解时： m a xz = c b b - 1 6 一( c b b - 1 一c ) x s t 2 b 1 6 一口以 i 芑o ，芑o ，整数 我们对上式约束条件等式的二边同时作用去整函数，则变为对应的松驰 问题： m a xz = o 口一冯一( q b 。1 一“) h 盯j o = b 1 6 一占1 a l k 苫o ，整数 由于q 曰。墙为常数，故问题可变为： m i nz = ( 曰。1 一c ) h 盯j o = 曰一1 6 一曰。1 k 【o ，整数 我们注意到，在此式中对芝0 的约束没有了 下面我们考虑这个一个罄数规掘可颢： 阢l 甄 至全塑j 基銮塑= 尘丝塞丝墼塑塑型问壁塑堑蔓鲨 对应的线性规划问题的最优解为 分别为三个约束条件对应的松驰变量) m a xz = 8 一 ( 莩 = ( i _ + ( 三 z ：+ 五= 三，石：= 詈，s = 7c 墨、s ：、是 此时对应的约束条件如下： 州绎瞄 其中_ 、屯、s 、s ：、s 0 ，整数 对应的松驰问题为： m i nz = 墨 ( 霉 一( 垂 s + ( 霉 s ：= ( 置 即m i nz + ：s ， 咖鼢= 其中s 、s 2 0 ，整数 由定理，( 髭) 、( 曼) 、( 荔) 为某一循环群的一部分， 江西师范大学2 0 0 6 届硕士研究生学位沦文 令4 = 彳= ( 鬓 、贝出龟= 2 42 ( j 乏) 、坞= & 42 ( ；主) o 、4 、彳：、4 为一循环群，阶数= 4 据此我们将原问题转化为： m i nz = 墨 f 捌+ 3 4 = 2 ，4 s + 爿s s tl i 。2 l 其中s 、只0 ，整数 即： m i nz 4 ；s mf4 宓+ 3 = 2 s 1 + s ， 盯 其中墨矗1 0 ，薹数 七= 0 时最优解为：s = 0 ，s 2 = 3 将其原问题的约束条件中，得： 而一2 ，x 2 3 ，s 1 0 ，s 2 = 3 ，s 3 = 1 ，这便是原问题的最优解 此方法将多个约束条件的尼p 问题转化为一个约束条件的豇尸问题 ( 一维背包问题) 大大降低了求解的复杂度，是求解尼p 问题的一种行之 有效的新方法但是我们注意到在对约束条件等式两边同时作用去整函数 的过程中，放弃了对基变量的符号约束这是否会导致错误的结果呢? 十分遗憾，答案是肯定的，也就是说此方法求出的“最优解”不一定 是可行的 下面我们将例1 中第三个约束条件改为：一2 五+ 4 bs 7 ，变为例 2 例2 ：m a xz = + 2 镌 f+ 缸2s8 趴j 孤t 鲥 ih 1 + 缸2 7 i 、x 2 o ，x 1 、x 2 整数 垒全丝塞窒塑= 尘丝壅盐墼塑塑型鲤壁堕堑篁鲨一 对应脚性规划问题的最优解为：_ = 耘= 詈 = 主 ( 墨、s 2 、是分别为三个约束条件对应的松驰变量) 此时对应的约束条件如 下： m a xz = 8 一s 1 0 o + 0 o 1 x 2 + 一1 s + 0 1 0 其中即x 2 、墨、s 2 、s 3 0 ，整数 对应的松驰问题为： m a xz 一8 一s 1 令乳= g = 0 & + 其中葺、z 2 、s 、 、 s 2 、 、则9 2 = 2 9 = s ， 5 ，0 ，整数 f 一 s ：+ 1 【 、9 7 = 7 9 = 则 o 、9 1 、g ：、g ，、9 4 、9 5 、g 。、9 7 ) 为一循环群， 阶数= 8 据此我们将原问题转化为： m i nz 4 = s 。，f8 七+ 7 = 2 s l + 墨 5 丁 其帕心：) ，毒数l 其中s 1 、s 3 o ，整数 兹 o 江西师范大学2 0 0 6 届硬士研究生学位论文 七= o 时最优解为：s = 0 ，& = 7 将其原问题的约束条件中，对应的最优 值z + ；0 ，最优解为：t = 4 ，花= 2 ，s = 一1 ，s 2 = 0 ，岛= o ， 很遗憾这组解不是原问题的可行解出现这一问题的原因在于：各列作 用函数厂后放弃了对基变量非负的约束此种方法求出的解是原问题的可行解 的一个必要条件，也就是说这一方法不具有充分性 由于原问题的可行解是对应松驰问题的一个子集，故原问题的最优解必为 对应松驰问题的一个可行解下面我们对以上方案进行改进使这种方案具有充 分性当松驰问题的最优解i 可能有多个) 不是原问题的可行解时，我们采用松 驰问题的次优解如此反复，直至找出原问题的最优解 显然当s ，= 1 ，s ，= 5 是松驰问题的次优解此时z = 1 代入原问题得 五= 3 ，吻= 2 ，s = 1 ，s 2 1 ，岛= 5 ，这组解是原问题的组可行解由于 原问题的可行解都满足此问题的约束条件，故它是原问题的最优解 2 2 步骤： 步骤二： 步骤三： 步骤四： 步骤五； 算法步骤 求出原儿p 问题对应的l p 问题的最优解，求出之后将最优表中各变量 的系数及常数列去整，得到对应的松驰问题 找出松驰问题各列构成的元素，求出包括这个集合在内的循环群，找 出生成元及各元素在循环群中的序数 根据步骤二中的结果将松驰问题转化为一维背包问题 令；d ，求出此时的最优解( 可能有多个) ，并检验其是否是原问题 的可行解，若可行则已求出原问题的最优解否则，转步骤五 继续寻找松驰问题的次优解若还无原问题的可行解，则继续寻找松 驰问题的再次优解，如此反复 步骤六：若七= 鲥无原问题的可行解则令七；1 ，类似的寻找原问题的可行解， 如此反复，直至找到原问题的最优解 第三章实例及算法的评价 3 1 二个实例 本章我们将引入二个实例，用新算法求解，并将其与分枝定界法进行比较 以说明该算法的可行性 例1 ：( 即1 2 的例题) 求下面见p 问题的最优解： m a x ，= 墨+ 5 2 2 f h x 2 一2 s 丁j 5 _ + 缸2 躬o is 4 l 昂x 2 o ，补z 2 整数 解：该问题对应的l p 问题达到最优解时对应的约束条件如下： m a x ，= 2 1 8 1 1 一( 1 9 1 1 ) 恐一( 6 1 1 ) 0 1 0 墨+ 1 0 0 镌+ 一 恐+ 一 其中五、吃、恐、砖o ，整数 对应的松驰问题为： m a x ，+ = 2 1 8 1 1 一( 1 9 1 1 ) 码一( 6 1 1 ) 确 殆 + 其中屯、0 ， 、 1 ， 整数 以+ o 0 1 江西师范大学2 0 0 6 届硕士研究生学位论文 令以= 4 = ， 、贝山4 。= 曩4 = 、以= 谢= o 、4 、4 、4 ， 为一循环群为，阶数= 1 2 据此我们求得对应的背包问题： m a x ，。= 2 1 8 1 1 一( 1 9 1 1 ) 屯一( 6 1 1 ) 心 c tf1 驰+ 7 = 5 + s t 其中为、_ j ，薹数 殆 忌= 0 时此问题为一维背包问题按1 3 提供的贪心算法进行求解，其 最优解为：码= 1 ，；2 将其代入原问题的约束条件中，得： 五= 2 ，x 2 = 3 ，b = 1 ，x 4 2 ，磅= 2 ，由于这组解是原问题的一组行 解，故它是原问题的最优解最优值，= 1 7 例2 ： 求f 面l ，问题的最优解： m a x ，= 3 + & 2 + 吨 f毡+ 缸2s8 s 丁j 毡+ 5 _ s l o i甄+ 矾+ 瓴s 1 2 i 、z 2 、恐o ，鼍、x 2 、屯整数 解：该问题对应的l p 问题达到最优解时对应的约束条件如下： 多个约束变为一个约束的整数规划问题的新算法 m a x 厂= 7 3 2 4 1 一( 4 5 4 1 ) x 4 一( 2 4 4 1 ) 砖一( 1 】4 1 ) ， 5 1 。 鼍+ 1 0 0 屹+屯+ 其中昂屯、而、z 4 、砖、芑0 ， 1 1 一。 一1 整数 x a + ， 。 _ 1 砖+ 对应的松驰问题为： m a ) 【，+ = 7 3 2 4 1 一( 4 5 4 1 ) _ 一( 2 4 4 1 ) 一( 1 】4 1 ) 讫 圄 其中杨、 令4 = 爿= 4 0 = 1 叫= 1 1 兹1 3 1 扎+ 。 ， 。 、芑0 ，整数 。 ， 1 、则4 = 7 爿= 3 1 。 ， + 1 1 兹， 3 1 ， 1 1 1 、以= 9 4 = o 、4 、彳2 、4 。) 为一循环群，阶数= 4 1 据此 我们求得对应的背包问题： ， ， 1 1 _ 1 1 ， 1 1 江西师范大学2 0 0 6 届硕士研究生学位论文 m a x ，。= 7 3 2 4 1 一( 4 5 4 1 ) 心一( 2 4 4 1 ) 骛一( 1 】4 1 ) x 6 c tf 4 披+ 1 0 = 7 x 4 + b + s t 其中石。、x 。、妄。i ，整薮i 其中、砖、x 6 o ，整数 忌= o 时此问题为一维背包问题按1 3 提供的贪心算法进行求解，其 最优解为：巍= 0 ，镌= 1 ，x 6 = 1 将其代入原问题的约束条件中，得： 五= 1 ，屯= 2 ，= 1 ，= o ，= 1 ，= 1 ，由于这组解是原问题的一 组行解，故它是原问题的最优解最优值，= 1 7 3 2 新算法的评价 例1 中按本论文提出的新算法求解，只求解了次线性规划问题和一次一 维背包问题若按1 2 中介绍的分枝定界法则需求解五次线性规划问题 例2 中按本论文提出的新算法求解，只求解了一次线性规划问题和一次一 维背包问题若按分枝定界法则需求解六次线性规划问题 实践证明：该算法比传统算法提高了求解效率，是求解i l p 问题一种行之 有效的新方法但算法中仍有不少问题有待解决如：可行域中无整数可行解 时，能否有好的方法将其迅速判定；当约束条件较多时，如何快速的寻找生成 元及循环群的阶数；以及如何在计算机上实现整个算法，并将新算法与传统算 法在复杂度上进行量化的比较这些都应是在今后的研究中应着重解决的问题 3 0 多个约束变为一个约束的整数规划问题的新算法丝 参考书目 1 】管梅谷，郑汉鼎，线性规划 m 】山东：山东科学技术出版社，1 9 8 3 【2 】赵风治线性规划计算方法【m 】北京：科学技术出版社，1 9 9 1 【3 】hm w a g n e r ：o nad a s so fc a p a c j t a i e dt r a n s p o r i a t i o np r o b l e m ，m a n a g e m e n ts c i ，5 ( 1 9 5 9 ) ， 2 5 7 2 6 1 【4 】m 0 1 ( 1 1 f a rs b a z a a ，“n e a rp r o g r a m m i n ga n dn e 似o r kf l o w s m a d d i s o n - w e s l ey 1 9 8 7 0 5 3 4 0 3 【5 1b b c k 0 6b a ，m 唧p e m e 唧0 6 i u c 荫3 a 酗啊 h h 萌肿r o p o r p a m m hp o b a 胁， c h o h c k 话m a t e m a t 聃e c k 耐埘p h a ；3 ( 1 9 6 2 ) 【6 】h a m d ya t 曲a ：i n t e g e rp m g r a m m i n gt h r y a p p l i c a t i o na n dc o m p u t a t i o n s ， m 】a c a d e m i c p r e s s ，1 9 7 5 ，2 3 0 2 6 2 7 】魏权龄，胡显佑，黄志民运筹学简明教程 m 】北京：中国人民大学出版社，2 0 0 3 ，5 1 6 8 【8 】卢开澄组合数学算法与分析【m 】北京：清华大学出版社，1 9 8 31 4 7 1 6 9 【9 】马伸著，魏权龄，赖炎连数学规划讲义，中国人民大学出版社【m 】，1 9 8 1 ，1 3 3 1 4 7 【1 0 r i c h a r dd e d e k i n d u b e rd i et l l e o r i ed e rg a n z e na l g e b r a i s c h e nz a b l e n s u p p l e m e n t t op g 【巧e u n e d i r i c h l e t ： v o r l e s u n g e n ， u b e r z a l l l e n t h e o r i e 【j 】 a u 丑d c ka n d v e r l a y ， b r a u n s c h v e i y m ，1 8 9 4 1 1 】e s m a c a u l a y ，朋g e b r a i ct h e o r yo fm o d u l a rs y s l e m s m 】c a m b r i d g eu n i v e r s i l y p r e s s ，c a n b r i d g e ，1 9 1 6 1 2 】、v o l 奄柚g 砀1 1 1 1 a x i o m a t i s c h eb e g f l l n d u n gd e ra l g e m e i m e ni d e a l t h e o f 弘s i t z ，p h y s - m e d 【j 】 s o c ，e d c o d g e n ，1 9 2 4 ，5 6 ：4 7 6 3 f 1 3 e m m y n o t h e la b s 吼k t e ra u f b a u d e r i d e a l t h e o r y i n a l g e b r a i s c b e n z a h l u n d f l l n k t i 伽e n k o r p e n j 】m a t h a 丑n ，1 9 2 7 ，9 6 ：2 6 - 6 1 f 1 4 】林斐一类整数规划问题有唯一最优解的充要条件