運(yùn)籌學(xué)-or(編輯修改稿)
2024-10-27 16:05 本頁面
【文章內(nèi)容簡介】 約束條件總數(shù)為 n個(gè) 決策變量 xj ≥0 第 j個(gè)約束條件類型為 ≥ 決策變量 xj ≤0 第 j個(gè)約束條件類型為 ≤ 決策變量 xj是自由變量 第 j個(gè)約束條件類型為 = ?原問題中的價(jià)值向量與對偶問題中的資源向量對換 ,“上下對換 ” . ?原問題 : X在 C和 A的右邊 。 對偶問題 :Y在 b和 A的左邊 ,“左右對換 ” 05643732532432321321321321321??????????????xxxxxxxxxxxxxxxZ,m i n05643732532432321321321321321?????????????????xxxxxxxxxxxxxxxZ,m a x321yyy04675343232532321321321321321??????????????????yyyyyyyyyyyyyyyW,m i n 321532 yyyW ???m a x321 32 yyy ??≤ 2 343 321 ???? yyy4675 321 ???? yyy0321 ?yyy ,≥ 031 ?yy , 02 ?y例 3 試求下述線性規(guī)劃問題的對偶問題 無約束432143243143214321006 42 2 53 532x。x,x。xxxxxxxxxxxxxxxzmi n???????????????? 解：設(shè)對偶變量為 y1,y2,y3,對偶問題模型為 ： Max w=5y1+4y2+6y3 y1 +2y2 y1 + y3 3y1 +2y2 +y3 y1 y2 +y3 ≥ ≤ ≤ = y1≥0, y2≤0, y3無約束 2 3 5 1 對偶問題的基本性質(zhì)和基本定理 1 對稱性定理 ：對偶問題的對偶是原問題 證明： 設(shè)原問題為??????0.m a xXbAXtsCXZ ??????0.m i nYCYAtsYb? ??????????0)(.)()m a x (YCAYtsbY? ??????????0.)m i n (39。XbAXtsCX? ??????0.m a xXbAXtsCXZ2 弱對偶性定理 若 X（ 0） 和 Y（ 0） 分別是原問題和對偶問題的可行解，則有 CX（ 0） ≤ Y（ 0） b 3 若原問題（對偶問題）為無界解，則其對偶問題（原問題）無可行解。 證明 : 因?yàn)?X（ 0） 是原問題的可行解，故有 AX（ 0） ≤ b。 又因?yàn)?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)不一定有可行解 。 逆命題不成立： (D)無可行解 ， (P)不一定為無界解 。 （ 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)解。
物理相關(guān)推薦
鄂ICP備17016276號-1