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

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

2、把目標(biāo)函數(shù)乘以-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)造初始可行基得到初始可行解，把人工變量”強(qiáng)行”的加到原來的約束方程

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

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

5、s。4. 得出運(yùn)行結(jié)果。5. 改變3步驟中的值（例100改為100000），再按之后的步驟運(yùn)行，得出結(jié)果。6. 觀察對比結(jié)果。兩階段法步驟：1）打開TORA命令窗口；2）選擇Linear programming-Select input mode-Go to input screen；3)輸入待解的方程組-Slolve menu -Solve problem-Algebraic-Iterations-Two-phase method-點(diǎn)擊Go To Output Format Screen- 點(diǎn)擊All lterations；4)得出運(yùn)行結(jié)果。 實(shí)驗(yàn)內(nèi)容（包括實(shí)驗(yàn)具體內(nèi)容、算法分析、源代碼等等

6、）：1. 書上P97頁第6題：用大M法和兩階段法求解下列線性規(guī)劃問題。 max z=5 約束條件：， A：大M法 圖1.1 圖1.2由上面的結(jié)果可知， 滿足所求出的，得出目標(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)得出有效解。 B：兩階段法 圖1.3 由圖1.3可知，先進(jìn)行線性規(guī)劃的第一階段，滿足，且z值為零，即說明存在一個可行解使得所有的人工變量都為零，此時x2=2.5，sx6=21，其余為0得出z=0。接下來進(jìn)行第二階段，令z=5x1+x2+3x3-0sx4+

7、0Rx5+0sx6，和大M的分析方法一樣，最終將得到滿足時達(dá)到最優(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ī)劃問題 。 max z=約束條件： A：大M法 圖2.1 圖2.2由上面的圖2.1可知，首先先輸入數(shù)據(jù)即線性規(guī)劃的系數(shù)如圖2.1所示令max z=-0sx4+0sx6+0sx7-MRx5； 進(jìn)行下一次迭代，以同樣的方法一直下去，直到所求出的，就可以得出目標(biāo)函數(shù)的最優(yōu)解：x1=4，sx4=12，sx6=12，其余為0時，最優(yōu)值為8。當(dāng)把M的值改為100000后，值還是一樣的，這樣就可以得

8、出當(dāng)M為100時，已經(jīng)得出有效解。 B：兩階段法 圖2.3由圖2.3可知，先進(jìn)行線性規(guī)劃的第一階段，z=0x1+0x2+0x3+0sx4-Rx5+0sx6， 通過迭代，滿足，且z值為零，即說明存在一個可行解使得所有的人工變量都為零，此時x1=1，sx6=18，sx7=12，其余為0，得出z=0。接下來進(jìn)行第二階段，令z=2x1+x2+1x3+0sx4+0Rx5+0sx6+0sx7，和大M的分析方法一樣，最終將得到滿足時達(dá)到最優(yōu)解：當(dāng)x1=4，x2=0，x3=0，sx4=12，Rx5=0，sx6=12，最優(yōu)值為8。實(shí)驗(yàn)結(jié)果與討論： 1.首先找出一個初始基本可行解，然后進(jìn)行最優(yōu)性檢驗(yàn)，基變化的步驟，最后得到結(jié)果。同時學(xué)會了用Tora軟件求解線性規(guī)劃問題，并在求解過程中學(xué)會理解每一步迭代計(jì)算中進(jìn)基與出基變量。 2.為了構(gòu)造初始可行基得到初始可行解，把人工變量”強(qiáng)行”的加到原來的約束方程中去，又為了盡力地把人工變量從基變量中替換出來就令人工變量在求最大的目標(biāo)函數(shù)里的系數(shù)為-M