運籌學(xué)-大M法或兩階段法的上機試驗

1、實驗報告實驗課程名稱運籌學(xué)實驗項目名稱大M法或兩階段法的上機實驗?zāi)昙墝I(yè)學(xué)生姓名學(xué)號00學(xué)院實驗時間：年月曰姓名學(xué)號實驗組實驗時間指導(dǎo)教師成績實驗項目名稱大M法或兩階段法的上機實驗實驗?zāi)康募耙螅簩嶒災(zāi)康模?.學(xué)會用Tora軟件或Lindo軟件求解線性規(guī)劃問題，2,理解每一步迭代計算中進基與出基變量等，了解大M法或兩段法的上機實驗。實驗要求：完成作業(yè)P97頁第6題及第7題（4）。實驗（或算法）原理：1.大M法思路：在單純形法的基礎(chǔ)上，為了使解線性規(guī)劃有一個務(wù)-的解法，我們把所有求目標(biāo)函數(shù)最小值的問題化為求目標(biāo)函數(shù)最大值的問題。只要把目標(biāo)函數(shù)乘以-1,就可以把原來求目標(biāo)函數(shù)最小值的問題化為求目標(biāo)

2、函數(shù)最大值問題。為了找到一個滿足條件的單位向量（非負(fù)），就需要加人工變量，注意人工變量與松弛變量和剩余變量是不同的，松弛變量和人工變量可以取零值也可以取正值，而人工變量只可以取零值，否則就會不等價。我們規(guī)定人工變量在目標(biāo)函數(shù)中的系數(shù)為-M,M為任意大的數(shù)，這樣只要人工變量大于零，所求的目標(biāo)函數(shù)就是一個任意小的數(shù)，為了使目標(biāo)函數(shù)最大，就必須將人工變量從基變量中換出。如果一直到最后，人工變量仍不能從基變量中換出，也就是說人工變量仍不為零，則該問題尢可行解。像這樣，為了構(gòu)造初始可行基得到初始可行解，把人工變量”強行”的加到原來的約束方程中去，又為了盡力地把人工變量從基變量中替換出來就令人工變量在求最

3、大的目標(biāo)函數(shù)里的系數(shù)為-M的方法叫做大M法，M叫做罰因子。2.兩階段法原理：兩階段法是處理人工變量的另一種方法，這種方法是將加入人工變量后的線性規(guī)劃問題分兩階段求解。第一階段：要判斷原線性規(guī)劃問題是否有基本可行解，保持線性規(guī)劃問題的約束條件原線性規(guī)劃問題一樣，而目標(biāo)是求人工變量的相反數(shù)之和的最大值，如果此值大于零，即說明不存在使所有人工變量都為零的可行解，即原問題無可行解，因停止計算。如果此值為零，即說明存在一個可行解使得所有的人工變量都為零。第二階段：將第一階段的最終單純形表中的人工變量（都是非基變量）取消，將目標(biāo)函數(shù)換為原來的目標(biāo)函數(shù)，把此可行解作為初始解進行計算，接下來的計算和單純形法計

4、算原理是一樣的。實驗硬件及軟件平臺：PC機，Tora軟件，Internet網(wǎng)。實驗步驟：大M法步驟：1 .打開TOR的令窗口；2 .選擇Linearprogramming->Selectinputmode->Gotoinputscreen;3 .輸入待解的方程組-Slolvemenu->Solveproblem->Algebraic->Iterations-M-method-輸入值-點擊GoToOutputFormatScreen-點擊GoToOutputScreen->點擊Alllterations。4 .得出運行結(jié)果。5 .改變3步驟中的值（例100改為

5、100000）,再按之后的步驟運行，得出結(jié)果。6 .觀察對比結(jié)果。兩階段法步驟：1）打開TOR的令窗口；2）選擇Linearprogramming->Selectinputmode->Gotoinputscreen；3）輸入待解的方程組-Slolvemenu->Solveproblem->Algebraic->Iterations-Two-phasemethod-點擊GoToOutputFormatScreen-點擊Alllterations;4）得出運行結(jié)果。實驗內(nèi)容（包括實驗具體內(nèi)容、算法分析、源代碼等等）：1 .書上P97頁第6題：用大M法和兩階段法求解下列

6、線性規(guī)劃問題。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由上面的結(jié)果可知，滿足所求出的3M0,得出目標(biāo)函數(shù)的最優(yōu)解x1=16,x2=0,x3=0,sx4=16,Rx5=0sx=0,最優(yōu)值是80。當(dāng)把M的值改為100000后，值還是一樣的,這樣就可以得出當(dāng)M為100時，已經(jīng)得出有效解。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可知，先進行線性規(guī)劃的第一階段，滿足M<0,且z值為零，即說明存在一個可行解使得所有的人工變量都為零，此時x2=2.5,sx6=21,其余為0得

10、出z=0。接下來進行第二階段，令z=5x1+x2+3x3-0sx4+0Rx5+0sx6,和大M的分析方法一樣，最終將得到滿足可<0時達至ij最優(yōu)解：當(dāng)x1=16,x2=0,x3=0,sx4=6,Rx5=0,sx6=0,最優(yōu)值為80。2 .書上P97頁第7題（4）大M法和兩階段法求解下列線性規(guī)劃問題。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可知，首先先輸入數(shù)據(jù)即線性規(guī)劃的系數(shù)如圖2.1所示令maxz=2xi+X2+x3-0sx4+0sx6+0sx7-MRx5;進行下一次迭代，以同樣的方法一直下去,其余到所求出的3W0為止，就可以得出目標(biāo)函數(shù)的最優(yōu)解：x1=4,sx4=12,sx6=12,為0時，最優(yōu)值為8。當(dāng)把M的值改為100000后，值還是一樣的，這樣就可以得出當(dāng)M為100時，已經(jīng)得出有效解。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可知，先進行線性規(guī)劃的第一階段，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時達到最優(yōu)解：當(dāng)x1=4,x2=0,x3=0,sx4=12,Rx5=0,sx6=12,最優(yōu)值為8。實