第2章线性规划的对偶理论与灵敏度分析26课件.ppt

,。,2.6 线性规划应用案例 用线性规划解决经济管理和生产中的优化问题，首先要将实际问题抽象为数学模型，是一项技巧性很强的创造性工作，然后通过软件求解，并对求解结果进行分析。下面通过几个例子介绍线性规划的应用案例。,2.6.1 经理会议建议的分析,。2.6 线性规划应用案例2.6.1 经理会议建议的分析,表2.6.1 生产单位产品耗用的工时和原材料数据,表2.6.1 生产单位产品耗用的工时和原材料数据产,第2章线性规划的对偶理论与灵敏度分析26课件,max=30*x1+20*x2+50*x3;x1+2*x2+x3=70;x3=240;,max=30*x1+20*x2+50*x3;,（2）可行，但不能增加利润。因为它本身的影子价格才,第2章线性规划的对偶理论与灵敏度分析26课件,例2.6.2 一种汽油的特性可用两个指标描述:其点火性用“辛烷数”描述,其挥发性用“蒸汽压力”描述。某炼油厂有四种标准汽油,其标号分别为1,2,3,4，其特性及库存量列于表2.6.2中，将上述标准汽油适量混合，可得两种飞机汽油，某标号为1，2，这两种飞机汽油的性能指标及产量需求列于表2.6.3中。问应如何根据库存情况适量混合各种标准汽油，使既满足飞机汽油的性能指标，而产量又最高。,2.6.2汽油配料模型,表2.6.2 各种标号的标准汽油的特性与存量,例2.6.2 一种汽油的特性可用两个指标描述:,第2章线性规划的对偶理论与灵敏度分析26课件,整理以后就是线性规划模型。用LINGO求解的输入模型：max=x1+x2+x3+x4;x5+x6+x7+x8=250000;x1+x5=0;7.5*x5-7.0*x6-13.0*x7+8.0*x8=0;2.85*x1-1.42*x2+4.27*x3-18.49*x4=0;2.85*x5-1.42*x6+4.27*x7-18.49*x8=0;,整理以后就是线性规划模型。,例2.6.3 某投资公司拟制定今后5年的投资计划，初步考虑下面四个投资项目：项目A：从第1年到第4年每年年初可以投资，于次年年末收回成本，并可获利润15%；项目B：第3年年初可以投资，到第5年年末可以收回成本，并获得利润25%,但为了保证足够的资金流动，规定该项目的投资金额上限为不超过总金额的40%；项目C：第2年年初可以投资，到第5年年末可以收回成本，并获得利润40%,但公司规定该项目的最大投资金额不超过总金额的30%；项目D：5年内每年年初可以购买公债，于当年年末可以归还本金,并获利息6%。该公司现有投资金额100万元,请帮助该公司制定这些项目每年的投资计划,使公司到第5年年末核算这5年投资的收益率达到最大。,2.6.3连续投资问题,例2.6.3 某投资公司拟制定今后5年的,解 虽然这是一个连续投资问题，但可以把5年的投资计划一并考虑。用决策变量(i=1,2,3,4,5)分别表示第i年年初为项目A,B,C,D的投资额，根据问题的要求各个变量对应的关系见2.6.4，表中的空白处表示当年不能为该项目投资，也可以认为投资额等于0。,表2.6.4 连续投资问题各变量的对应关系,项目,年份,首先注意到，项目D每年都可以投资，并且当年末就能收回本息，所以公司每年都应该把全部资金投出去。因此投资方案应满足以下条件：,解 虽然这是一个连续投资问题，但可以把5,第1年：将100万元资金全部用项目A和D的投资，即,第2年：第2年初可投资项目A、C、D的资金是第1年项目D投资收回的本息之和,第5年：第5年初投资于项目D的资金是第3年项目A投资和第4年项目D投资收回的本息之和,第4年：第4年初可投资项目A、D的资金是第2年项目A投资和第3年项目D投资收回的本息之和,第1年：将100万元资金全部用项目A和D的投资，即,问题的目标是第5年年末公司收回四个项目全部总和最大，即,于是我们所建立线性规划问题的数学模型为：,用LINGO求解,问题的目标是第5年年末公司收回四个项目全部总和最大，即于是我,max=1.15*x41+1.25*x32+1.4*x23+1.06*x54;x11+x14=1000000;x21+x23+x24-1.06*x14=0;x31+x32+x34-1.15*x11-1.06*x24=0;x41+x44-1.15*x21-1.06*x34=0;x54-1.15*x31-1.06*x44=0;x32=400000;x23=300000;,得最优解：,即连续投资方案为：第1年用于投资项目A的金额为716981.1元，项目D的金额为283018.9元；第2年用于项目C的投资金额为300000元（这部分资金是第1年投资项目D收回的本息之和）；第3年用于项目A的投资金额为424528.3元，用于项目B的投资金额为400000元（这两部分资金是第1年,max=1.15*x41+1.25*x32+1.4*x23+,投资项目A收回的本息之和）；第4年不投资；第5年用于项目D的金额为 488207.5元（这部分资金是第3年投资项目A收回的本息之和），可使该公司到第五年末核算收益率最大。到第5年年末该公司拥有总资金1437500元,五年期间的收益率43.75%。,投资项目A收回的本息之和）；第4年不投资；第5年用于项目D的,2.6.5多工厂模型,例2.6.5 一家公司有A和B两个工厂，每个工厂生产两种同样的产品。一种是普通的，一种是精制的。普通产品每件可盈利10元，精制产品每件可盈利15元。两厂采用相同的加工工艺研磨和抛光来生产这些产品。A厂每周的研磨能力为80小时，抛光能力为60小时；B厂每周的研磨能力为60小时，抛光能力为75小时。两厂生产各类单位产品所需的研磨和抛光工时（以小时计）如表2.6.6所示。另外，每类每件产品都消耗4公斤原材料，该公司每周可获得原材料120公斤，分配给A厂75公斤，B厂45公斤。问应该如何制定生产计划可使总产值达到最大？,表2.6.6 多工厂模型技术系数,2.6.5多工厂模型 例2.6.5 一家公司有A和B,但是由于120公斤原料可以在两个工厂按照收益最大来分配，让模型来确定原材料的分配，则公司模型1为,B厂模型 A厂模型 利用LINGO求解得A厂模型的最优解：,可以求得公司模型1的最优解为：,maxS=404.17,A厂和B厂分别剩余26.67和22.5小时研磨工时。总利润比两个工厂模型利润之和超过10.42元，两个工厂原料分配分A厂70公斤，B厂50公斤。但是，由于两个厂的生产工艺完全相同，除了原料之外，研磨和抛光两个工艺也在一起考虑，可以建立公司模型2,可以求得公司模型1的最优解为：maxS=404.17,A,这种讨论也适合于更大的、更实际的多工厂模型，使得不但协助各工厂制定本厂的最优计划而且解决工厂之间的分配问题。,这种讨论也适合于更大的、更实际的多工厂模型，使得不但,习题2,1.写出下列线性规划问题的对偶问题,（1）,(2),(3),(4),(1),习题21.写出下列线性规划问题的对偶问题（1）(2)(3),2.设有线性规划问题：,（1）写出该问题的对偶问题；（2）将该问题变换为标准形，并写出初始单纯形表。,3.判断下列说法是否正确，为什么？（1）如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解;（2）如果线性规划的对偶问题无可行解，则原问题也一定无可行解；（3）任何线性规划问题具有唯一的对偶问题；（4）当线性规划问题的原问题和对偶问题都有可行解时，则它们都有最优解,且对应目标函数的最优值相等。,2.设有线性规划问题：（1）写出该问题的对偶问题；（2）,4.已知线性规划问题,4.已知线性规划问题要求（1）写出其对偶问题；（2）已知原问,5.设有线性规划问题,其中b1,b2是常数。已知此线性规划问题的最优基所对应的单纯形表为表2-1：,(3)写出其对偶规划问题，并指出对偶规划问题的最优解。,(1)确定b1，b2；（2）确定常数a,b,c,d,e。,5.设有线性规划问题 其中b1,b2是常数。,6.用对偶单纯形方法求解下列线性规划问题,（1）,(2),（3）,（4）,6.用对偶单纯形方法求解下列线性规划问题（1）(2)（3）,7.考虑如下线性规划问题,要求(1)写出对偶线性规划问题；(2)用对偶单纯形方法求解原问题；(3)用单纯形方法求解对偶问题；(4)对比(2)与(3)每一步计算得到的结果。,7.考虑如下线性规划问题要求(1)写出对偶线性规划问题；(2,8.已知线性规划问题,先用单纯形方法求出最优解，再分别就下列情形进行分析：（1）目标函数中变量x1,x2,x3的系数分别在什么范围内变化，问题的最优解不变；（2）两个约束的右端常数项在什么范围内变化，问题的最优解不变；（3）增加一个新的约束条件，寻找新的最优解。,8.已知线性规划问题先用单纯形方法求出最优解，再分别就下列情,9.已知线性规划问题,其最优基所对应的单纯形表如表2-2。,表2-2 最优基所对应的单纯形表,9.已知线性规划问题其最优基所对应的单纯形表如表2-2。表2,试用灵敏度分析的方法分别判断：（1）目标函数中的价值系数c1或c2分别在什么范围内变动，上述最优解不变；（2）约束条件右端项b1,b2当一个保持不变，另一个在什么范围内变化时，原问题的最优解保持不变；（3）问题的目标函数变为 max=12x1+4x2时，最优解如何变？,试用灵敏度分析的方法分别判断：（4）约束条件右端项由 变为,10.某厂利用甲、乙、丙三种原料生产A、B、C、D、E五种产品，单位产品（万件）对原材料的消耗（吨）、原材料的限量（吨）以及单位产品利润如表2-3。,表2-3 三种原料生产五种产品的数据,10.某厂利用甲、乙、丙三种原料生产A、B、C、D、E五种产,（1）试确定一种最优的生产计划，对应甲、乙、丙三种原料的影子价格分别是多少？分析其他产品不安排生产的原因；（2）对A产品的利润系数作灵敏度分析；（3）对甲、乙、丙的资源限量作灵敏度分析；（4）若D产品对甲、乙、丙的单位消耗分别为0、2.5、1，应如何安排生产计划？,（1）试确定一种最优的生产计划，对应甲、乙、丙三种原料的影子,11.求解参数线性规划问题,（1）,（2）,11.求解参数线性规划问题（1）（2）,