【正文】 出 ?167。 5 對偶單純形法 ?167。 占用設(shè)備時(shí)間 (h) I II 用于生產(chǎn)的能力 設(shè)備 A 2 2 12 設(shè)備 B 4 0 16 設(shè)備 C 0 5 15 利潤 (元 ) 2 3 例 1 生產(chǎn)計(jì)劃問題 21 對偶問題的提出 模型 21 32m a x xx ?1222 21 ?? xx164 1 ?x155 2 ?x0, 21 ?xx. 現(xiàn)有四海機(jī)器廠 , 為擴(kuò)大生產(chǎn)想租常山機(jī)器廠的設(shè)備 , 問常山機(jī)器廠分別以每小時(shí)什么價(jià)格才愿意出租自己的設(shè)備呢 ? 設(shè)設(shè)備 A, B, C每小時(shí)的出租價(jià)格分別為 y1, y2,和 y3元 出租條件 : 租金收入 ≥生產(chǎn)的獲利。 ),1( njx j ??? ),1( miy i ???設(shè) 是原問題的最優(yōu)解， 是其對偶問題的最優(yōu)解。反之如果約束條件取嚴(yán)格不等式 , 則該對應(yīng)的對偶變量一定為零。?1???njijij bxa ,?1???njijij bxa0? ?iy 在生產(chǎn)中 , 若某資源未充分利用時(shí) , 影子價(jià)格為 0；當(dāng)影子價(jià)格不為 0時(shí) , 表明該資源在生產(chǎn)中已耗費(fèi)完畢 . 5) 檢驗(yàn)數(shù)的經(jīng)濟(jì)意義 。 或這些參數(shù)在一個(gè)多大范圍內(nèi)變化時(shí) , 問題的最優(yōu)解不變 . 3. 如何解決 1) 用單純表法從頭計(jì)算 (此法既麻煩又沒有必要 ) 2) 把參數(shù)的變化直接反映到單純形表中，再繼續(xù)處理。 )15,16,12( 321 ??? ????b321 ??? 、,021 ?? ?? )15,16,12( 3????bT?????? ???? 53,544,53 333 ???0530544053 333 ?????? ??? ，即 1553 ??? ?類似可求得當(dāng) 231 4,0 ??? ????26,0 132 ????? ???問題的最優(yōu)基不變 第 39頁 解： cj → 2 3 0 0 0 CB 基 b x1 x2 x3 x4 x5 cj zj x1 x4 x2 2 0 3 3 1 0 1/2 0 1/5 3 0 1 0 0 1/5 4 0 0 2 1 4/5 0 0 1 0 1/5 ???????????????????????????32111516125/1005/4125/102/1???bB當(dāng) T?????? ??????? 53,5424,523 332131 ??????即 問題的最優(yōu)基不變 (3) 若 ，分析 在什么范圍內(nèi)變化時(shí) , 問題的最優(yōu)基不變。 (b) 如果線性規(guī)劃的對偶問題無可行解 , 則原問題也一定無可行解 。 ??????????????????0,0,0122..m a x32132132121xxxxxxxxxtsxxz對偶問題 原問題 ??????????????????0,00112..2m i n2121212121yyyyyyyytsyyw約束 (1)(2)相加推出矛盾 無可行解 因?yàn)閷ε紗栴}無可行解，所以原問題無可行解或無界解 而 (0,0,0)是原問題的可行解，所以原問題無界解 第 61頁 24 已知線性規(guī)劃問題： ??????????????????????????)4,3,2,1(0966283..42m a x321432214214321jxxxxxxxxxxxxtsxxxxzj對偶問題 ??????????????????????????)4,3,2,1(0114322..9668m i n314343214214321iyyyyyyyyyyyytsyyyywi要求 : (a)寫出其對偶問題； (b)已知原問題最優(yōu)解為 根據(jù)對偶理論 , 直接求出對偶問題的最優(yōu)解 . )0,4,2,2(??X由互補(bǔ)松弛性得 14322434321421?????????yyyyyyyyy由目標(biāo)函數(shù)相等得 169668 4321 ???? yyyy第 62頁 25 已知線性規(guī)劃問題 A和 B如下： 問題 A 問題 B ?????????????????????????),1(0..m a x1331221111njxbxabxabxatsxczjnjjjnjjjnjjjnjjj? ???????????????????????????),1(03)3(5555..m a x113131221111njxbbxaabxabxatsxczjnjjjjnjjjnjjjnjjj?對偶變量 對偶變量 321yyy321???yyy試分別寫出 yi同 間的關(guān)系式 )3,2,1(? ?iyi第 63頁 ?????????????????????????),1(0..m a x1331221111njxbxabxabxatsxczjnjjjnjjjnjjjnjjj? ???????????????????????????),1(03)3(5555..m a x113131221111njxbbxaabxabxatsxczjnjjjjnjjjnjjjnjjj?對偶變量 對偶變量 321yyy321???yyy對偶問題 ),1(m i n332211332211njcyayayaybybybwjjjj????????),1(?)3(?5?5?)3(?5?5m i n31322113132211njcyaayayaybbybybwjjjjj??????????對偶問題 3322311 ?,5?,?3?5 yyyyyyy ????第 64頁 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頁 解 :(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頁 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頁 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頁 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?