[管理學(xué)]線性規(guī)劃的圖解法與單純形解法-展示頁
2025-01-28 07:42本頁面
【正文】 BC B 1?稱為單純形乘子，若令BC BY 1?? ，則有0, ?? YCYA成立。故當(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ì)算舉例 例：用單純形法求解線性規(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ì)算各非基變量 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為換出變量。 ? 最佳換入換出變量確定 ???????????????????????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)型。 令 ( 1 )( 1 )( 1 ),0 ( 1 , , , )1 , 2 ,mkji i i m kxx j m n j m kx b a i m?????? ? ? ? ???? ? ?但 T( 1 ) ( 1 ) ( 1 ( 1 ) ( 1 ) ( 1 )12 , , , , 0 , , 0 , , 0 , , 0l m m kX x x x x x ???? ??） ， ， 新解必須滿足非負(fù)約束，從而必須 (1), 0 , 1 , 2 ,i i i m kx b a i m????? ? ?≥ 換出變量的確定 就必須要求,0, ?? ? kmia 0, ???? ? ?kmii ab若 kmiiab????,?從而必須有：，取kmllkmiia ababkmi ???? ????????????????? ,0m i n m i n,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1