-线性规划对偶问题.pptVIP

第一、二节 线性规划的对偶问题 一、对偶问题的提出 二、原问题与对偶问题的数学模型 三、原问题与对偶问题的对应关系 一、对偶问题的提出 实例：某家电厂家利用现有资源生产两种产品， 有关数据如下表： 如果我们换一个角度，考虑另外一种经营问题。 假如有另一个厂家需租用该家电厂的现有资源。因此，他要同家电厂谈判付给该厂设备及调试工时的单价。请构造一个数学模型来研究如何既使家电厂觉得有利可图肯把资源出租给他，又使自己付的租金最少？ 又如教材P53有关数据如下: 模型: 二、原问题与对偶问题的数学模型 三、原问题与对偶问题的对应关系 结论 (对于不等式) 原问题为max 则:对偶问 题的约束方程的不等式的方向与原问题的变量的不等式的方向同向. 对偶问题的变量的不等式的方向与原问题的约束方程的不等式的方向反向 原问题为min 则:对偶问 题的约束方程的不等式的方向与原问题的变量的 不等式的方向反向. 对偶问题的变量的不等式的方向与原问题的约束方程的不等式的方向同向. (对于等式与无约束对应) 线性规划的对偶问题 * 返回 上页 下页 对偶问题 * 返回 继续 设备A 设备B 调试工序 利润（元） 0 6 1 2 5 2 1 1 15时 24时 5时 产品Ⅰ 产品Ⅱ D 如何安排生产， 使获利最多？ 厂 家 设 Ⅰ产量––––– Ⅱ产量––––– 设：设备A —— 元／时 设备B –––– 元／时 调试工序 –––– 元／时 收 购 付出的代价最小， 且对方能接受。 出让代价应不低于 用同等数量的资源 自己生产的利润。 设备A 设备B 调试工序 利润（元） 0 6 1 2 5 2 1 1 15时 24时 5时 Ⅰ Ⅱ D 厂家能接受的条件： 租用方的意愿： 单位产品Ⅰ出租 收入不低于2元 单位产品Ⅱ出租收入不低于1元 出让代价应不低于 用同等数量的资源 自己生产的利润。 对 偶 问 题 原 问 题 收 购 厂 家 一对对偶问题 设备A 设备B 设备C 利润（元） 2 4 0 2 2 0 5 3 12时 16时 15时 产品Ⅰ 产品Ⅱ 总时 设：租用设备A —— 元／时 租用设备B –––– 元／时 租用设备C–––– 元／时 对 偶 问 题 原 问 题 收 购 厂 家 一对对偶问题 特点： 1． 2．限定向量b 价值向量C （资源向量） 3．一个约束 一个变量。 4． 的LP约束“ ” 的 LP是“ ”的约束。 3个约束 2个变量 2个约束 3个变量 原问题 对偶问题 一般规律 1．对称形式的对偶 当原问题与对偶问题只含有不等式约束时，称为对称形式的对偶。 原问题 对偶问题 情形一： 例1：写出下列线性规划问题的对偶问题 max S = 10x1 + x2 + 2x3 s.t. X1 + x2 + 2x3 ? 10 4x1 +2x2 - x3 ? 20 x1，x2 ， x3 ? 0 解：该问题的对偶问题： min g = 10 y1 + 20 y2 s.t. y1 + 4y2 ? 10 y1 + 2y2 ? 1 2 y1 - y2 ? 2 y1，y2 ? 0 max S = 10x1 + x2 + 2x3 s.t. X1 + x2 + 2x3 ? 10 4x1 +2x2 - x3 ? 20 x1，x2 ， x3 ? 0 例2：写出下列线性规划问题的对偶问题 min S=12x1+8x2 +16x3+12x4 s.t. 2x1+ x2 +4x3 ? 2 2x1+2x2 + 4x4 ? 3 x1，x2 ， x3 ， x4 ? 0 解：该问题的对偶问题： max g = 2y1