運籌學線性規(guī)劃對偶問題(編輯修改稿)
2025-06-19 22:18 本頁面
【文章內容簡介】 /4 － 15/2 x1 7/2 1 0 0 1/4 － 1/2 x2 3/2 0 1 0 － 1/4 3/2 0 0 0 1/4 1/2 對偶問題的剩余變量 對偶問題變量 y4 y5 y1 y2 y3 jj zc ? 對偶問題變量 對偶問題的剩余變量 y1 y2 y3 y4 y5 y2 1/4 － 5/4 1 0 － 1/4 1/4 y3 1/2 15/2 0 1 1/2 － 3/2 15/2 0 0 7/2 3/2 原問題松弛變量 x3 x4 x5 原問題變量 x1 x2 二、原規(guī)劃與對偶規(guī)劃問題的變量及解之間的對應關系 ● 對偶 (min型 )變量的最優(yōu)解等于原問題 松弛變量 檢驗數(shù)的絕對值 ● 對偶問題最優(yōu)解的剩余變量解值等于原問題 對應變量 的檢驗數(shù)的絕對值 ● 由于原問題和對偶問題是相互對偶的，因此對偶問題的檢驗數(shù)與原問題的解也有類似上述關系 。 ● 更一般地講，不管原問題是否標準，在 最優(yōu)解的單純型表 中，都有原問題 虛變量 (松弛或剩余 ) 的檢驗數(shù)對應其對偶問題 實變量 (對偶變量 )的最優(yōu)解 ， 原問題 實變量 (決策變量 ) 的檢驗數(shù)對應其對偶問題 虛變量 (松弛或剩余變量 )的最優(yōu)解。因此，原問題或對偶問題只需求解其中之一就可以了。 三、線性規(guī)劃的對偶定理 1. 弱對偶性（ 弱 對偶定理 ） 如果 ),2,1( njxj ??是 原 問 題 (max) 的 可 行 解 ，),2,1( miy i ?? 是對偶問題 (mi n) 的可行解，則恒有 ?????miiinjjj ybxc11 證明： ??? ?? ??? ?? ????? ?? ??? ?? ????????miiinjjjminjijijmiinjjijmiiiminjijijnjjmiiijnjjjybxcyxayxaybyxaxyaxc111 11 111 11 11)()
高考資料相關推薦
鄂ICP備17016276號-1