运筹学-大M法或两阶段法的上机试验

1、实验报告实验课程名称运筹学实验项目名称大M法或两阶段法的上机实验年级专业学生姓名学号00学院实验时间：年月曰姓名学号实验组实验时间指导教师成绩实验项目名称大M法或两阶段法的上机实验实验目的及要求：实验目的：1.学会用Tora软件或Lindo软件求解线性规划问题，2,理解每一步迭代计算中进基与出基变量等，了解大M法或两段法的上机实验。实验要求：完成作业P97页第6题及第7题（4）。实验（或算法）原理：1.大M法思路：在单纯形法的基础上，为了使解线性规划有一个务-的解法，我们把所有求目标函数最小值的问题化为求目标函数最大值的问题。只要把目标函数乘以-1,就可以把原来求目标函数最小值的问题化为求目标

2、函数最大值问题。为了找到一个满足条件的单位向量（非负），就需要加人工变量，注意人工变量与松弛变量和剩余变量是不同的，松弛变量和人工变量可以取零值也可以取正值，而人工变量只可以取零值，否则就会不等价。我们规定人工变量在目标函数中的系数为-M,M为任意大的数，这样只要人工变量大于零，所求的目标函数就是一个任意小的数，为了使目标函数最大，就必须将人工变量从基变量中换出。如果一直到最后，人工变量仍不能从基变量中换出，也就是说人工变量仍不为零，则该问题尢可行解。像这样，为了构造初始可行基得到初始可行解，把人工变量”强行”的加到原来的约束方程中去，又为了尽力地把人工变量从基变量中替换出来就令人工变量在求最

3、大的目标函数里的系数为-M的方法叫做大M法，M叫做罚因子。2.两阶段法原理：两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划问题分两阶段求解。第一阶段：要判断原线性规划问题是否有基本可行解，保持线性规划问题的约束条件原线性规划问题一样，而目标是求人工变量的相反数之和的最大值，如果此值大于零，即说明不存在使所有人工变量都为零的可行解，即原问题无可行解，因停止计算。如果此值为零，即说明存在一个可行解使得所有的人工变量都为零。第二阶段：将第一阶段的最终单纯形表中的人工变量（都是非基变量）取消，将目标函数换为原来的目标函数，把此可行解作为初始解进行计算，接下来的计算和单纯形法计

4、算原理是一样的。实验硬件及软件平台：PC机，Tora软件，Internet网。实验步骤：大M法步骤：1 .打开TOR的令窗口；2 .选择Linearprogramming->Selectinputmode->Gotoinputscreen;3 .输入待解的方程组-Slolvemenu->Solveproblem->Algebraic->Iterations-M-method-输入值-点击GoToOutputFormatScreen-点击GoToOutputScreen->点击Alllterations。4 .得出运行结果。5 .改变3步骤中的值（例100改为

5、100000）,再按之后的步骤运行，得出结果。6 .观察对比结果。两阶段法步骤：1）打开TOR的令窗口；2）选择Linearprogramming->Selectinputmode->Gotoinputscreen；3）输入待解的方程组-Slolvemenu->Solveproblem->Algebraic->Iterations-Two-phasemethod-点击GoToOutputFormatScreen-点击Alllterations;4）得出运行结果。实验内容（包括实验具体内容、算法分析、源代码等等）：1 .书上P97页第6题：用大M法和两阶段法求解下列

6、线性规划问题。maxz=5x1x23x3;约束条件：x1+4x2+2x3>10,x1-2x2x3M16.123CTA:大M法TORAFileEdfitGridLINEARPROGRAMMING心jc3Enter<,"机Of-Fm.主Var.HanieMlXlfltllt|眄3.WConatr1i.dq|4.DD2.M>-10JM'Constr2-2.D01.Mc-16.04LowerB<HindO.W0.00gjm刖u”i而而Winlinih191rt2争|rdlnnIteration4Bdxick1x3Sx4Rm5$x6Solutionz(max|0

7、.00_J1.002.000.00100.005.00eo.ocdk11.00-2.00100U.0Q-0.001000.00-C.00-1.0010而1.001.00LowerBound0一回0UD0.00UpperBoundinfinityinfinityinfinityUme&ti'd(y/n)?nnIi图1.2由上面的结果可知，满足所求出的3M0,得出目标函数的最优解x1=16,x2=0,x3=0,sx4=16,Rx5=0sx=0,最优值是80。当把M的值改为100000后，值还是一样的,这样就可以得出当M为100时，已经得出有效解。Phase1Iter1Basicx1

8、«2SMRh5nfiSolution2.(min)1.D04.002r000.000.0010.001004.002.00T,口口1口4口¥*61.00-2.00J.00000001.0016.00LowerBound(LOO0.000.00UppeiBoundinfinityinfinityinfinityUnreslr'd(y/nj?nnrqrq1111Phase1Iter2Basicx2*3Sm4Rk5£K6SolutionZ(min)0.000.000一口。0.001.000.000000.251.000M-0.250250.002.501.500

9、.002U。0500501.0021.00LowerBound0000.00口一疝UppeiBoundinfiniityinfinityiminit.zdUnfestf"d(y/nj?nnnrq11Phase2(Itef3Basicxl«2*3Sx4Rk5ts£Solutionz(maxJ0.002500.25blocked0.002.50251.000.50-0.252.50Phate2Itei5图1.3由图1.3可知，先进行线性规划的第一阶段，满足M<0,且z值为零，即说明存在一个可行解使得所有的人工变量都为零，此时x2=2.5,sx6=21,其余为0得

10、出z=0。接下来进行第二阶段，令z=5x1+x2+3x3-0sx4+0Rx5+0sx6,和大M的分析方法一样，最终将得到满足可<0时达至ij最优解：当x1=16,x2=0,x3=0,sx4=6,Rx5=0,sx6=0,最优值为80。2 .书上P97页第7题（4）大M法和两阶段法求解下列线性规划问题。maxz=2x1x2x3；约束条件：4x12x22x3.4,2x14x2-20,4x18x22x3三16,123A:大M法Iteration3Basic«1k2«3S«4Rx5sxG£*7SolutiDn|z(max0.003.000.000.00100

11、.000.000.508.00x11.002.000.500.000.0(o.oo0.25-0.504.00|sx60.000.00-1.000.000.0(1.0012.00Sx40.00GOO0.001.00-1-0I0.001.0012.00LowerBoundUpperBound0.000.000.00infinityinfinityinfinityUnractr'dy/nj?nnniidmqCBnr»Ockk>cli«qg«HEIbreimir词MmE间»ioi)nxnTHSiffi,C0Fr.drmilcctiimnirwi,r

12、fecuteMinqcv*afFbmiMrfH/msii诉f仆pul4wriFd帕后I»forIMLRli»de.asfin*|d<xjNe>dckollrqetIjiNjamtwnflm(tefiiai)必图2.1Jtlm2心fcnlBfn。二R.H.S.丽mhm-aMaxiniiiv叩1IjMCfMSIII1?叫H3CMVtri0-W'<-20JWCMfiir/4gl7M1FELowerBoumdD-DOlOjHlipperkkrnriFdintwiitrimhnTUhrestfU忸?m1JPKIPWIT&RIID-UNUHPnDDRA

13、MMING图2.2由上面的图2.1可知，首先先输入数据即线性规划的系数如图2.1所示令maxz=2xi+X2+x3-0sx4+0sx6+0sx7-MRx5;进行下一次迭代，以同样的方法一直下去,其余到所求出的3W0为止，就可以得出目标函数的最优解：x1=4,sx4=12,sx6=12,为0时，最优值为8。当把M的值改为100000后，值还是一样的，这样就可以得出当M为100时，已经得出有效解。Phase1Iter1Basick1k2Sx4Rw5suGsx7Solutionz(min)2aa2.00100ODDaaa0.004.DO4叫2002.001DO4DOsxG2而4.000.00DOOO

14、DD1.000.002D.00sx74mf8.002.00ODDO000.001.001B.00LowerBound0OD0.00U.OOILipperOoundinfinityinfinityinfinityUnrestr'dhf/n?一.1RinPhau1(Iter2Basicxln2x3Sx4Rx53x6sx7Solutionz(min)0000.00DOOODD-1000IooDOO0.0(1xl1000.500.50-0.25250J0.001.00xxG0DO3l00-1.000500501.10,0018DOnAin£nn01001nn1DDn1nnnnU.OU

15、u_UU-1*LPU!1£.bLPU1u*M：rflftundODD0.000.00UpperHoundinlinilyinfinityinfinityL1Unrestr'dy/nj?nmnrnPhase2(Iter3Basicx1k2x3Sx4R*5txGjk7Solutionz(max)DOO0DO0.001-050blockedODD0.002.DOx11.000500.5Q-0.250.250DO0,001.00non3,00inn050-0.501.00Q.QQIBnoDOO6.000.001DD12.D0LowerBound0.00Q000.0QIUpperBou

16、ndlinfinityinfinityinfinity|Unrestr'd(y/nj?nnnPhon2(Iter4Baiicxl*2x3Sx4Rx5ixGs«7Solulionz(max)0.003_000.000.00blockedODO0.500.00x11.口口20万OM0000,000DO。25sxGu川0001加0000.001DO-0.501万0Sx4(f而6一口万足口万1.00-1.000.001.00|12而LowerBoundo.ouQ口口0.口口UppetBoundinfinityinfinilyiMinityUnreslrMQjp/nJ?：n|nn1图2.3由图2.3可知，先进行线性规划的第一阶段，z=0x1+0x2+0x3+0sx4-Rx5+0sx6,通过迭代，满足罚E0,且z值为零，即说明存在一个可行解使得所有的人工变量都为零，此时x1=1,sx6=18,sx7=12,其余为0,得出z=0o接下来进行第二阶段，令z=2x1+x2+1x3+0sx4+0Rx5+0sx6+0sx7,和大M的分析方法一样，最终将得到满足6j<0时达到最优解：当x1=4,x2=0,x3=0,sx4=12,Rx5=0,sx6=12,最优值为8。实