【正文】 1 0 2 3 4 對(duì) 偶 單 純 形 法 97 China University of Mining and Technology 運(yùn) 籌 學(xué) 基變換的過(guò)程： 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 對(duì) 偶 單 純 形 法 98 China University of Mining and Technology 運(yùn) 籌 學(xué) 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 可見(jiàn)正則解的有負(fù)分量，由于 x4=1 , 所以取 x4為換 出變量，取 422212544 58}1,4m i n {}0m i n {?????? ??????????jjjx2為換入變量，得新基 {x2,x1} ， ?42=5/2為主元 對(duì) 偶 單 純 形 法 99 China University of Mining and Technology 運(yùn) 籌 學(xué) 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 此時(shí)正則解是可行解，也是最優(yōu)解。 X*=(11/5， 2/5， 0， 0， 0)； z*=28/5 進(jìn)行基變換，得新正則解的單純形表： 對(duì) 偶 單 純 形 法 100 China University of Mining and Technology 運(yùn) 籌 學(xué) ????????????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 運(yùn) 籌 學(xué) 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 運(yùn) 籌 學(xué) ???????????????0x,x,x10xx5x27xxxx5x3x2zM ax321321321321?????????????????????0x,x,x,x,x10xxx5x27xxxxMxx5x3x2zM a x54321532143214321例 11 103 China University of Mining and Technology 運(yùn) 籌 學(xué) 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 運(yùn) 籌 學(xué) ?????????????????????0x,x,x1x2x32xx4x11x2xxxx3xzM a x32121321321321?????????????????????????0x,x1xx2x3x2xx4x11xx2xxMxxx3xzM ax61621532143216321?例 12 105 China University of Mining and Technology 運(yùn) 籌 學(xué) 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 運(yùn) 籌 學(xué) 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 運(yùn) 籌 學(xué) 對(duì)偶單純形法的迭代步驟中 ,如何找一個(gè) 初始正則解 ？ 初始正則解的確定 標(biāo)準(zhǔn)形線性規(guī)劃問(wèn)題 0..)(m a x??????XbAXtsPCXZ選定的基 B，不妨設(shè) ),( 21 mPPPB ??對(duì) 偶 單 純 形 法 ? ?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的典式為 右端常數(shù)中有負(fù)數(shù)，而檢驗(yàn)數(shù)全非正，則基 B為正則基，相應(yīng)的 解 為初始正則解，就可用對(duì)偶單純形法求解。 TmX )0,0,( 21)0( ?? ????否則，若出現(xiàn)正檢驗(yàn)數(shù)， X(0)就不是正則解。 108 China University of Mining and Technology 運(yùn) 籌 學(xué) 為 此， 求初始正則基和初始正則解，可增加一個(gè)約束條件： Mxxx nm ???? ? ?10原問(wèn)題 (P)的典式擴(kuò)充為下列問(wèn)題 : ( 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????????????? ? ????????????????擴(kuò)充問(wèn)題： 對(duì) 偶 單 純 形 法 00??Mx j非基變量 充分大數(shù) 109 China University of Mining and Technology 運(yùn) 籌 學(xué) ?擴(kuò)充問(wèn)題的一個(gè)正則基和正則解是不難得到的。 對(duì)偶單純形法 ?擴(kuò)充問(wèn)題的兩種可能結(jié)果： （ 1）若擴(kuò)充問(wèn)題無(wú)可行解，則原問(wèn)題 (P)也無(wú)可行解。 （ 2）若擴(kuò)充問(wèn)題有最優(yōu)解 TnxxxX ),(* **1*0 ??且目標(biāo)函數(shù)最優(yōu)值與 M 無(wú)關(guān) ,則有 TnxxxX ),(* **2*1 ??必為原問(wèn)題 (P)的最優(yōu)解。 113 China University of Mining and Technology 運(yùn) 籌 學(xué) 對(duì)偶單純形法的理論解釋 對(duì)偶單純形法所使用的表格與原單純形法一樣，可將典式中的數(shù)據(jù)放在原單純形表上，即得到對(duì)偶單純形表， 所不同的是 這里保證在整個(gè)過(guò)程中 ),2,1(0 nmmjj ??????不保證 01 ?? bB ,即右端常數(shù)中可以出現(xiàn)負(fù)數(shù)。 對(duì)偶單純形法 先定換出變量，再定換入變量。 從本章起，不強(qiáng)調(diào)右端常數(shù)非負(fù)這個(gè)條件。 121 China University of Mining and Technology 運(yùn) 籌 學(xué) (1) 用對(duì)偶單純形法求解線性規(guī)劃問(wèn)題時(shí)，當(dāng)約束條件為“＞”時(shí)，不必引進(jìn)人工變量，使計(jì)算簡(jiǎn)化。 (2) 當(dāng)線性規(guī)劃問(wèn)題中變量多于約束條件時(shí)，用對(duì)偶單純形法計(jì)算可以減少工作量。 (3) 對(duì)偶單純形法應(yīng)用于主要應(yīng)用于靈敏度分析及整數(shù)規(guī)劃等有關(guān)章節(jié)中。 (4) 對(duì)偶單純形法的 局限性 主要是：對(duì)大多數(shù)線性規(guī)劃問(wèn)題，很難找到一個(gè)初始正則解。因此對(duì)偶單純形法一般不單獨(dú)使用。 對(duì)偶單純形法的優(yōu)缺點(diǎn)： 對(duì)偶單純形法