求解整数线性规划问题的一种新算法.pdfVIP

( ) 2007 年 3 月 第 4 卷 第 1 期 长江大学学报 自科版 理工卷 　 Journal of Yangtze University ( Nat Sci Edit) Sci Eng V 　Mar2007 , Vol4 No 1 ·5 · 求解整数线性规划问题的一种新算法 ( ) 　　燕子宗　 长江大学信息与数学学院 , 湖北 荆州 434023 [摘要] 提出了一种求解整数线性规划问题的新方法 。利用流动等值面技术的原单纯形方法 , 从初始整数 可行解出发 , 逐步寻找下一个更好的整数可行解 , 直到找到原问题的最优解 , 必要时通过 Gomory 割平面 来寻找整数可行解 。该方法不但保留了原割平面法保持整数可行解的特点 , 而且继承了对偶割平面法灵 活利用割平面的优点 。 [ 关键词] 整数线性规划 ; Gomory 割平面技术 ; 线性规划 ; 流动等值面 ; 对偶间隙 [ 中图分类号] O22 12 [文献标识码] A 　　 [文章编号] 1673 1409 (2007) 0 1 N005 04 　　 ( ) 割平面算法以及结合分支定界技术的分支割算法 , 目前已经变成求解 混合 整数线性规划问题的 非常有用的工具[ 1～3 ] 。事实上 , 这些算法绝大部分都是通过引入对偶割平面 , 逐步压缩原问题的相应松 弛线性规划问题的可行域 , 然后利用对偶单纯形算法求得问题的整数最优解 , 必要时通过分支定界技术 加快收敛速度 , 这些方法本质上都是以 Go mory 的割平面法为基础的[4 ] 。笔者讨论求解整数线性规划问 题 : T n ( ) 　　max c x 　　st Ax = b 　　x ∈Z+ 1 n m ×n m n 式中, c ∈Z , A ∈Z 和 b ∈Z 是已知的参数; Z+ 代表 n 维非负整数集合 。对应的松弛线性规划问题为: T ( ) 　　max c x 　　st Ax = b 　　x ≥0 2 借助对偶单纯形算法的割平面技术在求解整数线性规划问题方面取得巨大成功 , 但该方法的处理策 略也是有明显缺点的。它必须要在求得相应松弛问题的最优解后 , 通过割平面压缩其可行域后逐步求得 原问题的整数最优解 。尽管 Yo ung 后来提出了原割平面算法对原方法进行了修改[ 5 ]