对偶理论1.pptVIP

第3章 对偶线性规划 对偶问题 对偶理论 对偶单纯形法 对偶的经济解释 灵敏度分析 第3章 对偶理论与灵敏度分析 第一节 LP的对偶问题 思路1：如何安排生产，使获利最大 思路 2：设备出租，原料出售。 结论： 原问题与对偶问题的结构关系 原问题与对偶问题中的目标函数的优化方向相反（前者为极大，后者为极小） 原问题的每个约束式对应于对偶问题的一个决策变量，且原问题的资源系数（右端的常数项）为对偶问题相应决策变量的价值系数。原问题与对偶问题的等式右边项与价值系数互易位置。 对偶问题中的系数矩阵为原问题中的系数矩阵的转置 原问题的 “≤”不等式对应于对偶问题中的变量取非负值，原问题中决策变量非负对应于对偶问题中相应的“≥ ”不等式约束。 二、对称形式下对偶问题的一般形式 原问题与对偶问题的结构关系表 原问题 原LP DLP 约束系数阵 约束系数阵的转置 约束条件右端项向量 目标函数的系数向量 目标函数的价值系数向量 约束式右端项向量 三、对偶LP的对称性 第二节 单纯形法的矩阵描述 一、单纯形法的矩阵描述 初始单纯形表 选E为初始基 4.当B为最优基时 注：最优时， * * DUAL 一、对偶问题的提出（数学描述） 例:某厂有原料AB。利用设备生产Ⅰ、Ⅱ两种产品 3 2 获利水平 12 4 0 原料B 16 0 4 原料A 8 2 1 设 备 资源限量 产品Ⅱ 产品Ⅰ 设 为产品Ⅰ、Ⅱ的产量。 设备每台租价 ，原料A B 每单位售价 1） 2） 3） （若y为列向量） 为列向量， 为行向量； 一对对偶问题，技术系数矩阵转置， 价值系数向量与资源向量互易。 若设y为列向量，则有： 设 列向量； 行向量； 原问题与对偶问题的结构关系 原问题 对偶问题 目标函数 max 目标函数 min 非负 决策变量 非正 无约束 约束条件 ≥ ≤ = ≥ 约束条件 ≤ = 决策变量 非正 非负 无约束 非正 决策变量 非负 无约束 = 约束条件 = = = 约束条件 = = 非负 决策变量 非正 无约束 目标函数min 目标函数max 对偶问题(原问题) 原问题(对偶问题) Max w=5y1+4y2+6y3 ≥ ≤ ≤ y1 +2y2 y1 + y3 -3y1+2y2+y3 y1- y2+ y3 = 2 3 -5 1 y1 ≥ 0， y2 ≤ 0, y3无约束 对偶问题 例 写出线性规划问题的对偶问题 x1+x2- 3x3 +x4 ≥5 2x1+ 2x3 -x4≤4 x2 + x3 +x4=6 x1 ≤0 ,x2, x3 ≥0, x4无约束 Minz=2x1+3x2-5x3+x4 目标函数 约束条件 决策变量 对偶问题的对偶即原问题。 对偶问题 对偶 四、非对称形式的原-对偶问题 例：写出线性规划问题的对偶问题 化为SLP： 为单位阵。 为初始基变量。经过若干次迭代后， 基变量变为 。即此时表中 对应矩阵已由 。其间的行初等变换，相当于左乘 ，所以 1. 2. 3. 系数矩阵第 列向量变为 又 称 为单纯形乘子。令 ，则： 式 式 ………(2) …..(3) 对应检验数的相反数恰好是DLP的可行解。 DLP此时的目标函数值 （此后将看到 也是DLP最优） 若 （决策变量），则 剩余变量。