【正文】 對偶理論與靈敏度分析 一、 LP的對偶問題 課本 P6的生產(chǎn)計(jì)劃問題是一個(gè)在有限資源的條件下 ， 求使利潤最大的生產(chǎn)計(jì)劃安排問題 ， 其數(shù)學(xué)模型為： ????????????0,)(2623)(2432.34Zmaxxxxxxxxx21212121工時(shí)約束材料約束現(xiàn)從另一角度考慮此問題。 67 總 結(jié) 一、線性規(guī)劃模型的建立 確定決策變量 確定目標(biāo)函數(shù) 確定約束條件 二、線性規(guī)劃模型的求解 1）找到初始可行基解，建立初始單純形表 2）判斷最優(yōu)：所有檢驗(yàn)數(shù)大于等于 0時(shí)最優(yōu) 3）換基迭代：以負(fù)檢驗(yàn)數(shù)對應(yīng)的變量進(jìn)基，按最小元素法確定出基變量。 從表中可知原問題的最優(yōu)解為 X1=1/2， X2=3/2， 最優(yōu)目標(biāo)函數(shù)值為Z=9/4。 MinZ=x1++0x3+0x4 ?????????????0,0,2334321421321xxxxxxxxxx MinW=x5+x6 輔助問題： ????????????????0,0,0,23365432164215321xxxxxxxxxxxxxx原問題： 用單純形法求解的迭代表如下： 64 cj 0 0 0 0 1 1 CB XB b x1 x2 x3 x4 x5 x6 1 1 x5 x6 3 2 1 3 1 0 1 0 1 1 0 1 0 1 W 5 2 4 1 1 0 0 cj 0 0 0 0 1 1 CB XB b x1 x2 x3 x4 x5 x6 0 1 x2 x6 1 1 1/3 1 1/3 0 1/3 0 2/3 0 1/3 1 1/3 1 W 1 2/3 0 1/3 1 4/3 0 65 cj 0 0 0 0 1 1 CB XB b x1 x2 x3 x4 x5 x6 0 0 x2 x1 1/2 3/2 0 1 1/2 1/2 1/2 1/2 1 0 1/2 3/2 1/2 3/2 W 0 0 0 0 0 1 1 上述表中目標(biāo)函數(shù)值 W=0，且人工變量已全部出基，得到原問題的一個(gè)可行基 B=（ P2， P1）和一個(gè)基可行解 X=（ X2， X1） =（ 1/2， 3/2）。 （ 1） 63 第二階段：在第一階段所得的基可行解的基礎(chǔ)上 ， 將最終表中的人工變量列刪去 ， 同時(shí)將人工目標(biāo)函數(shù)行換為原問題的目標(biāo)函數(shù)作為第二階段計(jì)算的初始表 。若 W?0，則原問題無可行解，停止計(jì)算。 所以本題求解過程略 。 ③ 對于 minZ判別最優(yōu)性準(zhǔn)則應(yīng)是 Cj－ Zj≤0。 人工變量法常見的有大 M法和兩階段法。 因此 ， 該法的關(guān)鍵在于將人工變量全部換出 。 經(jīng)迭代后 ， 若人工變量全部被換成非基變量 ， 即人工變量全部出基 ， 則得到原問題的一個(gè)基可行解 。 當(dāng)增加的人工變量全部取值為 0時(shí) ， 才與原問題等價(jià) 。 e=0,d=5,b=5,c=10,a=23,b1=30,b2=40 59 ──用人工變量法求初始基可行解 （ 一 ） 人工變量法 若對 LP模型標(biāo)準(zhǔn)化后 ， 不具有 B=I時(shí) ， 如何辦 ？ 此時(shí)可采用人工變量法得到初始基可行解 。 cj 0 0 0 0 1 1 CB XB b x1 x2 x3 x4 x5 x6 0 2 1 x4 x1 x2 1 1 2 0 1/2 1/2 0 1/2 1/2 Z 10 15 5 0 0 1 1 0 1/2 1/2 0 1 3/2 0 25 0 0 3/2 0 3/2 1/2 57 用單純形法求解某極大化問題的單純形表如下，問表中參數(shù) a1,a2,a3,d,?1, ? 2為何取值范圍時(shí)，下列結(jié)論成立。 cj 4 3 0 0 CB XB b x1 x2 x3 x4 0 4 x3 x1 20/3 26/3 0 5/ 3 1 2/3 1 2/3 0 1/3 Z 104/3 0 1/3 0 4/3 55 cj 4 3 0 0 CB XB b x1 x2 x3 x4 3 4 x2 x1 4 6 0 1 3/5 2/5 1 0 2/5 3/5 Z 36 0 0 1/5 6/5 表中最后一行的所有檢驗(yàn)數(shù)均為非負(fù)數(shù)，表明目標(biāo)函數(shù)已達(dá)到最大值，上述表為最優(yōu)表。 53 例 5 求解下列線性規(guī)劃問題 ????????????0,26232432.34Zmaxxxxxxxxx21212121解：引進(jìn)松馳變量 x3, x4，化為標(biāo)準(zhǔn)形得： ????????????????0,26232432.0034Zmaxxxxxxxxxxxxxxx43214213214321從標(biāo)準(zhǔn)形中可看出存在可行基 B=（ P3， P4） =I，基變量為X3， X4；非基變量為 X1， X2。 其中主元LKa 變成 1 。 LKaKPLkLikikiabaab ??????? ?? 0|min?2? 按最小比值原則確定出基變量 xL： 3? 以 為主元，進(jìn)行初等行變換（又稱旋轉(zhuǎn)變換） 即將列向量 變換為單位列向量： 52 返回（ 2 ）。 2? 在 T(B)中 ， 若有 σk0 (1?k?n)， 且 xk的系數(shù)列向量 Pk?0， 則該問題無界 ， 停止計(jì)算 。 （ 2）在單純形表中，凡基變量所在的列向量必是單位列向量，其相應(yīng)的檢驗(yàn)數(shù)均為零。 2 單純形法與計(jì)算機(jī)求解 1. 解 LP 問題單純形法的基本思路： 求出一個(gè)初始基可行解 y 判別此基可行解是否 最 優(yōu) 解 換 基 迭 代 N 求出使目標(biāo)函數(shù)值得到 改善的基可行解 停 LP 問題的標(biāo)準(zhǔn)形 46 ?????????????????????????),.. .,2,1(0...... .........11221122111111njxbxaxaxbxaxaxbxaxaxjmnmnmmmmnnmmnnmm將目標(biāo)函數(shù)改寫為： Z+c1x1+c2x2+… +xn=0 把上述方程組和目標(biāo)函數(shù)方程構(gòu)成 n+1個(gè)變量 ， m+1個(gè)方程的方程組 ， 并寫成增廣矩陣的形式： （ 表格形式 ） （ 1） 建立初始單純形表 ， 假定 B=I， b≥0 設(shè) maxZ=c1x1+c2x2+… +xn 47 Z x1 x2 ? xm xm + 1 ? xn b 0 1 0 ? 0 a1 m + 1 ? a1n b1 0 0 1 ? 0 a2 m + 1 ? a2n b2 0 0 0 ? 1 am m + 1 ? amn bm 1 c1 c2 ? cm cm + 1 ? cn 0 以非基變量表示基變量形式?????n1mjjijiixabx ， 代入Z 中的基變量 , 有 ? ? ?? ?? ?????minmjnmjjjjijiixcXabcZ1 1 1)( ? ? ? ?? ? ?? ?????miminmjnmjjjjjiiiixcxacbc1 1 1 1)( ? ? ?? ?? ????minmjjjmiijiiixcacbc1 1 1)( 48 令? ?? ???mimijiijiiacZbcZ1 10, 于是 ??????nmjjjjoxcZZZ1)(因此，上述的增廣矩陣就可寫成： Z x1 x2? xmxm+ 1? xn b0 1 0 ? 0 a1 m + 1? a1n b10 0 1 ? 0 a2 m + 1? a2n b20 0 0 ? 1 amm + 1? amn bm 1 0 0 ? 0111 ????? mmiimicac ???miiniac1－ cn