生产经营管理数学建模两阶段特殊结构混合0-1规划的分解算法

第４期

２００９年８月第１８卷运筹与管理Ｖ０１．１８．Ｎｏ．４Ａｕｇ．２００９０ＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＣＥＭＥＮＴＳＣＩＥＮＣＥ

两阶段特殊结构混合０．１规划的分解算法

刘均华，姜波

（清华大学经济管理学院，北京１０００８４）

摘要：本文介绍了一种用于求解具有特殊结构的两阶段混合０一ｌ规划问题的原始一对偶分解算法，并以

ＣＰＬＥｘ软件作为核心求解器将算法实现。该算法将原问题分解成两个相对简单的子问题，较传统分解算法有

更平衡的分解结构和收敛性。实验数据表明，该算法在求解较大规模、稀疏度较大、耦合度较大的复杂两阶段下

三角结构混合０一ｌ规划问题时，相比ｃＰＬＥｘ提供的分枝剪枝法，在时间效率上有明显提高。算法最后通过固

定Ｏ—ｌ变量的取值可以得到满足管理精度要求的近似最优解。

关键词：混合Ｏ—ｌ规划；分解算法；原始－对偶分解；ｃＰＬＥｘ９．０；分枝剪枝法

中图分类号：０２２１．１文章标识码：Ａ文章编号：１００７—３２２ｌ（２００９）０４，Ｏｏｏｌ－０６

ＡＤｅＣＯｍｐＯＳｉｔｉＯｎＭｅｔｈＯｄｆＯｒＳＯｌＶｉｎｇＴｗＯ—ＳｔａｇｅＭｉｘｅｄ

Ｏ－１ＰｒＯｇｒａｍｍｉｎｇｗｉｔｈＳｐｅｃｉａＩＳｔｒｕｃｔｕｒｅ

ＬＩＵＪｕｎ－ｈｕａ．ＪＩＡＮＧＢｏ

（Ｓｃ＾ＤＤＺ矿Ｅ∞ｎＤｍ记ｓｏｎｄ肘矗ｎ口ｇｅｍｅｎｔ。乃￡，曙＾“口№ｆ北您ｆ秒，８ｅ彬，曙１０００８４，Ｃ＾ｆｎｏ）

ＡｂＳｔｒａＣｔ：Ｔｈｉｓｐａｐｅｒｉｎｔｒｏｄｕｃｅｓ

ｐｒｏｂｌｅｍｓｗｉｔｈ８ａｐｒｉｍａｌ－ｄｕａｌｄｅｃｏｍｐｏｓｉｔｉｏｎｍｅｔｈｏｄｔｏｓｏｌｖｅｔｗｏ－ｓｔａｇｅｍｉｘｅｄ０－１ｐｒｏｇｒａｍｍｉｎｇｉｔ’ｓｓｐｅｃｉａｌｓｔｍｃｔｕｒｅ．Ａｆｔｅｒｄｅｄｕｃｔｉｏｎａｎｄｄｉｓｃｕｓｓｉｏｎａｂｏｕｔｔｈｅａｌｇｏｒｉｔｈｍ，ｉｍｐｌｅｍｅｎｔｅｄ

ａｗｉｔｈＣＰＬＥＸ９．０．ＴｈｅｎｅｗｍｅｔｈｏｄｄｉＶｉｄｅｓｔｈｅｏｒｉｇｉｎａｌｐｒｏｂｌｅｍｉｎｔｏｔｗｏｓｉｍｐｌｅｓｕｂｐｒｏｂｌｅｍｓａｎｄｈａｓ

ｓｔｍｅｔｕｒｅａｎｄｒ８ｐｉｄｃｏｎｖｅｒｇｅｎｃｅｓｐｅｅｄｔｈａｎｔｒａｄｉｔｉｏｎａｌｄｅｃｏｍｐｏｓｉｔｉｏｎｍｅｔｈｏｄｓ．Ｃｏｍｐｕｔａｔｉｏｎａｌｍｏｒｅｂａｌａｎｃｅｄｏｕｒｔｅｓｔｓｓｈｏｗｔｈａｔａｐｐｒｏａｃｈｈａｓｈｉｇｈｅｒｔｉｍｅｅ仿ｃｉｅｎｃｙｔｈａｎｂｒａｎｃｈ ａｎｄ－ｃｕｔａｌｇｏｒｉｔｈｍｓｕｐｐｌｉｅｄｂｙＣＰＬＥＸｉｎｓｏｌｖｉｎｇｌａｒｇｅ－ｓｃａｌｅｔｗｏ—ｓｔａｇｅｍｉｘｅｄ０一ｌｐｒｏｇｒａｍｍｉｎｇｐｍｂｌｅｍｓｗｉｔｈｈｉｇｈｅｒｄｅｎｓｉｔｙａｎｄｃｏｕｐｌｉｎｇｍｔｉｏ．Ａｆｔｅｒｈｅｕｒｉｓｔｉｃ

ｃａｎｍｅｔｈｏｄｗｉｔｈ０ ｌｖａｒｉａｂｌｅｓｆｉｘｅｄｉｓａｐｐｌｉｅｄ，ｎｅａｒ ｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｓｂｅｏｂｔａｉｎｅｄ．

ＫｅｙｗＯｒｄＳ：ｍｉｘｅｄＯ ｌｐｒｏｇｒａｍｍｉｎｇ；ｄｅｃｏｍｐｏｓｉｔｉｏｎｍｅｔｈｏｄ；ｐｒｉｍａｌ ｄｕａｌｄｅｃｏｍｐｏｓｉｔｉｏｎ；ＣＰＬＥＸ９．０；ｂｒａｎｃｈ－ａｎｄ－ｃｕｔａｌｇｏｒｉｔｈｍ

０引言

０一ｌ变量常被用来表示系统是否处于某个特定的状态或者决策时是否取某个特定的方案，在工业、商业、交通运输、经济管理和军事等领域都有重要的应用。由于性质不同的变量（连续变量和０一ｌ变量）和约束（纯线性约束、混合线性约束和纯０—１约束）在系数矩阵中所处的位置不同，混合０—１规划模型会表现出多样化的结构。现实中的大规模混合Ｏ—ｌ规划模型通常具有更加特殊的结构，而且规模越大，这种结构性可能越明显。本文主要研究具有下列结构的混合Ｏ一１规划问题

收稿日期：２００８．“一１４

作者简介：刘均华（１９８ｌ ）。男．博士研究生。主要从事线性规划和混合Ｏ—ｌ规划分解算法方面的研究；姜波，男。博士，攻读博士学位期问主要研究方向为大规模线性规划算法和矩阵分解。

２运筹与管理２００９年第１８卷

ｎｌａＸ

０ＭｌＰ、’

Ｓ．ｔ．

Ａ２Ｉ茗Ｉ＋Ａ２２ｘ２≤６２

戈。≥ｏ，戈２≥ｏ；ｚ１，砖∈｛ｏ，１｝

其中ｃ。，＝（ｃ…ｃ。：）ＥＲ“，ｃ：＝（ｃ：。，ｃ：：）∈月”，ｃ。。和ｃ：。对应原问题中的连续变量，ｃ。：和ｃ：：对应原问题中的。一ｌ变量。同理。令Ａ。。＝（Ａ：。，Ａ：。）∈尺”‘。“，Ａ：。＝（Ａ：。，Ａ；。）ＥＲ“２。“，Ａ：：＝（Ａ：：，Ａ；：）∈Ｒ“２。“，石．，茗：，６。，６：是维数与前面的系数矩阵对应一致的向量，，。＝口。，口。＋１，…。ｎ。，Ｌ＝ｇ：，ｑ：＋１，…，ｎ：（下文中称石。和ｘ：为混合变量）。上述混合０一ｌ规划问题（肘伊）整体上可以划分为两个阶段，第一阶段的约束称为独立约束，

第二阶段的约束称为耦合约束，混合变量髫．称为耦合变量，戈：称为独立变量。具有这种结构的问题，其共同的特点就是在每个阶段中都包含了混合整数变量和混合线性约束，而且Ｏ—ｌ变量在整个问题中仅占很小的部分，很多问题很难直接求解。虽然传统的整数规划算法（例如分枝定界法¨ｌ、割平面法心Ｊ１）有时也可以求解，但是算法的求解效率和空间效率很难满足日常管理的需要，本文主要研究利用分解算法来求解这类问题。

１分解算法简单回顾

目前用于求解。一ｌ规划问题的分解算法主要是Ｄａｎｔｚ唔一ｗｏｌｆｅ分解算法”１（以下简称Ｄ．ｗ分解方法）和Ｂｅｎｄｅｒｓ分解算法¨１。Ｄ－ｗ分解算法最初主要针对具有块角结构的线性规划问题，很多实际问题，例如多周期生产计划问题、能力扩展计划问题、稀缺资源分部门配置问题、电力生产系统的排班问题等，系数矩阵都具有块角结构，ｓｗｅｅｎｅｙ和Ｍｕｒｐｈｙ¨１在解决具有该结构的混合０—１规划问题时采用了Ｄ．形分解算法。

利用Ｄ一矽分解算法求解混合整数规划，需要将原问题的变量和约束进行分组，形成与上述（Ｍ，尸）问题结构相同的模型。其中独立约束Ａ。。石。≤６。是一个混合０一ｌ系统，仅与变量石。相关；约束Ａ：。戈。＋Ａ：：算：≤６：是与变量名：耦合的耦合约束。选择第一个混合０—１系统构成一个子问题，利用该子问题可行域凸包极点和极方向的。一１组合来表示混合变量ｚ。，形成分解方法的主问题。主子问题之间通过列生成的方法进行迭代。Ｄ一形分解算法最终可以提供一个较原问题线性松弛更紧的边界，其主问题可以看作拉格朗日松弛方法¨’副的对偶问题。

Ｄ一形分解算法最后得到的是原问题（最大化问题）最优目标函数值的上界，提供的最优解对于原问题来说是不可行的。为了能得到原问题的可行解或最优可行解，该方法还需借助启发式方法，以分解算法得到的解为搜索起点利用启发式方法搜索整数可行解，也可以转入分枝剪枝过程，求解受限的原问题来获得原问题的可行解。

求解混合整数规划更为著名的方法是Ｂｅｎｄｅｒｓ分解算法。它最初就是针对混合整数规划问题提出的分解方法。Ｂｅｎｄｅｒｓ分解方法将连续变量和整数变量分解，通过固定０—１变量（髫…茗：：）的取值构造一个 …… 此处隐藏：2225字，全部文档内容请下载后查看。喜欢就下载吧 ……