资源描述：
《对偶理论和灵敏度分析(新)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、对偶理论和灵敏度分析对偶的定义原始对偶关系目标函数值之间的关系最优解之间的互补松弛关系对偶问题的性质对偶的经济解释对偶单纯形法灵敏度分析DUAL1第3节线性规划对偶问题的提出现有甲乙两种原材料生产A1，A2两种产品，所需的原料，甲乙两种原料的可供量，以及生产A1,A2两种产品可得的单位利润见表。问如何安排生产资源使得总利润为最大？A1A2可供量甲3224已4540利润4.552解：设生产A1为x1件，生产A2为x2件，则线性规划问题为：maxZ=4.5x1+5x2s.t.3x1+2x2≤244x1+5x2≤40x1,x2≥0假设现在不
2、考虑生产产品，而是把甲乙两种原材料卖掉，则问题变成对于甲乙两种原材料企业以多少最低价愿意出让？解：设甲资源的出让价格为y1,乙资源的出让价格为y2minw=24y1+40y2s.t.3y1+4y2≥4.52y1+5y2≥5y1,y2≥0254253第4节线性规划的对偶理论——对偶问题的一般形式一般认为变量均为非负约束的情况下，约束条件在目标函数取极大值时均取“≤”号；当目标函数求极小值时均取“≥“号。则称这些线性规划问题具有对称性。maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn≤b1a21
3、x1+a22x2+……+a2nxn≤b2……am1x1+am2x2+……+amnxn≤bmx1,x2,……,xn≥0minw=b1y1+b2y2+……+bmyms.t.a11y1+a21y2+……+am1ym≥c1a12y1+a22y2+……+am2ym≥c2……a1ny1+a2ny2+……+amnym≥cny1,y2,……,ym≥0MaxZ=CXs.t.AX≤bX≥0Minw=Y’bs.t.A’Y≥C’Y≥04原始问题maxz=CXs.t.AX≤bX≥0对偶问题minw=Y’bs.t.A’Y≥C’Y≥0≥maxbACCATb≤min
4、mnmn4.1原问题与对偶问题的关系5举例：maxZ=3x1+2x2s.t.-x1+2x2≤43x1+2x2≤14x1-x2≤3x1,x2≥0minw=4y1+14y2+y3s.t.-y1+3y2+y3≥32y1+2x2-y3≥2y1,y2,y3≥0y1y2y3第一种资源第二种资源第三种资源第一种产品第二种产品x1x26原始问题为minz=2x1+3x2-x3s.t.x1+2x2+x3≥62x1-3x2+2x3≥9x1,x2,x3≥0根据定义，对偶问题为maxy=6y1+9y2s.t.y1+2y2≤22y1-3y2≤3y1+2y2≤-
5、1y1,y2≥0原始问题是极小化问题原始问题的约束全为≥原始问题有3个变量，2个约束原始问题的变量全部为非负对偶问题是极大化问题对偶问题的约束全为≤对偶问题有2个变量，3个约束原始问题的变量全部为非负原始问题变量的个数(3)等于对偶问题约束条件的个数(3)原始问题约束条件的个数(2)等于对偶问题变量的个数(2)7非对称形式的原—对偶问题minz=2x1+3x2-5x3+x4s.t.x1+x2-3x3+x4≥52x1+2x3-x4≤4x2+x3+x4=6x1≤0,x2,x3≥0x2+x3+x4≥6x2+x3+x4≤6-x1=x1’，x1
6、’≥0;x4’-x4”=x4,x4’≥0,x4”≥0minz=-2x1’+3x2-5x3+(x4’-x4”)s.t.-x1’+x2-3x3+(x4’-x4”)≥52x1’-2x3+(x4’-x4”)≥-4x2+x3+(x4’-x4”)≥6-x2-x3-(x4’-x4”)≥-6x1’,x2,x3,x4’,x4”≥0变为一般形式y1y2’y3’y3”maxw=5y1-4y2’+6(y3’-y3”)s.t.-y1+2y2’≤-2y1+(y3’-y3”)≤3-3y1-2y2’+(y3’-y3”)≤-5y1+y2’+(y3’-y3”)≤1-y1
7、-y2’-(y3’-y3”)≤-1y1,y2’,y3’,y3”≥0写出对偶问题8maxw=5y1-4y2’+6(y3’-y3”)s.t.-y1+2y2’≤-2y1+(y3’-y3”)≤3-3y1-2y2’+(y3’-y3”)≤-5y1+y2’+(y3’-y3”)≤1-y1-y2’-(y3’-y3”)≤-1y1,y2’,y3’,y3”≥0设y2=-y2’,y3=y3’-y3”,则y2≤0,y3无约束此时对偶问题变为maxw=5y1+4y2+6y3s.t.y1+2y2≥2y1+y3≤3-3y1+2y2+y3≤-5y1-y2+y3=1y1≥
8、0,y2≤0,y3无约束minz=2x1+3x2-5x3+x4s.t.x1+x2-3x3+x4≥52x1+2x3-x4≤4x2+x3+x4=6x1≤0,x2,x3≥0比较原问题和对偶问题9原始对偶表10对偶关系1、极大与
