【正文】 福州大學公共管理學院 1 第二章 對偶理論和靈敏度分析 一、單純形法的矩陣描述 Cj C1 C2 …………… Cj…………. Cn CB XB b x1 x2 … xj … xn xB1 xB2 … xBn b1 b2 ... bn a11 a12 … a1j … a1n a21 a22 … a2j … a2n … an1 an2 … anj … ann 檢驗數(shù) ?j 福州大學公共管理學院 2 設線性規(guī)劃問題 : 目標函數(shù) max z=CX。 約束條件 AX≤b。 非負條件 X≥0 福州大學公共管理學院 3 給這線性規(guī)劃問題的約約束條件加入松弛變量以后，得到標準型： max z=CX+0Xs。 AX+IXs=b。 X， X s≥ 0 這里 I 是 m m單位矩陣。 ???????????1001?????I福州大學公共管理學院 4 第二章 對偶理論和靈敏度分析 初始單純形表和最終單純形矩陣表示如下 : Cj CN CB 0 0 XS b XN XB XS XS b N B I 檢驗數(shù) ?j Cj CN CB 0 CB XB b XN XB XS XB B1b B1N BB1 B1 檢驗數(shù) ?j CN CB B1N CB B1 福州大學公共管理學院 5 令非基變量 =0；由上式得到： bB。bBX)(1B11Cz0????????????目標函數(shù)的值基可行解福州大學公共管理學院 6 二、改進單純形法 求解線性規(guī)劃問題的關鍵是計算 以下介紹一種比較簡便的計算方法 設 m?m系數(shù)矩陣 A，求其逆矩陣。 1?B???????????????mmmmmmaaaaaaaaaA??????212222111211福州大學公共管理學院 7 可以先從第 1列開始 以 為主元素 , 進行變換 ???????????????121111maaaP?11a福州大學公共管理學院 8 )1(///11111121111112111???????????????????????????????aaaaaaaaPmm???主元素福州大學公共管理學院 9 然后 構造 含有（ 1）列，而其他列都是單位列的矩陣 ?????????????????110011111121111a/aa/aa/Em???福州大學公共管理學院 10 可得到： ??????????????????????????????)(mm)(m)(m)()(m)(aaaaaaAE。PE1121212211112111001001???????1121122211211121 aaaaaaaa ??福州大學公共管理學院 11 而后以第 2列的 為主元素，進行變換 )(a/aa/a/aP)()(m)()()()(2112212122122112212??????????????????)(a 122福州大學公共管理學院 12 然后 構造 含有（ 2）列，而其他列都是單位列的矩陣 ?????????????????1001001122121221221122??????)()(m)()()(a/aa/a/aE福州大學公共管理學院 13 可得到 ???????????????)(mm)(m)(m)(m)()(aaaaaaAEE222212322321312001001???????福州大學公共管理學院 14 重復以上的步驟，直到獲得 112111????????????????? AAEEEm??福州大學公共管理學院 15 ? 求單純形表的基矩陣的逆矩陣也可以用這方法 例：用改進單純形法求解線性規(guī)劃問題： 1241648200032524132154321????????????xxxxxxxxxxxxzma x福州大學公共管理學院 16 第 1步 ：確定初始基，初始基變量 。確定換入，換出變量。 （ 1）確定初始基和初始基變量： ? ????????????????????????54354300111xxxX。P,P,PBB福州大學公共管理學院 17 （ 2）計算非基變量的檢驗數(shù)，確定換入變量。 ? ?? ?? ? ? ?換入變量對應注意：212100103240204110001000100032000x,x,),(,)P,PN(NBCCBNN?????????????????????????????福州大學公共管理學院 18 (3) 確定換出變量 計算： 表示選擇 0的元素 ? ?? ?5341201628021021010x,mi nPBPBbBmi nii對應???????????????????????福州大學公共管理學院 19 （ 4）基變換計算 將新的基 單位矩陣。計算： ? ? ?243 P,P,P?????????? ???????????? ??????????????410121141021402112//E//P ；構造主元素??????????? ?????????????????????? ?????4101211111410121110111////BEB福州大學公共管理學院 20 （ 5）計算非基變量的系數(shù)矩陣 ?????????? ?????????????????????? ???????????????410214114141012111411111////NBN福州大學公共管理學院 21 （ 6）計算 RHS ??????????????????????????????? ???316212168410121111//bB福州大學公共管理學院 22 第 1步計算結束后的結果 ? ?? ?? ?? ? ? ?),(),(C,CC。x,xX。x,x,xX。P,P,PBNBTNTB023001111512432431?????價值系數(shù)非基變量基變量基福州大學公共管理學院 23 第 2步 重復第 1步的計算步驟 從新的基，基變量開始。 福州大學公共管理學院 24 計算非基變量的檢驗數(shù)，確定換入變量。 ? ?? ?? ? ? ?換入變量對應注意：515111114321000414100010210130002111x,x/,//),(,)P,PN(NBCCBNN??????????????????????? ????????福州大學公共管理學院 25 (3) 確定換出變量 計算： 表示選擇 0的元素 ? ?? ?120341612011111111x,mi nPBPBbBmi nii對應???????????????????????福州大學公共管理學院 26 ? ???????????????????????? ??????????????????????????????????????????????????????410021421014100010210110001400110001400104104111212212412////BEBEPP,P,PB2?主元素福州大學公共管理學院 27 計算 RHS ???????????????????????????????????3821216841002142