資源描述：
《線性規(guī)劃問題的對偶問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、2、線性規(guī)劃問題的對偶問題例2．1勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價50元/個，椅子銷售價格30元/個，生產(chǎn)桌子和椅子要求需要木工和油漆工兩種工種。生產(chǎn)一個桌子需要木工4小時，油漆工2小時。生產(chǎn)一個椅子需要木工3小時，油漆工1小時。該廠每個月可用木工工時為120小時，油漆工工時為50小時。問該廠如何組織生產(chǎn)才能使每月的銷售收入最大？2.1對偶問題數(shù)學(xué)模型maxg=50x1+30x2s.t.4x1+3x2?120(2.1)2x1+x2?50x1,x2?0假如有一個企業(yè)家有一批等待加工的訂單，有意利用該家具廠的木工
2、和油漆工資源來加工他的產(chǎn)品。因此，他要同家具廠談判付給該廠每個工時的價格?？梢詷?gòu)造一個數(shù)學(xué)模型來研究如何既使家具廠覺得有利可圖肯把資源出租給他，又使自己付的租金最少？假設(shè)y1,y2分別表示每個木工和油漆工工時的租金，則所付租金最小的目標(biāo)函數(shù)可表示為：mins=120y1+50y2目標(biāo)函數(shù)中的系數(shù)120，50分別表示可供出租的木工和油漆工工時數(shù)。該企業(yè)家所付的租金不能太低，否則家具廠的管理者覺得無利可圖而不肯出租給他。因此他付的租金應(yīng)不低于家具廠利用這些資源所能得到的利益：4y1+2y2?503y1+y2?30y1,y2
3、?0得到另外一個數(shù)學(xué)模型：mins=120y1+50y2s.t.4y1+2y2?50(2.2)3y1+y2?30y1,y2?0模型(2.1)和模型(2.2)既有區(qū)別又有聯(lián)系。聯(lián)系在于它們都是關(guān)于家具廠的模型并且使用相同的數(shù)據(jù)，區(qū)別在于模型反映的實質(zhì)內(nèi)容是不同的。模型(2.1)是站在家具廠經(jīng)營者立場追求銷售收入最大，模型(2.2)是則站在家具廠對手的立場追求所付的租金最少。如果模型(2.1)稱為原問題，則模型(2.2)稱為對偶問題。任何線性規(guī)劃問題都有對偶問題，而且都有相應(yīng)的意義。例2.2：常山機器廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，
4、按工藝資料獲得如下資料：ⅠⅡ設(shè)備能力設(shè)備A2h2h12h設(shè)備B4h0h16h設(shè)備C0h5h15h單位利潤（元）23問該企業(yè)因安排生產(chǎn)兩種產(chǎn)品各多少件，使總的利潤收入為最大？數(shù)學(xué)模型maxZ=2x1+3x2s.t.2x1+2x2?124x1?165x2?15x1,x2?0現(xiàn)某機械廠為擴大生產(chǎn)租借常山機器廠擁有的設(shè)備資源，問常山廠分別以每小時什么樣的價格才愿意出租自己的設(shè)備？設(shè)常山廠將設(shè)備A、B、C每h的出租價格為y1,y2,y3;它的對偶問題為minw=12y1+16y2+15y32y1+4y2≥22y1+5y3≥3y1
5、,y2,y3≥0把例2.2用矩陣表示：對偶問題原問題:Maxz=(2,3)線性規(guī)劃的對偶關(guān)系：（I）Maxz=Cxs.t.Ax?b（2.3）x?0(II)Minw=b’ys.t.A’y?C’（2.4）y?0（2.3)(2.4)稱作互為對偶問題。其中一個稱為原問題，另一個稱為它的對偶問題。例2-3：寫出下列線性規(guī)劃問題的對偶問題minw=12x1+8x2+16x3+12x4s.t.2x1+x2+4x3?22x1+2x2+4x4?3x1，x2，x3，x4?0解：該問題的對偶問題：maxz=2y1+3y2s.t.2y1+2y
6、2?12y1+2y2?84y1?164y2?12y1，y2?0例2-4：寫出下列線性規(guī)劃問題的對偶問題maxS=10x1+x2+2x3s.t.X1+x2+2x3?10y14x1+2x2-x3?20y2x1，x2，x3?0解：該問題的對偶問題：ming=10y1+20y2s.t.y1+4y2?10y1+2y2?12y1-y2?2y1，y2?0例2-5：寫出下列線性規(guī)劃問題的對偶問題minS=x1+2x2+3x3s.t.2x1+3x2+5x3?23x1+x2+7x3?3x1，x2，x3?0解：用（-1）乘以第二個約束方程兩
7、邊minS=x1+2x2+3x3s.t.2x1+3x2+5x3?2y1-3x1-x2-7x3?-3y2x1，x2，x3?0該問題的對偶問題：maxz=2y1-3y2s.t.2y1-3y2?13y1-y2?25y1-7y2?3y1，y2?0例2-6：寫出下列線性規(guī)劃問題的對偶問題minS=2x1+3x2-5x3s.t.x1+x2-x3?52x1+x3=4x1，x2，x3?0解：將原問題的約束方程寫成不等式約束形式：minS=2x1+3x2-5x3x1+x2-x3?5y12x1+x3?4y2’-2x1-x3?-4y2”x1
8、，x2，x3?0引入變量y1,y2’，y2”寫出對偶問題maxg=5y1+4y2’-4y2”s.t.y1+2y2’-2y2”?2y1?3-y1+y2’-y2”?-5y1，y2’，y2”?0令y2=y2’-y2”得到maxg=5y1+4y2s.t.y1+2y2?2y1?3-y1+y2?-5y1?0，y2無非負(fù)約束此類問題稱為非對稱型
