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

《对偶线性规划和灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《对偶线性规划和灵敏度分析.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章对偶线性规划与灵敏度分析第三章第三章对偶线对偶线性规划性规划与灵敏与灵敏度分析度分析|线性规划的对偶问题|线性规划的对偶理论|对偶解的经济解释|对偶单纯形法|敏感性分析线性规划的对偶问题|对偶问题的提出|如何将原问题转化为对偶问题|原问题与对偶问题的对应关系对偶问对偶问题的提题的提出出|对偶理论是线性规划的内容之一。任何一个线性规划都有一个伴生的线性规划，称之为原规划的对偶规划问题。下面通过实例引出对偶问题，然后给出对偶线性规划的定义|家具厂线性规划模型|该问题站在家具厂管理者的角度追求销售收入最大例：生产计划问题|胜利家具厂生产桌子和椅子两种家具。桌子售价50元，椅子售价30元，生产一

2、个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。该厂如何生产才能使每月销售收入最大？家具厂家具厂家具厂家具厂的另一的另一的另一的另一个模型个模型个模型个模型|考虑另一种问题：一个企业家有一批待加工的订单，有意利用该家具厂的资源来加工他的产品，该企业家试图劝说家具厂管理者将资源组给他。|他的目标是什么？|很明显，目标是他所付的租金最少。租赁者模型的目标函数|设y1为每个木工工时的租金，y2为每个油漆工工时的租金，则得到租赁者的目标函数是使租金最小化：|租金=木工租金木工工时+油漆工租金|Min 120y1+50

3、y2|租赁者希望所付的租金越少越好。租赁者租赁者模型的模型的约束条约束条件件|所付租金应不低于家具厂利用这些资源能获得的利益，模型应有一下约束：|1）生产桌子等价的租金桌子价格 4y1+2y2 50|2）生产椅子等价的租金椅子价格 3y1+y2 30|租金应大于零 y1，y2 0租赁者的完整模型|家具厂与租赁者所面临的数学模型都是线性规划，它们在结构上具有某些对称性，称后一个线性规划为原规划的对偶问题。两个模型的区别与联系|联系：都是关于家具厂的模型，使用相同的数据|区别：反应的内容不同，前者站在家具厂立场追求家具厂收入最大；后者则站在家具厂对手的立场上寻求付给家具厂的租金最少。|前一个是原问

4、题，后一个是对偶问题对偶问题的界关系|用图解法解租赁问题|在最优情况下，家具厂的最优收入应等于租赁者愿意支付的最小租金。|目标函数互为上下界。|租赁者了解家具厂资源可创造的价值，他付给家具厂的租金至少要大于家具厂利用该资源可创造的价值，因此家具厂模型（最大）的解是租赁者模型（最小）的一个下界。对偶问题的界关系|家具厂了解自己手里的资源可创造的价值，只有当租赁者支付的租金大于该价值时才会出让手中的资源，因此，租赁者模型的解是家具厂模型的一个上界。例：营养配餐问题 假定一个成年人每天需要从食物中获取3000大卡的热量，55可蛋白质和800毫克的钙，市场上只有四种食品可供选择。它们每公斤所含热量和营

5、养成分以及市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小。食物营养表序号食品名称热量(大卡)蛋白质(g)钙(mg)价格(元)1猪肉100050400142鸡蛋8006020063大米9002030034白菜200105002营养配餐模型|决策变量：xj每天购入j种食品数量|目标函数：每天采购成本最小|约束方程：满足每天的营养要求 满足3000大卡的人量要求满足蛋白质摄入量要求：满足钙摄入量要求：非负约束：采购量不能为负值营养配餐问题的完整模型|某生产减肥食品的公司生产三种可代替食品中热量、蛋白质和钙的营养素，希望产品既有市场竞争力，又能带来最大的利润，需构造模型研究定价问

6、题。|模型变量为营养素单位营养量的价格；|目标函数应反映销售收入最大的目标；|约束反映市场竞争条件：购买与食品营养价值相同的营养素的成本应小于食品价格|变量设置 y1：单位热量营养素价格；y2：单位蛋白质营养素价格 y3：单位钙营养素价格；|目标函数：满足人一天需要的营养素的销售收入最大：热量需求量单位热量营养素价格+蛋白质需求量单位蛋白质价格+钙需求量单位钙营养素价格 max：3000y1+55y2+800y3|约束：购买与猪肉、鸡蛋、大米和白菜营养价值等价的营养素成本应不高于它的价格：|配餐问题与对偶问题的比较|对偶问题的定义见书P47如何将如何将原问题原问题转化为转化为对偶问对偶问题题|原问题和对偶问题有很多内在联系，它们之间存在严格的对应关系；|目标函数类型之间的对应关系；|目标函数系数与右边项的对应关系；|约束系数矩阵之间的对应关系；|约束类型与变量类型之间的对应关系；