【正文】 第 1頁(yè) 線性規(guī)劃問題具有對(duì)偶性 ,即任何一個(gè)線性規(guī)劃問題 ,都存在另一個(gè)線性規(guī)劃問題問題與之對(duì)應(yīng) .如果把其中一個(gè)問題叫做原問題 ,則另外一個(gè)就叫做它的對(duì)偶問題 .并稱這兩個(gè)相互聯(lián)系的問題為一對(duì)對(duì)偶問題 .研究對(duì)偶問題之間的關(guān)系及其性質(zhì) ,就是線性規(guī)劃的對(duì)偶理論 (Duality Theory). 第 2章 線性規(guī)劃的對(duì)偶理論 第 2頁(yè) ?167。 1 對(duì)偶問題的提出 ?167。 2 原問題與對(duì)偶問題 ?167。 3 對(duì)偶問題的基本性質(zhì) ?167。 4 影子價(jià)格 ?167。 5 對(duì)偶單純形法 ?167。 6 靈敏度分析 ?167。 7 參數(shù)線性規(guī)劃 第 3頁(yè) 常山機(jī)器廠用 A、 B、 C三種設(shè)備生產(chǎn) I、 II兩種產(chǎn)品。問該企業(yè)應(yīng)安排生產(chǎn)使總的利潤(rùn)收入為最大。 占用設(shè)備時(shí)間 (h) I II 用于生產(chǎn)的能力 設(shè)備 A 2 2 12 設(shè)備 B 4 0 16 設(shè)備 C 0 5 15 利潤(rùn) (元 ) 2 3 例 1 生產(chǎn)計(jì)劃問題 21 對(duì)偶問題的提出 模型 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)的獲利。 四海機(jī)器廠接受條件 : 租金要低 ?????????????0,352242151612m i n3213121321yyyyyyyyyywLP1 LP2 第 4頁(yè) 原問題 對(duì)偶問題 ??????????????),1(0),1(..m a x11njxmibxatsxczjnjijijnjjj????????????????),1(0),1(..m i n11miynjcyatsybwimijiijmiii??矩陣形式 ??????0..m a xXbAXtsCXz?????????0..m i nYCYAtsYbw第 5頁(yè) 22 原問題與對(duì)偶問題 對(duì)應(yīng)關(guān)系： m i nm ax(1) (2) 變量的 個(gè)數(shù) 約束條件個(gè)數(shù) = (3) (原 )約束條件 ≥ (4) 右端項(xiàng) 目標(biāo)函數(shù) 的系數(shù) (對(duì)偶 )約束條件 ≥ 第 6頁(yè) 原問題 (求極大 ) c1 c2 … 右端項(xiàng) x1 x2 … xn a11 a12 … a1n a21 a22 … a2n am1 am2 … amn mbbb????21? ? ? ?nccc ??? ?21y1 y2 ym b1 b2 bm ? 對(duì)偶問題(求極小 ) 右端項(xiàng) 第 7頁(yè) 原問題 (對(duì)偶問題 ) 對(duì)偶問題 (原問題 ) ?????????無(wú)約束個(gè)變量00n??????????個(gè)約束條件m約束條件個(gè)??????????n變量個(gè)??????????00m目標(biāo)函數(shù) max 目標(biāo)函數(shù) min 目標(biāo)函數(shù)中變量的系數(shù) 約束條件右端項(xiàng) 約束條件右端項(xiàng) 目標(biāo)函數(shù)中變量的系數(shù) 第 8頁(yè) 例 2 寫出下列線性規(guī)劃的對(duì)偶問題 ??????????????????????0,0837435522..)1(365m a x32321321321321xxxxxxxxxxxtsxxxz???????????????????????????),1(),1(0),1(),1(..)2(m a x1111111nnjxnnjxmmibxammibxatsxczjjnjijijnjijijnjjj????無(wú)約束第 9頁(yè) ??????????????????????0,0837435522..)1(365m a x32321321321321xxxxxxxxxxxtsxxxz321 835m i n yyyw ???無(wú)約束1y02 ?y03 ?y54 321 ??? yyy6752 321 ??? yyy332 321 ??? yyy第 10頁(yè) ???????????????????????????????),1(),1(0),1(),1(..m a x1111111nnjxnnjxmmibxammibxatsxczjjnjijijnjijijnjjj????無(wú)約束???miii ybw1m in),1(0 1miy i ???),1( 1 mmiy i ???無(wú)約束????mijiij njcya11 ),1( ??????mijiij nnjcya11 ),1( ?第 11頁(yè) 寫出下列線性規(guī)劃的對(duì)偶問題 321 365m a x xxxz ??????????????????????????00332675254..835m i n32321321321321yyyyyyyyyyytsyyyw03 ?x35 321 ???? xxx無(wú)約束1x02 ?x8374 321 ??? xxx522 321 ??? xxx第 12頁(yè) 23 對(duì)偶問題的基本性質(zhì) 弱對(duì)偶性；強(qiáng)對(duì)偶性； 最優(yōu)性 。 無(wú)界性 。 互補(bǔ)松弛性 說(shuō)明 在下面的討論中 , 假定線性規(guī)劃原問題和對(duì)偶問題分別如下 原問題 對(duì)偶問題 ??????????????),1(0),1(..m a x11njxmibxatsxczjnjijijnjjj????????????????),1(0),1(..m i n11miynjcyatsybwimijiijmiii??掌握原問題和其對(duì)偶問題解之間的關(guān)系 第 13頁(yè) 1. 弱對(duì)偶性 是其對(duì)偶問題的可行解，則恒有 ),1( njx j ??),1( miy i ??若 是原問題的可行解， imiijnjj ybxc ?????11證明： 原問題 對(duì)偶問題 ???????????),1(0),1(.. 1njxmibxatsjnjijij?????????????),1(0),1(..1miynjcyatsimijiij??jmiinjijjnjimiij xyaxya ? ?? ?? ?? ???1 11 1)(? ?? ?? ?? ???mijinjijimijnjji xyayxa1 11 1)(jnjj xc??1imii yb??1???njjj xcz1m ax ???miii ybw1m i n第 14頁(yè) 優(yōu)性 問題的可行解，且有 ),1(? njx j ?? ),1(? miy i ??若 是原問題的可行解， imiijnjj ybxc ??11?????提示 ????? ? jnjjjnjj xcxc11 imiiimii ybyb ??????11),1(? njx j ??),1(? miy i ??,則 是原問題的最優(yōu)解， 是其對(duì)偶問題的最優(yōu)解。 ),1( njx j ??? ),1( miy i ???設(shè) 是原問題的最優(yōu)解， 是其對(duì)偶問題的最優(yōu)解。 ?是其對(duì)偶 界性 若原問題 (對(duì)偶問題 )具有無(wú)界解 , 則其對(duì)偶問題 (原問題 )無(wú)可行解 . 說(shuō)明 逆命題不成立。 即原問題 (對(duì)偶問題 )無(wú)可行解，則其對(duì)偶問題 (原問題 )或無(wú)可行解或具有無(wú)界解 , 反證法結(jié)合弱對(duì)偶性 第 15頁(yè) 4. 強(qiáng)對(duì)偶性 (對(duì)偶定理 ) 若原問題有最優(yōu)解 , 則其對(duì)偶問題 wz m i nm ax ?且有 證明： ?????????????????),1,1(0,0),1(..m a x11njmixxmibxxatsxczsijnjisijijnjjj???將原問題化成標(biāo)準(zhǔn)形式 用單純形法求得最優(yōu)解 ，則有 ,0??Y 即 ),1(0 miy i ???0??? YAC? 即 ),1(1njcyanijiij ?????故 ),1(0 miyi ???是對(duì)偶問題的可行解 , 又因 bBCxc Bnjjj11????由性質(zhì) 2即可證得。 ???miii yb1也一定有最優(yōu)解 , 第 16頁(yè) 5. 互補(bǔ)松弛性 在線性規(guī)劃問題的最優(yōu)解中 , 如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零 , 則該約束條件取嚴(yán)格等式 。反之如果約束條件取嚴(yán)格不等式 , 則該對(duì)應(yīng)的對(duì)偶變量一定為零。 即： 如果 則 如果 則 ,0? ?iy 。?1???njijij bxa ,?1???njijij bxa0? ?iy證明： 由弱對(duì)偶性知， imii yb ?1???由最優(yōu)性知 imiijnjj ybxc ??11?????從而 0?)?(1 1??? ?? ?iijminjij ybxa0?,0?1??? ??injjiji bxay?),1(0?)?(1miybxa iijnjij ????? ??因此 ??? ??? ???miji