第三讲 LP对偶ppt课件.ppt

《第三讲 LP对偶ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章线性规划问题的对偶与灵敏度分析线性规划的对偶问题概念、理论及经济意义线性规划的对偶单纯形法线性规划的灵敏度分析本章内容重点11.线性规划对偶问题对偶原理对偶问题定义——线性规划问题写出其对偶问题，要掌握在对称形式和非对称情况下由原问题写出对偶问题的方法。对偶定理——强对偶定理弱对偶定理2线性规划原问题例:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。产品甲产品乙设备能力（

2、h）设备A3265设备B2140设备C0375利润/（元/件）1500250031.对偶问题：换一个角度考虑：假定有另一个公司欲租用该公司的设备，他至少应付出多少代价，才能使该公司愿意放弃生产活动，出让设备机时？显然该公司放弃自己组织生产的条件是，对同等数量机时出让的代价不应低于自己组织生产活动的利润。设y1，y2，y3分别为每工时设备A、B、C的出租费用。1.线性规划对偶问题4Maxz=1500x1+2500x2s.t.3x1+2x2≤652x1+x2≤40原问题3x2≤75x1,x2≥0Minf

3、=65y1+40y2+75y3s.t.3y1+2y2≥1500（不少于甲产品的利润）2y1+y2+3y3≥2500对偶问题（不少于乙产品的利润）y1,y2,y3≥01.线性规划对偶问题52、对偶定义对称形式：互为对偶(LP)Maxz=cTx(DP)Minf=bTys.t.Ax≤bs.t.ATy≥cx≥0y≥01.线性规划对偶问题从单纯形法推导的公式中知道：在（LP）中加松弛变量xs,最优时是求一个基B,使B-1b≥0,且(CT,0)-CBTB-1(A,I)≤0,最优目标值z*=CBTB-1b.令yT=C

4、BTB-1——单纯形乘子，亦是对偶变量。得(DP）6一对对称形式的对偶规划之间具有下面的对应关系。(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，≤”和“min，≥”相对应。1.线性规划对偶问题(LP)Maxz=cTx(DP)Minf=bTys.t.Ax≤bs.t.ATy≥cx≥0y≥07(2)从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3

5、)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。(4)两个规划模型中的变量皆非负。1.线性规划对偶问题(LP)Maxz=cTx(DP)Minf=bTys.t.Ax≤bs.t.ATy≥cx≥0y≥0LP变量DP约束8非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。（1）将模型统一为“max，≤”或“min，≥”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；（2）若原规划的某个约束条件为

6、等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；1.线性规划对偶问题9（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。下面对关系（2）作一说明。对于关系（3）可以给出类似的解释。设原规划中第一个约束为等式：a11x1+…+a1nxn=b1那么，这个等式与下面两个不等式等价1.线性规划对偶问题101.线性规划对偶问题这样，原规划模型可以写成111.线性规划对偶问题此时已转化为对称形式，直接写出对偶规划这里，把y1看作是y1=y1’-y1’’，于是y1没

7、有非负限制，关系（2）的说明完毕。12对偶规则.原问题对偶问题目标函数maxmin目标函数约束条件≤≥=≥变量≤无约束≥变量符号≤无约束≥≤约束条件=131.线性规划对偶问题例3.1写出下面线性规划的对偶规划模型解先将约束条件变形为“≤”形式141.线性规划对偶问题再根据非对称形式的对应关系，直接写出对偶规划151.线性规划对偶问题163.对偶定理(原问题与对偶问题解的关系）考虑（LP）和（DP）定理3-1(弱对偶定理）若x,y分别为（LP)和（DP）的可行解，那么cTx≤bTy。证明:∵x,y分别为(

8、LP)(DP)的可行解，∴Ax≤b,ATy≥c→cTx≤yTAx≤yTb1.线性规划对偶问题171.线性规划对偶问题推论若（LP）可行，那么（LP）无有限最优解的充分必要条件是（DP）无可行解。18定理3-2(最优性准则定理)若x,y分别(LP),(DP)的可行解,且cTx=bTy，那么x,y分别为(LP)和(DP)的最优解。1.线性规划对偶问题证明：反证，若可行的x0，使cTx