運籌學(xué)單純形法的例題

1、01.04.2021,運籌學(xué)單純形法,1,教案要點,文 件 名：051OR11.PPT；第五章.XLS 授課時間：第十一講 授課內(nèi)容：LP問題的單純形法大M法,無解. 預(yù)備知識：凸集合，Excel 復(fù)習(xí)可行解、基可行解，基及非基變量。 難 點：引入人工變量,解的各種情況. 重 點：單純形法的步驟：引入人工變量,初始表，檢驗數(shù)，判優(yōu)，進基、比值、出基、迭代，無解、無窮界的情況表上操作；利用Excel。 下節(jié)預(yù)習(xí)：教材第六章2 對偶理論。,01.04.2021,運籌學(xué)單純形法,2,運籌學(xué)單純形法,01.04.2021,運籌學(xué)單純形法,3,練習(xí)用圖解法和單純形法求如下線性規(guī)劃問題的最優(yōu)解： Max

2、z =4 x1 + x2 x1 + 3x2 7 s.t. 4x1 + 2x2 9 x1 , x2 0,x1+3x2=7經(jīng)過點(_,0)與(1,_),7,2,4x1+2x2=9經(jīng)過點(2,_)與(0,_),0.5,4.5,可行域在x1+3x2=7與4x1+2x2=9之_,下,01.04.2021,運籌學(xué)單純形法,4,練習(xí)用圖解法,0,1,2,3,4,5,6,7,1,2,3,4,5,(2.25,0),4x1+x2=9,01.04.2021,運籌學(xué)單純形法,5,練習(xí). 單純形表,填入第一個約束的數(shù)據(jù).,1,3,1,0,7,填入第二個約束的數(shù)據(jù).,4,2,0,1,9,01.04.2021,運籌學(xué)單純形

3、法,6,練習(xí). 單純形表,基?,填目標(biāo)函數(shù)系數(shù),填基變量列,填CB列,計算Zj,計算檢驗數(shù)j,4 1 0 0,x3 x4,0 0,0 0 0 0 0,4 1 0 0,01.04.2021,運籌學(xué)單純形法,7,練習(xí). 單純形表,最優(yōu)嗎？,查什么？,不是！,誰進基？,檢驗數(shù)最大的x1進基,誰出基？,x1的系數(shù)有正的嗎？,求比值？,7,9/4,9/4,4,01.04.2021,運籌學(xué)單純形法,8,練習(xí). 單純形表,基變量列中_換為_,x4,x1,改CB列,_換為_.,0,4,Excel,01.04.2021,運籌學(xué)單純形法,9,練習(xí)用單純形法,x3,x4,4,1,0,0,0,0,1 3 1 0 7,

4、4 2 0 1 9,0 0 0 0 0,4 1 0 0,7,9/4,4 1 0 0,x3,x1,0,4,1 0.5 0 0.25 2.25,0 2.5 1 -0.25 4.75,4 2 0 1 9,0 -1 0 -1,01.04.2021,運籌學(xué)單純形法,10,練習(xí)用圖解法和單純形法求如下線性規(guī)劃問題的最優(yōu)解： Max z =4 x1 + x2 x1 + 3x2 7 s.t. 4x1 + 2x2 9 x1 , x2 0,可行域在直線 x1+3x2=7之_,下,可行域在直線4x1+2x2=9之_,上,01.04.2021,運籌學(xué)單純形法,11,練習(xí)用圖解法,0,1,2,3,4,5,6,7,1,2

5、,3,4,5,(7,0),4x1+x2=28,最優(yōu)解是x1=7,x2=0,此時Max z=28,01.04.2021,運籌學(xué)單純形法,12,練習(xí).用單純形法,基是誰?,這個“-”如何處理?,再引進一個“人工變量”x5,+x5,-Mx5,M是一個大的正數(shù),(大M法), x5,01.04.2021,運籌學(xué)單純形法,13,練習(xí).用單純形法,Max z =4x1+x2+0 x3+0 x4-Mx5 x1 + 3x2 + x3 =7 s.t. 4x1 + 2x2 -x4+x5 =9 x1, x2 , x3 , x4 , x5 0,基是誰?,x3,x5,x5的檢驗數(shù)為0,請它出基,逼它取值為0.,01.04

6、.2021,運籌學(xué)單純形法,14,練習(xí). 單純形表,兩行，幾列?,少一列?,填入第一個約束的數(shù)據(jù).,01.04.2021,運籌學(xué)單純形法,15,練習(xí). 單純形表,填入第二個約束的數(shù)據(jù).,基?,填目標(biāo)函數(shù)系數(shù),填基變量列,填CB列,計算Zj,計算檢驗數(shù)j,01.04.2021,運籌學(xué)單純形法,16,練習(xí). 單純形表,最優(yōu)嗎？,查什么？,不是！,誰進基?,檢驗數(shù)最大的x1進基,誰出基?,x1的系數(shù)有正的嗎?,求比值?,7,9/4,01.04.2021,運籌學(xué)單純形法,17,練習(xí). 單純形表：迭代,基變量列中_換為_,x5,x1,改CB列,_換為_.,-M,4,Excel,01.04.2021,運籌

7、學(xué)單純形法,18,練習(xí)用圖解法和單純形法求如下線性規(guī)劃問題的最優(yōu)解： Max z =4 x1 + x2 x1 + 3x2 7 s.t. 4x1 + 2x2 9 x1 , x2 0,可行域在直線 x1+3x2=7之_,上,可行域在直線4x1+2x2=9之_,上,01.04.2021,運籌學(xué)單純形法,19,練習(xí)用圖解法,0,1,2,3,4,5,6,7,1,2,3,4,5,有可行解,但無有限的最優(yōu)解,z+.,01.04.2021,運籌學(xué)單純形法,20,練習(xí).用單純形法,基是誰?,這里“-”如何處理?,引進兩個“人工變量” x5 ,x6,+x5,-Mx5 -Mx6,M是一個大的正數(shù),(大M法),x5

8、,x6,+x6,01.04.2021,運籌學(xué)單純形法,21,練習(xí).用單純形法,Max z=4x1+x2+0 x3+0 x4 -Mx5 Mx6 x1+3x2-x3 +x5 =7 s.t. 4x1+2x2 -x4 +x6=9 x1,x2,x3,x4 ,x5,x6 0,基是誰?,x5,x6,它們的檢驗數(shù)為0,請它們出基,逼它們?nèi)≈禐?.,Excel,不能全出基,就無可行解.,01.04.2021,運籌學(xué)單純形法,22,解LP問題單純形法,LP問題解的幾種可能：,唯一解 無窮多解,有解,無解,無有限最優(yōu)解 無可行解,01.04.2021,運籌學(xué)單純形法,23,解LP問題單純形法,LP問題解的幾種可能：

9、,無需引入人工變量.一定有可行解,從而一定有基可行解,但還有可能有無窮最優(yōu)解或無有限最優(yōu)解.,01.04.2021,運籌學(xué)單純形法,24,解LP問題單純形法,LP問題解的幾種可能：,一般要引入人工變量.,人工變量不能全出基則無可行解,更無最優(yōu)解.,不需人工變量或人工變量可以全部出基則必有可行解.分: 至少有一個非基變量的檢驗數(shù)為正,但它的系數(shù)全為非正,則無有限最優(yōu)解； 所有非基變量的檢驗數(shù)全為非正，已有最優(yōu)解，但若其中至少有一個的檢驗數(shù)為0，且它的系數(shù)中有正的，則可能有無窮多個最優(yōu)解。,01.04.2021,運籌學(xué)單純形法,25,作業(yè),第五章(P.99-100)： 7a,b,c,d,預(yù)習(xí)第六章2