第3章LP对偶与灵敏度分析.ppt

《第3章LP对偶与灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）150025003Maxz=1500x1+2500x2s.t.3x1+2x2≤652x1+x2≤403x2≤75x1,x2≥0原问题41.对偶问题若例2.1问题的设备都用于外协加工，工厂收取加工费（租金：扣除成本后的利润）。试问：设备A、B、C每工时各如何收费才最有竞争力？设y1，y2，y3分别为每工时设备A、B、C的收取费用。一.线性规划对偶问题5Minf=65y1+40y2+75y3（在满足约束的条件下尽可能低才能得到其它单位的委托加工或租用）s.t.3y1+2

3、y2≥1500（不少于自己生产甲产品的利润）2y1+y2+3y3≥2500（不少于自己生产乙产品的利润）y1,y2,y3≥0对偶问题6原问题和对偶问题关系对比请看教材P11372、对偶定义对称形式：互为对偶(LP)Maxz=cx(DP)Minf=bTys.t.Ax≤bs.t.ATy≥cTx≥0y≥0“Max--≤”“Min--≥”8原问题和对偶问题的关系1、对称形式的对偶关系（1）定义：若原问题是9则定义其对偶问题为这两个式子之间的变换关系称为“对称形式的对偶关系”。10一对对称形式的对偶规划之间具有下面的对应关系。(1)若一个模型为目标求

4、“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，≤”和“min，≥”相对应。11(2)从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。(4)两个规划模型中的变量皆非负。12原问题对偶问题目标函数maxmin约束条件≤≥变量数量约束条件个数约束条件个数变量数量13非对称形式的对偶规划14非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对

5、称形式的对偶规划。对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。（1）将模型统一为“max，≤”或“min，≥”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；15（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。（4）原规划的每个变量xj的约束列向量对应对偶规划的一个约束，若xj>0,则约束为不等式，若xj为自由变量，则约束为等式。16下面对关系（2）作一说明。对于关（3）可以给出

6、类似的解释。设原规划中第一个约束为等式：a11x1+…+a1nxn=b1那么，这个等式与下面两个不等式等价17这样，原规划模型可以写成18此时已转化为对称形式，直接写出对偶规划这里，把y1看作是y1=y1’-y1’’，于是y1没有非负限制，关系（2）的说明完毕。19例3.1写出下面线性规划的对偶规划模型解：先将约束条件变形为“≤”形式20再根据非对称形式的对应关系，直接写出对偶规划2122例3-2写出线性规划问题的对偶问题解：首先将原式变形23注意：以后不强调等式右段项b≥0，原因是在对偶单纯型表中只保证而不保证，故b可以是负数。（对于求极

7、小：）24例3-3原问题25例3-4原问题26对偶问题27例3-5、线性规划问题如下：2829综上所述，其变换形式归纳如下：原问题（或对偶问题）对偶问题（或原问题）目标函数max目标函数min约束条件m个m个变量≤≥0≥≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项30根据上表，对例3-4而言在原规划在目标函数求极大情况下：1）如果原规划的某变量xi为小于等于零，则令xi＝-xi’，然后替换模型中的所有xi；2）如果原规划的第i个约束为大于等于型，则令和其对应的对偶变量为

8、yi’,然后在最后的对偶模型中令-yi＝yi’。31根据上表，对例3-5而言在原规划在目标函数求极小情况下：1）如果原规划的某变量xi为小于等于零，则令xi＝-xi’，然后替换模