解整数线性规划中选择割平面的一个方法(1)

《解整数线性规划中选择割平面的一个方法(1)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第13卷
第2期运
筹
与
管
理Vol.13,No.22004年4月OPERATIONSRESEARCHANDMANAGEMENTSCIENCEApr.2004

解整数线性规划中选择割平面的一个方法左光纪(青海民族学院数学系,青海西宁810007)摘
要:本文指出了文[4]的一个错误。用最速下降规则,给出了选择割平面的一个新方法。一个复杂的例子说明,该方法有一定的实用价值。关键词:整数线性规划;割平面方法;对偶单纯性方法;最速下降规则中图分类号:O2214


文章标识码:A


文章编号:1007
3221(

2、2004)02
0001
04ASelectiveMethodofCuttingPlaneinResolvingILPZUOGuang
ji(MathematicalDepartment,QinghaiNationalitiesCollege,Xining810007,China)Abstract:Thispaperpointsoutanerrorin[4].Bysteepestdescentrule,anewmethodofselectingcuttingplaneequationhasbeengiven.Acom

3、plexexampleshowsthatthemethodispractical.Keywords:ILP;cuttingplanemethod;dualsimplexmethod;steepestdescentrule0
引言周知,求解整数线性规划的常用方法是分枝定界法和割平面法,在许多运筹学教科书中都介绍了这两个方法。文[1]、[2]都指出过:用割平面法求解整数规划时,常常会遇到收敛很慢的问题;在实际应用时,往往和分枝定界法配合使用。文[4]说:之所以发生收敛很慢的情况,原因是在我们没有找到割平面方程的优选准

4、则。于是,该文给出了这样一个准则:应首先选择用约束方程中正系数的小数部分去除相应的检验数后所得具有最小绝对值的约束方程为导出方程。该文在举例验证中,按准则选出的表2的割约束虽有效,但在通过表3分析另一割约束方程不选的原因时,却因一个计算错误而否定了割平面的一个重要性质:所以,许多教科书中说割平面方法不会割去任何整数解的说法,在没有割平面方程的优选准则的前提下是错误的。本文将进一步分析割平面方法的理论意义和实用价值,指出文[4]的上述错误。用最速下降规则,本文给出了选择割平面的一个新方法,还计算了文[1]的一个复杂

5、例子,说明该方法有一定的实用价值。1
割平面方法的理论意义和实用价值设纯整数线性规划问题收稿日期:2003
07
10基金项目:教育部科学技术研究重点项目(03134)作者简介:左光纪(1944
),男,四川广安人,青海民族学院应用数学系教授,1968年毕业于四川大学数学系,主要从事数学和运筹学的教学,研究方向为组合优化与运筹学。2运
筹
与
管
理











2004年第13卷maxz=cxs.t.Ax=b(ILP):

x!0
x为整数向量的松弛问题为maxz=cx(LP):s.t.Ax=b

x!0

6、其中A为m∀n矩阵,A的秩为m(m

7、了(LP)的整数可行解。第三,添加新的约束(割平面方程)#(-fi,j)xj+si=-fi于(LP)的最优单纯形表后,得到的表是一个原始基本不可行解和对偶可行解,需要用对偶单纯形方法换基迭代。第四,割平面不等式往往有多个,恰当选取割平面可使迭代过程尽快地收敛到(ILP)的最优解。文[3]对第一、三点特别强调,称之为分数对偶割平面算法,并指出该算法的有限收敛性。*第五,按照一定的规则选取非整数bi所在行做割平面的生成行,再运用对偶单纯形算法避免循环的规则,可以保证分数对偶割平面算法在有限步内结束运算。上述分析表明,割

8、平面法有着重要的理论意义和应用价值。通过单纯形表的运算,可把x为整数向量这个信息逐步转化为一系列线性约束(割平面)。文[3]曾举例说明,变量限制为整数本质上是一个非线性约束,它不可能用线性约束来代替。然而割平面法表明,可用一系列线性约束来逼近这个非线性约束。并且,该方法可在有限步内求得整数最优解,有可操作的实用价值。因此,割平面法的价值并不