運(yùn)籌學(xué)——3單純形矩陣描述與改進(jìn)單純形法-在線瀏覽
2024-09-15 17:28本頁面
【正文】 ??11112??可見 En…E2E1=A1。 1241648200032524132154321????????????xxxxxxxxxxxxzma x20 第 2節(jié) 改進(jìn)單純形法 第 1步 ：確定初始基，初始基變量 。 ? ????????????????????????5435430 0111xxxX。計算： ? ??243 P,P,P?????????? ???????????? ??????????????410121141021402112//E//P ；構(gòu)造主元素??????????? ?????????????????????? ??? ??4/1012/111114/1012/1110111 BEB23 （ 5）計算非基變量的系數(shù)矩陣 （ 6）計算 RHS ?????????? ?????????????????????? ???????????????410214114141012111411111////NBN??????????????????????????????? ???316212168410121111//bB24 第 2節(jié) 改進(jìn)單純形法 第 1步計算結(jié)束后的結(jié)果 ? ?? ?? ?? ? ? ?),(),(C,CC。x,x,xX。x,xX。P,P,PBNBTNTB003022222532412412?????價值系數(shù)非基變量基變量基30 第 3步： 計算非基變量（ x3, x5）的檢驗(yàn)數(shù) ? ?? ?? ? ? ?換入變量正檢驗(yàn)數(shù)對應(yīng)注意：535322124121000014100314210130200222x,x/,//),(,)P,PN(NBCCBNN????????????????????????????????31 確定換出變量 ? ?? ?4441328212051251212x/,/m i nPBPBbBm i nii對應(yīng)????????????????????????32 新的基 ? ?主元素的系數(shù)向量是換入變量??????????? ???????????????????????????4/122/11004/1002142/101。確定，從而計算，）求（。確定換入變量，從而求出）求（11111111111110k10010010000010,321 2.NBNBlkBNNCCXXbBNBBExbBPBNBxNBCCNB???????? ????3. 重復(fù)第 2步（下標(biāo)加 1），直至求出最優(yōu)解。 ? 通過逐步迭代 ， 當(dāng)在檢驗(yàn)數(shù)行得到對偶問題的解也是基可行解時 ， 已得到最優(yōu)解 。 ? 根據(jù)對偶問題的對稱性 ， 可以這樣考慮：若保持對偶問題的解是基可行解 ， 即 cj?CBB1Pj≤0， 而原問題在非可行解的基礎(chǔ)上 ， 通過逐步迭代達(dá)到基可行解 ， 這樣也得到最優(yōu)解 。 因 b列數(shù)字為負(fù)，故需進(jìn)行迭代運(yùn)算。檢查 b列的數(shù)字，若都為非負(fù)，檢驗(yàn)數(shù)都為非正，則已得到最優(yōu)解。若檢查 b列的數(shù)字時，至少還有一個負(fù)分量，檢驗(yàn)數(shù)保持非正，那么進(jìn)行以下計算。按 min｛ (B1b)i｜ (B1b)i＜ 0}＝ (B1b)l對應(yīng)的基變量 xi為換出變量 (3) 確定 換入變量 。若 所有 αlj≥0，則無可行解 ，停止 計算。 (4) 以 αlk為主元素 ， 按原單純形法在表中進(jìn)行迭代運(yùn)算 ， 得到新的計算表 。 41 ? 例 6 用對偶單純形法求解 min w=2x1+3x2+4x3 x1+2x2+x3≥3 2x1?x2+3x3≥4 x1， x2， x3≥0 解： 先將此問題化成下列形式，以便得到對偶問題的初始基可行解 max z= ? 2x1 ? 3x2 ? 4x3 ? x1 ? 2x2 ? x3+x4 = ? 3 ?2x1+x2 ? 3x3 +x5= ? 4 xj≥0， j=1,2,…,5 42 ? 例 6的初始單純形表，見表 26。 因 b列數(shù)字為負(fù)，故需進(jìn)行迭代運(yùn)算。 若所有α lj≥ 0，則無可行解 ，停止 計算。 計算 min(? 3, ? 4)= ? 4 故 x5為換出變量。換入、換出變量的所在列、行的交叉處“ ?2”為主元素。 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
公司管理相關(guān)推薦
鄂ICP備17016276號-1