運(yùn)籌學(xué)——3單純形矩陣描述與改進(jìn)單純形法(文件)
【正文】 xtxxxtxxxxxxxz56 c j → 1 3 0 0 C B X B b x 1 x 2 x 3 x 4 1 3 x 1 x 2 2 4 1 0 0 1 2/3 1/3 1/3 1/3 c j z j 0 0 5/3 2/3 然后計(jì)算 ?????? ???????? ??????? ????03/13/13/13/21 tttbB 令 t=0， 用單純形法迭代兩次 ， 求解的結(jié)果 ， 見(jiàn)表 224。 t=5為第二臨界點(diǎn)。 t=9/7為第一臨界點(diǎn)。 當(dāng)參數(shù) t≥0時(shí)的最優(yōu)解變化 。 先令 t=0， 用單純形法求出最優(yōu)解； ? (2) 用靈敏度分析法 ， 將參變量 t直接反映到最終表中； ? (3) 當(dāng)參變量 t連續(xù)變大或變小時(shí) ， 觀察 b列和檢驗(yàn)數(shù)行各數(shù)字的變化 。 ? 參數(shù)線性規(guī)劃研究這些參數(shù)中某一參數(shù)連續(xù)變化時(shí) ， 使最優(yōu)解發(fā)生變化的各臨界點(diǎn)的值 。 ?對(duì)偶單純形法的 主要局限性 ：對(duì)大多數(shù)線性規(guī)劃問(wèn)題，很難找到一個(gè)初始基。 故重復(fù)上述迭代步驟，得表 2 8 。 12234,22m i n ?????????? ???????故 x1為換入變量。 43 ? 換出變量的確定： ? 換入變量的確定：按上述對(duì)偶單純形法計(jì)算步驟 (3)，即在單純形表中檢查 xl所在行的各系數(shù) α lj(j=1,2,… ， n)。 重復(fù)步驟 (1)～ (4)。在單純形表中檢查 xl所在行的各系數(shù)αlj(j=1,2,… ， n)。停止計(jì)算。 38 c j → 2 3 4 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 0 0 x 4 x 5 3 4 1 [ 2] 2 1 1 3 1 0 0 1 c j z j 2 3 4 0 0 從該表看到，檢驗(yàn)數(shù)行對(duì)應(yīng)的對(duì)偶問(wèn)題的解是可行解。 37 第 6節(jié) 對(duì) 偶單純形法 ? 在單純形表中進(jìn)行迭代時(shí) ， 在 b列中得到的是原問(wèn)題的基可行解 ， 而在檢驗(yàn)數(shù)行得到的是對(duì)偶問(wèn)題的 基解 。,51252513PBxPPPB基變換： 33 計(jì)算 B的逆矩陣 ?????????????? ???????????????????18/1002/1004/118/12/14/133 E構(gòu)造?????????????????????????????????????????08121121204104100214210118100210041112313/////////BEB34 計(jì)算非基變量的檢驗(yàn)數(shù) ? ?? ?? ?已無(wú)正檢驗(yàn)數(shù)注意：8/1,2/301000108/12/112/1204/10)3,0,2(0,0,433313333???????????????????????????????PPNNBCCBNN?35 得到最優(yōu)解： ?????????????????????????????????????244128/12/1162/1284/1013251*bBxxxX? ? 1424430213 ????????????? ? ,bBCz B*?目標(biāo)函數(shù)的最優(yōu)值為： 36 改進(jìn)單純形法步驟 1. 求線性規(guī)劃的標(biāo)準(zhǔn)形式，確定 1000000 , BBCCXX NBNB 及其逆矩陣和初始基。P,P,PBNBTNTB023001111512432431?????價(jià)值系數(shù)非基變量基變量基25 第 2節(jié) 改進(jìn)單純形法 第 2步： 計(jì)算非基變量的檢驗(yàn)數(shù)，確定換入變量 ? ?? ?? ? ? ?換入變量對(duì)應(yīng)注意：515111114321000414100010210130002111x,x/,//),(,)P,PN(NBCCBNN??????????????????????? ????????26 第 2節(jié) 改進(jìn)單純形法 確定換出變量 ? ?? ?3203,416,12m i n0m i n11111111xPBPBbBii對(duì)應(yīng)???????????????????????27 由此得到新的基 ? ???????????????????????? ???????????????????????????????????????????????????????4/1002142/1014/1000102/101100014001100014001041041,1121221112412BEBEPBPPPB2?主元素28 計(jì)算 RHS ?
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1