[管理學(xué)]線性規(guī)劃的圖解法與單純形解法-文庫吧
2025-01-04 07:42 本頁面
【正文】 ???????????pqpapqabpqq00m i nm a x ??單純形表 c j c 1 c 2 … c m c m + 1 … c m + k … c n c B X B x 1 x 2 … x m x m + 1 … x m + k … x n b θ i c 1 c 2 ? c m x 1 x 2 ? x m 1 0 ? 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 單純形算法的計(jì)算步驟 ① 將線性規(guī)劃問題化成標(biāo)準(zhǔn)型。 ②找出或構(gòu)造一個(gè) m階單位矩陣作為初始可行基，建立初始單純形表。 ③計(jì)算各非基變量 xj的檢驗(yàn)數(shù) ?j，若所有 ?j≤0，則問題已得到最優(yōu)解， ④在大于 0的檢驗(yàn)數(shù)中，若某個(gè) ?k所對(duì)應(yīng)的系數(shù)列向量 Pk≤0，則此問題 ⑤根據(jù) max{?j｜ ?j＞ 0}=?k原則，確定 xk為換入變量 (進(jìn)基變量 )，再按 ?規(guī)則計(jì)算： ?=min{bi/aik| aik＞ 0}=bl/ aik 確定 xl為換出變量。建立新的單純形表，此時(shí)基變量中 xk取代了 xl ⑥以 aik為主元素進(jìn)行迭代，把 xk所對(duì)應(yīng)的列向量變?yōu)閱挝涣邢蛄浚碼ik變?yōu)?1，同列中其它元素為 0，轉(zhuǎn)第③ 步。 單純形算法計(jì)算舉例 例：用單純形法求解線性規(guī)劃問題 m a x z = 2 x1+ x2 x2 ≤ 3 3 x1+ x2≤ 12 x1+ x2≤ 5 x1， x2≥ 0 ， 解：先將上述問題化為標(biāo)準(zhǔn)形式 m a x z = 2 x1+ x2+0 x3+0 x4+0 x5 x2 + x3=3 3 x1+ x2+ x4= 12 x1+ x2+ x5=5 x1， x2， x3， x4， x5≥ 0 單純形法計(jì)算舉例 ??????????5123100110101300110P1 P2 P3 P4 P5 b 單純形法計(jì)算舉例 c j 2 1 0 0 0 C B X B x 1 x 2 x 3 x 4 x 5 b θ i 0 0 0 x 3 x 4 x 5 0 1 1 0 0 [ 3] 1 0 1 0 1 1 0 0 1 3 12 5 — 4 5 σ j 2 1 0 0 0 z = 0 單純形法計(jì)算舉例 c j 2 1 0 0 0 C B X B x 1 x 2 x 3 x 4 x 5 b θ i 0 2 0 x 3 x 1 x 5 0 1 1 0 0 1 1/3 0 1/3 0 0 [ 2/3 ] 0 1/3 1 3 4 1 3 12 3/2 σ j 0 1/3 0 2 /3 0 z =8 單純形法計(jì)算舉例 c j 2 1 0 0 0 C B X B x 1 x 2 x 3 x 4 x 5 b θ i 0 2 1 x 3 x 1 x 2 0 0 1 1/2 3/2 1 0 0 1/2 1/2 0 1 0 1/2 3/2 3/2 7/2 3/2 σ j 0 0 0 1/2 1/2 z = 17/2 單純形法計(jì)算的矩陣描述 對(duì)標(biāo)準(zhǔn)形式的線性規(guī)劃問題 m a x0z C XA X bX????=≥ 假定存在基 B ，基變量為BX，非基變量為NX，則有 111111()()BNB B N N B N N NB N B NX B b B N Xz C X C X C B b B N X C XC B b C C B N X????????? ? ? ? ?? ? ? 單純形法計(jì)算的矩陣描述 與前面檢驗(yàn)數(shù)計(jì)算公式對(duì)照，可得非基變量檢驗(yàn)數(shù)計(jì)算公式 1N N BC C B N???? 另外，基變（向）量 XB的檢驗(yàn)數(shù)可寫作 1 0B B BC C B B??? ? ? 所以可得標(biāo)準(zhǔn)形式的線性規(guī)劃模型檢驗(yàn)數(shù)計(jì)算的一般計(jì)算公式 1BC C B A???? 單純形法計(jì)算的矩陣描述 再考慮下列線性規(guī)劃問題 m a x0z C XA X bX????≤≥ 上式加上松弛變量后為 m a x 00 , 0SSSz CX XA X I X bXX???????≥ ≥ 單純形法計(jì)算的矩陣描述 ? ?m a x z | 0SXCX??? ???? ? ??????????????0,|XXbXXIASS 式中，X S松馳變量，),( 21TxxxX mnnnS ???? ? ， I 為 nm ? 單位矩陣。 單純形法計(jì)算的矩陣描述 非基變量 基變量 BX NX SX X S0 B N I b zc jj ? C B C N 0 當(dāng)?shù)舾刹胶?，基變量為X B 時(shí)，該步的單純形中由X B 系數(shù)組成的矩陣為 I ，這時(shí)對(duì)應(yīng)X S 的系數(shù)矩陣在新表中應(yīng)為B 1? 。故當(dāng)基變量為X B 時(shí)，新的單純形表就變?yōu)? 基變量 非基變量 BX NX SX XC BB I NB 1? B 1? bB 1? zc jj ? 0 NBCC BN 1?? BC B 1?? 單純形法計(jì)算的矩陣描述 從上面兩表可看出，當(dāng)?shù)?，基變量為X B，其在初始單純形表中的系數(shù)矩陣為 B ，則有： （ 1 ） 對(duì)應(yīng)初始單純形表中的單位陣 I ，迭代后的單純形表中為B 1?； （ 2 ） 初始基變量bX S ? ，迭代后的表中bBX B 1??； （ 3 ） 初始單純形表中，約束系數(shù)矩陣為? ? ? ?INBIA , ?，迭代后的表中約束系數(shù)矩陣為? ? ? ? ? ?BNBIIBNBBBIBAB 1111111 ,, ??????? ?? （ 4 ） 若初始矩 陣中變量x j的系數(shù)向量為P 39。 j，迭代后為P j ，則有P jBP 39。 j1?? （ 5 ） 當(dāng) B 為最優(yōu)基時(shí)，在上表中應(yīng)有 ?????????0011BCABCCBBN 因 X B的檢驗(yàn)數(shù)可寫作01 ?? ? BBCC BB 所以 有 ?????????0011BCABCCBB
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1