對(duì)偶與對(duì)偶算法教學(xué)課件

《對(duì)偶與對(duì)偶算法教學(xué)課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、對(duì)偶性與對(duì)偶算法線性規(guī)劃對(duì)偶性質(zhì)求解標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題最終要找到一個(gè)基陣滿(mǎn)足而最優(yōu)目標(biāo)值等于記，原問(wèn)題有最優(yōu)解時(shí)，滿(mǎn)足以下約束可否在滿(mǎn)足以上約束的解中找到，進(jìn)而找到？設(shè)是原問(wèn)題的任意一個(gè)可行解，即滿(mǎn)足對(duì)任何滿(mǎn)足不等式約束的，成立下述線性規(guī)劃問(wèn)題的最優(yōu)目標(biāo)值不會(huì)小于原問(wèn)題任何可行解的目標(biāo)函數(shù)值當(dāng)是原問(wèn)題最優(yōu)基陣時(shí)，滿(mǎn)足其中是決定的最優(yōu)的基本可行解求解上面的線性規(guī)劃問(wèn)題能找到原問(wèn)題的最優(yōu)基矩陣定義：標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題原問(wèn)題對(duì)偶問(wèn)題矩陣形式（）原問(wèn)題和對(duì)偶問(wèn)題之間的關(guān)系強(qiáng)對(duì)偶性：若原問(wèn)題有最優(yōu)解，則對(duì)偶問(wèn)題一定也有最優(yōu)解，并且最優(yōu)目標(biāo)值相等，即則

2、弱對(duì)偶性：若和分別是原、對(duì)偶問(wèn)題可行解，即規(guī)范形式線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題原問(wèn)題標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題標(biāo)準(zhǔn)線性規(guī)劃對(duì)偶問(wèn)題原問(wèn)題對(duì)偶問(wèn)題等價(jià)問(wèn)題標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題對(duì)偶問(wèn)題的對(duì)偶問(wèn)題原問(wèn)題對(duì)偶問(wèn)題對(duì)偶問(wèn)題的對(duì)偶問(wèn)題是原問(wèn)題結(jié)論：任何原問(wèn)題和對(duì)偶問(wèn)題之間都存在下述相互關(guān)系弱對(duì)偶性：原對(duì)偶問(wèn)題任何可行解的目標(biāo)值都是另一問(wèn)題最優(yōu)目標(biāo)值的界（推論：原對(duì)偶問(wèn)題目標(biāo)值相等的一對(duì)可行解是各自的最優(yōu)解）強(qiáng)對(duì)偶性：原對(duì)偶問(wèn)題只要有一個(gè)有最優(yōu)解，另一個(gè)就有最優(yōu)解，并且最優(yōu)目標(biāo)值相等原對(duì)偶有最優(yōu)解有最優(yōu)解問(wèn)題無(wú)界問(wèn)題無(wú)界無(wú)可行解無(wú)可行解不會(huì)不會(huì)不會(huì)不會(huì)不會(huì)不會(huì)出現(xiàn)的情況：原問(wèn)題對(duì)

3、偶問(wèn)題含義：如果原（對(duì)偶）問(wèn)題某不等式是松的（不等于0）則其相應(yīng)的對(duì)偶（原）變量必須是緊的（等于0）互補(bǔ)松弛性定理若、分別是原（對(duì)偶）問(wèn)題可行解，則它們分別是各自問(wèn)題最優(yōu)解的充要條件是滿(mǎn)足互補(bǔ)松弛性等式等價(jià)于證明充分性：由以上兩式可得，根據(jù)弱對(duì)偶性的推論可知兩者分別是各自問(wèn)題的最優(yōu)解證明必要性：當(dāng)和是原、對(duì)偶問(wèn)題的最優(yōu)解時(shí)，所以由強(qiáng)對(duì)偶性可知，再利用可行性條件可得例原問(wèn)題對(duì)偶問(wèn)題已知原問(wèn)題最優(yōu)解，求對(duì)偶問(wèn)題最優(yōu)解利用互補(bǔ)松弛定理少一個(gè)方程，還有沒(méi)有其它信息可以利用？對(duì)偶問(wèn)題原問(wèn)題最優(yōu)解影子價(jià)格原問(wèn)題如果增加某些的數(shù)值，最優(yōu)目標(biāo)值應(yīng)該增加能否定量地

4、刻劃增加不同的效果？例1最優(yōu)目標(biāo)值增量第一個(gè)約束的常數(shù)項(xiàng)加1:最優(yōu)目標(biāo)值增量第二個(gè)約束的常數(shù)項(xiàng)加1最優(yōu)目標(biāo)值增量第三個(gè)約束的常數(shù)項(xiàng)加1不同約束常數(shù)項(xiàng)對(duì)最優(yōu)目標(biāo)值的影響例1對(duì)偶問(wèn)題最優(yōu)解對(duì)偶問(wèn)題最優(yōu)解正好是最優(yōu)目標(biāo)函數(shù)的增量?。ㄓ脤?duì)偶性驗(yàn)證）設(shè)對(duì)偶問(wèn)題最優(yōu)解為，由強(qiáng)對(duì)偶性知，原問(wèn)題的最優(yōu)目標(biāo)值為所以，原問(wèn)題最優(yōu)目標(biāo)關(guān)于的偏導(dǎo)數(shù)分別是，說(shuō)明增加一個(gè)單位可望增加的最優(yōu)目標(biāo)值，故稱(chēng)其為的影子價(jià)格原問(wèn)題對(duì)偶問(wèn)題一般情況原問(wèn)題對(duì)偶問(wèn)題如果原問(wèn)題的某個(gè)約束在最優(yōu)解處不是嚴(yán)格等式，例如，增加不會(huì)增加最優(yōu)目標(biāo)值，所以其影子價(jià)格等于0，因此有互補(bǔ)松弛等式同樣道理可得

5、設(shè)是原問(wèn)題的最優(yōu)解，是對(duì)偶問(wèn)題的最優(yōu)解物理意義為生產(chǎn)單位產(chǎn)品的利潤(rùn)減去按影子價(jià)格計(jì)算的資源的總成本，如果差值大于零，應(yīng)繼續(xù)生產(chǎn)，所以最優(yōu)解必須滿(mǎn)足所有檢驗(yàn)數(shù)非正如果原問(wèn)題為標(biāo)準(zhǔn)型是最優(yōu)基矩陣，在推導(dǎo)強(qiáng)對(duì)偶性時(shí)已說(shuō)明其對(duì)偶問(wèn)題的最優(yōu)解為，于是，非基變量的檢驗(yàn)數(shù)可寫(xiě)成影子價(jià)格只能在局部范圍內(nèi)反映資源增長(zhǎng)（即增加約束的右邊常數(shù)）可以產(chǎn)生的目標(biāo)函數(shù)的增值，一旦資源增長(zhǎng)導(dǎo)致最優(yōu)基矩陣改變，原來(lái)的最優(yōu)對(duì)偶變量值一般情況下不等于單位資源增長(zhǎng)帶來(lái)的目標(biāo)函數(shù)的增值，從而失去影子價(jià)格的意義注意改變，但不變，影子價(jià)格不變改變導(dǎo)致改變，影子價(jià)格改變影子價(jià)格不變，最優(yōu)目標(biāo)

6、值增量等于例如：例1中第三個(gè)約束的常數(shù)項(xiàng)加1如果最優(yōu)基改變，最優(yōu)目標(biāo)值增量不等于對(duì)偶單純型法例1如果取，用左乘等式約束兩邊，可將其變換成以下等價(jià)的標(biāo)準(zhǔn)線性規(guī)劃模型將的表示式代入目標(biāo)函數(shù)，原問(wèn)題等價(jià)為變換后的等價(jià)問(wèn)題對(duì)應(yīng)的單純型表為該單純型表的檢驗(yàn)數(shù)均為非正數(shù)，如果右邊常數(shù)沒(méi)有負(fù)數(shù)，已經(jīng)得到原問(wèn)題的最優(yōu)解能否在保持檢驗(yàn)數(shù)非正的前提下消除負(fù)的右邊數(shù)？②①①×(-0.5)+②①×(-2)+②或合格不合格選比值小的進(jìn)基！出基變量行非基變量的系數(shù)全為負(fù)數(shù)②①①×(-2)+②合格選比值小的變量進(jìn)基時(shí)不用考慮負(fù)數(shù)！出基變量行非基變量的系數(shù)中有正數(shù)出基變量行的變

7、量系數(shù)全為正數(shù)時(shí)原問(wèn)題無(wú)解！不可能同時(shí)成立出基變量行非基變量的系數(shù)全為正數(shù)一般情況：要處理的等式約束和目標(biāo)約束可寫(xiě)成用進(jìn)基替換，可驗(yàn)證所有檢驗(yàn)數(shù)保持非正若中沒(méi)負(fù)數(shù)，原問(wèn)題無(wú)可行解否則可確定其中是出基變量，，其中用進(jìn)基替換得到新的檢驗(yàn)數(shù)的過(guò)程如下：①①×()+②②所有檢驗(yàn)數(shù)保持非正進(jìn)基出基后的表回到開(kāi)始的單純型表常數(shù)項(xiàng)全部非負(fù)檢驗(yàn)數(shù)全部非正已經(jīng)得到最優(yōu)解一般情況：消除負(fù)的右邊常數(shù)后可能在常數(shù)項(xiàng)中產(chǎn)生新的負(fù)常數(shù)，例如，在原表中將第三行除以得變換后的前兩個(gè)常數(shù)值取決于所在列的前兩個(gè)數(shù)據(jù)，完全可能出現(xiàn)負(fù)數(shù)繼續(xù)迭代能否保證收斂？由于每次迭代是從一個(gè)不可行的

8、基矩陣轉(zhuǎn)到另一個(gè)不可行的基矩陣（一旦遇到可行的基矩陣就得到了最優(yōu)解），而基矩陣的總數(shù)是有限的，如果不出現(xiàn)循環(huán)，算法一定在有限步內(nèi)停止于最