線性規(guī)劃的對(duì)偶理論(2)-資料下載頁(yè)
2025-05-02 12:40本頁(yè)面
【正文】 ??????????53544531516125/1005/4125/102/11????bB5/3 ??5/3 ??5/44 ??第 56頁(yè) cj → 2 3 0 0 0 CB 基 b x1 x2 x3 x4 x5 cj zj x1 x4 x2 2 0 3 1 0 1/2 0 1/5 0 1 0 0 1/5 0 0 2 1 4/5 0 0 1 0 1/5 155 ??? ?5/3 ??5/3 ??5/44 ??迭代利用對(duì)偶單純形法繼續(xù)時(shí)當(dāng) ,0,5 4 ??? x?[ ] 2 x1 4 1 0 0 1/4 0 0 x3 0 0 1 1/2 2/5 3 x2 2 0 1 0 0 1/5 cj zj 0 0 0 1/2 3/5 5/3 ??5/22 ??? 515 ???? ?時(shí)，本題無可行解當(dāng) 15???第 57頁(yè) cj → 2 3 0 0 0 CB 基 b x1 x2 x3 x4 x5 cj zj x1 x4 x2 2 0 3 1 0 1/2 0 1/5 0 1 0 0 1/5 0 0 2 1 4/5 0 0 1 0 1/5 155 ??? ?5/3 ??5/3 ??5/44 ??迭代利用對(duì)偶單純形法繼續(xù)時(shí)當(dāng) ,0,15 1 ?? x?[ ] 0 x5 5 0 5/2 0 1 0 x4 16 4 0 0 1 0 3 x2 6 1 1 1/2 0 0 cj zj 1 0 3/2 0 0 15??15??第 58頁(yè) 課后習(xí)題選講 21 寫出下列線性規(guī)劃問題的對(duì)偶問題 ???????????????????? ???? ?),1。,1(0),1(),1(..m i n111 1njmixnjbxmiaxtsxczijmijijnjiijminjijij????),1( miy ai ??無約束),1( njy bj ??無約束? ?? ???minjbjjaii ybyaw1 1m a xijbjai cyy ??第 59頁(yè) 22 判斷下列說法是否正確，為什么？ (a) 如果線性規(guī)劃的原問題存在可行解 , 則其對(duì)偶問題也一定存在可行解 。 (b) 如果線性規(guī)劃的對(duì)偶問題無可行解 , 則原問題也一定無可行解 。 (c)在互為對(duì)偶的一對(duì)原問題與對(duì)偶問題中 , 不管原問題是求極大還是極小 , 原問題可行解的目標(biāo)函數(shù)值一定不超過其對(duì)偶問題可行解的目標(biāo)函數(shù)值 。 (d)任何線性規(guī)劃問題具有唯一的對(duì)偶問題。 ? ? 無界性 ? 無可行解或無界解 ? 第 60頁(yè) 23 應(yīng)用對(duì)偶理論證明下述線性規(guī)劃問題為無界解。 ??????????????????0,0,0122..m a x32132132121xxxxxxxxxtsxxz對(duì)偶問題 原問題 ??????????????????0,00112..2m i n2121212121yyyyyyyytsyyw約束 (1)(2)相加推出矛盾 無可行解 因?yàn)閷?duì)偶問題無可行解，所以原問題無可行解或無界解 而 (0,0,0)是原問題的可行解，所以原問題無界解 第 61頁(yè) 24 已知線性規(guī)劃問題： ??????????????????????????)4,3,2,1(0966283..42m a x321432214214321jxxxxxxxxxxxxtsxxxxzj對(duì)偶問題 ??????????????????????????)4,3,2,1(0114322..9668m i n314343214214321iyyyyyyyyyyyytsyyyywi要求 : (a)寫出其對(duì)偶問題； (b)已知原問題最優(yōu)解為 根據(jù)對(duì)偶理論 , 直接求出對(duì)偶問題的最優(yōu)解 . )0,4,2,2(??X由互補(bǔ)松弛性得 14322434321421?????????yyyyyyyyy由目標(biāo)函數(shù)相等得 169668 4321 ???? yyyy第 62頁(yè) 25 已知線性規(guī)劃問題 A和 B如下： 問題 A 問題 B ?????????????????????????),1(0..m a x1331221111njxbxabxabxatsxczjnjjjnjjjnjjjnjjj? ???????????????????????????),1(03)3(5555..m a x113131221111njxbbxaabxabxatsxczjnjjjjnjjjnjjjnjjj?對(duì)偶變量 對(duì)偶變量 321yyy321???yyy試分別寫出 yi同 間的關(guān)系式 )3,2,1(? ?iyi第 63頁(yè) ?????????????????????????),1(0..m a x1331221111njxbxabxabxatsxczjnjjjnjjjnjjjnjjj? ???????????????????????????),1(03)3(5555..m a x113131221111njxbbxaabxabxatsxczjnjjjjnjjjnjjjnjjj?對(duì)偶變量 對(duì)偶變量 321yyy321???yyy對(duì)偶問題 ),1(m i n332211332211njcyayayaybybybwjjjj????????),1(?)3(?5?5?)3(?5?5m i n31322113132211njcyaayayaybbybybwjjjjj??????????對(duì)偶問題 3322311 ?,5?,?3?5 yyyyyyy ????第 64頁(yè) 211 已知線性規(guī)劃問題： 如下時(shí)求解得最終單純形表當(dāng) 0)5,4,3,2,1(03..00)(m a x21225323222121214313212111543322111?????????????????????????ttjxtbxxaxaxatbxxaxaxatsxxxcxcxtczjx1 x2 x3 x4 x5 x3 5/2 0 1/2 1 1/2 0 x1 5/2 1 1/2 0 1/6 1/3 cjzj 0 4 0 4 2 上述最優(yōu)基不變值在什么范圍內(nèi)變化，時(shí)當(dāng)上述最優(yōu)解不變值在什么范圍內(nèi)變化，時(shí)當(dāng)?shù)闹岛痛_定211221321232221131211,0)(,0)(,,,)(ttcttbbbcccaaaaaaa??第 65頁(yè) 解 :(a) ),( 13 PPB ? ???????? ??? 3/16/1 02/11B???????????????????02/1112/102322211312111aaaaaaB????????????????????2)304)62(04)22(113132cccccc??????????????????113210232221131211aaaaaa?????????????????? 2/5 2/5211bbB????????????????? 10521bb?????????1026321ccc第 66頁(yè) x1 x2 x3 x4 x5 x3 5/2 0 1/2 1 1/2 0 x1 5/2 1 1/2 0 1/6 1/3 cjzj 0 4 0 4 2 10 6 6 2 10 0 0 上述最優(yōu)解不變值在什么范圍內(nèi)變化，時(shí)當(dāng) 12 ,0)( ttb ?543211 00102)6(m a x xxxxxtz ??????16 t?16 t?281 ?t6241?t361??t02 81 ??t 06241 ??t 03 61 ??? t86 1 ??? t由 得 第 67頁(yè) x1 x2 x3 x4 x5 x3 5/2 0 1/2 1 1/2 0 x1 5/2 1 1/2 0 1/6 1/3 cjzj 0 4 0 4 2 10 6 6 2 10 0 0 1535 2 ??? t由 得 上述最優(yōu)基不變值在什么范圍內(nèi)變化，時(shí)當(dāng) 21 ,0)( ttc ????????????????????????)5,4,3,2,1(01023352..001026m a x25321243254321jxtxxxxtxxxtsxxxxxzj??????????????????????????????6/152/)35(10353/16/102/12222tttt61523522tt??0615,02 35 22 ???? tt第 68頁(yè) CXz ?m ax?????0.. XbAXts線性規(guī)劃的標(biāo)準(zhǔn)形式 初始單純形表為 初始解 非基變量 基變量 b B N I cjzj ?N 0,…,0 基可行解 基變量 非基變量 B1b I B1N B1 cjzj 0,…,0 y1,…, ym N??111 0),( ?? ???????? BCBCyyY BBm?關(guān)系： jjjBjj YPcPBCc ????? ? 1?或 YACABCC B ???? ? 1?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1