【文章內(nèi)容簡介】 σ σ σ???????????????6 1 739。39。X = ( , 0 , , 0 , 0 )55T* 6 1 739。39。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)解 。 如果不是最優(yōu)又可以通過檢驗向量確定合適的換入變量 。 ? 每一個基本可行解所對應的目標函數(shù)值 通過目標函數(shù)值可以觀察單純形法的每次迭代是否能使目標函數(shù)值有效地增加 ， 直至求得最優(yōu)目標函數(shù)為止 。 ?在單純形法求解過程中 ， 每一個基本可行解Ｘ都以 某個經(jīng)過初等行變換的 約束方程組中的單位矩陣 Ι 為可行基 。 當Ｂ =Ｉ時 ， Ｂ 1=Ｉ ， 易知： 1N N Bσ =C C B N1BZ =C B b?N N Bσ =C C N BZ=C b28 可將這些重要結(jié)論的計算設計成如下一個簡單的表格 ， 即單純形表來完成： C CB CN θ CB XB b X1 X2 Xm X m+1 Xm+2 Xn C1 C2 . . Cm X1 X2 . Xm b1 b2 . . bm I N θ1 θ2 . . θm Z CBb 0 CN CBN 29 例 試利用單純形表求例 1中的最優(yōu)解解： 得初始的單純形表： C = ( 5 , 2 , 3 , 1 , 1 )?1 2 2 1 0 8( A b ) =3 4 1 0 1 7??????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? ? ? ?? ? ? ???? ? ? ??? ??N N Bσ =C C NBZ=C b 初始基本可行解 ， Z= 1， X = ( 0 , 0 , 0 , 8 , 7 ) T 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 30 換入變量 ， 換出變量 ， ２為主元進行旋轉(zhuǎn)變換 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? ??? ???? 換入變量 ， 換出變量 ， ５ /２為主元進行旋轉(zhuǎn)變換 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ù)相差一個符號而已。 1213241 2 5jm i nZ = x 2xx x 4x x 3x 2x x 8x 0 j 1,2,3, 4,5????????? ? ??? ???，1239。Z = Z = x + 2 x39。1 2 1 2m i nZ = x 2x m a x x +2xZ??33 0 1 0 1 0 3 x2 2 0 0 1 2 1 2 x3 0 0 1 0 1 0 3 x2 2 4/1 1 0 1 0 0 4 x3 0 3/1 0 1 0 1 0 3 x4 0 _ 1 0 1 0 0 4 x3 0 0 0 0 0 1 8 Z’ 1 0 0 2 1 2 x1 1 1 0 0 2 0 6 Z’ 2/1 1 0 0 2 1 2 x5 0 1 2 0 0 0 0 Z’ 8/2 1 2 0 0 1 8 x5 0 x1 x2 x3 x4 x5 b XB CB Θ 1 2 0 0 0 C 最優(yōu)解 最優(yōu)值 ? ?X 2 , 3 , 2 , 0 , 0 T? ? 39。m a x Z = 8 o r m i n Z = 82/2 3/1 34 因為非基變量 x4的檢驗數(shù) σ 4=0， 由無窮多最優(yōu)解判別定理 ， 本例的線性規(guī)劃問題存在無窮多最優(yōu)解 。 事實上若以 x4為換入變量 ， 以 x3為換出變量 ， 再進行一次迭代 ， 可得一下單純形表： 最優(yōu)解 最優(yōu)值 最優(yōu)解的一般表示式 39。m a x Z = 8 o r m i n Z = 8? ?X 4 , 2 , 0 , 1 , 0 T? ?? ?X ( 2 , 3 , 2 , 0 , 0 ) ( 1 ) 4 , 2 , 0 , 1 , 0 , 0 1 .TT? ? ?? ? ? ? ? ?C 1 2 0 0 0 Θ CB XB b x1 x2 x3 x4 x5 0 2 1 x4 x2 x1 1 2 4 0 0 1/2 1 1/2 0 1 1/2 0 1/2 1 0 1 0 0 Z’ 8 0 0 0 0 1 35 對于極小化的線性規(guī)劃問題的處理： ? 先化為標準型 ， 即將極小化問題變換為極大化問題 ， 然后利用單 純形方法求解 ． ? 直接利用單純形方法求解 ， 但是檢驗是否最優(yōu)的準則有所不同 ， 即： 若某個基本可行解的所有非基變量對應的檢驗數(shù) （ 而不是 ≤ ０ ） ， 則基本可行解為最優(yōu)解 ． 否則采用最大減少原則 （ 而非最大增加原則 ） 來確定換入變量 ， 即： 若 則選取對應的非基變量 xm+k為換入變量． ? 確定了換入變量以后，換出變量仍采用最小比值原則來確定。 N N Bσ = C C N 0?? ?j j m + km in σ /σ 0, m + 1 j n = σ??36 ?借助人工變量求初始的基本可行解 若約束方程組含有 “ ≥ ” 不等式 ， 那么在化標準形時除了在方程式左端減去剩余變量 ， 還必須在左端加上一個非負的人工變量 。 因為人工變量是在約束方程已為等式的基礎上 ， 人為的加上去的一個新變量 ， 因此 加入人工變量后的約束方程組與原約束方程組是不等價的 。 加上人工變量以后 ， 線性規(guī)劃的基本可行解不一定是原線性規(guī)劃的問題的基本可行解 。 只有當基本可行解中所有人工變量都為取零值的非基變量時 ， 該基本可行解對原線性規(guī)劃才有意義 。 因為此時只需去掉基本可行解中的人工變量部分 ， 剩余部分即為原線性規(guī)劃的一個基本可行解 ． 而這正是我們引入人工變量的主要目的 。 37 考慮線性規(guī)劃問題： 為了在約束方程組的系數(shù)矩陣中得到一個 m階單位矩陣作為 初始可行基 ， 在每個約束方程組的左端加上一個人工變量 可得到： njjj= 1ni j j ij= 1jm a xZ = c x a x =b ,i=1, 2, ... ,m x 0, j =1 ,2 ,.. .., n???? ????n + ix ( i = 1 , 2 , m )njjj= 1ni j j n + i ij= 1jm a xZ = c x a x + x = b ,i= 1, 2, ... ,m x 0, j=1 ,2 ,..