運籌學(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實驗（或算法）原理：1.大 M 法思路：在單純形法的基礎(chǔ)上，為了使解線性規(guī)劃有一個統(tǒng)一的解法，我們把所有求目標(biāo)函數(shù)最小值的問題化為求目標(biāo)函數(shù)最大值的問題。只要把目標(biāo)函數(shù)乘以-

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

4、來的目標(biāo)函數(shù)，把此可行解作為初始解進行計算，接下來的計算和單純形法計算原理是一樣的。實驗硬件及軟件平臺：PC 機， Tora 軟件， Internet 網(wǎng)。3實驗步驟：大 M 法步驟：1.打開 TORA 命令窗口；2.選擇 Linear programming->Select input mode->Go to input screen;3.輸 入待解的 方程組 - Slolve menu->Solveproblem->Algebraic->Iterations-M-method-輸入值 - 點擊 Go To Output Format Screen- 點擊 Go

5、 To Output Screen- 點擊 All lterations 。4.得出運行結(jié)果。5.改變 3 步驟中的值（例100 改為 100000），再按之后的步驟運行，得出結(jié)果。6.觀察對比結(jié)果。兩階段法步驟：1）打開 TORA 命令窗口；2）選擇 Linear programming->Select input mode->Go to input screen；3) 輸 入待 解的 方程組 - Slolve menu->Solveproblem->Algebraic->Iterations-Two-phase method- 點擊 Go To Output

6、Format Screen- 點擊 All lterations ；4)得出運行結(jié)果。4實驗內(nèi)容（包括實驗具體內(nèi)容、算法分析、源代碼等等）：1.書上 P97 頁第 6 題：用大 M 法和兩階段法求解下列線性規(guī)劃問題。maxz=5x1x 2 3x 3；約束條件： x14x 22x 310 ，x1- 2x 2x 316.A：大M法圖 1.15圖 1.2由上面的結(jié)果可知，滿足所求出的j0 ，得出目標(biāo)函數(shù)的最優(yōu)解x1=16 ，x2=0 ，x3=0 ，sx4=16， Rx5=0， sx=0，最優(yōu)值是 80。當(dāng)把 M 的值改為 100000 后，值還是一樣的，這樣就可以得出當(dāng)M 為 100 時，已經(jīng)得出有

7、效解。6B：兩階段法7圖 1.3由圖 1.3 可知，先進行線性規(guī)劃的第一階段，滿足j 0 ，且 z 值為零，即說明存在一個可行解使得所有的人工變量都為零，此時x2=2.5，sx6=21，其余為 0 得出 z=0。接下來進行第二階段，令z=5x1+x2+3x3-0sx4+0Rx5+0sx6 ，和大 M 的分析方法一樣，最終將得到滿足j0 時達到最優(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= 2x1x 2 x 3；約束條件： 4x12x 22x 34，2x

8、14x 220，4x18x 22x316，A：大M法8圖 2.1圖 2.2由上面的圖2.1可知，首先先輸入數(shù)據(jù)即線性規(guī)劃的系數(shù)如圖2.1 所示令 maxz= 2x 1 x 2x 3 -0sx4+0sx6+0sx7-MRx5 ； 進行下一次迭代，以同樣的方法一直下去，直到所求出的j為止 ，就可以得出目標(biāo)函數(shù)的最優(yōu)解： x1=4 ，sx4=12，sx6=12，其0余為 0 時，最優(yōu)值為 8。當(dāng)把 M 的值改為 100000 后，值還是一樣的，這樣就可以得出9當(dāng) M 為 100 時，已經(jīng)得出有效解。B：兩階段法圖 2.310由圖 2.3 可知，先進行線性規(guī)劃的第一階段，z=0x1+0x2+0x3+0

9、sx4-Rx5+0sx6 ， 通過迭代，滿足j0 ，且 z 值為零，即說明存在一個可行解使得所有的人工變量都為零，此時 x1=1 ，sx6=18， sx7=12，其余為 0，得出 z=0 。接下來進行第二階段，令z=2x1+x2+1x3+0sx4+0Rx5+0sx6+0sx7 ，和大 M 的分析方法一樣，最終將得到滿足j0時達到最優(yōu)解：當(dāng)x1=4 ，x2=0 ，x3=0，sx4=12 ，Rx5=0， sx6=12，最優(yōu)值為 8。11實驗結(jié)果與討論：1.首先找出一個初始基本可行解，然后進行最優(yōu)性檢驗， 基變化的步驟， 最后得到結(jié)果。同時學(xué)會了用Tora 軟件求解線性規(guī)劃問題，并在求解過程中學(xué)會理解每一步迭代計算中進基與出基變量。2.為了構(gòu)造初始可行基得到初始可行解，把人工變量”強行”的加到原來的