運籌學(xué)04-對偶問題.ppt

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