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