山东林木昆虫

《山东林木昆虫》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1一、对偶问题的提出引例：胜利家具厂生产桌子和椅子，桌子售价50元/张，椅子售价30元/张，生产桌子和椅子都需要木工和油漆工。生产一张桌子需要木工4h，油漆工2h；生产一张椅子需要木工3h，油漆工1h，该厂每个月可用木工工时120h，油漆工工时50h。问：如何组织生产才能使每月的销售收入最大?§3.1LP的对偶理论2解:设生产桌子的数量为x1，生产椅子的数量为x24x1+3x21202x1+x250x1，x20maxZ=50x1+30x23②假如有一家企业有一批等待加工的订单，有意利用该家具厂的

2、木工和油漆工资源来加工他的产品。因此，他要同家具厂谈判付给该厂每个工时的价格。研究如何即使家具厂觉得有利可图肯把工人出租给他，又使资金付的租金最少？4解：设y1,y2,分别每个木工和油漆工时的租金minW=120y1+50y24y1+2y2503y1+y230y1、y20分析问题：1、出让每种资源的收入不能低于自己生产时的可获利润；2、定价不能太高，要使对方能够接受。例甲乙备用资源A1145B2180C1390收入45产品资源设x1，x2为产品甲，乙的产量x1+x2452x1+x280x1+

3、3x290x1，x20maxZ=4x1+5x2114521x18013x290(45)x1x2设y1,y2,y3分别为A,B,C资源的单价y1+2y2+y34y1+y2+3y35y1…y30121113y1y2y345(y1y2y3)112113(4,5)minw=45y1+80y2+90y3458090(y1y2y3)9二、对偶问题与原问题的关系1.“对称型”(P)MaxZ=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXnb1a21X1+a22X2+…+a2n

4、Xnb2………am1X1+am2X2+…+amnXnbmXj0(j=1,…,n)10MinW=b1Y1+b2Y2+…+bnYma11Y1+a21Y2+…+am1Ymc1a12Y1+a22Y2+…+am2Ymc2………a1nY1+a2nY2+…+amnYmcnYi0(i=1,…,m)(D)“对称型”对应：对偶问题minw=YbYACY0A矩阵Y,C行向量b列向量maxZ=CXAXbX0A矩阵X,b列向量C行向量原问题两模型的对应关系：（1）两问题的系数矩阵互为转置（2）一个问题的变

5、量个数等于另一个问题的约束条件个数（3）一个问题的右端常数是另一个问题的目标函数的系数（4）一个问题的目标函数为极大化，约束条件为“”类型，另一个问题的目标为极小化，约束条件为“”类型13例1：写出下面问题的对偶规划maxZ=5X1+6X23X1-2X274X1+X29X1,X20minW=7y1+9y23y1+4y25-2y1+y26y1,y20(1)、maxZ=CXAX=bX0的对偶问题是minW=ybyACy为自由2、非对称型对偶例1、写出下面问题的对偶规划maxZ=5x1+

6、6x23x1–2x2=74x1+x29x1,x20解：3x1–2x273x1–2x274x1+x29maxZ=5x1+6x23x1–2x27-3x1+2x2-74x1+x29x1,x20y1'y1"y2对偶问题令y1=y1'-y1"3y1'-3y1"+4y25-2y1'+2y1"+y26y1',y1",y20minw=7y1'-7y1"+9y2minw=7y1+9y23y1+4y25-2y1+y26y1自由,y20（2）原问题第k个约束为等式，对偶问题第k个变量是自由变量

7、。原问题第k个变量是自由变量，则对偶问题第k个约束为等式约束。对偶关系对应表原问题对偶问题目标函数类型maxmin目标函数系数目标函数系数右边项系数与右边项的对应关系右边项系数目标函数系数变量数与约束数变量数n约束数n的对应关系约束数m变量数m原问题变量类型与0对偶问题约束类型的对应关系无限制＝原问题约束类型与对偶问题变量类型约束变量0的对应关系＝无限制例2、写对偶问题maxZ=x1+2x2+x3x1+x2+x32x1–x2+x3=12x1+x2+x32x10x2,x3为无非负约束min

8、w=2y1+y2-2y3y1+y2-2y31y1-y2+y3=2y1+y2-y3=1y1，y30,y2自由产品A，B产量x1，x2，Z为利润例、3x1+x2+x3=483x1+4x2+x4=120x1…x40maxZ=5x1+6x23x1+x2483x1+4x2120x1,x20机器台时劳动工时X=(8,24)TZ=1845600CBXBb*x1x2x3x40x34831100x41203[4]0156000x318[9/4]01-1/46x