[管理学]运筹学经典课件第5次1.ppt

第2章 线性规划的  对偶理论及其应用 线性规划最重要的理论之一 进行经济分析的重要工具 §2.1 线性规划的对偶问题 * 关于可行基B的典则形式: 上堂课的主要内容: 单纯形法的矩阵形式： E 0 常数项 ≤0 最优值 最优单纯形表 一、对偶问题的提出 二、原问题与对偶问题的对应关系 三、原问题与对偶问题的数学模型 一、对偶问题的提出 例1：大众家电厂家利用现有资源生产两种 产品， 有关数据如下表： 设备A 设备B 设备C 利润（百元） 0 6 1 2 5 2 1 1 15时 24时 5时 产品Ⅰ 产品Ⅱ 可用工时 设 Ⅰ产量––––– Ⅱ产量––––– 问如何安排生产，使获利最多？ 例2.1* 有一个企业家接到一批加工定单，需用到 设备 A,B,C,有意租用大众家电厂的三种设备，问该企业 家应如何出价，才能使家电厂觉得有利可图肯把设 备出租，又使自己付出的租金最少？ 企 业 家 付出的代价最小 出让代价应不低于 用同等数量的资源 自己生产的利润。 对方能接受 厂 家 设备A 设备B 设备C 利润（百元） 0 6 1 2 5 2 1 1 15时 24时 5时 Ⅰ Ⅱ D 厂家能接受的条件： 收购方的意愿： 出让代价应不低于 用同等数量的资源 自己生产的利润。 设：设备A —y1元／时,设备B ––y2元／时, 设备C––y3元／时 对 偶 问 题 原 问 题 企 业 家 厂 家 一对对偶问题 例2.2 假定一个成年人每天需要从食物中获取3000kcal的热量、55g蛋白质和800mg的钙。如果市场上只有四种食品可供选择，问如何选择才能在满足营养的前提下使购买食品的费用最小？ 2 500 10 200 白菜 800 55 3000 每天 需求 3 300 20 900 大米 6 200 60 800 鸡蛋 14 400 50 1000 猪肉 价格元 钙mg 蛋白质g 热量kcal 食品 例2.2* 有一个厂商生产三种可代替食品中热量、蛋白质、钙的营养素，问该厂商应如何制定每种营养素单位营养量的价格，使其获得最大的收益？ 2 500 10 200 白菜 800 55 3000 每天 需求 3 300 20 900 大米 6 200 60 800 鸡蛋 14 400 50 1000 猪肉 价格元 钙mg 蛋白质g 热量kcal 食品 消费者： 经营者： 原问题 对偶问题 一对对偶问题 目标:求max 目标:求min 原问题 对偶问题 二、原问题与对偶问题的对应关系 变量: 2个且≥0 约束: 3个且≤ 约束: 2个且≥ 变量: 3个且≥0 目标函数的系数 约束方程的常数项 约束方程的常数项 目标函数的系数 约束方程的系数矩阵A 约束方程的系数矩阵A′ 对偶问题： 原问题： 3个约束 4个变量 4个约束 3个变量 三、原问题与对偶问题的数学模型 1、对称型线性规划的对偶问题 2、标准型线性规划的对偶问题 3、混合型线性规划的对偶问题 1、对称型线性规划的对偶问题 对称型线性规划： 形如： bi无正负限制 或： 定义： 设原线性规划问题为： 则称下列线性规划问题： 为其对偶规划， （P） （D） 一对对偶问题 互为对偶 所求对偶问题为： 所求对偶问题为： 对称型对偶问题的矩阵形式： 2、标准型对偶问题 设原问题（P）为标准型： 化为对称型 所求对偶问题为： 所求对偶问题为： 所求对偶问题为： 所求对偶问题为： 与对称型对偶问题比较： 规则： 若原问题（P）的约束方程为“=”约束 则对偶原问题（D）的变量无符号限制 因此若原问题（P）为标准型： 则对偶问题（D）为： 3、混合型对偶问题 化为对称型 化为对称型 对偶规划问题（D）为 *