運(yùn)籌學(xué)-單純形法(已修改)
2025-08-17 17:04 本頁面
【正文】 2022/8/28 1 第 4節(jié) 單純形法計算步驟 2022/8/28 2 Step 1 化為標(biāo)準(zhǔn)型，找出初始可行基，并列出初始單純形表 ? 上述初始單純形表中，最后一行稱為檢驗數(shù) σj 2022/8/28 3 基 基向量 x1 x2 x3 x4 x5 Z 可行解 圖中點 B1 P3P4P5 0 0 8 16 12 0 √ O B2 P2P4P5 0 4 0 16 4 12 ╳ A B3 P2P3P5 0 0 無解 B4 P2P3P4 0 3 2 16 0 9 √ Q4 B5 P1P4P5 8 0 0 16 12 16 ╳ C B6 P1P3P5 4 0 4 0 12 8 √ Q1 B7 P1P3P4 0 0 無解 B8 P1P2P5 4 2 0 0 4 14 √ Q2 B9 P1P2P4 2 3 0 8 0 13 √ Q3 B10 P1P2P3 4 3 2 0 0 17 ╳ B ??????????????????5,1 ,012 4 16 48 2x 32 m a x524132121?jxxxxxxxxxzjx2 x1 O 1 1 2 2 3 3 4 4 Q1 Q2 Q3 Q4 A B C 2022/8/28 4 ? Step2： 檢查非基變量所對應(yīng)的檢驗數(shù) σj，若所有的 σj≤0，則當(dāng)前的基可行解就是最優(yōu)解，當(dāng)前的目標(biāo)函數(shù)值就是最優(yōu)值，停止計算。 ? 否則，轉(zhuǎn)入下一步。 ? Step3： 若存在一個 σk0， σk所對應(yīng)的變量 xk的系數(shù)列向量Pk≤0(即 Pk中每一個分量 aik≤0)，則該 LP無有限最優(yōu)解，停止計算。 ? 否則，轉(zhuǎn)入下一步。 ? Step4： 進(jìn)行可行基的迭代。 ? 重復(fù)以上步驟 2022/8/28 5 ? 例 7 用單純形法求解例 6。 ? max z = 2x1 + 3x2 . x1 + 2x2 +x3 =8 4x1 +x4 =16 4x2 +x5 =12 xj≥0， j=1,2,…,5 2022/8/28 6 練習(xí)： ? 分別用圖解法和單純形法求解下列線性規(guī)劃問題，并指出單純形法迭代的每一步相當(dāng)于圖形上哪一個頂點。 Max Z = 10x1+ 5x2 3x1+ 4x2≤9 5x1+ 2x2 ≤8 x1 ， x2≥0 2022/8/28 7 解： cj 10 5 0 0 CB XB bi x1 x2 x3 x4 θ 0 x3 9 3 4 1 0 0 x4 8 5 2 0 1 σj 10 5 0 0 [ ] 3 8/5 [ ] 0 X3 10 x1 8/5 1 2/5 0 1/5 21/5 0 14/5 1 3/5 x1入 ,x4出 σj 0 1 0 2 [ ] x2入 ,x3出 3/2 4 5 X2 10 x1 σj 1 1 0 1/7 2/7 3/2 0 1 5/14 3/14 0 0 5/14 25/14 所以： X*=(x1,x2)T=(1,3/2)T Z*=35/2 [ ] 0: (0,0) C: (0,9/4) A: (8/5,0) B:(1,3/2) x1 x2 對應(yīng)0 對應(yīng)A 對應(yīng)B 2022/8/28 8 回顧：單純形法求解步驟： 2022/8/28 9 第 5節(jié) 單純形法的進(jìn)一步討論 2022/8/28 10 第 5節(jié) 單純形法的進(jìn)一步討論 一、人工變量法（大 M法） 約束條件： “ ≤” → 加一個松弛變量 “ ≥” → 減一個剩余變量后，再加一個人工變量 “ ＝ ” → 加一個人工變量 目標(biāo)函數(shù)： 人工變量的系數(shù)為 “ － M”，即罰因子 若線性規(guī)劃問題有最優(yōu)解則人工變量必為
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1