對偶問題的基本性質(1)(編輯修改稿)
2025-06-20 07:19 本頁面
【文章內容簡介】 Z x x xx x xx x xstx x xx x x? ? ?? ? ???? ? ???? ? ??? ???無約束返回 上頁 下頁 對偶問題 三、最優(yōu)性定理： —— 若 和 分別是（ 1）和（ 2）的 可行解，且有 則 分別是（ 1）和（ 2）的最優(yōu)解 。 ?? YX???? ? YXbYCX ,則 為（ 1）的最優(yōu)解， 反過來可知： 也是（ 2）的最優(yōu)解。 ?X?YbYCXbYXC?????? ,證明：因為（ 1）的任一可行解 均滿足 X對偶問題的基本性質 返回 上頁 下頁 對偶問題 原問題與對偶問題的解一般有三種情況 ： ?一個有有限最優(yōu)解 另一個有有限最優(yōu)解。 ?一個有無界解 另一個無可行解。 ?兩個均無可行解。 四、對偶定理（強對偶性）： —— 若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標函數值相等 。 對偶問題的基本性質 返回 上頁 下頁 對偶問題 五、互補松弛性： —— 若 分別是原問題（ 1）與對偶問題（ 2）的可行解， 分別為（ 1）、（ 2）的松弛變量，則： 即： YX ?,?SS YX ,YXXYXY SS ?,?0?,0? ??? 為最優(yōu)解 ??????????? ???????????????0??0?,??0?0?0??0)?(?0?1iiisiinjjijisiisiiSybXAxbxaXAxyxyXAbYXY原問題第 i條約束 A的第 i行 返回 上頁 下頁 對偶問題 ?????????????????0???0?0?)?(0?)?(0?jjjjjjjjjSxcPYcPYxxcPYXCAYXY另一方面： 對偶問題的第 j條約束 說明： 在線性規(guī)劃問題的最優(yōu)解中，如果對應某一約束條件的對偶變量最優(yōu)值為非零，則該約束條件針對最優(yōu)值是嚴格等式；反之如果約束條件針對最優(yōu)值取嚴格不等式，則其對應的對偶變量最優(yōu)值一定為零。 返回 上頁 下頁 對偶問題 ?互補松弛定理應用： ? （ 1）
畢業(yè)設計相關推薦
鄂ICP備17016276號-1