线性规划的对偶理论(部分).pptVIP

一、对偶问题的提出 1、? 对偶思想举例：某工厂拥有一定生产原材料时，该工厂考虑是自己进行产品生产所赚的利润大还是将其原材料直接出售给其它工厂时所以赚取的利润大的问题。 第二章? 线性规划的对偶理论 2、? 换个角度审视生产计划问题 例：（第一章例2）要求制定一个生产计划方案，在劳动力和原材料可能供应的范围内，使得产品的总利润最大 。 它的对偶问题就是一个价格系统，使在平衡了劳动力和原材料的直接成本后，所确定的价格系统最具有竞争力： （用于生产第i种产品的资源转让收益不小于生产该种产品时获得的利润） 对偶变量的经济意义可以解释为对工时及原材料的单位定价 ； 若工厂自己不生产产品A、B和C，将现有的工时及原材料转而接受外来加工时，那么上述的价格系统能保证不亏本又最富有竞争力（包工及原材料的总价格最低） 当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的： Zmax=Wmin 二、原问题和对偶问题的关系 1、对称形式的对偶关系 （1）定义：若原问题是 则定义其对偶问题为 这两个式子之间的变换关系称为“对称形式的对偶关系”。 原问题与对偶问题的对比： 若原问题 对偶问题 （2）对称形式的对偶关系的矩阵描述 （D） （L） （3）怎样从原始问题写出其对偶问题？ ? 按照定义； ?记忆法则： “上、下”交换，“左、右”换位， 不等式变号，“极大”变“极小” 例 写出下面线性规划的对偶问题： 2、非对称形式的对偶关系： （1） 原问题 对偶问题 （特点：对偶变量符号 不限，系数阵转置） (特点：等式约束) （2）怎样写出非对称形式的对偶问题？ ?把一个等式约束写成两个不等式约束，再根据对称形式的对偶关系定义写出； ?按照原始-对偶表直接写出 ； （3）原始-对偶表 原问题（或对偶问题） 对偶问题（或原问题） 目标函数 MaxZ 目标函数 MinW 变量数：n个 变量 ≥0 变量 ≤0 变量 无约束 约束条件数：n个 约束条件 ≥ 约束条件 ≤ 约束条件 = 约束条件：m个 约束条件 ≤ 约束条件 ≥ 约束条件 = 变量数：m个 变量 ≥0 变量 ≤0 无约束 课堂练习：写出下面线性规划的对偶规划： 下面的答案哪一个是正确的？为什么？ （原问题是极小化问题，因此应从原始对偶表的右边往左边查！） √ × 三、对偶定理 对偶定理是揭示 原始问题的解与对偶问题的解之间重要关系的 一系列性质。 对称性—— 对偶问题的对偶是原问题。 性质1 弱对偶性——如果 是原问题的可行解， 其对偶问题的可行解，则恒有： （L） 和 （D） 均有可行解，分别为 和 ，则C ≤ b。 证明思路： 由（L） 左乘 ，得 由（D） 右乘 ，得 ? 关于“界”的结果； ?极小化问题有下界—— 推论1 极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。 ?极大化问题有上界—— 推论2 极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。 性质2 最优性 若 、 分别为对称形式对偶线性规划的可行解，且两者目标函数的相应值相等，即 则 ， 分别为原始问题和对偶问题的最优解。 性质3 无界性 如果原问题（对偶问题）具有无界解，则对偶问题（原问题）无可行解。 注意：这个性质逆不成立。因为当原问题（对偶问题）无可行解时，其对偶问题（原问题）或无可行解或具有无界解。 性质4 强对偶性(或称对偶定理) 如果原问题有最优解，则其对偶问题也一定具有最优解，且有 性质5 互补松弛性 在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。 即： 性质6 线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松驰变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基解变量，则在另一问