1、11/2/20211教案要點教案要點文文 件件 名：名：051or11.ppt051or11.ppt；第五章；第五章.xls.xls授課時間：第十一講授課時間：第十一講授課內容：授課內容：lplp問題的單純形法大問題的單純形法大m m法法, ,無解無解. .預備知識：凸集合，預備知識：凸集合，excelexcel復習可行解、基可行解，基及非基變量。復習可行解、基可行解，基及非基變量。難難 點：引入人工變量點：引入人工變量, ,解的各種情況解的各種情況. .重重 點：單純形法的步驟：引入人工變量點：單純形法的步驟：引入人工變量, ,初初始表，檢驗數，判優，進基、比值、出基、迭代，始表，檢驗數，判

2、優，進基、比值、出基、迭代，無解、無窮界的情況表上操作；利用無解、無窮界的情況表上操作；利用excelexcel。下節預習：教材第六章下節預習：教材第六章2 2 對偶理論。對偶理論。11/2/20212運籌學單純形法11/2/20213練習用圖解法和單純形法求如下線性規劃問題的最優解： max z =4 x1 + x2 x1 + 3x2 7 s.t. 4x1 + 2x2 9 x1 , x2 0 x1+3x2=7經過點(_,0)與(1,_)724x1+2x2=9經過點(2,_)與(0,_)0.54.5可行域在x1+3x2=7與4x1+2x2=9之_11/2/202140123456712345(

3、2.25,0)4x1+x2=911/2/20215填入第一個約束的數據.13107填入第二個約束的數據.4201911/2/202161310742019基基?填目標函數系數,填基變量列填基變量列,填cb列,計算計算zj,計算檢驗數j,4 1 0 0 x3x4000 0 0 0 04 1 0 011/2/2021713107420194 1 0 0 x3x4000 0 0 0 04 1 0 0最優嗎？查什么？ 不是！ 誰進基？檢驗數最大的x1進基, 誰出基？x1的系數有正的嗎？求比值？79/49/4411/2/2021813107420194 1 0 0 x3x4000 0 0 0 04 1

4、0 09/47基變量列中_換為_,x4x1改cb列,_換為_.0411/2/20219x3x44100001 3 1 0 74 2 0 1 9迭代次數基變量cbx1x2x3x4bi比 迭代次數基變量cbx1x2x3x4bi比 0zjj=cj- zj1zjj=cj- zj0 0 0 0 04 1 0 079/44 1 0 0 x3x1041 0.5 0 0.25 2.250 2.5 1 -0.25 4.754 2 0 1 90 -1 0 -111/2/202110練習用圖解法和單純形法求如下線性規劃問題的最優解： max z =4 x1 + x2 x1 + 3x2 7 s.t. 4x1 + 2x

5、2 9 x1 , x2 0可行域在直線 x1+3x2=7之_可行域在直線4x1+2x2=9之_11/2/2021110123456712345(7,0)4x1+x2=28最優解是x1=7,x2=0,此時max z=2811/2/202112標準化為:max z =4 x1+x2+0 x3+0 x4 x1 + 3x2 + x3 =7 s.t. 4x1 + 2x2 -x4 =9 x1 , x2 , x3 , x4 0基是誰?這個“-”如何處理?再引進一個“人工變量”x5+x5-mx5m是一個大的正數, x511/2/202113max z =4x1+x2+0 x3+0 x4-mx5 x1 + 3x

6、2 + x3 =7 s.t. 4x1 + 2x2 -x4+x5 =9 x1, x2 , x3 , x4 , x5 0基是誰?x3,x5x5的檢驗數為0請它出基,逼它取值為0.11/2/202114兩行，幾列? 少一列?填入第一個約束的數據.11/2/202115填入第二個約束的數據.基基?填目標函數系數,填基變量列填基變量列,填cb列,計算計算zj,計算檢驗數j,11/2/202116最優嗎？查什么？ 不是！ 誰進基?檢驗數最大的x1進基,誰出基?x1的系數有正的嗎?求比值?79/411/2/202117基變量列中_換為_,x5x1改cb列,_換為_.-m411/2/202118練習用圖解法和

7、單純形法求如下線性規劃問題的最優解： max z =4 x1 + x2 x1 + 3x2 7 s.t. 4x1 + 2x2 9 x1 , x2 0可行域在直線 x1+3x2=7之_可行域在直線4x1+2x2=9之_11/2/2021190123456712345有可行解,但無有限的最優解,z+.11/2/202120標準化為:max z=4x1+x2+0 x3+0 x4 x1 + 3x2 - x3 =7 s.t. 4x1 + 2x2 -x4 =9 x1 ,x2 ,x3 ,x4 0基是誰?這里“-”如何處理?引進兩個“人工變量” x5 ,x6+x5-mx5 -mx6m是一個大的正數(大m法),x

8、5 ,x6+x611/2/202121max 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它們的檢驗數為0請它們出基,逼它們取值為0.不能全出基,就無可行解.11/2/202122vlp問題解的幾種可能：問題解的幾種可能：11/2/202123vlp問題解的幾種可能：問題解的幾種可能： axb s.t. x011/2/202124vlp問題解的幾種可能：問題解的幾種可能：11/2/202125v第五章第五章(p.99-100)： 7a,b,c,d11/2/202