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