【正文】 a6/a12→ a10 a6≥0 → a1 ≤ 0 2022/2/16 81 課后作業(yè) P43 。 2022/2/16 76 （第二階段）單純形表 2 cj 3 0 1 0 0 CB XB bi x1 x2 x3 x4 x5 θ 0 x4 0 0 0 0 1 1/2 0 x2 3 0 1 1/3 0 0 3 x1 1 1 0 2/3 0 1/2 σj 0 0 3 0 3/2 [ ] 9 3/2 [ ] 0 X4 0 X2 1 x3 5/2 1/2 1 0 0 1/4 0 0 0 0 1 1/2 3/2 3/2 0 1 0 3/4 x3入， x1出 σj 9/2 0 0 0 3/4 所以： X*=(x2,x3,x4)T=(5/2,3/2,0)T Z*=3/2 2022/2/16 77 ? 目標函數(shù)極小化時解的最優(yōu)性判別； ? 退化解的判別； ? 無可行解的判別； ? 無界的判別； ? 無窮多最優(yōu)解的判別； ? 唯一最優(yōu)解的判別 . 三、單純形法計算中的幾個問題 當所有非基變量的 σj≥0時為最優(yōu)解； 最優(yōu)解中基變量有取值為 0的值時； 最優(yōu)解中人工變量為非 0的基變量時； 存在某個 σk0，且所有的 aik≤0時； 得最優(yōu)解時，有檢驗數(shù)為 0的非基變量； 得最優(yōu)解時，所有非基變量檢驗數(shù)為負； 2022/2/16 78 cj 40 45 25 0 0 CB XB bi x1 x2 x3 x4 x5 θ 0 x3 100 2 3 1 1 0 0 x4 120 3 3 2 0 1 σj 40 45 0 25 100/3 40 [ 3 ] 45 X2 25 x3 80/3 1/3 1 0 2/3 1/3 20 1 0 1 1 1 x2入， x3出 σj 0 0 0 5 因為 σj全 ≥0, 且 σ1=0,則有無窮多最優(yōu)解。 2022/2/16 74 求解輔助問題，得到輔助問題的最優(yōu)解 引進人工變量 x6， x7，構(gòu)造輔助問題，輔助問題的目標函數(shù)為所有人工變量之和的極小化 MaxW=0? 原問題沒有可行解。 ? 當?shù)谝浑A段中目標函數(shù)的最優(yōu)值＝ 0，既人工變量＝ 0，則轉(zhuǎn)入第二階段；若第一階段中目標函數(shù)的最優(yōu)值不等于 0，既人工變量不等于 0，則判斷原問題為無解。 2022/2/16 71 MaxZ=3x1+x3 x1+ x2+ x3≤4 2x1+ x2 x3≥1 3x2+x3=9 xi ≥0,j=1,2,3 增加人工變量后，線性規(guī)劃問題中就存在一個 B為單位矩陣， 后面可以根據(jù)我們前面所講的單純形法來進行求解。 （ 4）當存在 σj0時，且有 aik0,繼續(xù)第三步； 計 算非基 變 量 檢驗數(shù)用 jjm1iijijj Zcaccσ ???? ??2022/2/16 66 三 .基變換 ? ?轉(zhuǎn)第二步；，得一新的基可行解，為主元進行初等行變換以為換出變量，則＝若比值為換入變量，計算最小則lkllklikikikjjaxabaabxM a x,0m i n0|σk??????????????????用用單純形法按上述步驟求解時，可采用表格形式，這樣更直觀，易于避免錯誤，該表格稱為單純形表。 （ 2）當所有 σj≤ 0 且 存在 σj＝ 0（ j=m+1,… ,n)時，則已得最優(yōu)解，且有無窮多最優(yōu)解，計算終止。目標函數(shù)需要減去罰因子。 為了不改變問題的性質(zhì)，對引入人工變量 Xi” 的線性規(guī)劃問題，需要在目標函數(shù)中減去 MXi” ,M為足夠大的正數(shù)，稱罰因子，促使 Xi” 最終必為 0。 2022/2/16 64 一 .求初始基可行解 “ ≤” 時，直接在約束不等式左邊加上非負的松弛變量，使約束方程的系數(shù)矩陣很容易找到一個單位矩陣，求出一個初始基可行解。 轉(zhuǎn) STEP 3。 如果 有某非基變量檢驗數(shù)為正，且工藝系數(shù)全非正，則無界， 運算終止 。 ； 如果 有為 0的非基變量檢驗數(shù)，則有 無窮多最優(yōu)解 。 轉(zhuǎn) STEP 2。 轉(zhuǎn)STEP 1。139。239。ln39。39。239。39。 ? 換出變量的確定 令 xk=θ0,xj=0,j=m+1,…,n,j ≠k 則 xi=biaik θ≥0， i=1,…,m 當 aik ≤0時， θ可任取； 當 aik 0時， θ lklikikiikiabaabmiab ??????? ??? 0|m i n,1, ??則 xl為換出變量。 該問題無界為一可行解證明：令??????????????????????????????)1(0010)1()1(,1,1,00CXMMZxZxZCXXmixabxkjnmjxMxkkknmjjjkikiijk????（ 4） 因為所有 Xj≥0，當存在 σj0時，則該基可行解不是最優(yōu)解，需要尋找另一個基可行解； 2022/2/16 59 ? 變換目的 ：使目標函數(shù) Z值得到改善，接近最優(yōu)解，一次基變換，是從該頂點到相鄰頂點，即一次基變換僅變換一個基變量。（可行，基解，最優(yōu)） ?????????????????????????????????njxbxaxaxbxaxaxbxaxaxxcxcxcM a x Zjmnmnmmmmnnmmnnmmnn,2,10112211221111112211??????mmTmTmBbcbcbcZbbbxxxX?????????221102121 ),(),(則基解，可行解 2022/2/16 57 Zmixaxabx ninmimii 代入目標函數(shù),1,11 ?? ????? ??非基變量檢驗數(shù) ?? ??? ??????? ??? ???????????????????????????????????????nmjjjjnmjmiijijmiiiminmjjijinmjjjmiiinnmmnmnmmmmmnnmmnnmmnnxZxaccbcxacxcbcxcxcxaxabcxaxabcxaxabcxcxcxc101 111 11111112112221111112211)()()()(???????2022/2/16 58 由檢驗數(shù)可以判斷解的最優(yōu)性情況 （ 1）因為所有 Xj≥0 ，當所有 σ j0時，則 Z≤ Z0,則該基可行解對應最優(yōu)解； （ 2）因為所有 Xj≥0 ，當 σ j≤ 0 且 存在 σ j＝ 0（ j=m+1,?,n) 時，則該線性規(guī)劃問題有無窮多最優(yōu)解。 X0為 LP的最優(yōu)解， Z*=CX0，如果 X0不是基可行解，則定有 X(1)＝ X0ta , X(2)=X0+ta為可行解，則有 CX(1)=CX0+tCa≤CX0 CX(2)=CX0tCa≤CX0 則必有 tCa=0 所以 X0 ， X(1) ， X(2)均為最優(yōu)解，如果 X(1) ， X(2)不是基可行解，繼續(xù)下去，則必可以找到基可行解為最優(yōu)解。 ???????????????????線性無關mTmTmPPPbAXbAXbAXXXXXXX,)0,0,()0,0,(21)2()1(0)2()2(1)2()1()1(1)1(?????0, )2()1(0 ?均，又因 XXX)2()1(0 XXX ??所以 X不能表示成可行域中另外兩點的凸組合，與假設相矛盾，則 X必為可行域的頂點。 2022/2/16 54 2）假設 X0是基可行解， X0不是頂點。 ? ?)2()1()2()1( ,0,/XXCXCXXbAXXC??????且證明：令可行域??????????????00 )2()2()1()1(XbAXXbAX則10)1( )2()1( ????? ??? XXX令：bAXAXAXXXA ??????? )2()2()1()2()1( ))1(( ????AX則為凸集CCX ???2022/2/16 53 定理 2： 線性規(guī)劃問題的基可行解 X對應線性規(guī)劃問題可行域的頂點。 ? 對任何 x1 ∈C ， x2 ∈C ，不存在 x=α x1 ＋（ 1－ α ） x2(0＜ α ＜ 1)，則稱 x為凸集的頂點。 ，基變量，非基變量；基解，基可行解，可行基 ??????????mjmimiiijnjxxx,1,0,111??? ??2022/2/16 49 max z=x1+2x2 . x1+x2?3 x2 ?1 x1, x2 ?0 max z=x1+2x2 . x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x4?0 x1=0, x2=0 x3=3, x4=1 基可行解 x1=0, x4=0 x2=1, x3=2 基可行解 x2=0, x3=0 x1=3, x4=1 基可行解 x3=0, x4=0 x1=2, x2=1 基可行解 x1=0, x3=0 x2=3, x4=2 是基解，但不是可行解 O A B x3=0 x4=0 x2=0 x1=0 C D 可行域 2022/2/16 50 =2x1+3x2 x1 +x3＝ 5 x1+2x2 +x4 ＝ 10 x2 + x5 ＝4 xi ≥0 x1 x2 x3 x4 x5 Z 是否為基可行解 1 0 0 5 10 4 5 √ 2 0 4 5 2 0 17 √ 3 5 0 0 5 4 10 √ 4 0 5 5 0 － 1 20 5 10 0 － 5 0 4 15 6 5 0 0