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

1、2.6 线性规划运用案例线性规划运用案例 用线性规划处理经济管理和消费中的优化问题，首先要用线性规划处理经济管理和消费中的优化问题，首先要将实践问题笼统为数学模型，是一项技巧性很强的发明性任务，将实践问题笼统为数学模型，是一项技巧性很强的发明性任务，然后经过软件求解，并对求解结果进展分析。下面经过几个例然后经过软件求解，并对求解结果进展分析。下面经过几个例子引见线性规划的运用案例。子引见线性规划的运用案例。1231212,A AAB BC C 例2.6.1 某公司生产三种产品，它们在两种设备上加工，并耗用两种原材料。已知生产单位产品耗用的设备时间和原材料、单位产品利润及设备和原材料的最多可使用

2、量见表2.6.1。2.6.1 经理睬议建议的分析经理睬议建议的分析表表2.6.1 消费单位产品耗用的工时和原资料数据消费单位产品耗用的工时和原资料数据产品每天最多可使用量 121430302460140420111300每件利润(元)3020501A2A3A1(min)B设备2(min)B设备2()C kg原料1()C kg原料资源23370420AAA 已知对产品的需求每天不低于件，不超过件。经理会议讨论如何增加公司收入，提出了如下建议： (1)产品提价，使每件利润增至60元，但市场销量将下降为每天不超过210件；21221240min100 2minCBBAAB (2)原材料是限制产量增加

3、的因素，如果通过别的供应商提供补充，每千克价格将比原供应商高20元。 (3)设备和每天可增加的时间，但相应需支付额外费用各350元； (4)产品的需求增加到每天件；(5)产品在上的加工时间可缩短到，但每天需额外支出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

4、*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*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的数量为25

5、0000 。 例例2.6.3 某投资公司拟制定今后某投资公司拟制定今后5年的投资方案，初步思索下面四个年的投资方案，初步思索下面四个投资工程：投资工程：工程工程A：从第：从第1年到第年到第4年每年年初可以投资，于次年年末收回本钱，并年每年年初可以投资，于次年年末收回本钱，并可获利润可获利润15%；工程工程B：第：第3年年初可以投资，到第年年初可以投资，到第5年年末可以收回本钱，并获得利润年年末可以收回本钱，并获得利润25%,但为了保证足够的资金流动，规定该工程的投资金额上限为不超越总但为了保证足够的资金流动，规定该工程的投资金额上限为不超越总金额的金额的40%；工程工程C：第：第2年年初可以投

6、资，到第年年初可以投资，到第5年年末可以收回本钱，并获得利润年年末可以收回本钱，并获得利润40%,但公司规定该工程的最大投资金额不超越总金额的但公司规定该工程的最大投资金额不超越总金额的30%；工程工程D：5年内每年年初可以购买公债，于当年年末可以归还本金年内每年年初可以购买公债，于当年年末可以归还本金, 并获并获利息利息6%。该公司现有投资金额该公司现有投资金额100万元万元, 请协助该公司制定这些工程每年的投资方请协助该公司制定这些工程每年的投资方案案,使公司到第使公司到第5年年末核算这年年末核算这5年投资的收益率到达最大。年投资的收益率到达最大。2.6.3延续投资问题延续投资问题 解解

7、虽然这是一个延续投资问题，但可以把虽然这是一个延续投资问题，但可以把5年的投资方案一并思索。用年的投资方案一并思索。用决策变量决策变量 (i=1,2,3,4,5) 分别表示第分别表示第i年年初为工程年年初为工程A,B,C,D的的投资额，根据问题的要求各个变量对应的关系见投资额，根据问题的要求各个变量对应的关系见2.6.4，表中的空白处表示当，表中的空白处表示当年不能为该工程投资，也可以以为投资额等于年不能为该工程投资，也可以以为投资额等于0。1234,iiiixxxx表表2.6.4 延续投资问题各变量的对应关系延续投资问题各变量的对应关系12345ABCD工程年份11x21x41x31x32x

8、23x14x54x44x34x24x 首先留意到，工程D每年都可以投资，并且当年末就能收回本息，所以公司每年都应该把全部资金投出去。因此投资方案应满足以下条件：第1年：将100万元资金全部用工程A和D的投资，即11141000000 xx 第2年：第2年初可投资工程A、C、D的资金是第1年工程D投资收回的本息之和 141.06x21232414231.06300000 xxxxx， 第3年：第3年初可投资工程A、B、D的资金是第1年工程A投资和第2年工程D投资收回的本息之和3132341124321.151.06400000 xxxxxx， 第5年：第5年初投资于工程D的资金是第3年工程A投资

9、和第4年工程D投资收回的本息之和5431441.151.06xxx 第4年：第4年初可投资工程A、D的资金是第2年工程A投资和第3年工程D投资收回的本息之和414421341.151.06xxxx问题的目的是第5年年末公司收回四个工程全部总和最大，即41322354max1.151.251.401.06Sxxxx于是我们所建立线性规划问题的数学模型为： 4132235411142123241431323411244144213454314423321234max1.151.251.401.0610000001.0601.151.060. .1.151.0601.151.060300000,40

10、0000,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=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

11、.3,4000000,0488207.5max1437500 xxxxxxxxxxS，。得最优解： 即延续投资方案为：第1年用于投资工程A的金额为716981.1元，工程D的金额为283018.9元；第2年用于工程C的投资金额为300000元这部分资金是第1年投资工程D收回的本息之和；第3年用于工程A的投资金额为424528.3元，用于工程B的投资金额为400000元这两部分资金是第1年投资工程A收回的本息之和；第4年不投资；第5年用于工程D的金额为 488207.5元这部分资金是第3年投资工程A收回的本息之和，可使该公司到第五年末核算收益率最大。到第5年年末该公司拥有总资金1437500元,

12、五年期间的收益率43.75%。2.6.5多工厂模型多工厂模型 例例2.6.5 一家公司有一家公司有A和和B两个工厂，每个工厂消费两种同样的产品。一两个工厂，每个工厂消费两种同样的产品。一种是普通的，一种是精制的。普通产品每件可盈利种是普通的，一种是精制的。普通产品每件可盈利10元，精制产品每件可元，精制产品每件可盈利盈利15元。两厂采用一样的加工工艺元。两厂采用一样的加工工艺研磨和抛光来消费这些产品。研磨和抛光来消费这些产品。A厂每周的研磨才干为厂每周的研磨才干为80小时，抛光才干为小时，抛光才干为60小时；小时；B厂每周的研磨才干为厂每周的研磨才干为60小时，抛光才干为小时，抛光才干为75小

13、时。两厂消费各类单位产品所需的研磨和抛光工小时。两厂消费各类单位产品所需的研磨和抛光工时以小时计如表时以小时计如表2.6.6所示。另外，每类每件产品都耗费所示。另外，每类每件产品都耗费4公斤原资料公斤原资料，该公司每周可获得原资料，该公司每周可获得原资料120公斤，分配给公斤，分配给A厂厂75公斤，公斤，B厂厂45公斤。问公斤。问应该如何制定消费方案可使总产值到达最大？应该如何制定消费方案可使总产值到达最大？表表2.6.6 多工厂模型技术系数多工厂模型技术系数工厂A工厂B工厂产品普通精制普通精制研磨4253抛光25531234xAxAxBx 解 设 为 厂生产普通产品的产量， 为 厂生产精品产

14、品的产量；为 厂生产普通产品的产量，厂生产精品产品的产量。则建立两个独立的线性规划模型为：B厂模型 A厂模型 1212121212max101544754280. .25600,0Sxxxxxxstxxxx3434343434max101544455360. .56750,0Sxxxxxxstxxxx利用LINGO求解得A厂模型的最优解： 1211.25,7.5,max225xxS，剩余20小时研磨工时；B厂模型的最优解： 340,11.25,max168.75xxS，剩余26.25小时研磨工时和7.5小时抛光工时。 但是由于120公斤原料可以在两个工厂按照收益最大来分配，让模型来确定原资料的

15、分配，那么公司模型1为12341234121234341234max10151015444412042802560. .536056750,0,0,0Sxxxxxxxxxxxxstxxxxxxxx可以求得公司模型1的最优解为： 12349.17,8.33,0,12.5,xxxxmaxS=404.17, A厂和B厂分别剩余26.67和22.5小时研磨工时。总利润比两个工厂模型利润之和超越10.42元，两个工厂原料分配分A厂70公斤，B厂50公斤。但是，由于两个厂的消费工艺完全一样，除了原料之外，研磨和抛光两个工艺也在一同思索，可以建立公司模型212341234123412341234max101

16、5101544441204253140. .25561350,0,0,0Sxxxxxxxxxxxxstxxxxxxxx1234345,25,0,0,max425704250,0 xxxxSxxBA 求解得公司模型的最优解为：，剩余研磨工时小时。总收益元达到最大。同时，由可以看出，工厂 的效率没有工厂 的效率高。 这种讨论也适宜于更大的、更实践的多工厂模型，使得不但协助各工厂制定本厂的最优方案而且处理工厂之间的分配问题。习题21.写出以下线性规划问题的对偶问题1123123123123123min601020321. .21,0Sxxxxxxxxxstxxxx x x (2)1231231231

17、2323min2242352373. .4650,0Sxxxxxxxxxstxxxxx(3)1234123412341234124max236344721273818. .25340,0,0Sxxxxxxxxxxxxstxxxxxxx (4)123123123123max436360. . 22340,0Sxxxxxxstxxxx x x(1) 2.设有线性规划问题：无约束43214321432143214321, 0, 0, 0632162432.6334maxxxxxxxxxxxxxxxxxtsxxxxZ 1写出该问题的对偶问题；2将该问题变换为规范形，并写出初始单纯形表。 3.判别以下说

18、法能否正确，为什么？1假设线性规划的原问题存在可行解，那么其对偶问题也一定存在可行解;2假设线性规划的对偶问题无可行解，那么原问题也一定无可行解；3任何线性规划问题具有独一的对偶问题；4当线性规划问题的原问题和对偶问题都有可行解时，那么它们都有最优解, 且对应目的函数的最优值相等。4.知线性规划问题1234124122341231234max24382669,0Sxxxxxxxxxxxxxxxx xx x要求1写出其对偶问题；2知原问题的最优解为 (2,2,4,0)T*xmax S =16，试根据对偶实际，直接求出对偶问题的最优解。 5.设有线性规划问题 0,6525.325max321232

19、11321321xxxbxxxbxxxtsxxxS 其中b1,b2是常数。知此线性规划问题的最优基所对应的单纯形表为表2-1：301b210100c-8- 11-S-1500a-7-d-eBxb1x2x3x4x5x1x5x(3)写出其对偶规划问题，并指出对偶规划问题的最优解。(1)确定b1，b2；2确定常数a,b,c,d,e。6.用对偶单纯形方法求解以下线性规划问题11231323123min4121833. .225,0Sxxxxxstxxx x x (2)123123123123min524322. . 63510,0Sxxxxxxstxxxx x x30,28242.32min32132

20、321321321xxxxxxxxxxxtsxxxS40,1211.34max212122121xxxxxxxtsxxS 7.思索如下线性规划问题123123123123123min604080322434. .2223,0Sxxxxxxxxxstxxxx x x要求(1)写出对偶线性规划问题；(2)用对偶单纯形方法求解原问题；(3)用单纯形方法求解对偶问题；(4)对比(2)与(3)每一步计算得到的结果。8.知线性规划问题12312312123max26. .24,0Sxxxxxxstxxx x x先用单纯形方法求出最优解，再分别就以下情形进展分析：1目的函数中变量x1,x2,x3的系数分别在什么范围内变化，问题的最优解不变；2两个约束的右端常数项在什么范围内变化，问题的最优解不变；3添加一个新的约束条件，寻觅新的最优解。9.知线性规划问题12121212max105349. . 528,0Sxxxxstxxx x其最优基所对应的单纯形表如表2-2。表2-2 最优基所对应的单