NEW线性规划对偶理论

1、返回继续单纯形法的进一步讨论-单纯形法的矩阵描述 及对偶理论为什麽要研究单纯形法的矩阵描述？ 进一步讨论修正单纯形法 便于理论推导（如对偶定理的证明）1、准备工作：（1）标准型的矩阵形式 （2）将式中矩阵写成分块矩阵形式 2、将分块形式代入矩阵形式标准型，得出两个基本表达式：（1）由约束条件 可得 用非基变量表示基变量的表达式：（2-1） （2）将式（2-1）代入目标函数的表达式， 可得：用非基变量表示目标函数的表达式：5（3）借助一个恒等式推出用非基变量表示 目标函数的另一个等价表达式：代入式（2-2），并令 （2-4） 单纯形乘子 6返回继续线性规划的对偶问题一、对偶问题的提出二、原问题与

2、对偶问题的数学模型三、原问题与对偶问题的对应关系实例：某家电厂家利用现有资源生产两种 产品， 有关数据如下表： 设备A 设备B调试工序利润（元）0612521115时24时 5时产品产品D一、对偶问题的提出 （从生产计划问题到对资源的定价）如何安排生产，使获利最多？厂家设 产量 产量 设：设备A 元时 设备B 元时 调试工序 元时收购 付出的代价最小， 且对方能接受。出让代价应不低于用同等数量的资源自己生产的利润。 设备A 设备B调试工序利润（元）0612521115时24时 5时D厂家能接受的条件：收购方的意愿：单位产品(消耗资源)出租收入不低于2元单位产品 (消耗资源)出租收入不低于1元出

3、让代价应不低于用同等数量的资源自己生产的利润。厂家对偶问题原问题收购厂家一对对偶问题3个约束2个变量2个约束 3个变量原问题对偶问题一般规律 特点： 1 2限定向量b 价值向量C （资源向量） 3一个约束 一个变量。 4 的LP约束“ ” 的 LP是“ ”的约束。 5变量都是非负限制。 其它形式的对偶?二、原问题与对偶问题的数学模型1对称形式的对偶 当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。原问题对偶问题情形一：原问题对偶问题化为标准对称型情形二：证明对偶2、 非对称形式的对偶 若原问题的约束条件是等式，则原问题对偶问题推导:原问题 根据对称形式的对偶模型,可直接写出上述问题的对

4、偶问题:令 ，得对偶问题为：证毕。三、原问题与对偶问题的对应关系 原问题（或对偶问题）对偶问题（或原问题）例:对偶问题为返回结束线性规划的对偶问题返回继续第二节 对偶问题的基本性质引例对称性弱对偶性最优性对偶性（强对偶性）互补松弛性对偶问题的基本性质一、对称定理： 定理： 对偶问题的对偶是原问题。设原问题（1） 对偶问题（2）二、弱对偶性定理： 若 和 分别是原问题（1）及对偶问题（2）的可行解，则有 证明：对偶问题的基本性质从弱对偶性可得到以下重要结论：（1）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。（2）极小化问题（对偶问题）的任一可行解所对应的目标

5、函数值是原问题最优目标函数值的上界。（3）若原问题可行，但其目标函数值无界，则对偶问题无可行解。（4）若对偶问题可行，但其目标函数值无界，则原问题无可行解。（5）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。（6）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。原问题对偶问题对偶问题的基本性质定理三 最优性准则定理 若 、 分别为对称形式对偶线性规划的可行解，且两者目标函数的相应值相等，C =b ，则 ， 分别为原始问题和对偶问题的最优解。 C = bCXYb弱对偶定 理已 知结论最优解定义X=CX bY=特别取 bYbCXCC Yb证明思路 证明：原问题与对偶

6、问题的解一般有三种情况：一个有有限最优解 另一个有有限最优解。一个有无界解 另一个无可行解。两个均无可行解。四、对偶定理（强对偶性）： 若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。对偶问题的基本性质五、互补松弛性： 若 分别是原问题（1）与对偶问题（2）的可行解， 分别为（1）、（2）的松弛变量，则： 即：为最优解原问题第i条约束 A的第i行 说明：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件去严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。另一方面：对偶问题的第j条约束五、互补松弛性： 若 分别是原

7、问题（1）与对偶问题（2）的可行解， 分别为（1）、（2）的松弛变量，则：为最优解原理：在一对互为对偶的线型的规划问题中，原问题的变量和对偶问题的约束是一一对应的，原问题的约束和对偶问题的变量也是一一对应的。解释：互补松弛性描述了线型规划问题达到最优时，原问题（或对偶问题）的变量取值和对偶问题（或原问题）约束的松紧性之间的对应关系。当线型规划达到最优时，有下列关系：1、如果原问题的某一约束为紧约束（松弛变量为零），该约束对应的对偶变量应大于或等于零。2、如果原问题的某一约束为松约束（松弛变量大于零），该约束对应的对偶变量必为零。3、如果原问题的某一变量大于零，该变量对应的对偶约束为紧约束。4、如果原问题的某一变量等于零，该变量对应的对偶约束可能是紧约束，也可能是松约束。互补松弛定理应用：（1）从已知的最优对偶解，求原问题最优解，反之亦然。（2）证实原问题可行解是否为最优解。（3）从不同假设来进行试算，从而研究原始、对偶问题最优解的一般性质。（4）非线性的方面的应用。以上性质同样适用于非对称形式。书P52，例2已知：X=(x1，x2)T =(7/6，4/3