運(yùn)籌學(xué) (單純形法原理).ppt

1、復(fù)習(xí) 由圖解法得到的啟示：,1.求解線性規(guī)劃問題時，解的情況有：唯一解；無窮多最優(yōu)解；無界解；無可行解。,2.若線性規(guī)劃問題的可行域存在，則可行域是一個凸集。,3.若線性規(guī)劃問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一（有無窮多最優(yōu)解）一定是可行域的凸集的某個頂點(diǎn)。,4.解題思路是，先找出凸集的任一頂點(diǎn)，計(jì)算在頂點(diǎn)處的目標(biāo)函數(shù)值。比較周圍相鄰頂點(diǎn)的目標(biāo)函數(shù)值是否比這個值大，如果為否，則該頂點(diǎn)就是最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一，否則轉(zhuǎn)到比這個點(diǎn)的目標(biāo)函數(shù)值更大的另一頂點(diǎn)，重復(fù)上述過程，一直到找出使目標(biāo)函數(shù)值達(dá)到最大的頂點(diǎn)為止。,單純形法的計(jì)算步驟,單純形法的思路,找出一個初始可行解,是否最優(yōu),轉(zhuǎn)移到另一個

2、基本可行解 （找出更大的目標(biāo)函數(shù)值）,最優(yōu)解,是,否,循 環(huán),核心是：變量迭代,結(jié)束,如何改善？ 如何判斷沒有有限最優(yōu)解？,線性規(guī)劃問題的代數(shù)運(yùn)算形式,例：用單純形法的代數(shù)運(yùn)算形式求解下列線性規(guī)劃問題,求解步驟,（1）化為標(biāo)準(zhǔn)型,（2）找一個初始基本可行解X（0）,B0為一個可行基， x3 、 x4 、 x5為關(guān)于可行基B0的基變量， x1 、 x2 為關(guān)于可行基B0的非基變量，為求初始基本可行解，令非基變量x1 = x2 =0。從而有x3 =12， x4 =16， x5 =15，于是得到初始基本可行解：,X （0） =（0，0，12，16，15） T,其對應(yīng)的目標(biāo)函數(shù)值,z0=20+30=0

3、,（3）檢驗(yàn)X（0）是否為最優(yōu)解。由目標(biāo)函數(shù)的表達(dá)式：,z =2x1 +3x2,可知，非基變量x1 和 x2 的系數(shù)為正，如果把非基變量x1 或x2轉(zhuǎn)換為基變量，則會使目標(biāo)函數(shù)的值增加?？梢?X（0）不是最優(yōu)解,（4）第一次迭代。,每一次迭代，得到一個新的基本可行解。因此，哪些變量作為基變量，哪些非基變量，就要發(fā)生變化。,由于目標(biāo)函數(shù)中x2的系數(shù)大于x1的系數(shù)，因此，可以選擇x2使它作為基變量，而且讓它取盡可能大的值，同時， x1仍作為非基變量取值為零。從原來的基變量x3 、 x4 、 x5中選出一個作為非基變量。 x2的取值不能任意地增加，它要受到約束方程的限制：,2x1 +2x2 + x3

4、 = 12 4x1 + x4 = 16 5x2 + x5 = 15,x3 = 12 2x1 2x2 x4= 16 4x1 x5 = 15 5x2,將x1 = 0， x2 = 代入上面約束方程，為了讓取盡可能大的值，同時又要考慮到x3 、 x4 、 x5必須滿足非負(fù)約束，從而的值應(yīng)滿足：,x3 = 12 2 0 x4 = 16 0 x5 = 15 5 0,即：,x2 = =min12/2，15 /5=3,相應(yīng)地有：,x3 = 12 2 3=6 x4 = 16 x5 = 15 5 3=0,可見，從原來的基變量x3 、 x4 、 x5中選出x5作為非基變量，得第一次迭代后的基本可行解：,X （1）

5、=（0，3，6，16，0） T,其對應(yīng)的目標(biāo)函數(shù)值：,z1=20+33=9,（5）檢驗(yàn)X （1） 是否為最優(yōu)解,將約束方程組改為用非基變量x1 、 x5來表示基變量x2、 x3 、 x4的表達(dá)式?？捎酶咚瓜シǖ玫剑?2x1 + x3 2 /5x5 = 6 4x1 + x4 = 16 x2 + 1 /5 x5 = 3,移項(xiàng)后得到：,x3 = 6 2x1 + 2/5x5 x4 = 16 4x1 x2 = 3 1/5 x5,將上式代入目標(biāo)函數(shù)，得目標(biāo)函數(shù)用非基變量x1 、 x5表示的表達(dá)式,z =9+2x1 3/5x5,由于非基變量x1的系數(shù)是正數(shù)，如果把非基變量轉(zhuǎn)換為基變量，則會使目標(biāo)函數(shù)的值增

6、加?？梢奨 （1）不是最優(yōu)解。,（6）第二次迭代,和第一次迭代同樣的道理，應(yīng)選取非基變量x1使它成為基變量，而且讓它取盡可能大的值，同時， x5仍作為非基變量取值為零。從原來的基變量x2 、 x3 、 x4中選出一個作為非基變量。 x1的取值也按同樣的方法確定：,x3 = 6 2x1 + 2/5x5 x4 = 16 4x1 x2 = 3 1/5 x5,將x1 = ， x5 = 0代入：,x3 = 6 2 0 x4 = 16 4 0 x2 = 3 0,即：,x1 = =min6/2，16 /4 ，=3,相應(yīng)地有：,可見，從原來的基變量x2 、 x3 、 x4中選出x3作為非基變量，得第二次迭代后

7、的基本可行解：,X （2） =（3，3，0，4，0） T,x3 = 6 2 3 =0 x4 = 16 4 3=4 x2 = 3,其對應(yīng)的目標(biāo)函數(shù)值：,z1=23+33=15,（7）檢驗(yàn)X （2） 是否為最優(yōu)解,將約束方程組改為用非基變量x3 、 x5來表示基變量x1、 x2 、 x4的表達(dá)式?？捎酶咚瓜シǖ玫剑?x1 + 1/2 x3 1/5x5 = 3 2 x3 + x4 + 4/5x5 = 4 x2 + 1/5 x5 = 3,移項(xiàng)后得到：,x1 = 3 1/2 x3 + 1/5x5 x4 = 4 + 2 x3 4/5x5 x2 = 3 1/5 x5,將上式代入目標(biāo)函數(shù)，得目標(biāo)函數(shù)用非基變

8、量x3 、 x5表示的表達(dá)式,z =15 x3 1/5x5,這時,目標(biāo)函數(shù)中非基變量的系數(shù)都不大于零，可見目標(biāo)函數(shù)的值不可能再繼續(xù)增大,目標(biāo)函數(shù)已經(jīng)取得最大值15 ，故為X （2）最優(yōu)解。,總 結(jié),通過以上例題的分析，可以歸納出單純形法的步驟：,（1）建立實(shí)際問題的線性規(guī)劃數(shù)學(xué)模型；,（2）把一般的線性規(guī)劃問題化為標(biāo)準(zhǔn)型；,（3）確定初始基本可行解；,（4）檢驗(yàn)所得到的基本可行解是否為最優(yōu)解；,（5）迭代，求得新的基本可行解。,單純形法的三個關(guān)鍵部分：,（1）初始基本可行解的確定；,（2）最優(yōu)性檢驗(yàn)；,（3）如何進(jìn)行迭代: 確定入基變量,出基變量,單純形法一般步驟,1.初始基本可行解的確定（觀

9、察法）；,基本可行解,基,2.從約束中解出基變量；,3.代入目標(biāo)消去基變量，得到非基變量xj的檢驗(yàn)數(shù) j,4.判斷最優(yōu)； 最優(yōu)性判別定理：若 是對應(yīng)于B的基本可行解， j是用非基變量表示目標(biāo)函數(shù)的表達(dá)式 中非基變量xj的檢驗(yàn)數(shù)，若對于一 切非基變量的角指數(shù)j均有j 0 則當(dāng)前基本可行解為最優(yōu)解。,對于任意可行解X，,對于基本可行解X0，,無窮多最優(yōu)解的判定?,若對于一 切非基變量的角指數(shù)j均有j 0, 并且存在一個j =0, 則線性規(guī)劃問題有無窮多最優(yōu)解,5.沒有有限最優(yōu)解的判斷； 無最優(yōu)解判別定理：若 是對應(yīng)于B的基本可行解， 非基變量x k的檢驗(yàn)數(shù)k 0 , 且對于i=1,2,m 均有aik 0, 則原問題沒有有限最優(yōu)解。,該證明留作課后練習(xí),6.改進(jìn)目標(biāo) 若k 0，則選xk進(jìn)基; 用最小比值法確定xk的最大值， 使基變量xl取0值，其它基變量非負(fù)；,即xl出基，換基過程 若不存在, 則Z，沒有有限最優(yōu)解。,7.主元變換（樞變換或旋轉(zhuǎn)變換） xk進(jìn)基， xl出基，解出新的基變量,表格單純形法,標(biāo)準(zhǔn)型：,表格單純形法,標(biāo)準(zhǔn)型：,表格單純形法,表格單純形法,基變量,檢驗(yàn)數(shù),最小比值列,基變量系數(shù),右端常數(shù),表格單純形法,例5 用單純形法求解線性規(guī)劃問