第3章线性规划问题的对偶与灵敏度分析ppt课件.ppt

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

1、第三章线性规划问题的对偶与灵敏度分析1本章内容重点线性规划的对偶问题概念、理论及经济意义线性规划的对偶单纯形法线性规划的灵敏度分析2线性规划原问题例2.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）150025003对偶问题若上问题的设备都用于外协加工，工厂收取加工费。试问：设备A、B、C每工时各如何收费才最有竞争力

2、？设y1,y2,y3分别为每工时设备A、B、C的收取费用。4原问题Maxz=1500x1+2500x2s.t.3x1+2x2≤652x1+x2≤403x2≤75x1,x2≥0对偶问题Minf=65y1+40y2+75y3s.t.3y1+2y2≥1500（不少于甲产品的利润）2y1+y2+3y3≥2500（不少于乙产品的利润）y1,y2,y3≥052、对偶定义对称形式：互为对偶(LP)Maxz=cTx(DP)Minf=bTys.t.Ax≤bs.t.ATy≥cx≥0y≥0“Max--≤”“Min--≥”6一对对称形式的对偶规划之

3、间具有下面的对应关系。(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，≤”和“min，≥”相对应。7(2)从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。(4)两个规划模型中的变量皆非负。8非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，可以按照下面的对应

4、关系直接给出其对偶规划。（1）将模型统一为“max，≤”或“min，≥”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；9（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式下面对关系（2）作一说明。对于关系（3）可以给出类似的解释。设原规划中第一个约束为等式：a11x1+…+a1nxn=b1那么，这个等式与下面两个不等式等价10这样，原规划模型可以写成11此时已转化为对称形式，直接写出对偶

5、规划这里，把y1看作是y1=y1’-y1’’，于是y1没有非负限制，关系（2）的说明完毕。12例写出下面线性规划的对偶规划模型解先将约束条件变形为“≤”形式13再根据非对称形式的对应关系，直接写出对偶规划1415对偶性定理设有一对互为对偶的线性规划A为m×n阶矩阵，A的秩为m16引入松弛变量xs，得到原规划(P)的标准型为(P1)其中01和I分别为m维的零向量和m维的单位矩阵17则上面的标准型可以表示为(P2)其中02为m+n维零向量18设B为一可行基得到模型P2的另一表达形式19记为非基变量检验数的向量表达式由于基变量的检验

6、数为零，所以全部检验数的向量形式可记为20可行基B对应的基本可行解为x0的目标函数值为21定理3-1(弱对偶定理)设分别为原规划(P)和对偶规划(D)的可行解，则证：因为是原规划可行解，且所以有又因为是对偶规划的可行解，且所以有所以这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值22推论1设分别为原规划(P)和对偶规划(D)的可解，当时，分别是两个问题的最优解证明，由定理3.1可知，对于线性规划(D)的任一可行解y。都有

7、，因此是线性规划(D)的最优解，类似的，可以证明是线性规划(P)的最优解2324例3.4试用对偶理论判断下面线性规划是否有最优解25解此线性规划存在可行解,其对偶规划为此线性规划没有可行解，因此原规划没有最优解2627解此线性规划存在可行解,其对偶规划为此线性规划存在可行解因此原规划存在最优解28定理3.2若原规划(P)有最优解，则对偶规划(D)也有最优解，反之亦然，并且两者的目标函数值相等证明:考虑原规划(P)的标准型(P2)设B为模型P2的最优解，现在证明对偶规划D也有最优解。由单纯形法可知，此时29令，则有因此，为对偶规

8、划(D)的可行解。另一方面其中为原规划的最优解。由推论1可知为对偶规划(D)的最优解30类似的，若对偶规划(D)有最优解，则原规划(P)也有最优解从定理3.2可以看到，对偶规划(D)的最优解可以在原规划(P)的检验数中得到由于的后m列为单位矩阵，的后m个分量为031对偶规划(