对偶线性规划和灵敏度分析

第三章对偶线性规划与灵敏度分析 第三章对偶线性规划与灵敏度分析 线性规划的对偶问题线性规划的对偶理论对偶解的经济解释对偶单纯形法敏感性分析 线性规划的对偶问题 对偶问题的提出如何将原问题转化为对偶问题原问题与对偶问题的对应关系 对偶问题的提出 对偶理论是线性规划的内容之一 任何一个线性规划都有一个伴生的线性规划 称之为原规划的对偶规划问题 下面通过实例引出对偶问题 然后给出对偶线性规划的定义家具厂线性规划模型该问题站在家具厂管理者的角度追求销售收入最大 例 生产计划问题 胜利家具厂生产桌子和椅子两种家具 桌子售价50元 椅子售价30元 生产一个桌子需要木工4小时 油漆工2小时 生产一个椅子需要木工3小时 油漆工1小时 该厂每月可用木工工时为120小时 油漆工工时为50小时 该厂如何生产才能使每月销售收入最大 家具厂的另一个模型 考虑另一种问题 一个企业家有一批待加工的订单 有意利用该家具厂的资源来加工他的产品 该企业家试图劝说家具厂管理者将资源组给他 他的目标是什么 很明显 目标是他所付的租金最少 租赁者模型的目标函数 设y1为每个木工工时的租金 y2为每个油漆工工时的租金 则得到租赁者的目标函数是使租金最小化 租金 木工租金 木工工时 油漆工租金Min120y1 50y2租赁者希望所付的租金越少越好 租赁者模型的约束条件 所付租金应不低于家具厂利用这些资源能获得的利益 模型应有一下约束 1 生产桌子等价的租金 桌子价格4y1 2y2 502 生产椅子等价的租金 椅子价格3y1 y2 30租金应大于零y1 y2 0 租赁者的完整模型 家具厂与租赁者所面临的数学模型都是线性规划 它们在结构上具有某些对称性 称后一个线性规划为原规划的对偶问题 两个模型的区别与联系 联系 都是关于家具厂的模型 使用相同的数据区别 反应的内容不同 前者站在家具厂立场追求家具厂收入最大 后者则站在家具厂对手的立场上寻求付给家具厂的租金最少 前一个是原问题 后一个是对偶问题 对偶问题的界关系 用图解法解租赁问题在最优情况下 家具厂的最优收入应等于租赁者愿意支付的最小租金 目标函数互为上下界 租赁者了解家具厂资源可创造的价值 他付给家具厂的租金至少要大于家具厂利用该资源可创造的价值 因此家具厂模型 最大 的解是租赁者模型 最小 的一个下界 对偶问题的界关系 家具厂了解自己手里的资源可创造的价值 只有当租赁者支付的租金大于该价值时才会出让手中的资源 因此 租赁者模型的解是家具厂模型的一个上界 例 营养配餐问题 假定一个成年人每天需要从食物中获取3000大卡的热量 55可蛋白质和800毫克的钙 市场上只有四种食品可供选择 它们每公斤所含热量和营养成分以及市场价格见下表 问如何选择才能在满足营养的前提下使购买食品的费用最小 食物营养表 营养配餐模型 决策变量 xj每天购入j种食品数量目标函数 每天采购成本最小约束方程 满足每天的营养要求满足3000大卡的人量要求 满足蛋白质摄入量要求 满足钙摄入量要求 非负约束 采购量不能为负值 营养配餐问题的完整模型 某生产减肥食品的公司生产三种可代替食品中热量 蛋白质和钙的营养素 希望产品既有市场竞争力 又能带来最大的利润 需构造模型研究定价问题 模型变量为营养素单位营养量的价格 目标函数应反映销售收入最大的目标 约束反映市场竞争条件 购买与食品营养价值相同的营养素的成本应小于食品价格 变量设置y1 单位热量营养素价格 y2 单位蛋白质营养素价格y3 单位钙营养素价格 目标函数 满足人一天需要的营养素的销售收入最大 热量需求量 单位热量营养素价格 蛋白质需求量 单位蛋白质价格 钙需求量 单位钙营养素价格max 3000y1 55y2 800y3 约束 购买与猪肉 鸡蛋 大米和白菜营养价值等价的营养素成本应不高于它的价格 配餐问题与对偶问题的比较对偶问题的定义见书P47 如何将原问题转化为对偶问题 原问题和对