《线性规划的对偶理论与灵敏度分析》由会员分享，可在线阅读，更多相关《线性规划的对偶理论与灵敏度分析（31页珍藏版）》请在金锄头文库上搜索。
1、。2.6 线性规划应用案例线性规划应用案例 用线性规划解决经济管理和生产中的优化问题，首先要将实际问题抽象为数学模型，是一项技巧性很强的创造性工作，然后通过软件求解，并对求解结果进行分析。下面通过几个例子介绍线性规划的应用案例。2.6.1 经理会议建议的分析经理会议建议的分析表表2.6.1 生产单位产品耗用的工时和原材料数据生产单位产品耗用的工时和原材料数据产品每天最多可使用量 121430302460140420111300每件利润(元)302050max =30*x1+20*x2+50*x3;x1+2*x2+x3=430;3*x1+2*x3=460;x1+4*x2=420;x1+x2+x3
2、=70;x3=250000; x1+x5=380000; x2+x6=265200;x3+x7=408100;x4+x8=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; 例例 某投资公司拟制定今后5年的投资计划，初步考虑下面四个投资项目：项目A：从第1年到第4年每年年初可以投资，于次年年末收回成本，并可获利润15%；项目B：第3年年初可以投资，到第5年年末可以收回成本，并获得利润25%,但为了保证足够的资金流动，规定该项目的投资金额上限
3、为不超过总金额的40%；项目C：第2年年初可以投资，到第5年年末可以收回成本，并获得利润40%,但公司规定该项目的最大投资金额不超过总金额的30%；项目D：5年内每年年初可以购买公债，于当年年末可以归还本金, 并获利息6%。该公司现有投资金额100万元, 请帮助该公司制定这些项目每年的投资计划,使公司到第5年年末核算这5年投资的收益率达到最大。连续投资问题连续投资问题 解解 虽然这是一个连续投资问题，但可以把5年的投资计划一并考虑。用决策变量 (i=1,2,3,4,5) 分别表示第i年年初为项目A,B,C,D的投资额，根据问题的要求各个变量对应的关系见2.6.4，表中的空白处表示当年不能为该项
4、目投资，也可以认为投资额等于0。表表2.6.4 连续投资问题各变量的对应关系连续投资问题各变量的对应关系12345ABCD项目年份 首先注意到，项目D每年都可以投资，并且当年末就能收回本息，所以公司每年都应该把全部资金投出去。因此投资方案应满足以下条件：第1年：将100万元资金全部用项目A和D的投资，即 第2年：第2年初可投资项目A、C、D的资金是第1年项目D投资收回的本息之和 第3年：第3年初可投资项目A、B、D的资金是第1年项目A投资和第2年项目D投资收回的本息之和 第5年：第5年初投资于项目D的资金是第3年项目A投资和第4年项目D投资收回的本息之和 第4年：第4年初可投资项目A、D的资金
5、是第2年项目A投资和第3年项目D投资收回的本息之和问题的目标是第5年年末公司收回四个项目全部总和最大，即于是我们所建立线性规划问题的数学模型为： 用LINGO求解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的金额为元，项目D的
6、金额为元；第2年用于项目C的投资金额为300000元（这部分资金是第1年投资项目D收回的本息之和）；第3年用于项目A的投资金额为元，用于项目B的投资金额为400000元（这两部分资金是第1年投资项目A收回的本息之和）；第4年不投资；第5年用于项目D的金额为 元（这部分资金是第3年投资项目A收回的本息之和），可使该公司到第五年末核算收益率最大。到第5年年末该公司拥有总资金1437500元,五年期间的收益率43.75%。多工厂模型多工厂模型 例例 一家公司有A和B两个工厂，每个工厂生产两种同样的产品。一种是普通的，一种是精制的。普通产品每件可盈利10元，精制产品每件可盈利15元。两厂采用相同的加工
7、工艺研磨和抛光来生产这些产品。A厂每周的研磨能力为80小时，抛光能力为60小时；B厂每周的研磨能力为60小时，抛光能力为75小时。两厂生产各类单位产品所需的研磨和抛光工时（以小时计）如表所示。另外，每类每件产品都消耗4公斤原材料，该公司每周可获得原材料120公斤，分配给A厂75公斤，B厂45公斤。问应该如何制定生产计划可使总产值达到最大？表表2.6.6 多工厂模型技术系数多工厂模型技术系数工厂A工厂B工厂产品普通精制普通精制研磨4253抛光2553B厂模型 A厂模型 利用LINGO求解得A厂模型的最优解： 剩余20小时研磨工时；B厂模型的最优解： 剩余26.25小时研磨工时和7.5小时抛光工时
8、。 但是由于120公斤原料可以在两个工厂按照收益最大来分配，让模型来确定原材料的分配，则公司模型1为可以求得公司模型1的最优解为： maxS=404.17, A厂和B厂分别剩余和小时研磨工时。总利润比两个工厂模型利润之和超过元，两个工厂原料分配分A厂70公斤，B厂50公斤。但是，由于两个厂的生产工艺完全相同，除了原料之外，研磨和抛光两个工艺也在一起考虑，可以建立公司模型2 这种讨论也适合于更大的、更实际的多工厂模型，使得不但协助各工厂制定本厂的最优计划而且解决工厂之间的分配问题。习题21.写出下列线性规划问题的对偶问题（1）(2)(3) (4)(1) 2.设有线性规划问题： （1）写出该问题的
9、对偶问题；（2）将该问题变换为标准形，并写出初始单纯形表。 3.判断下列说法是否正确，为什么？（1）如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解;（2）如果线性规划的对偶问题无可行解，则原问题也一定无可行解；（3）任何线性规划问题具有唯一的对偶问题；（4）当线性规划问题的原问题和对偶问题都有可行解时，则它们都有最优解, 且对应目标函数的最优值相等。4.已知线性规划问题要求（1）写出其对偶问题；（2）已知原问题的最优解为 max S =16，试根据对偶理论，直接求出对偶问题的最优解。 5.设有线性规划问题 其中b1,b2是常数。已知此线性规划问题的最优基所对应的单纯形表为表2-1
10、：301b210100c-8- 11-S-1500a-7-d-e(3)写出其对偶规划问题，并指出对偶规划问题的最优解。(1)确定b1，b2；（2）确定常数a,b,c,d,e。6.用对偶单纯形方法求解下列线性规划问题（1） (2)（3）（4） 7.考虑如下线性规划问题要求(1)写出对偶线性规划问题；(2)用对偶单纯形方法求解原问题；(3)用单纯形方法求解对偶问题；(4)对比(2)与(3)每一步计算得到的结果。8.已知线性规划问题先用单纯形方法求出最优解，再分别就下列情形进行分析：（1）目标函数中变量x1,x2,x3的系数分别在什么范围内变化，问题的最优解不变；（2）两个约束的右端常数项在什么范围
11、内变化，问题的最优解不变；（3）增加一个新的约束条件，寻找新的最优解。9.已知线性规划问题其最优基所对应的单纯形表如表2-2。表2-2 最优基所对应的单纯形表3/2015/14-3/14110-1/72/7-S-35/200- 5/14 -25/14试用灵敏度分析的方法分别判断：（1）目标函数中的价值系数c1或c2分别在什么范围内变动，上述最优解不变；（2）约束条件右端项b1,b2当一个保持不变，另一个在什么范围内变化时，原问题的最优解保持不变；（3）问题的目标函数变为 max=12x1+4x2时，最优解如何变？ （4）约束条件右端项由 变为 时，最优解为多少？ 10.某厂利用甲、乙、丙三种原
12、料生产A、B、C、D、E五种产品，单位产品（万件）对原材料的消耗（吨）、原材料的限量（吨）以及单位产品利润如表2-3。表表2-3 三种原料生产五种产品的数据三种原料生产五种产品的数据产品原料A B C D E原料限量（吨）甲1 210110乙1 013224丙1 222221单位产品利润（万元/万件）820102021（1）试确定一种最优的生产计划，对应甲、乙、丙三种原料的影子价格分别是多少？分析其他产品不安排生产的原因；（2）对A产品的利润系数作灵敏度分析；（3）对甲、乙、丙的资源限量作灵敏度分析；（4）若D产品对甲、乙、丙的单位消耗分别为0、1，应如何安排生产计划？11.求解参数线性规划问题（1）（2）
