资源描述：
《基于CPLEX的原始_对偶嵌套分解算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第17卷第6期运筹与管理Vol.17,No.62008年12月OPERATIONSRESEARCHANDMANAGEMENTSCIENCEDec.2008基于CPLEX的原始———对偶嵌套分解算法刘均华,蓝伯雄(清华大学经济管理学院,北京100084)摘要:本文介绍了一种求解大规模下三角结构线性规划问题的原始-对偶嵌套分解算法,并以CPLEX9.0作为核心求解器将算法实现。原始———对偶嵌套分解算法将原问题分解成一系列子问题,每个子问题既可以收到来自前一阶段子问题的价格信息,又可以收到来自后一阶段子问题的资源信息,较传统嵌套分解算法具有更加平衡的信息传递方式和良好的收敛性。实验数据表明
2、,该算法在求解较大规模、稀疏度较小、耦合度较小的下三角结构线性规划问题时,相比单纯形法,在时间效率上有明显提高。关键词:线性规划;嵌套分解算法;原始-对偶分解;CPLEX;单纯形法中图分类号:0221.1文章标识码:A文章编号:100723221(2008)0620001205NestedPrimal2DualDecompositionMethodBasedonCPLEXLIUJun2hua,LANBo2xiong(SchoolofEconomicsandManagement,TsinghuaUniversity,Beijing100084,China)Abstract:Thispap
3、erintroducesanestedprimal2dualdecompositionmethodforlarge2scalelinearprogramswithalowertriangularstructure,andthenimplementsitbasedonCPLEX9.0.Thenewmethoddividestheoriginalproblemintoaseriesofsubproblems.Eachsubproblemhasbothpriceinformationfromthepreviousonesandre2sourceinformationfromthelatter
4、ones.Ithasamorebalancedstructureandmorerapidconvergencespeedthantraditionalnesteddecompositionmethods.Computationaltestsshowthatthenestedprimal2dualdecompositionmethodhashighertimeefficiencythansimplexalgorithminsolvinglarge2scalelinearprogramswithlowcouplingratioandlowdensity.Keywords:linearpro
5、gramming;nesteddecompositionmethod;primal2dualdecomposition;CPLEX;simplexmethod0引言由于管理科学的日趋发展和定量化的研究趋势,具有庞大组织体系的企业单位与行政机构不断涌现,实际应用中的线性规划问题规模通常都非常巨大,约束及变量个数成百上千,甚至更多。同时注意到,这样的大规模线性规划问题通常都有自己的特殊结构,并且规模越大,这种结构性可能越明显:变量或约束可以划分成不同的阶段或组合,每个阶段可能互相独立,同时又由另一些变量或约束建立一定的耦合联系[1,2]等。这种结构的问题尽管可以用一般的单纯形法直接求解,但
6、是问题的特殊结构总是鼓励人们去寻求一种更有针对性的求解方法,无论从空间还是时间效率上都能够有所提高。嵌套分解算法是求解具有多级下三角结构线性规划的主要方法。收稿日期:2008204202作者简介:刘均华(19812),男,山东泰安人,博士研究生,研究方向:大规模线性规划及混合0-1规划分解算法;蓝伯雄(19502),男,教授,博士生导师,研究方向:运筹学、优化模型、大系统分解算法。2运筹与管理2008年第17卷1传统嵌套分解算法[3,4][5]在以往的分解方法中,最为典型和成功的是Dantzig2Wolfe分解算法(1960)和Benders分解算法[6][7][8][9][10](1
7、962)。Dantzig(1963),Cobb和Cord(1970),Glassey(1973),Ho与Manne(1974),Ament(1981)等基于Dantzig2Wolfe分解算法提出了适用于多级下三角结构线性规划的对偶套分解方法;Dantz2[11][12][13]ig(1980),Abrahamson(1981),Wittrock(1984)等基于Benders分解算法提出了适用于多级下三角结构线性规划的原始套分解方法。对偶套分解
