【正文】 0 1 Z 3 4 1 0 1 7 x5 1 x1 x2 x3 x4 x5 b XB CB Θ 5 2 3 1 1 C 30 換入變量 ， 換出變量 ， ２為主元進行旋轉變換 3x 4x基本可行解 ， Z= 15， X = ( 0 , 0 , 4 , 0 , 3 ) T1/2 1 1 1/2 0 4 x3 3 1 4 0 2 0 15 Z 5/2 3 0 1/2 1 3 x5 1 x1 x2 x3 x4 x5 b XB CB Θ 5 2 3 1 1 C 1 2 2 1 0 8 x4 1 3 0 4 0 0 1 Z 3 4 1 0 1 7 x5 1 x1 x2 x3 x4 x5 b XB CB Θ 5 2 3 1 1 C 8/2 7/1 31 最優(yōu)解 最優(yōu)值 6 1 7X , 0 , , 0 , 055T? ??? ???? 換入變量 ， 換出變量 ， ５ /２為主元進行旋轉變換 1x 5xN N Bσ = C C N 0? 81Z5? ?4/1/2 1/2 1 1 1/2 0 4 x3 3 1 4 0 2 0 15 Z 3/5/2 5/2 3 0 1/2 1 3 x5 1 x1 x2 x3 x4 x5 b XB CB Θ 5 2 3 1 1 C 0 2/5 1 3/5 1/5 17/5 x3 3 0 26/5 0 9/5 2/5 81/5 Z 1 6/5 0 1/5 2/5 6/5 x1 5 x1 x2 x3 x4 x5 b XB CB Θ 5 2 3 1 1 C 32 例 用單純形方法求解線性規(guī)劃問題 解：本題的目標函數(shù)是求極小化的線性函數(shù)， 可以令 則 這兩個線性規(guī)劃問題具有相同的可行域和最優(yōu)解， 只是目標函數(shù)相差一個符號而已。 當Ｂ =Ｉ時 ， Ｂ 1=Ｉ ， 易知： 1N N Bσ =C C B N1BZ =C B b?N N Bσ =C C N BZ=C b28 可將這些重要結論的計算設計成如下一個簡單的表格 ， 即單純形表來完成： C CB CN θ CB XB b X1 X2 ? 每一個基本可行解所對應的目標函數(shù)值 通過目標函數(shù)值可以觀察單純形法的每次迭代是否能使目標函數(shù)值有效地增加 ， 直至求得最優(yōu)目標函數(shù)為止 。X = X = ( , 0 , , 0 , 0 )55T* 81Z=52B3B N 4N152 3 1 1 7xC = ( 3 ,5 )x 10 5 5 5 5X = ,X = x ,B = ,N = , ,b =C = ( 2 , 1 ,1 )x 0 1 6 1 2 6x5 5 5 5? ? ? ???? ? ? ??? ????? ? ? ??? ????? ? ? ????? ??? ? ? ???? ? ? ?27 ?表格單純形法 通過例１我們發(fā)現(xiàn) ， 在單純形法的求解過程中 ， 有下列重要指標： ? 每一個基本可行解的檢驗向量 根據(jù)檢驗向量可以確定所求得的基本可行解是否為最優(yōu)解 。X = ( , 0 , , 0 , 0 )55T* 6 1 739。 檢驗向量 因為所有檢驗數(shù)均小于零， 所以 是最優(yōu)解， 1N N B2 4 52 3 15 5 5σ =C C B N =( 2, 1,1) (3,5)6 1 25 5 536 4 7 26 9 2=( 2, 1,1) ( , , ) =( , , )5 5 5 5 5 5 σ σ σ???????????????6 1 739。X1x5x11111 1 0 41 1 0 4 2222665 1 21103 0 1 35 5 5 5223 1 72 101 5 5 5 5 66 1 2105 5 5 5???????????????????? ???? ???????????????????????13BB N 25N411x1x C = ( 3 , 1 )1 0 422X = , X = x , B = , N = , , b =x C = ( 5 , 2 , 1 )0 1 5 1 33x22???????? ? ? ? ??????? ? ? ? ???? ? ? ? ? ??? ????????第二行乘以２ /５ 第一行減以第二行的１ /２倍 25 —————————————————————————— 可得改進的基本可行解 。 ② 選取換出變量 且 ， 選取 為換出變量 . 4 3 3m i n ,1 / 2 5 / 2 5 / 2?? ?????X = ( 0 , 0 , 4 , 0 , 3 ) T11114 2B b = , B P 0352??????????????? ? ? ?????1 10? ?? 1x5x13BB N 25N411x1x C = ( 3 , 1 )1 0 422X = , X = x , B = , N = , , b =x C = ( 5 , 2 , 1 )0 1 5 1 33x22???????? ? ? ? ??????? ? ? ? ???? ? ? ? ? ??? ????????3 1 11 1 15x 4 1 / 2= B b B P x = xx 3 5 / 2?? ? ? ? ??? ? ? ? ?? ? ? ???24 （ 4） 求改進了的基本可行解 對約束方程組的增廣矩陣施以初等行變換 ， 使換入變量 所對應 的系數(shù)列向量 變換成換出變量 所對應的單位向量 , 112P=52????????????50P1???????39。 檢驗向量 因為 ， 所以 仍不是最優(yōu)解。 ， 基變量 ， 非基變量 。 32P=1?????? 41P0???????50P=1?????? 11 1 1 0 41 2 2 1 0 8 223 4 1 0 1 73 4 1 0 1 7111 1 0 422 5 13 0 1 322??????????????????????????????????????? 39。 X = ( 0 , 0 , 0 , 8 , 7 ) T 1N N B1 2 31 2 2σ =C C B N=( 5,2, 3) (1,1)3 4 1=( 5,2, 3) ( 2,2, 1)= ( 3, 0 , 4) σ σ σ?????????14BB N 25N3xx C = ( 1 ,1 )1 0 1 2 2 8X = ,X = x ,B = ,N = , ,b =x C = ( 5 ,2 ,3 )0 1 3 4 1 7x???? ? ? ? ? ? ????? ? ? ? ? ? ???? ? ? ? ? ??? ????X = ( 0 , 0 , 0 , 8 , 7 ) T19 （ 3） 基本可行解 的改進 ① 選取換入變量 因為 max{3， 4}=4，取 x3為換入變量。 4510B = ( P P ) =01??????45x ,x 1 2 3x ,x , x14BB N 25N3xx C = ( 1 ,1 )1 0 1 2 2 8X = ,X = x ,B = ,N = , ,b =x C = ( 5 ,2 ,3 )0 1 3 4 1 7x???? ? ? ? ? ? ????? ? ? ? ? ? ???? ? ? ? ? ??? ????1NB8X = 0 X = B b=7? ???? ????X = ( 0 , 0 , 0 , 8 , 7 ) T1B8Z =C B b=( 1,1) 17? ?? ??????18 (2) 檢驗 是否最優(yōu)。X17 1 2 3 4 51 2 3 41 2 3 51 2 3 4 5m a xZ =5 x 2x 3x x xx 2x 2x x 83x 4x x x 7 x ,x ,x ,x ,x 0? ? ? ?? ? ? ???? ? ? ??? ??1 2 2 1 0A=3 4 1 0 1??????8b7???????C = ( 5 , 2 , 3 , 1 , 1 )?例 1 解： (１ )確定初始的基本可行解。 由于行初等變換后的方程組 與原約束方程組 或 同解 B 1 1NX( I , B N ) = B bX??????AX=b39。這些基變量的系數(shù)列向量是單位矩陣 I中的單位向量。變換的結果是將系數(shù)矩陣Ａ中的可行基Ｂ變換成單位矩陣 I，把非基變量系數(shù)列向量構成的矩陣Ｎ變換成 ，把資源向量 b變換成 。 可得基本可行解 。 1BbX= 0???????1 m + kB P 0?m +k 0? ?證：令 ，則得新的可行解 將上式代入 因為