1、運籌學線性規劃與目標規劃第二章 對偶問題與靈敏度分析Duality Theory and Sensitivity Analysis上節內容回顧上節內容回顧m ax 0zA XbXC Xm a x 0 0 ,0ssszC XXA XIXbXXXSXAI1Ib1BCCIAC10BBCCII0SCbBXNXSX1B BI1BBCC BB1B N1NBCC B N11B IB10BC B I1Bb1BCBb1NNBCC B N10jB P111:min0ilkikiB bxB PB P1BC B b1B為單純形法中關鍵的因素！111012BBB如何求每步迭代中基變量對應的基矩陣的逆矩陣、？100,;B

2、IBI易得12EE 如何求、？11110;BE B11221BE B本節內容摘要本節內容摘要產品產品I產品產品II供應量供應量設設 備備原材料原材料A原材料原材料利 潤潤23現工廠決策者決定不生產產品，而將其所有資源出租或現工廠決策者決定不生產產品，而將其所有資源出租或出售，應如何給每種資源定價？出售，應如何給每種資源定價？設y1，y2和y3分別表示出租單位設備臺時的租金和出讓單位原材料A，B的價格。則有：1242yy13243yy12381612yyy123,0y yy min1242yy13243yy12381612yyy123,0y yy 1228xx14 16

3、x2412x 1223zxxmax12,0 x x . .stmax0zCXAXbXmin0YbYACYmin產品產品I產品產品II供應量供應量設設 備備原材料原材料A原材料原材料利 潤潤2310BCC B A(P) max . .0zCXAXbstX(D) min . .0YbYACs tY1BYC B0Y YACYbz1BzC B b10BC B1228xx14 16x2412x 1223zxxmax12,0 x x . .st124004A2,3C 81612b1238min,1612y yy12312,402304yyy0Y 1242yy13243yy123m

4、in81612yyy123,0y yy min0YbYACYmax0zCXAXbX每一個線性規劃（每一個線性規劃（ LP ）必然有與之相伴而生的另一）必然有與之相伴而生的另一個線性規劃問題，即任何一個求個線性規劃問題，即任何一個求 maxZ 的的LP都有一都有一個求個求 minZ 的的LP。其中的一個問題叫。其中的一個問題叫“原問題原問題”，記為記為“P”，另一個稱為，另一個稱為“對偶問題對偶問題”，記為，記為“D”。本節內容摘要本節內容摘要1242yy13243yy123min81612yyy123,0y yy 1228xx14 16x2412x 1223zxxmax12,0 x x iyj

5、x12nxxx12myyy111212122212nnmmmnaaaaaaaaa12nccc123bbbmaxminzminmax z 注意：以后不強調等式右端項注意：以后不強調等式右端項 b b00，b b可以是負數。可以是負數。故對于約束為故對于約束為的情形可以先乘以的情形可以先乘以1 1變為變為再按照對再按照對稱形式的變換關系進行變換稱形式的變換關系進行變換. .對偶模型的一般式對偶模型的一般式max. .0zCXAXbstX(P)上對偶模型稱為對稱式對偶模型。二者間有對稱的對應關系：上對偶模型稱為對稱式對偶模型。二者間有對稱的對應關系： 原問題（原問題（P P） 對偶問題對偶問題 （D

6、 D） 目標目標max型型 目標目標min型型 有有n個變量（非負）個變量（非負） 有有n個約束（大于等于）個約束（大于等于） 有有m個約束個約束 （小于等于）（小于等于） 有有m個變量（非負）個變量（非負） 價格系數價格系數 資源向量資源向量 資源向量資源向量 價格系數價格系數 技術系數矩陣技術系數矩陣 技術系數矩陣的轉置技術系數矩陣的轉置 min. .0YbYACs tY(D)非對稱形式（即原問題約束條件中含有等式非對稱形式（即原問題約束條件中含有等式約束、原問題的變量無非負約束）怎樣求其約束、原問題的變量無非負約束）怎樣求其對偶問題？對偶問題？2、非對稱型對偶問題、非對稱型對偶問題123

7、4123412412341234P max235 4 325 32 74 2 34 60,0,Zxxxxxxxxxxxxxxxxxxx無約束12312312313123123D min 5464322 233 3 +452710,0,yyyyyyyyyyyyyyyyy 無約束大約變，小相反，實例參考定價與生產！大約變，小相反，實例參考定價與生產！(P) max . .0zCXAXbstX(D) min . .0YbYACs tY練習練習1：求下面線性規劃問題的對偶問題：求下面線性規劃問題的對偶問題1231213123123123P max 4562 =1 5 327420,0,yyyyyyyy

8、yyyyyyyy 無約束123412341342341234D min572 3 42 245 6 00Zxxxxxxxxxxxxxxx, xx,x無約束、練習練習2：求下面線性規劃問題的對偶問題：求下面線性規劃問題的對偶問題123412341342341234P min572 3 42 245 6 00Zxxxxxxxxxxxxxxx, xx,x無約束、1231213123123123D max 4562 =1 5 327420,0,yyyyyyyyyyyyyyyy 無約束123412341342341234D min572 3 42 245 6 00Zxxxxxxxxxxxxxxx, xx,x無約束、1231213123123123P max 4562 =1 5 327420,0,yyyyyyyyyyyyyyyy 無