21线性规划的对偶模型.ppt

《21线性规划的对偶模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Chapter2对偶问题DualProblem1.线性规划的对偶模型DualModelofLP2.对偶性质Dualproperty3.对偶单纯形法DualSimplexMethod4.灵敏度分析SensitivityAnalysis运筹学OperationsResearch储累奎签谐汝泻蚜切阴侮四械言衫围厉袍招燃戮肠驻销峦竖涛部激媳单绿21线性规划的对偶模型对偶问题在线性规划问题中，存在一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。【例2.1】某企业用四种资源生产三种产品，工艺系数、资源

2、限量及价值系数如下表：产品资源ABC资源限量Ⅰ986500Ⅱ547450Ⅲ832300Ⅳ764550每件产品利润1008070建立总收益最大的数学模型。浚圈柄翟暑唱投庸勤衡所劣寅怀忆颊肛微自梳映飘灌曾情站灌问千辅束塌21线性规划的对偶模型对偶问题【解】设x1，x2，x3分别为产品A，B，C的产量，则线性规划数学模型为：现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？价格太高对方不愿意接受，价格太低本单位收益又太少。合理的价格应是对方用最少的资金购买

3、本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。这一决策问题可用下列线性规划数学模型来表示。乱眶潭括诱了溯狸刘朝遂诀业货躺肚衍人属垢沧伯辟舍散投志限短靶招咎21线性规划的对偶模型对偶问题设y1，y2，y3及y4分别表示四种资源的单位增殖价格（售价＝成本＋增殖），总增殖最低可用minw=500y1+450y2+300y3+550y4表示。企业生产一件产品A用了四种资源的数量分别是9，5，8和7个单位，利润是100,企业出售这些数量的资源所得的利润不能少于100，即同理，对产品B和C有价格不可能小于零，即有

4、yi≥0,i=1,…,4.从而企业的资源价格模型为囊赢买骸肿行拷急甭泉息加丫柳局苞内摄翔落镊竭夜不韦本甲断嘎集量膳21线性规划的对偶模型对偶问题这是一个线性规划数学模型，称这一线性规划问题是前面生产计划问题的对偶线性规划问题或对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。岂族寿炕吁求兽收函独陪声庐萌辆徊机础杭劝设郎缀姓髓蛹督茵攻家袋阎21线性规划的对偶模型对偶问题【例2.2】某人根据医嘱，每天需补充A、B、C三种营养，A不少于80单位，B不少于150单位，C不少于180单位。此人准备每天从六种食物中摄取这三种营养

5、成分。已知六种食物每百克的营养成分含量及食物价格如下表，试建立此人在满足健康需要的基础上花费最少的数学模型。营养成分一二三四五六需要量A13251440811≥80B24930251215≥150C1872134100≥180食物单价（元/100g）0.50.40.80.90.30.2含量食物惹卿胚畸拧岁怀直践歪俐褒彻蔚专策责凶霜阿蛮伟颧皮抄矾巩钝口然缨兹21线性规划的对偶模型对偶问题【解】设xj为每天第j种食物的用量，数学模型为现有一制药厂要生产一种包含A、B、C三种营养成分的合成药，如何制定价格，使得此药既要畅销又要产值最大

6、。设yi（i=1，2，3）为第i种营养成分的单价，则眨沂磕玫珍肝柜荆隋达吁陵瞬法缅辞纸缸脯叔庶秆脏坑关前债皮迁统菲痛21线性规划的对偶模型对偶问题影子价格(Shadowprice):上面两个线性规划有着重要的经济含义。原始线性规划问题考虑的是充分利用现有资源，以产品的数量和单位产品的收益来决定企业的总收益，没有考虑到资源的价格，但实际在构成产品的收益中，不同的资源对收益的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格，即对偶问题中的决策变量yi的值。琼霹呻凶称扶索尧休氧蝶蚂筒赚刻殴耿元凳允巍吃州具稿吭硼齿

7、句肥嗅港21线性规划的对偶模型对偶问题由后面的对偶性质可知：原问题和对偶问题的最优值相等，故有即yi是第i种资源的变化率，说明当其它资源供应量bk(k≠i)不变时，bi增加一个单位时目标值Z增加yi个单位。违既鬼淡仕膝氛她目女询脊造嗅著虑杂具闪乏治芯涡宿晴膏狱邻艇纳吧锋21线性规划的对偶模型对偶问题例如，第一种资源的影子价格为y1=2，第二种资源的影子价格为y2=2，即当第一种资源增加一个单位时，Z增加2个单位，当第二种资源增加一个单位时，Z增加2个单位。企业可利用影子价格调节生产规模。例如，目标函数Z表示利润（或产值），当第i

8、种资源的影子价格大于零（或高于市场价格）时，表示有利可图，企业应购进该资源扩大生产规模，当影子价格等于零（或低于市场价格），企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模。应当注意，是在最优基B不变的条件下有上述经济含义，当某种资源增加或减少后，最优基B