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

1、2.6 线性规划应用案例线性规划应用案例 用线性规划解决经济管理和生产中的优化问题，首先要将实际问题抽象为数学模型，是一项技巧性很强的创造性工作，然后通过软件求解，并对求解结果进行分析。下面通过几个例子介绍线性规划的应用案例。1231212,A AAB BC C 例2.6.1 某公司生产三种产品，它们在两种设备上加工，并耗用两种原材料。已知生产单位产品耗用的设备时间和原材料、单位产品利润及设备和原材料的最多可使用量见表2.6.1。2.6.1 经理会议建议的分析经理会议建议的分析表表2.6.1 生产单位产品耗用的工时和原材料数据生产单位产品耗用的工时和原材料数据产品每天最多可使用量 121430

2、302460140420111300每件利润(元)3020501A2A3A1(min)B设备2(min)B设备2()C kg原料1()C kg原料资源23370420AAA 已知对产品的需求每天不低于件，不超过件。经理会议讨论如何增加公司收入，提出了如下建议：(1)产品提价，使每件利润增至60元，但市场销量将下降为每天不超过210件；21221240min100 2minCBBAAB (2)原材料是限制产量增加的因素，如果通过别的供应商提供补充，每千克价格将比原供应商高20元。(3)设备和每天可增加的时间，但相应需支付额外费用各350元；(4)产品的需求增加到每天件；(5)产品在上的加工时间可

3、缩短到，但每天需额外支出40元。分别讨论上述各条建议的可行性。123123123123131212323,max3020502430324604420300 .70240A AAxxxSxxxxxxxxxxxxxs txxx 解 设计划生产的数量分别为，则可建立线性规划数学模型：123,0 xx 用LINGO求解max=30*x1+20*x2+50*x3;x1+2*x2+x3=430;3*x1+2*x3=460;x1+4*x2=420;x1+x2+x3=70;x3=250000;x1+x5=380000;x2+x6=265200;x3+x7=408100;x4+x8=0;7.5*x5-7.0*

4、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;12345678264937.9135702.1408100124660115062.1129497.9054401933400,xxxxxxxxLL 求解得最优解：，生产飞机汽油的数量为生产飞机汽油2的数量为250000。例例2.6.3 某投资公司拟制定今后5年的投资计划，初步考虑下面四个投资项目：项目A：从第1年到第4年每年年初可以投资，于次年年末收回成本，并可获利润15%；项目B：第3年年初可以投资，到第5年年

5、末可以收回成本，并获得利润25%,但为了保证足够的资金流动，规定该项目的投资金额上限为不超过总金额的40%；项目C：第2年年初可以投资，到第5年年末可以收回成本，并获得利润40%,但公司规定该项目的最大投资金额不超过总金额的30%；项目D：5年内每年年初可以购买公债，于当年年末可以归还本金,并获利息6%。该公司现有投资金额100万元,请帮助该公司制定这些项目每年的投资计划,使公司到第5年年末核算这5年投资的收益率达到最大。2.6.3连续投资问题连续投资问题 解解 虽然这是一个连续投资问题，但可以把5年的投资计划一并考虑。用决策变量 (i=1,2,3,4,5)分别表示第i年年初为项目A,B,C,

6、D的投资额，根据问题的要求各个变量对应的关系见2.6.4，表中的空白处表示当年不能为该项目投资，也可以认为投资额等于0。1234,iiiixxxx表表2.6.4 连续投资问题各变量的对应关系连续投资问题各变量的对应关系12345ABCD项目年份11x21x41x31x32x23x14x54x44x34x24x 首先注意到，项目D每年都可以投资，并且当年末就能收回本息，所以公司每年都应该把全部资金投出去。因此投资方案应满足以下条件：第1年：将100万元资金全部用项目A和D的投资，即11141000000 xx 第2年：第2年初可投资项目A、C、D的资金是第1年项目D投资收回的本息之和 141.0

7、6x21232414231.06300000 xxxxx，第3年：第3年初可投资项目A、B、D的资金是第1年项目A投资和第2年项目D投资收回的本息之和3132341124321.151.06400000 xxxxxx，第5年：第5年初投资于项目D的资金是第3年项目A投资和第4年项目D投资收回的本息之和5431441.151.06xxx 第4年：第4年初可投资项目A、D的资金是第2年项目A投资和第3年项目D投资收回的本息之和414421341.151.06xxxx问题的目标是第5年年末公司收回四个项目全部总和最大，即41322354max1.151.251.401.06Sxxxx于是我们所建立线

8、性规划问题的数学模型为：4132235411142123241431323411244144213454314423321234max1.151.251.401.0610000001.0601.151.060.1.151.0601.151.060300000,400000,0(1,2,3,4,iiiiSxxxxxxxxxxxxxxxstxxxxxxxxxxxxxi5)用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

9、=0;x41+x44-1.15*x21-1.06*x34=0;x54-1.15*x31-1.06*x44=0;x32=400000;x23=300000;11142123243132414454 716981.1,283018.9,0,300000,0424528.3,4000000,0488207.5max1437500 xxxxxxxxxxS，。得最优解：即连续投资方案为：第1年用于投资项目A的金额为716981.1元，项目D的金额为283018.9元；第2年用于项目C的投资金额为300000元（这部分资金是第1年投资项目D收回的本息之和）；第3年用于项目A的投资金额为424528.3元，

10、用于项目B的投资金额为400000元（这两部分资金是第1年投资项目A收回的本息之和）；第4年不投资；第5年用于项目D的金额为 488207.5元（这部分资金是第3年投资项目A收回的本息之和），可使该公司到第五年末核算收益率最大。到第5年年末该公司拥有总资金1437500元,五年期间的收益率43.75%。2.6.5多工厂模型多工厂模型 例例2.6.5 一家公司有A和B两个工厂，每个工厂生产两种同样的产品。一种是普通的，一种是精制的。普通产品每件可盈利10元，精制产品每件可盈利15元。两厂采用相同的加工工艺研磨和抛光来生产这些产品。A厂每周的研磨能力为80小时，抛光能力为60小时；B厂每周的研磨能

11、力为60小时，抛光能力为75小时。两厂生产各类单位产品所需的研磨和抛光工时（以小时计）如表2.6.6所示。另外，每类每件产品都消耗4公斤原材料，该公司每周可获得原材料120公斤，分配给A厂75公斤，B厂45公斤。问应该如何制定生产计划可使总产值达到最大？表表2.6.6 多工厂模型技术系数多工厂模型技术系数工厂A工厂B工厂产品普通精制普通精制研磨4253抛光25531234xAxAxBx 解 设 为 厂生产普通产品的产量，为 厂生产精品产品的产量；为 厂生产普通产品的产量，厂生产精品产品的产量。则建立两个独立的线性规划模型为：B厂模型 A厂模型 1212121212max101544754280

12、.25600,0Sxxxxxxstxxxx3434343434max101544455360.56750,0Sxxxxxxstxxxx利用LINGO求解得A厂模型的最优解：1211.25,7.5,max225xxS，剩余20小时研磨工时；B厂模型的最优解：340,11.25,max168.75xxS，剩余26.25小时研磨工时和7.5小时抛光工时。但是由于120公斤原料可以在两个工厂按照收益最大来分配，让模型来确定原材料的分配，则公司模型1为12341234121234341234max10151015444412042802560.536056750,0,0,0Sxxxxxxxxxxxxst

13、xxxxxxxx可以求得公司模型1的最优解为：12349.17,8.33,0,12.5,xxxxmaxS=404.17,A厂和B厂分别剩余26.67和22.5小时研磨工时。总利润比两个工厂模型利润之和超过10.42元，两个工厂原料分配分A厂70公斤，B厂50公斤。但是，由于两个厂的生产工艺完全相同，除了原料之外，研磨和抛光两个工艺也在一起考虑，可以建立公司模型212341234123412341234max1015101544441204253140.25561350,0,0,0Sxxxxxxxxxxxxstxxxxxxxx1234345,25,0,0,max425704250,0 xxxxS

14、xxBA 求解得公司模型的最优解为：，剩余研磨工时小时。总收益元达到最大。同时，由可以看出，工厂 的效率没有工厂 的效率高。这种讨论也适合于更大的、更实际的多工厂模型，使得不但协助各工厂制定本厂的最优计划而且解决工厂之间的分配问题。习题21.写出下列线性规划问题的对偶问题（1）123123123123123min601020321.21,0Sxxxxxxxxxstxxxx x x(2)12312312312323min2242352373.4650,0Sxxxxxxxxxstxxxxx(3)1234123412341234124max236344721273818.25340,0,0Sxxxx

15、xxxxxxxxstxxxxxxx (4)123123123123max436360.22340,0Sxxxxxxstxxxx x x(1)2.设有线性规划问题：无约束43214321432143214321,0,0,0632162432.6334maxxxxxxxxxxxxxxxxxtsxxxxZ （1）写出该问题的对偶问题；（2）将该问题变换为标准形，并写出初始单纯形表。3.判断下列说法是否正确，为什么？（1）如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解;（2）如果线性规划的对偶问题无可行解，则原问题也一定无可行解；（3）任何线性规划问题具有唯一的对偶问题；（4）当线性规划

16、问题的原问题和对偶问题都有可行解时，则它们都有最优解,且对应目标函数的最优值相等。4.已知线性规划问题1234124122341231234max24382669,0Sxxxxxxxxxxxxxxxx xx x要求（1）写出其对偶问题；（2）已知原问题的最优解为(2,2,4,0)T*xmax S=16，试根据对偶理论，直接求出对偶问题的最优解。5.设有线性规划问题 0,6525.325max32123211321321xxxbxxxbxxxtsxxxS 其中b1,b2是常数。已知此线性规划问题的最优基所对应的单纯形表为表2-1：301b210100c-8-11-S-1500a-7-d-eBxb

17、1x2x3x4x5x1x5x(3)写出其对偶规划问题，并指出对偶规划问题的最优解。(1)确定b1，b2；（2）确定常数a,b,c,d,e。6.用对偶单纯形方法求解下列线性规划问题（1）1231323123min4121833.225,0Sxxxxxstxxx x x(2)123123123123min524322.63510,0Sxxxxxxstxxxx x x（3）0,28242.32min32132321321321xxxxxxxxxxxtsxxxS（4）0,1211.34max212122121xxxxxxxtsxxS 7.考虑如下线性规划问题123123123123123min6040

18、80322434.2223,0Sxxxxxxxxxstxxxx x x要求(1)写出对偶线性规划问题；(2)用对偶单纯形方法求解原问题；(3)用单纯形方法求解对偶问题；(4)对比(2)与(3)每一步计算得到的结果。8.已知线性规划问题12312312123max26.24,0Sxxxxxxstxxx x x先用单纯形方法求出最优解，再分别就下列情形进行分析：（1）目标函数中变量x1,x2,x3的系数分别在什么范围内变化，问题的最优解不变；（2）两个约束的右端常数项在什么范围内变化，问题的最优解不变；（3）增加一个新的约束条件，寻找新的最优解。9.已知线性规划问题12121212max10534

19、9.528,0Sxxxxstxxx x其最优基所对应的单纯形表如表2-2。表2-2 最优基所对应的单纯形表3/2015/14-3/14110-1/72/7-S-35/200-5/14-25/14Bxb1x2x3x4x1x2x试用灵敏度分析的方法分别判断：（1）目标函数中的价值系数c1或c2分别在什么范围内变动，上述最优解不变；（2）约束条件右端项b1,b2当一个保持不变，另一个在什么范围内变化时，原问题的最优解保持不变；（3）问题的目标函数变为 max=12x1+4x2时，最优解如何变？（4）约束条件右端项由 变为 时，最优解为多少？98 111910.某厂利用甲、乙、丙三种原料生产A、B、C

20、、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、2.5、1，应如何安排生产计划？11.求解参数线性规划问题（1）123123123123max(6)(142)(132)12242.2460,0Sxxxxxxstxxxx x x123123123123123123min(30)(78)(135)6692133312.61261836915,0Sxxxxxxxxxstxxxxxxx x x(020)（2）