【正文】 例３：最優(yōu)表： 非基變量檢驗 數(shù) ， 所以有無窮多 最優(yōu)解。 54 例 求解下述線性規(guī)劃問題： 解： 引入松弛變量 化標準型 1 2 3 41 2 3 41 2 3 4 3jm a xZ =3x 80x +2x 24xx 32x 4x 36x 0x 24x x 6x 0 x 1 x 0,j 1,2,3, 4??????????? ??? 1 2 3 41 2 3 4 51 2 3 4 637jm a xZ = 3x 80 x + 2x 24 xx 32 x 4x 36 x x 0x 24 x x 6 x x 0 x x 1 x 0, j 1, 2, 3, 4, 5, 6, 7? ? ???? ? ??????? ???5 6 7x ,x ,x55 0 0 0 24 2 80 3 0 Z 5 6 0 42 0 8 0 5 Z 1 0 0 0 1 0 0 1 x3 2 1 2 0 6 0 24 1 1 x1 3 3 2 1 30 0 8 0 3 x5 0 0 3 0 42 5 8 0 0 Z 1 1 0 0 1 0 0 1 x7 0 0 1 0 6 1 24 1 0 x1 3 0 1 1 30 3 8 0 0 x5 0 1 1 0 0 1 0 0 1 x7 0 0 0 1 0 6 1 24 1 0 x6 0 0 0 0 1 36 4 32 1 0 x5 0 x7 x6 x5 x4 x3 x2 x1 b XB CB 0 0 0 24 2 80 3 C θ 第一次迭代中使用了攝動法原理 ， 選擇下標為 6的基變量 x6離基 。 通過基變換以后的前后兩個退化的基本可行解的坐標形式完全相同 。 ? 產(chǎn)生的原因：在單純形法計算中用最小比值原則確定換出變量時 ，有時存在兩個或兩個以上相同的最小比值 θ， 那么在下次迭代中就會出現(xiàn)一個甚至多個基變量等于零 。 無最優(yōu)解也稱為有限最優(yōu)解 ， 或無界解 。 51 ?無最優(yōu)解 無最優(yōu)解與無可行解時兩個不同的概念 。Z = Z故引入人工變量 ， 并利用大 M法求解 78x ,x1 2 31 2 3 41 3 52 3 639。 49 例 求解下列線性規(guī)劃問題 解： 首先將問題化為標準型 令 ， 則 1 2 31 2 313231 2 3m i n Z = 3 x + 2 x + xx x x 6x x 4 x x 3x ,x ,x 0? ? ????????? ??39。 人工變量的值不能取零 ， 說明了原線性規(guī)劃的數(shù)學模型的約束條件出現(xiàn)了相互矛盾的約束方程 。 ? ?X 0 , 3 , 1 , 2 , 0 T? ?48 ?單純形表與線性規(guī)劃問題的討論 ?無可行解 通過大Ｍ法或兩階段法求初始的基本可行解 。 解：首先將問題化為標準型 添加人工變量 x6,x7,并建立輔助線性規(guī)劃如下： 121212212max Z = x + 2 xx x 2 x x 1 x 3 x ,x 0??????????? ???1 2 31 2 425j x x x 2 x x x 1 x x 3 x 0 , j 1 , 2 , 3 , 4 , 5???????????? ???671 2 3 61 2 4 725jm inZ = x + x x x x x 2 x x x x 1 x x 3 x 0, j 1, 2, 3, 4, 5, 6, 7? ? ???? ? ??????? ???由于輔助線性規(guī)劃的目標函數(shù)是極小化，因此最優(yōu)解的判別準則應(yīng)為： N N Bσ = C C N 0?45 0 1 1/2 1/2 0 1/2 1/2 3/2 X2 0 1 0 1/2 1/2 0 1/2 1/2 1/2 X1 0 1 1 0 1 0 0 1 1 X2 0 1/2 2 0 1 1 0 1 1 1 X6 1 1/1 1 1 0 1 0 0 1 1 X7 1 2/1 1 1 1 0 0 1 0 2 X6 1 0 0 0 0 0 1 1 0 W 0 0 1/2 1/2 1 1/2 1/2 3/2 X5 0 2 0 1 1 0 0 2 1 W 2/1 1 0 0 1 1 0 1 2 X5 0 0 2 1 1 0 0 0 3 W 3/1 0 1 0 0 1 0 0 3 X5 0 x1 x2 x3 x4 x5 x6 x7 b XB CB θ 0 0 0 0 0 1 1 C 輔助規(guī)劃所有檢驗數(shù)： N N Bσ = C C N 0? m in W = 0 1 3 3X = ( , , 0 , 0 , )2 2 2原問題已得一個初始基本可行解， 46 由上表可知 ， 通過若干次旋轉(zhuǎn)變換 ， 原問題的約束方程組已變換成包含一個單位矩陣的約束方程組 該約束方程組可作為第二階段初始約束方程組 ， 將目標函數(shù)則還原成原問題的目標函數(shù) ， 可繼續(xù)利用單純形表求解 。 ? 求原問題的最優(yōu)解 。 如果輔助線性規(guī)劃存在一個基本可行解 ， 使目標函數(shù)的最小值等于零 ， 則所有人工變量都已經(jīng) “ 離基 ” 。 兩階段法的步驟： ? 求解一個輔助線性規(guī)劃 。 否則最優(yōu)解中剔除人工變量的剩余部分即為原問題的初始基本可行解 。 以后的計算與單純形表解法相同 ， Ｍ只需認定是一個很大的正數(shù)即可 。 為此可以在目標函數(shù)中賦予人工變量一個絕對值很大的負系數(shù) Ｍ 。 以單位矩陣為初始基 ， 即可求得一個初始的基本可行解 。 如果約束方程組中包含有一個單位矩陣 I， 那么已經(jīng)得到了一個初始可行基 。 此時可以把所有人工變量剔除 ， 開始正式進入求原線性規(guī)劃最優(yōu)解的過程 。 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 ,.. .., n+ m???? ????38 ———————————————————————— 添加了 m個人工變量以后 ， 在系數(shù)矩陣中得到一個 m階單位矩陣 ，以該單位矩陣對應(yīng)的人工變量 為基變量 ， 即可得到一個初始的基本可行解 這樣的基本可行解對原線性規(guī)劃沒有意義的 。 只有當基本可行解中所有人工變量都為取零值的非基變量時 ， 該基本可行解對原線性規(guī)劃才有意義 。 因為人工變量是在約束方程已為等式的基礎(chǔ)上 ， 人為的加上去的一個新變量 ， 因此 加入人工變量后的約束方程組與原約束方程組是不等價的 。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)的準則有所不同 ， 即： 若某個基本可行解的所有非基變量對應(yīng)的檢驗數(shù) （ 而不是 ≤ ０ ） ， 則基本可行解為最優(yōu)解 ． 否則采用最大減少原則 （ 而非最大增加原則 ） 來確定換入變量 ， 即： 若 則選取對應(yīng)的非基變量 xm+k為換入變量． ? 確定了換入變量以后，換出變量仍采用最小比值原則來確定。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)解 。Z = Z = x + 2 x39。 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