運(yùn)籌學(xué)-大M法或兩階段法的上機(jī)試驗(yàn)

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

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

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

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

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

6、線性規(guī)劃問(wèn)題。maxz=5x1x23x3;約束條件：x1+4x2+2x3>10,x1-2x2x3M16.123CTA:大M法TORAFileEdfitGridLINEARPROGRAMMING心jc3Enter<,"機(jī)Of-Fm.主Var.HanieMlXlfltllt|眄3.WConatr1i.dq|4.DD2.M>-10JM'Constr2-2.D01.Mc-16.04LowerB<HindO.W0.00gjm刖u”i而而Winlinih191rt2爭(zhēng)|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時(shí)，已經(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可知，先進(jìn)行線性規(guī)劃的第一階段，滿足M<0,且z值為零，即說(shuō)明存在一個(gè)可行解使得所有的人工變量都為零，此時(shí)x2=2.5,sx6=21,其余為0得

10、出z=0。接下來(lái)進(jìn)行第二階段，令z=5x1+x2+3x3-0sx4+0Rx5+0sx6,和大M的分析方法一樣，最終將得到滿足可<0時(shí)達(dá)至ij最優(yōu)解：當(dāng)x1=16,x2=0,x3=0,sx4=6,Rx5=0,sx6=0,最優(yōu)值為80。2 .書(shū)上P97頁(yè)第7題（4）大M法和兩階段法求解下列線性規(guī)劃問(wèn)題。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;進(jìn)行下一次迭代，以同樣的方法一直下去,其余到所求出的3W0為止，就可以得出目標(biāo)函數(shù)的最優(yōu)解：x1=4,sx4=12,sx6=12,為0時(shí)，最優(yōu)值為8。當(dāng)把M的值改為100000后，值還是一樣的，這樣就可以得出當(dāng)M為100時(shí)，已經(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萬(wàn)OM0000,000DO。25sxGu川0001加0000.001DO-0.501萬(wàn)0Sx4(f而6一口萬(wàn)足口萬(wàn)1.00-1.000.001.00|12而LowerBoundo.ouQ口口0.口口UppetBoundinfinityinfinilyiMinityUnreslrMQjp/nJ?：n|nn1圖2.3由圖2.3可知，先進(jìn)行線性規(guī)劃的第一階段，z=0x1+0x2+0x3+0sx4-Rx5+0sx6,通過(guò)迭代，滿足罰E0,且z值為零，即說(shuō)明存在一個(gè)可行解使得所有的人工變量都為零，此時(shí)x1=1,sx6=18,sx7=12,其余為0,得出z=0o接下來(lái)進(jìn)行第二階段，令z=2x1+x2+1x3+0sx4+0Rx5+0sx6+0sx7,和大M的分析方法一樣，最終將得到滿足6j<0時(shí)達(dá)到最優(yōu)解：當(dāng)x1=4,x2=0,x3=0,sx4=12,Rx5=0,sx6=12,最優(yōu)值為8。實(shí)