Chapter3.1-3.2线性规划的对偶和灵敏度分析

《Chapter3.1-3.2线性规划的对偶和灵敏度分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter3线性规划的对偶和灵敏度分析对偶问题的提出对偶问题的基本性质影子价格对偶单纯形法灵敏度分析(选讲)本章主要内容：3.1对偶问题的提出对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？对偶问题的提出两个黄鹂鸣翠柳，一行白鹭上青天。窗含西岭千秋雪，门泊东吴万里船。杜甫《绝句》俩家具制造商间的对话：唉!我想租您的木工和油漆工一用。咋样？价格嘛

2、……好说，肯定不会让您兄弟吃亏。王老板做家具赚了大钱，可惜我老李有高科技产品，却苦于没有足够的木工和油漆工咋办？只有租咯。Hi：王老板，听说近来家具生意好呀，也帮帮兄弟我哦!家具生意还真赚钱，但是现在的手机生意这么好，不如干脆把我的木工和油漆工租给他，又能收租金又可做生意。价格嘛……好商量，好商量。只是…...王老板李老板引例1对偶问题的提出王老板家具厂木器车间生产木门与木窗两种产品。加工木门收入为56元/扇，加工木窗收入为30元/扇。生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工

3、总工时为120小时，油漆工总工时为50小时。该车间应如何安排生产才能使每日收入最大？王老板解：设该车间每日安排生产木门x1扇，木窗x2扇，则数学模型为设用y1,y2分别表示付给木工和油漆工的价格。王老板在做定价决策时,作如下比较：若用4个小时木工和2个小时油漆工可以生产一扇木门,可获利56元,那么付给加工木门的木工和油漆工的价格应不低于加工一扇木门的利润,这就有同理付给加工木窗的木工和油漆工的价格应不低于加工一扇木窗的利润,这就有把每日可用木工和油漆工的总工时出让,其总收入为只能在满足≥所有产品的利润的条件下,其总收入尽可能少,才能成交

4、.王老板的家具生产模型：x1、x2是木门、木窗生产量。Z是家具销售总收入。maxZ=56x1+30x2s.t.4x1+3x2≤120（木工）2x1+x2≤50（油漆工）x1，x2≥0原始线性规划问题，记为（P）王老板的资源出租模型：y1、y2木、油漆工出租价格。W是资源出租租金总收入。minW=120y1+50y2s.t.4y1+2y2≥563y1+y2≥30y1，y2≥0对偶线性规划问题，记为（D）所得不得低于生产的获利（不吃亏原则）要使对方能够接受（竞争性原则）两个原则对偶问题的提出王老板按（D）的解y1、y2出租其拥有的木、漆工资

5、源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。按时下最流行的一个词，叫什么来着————对偶问题的提出MaxZ=1500x1+2500x23x1+2x2652x1+x2403x275x1，x20s.t目标函数约束条件设三种资源的使用单价分别为y1,y2,y3y1y2y3生产单位产品甲的资源消耗所得不少于单位产品甲的获利生产单位产品乙的资源消耗所得不少于单位产品乙的获利3y1+2y215002y1+y2+3y32500甲乙设备能力A3

6、265B2140C0375获利15002500通过使用所有设备对外利用所获得的收益W=65y1+40y2+75y3对偶问题的提出根据原则2，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：MinW=65y1+40y2+75y33y1+2y215002y1+y2+3y32500y1,y2,y30s.t目标函数约束条件原线性规划问题称为原问题，此问题为对偶问题，y1,y2,y3为对偶变量，也称为影子价格对偶问题的提出2.4线性规划的对偶理论MaxZ=1500x1+2500x23x1+2x2652x1+x2403x

7、275x1，x20s.t原问题（对偶问题）对偶问题（原问题）一、原问题与对偶问题的对应关系MinW=65y1+40y2+75y33y1+2y215002y1+y2+3y32500y1,y2,y30s.t（y1）（y2）（y3）（x1）3201500（x2）2102500654075minωmaxz3个约束2个变量2个约束3个变量线性规划的对偶理论对偶问题的形式定义设原线性规划问题为则称下列线性规划问题为其对偶问题，其中yi(i=1,2,…,m)称为对偶变量上述对偶问题称为对称型对偶问题原问题简记为(P)，对偶问题简记为(D)称

8、问题(P)和(D)为一对对偶问题线性规划的对偶理论对称型问题的对偶规则1、给每个原始约束条件定义一个非负对偶变量yi(i=1,2,…,m)；2、使原问题的目标函数系数cj变为其对偶问题约束条件的右端常数；3