運(yùn)籌學(xué)——3單純形矩陣描述與改進(jìn)單純形法-免費(fèi)閱讀
【正文】 當(dāng) t＞ 2時(shí)，則 b1＜ 0；故將 x1作為換出變量，用對(duì)偶單純形法迭代一步，得表 226 c j → 1 3 0 0 C B X B b x 1 x 2 x 3 x 4 0 3 x 1 x 2 6+3t 6 t 3 1 0 1 2 1 1 0 c j z j 2 0 3 0 從表 226可見 ， 當(dāng) t＞ 6時(shí) ， 問題無可行解 ；當(dāng) 2≤t≤6時(shí) ，問題的最優(yōu)解為 (0， 6?t， 0， ?6+3t)T。 c j → 3+ 2 t 5 t 0 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 0 5 t 3+2t x 4 x 2 x 1 6 3 4 0 0 1 0 1 0 3 3/2 1 1 0 0 1 1/2 0 c j z j 0 0 (9/2) (7/2)t 0 (5/2)+(1/2)t 54 當(dāng) t繼續(xù)增大 t≥(5/2)/(1/2)=5時(shí)，在檢驗(yàn)數(shù)行首先出現(xiàn) σ5≥0，在 σ5≤0，即 9/7≤t≤5時(shí)，得最優(yōu)解 (4,3,0,6,0) T 。 51 參數(shù) c的變化 ????????????????0,18231224)5()23()(m ax21212121xxxxxxxtxttz? 例 12 試分析以下參數(shù)線性規(guī)劃問題 。 21m in xxz ????????????0,3742212121xxxxxx? 作業(yè) 4： 4. 課本 P76. (1)(5) 49 第 8節(jié) * 參數(shù)線性規(guī)劃 ? 靈敏度分析主要討論在最優(yōu)基不變情況下 ， 確定系數(shù) aij，bi， cj的變化范圍 。 44 c j → 2 3 4 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 0 2 x 4 x 1 1 2 0 1 [ 5/2] 1/2 1/2 3/2 1 0 1/2 1/2 c j z j 0 4 1 0 1 由表 2 7 看出，對(duì)偶問題仍是可行解，而 b 列中仍有負(fù)分量。 因 b列數(shù)字為負(fù)，故需進(jìn)行迭代運(yùn)算。按 min｛ (B1b)i｜ (B1b)i＜ 0}＝ (B1b)l對(duì)應(yīng)的基變量 xi為換出變量 (3) 確定 換入變量 。 ? 根據(jù)對(duì)偶問題的對(duì)稱性 ， 可以這樣考慮：若保持對(duì)偶問題的解是基可行解 ， 即 cj?CBB1Pj≤0， 而原問題在非可行解的基礎(chǔ)上 ， 通過逐步迭代達(dá)到基可行解 ， 這樣也得到最優(yōu)解 。P,P,PBNBTNTB003022222532412412?????價(jià)值系數(shù)非基變量基變量基30 第 3步： 計(jì)算非基變量（ x3, x5）的檢驗(yàn)數(shù) ? ?? ?? ? ? ?換入變量正檢驗(yàn)數(shù)對(duì)應(yīng)注意：535322124121000014100314210130200222x,x/,//),(,)P,PN(NBCCBNN????????????????????????????????31 確定換出變量 ? ?? ?4441328212051251212x/,/m i nPBPBbBm i nii對(duì)應(yīng)????????????????????????32 新的基 ? ?主元素的系數(shù)向量是換入變量??????????? ???????????????????????????4/122/11004/1002142/101。 ? ????????????????????????5435430 0111xxxX。?????????目標(biāo)函數(shù)：8 單純形表中的數(shù)據(jù) 基變量 非基變量 等式右邊 系數(shù)矩陣 檢驗(yàn)數(shù) 0I1??BBXBbBCNBCCbBNBR H SXBBNN1111 ??????9 單純形表中的數(shù)據(jù) 基變量 非基變量 松弛變量 等式右邊 系數(shù)矩陣 檢驗(yàn)數(shù) 01IBBXB??bBCBCNBCCbBBNBR H SXXBBBNsN111111?????????10 （ 3） θ 規(guī)則表示為： RHS值 表示選用 0的分量 換入變量的系數(shù)向量 ljlijijiPBbBPBPBbB)()(0)()()(m i n11111?????????????????11 小結(jié) 1）掌握矩陣的運(yùn)算； 2）理解基矩陣的作用； 3）了解矩陣運(yùn)算與單純表的關(guān)系。1 第 1節(jié) 單純形法的矩陣描述 設(shè)線性規(guī)劃問題可以用如下矩陣形式表示： 目標(biāo)函數(shù) max z=CX 約束條件 AX≤b 非負(fù)條件 X≥0 2 將該線性規(guī)劃問題的約束條件加入松弛變量后 ， 得到標(biāo)準(zhǔn)型
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1