整数线性规划的一种新的割平面法.pdf

第 18 卷第 1 期 经　济　数　学 V o l. 18　N o. 1 　　　　　　 　　 　　　　　　　 　 200 1 年 3 月 M A TH EM A T IC S IN ECON OM IC S M ar. 200 1 整数线性规划的一种新的割平面法 高培旺　　　　　　　　　高培生 ( 中南大学铁道校区数理力学系, 长沙, 4 10075) (湖南省农业银行, 长沙, 4 10007) 摘　要　本文提出了一种新的求解整数线性规划的割平面思路 它利用 目标函数等值面的移动来切割与 ( IL P ) 相应的(SL P ) 可行域的“无用”部分, 再通过扩大与(SL P ) 最优基相应的非基变量的取值来压缩( SL P ) 的 可行域, 由此求得整数线性规划的最优解 关键词　整数线性规划, 单纯形法, 割平面法 1. 引言 Gom o ry [ 1 ] 曾经引进割平面用于把与( IL P ) 相应的(SL P ) 可行域中的“无用”部分割掉, 直 到割到( ) 的最优整数解上为止 [4 ] 把原有规划约束中的常系数看作参变量, 考察了原 IL P P an ik 有- 对偶规划之间的关系, 发现参变量的变化将导致原有- 对偶规划的可行域相互对立地“膨 胀和缩小”本文把 Gom o ry 和 P an ik 的思想结合起来 即通过移动 目标函数等值面来切割 ( SL P ) 可行域中的“无用”部分, 再通过扩大与(SL P ) 最优基相应的非基变量的取值来压缩 (SL P ) 的可行域, 从而取得( IL P ) 的最优整数解 本方法的主要特征在于(SL P ) 可行域的切割与压缩将通过控制(SL P ) 最优 目标值的减少 和非基变量取非负整数的组合来实现 迭代过程可以在单纯形表上进行直到取得(IL P ) 的最 优整数解 迄今, 求解整数规划的大部分方法都是相当复杂的, 包括著名的割平面法和分枝定界原 理[ 5 ] 本文提出的方法为求解整数规划问题提供了一种新的途径 2 算法原理 考虑下面的整数线性规划问题: 　　　　　　　　　( ) 　　 　　 = T , IL P m ax f c x . . 　　 = , s t A x b x 0, 整数 这里, ∈ m ×n. 是整数集, 和 是相应维数的整数向量 与( ) 相对应的( ) 是: A Z Z b c IL P SL P 　　　　　　　　　( ) 　　 　　 = T , SL P m ax f c x . . 　　 = , s t A x b x 0 收稿 日期: 2000- 02- 2 1 第 1 期　　　　　　　　高培旺　高培生: 整数线性规划的一种新的割平面法