第四章線性規(guī)劃的對(duì)偶理論4.1對(duì)偶問題4.2對(duì)偶問題的基本性質(zhì)4.3對(duì)偶問題的解4.4影子價(jià)格4.5對(duì)偶單純形法4.1對(duì)偶問題(1)對(duì)偶問題的提出例1、生產(chǎn)組織與計(jì)劃問題A,B各生產(chǎn)多少,可獲最大利潤?可用資源煤勞動(dòng)力倉庫AB123202單位利潤4050306024MaxZ=40x1+50x2x1+2x2303x1+2x2602x224x1，x20s.t目標(biāo)函數(shù)約束條件如果因?yàn)槟撤N原因，不愿意自己生產(chǎn)，而希望通過將現(xiàn)有資源承接對(duì)外加工（或出售）來獲得收益，那么應(yīng)如何確定各資源的使用價(jià)格？MaxZ=40x1+50x2x1+2x2303x1+2x2602x224x1，x20s.t目標(biāo)函數(shù)約束條件兩個(gè)原則1.所得不得低于生產(chǎn)的獲利2.要使對(duì)方能夠接受設(shè)三種資源的使用單價(jià)分別為y1,y2,y3y1y2y3生產(chǎn)單位產(chǎn)品A的資源消耗所得不少于單位產(chǎn)品A的獲利生產(chǎn)單位產(chǎn)品B的資源消耗所得不少于單位產(chǎn)品B的獲利y1+3y2402y1+2y2+2y350通過使用所有資源對(duì)外加工所獲得的收益W=30y1+60y2+24y3根據(jù)原則2，對(duì)方能夠接受的價(jià)格顯然是越低越好，因此此問題可歸結(jié)為以下數(shù)學(xué)模型：MinW=30y1+60y2+24y3y1+3y2402y1+2y2+2y350y1,y2,y30s.t目標(biāo)函數(shù)約束條件原線性規(guī)劃問題稱為原問題，此問題為對(duì)偶問題，y1,y2,y3稱為影子價(jià)格(2)對(duì)偶問題的形式njxbxaxaxabxaxaxabxaxaxatsxcxcxcZMaxjmnmnmmnnnnnn,2,10.221122222121112121112211定義設(shè)原線性規(guī)劃問題為則稱下列線性規(guī)劃問題miycyayayacyayayacyayayatsybybybWMininmmnnnmmmmmm,2,10.221122222112112211112211為其對(duì)偶問題，其中yi(i=1,2,m)稱為對(duì)偶變量。上述對(duì)偶問題稱為對(duì)稱型對(duì)偶問題。原問題簡記為(P)，對(duì)偶問題簡記為(D)原始問題MaxZ=CXs.t.AXbX0bACMaxnm對(duì)偶問題MinW=Ybs.t.YATCY0MinCTATbTnm0,94723.6521212121xxxxxxtsxxZMax例2：求線性規(guī)劃問題的對(duì)偶規(guī)劃解：由原問題的結(jié)構(gòu)可知為對(duì)稱型對(duì)偶問題0,62543.9721212121yyyyyytsyyWMin0,94723.6521212121xxxxxxtsxxZMax例3：求線性規(guī)劃問題的對(duì)偶規(guī)劃解：由原問題的結(jié)構(gòu)可知不是對(duì)稱型對(duì)偶問題，可先化為對(duì)稱型，再求其對(duì)偶規(guī)劃。0,62543