线性规划的对偶理论

《线性规划的对偶理论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划的对偶理论1、引例一个工厂生产两种产品A、B，每个产品的利润分别为2元、4元。而生产一个A产品需4单位甲原料，2单位的乙原料。B产品需6单位甲原料，6单位乙原料，1单位丙原料。现有原料：甲：120单位乙：72单位丙：10单位如何计划生产，可使工厂总利润达到最大？一、对偶问题的提出AB甲46120乙2672丙110解：设x1,x2为A、B两产品的产品数量maxz=2x1+4x2=cxs.t.4x1+6x2≤1202x1+6x2≤72Ax≤bx2≤10x1,x2≥0.求解得x1=24,x2=4zm

2、ax=64从另一角度，工厂决策者考虑这样一个问题：卖出这些原料的单价应是多少，工厂才愿意停止生产A、B产品，而将原料全部出卖呢？或是当原料有剩余时，是将多余原料卖出，还是再购其他原料继续生产？假定甲乙丙三种原料的单价为y1,y2,y3.显然yi≥0i=1~3因为生产单位A产品要用甲:4乙:2丙:0而获利2元所以有：4y1+2y2+0y3≥2同理有：6y1+6y2+y3≥4如果工厂全部卖出原料的总得益为：120y1+72y2+10y3当然价格越高越好，但受到制约：最小为多少？minw=120y1+72y2+1

3、0y3bTys.t.4y1+2y2+0y3≥26y1+6y2+y3≥4ATy≥cyi≥0i=1~3这个问题我们称为原LP的DLP（对偶问题）其解称为原问题的对偶解y1=1/3y2=1/3y3=0wmin=64这不是实际价格，称为影子价格经济意义：当甲原料增加1单位，可得益1/3元。因为丙原料还有余，因此增加获减少1单位对利润无影响（y3=0）原规划与对偶规划可看成是对同一个问题从不同得角度所进行得分析与研究二、对偶问题的形式1、对称型对偶问题s.t.定义2.1设原LP问题为：其对偶问题为：其中yi(i=1,

4、2,…m)称为对偶变量，并称以上两式为一对对称型对偶问题。≥≥≥≥0()………………………………如果用矩阵形式来表示模型，则可更清楚地看出两者之间的对称性.（P）s.t.（D）s.t.是一行向量.≥cy≥0bTyATy≥c例2.1写出以下（P）问题的（D）问题s.t.解：首先将问题化为如下形式：s.t.再根据定义2.1，写出其（D）问题：s.t.2、非对称型对偶问题如果原问题是LP问题的标准形式，记（P）问题为：s.t.为了利用对称型问题的结论，先将问题等价地化为：s.t.再引入对偶向量（u,v），其中u为

5、对应于第一组不等式约束的对偶变量，v为对应于第二组不等式约束的对偶变量，按对称型的结论，可写出其（D）问题为：≤b≤－bx≥0s.t.s.t.即令y=u-v为m维行向量，则以上模型又可写成：s.t.例2.2写出（P）问题的（D）问题.s.t.解：s.t.原问题对偶问题目标函数max目标函数min约束条件m个≤≥＝m个≥0≤0无符号限制变量变量n个≥0≤0无符号限制n个≥≤＝约束条件目标函数的系数约束条件右端常数系数矩阵A约束条件右端常数目标函数的系数系数矩阵AT3.混合型对偶问题例2.3写出（P）问题的（D

6、）问题.s.t.解：根据对偶规划表，可直接写出该问题的（D）问题.s.t.考虑如下对称形式（P）问题：（D）问题：s.t.Ax≤bs.t.yA≥cx≥0y≥0定理2.1（对称性定理）对偶问题的对偶是原问题.一、对偶规划的若干问题定理2.2（弱对偶定理）设x0和y0分别是（P）问题和（D）问题的可行解，则必有cx0≤y0b§2对偶问题的基本性质即最大值比最小值小推论2.1如果x*和y*分别是（P）问题和（D）问题的可行解，且cx*=y*b，则x*、y*分别是（P）问题和（D）问题的最优解.推论2.2在一对对偶

7、问题中，如果其中一个问题可行，但目标函数无界，则为另一个问题不可行.推论2.3如果一对对偶问题都有可行解，则它们都有最优解.定理2.3（对偶定理）如果（P）问题（（D）问题）有最优解，那么（D）问题（（P）问题）也有最优解，且目标函数值相等.推论2.4（单纯形乘子定理）如果（P）问题有最优解，最优基为B，则y*＝CBB-1就是（D）问题的一个最优解.如何求对偶问题的最优解.cobcoboBNIbI检验数oo检验数o定理2.4（互补松弛定理）设x*和y*分别是（P）问题和（D）问题的可行解，则它们分别是（P）

8、、（D）问题的最优解的充要条件是：y*(b-Ax*)=0；(y*A-C)x*=0同时成立必要性设、分别是（P）问题和（D）问题的最优解.则≤b，≥0；≥c，≥0；，所以由≤≤推出==，于是，或:二、对偶规划的求解1、利用原问题的最优单纯形表求对偶最优解的方法如何求对偶问题的解？s.t.例2.4求如下LP问题的对偶问题的最优解.解:对偶问题为s.t.原问题的最优解和目标值：对原问题引入松弛变量x4,x5,将原问题化