【正文】 0 0 1 ? 0 … … … … 0 0 ? 1 a 1 , m +1 a 2 , m +1 ? a m , m +1 … … … a 1 , m + k a 2 , m + k ? a m , m + k … … ?… a 1n a 2n ? a mn b 1 b 2 ? b m θ 1 θ 2 ? θ m ????miijijj acc1? 0 0 … 0 σm +1 … σ m + k … σ n ???miii bcz1 單純形法全過程的計算 ， 可以用列表的方法計算更為簡潔 ， 這種表格稱為單純形表 。 19 單純形算法的計算步驟 ① 將線性規(guī)劃問題化成標準型。 ②找出或構(gòu)造一個 m階單位矩陣作為初始可行基，建立初始單純形表。 ③計算各非基變量 xj的檢驗數(shù) ?j，若所有 ?j≤0，則問題已得到最優(yōu)解， ④在大于 0的檢驗數(shù)中，若某個 ?k所對應的系數(shù)列向量 Pk≤0，則此問 ⑤根據(jù) max{?j｜ ?j＞ 0}=?k原則，確定 xk為換入變量 (進基變量 )，再按 ?規(guī)則計算： ?=min{bi/aik| aik＞ 0}=bl/ aik 確定 xl為換出變量。建立新的單純形表，此時基變量中 xk取代了 xl ⑥以 aik為主元素進行迭代，把 xk所對應的列向量變?yōu)閱挝涣邢蛄?，即aik變?yōu)?1，同列中其它元素為 0，轉(zhuǎn)第③ 步。 20 【 例 】 利用單純形列表算法求解例 ????????????0,30340243max21212121xxxxxxxxZ21 【 例 】 用單純形法求解 ????????????02053115232321321321xxxxxxxxx、321 2m ax xxxZ ???22 321 2m a x xxxZ ???【 解 】 將數(shù)學模型化為標準形式： ?????????????????5,2,1,0205311523253214321?jxxxxxxxxxj不難看出 x x5可作為初始基變量，單純法計算結(jié)果如表 。 23 Cj 1 2 1 0 0 b θ CB XB x1 x2 x3 x4 x5 0 x4 2 － 3 2 1 0 15 0 x5 1/3 1 5 0 1 20 λj 1 2 1 0 0 0 x4 2 x2 λj 1 x1 2 x2 λj 表 1－ 5 1/3 1 5 0 1 20 3 0 17 1 3 75 1/3 0 － 9 0 － 2 M 20 25 60 1 0 17/3 1/3 1 25 0 1 28/9 － 1/9 2/3 35/3 0 0 － 98/9 － 1/9 － 7/3 最優(yōu)解 X=(25， 35/3， 0， 0， 0)T，最優(yōu)值 Z=145/3 24 【 例 】 用單純形法求解 421 22m i n xxxZ ??????????????????????5,1,0212665521421321?jxxxxxxxxxxj25 【 解 】 這是一個極小化的線性規(guī)劃問題 ,可以將其化為極大化問題求解 ,也可以直接求解 ,這時判斷標準是： λj≥0(j=1， … ， n)時得到最優(yōu)解 。 容易觀察到 ,系數(shù)矩陣中有一個 3階單位矩陣 ,x x x5為基變量。目標函數(shù)中含有基變量 x4,由第二個約束得到 x4=6+x1－ x2，并代入目標函數(shù)消去 x4得 1 2 1 2 1 22 2 ( 6 ) 6Z x x x x x x? ? ? ? ? ? ? ?＝26 XB x1 x2 x3 x4 x5 b θ x3 x4 x5 1 1 6 [1] 1 2 1 0 0 0 1 0 0 0 1 5→ 6 21 5 6 21/2 λj 1 1↑ 0 0 0 x2 x4 x5 1 2 4 1 0 0 1 1 2 0 1 0 0 0 1 5 1 11 λj 2 0 1 0 0 表中 λj≥0,j=1,2,… ,5所以最優(yōu)解為 X=(0,5,0,1,11,)最優(yōu)值 Z=2x1－ 2x2－ x4=－ 2 5－ 1=－ 11 極小值問題 ,注意判斷標準 ,選進基變量時 ,應選 λj0的變量 xj進基。 表 27 21m a x xxZ ???????????????0,42123212121xxxxxx【 例 】 求解線性規(guī)劃 【 解 】 化為標準型 21m a x xxZ ????????????????4,1,042123421321?jxxxxxxxj28 初始單純形表為 XB x1 x2 x3 x4 b x3 x4 3 2 － 2 － 1 1 0 0 1 1 4 ?j － 1 1 0 0 λ2=10, x2進基 ， 而 a120， a220， 沒有比值 ， 從而線性規(guī)劃的最優(yōu)解無界 。 由模型可以看出 ， 當固定 x1使 x2→+∞且滿足約束條件 ， 還可以用圖解法看出具有無界解 。 29 【 例 】 求解線性規(guī)劃 21 42m a x xxZ ?????????????????0,21024221212121xxxxxxxx【 解 】 :化為標準型后用單純形法計算如下表所示 30 XB x1 x2 x3 x4 x5 b θ (1) x3 x4 x5 － 1 1 1 [2] 2 － 1 1 0 0 0 1 0 0 0 1 4→ 10 2 2 5 — λj 2 4↑ 0 0 0 (2) x2 x4 x5 － 1/2 [2] 1/2 1 0 0 1/2 － 1 1/2 0 1 0 0 0 1 2 6→ 4 — 3 8 λj 4↑ 0 － 2 0 0 (3) x2 x1 x5 0 1 0 1 0 0 1/4 － 1/2 [3/4] 1/4 1/2 － 1/4 0 0 1 7/2 3 5/2→ 14 — 10/3 λj 0 0 0↑ － 2 0 (4) x2 x1 x3 0 1 0 1 0 0 0 0 1 1/3 1/3 － 1/3 － 1/3 2/3 4/3 8/3 14/3 10/3 λj 0 0 0 － 2 0 31 表 (3)中 λj全部非正 ,則最優(yōu)解為 : 20,)25,0,0,27,3()1( ?? ZX T 表 (3)表明 ,非基變量 x3的檢驗數(shù) λ3=0, x3若增加 ,目標函數(shù)值不變 , 即當 x3進基時 Z仍 等于 20。 使 x3進基 x5出基繼續(xù)迭代 ,得到表 (4)的另一 基本最優(yōu)解 X(1),X(2