线性规划对偶理论与灵敏度分析.pptx

假设有某个公司想把美佳公司的资源收买过来，它至少应付出多大代价。设分别用y1，y2，y3代表单位时间(h)设备A、设备B、和调试式序的出让代价（单价）。第2页/共16页第1页/共16页原问题对偶问题第3页/共16页第2页/共16页 二、对称形式下对偶问题的一般形式 定义：满足下列条件的线性规划问题称为具有对称形式,其变量均具有非负约束，其约束条件当目标函数求极大时均取“”号，当目标函数求极小时均取“”号。对称形式下线性规划问题的一般形式：第4页/共16页第3页/共16页用yj（j1，m）代表第j种资源的估价则其对偶问题的一般形式为:第5页/共16页第4页/共16页用矩阵形式表示，对称形式的线性规划问题的原问题为:其对偶问题为:第6页/共16页第5页/共16页第7页/共16页第6页/共16页试证明:对偶问题的对偶即为原问题第8页/共16页第7页/共16页三、非对称形式的原-对偶问题关系例2 写出下述线性规划问题的对偶问题max z=c1x1+c2x2+c3x3a11x1+a12x2+a13x3b1 （2.7a）st.a21x1+a22x2+a23x3b2 （2.7b）a31x1+a32x2+a33x3b3 （2.7c）x10,x20,x3无约束 （2.7d）第9页/共16页第8页/共16页（1）将约束（2.7b）先转换成 a21x1+a22x2+a23x3b2a21x1+a22x2+a23x3b2，再变换为a21x1+a22x2+a23x3b2a21x1-a22x2-a23x3-b2；（2）将（2.7c）约束两端乘“-1”，得-a31x1-a32x2-a33x3 -b3；（3）在约束（2.7c）中令x2=-x2，由此x2 0；令x3=x3-x3，其中x3 0，x3 0。经上述变换后可重新表达为第10页/共16页第9页/共16页对偶问题第11页/共16页第10页/共16页原问题对偶问题第12页/共16页第11页/共16页项目原问题（对偶问题）对偶问题（原问题）A约束系数矩阵约束系数矩阵的转置b约束条件右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件右端项向量目标函数第13页/共16页第12页/共16页xj(j=1,2,n)xj0 xj0 xj无约束有n个(j=1,n)变量约束条件第14页/共16页第13页/共16页有m个(j=1,m)yi(i=1,2,m)yi0yi0yi无约束变量约束条件第15页/共16页第14页/共16页例：写出下列LP问题的对偶问题。（1）max z=2x1+3x2+x3 x1+2x2+x36 3x1+5x2-x3 12 x1,x2,x30（2）min z=x1+2x2+5x3 x1-2x2+5x3 8 2x1+3x2+x3=3 4x1-x2+2x3 6 x1,x2,x3 0P77:2.1(1),(4)第16页/共16页第15页/共16页感谢您的观看！第16页/共16页