管理运筹学对偶问题.ppt

* * 对偶问题 一、对偶问题的提出 二、原问题与对偶问题的数学模型 三、原问题与对偶问题的对应关系 四、对偶问题的性质 五、对偶问题的经济意义 六、对偶单纯形法 例：某家电厂家利用现有资源生产两种产品， 有关数据如下表： 设备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元 出让代价应不低于 用同等数量的资源 自己生产的利润。 厂 家 对 偶 问 题 原 问 题 收 购 3个约束 2个变量 2个约束 3个变量 原问题 对偶问题 一般规律 特点： 1． 2．限定向量b 价值向量C （资源向量） 3．一个约束 一个变量。 4． 的LP约束“ ” 的 LP是“ ”的约束。 5．变量都是非负限制。 其它形式 的对偶 ? 目标函数变量的系数 约束条件右端项 约束条件右端项 目标函数变量的系数 ≥ ≥0 = 无约束 ≤ ≤0 约 束 条 件 n个 n个 变 量 无约束 = ≤0 ≥ ≥0 ≤ 变 量 m个 m个 约 束 条 件 目标函数 min 目标函数 max 对偶问题（或原问题） 原问题（或对偶问题） 例: 对偶问题为 * 解：对偶规划： 写出下列线性规划的对偶问题 * 写出下列线性规划的对偶问题 解：上述问题的对偶规划： 性质1 对称性定理：对偶问题的对偶是原问题 min W= Y b s.t. YA ≥ C Y ≤ 0 max Z=C X s.t. AX≥b X ≥0