【正文】 否則 ,若有 arj0 ， 則選 ?=max{?j / arj┃ arj0}=?k/ark 那么 xk為進基變量 , Pk為主列 , 轉 4； 4) 以 ark為主元 ,作矩陣行變換使其變?yōu)?1,該列其它元變?yōu)?0,轉 2. 上一頁 下一頁 返回 對偶單純形法優(yōu)缺點 ： 優(yōu)點 : 1)原問題的初始解可以是非可行解 .當檢驗數都是非負時 ,就可以進行基變換 ,不需要加入人工變量 ,因此可以簡化計算 2)當變量多于約束條件個數 ,用對偶單純形法可以減少工作量 3)在靈敏度分析中有時用對偶單純形法較簡單 缺點 : 對偶單純形法要求滿足對偶問題有可行性解 .該條件不是總能滿足 ,因此這個方法很少單獨使用 . 上一頁 下一頁 返回 例：求解線性規(guī)劃問題： 解 Max Z = 2x1 3x2 4x3 x12x2x3+x4= 3 2x1+x23x3+x5= 4 x1,x2,x3,x4,x5 ≥ 0 Min z= 2x1 + 3x2 + 4x3 . x1 + 2x2 + x3 ≥ 3 2x1 x2 + x3 ≥ 4 x1 , x2 , x3 ≥ 0 上一頁 下一頁 返回 2 3 4 0 0 Z 0 2 3 4 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 0 x 4 3 1 2 1 1 0 0 x 5 4 [ 2 ] 1 3 0 1 1 3 / 4 Z 4 0 4 1 0 x 4 1 0 [ 5/2 ] 1/2 1 1/2 2 x 1 2 1 1/2 3/2 0 1/2 8/5 2 上一頁 下一頁 返回 最優(yōu)解 :(11/5,2/5,0,0,0) 最優(yōu)值 : Z*= 28/5, z*=28/5 Z 2 8 /5 0 0 9 /5 8 /5 1 /5 3 x 2 2 /5 0 1 1 /5 2 /5 1 /5 2 x 1 1 1 /5 1 0 7 /5 1 /5 2 /5 Z 4 0 4 1 0 1 0 x 4 1 0 [ 5 /2 ] 1 /2 1 1 /2 2 x 1 2 1 1 /2 3 /2 0 1 /2 8 /5 2 上一頁 下一頁 返回 是 是 是 是 否 否 否 否 所有 所有 得到 最優(yōu)解 計算 計算 典式對應原規(guī)劃的基本解是可行的 典式對應原規(guī)劃的基本解的檢驗數 所有 所有 計算 計算 以 為主元素進行迭代 以 為主元素進行迭代 停 沒有最優(yōu)解 沒有可行解 ,最優(yōu)解 單純形法 對偶單純形法 單純形法和對偶單純形法步驟 。 =min{bk180。否則 ,若有 b180。 上一頁 下一頁 返回 (2)離基變量與進基變量的選擇 c 1 c 2 … c m … c k … c n C B X B b x1 x 2 … x j … x k … x n Z Z 0 σ1 σ 2 … σ j … σ k … σ n c 1 x 1 b 1 a 1 1 a 1 2 … a 1 j … a 1 k … a 1 n ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ c r x r b r a r 1 a r 2 … a r j … ( a r k ) … a r n ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ c m x m b m a m 1 a m 2 … a m j … a m k … a mn 選取負值的基變量出基 :br =min{bi0 }, xr為出基變量 上一頁 下一頁 返回 1) 若第 r 行所有元素 arj ? 0 則原問題無可行解 . xr =br – (ar1 x1 …+ arj xj + …), j?JN 2) 若第 r行有 ark 0 , k?JN， 則相應的非基變量可能成為基變量 , 此時 br /= br / ark 0,有利于向可行解轉化 ,但還需考慮保證對偶解的可行性 ,即新檢驗數 ? j/ ≥ 0 ,于是取 ?k /ark = max{?j /arj | arj 0, j?JN } 則 ?j/ = ?j –(arj /ark ) ?k = ?j –(?k/ark ) arj ≥ ?j –(?j /arj ) arj =0 此 時 xr為出基變量 . 上一頁 下一頁 返回 1) 建立初始對偶單純形表 ,對應一個基本解 ,所有檢驗數均非負 ,轉 2； 二、對偶單純形法求解線性規(guī)劃問題步驟 2) 若 b180。 如果得到的基本解的分量皆非負，則該基本解為最優(yōu)解。 注意： B 是最優(yōu)基， 影子價格 —— 它表示最優(yōu)目標值隨相應資源數量變化的變化率。 根據 f = W*b=b1w1*+b2w2*+?+bmwm* 可知 ?f / ?bi = wi* wi* 表示 bi 變化 1個單位對目標 f 產生的影響（在不改變原最優(yōu)基情況下），即若原問題的某個約束的右端項 bi每增加一個單位而引起的最優(yōu)目標函數值的增加量就等于該約束條件相對應的對偶變量的最優(yōu)解。 (2)一個問題有 可行解而目標 為無界 ,另一個問題必無可行解 。 ATY≥C ,XTATY≥XTC , 那么 CTX ≤ bTY. 上一頁 下一頁 返回 推論 若 (LP)和 (DP)同時有可行解 那么 (LP)和 (DP)均有最優(yōu)解 . 推論 若 X (0), Y (0) 分別為（ LP)和 (DP)的可行解， 且 CTX(0)=bTY(0).那么 X (0), Y (0) 分別為 (LP)和 (DP)的最優(yōu)解 . 證 : CTX ≤ bTY(0) =CTX(0) 。 上一頁 下一頁 返回 （ 1） 將模型統(tǒng)一為 “