運籌學-or-文庫吧資料
2024-10-13 16:05本頁面
【正文】 試用對偶理論證明上述線性規(guī)劃問題無最優(yōu)解。 證明：設(shè) X（ 0） 是原問題的最優(yōu)解，相應的最優(yōu)基為B, 非基變量的檢驗數(shù)為 CN CBB1N≤0 全體檢驗數(shù)有 C CBB1A≤0 ，即 C≤ CBB1A 令 Y（ 0） = CBB1，則有 Y（ 0） A≥C 即 是對偶問題的可行解 (Y（ 0） ≥ 0,松馳變量的檢驗數(shù) )。 設(shè) Y為對偶問題的任一可行解，同理有 Yb ≥ Y（ 0） b 即 Y（ 0） 是對偶問題的最優(yōu)解。 （ D）不可行 （ P）無界 （ P）不可行 )2,1(0)(11m i n212121??????????jyDyyyyyywj例 : 4最優(yōu)性定理 若 X（ 0） 和 Y（ 0） 分別是原問題和對偶問題的可行解，且有 C X（ 0） =Y（ 0） b , 則 X（ 0） 和 Y（ 0） 分別是原問題和對偶問題的最優(yōu)解。 又因為 Y(0)是對偶問題的可行解，則有 Y（ 0） AX（ 0） ≤ Y（ 0） b, 及 Y（ 0） A≥C, 故 C X（ 0） ≤ Y（ 0） A X（ 0） ≤ Y（ 0） b 亦即 C X（ 0） ≤ Y（ 0） b 證畢 )2,1(0)(11m a x212121???????????jxPxxxxxxZj注意：此性質(zhì)說明： (P)有可行解 ， (D)不一定有可行解 。XbAXtsCX? ??????0.m a xXbAXtsCXZ2 弱對偶性定理 若 X（ 0） 和 Y（ 0） 分別是原問題和對偶問題的可行解，則有 CX（ 0） ≤ Y（ 0） b 3 若原問題（對偶問題）為無界解，則其對偶問題（原問題）無可行解。x,x。yyCAyytsbyy? ??? ??自由YCYAtsYb.m i n ? xj yix1 x2 ┅ xn原關(guān)系 m i n ωy1y2┇yma11 a12 ┅ a1 na21 a22 ┅ a2 n┇ ┇ ┇am1 am2 ┅ am n≤≤┇≤b1b2┇bm對偶關(guān)系 ≥ ≥ ┅ ≥m a x Z c1 c2 ┅ cnm a x Z = m i n ω 2. 其它形式 ， 按線性規(guī)劃化標準形的方法進行 ? 總結(jié)： 原問題與對偶問題的對應關(guān)系 進一步有 原問題（或?qū)ε紗栴}） 對偶問題（或原問題） 目標函數(shù) max z 目標函數(shù) min w 約束條件 : m個 對偶變量數(shù) : m個 變量 第 i個約束條件類型約束為 ≤ 對偶變量 : yi對偶變量 : ≥0 第 i個約束條件類型約束為 ≥ 對偶變量 : yi ≤0 第 i個約束條件類型約束為 = 對偶變量 : yi是 自由變量 決策變量總數(shù) :n 個 約束條件總數(shù)為 n個 決策變量 xj ≥0 第 j個約束條件類型為 ≥ 決策變量 xj ≤0 第 j個約束條件類型為 ≤ 決策變量 xj是自由變量 第 j個約束條件類型為 = ?原問題中的價值向量與對偶問題中的資源向量對換 ,“上下對換 ” . ?原問題 : X在 C和 A的右邊 。39。39。39。39。39。39。39。39。XybAXybAXtsCXZ ??????????????????????????0.m a xXbbXAAtsCXZ ? ?? ?? ??????????
物理相關(guān)推薦
鄂ICP備17016276號-1