【正文】 ????? ???316212168410121111//bB24 第 2節(jié) 改進(jìn)單純形法 第 1步計(jì)算結(jié)束后的結(jié)果 ? ?? ?? ?? ? ? ?),(),(C,CC。 3 若以 Xs為基變量 ， 并標(biāo)記成 XB， 可將系數(shù)矩陣 （ A， I）分為 （ B， N） 兩塊 。確定換入、換出變量（ 1）確定初始基和初始基變量： （ 2）計(jì)算非基變量的檢驗(yàn)數(shù)，確定換入變量。 即原問題與對(duì)偶問題都是最優(yōu)解 。 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 從表 26看到，檢驗(yàn)數(shù)行對(duì)應(yīng)的對(duì)偶問題的解是可行解。 321 422m i n xxxz ????????????????????無約束321321321321,0,534332243xxxxxxxxxxxx? ?試用對(duì)偶單純形法求解下列線性規(guī)劃問題。用單純形法迭代一步，得表 222。 作業(yè) 3： 1. 課本 P74. (2)、 (3) ? 寫出下列線性規(guī)劃問題的對(duì)偶問題 。 當(dāng)參數(shù) t≥0時(shí)的最優(yōu)解變化 。 故重復(fù)上述迭代步驟，得表 2 8 。在單純形表中檢查 xl所在行的各系數(shù)αlj(j=1,2,… ， n)。,51252513PBxPPPB基變換： 33 計(jì)算 B的逆矩陣 ?????????????? ???????????????????18/1002/1004/118/12/14/133 E構(gòu)造?????????????????????????????????????????08121121204104100214210118100210041112313/////////BEB34 計(jì)算非基變量的檢驗(yàn)數(shù) ? ?? ?? ?已無正檢驗(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 及其逆矩陣和初始基。 12 求解線性規(guī)劃問題的關(guān)鍵是計(jì)算 B1 ，以下介紹一種比較簡便的計(jì)算 B1的方法。?????????目標(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)系。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ù)向量是換入變量??????????? ????