基于CPLEX的原始_对偶嵌套分解算法.pdf

第 17卷 　第 6期 运 　筹 　与 　管 　理 Vo l. 17 ,No. 6 2008年 12 月 OPERA TION S RESEARCH AND MANA GEM EN T SC IENCE D ec. 2008 　 　 基于 CPLEX 的原始 ———对偶嵌套分解算法 刘均华 , 　蓝伯雄 (清华大学 经济管理学院 ,北京 100084) 摘 　要 :本文介绍了一种求解大规模下三角结构线性规划问题的原始 - 对偶嵌套分解算法 ,并以 CPL EX 9. 0 作 为核心求解器将算法实现 。原始 ———对偶嵌套分解算法将原问题分解成一系列子问题 ,每个子问题既可以收到 来自前一阶段子问题的价格信息 ,又可以收到来自后一阶段子问题的资源信息 ,较传统嵌套分解算法具有更加 平衡的信息传递方式和良好的收敛性 。实验数据表明 ,该算法在求解较大规模 、稀疏度较小 、耦合度较小的下三 角结构线性规划问题时 ,相比单纯形法 ,在时间效率上有明显提高 。 关键词 :线性规划 ;嵌套分解算法 ;原始 - 对偶分解 ; CPL EX;单纯形法 中图分类号 : 022 1. 1　　　文章标识码 : A 　　　文章编号 : 1007322 1 (2008) 06000 105 Nested Pr im a lD ua l D ecom position M ethod Ba sed on CPL EX L IU Junhua, LAN Boxiong (S chool of E conom ics and M anag em en t, Ts ing hua Un ivers ity, B eij ing 100084, Ch ina) Ab s tra c t: Th is p ap er in troduce s a ne sted p rim aldual decompo sition m ethod for largescale linear p rogram sw ith a lower triangu lar structu re, and then imp lem en ts it ba sed on CPL EX 9. 0. The new m ethod divide s the original p rob lem in to a serie s of subp rob lem s. Each subp rob lem ha s both p rice inform ation from the p reviou s one s and re sou rce inform ation from the latter one s. It ha s a more balanced structu re and more rap id convergence sp eed than traditional ne sted decompo sition m ethod s. Compu tational te sts show that the ne sted p rim aldual decompo sition m ethod ha s h igher tim e efficiency than simp lex algorithm in so lving largescale linear p rogram s w ith low coup ling ratio and low den sity. Ke y w o rd s: linear p rogramm ing; nested decompo sition m