【正文】 1 0 2 3 4 對 偶 單 純 形 法 97 China University of Mining and Technology 運 籌 學 基變換的過程： 2 3 4 XB b x1 x2 x3 x4 x5 x4 x1 2 3 4 0 0 XB b x1 x2 x3 x4 x5 x4 3 1 2 1 1 0 x5 4 [2] 1 3 0 1 0 2 3 4 2 1 1/2 3/2 0 1/2 1 0 5/2 1/2 1 1/2 4 0 4 1 0 1 對 偶 單 純 形 法 98 China University of Mining and Technology 運 籌 學 2 3 4 XB b x1 x2 x3 x4 x5 x4 x1 2 1 1/2 3/2 0 1/2 1 0 5/2 1/2 1 1/2 4 0 4 1 0 1 可見正則解的有負分量，由于 x4=1 , 所以取 x4為換 出變量，取 422212544 58}1,4m i n {}0m i n {?????? ??????????jjjx2為換入變量，得新基 {x2,x1} ， ?42=5/2為主元 對 偶 單 純 形 法 99 China University of Mining and Technology 運 籌 學 2 3 4 XB b x1 x2 x3 x4 x5 x2 2/5 0 1 1/5 2/5 1/5 x1 11/5 1 0 7/5 1/5 2/5 28/5 0 0 3/5 8/5 1/5 此時正則解是可行解，也是最優(yōu)解。 X*=(11/5， 2/5， 0， 0， 0)； z*=28/5 進行基變換，得新正則解的單純形表： 對 偶 單 純 形 法 100 China University of Mining and Technology 運 籌 學 ????????????0y,y30y3y502y4y50y120ywM i n21212121??????????????0y,y 30y3y 502y4y5 0y1 20 ywM a x21212121????????????????0y,y 3 0yy3y 5 0y2y4y5 0 y1 2 0 ywM a x2142132121例 10 101 China University of Mining and Technology 運 籌 學 cj B1b 120 50 0 0 cB yB y1 y2 y3 y4 0 y3 50 4 2 1 0 0 y4 30 3 1 0 1 σj 0 120 50 0 0 θ 120/4 50/2 50 y2 25 2 1 1/2 0 0 y4 5 1 0 1/2 1 σj 1250 20 0 25 0 θ 20 50 50 y2 15 0 1 3/2 2 120 y1 5 1 0 1/2 1 σj 1350 0 0 15 20 102 China University of Mining and Technology 運 籌 學 ???????????????0x,x,x10xx5x27xxxx5x3x2zM ax321321321321?????????????????????0x,x,x,x,x10xxx5x27xxxxMxx5x3x2zM a x54321532143214321例 11 103 China University of Mining and Technology 運 籌 學 cj B1b 2 3 5 M 0 θ cB xB x1 x2 x3 x4 x5 M x4 7 1 1 1 1 0 7 0 x5 10 2 5 1 0 1 σj 7M M+2 M+3 M5 0 0 θ 3 x2 7 1 1 1 1 0 0 x5 45 7 0 6 5 1 σj 21 1 0 7 M3 0 θ 1/7 7/6 (M+3)/5 3 x2 4/7 0 1 1/7 2/7 1/7 2 x1 45/7 1 0 6/7 5/7 1/7 σj 102/7 0 0 50/7 (M+16)/7 1/7 104 China University of Mining and Technology 運 籌 學 ?????????????????????0x,x,x1x2x32xx4x11x2xxxx3xzM a x32121321321321?????????????????????????0x,x1xx2x3x2xx4x11xx2xxMxxx3xzM ax61621532143216321?例 12 105 China University of Mining and Technology 運 籌 學 cj 3 1 1 0 0 M B1b θ cB xB x1 x2 x3 x4 x5 x6 0 x4 1 2 1 1 0 0 11 11 0 x5 4 1 2 0 1 0 3 M x6 2 0 1 0 0 1 1 1 σj 6M+3 1 M1 0 0 0 M cj 3 1 1 0 0 M B1b θ cB xB x1 x2 x3 x4 x5 x6 0 x4 3 2 0 1 0 1 10 0 x5 0 1 0 0 1 2 1 1 x3 2 0 1 0 0 1 1 σj 1 1 0 0 0 M+1 1 106 China University of Mining and Technology 運 籌 學 cj 3 1 1 0 0 M B1b θ cB xB x1 x2 x3 x4 x5 x6 3 x1 1 0 0 1/3 2/3 5/3 4 1 x2 0 1 0 0 1 2 1 1 x3 0 0 1 2/3 4/3 7/3 9 σj 0 0 0 1/3 1/3 M+2/3 2 cj 3 1 1 0 0 M B1b θ cB xB x1 x2 x3 x4 x5 x6 0 x4 3 0 0 1 2 5 12 1 x2 0 1 0 0 1 2 1 1 x3 2 0 1 0 0 1 1 σj 1 0 0 0 1 M1 2 107 China University of Mining and Technology 運 籌 學 對偶單純形法的迭代步驟中 ,如何找一個 初始正則解 ？ 初始正則解的確定 標準形線性規(guī)劃問題 0..)(m a x??????XbAXtsPCXZ選定的基 B，不妨設 ),( 21 mPPPB ??對 偶 單 純 形 法 ? ?0 1 11 1 ( 1 ) 1 1 12 2 ( 1 ) 1 2 2( 1 ) 1m a x0 1 , 2 , ,m m n nm m n nm m n nm m m m m n n mjz z x xx x xx x xx x xx j n??? ? ?? ? ?? ? ?????????? ? ? ?? ? ? ??? ? ? ? ???? ? ? ??? ???可行基 B的典式為 右端常數中有負數，而檢驗數全非正，則基 B為正則基，相應的 解 為初始正則解，就可用對偶單純形法求解。 TmX )0,0,( 21)0( ?? ????否則，若出現正檢驗數， X(0)就不是正則解。 108 China University of Mining and Technology 運 籌 學 為 此， 求初始正則基和初始正則解，可增加一個約束條件： Mxxx nm ???? ? ?10原問題 (P)的典式擴充為下列問題 : ( 0 )1101m a x 。( 1 , 2 , , ) 。..0( 0 , 1 , 2 , , ) ,njjjmni ij j ijmnjjmjZ Z xx x i ms t x x Mx j n????????????? ? ????????????????擴充問題： 對 偶 單 純 形 法 00??Mx j非基變量 充分大數 109 China University of Mining and Technology 運 籌 學 ?擴充問題的一個正則基和正則解是不難得到的。 對偶單純形法 ?擴充問題的兩種可能結果： （ 1）若擴充問題無可行解，則原問題 (P)也無可行解。 （ 2）若擴充問題有最優(yōu)解 TnxxxX ),(* **1*0 ??且目標函數最優(yōu)值與 M 無關 ,則有 TnxxxX ),(* **2*1 ??必為原問題 (P)的最優(yōu)解。 113 China University of Mining and Technology 運 籌 學 對偶單純形法的理論解釋 對偶單純形法所使用的表格與原單純形法一樣，可將典式中的數據放在原單純形表上，即得到對偶單純形表， 所不同的是 這里保證在整個過程中 ),2,1(0 nmmjj ??????不保證 01 ?? bB ,即右端常數中可以出現負數。 對偶單純形法 先定換出變量，再定換入變量。 從本章起，不強調右端常數非負這個條件。 121 China University of Mining and Technology 運 籌 學 (1) 用對偶單純形法求解線性規(guī)劃問題時，當約束條件為“＞”時，不必引進人工變量，使計算簡化。 (2) 當線性規(guī)劃問題中變量多于約束條件時，用對偶單純形法計算可以減少工作量。 (3) 對偶單純形法應用于主要應用于靈敏度分析及整數規(guī)劃等有關章節(jié)中。 (4) 對偶單純形法的 局限性 主要是：對大多數線性規(guī)劃問題，很難找到一個初始正則解。因此對偶單純形法一般不單獨使用。 對偶單純形法的優(yōu)缺點： 對偶單純形法