資源描述：
《單純形法和對(duì)偶問題.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、第六章單純形法的靈敏度分析與對(duì)偶問題§1單純形表的靈敏度分析§2線性規(guī)劃的對(duì)偶問題§3對(duì)偶規(guī)劃的基本性質(zhì)§4對(duì)偶單純形法1單純形表2§1單純形表的靈敏度分析一、目標(biāo)函數(shù)中變量系數(shù)Ck靈敏度分析（在什么范圍內(nèi)變化，最優(yōu)解不變，與第二章，第三章聯(lián)系起來）在線性規(guī)劃的求解過程中，目標(biāo)函數(shù)系數(shù)的變動(dòng)將會(huì)影響檢驗(yàn)數(shù)的取值，但是，當(dāng)目標(biāo)函數(shù)的系數(shù)的變動(dòng)不破壞最優(yōu)判別準(zhǔn)則時(shí)，原最優(yōu)解不變，否則，原最優(yōu)解將發(fā)生變化，要設(shè)法求出新的最優(yōu)解。下面我們具體的分析1.在最終的單純形表里，Xk是非基變量由于約束方程系數(shù)增廣矩陣在迭代中只是其本身的行的初等變換與Ck沒有任何關(guān)系，所以當(dāng)
2、Ck變成Ck+Ck時(shí)，在最終單純形表中其系數(shù)的增廣矩陣不變，又因?yàn)閄k是非基變量，所以基變量的目標(biāo)函數(shù)的系數(shù)不變，即CB不變，可知Zk也不變，只是Ck變成了Ck+Ck。這時(shí)K=Ck-Zk就變成了Ck+Ck-Zk=K+Ck。要使原來的最優(yōu)解仍為最優(yōu)解，只要K+Ck≤0即可，也就是Ck的增量Ck≤-K。32.在最終的單純形表中，Xk是基變量當(dāng)Ck變成Ck+Ck時(shí)，最終單純形表中約束方程的增廣矩陣不變，但是基變量的目標(biāo)函數(shù)的系數(shù)CB變了，則ZJ(J=1,2,…..,N)一般也變了，不妨設(shè)CB=(CB1,CB2。。。,Ck,…，CBm),當(dāng)CB變成=(CB1,CB2
3、。。。,Ck+Ck,…,CBm),則：ZJ=(CB1,CB2。。。,Ck,…,,…，CBm)(a’1j,a’2j,…,a’Kj,…,a’mj)Z’J=(CB1,CB2。。。,Ck+Ck,…，CBm)(a’1j,a’2j,…,a’Kj,…,a’mj)=ZJ+Cka’Kj4§1單純形表的靈敏度分析根據(jù)上式可知檢驗(yàn)數(shù)J(J=1,2,…..,M)變成了’J,只要當(dāng)JK時(shí)，有’J=CJ-Z’J=J-CKa’Kj。要使最優(yōu)解不變，’J<=05§1單純形表的靈敏度分析例：目標(biāo)函數(shù)：Maxz=50X1+100X2約束條件：X1+X2≤3002X1+X2≤400X2≤250X
4、1，X2≥0最優(yōu)單純形表如下迭代次數(shù)基變量CBX1X2S1S2S3b501000002X1501010-150S2000-21150X210001001250ZJ501005005027500CJ-ZJ00-500-506§1單純形表的靈敏度分析對(duì)非基變量目標(biāo)函數(shù)系數(shù)：C3我們先對(duì)非基變量S1的目標(biāo)函數(shù)的系數(shù)C3進(jìn)行靈敏度分析。這里δ3=-50，所以當(dāng)c3的增量Δc3≤-（-50），最優(yōu)解不變。對(duì)基變量目標(biāo)函數(shù)系數(shù)：c1再對(duì)基變量x1的目標(biāo)函數(shù)的系數(shù)c1進(jìn)行靈敏度分析。在a11’,a12’,a13’,a14’,a15’中，除了知道a11’和a13’大于0，a
5、15’小于0，可知，有同樣有。這樣可以知道當(dāng)-50≤Δc1≤50時(shí)，也就是x1的目標(biāo)函數(shù)c1’在0≤c1’≤100時(shí)最優(yōu)解不變。7§1單純形表的靈敏度分析迭代次數(shù)基變量CBX1X2S1S2S3bC’11000002X11010-150S2000-21150X210001001250ZJC’1100C’10-C’1+100CJ-ZJ00-C’10C’1-1008從δ3≤0，得到-c1’≤0,即c1’≥0，并且從δ5≤0，得到c1’≤100。那么如果c1’取值超出這個(gè)范圍，必然存在一個(gè)檢驗(yàn)數(shù)大于0，我們可以通過迭代來得到新的最優(yōu)解。另外一種求最優(yōu)解不變的C’1變
6、化范圍方法在最終的單純形表中，用C’1代替原來的C1=50,計(jì)算得表常數(shù)項(xiàng)靈敏度分析之前的一點(diǎn)補(bǔ)充知識(shí)：9補(bǔ)充知識(shí)10補(bǔ)充知識(shí)11補(bǔ)充知識(shí)12補(bǔ)充知識(shí)13補(bǔ)充知識(shí)14§1單純形表的靈敏度分析二、約束方程中常數(shù)項(xiàng)的靈敏度分析（使對(duì)偶價(jià)格不變的b的變化范圍）回想一下：第2章例一各個(gè)約束的對(duì)偶價(jià)格：從上表我們可以發(fā)現(xiàn)各個(gè)松弛變量的Zj值，正好等于相應(yīng)變量的對(duì)偶價(jià)格。15迭代次數(shù)基變量CBX1X2S1S2S3b501000002X1501010-150S2000-21150X210001001250ZJ501005005027500CJ-ZJ00-500-50§1單
7、純形表的靈敏度分析單純形表中的Zj跟對(duì)偶價(jià)格的關(guān)系：對(duì)于含有小于等于號(hào)的約束條件，添加松弛變量轉(zhuǎn)化為標(biāo)準(zhǔn)型。這時(shí)這個(gè)約束條件的對(duì)偶價(jià)格就和松弛變量的Zj有關(guān)。對(duì)偶價(jià)格應(yīng)取松弛變量的Zj的值。對(duì)于含有大于等于號(hào)的約束條件，添加剩余變量化為標(biāo)準(zhǔn)型。這時(shí)這個(gè)約束條件的對(duì)偶價(jià)格就和這個(gè)剩余變量的有關(guān)了。這時(shí)約束條件的對(duì)偶價(jià)格應(yīng)取值的相反數(shù)-。對(duì)于含有等于號(hào)的約束條件，其約束條件的對(duì)偶價(jià)格就和該約束方程的人工變量有關(guān)了。其約束條件的對(duì)偶價(jià)格就等于此約束方程的人工變量的值。16§1單純形表的靈敏度分析17最終單純形表對(duì)于不同約束類型的對(duì)偶價(jià)格的取值。常數(shù)項(xiàng)的靈敏度分析-
8、》使對(duì)偶價(jià)格不變的bj靈敏度分析-》知道對(duì)偶價(jià)格Zj
