對偶與對偶算法教學課件

《對偶與對偶算法教學課件》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

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

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

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

4、刻劃增加不同的效果？例1最優(yōu)目標值增量第一個約束的常數(shù)項加1:最優(yōu)目標值增量第二個約束的常數(shù)項加1最優(yōu)目標值增量第三個約束的常數(shù)項加1不同約束常數(shù)項對最優(yōu)目標值的影響例1對偶問題最優(yōu)解對偶問題最優(yōu)解正好是最優(yōu)目標函數(shù)的增量?。ㄓ脤ε夹则炞C）設對偶問題最優(yōu)解為，由強對偶性知，原問題的最優(yōu)目標值為所以，原問題最優(yōu)目標關于的偏導數(shù)分別是，說明增加一個單位可望增加的最優(yōu)目標值，故稱其為的影子價格原問題對偶問題一般情況原問題對偶問題如果原問題的某個約束在最優(yōu)解處不是嚴格等式，例如，增加不會增加最優(yōu)目標值，所以其影子價格等于0，因此有互補松弛等式同樣道理可得

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

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

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

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