解变量有上、下界限制的LP问题的一种新割平面法

解变量有上、下界限制的LP问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的一种新割平面法 解变量有上、下界限制的LP问题的一种新 割平面法 第26卷第1期 2008年2月 江西 JIANCXI 科学 SCIENCE Vo1.26No.1 Ireb.2008 文章编号:1001—3679(2008)O1—0033—04 解变量有上,下界限制的LP 问题的一种新割平面法 杭海霞,叶祥企,易颖华 (江西师范大学 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 与信息科学学院,江西南昌330022) 摘要:针对变量有上,下界限制的LP问题,本文给出了求解此类问题 的一种简易方法——割平面法,并以实 例加以说明. 关键词:变量有上,下界的LP;割平面法;推广单纯形法 中图分类号:O221.4文献标识码:A AKindofNewCuttingPlaneMethodforLinearProgramming withUpperandLowerBoundedVariables qi,YIYing—hua HANGHai—xia,YEXiang— (MathematicsandInformationDepartment,JiangxiNormalUniversity,JiangxiNanchang330022PRC) Abstract:Thispaperproposesakindofsimplemethodforlinearprogrammingwithupperandlower boundedvariables—thecuttingplanemethod,andperformsexamplestoexplain. Keywords:Linearprogrammingwithupperandlowerboundedvariables,Cuttingplanemethod, Generalizedsimplexmethod O引言 实践中提出的许多线性规划问题都包含既有 上界又有下界的变量,比如容量有限制的运输问 题,大的供电网的可变电压要位于所规定的界限 内等.因此对于此类问题的研究有其实用的意 义.本文在文献[1,2]介绍的推广单纯形法的基 础之上,提出了求解此类问题的另一种方法—— 割平面法.此方法在其理论依据上比推广单纯形 法的思想更简明一些,因而有利于编程计算. 1变量有上,下界限制的LP问题的 一 般形式 变量有上,下界限制的LP问题的一般形式 为?: (P)maxz=cY t.AY=h li<-yi<ki,j=1,2,…,rt. 这里,A?R,c?R,h?R,,.『=1,2,…, rto 无论fI,|i}取值如何,只要通过引人新的变 量,上述问题(P)可化成变量只有上界限制的IJP 问题(p1)?: (‘P1)maxz=crx s.t.AX=b 0d 其中,d=(d,,…,d)(如果无上界限制可 视di=?)o 收稿日期:2007—08—31;修订日期:2007一10—15 作者简介:杭海霞(1982一),女,陕西西安人,在读硕士研究生,研究方 向:数学规划. ? 34?江西科学2008年第26卷 在文献[1,2]中,问题(p1)有了较成熟的解 法——推广单纯形法.特别的,当f?0时,问题 (1)可表示为如下问题(p2): (p2)max.=crx s.t.AX=b 0ScSSd 其中,c=(c1,c2,…,c),d=(d1,d2,…,d)(如 果无上界限制可视d=..). 定义1:将与问题(p2)相对应的LP问题(D) 记为: (D)maxz=crx s.t.AX=b 0S 针对问题(p2),在不需要引人新的变量的情况下 提出了求解它的另一种方法——割平面法. 2割平面法(以目标函数最大化为例) 2.1割平面法的基本思想 先不考虑变量的有界限制求解相应的线性规 划,如果得到的解不在变量的取值范围内,则不断 增加适当的线性约束,割掉原可行域中不满足变 量有界限制解的一部分.最终得到一个满足变量 有界限制的可行域,在此可行域中求出原问题的 最优解. 2.2割平面法的基本步骤 步骤1:求解问题(D),可能得到以下情况之 ——: (1)(D)有最优解,并符合问题(p2)中变量 有界限制的条件,则(D)的最优解即为(p2)的最 优解,则停止. (2)(D)有最优解,但不符合问题(p2)中变 量有界限制的条件,则转步骤2. (3)(D)没有可行解,即可行域为空集,这时 (p2)也没有可行解,则停止. (4)(D)无最优解,即可行域无界,此时,任 选一有界变量:0ssd,给(D)增加约束i +s=d,若求出的解满足(p2)中变量有界限制的 条件,且此时所有非基变量的检验数s0,则此 解为(p2)的最优解,停止计算.否则转步骤2. 步骤2:在步骤1所求得相应线性规划的最 优表中,给任一不在其取值范围内的基变量增加 适当的割平面方程,并填到相应最优表的最后一 行,用对偶单纯形方法求出新的最优表,重复操作 此步骤.直至满足所有变量在其取值范围内,且 此时所有非基变量的检验数,s0,则得到问题 (p2)的最优解. 2.3割平面方程的求法 令是相应LP问题最优解中不在其取值范 围内的一个基变量,则在对应的最优表中可得 戈+?口=b(%) 其中,i?Q(Q指构成基变量号码的集合),k? K(K指构成非基变量号码的集合). 由()式有=b一?tl,ik,又因为0sc ssd,则有定义2. 定义2:(1)若在对应最优表中的值b> d,则令b一?au,xsd,取此不等式作为割平 面方程;(2)若在对应最优表中戈的值b<ci,则 令b一?口?c,取此不等式作为割平面方 程.显然此切割方程能割掉不在变量取值范围内 的一部分解,即它只割掉了非可行解. 定理1:上述割平面没有割掉问题(p2)的最 优解. 证明:显然割平面只割掉了非可行解,没有割 掉可行解,这是因为任意的可行解都满足定义2 中的割平面方程,因而没有割掉问题的(p2)最优 解. 3算例 max=3x1+2+23 戈1+22+23=三三14 s.t.2x1+42+3x3S23 0=三;1?4,2S2S5,0S33 解:(1)用割平面法求解的过程:取松弛变量为 ,基变量,求解相应LP问题,得最优表如表 1 表1 表中,1:23喏Eo, ],且l:23104>4,由l表中,1=喏,],且l=>,由l 第1期杭海霞等:解变量有上,下界限制的LP问题的一种新割平面 法?35? 行可得割平面方程:一2一吾,一s4,即 - 4x2—3x3一5一15.引入松弛变量s,则割约 束变为:-4x2—3x3一5+sl=一15.将割约束加 到表1最后一行,让x,进基,sLtl基,用对偶单纯 形法求得新的最优表如表2. 表2 表2中,3=5隹[0,3],且3=5>3,由3行 可得割平面方程:5一一?+了1s3,即一 4一+s一6.引入松弛变量s:,则割约束变 为:-4x2一+s+s2=一6.将割约束加到表2 最后一行,让进基,s出基,用对偶单纯形法求 得新的最优表如表3. 表3 表3中,2=?隹[2,5],且2=?<2,由2 行可得割平面方程:3一 1 + 1 s+ 1 s2,即 一 s一s一2.引入松弛变量s,,则割约束变 为:一s一s+s,:一2.将割约束加到表3的最 后一行,让s进基,s,出基,用对偶单纯形法求得 新的最优表如表4. 表4 此时所有非基变量的检验数,0,且变量 位于其取值范围内,故已得原问题的最优解为 : (4,2,{),最优值为maxz:5了6.JJ (2)用推广单纯形法求解的过程: 令Y1=1,Y2=2—2,Y3=3,再增加松弛变 量Y,Y原问题就变成: max=3yl+Y2+2ys+2 Y1+2y2+2,,3+Y4=10 文t.2y1+4,,2+3,,3+Y5:15 Y1,Y2,乃,Y4,YsO,Y14,Y23,Y33 作单纯形表如表5. 表5 ? 36?江西科学2008年第26卷 u,=M表示y,没有上界限制.初始基可行解 = (0,0,0,10,15),Y,Y2,Y3是下标属于的 非基变量,检验数为:Al-3>0,A=1>0,A=2 >0,所以取Y作为换人变量.因为u=4,0= min{半,竽}-05:了15,min{u,}=U1,所以Yl 仍然是非基变量,只是下标从变到,在单纯 形表上只是这一列有变化:yy0.-/3u,得到 单纯形表如表6. 表6 Y列上打上’,表示指标属于R的非基变 量.u,=3,=min{导,?}=?=,min{u,, }=05,,所以Y,是换人变量,Y是换出变量,换 成取值为零的非基变量.下一单纯形表如表7. 表7 由表7h<0,<0,>0,满足最优解的条 件,得最优解为Y=(4,0,?),故原问题的最 优解为X=(4,2,?),最优值max:=. 4讨论算法计算的有限性 定义3…:设xo=(,:,…,:)是问题(p2) 的任一基可行解,如果对任一基变量都有0 c<<d.,就称是非退化的基可行解,否则就 称为退化的基可行解.若问题(p2)的所有基可 行解都是非退化的,则称问题(p2)是非退化的. 设问题(p2)是非退化的,那么从它的任一基 可行解开始用上述方法进行迭代,在计算有限步 后一定能得到最优解(最优解存在的话).这也 可以从割平面的基本思想去考查,给某一不在其 取值范围内的基变量增加一个割约束,则在以后 的迭代过程中,此变量所对应的值始终保持在其 取值范围内,因此可以保证算法计算的有限性. 5结束语 当问题(D)有解时,用割平面法求解问题 (p2)不仅可以避免引进新的变量,且割平面法的 思想及其理论依据比推广单纯形法的要简单的 多,这有利于其编程计算.因而在实际的应用中 是行之有效的. 参考文献: [1]管梅谷,郑汉鼎.线性规划[M].济南:山东科学技 术出版社,1983. [2]郭立夫.运筹学[M].长春:吉林大学出版社,2002. [3]运筹学教材编写组.运筹学[M].北京:清华大学出 版社,1990. [4]邓成梁.运筹学的原理与方法(第2版)[M].武汉: 华中科技大学出版社,2001. (上接第32页) B5(N一.一?一, )=B5(,)+B5()+ 5B()+10B3()+10B()+5B()+参考文献: [1]ZhangWen—peng?Someidentitiesinvolvingthefi- 5..bonaccinumbers[J].TheFibonacciQuartedy,19971i,5s 一…………LJj’…J,, B4(?)=?B5()+5?B4(?一?)35:225-229.’ . ,一i[2]杨倩丽,李海龙.[标签:快照]