线性规划的对偶问题.pptxVIP

1第三章线性规划的对偶问题对偶线性规划对偶定理对偶单纯形法

任何一个线性规划问题都有一个与之相对应01的线性规划问题，如果前者称为原始问题，后者02就称为“对偶”问题。03对偶问题是对原问题从另一角度进行的描述04其最优解与原问题的最优解有着密切的联系，在05求得一个线性规划最优解的同时也就得到对偶线06性规划的最优解，反之亦然。07对偶理论就是研究线性规划及其对偶问题的08理论，是线性规划理论的重要内容之一。09对偶问题概念：第一节对偶问题

对偶线性规划3对偶问题的提出例1、某工厂生产甲,乙两种产品，这两种产品需要在A,B,C三种不同设备上加工。每种甲、乙产品在不同设备上加工所需的台时，它们销售后所能获得的利润，以及这三种设备在计划期内能提供的有限台时数均列于表。试问如何安排生产计划，即甲,乙两种产品各生产多少吨，可使该厂所获得利润达到最大。设备每吨产品的加工台时可供台时数甲乙ABC359448364076利润（元/吨）3230

4假设计划期内甲乙两种产品各生产吨，设备每吨产品的加工台时可供台时数甲乙ABC359448364076利润（元/吨）3230用图解法或单纯形法可求得最优解(元)即在计划期内甲产品生产吨，乙产品生产8吨，可以使总利润达到最大，为元。

现在从另一个角度来考虑该工厂的生产问题:假设该厂的决策者打算不再自己生产甲,乙产品，而是把各种设备的有限台时数租让给其他工厂使用，这时工厂的决策者应该如何确定各种设备的租价。设分别为设备A，B，C每台时的租价，约束条件：把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润目标函数：所获租金总额尽量少．（价格应该尽量低，这样，才能有竞争力）价格应该是非负的

由此可得两个对称的线性规划：6设备每吨产品的加工台时可供台时数甲乙ABC359448364076利润（元/吨）3230

矩阵形式：7

对偶线性规划8可以得到另一个线性规划：称之为原线性规划问题的对偶问题，01考虑如下具有不等式约束的线性规划问题02

9

10

线性规划问题标准型的对偶问题由于任何一个等式约束都可以用两个不等式约束等价地表示，所以标准形线性规划问题可等价表示为：考虑一个标准形式的线性规划问题它的对偶规划为：若令线性规划标准型的对偶规划为：

213目标函数在一个问题中是求最大值在另一问题中则为求最小值一个问题中目标函数的系数是另一个问题中约束条件的右端项一个问题中的约束条件个数等于另一个问题中的变量数4原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵对偶问题的特点

其他形式问题的对偶minf=CTXs.t. AX≤b X≥0maxz=bTYs.t.ATY≤CY≤0minf=CTXs.t. AX≥b X≥0maxz=bTYs.t.ATY≤CY≥0minf=CTXs.t. AX=b X≥0maxz=bTYs.t.ATY≤CY：unr

15对偶线性规划的求法从任何一个线性规划出发，都可以求出相应的对偶规划，在实际求解过程中，通常不通过求标准型，而是利用如下反映原始问题与对偶问题对应关系的原始─对偶表：目标函数变量系数约束条件右端项约束条件右端项目标函数变量系数约束条件个数：n个变量个数：n个变量个数：m个约束条件个数：m个目标函数minW目标函数maxZ对偶问题（或原问题）原问题（或对偶问题）

例2写出下列线性规划的对偶问题16解：对偶规划：

01例3写出下列线性规划的对偶问题02解：上述问题的对偶规划：

第二节对偶定理18本节讨论几条重要的对偶定理，这些定理揭示了原始问题的解和对偶问题的解之间的基本关系。01定理1：（对称性）对偶问题的对偶是原问题。02证明：设原问题为对偶问题为03改写对偶问题为对偶问题的对偶为04

定理2：弱对偶定理若是原（极小化）问题的可行解，是对偶（极大化）问题的可行解，那么证明：因为是对偶问题的可行解，所以满足约束条件又因为是原问题的可行解，可得，,所以。注：原（极小化）问题的最优目标函数值以对偶问题任一可行解的目标函数值为下界。对偶（极大化）问题的最优目标函数值以原问题任一可行解的目标函数值为上界。推论1：如果原问题没有下界（即minZ→－∞），则对偶问题不可行。如果对偶问题没有上界（即maxW→＋∞），则原问题不可行