运筹学例题及答案课件.ppt

1、运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外作业及答案作业及答案 0,44222.326max32131321321xxxxxxxxtsxxxz线性规划线性规划cj6-2300cBxBbx1x2x3x4x50 x422-12100 x5410401 cj-zj6-23006x111-1/211/200 x5301/23-1/21 cj-zj01-3-306x1410401-2x26016-12 cj-zj00-9-2-2cj6-2300cBxBbx1x2x3x4x5达到最优解，且最优解唯一达到最优解，且最优解唯一 0,02226.22max3213231321321xx

2、xxxxxxxxtsxxxzcj2-12000-M-M-McBxBbx1x2x3x4x5x6x7x8x9-Mx76111-100100-Mx82-2010-10010-Mx9002-100-1001Cj-zj2-M3M-1M+2-M-M-M000-Mx76103/2-101/210-1/2-Mx82-2010-10010-1x2001-1/200-1/2001/2Cj-zj2-M05/2M+3/2-M-M1/2M-1/200-3/2M+1/2cj2-12000-M-M-McBxBbx1x2x3x4x5x6x7x8x9-Mx73400-13/21/21-3/2-1/22x32-201000010

3、-1x21-1100-1/2-1/201/21Cj-zj5+4M00-M3/2M+3/21/2M-1/20-5/2M-3/2-3/2M+1/22x13/4100-1/43/81/81/4-3/8-1/82x37/2001-1/2-1/41/41/21/4-1/4-1x27/4010-1/4-1/8-3/81/81/83/8Cj-zj0005/4-无界解无界解3 3，某厂在今后四个月内需租用仓库堆放物资。已知各月份需某厂在今后四个月内需租用仓库堆放物资。已知各月份需租用仓库面积见表，仓库租借费用随合同期不同而不同，期租用仓库面积见表，仓库租借费用随合同期不同而不同，期限越长折扣越大，具体数字见表

4、。租借合同每个月月初都可限越长折扣越大，具体数字见表。租借合同每个月月初都可办理，合同规定具体的租借面积和月数，因此该厂可根据需办理，合同规定具体的租借面积和月数，因此该厂可根据需要，在任何一个月月初办理合同，每次办理可签一份或多份，要，在任何一个月月初办理合同，每次办理可签一份或多份，总目标是总的租借费用最低，请建立数学模型并用软件给出总目标是总的租借费用最低，请建立数学模型并用软件给出结果。结果。月份1234所需仓库面积（100m2）15102012合同租借期限1个月2个月3个月4个月租借费用2800450060007300解解:设一月初签订合同期限为一个月，两个月，三个设一月初签订合同期

5、限为一个月，两个月，三个月，四个月的仓库面积分别为月，四个月的仓库面积分别为 ，二月，二月初签订合同期限为一个月，两个月，三个月的仓库初签订合同期限为一个月，两个月，三个月的仓库面积分别为面积分别为 ，三月初签订合同期限为一，三月初签订合同期限为一个月，两个月的仓库面积分别为个月，两个月的仓库面积分别为 ，四月初签，四月初签订合同期限为一个月的仓库面积为订合同期限为一个月的仓库面积为 。则则11x12x13x14x232221,xxx3231,xx41x142313322212413121117300)(6000)(4500)(2800minxxxxxxxxxxz 01220101541322

6、31432312322141323222114131214131211ijxxxxxxxxxxxxxxxxxxxxx计算结果如下计算结果如下4 4，某厂生产，某厂生产I,II,IIII,II,III三种产品，都分别经过三种产品，都分别经过A,BA,B两道两道工序加工。设工序加工。设A A工序可分别在设备工序可分别在设备A1A1或或A2A2上完成，上完成，有有B1B1，B2B2，B3B3三种设备可用于完成三种设备可用于完成B B工序。已知产工序。已知产品品I I可在可在A,BA,B任何一种设备上加工；产品任何一种设备上加工；产品IIII可在任何可在任何规格的规格的A A设备上加工，但完成设备上加

7、工，但完成B B工序时，只能在工序时，只能在B1B1设设备上加工；产品备上加工；产品IIIIII只能在只能在A2A2和和B2B2设备上加工。加设备上加工。加工单位产品所需的工序时间及其它各项数据见表，工单位产品所需的工序时间及其它各项数据见表，试安排最优生成计划，使该厂获利最大。试安排最优生成计划，使该厂获利最大。设备 产品I II III设备有效设备有效台时台时设备加工费设备加工费（元（元/h）A15 10 60000.05A27 9 12100000.03B16 840000.06B24 1170000.11B3740000.05原料费（元原料费（元/件）件）售价（元售价（元/件）件）0.

8、25 0.35 0.501.25 2.00 2.80解：设第解：设第种产品中，分别在种产品中，分别在 上加工的数量依次为上加工的数量依次为 ，第，第种种产品中分别在产品中分别在A1,B1和和A2,B1 上加工的数量为上加工的数量为 生产生产种产品数量为种产品数量为 。3,2,1),(),(21 jBABAjj654321,;,xxxxxx87,xx9x 04000)(7700011)(44000)(8)(610000129)(7600010)(5)(705.011)(411.0)(8)(606.0129)(703.010)(505.0)5.08.2()(35.02()(25.025.1(max

9、639528741986547321639528741986547321987654321jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz对偶理论对偶理论1.1.已知线性规划问题：已知线性规划问题：0,966 283.42max4321321432214214321xxxxxxxxxxxxxxxtsxxxxz要求要求：a)a)写出对偶问题，写出对偶问题，b)b)已知原问题最有解已知原问题最有解X X*=(2,2,4,0),=(2,2,4,0),用互补松弛性求出对偶问题用互补松弛性求出对偶问题的最优解。的最优解。解：对偶问题：解：对偶问题：0,11

10、4 322.9668min4321314343214214321yyyyyyyyyyyyyyytsyyyyw将原问题的最优解带入约束，发现第将原问题的最优解带入约束，发现第4 4个约束为严格个约束为严格不等式，所以，得不等式，所以，得y y4 4*=0=0又因为，原问题最优解的前三个分量都大于又因为，原问题最优解的前三个分量都大于0 0，所以，所以，有如下三个等式成立。有如下三个等式成立。14 322332121yyyyyy解方程组得对偶问题的最优解为解方程组得对偶问题的最优解为Y Y*=(4/5,3/5,1,0)=(4/5,3/5,1,0)2 2。已知线性规划问题。已知线性规划问题 0,21

11、8 262.23max21221212121xxxxxxxxxtsxxz及最终单纯形表及最终单纯形表cj320000cBxBbx1x2x3x4x5x62x24/3012/3-1/3 003x110/3 10-1/3 2/3000 x5300-11100 x62/300-2/3 1/301cjzj00-1/3-4/3 00表表1 1分析下列各种条件单独变化时，最优解将如何变化。分析下列各种条件单独变化时，最优解将如何变化。（a）第）第1，2个约束条件的后端项分别由个约束条件的后端项分别由6变变7，8变变4；（b）目标函数变为）目标函数变为 ;（c）增加一个变量增加一个变量 ，系数为，系数为（d）

12、问题中变量）问题中变量 的系数变为的系数变为（e）增加一个新的约束）增加一个新的约束2152maxxxz 3xTpc)2,3,2,1(,433 2xT)2,1,2,3,4(41 x解：解：a a）0041b 25320041103/13/20111003/23/1003/13/2b将其加到表（将其加到表（1 1）的最终单纯形表的基变量）的最终单纯形表的基变量b b这一列数这一列数字上得表（字上得表（2 2）（表（表2 2）表（表（2 2）中原问题为非可行解，故用对偶单纯形法继续）中原问题为非可行解，故用对偶单纯形法继续计算得表（计算得表（3 3）cj320000cBxBbx1x2x3x4x5x

13、62x210/3 012/3-1/3 003x11/310-1/3 2/3000 x5-200-11100 x6-4/3 00-2/3 1/301cjzj00-1/3-4/3 00（表（表3 3）cj320000cBxBbx1x2x3x4x5x62x220101/32/303x111001/3-1/3 00 x32001-1-100 x60000-1/3-2/3 1cjzj000-5/3-1/3 0即新解为即新解为Tx)0,0,0,2,2,1(第第25页页b)b)将将c cj j的改变反应到最终单纯形表上的改变反应到最终单纯形表上,得表（得表（4 4）cj250000cBxBbx1x2x3x4

14、x5x65x24/3012/3-1/3 002x110/3 10-1/3 2/3000 x5300-11100 x62/300-2/3 1/301cjzj00-8/3 1/300继续迭代继续迭代,得表（得表（5 5）cj250000cBxBbx1x2x3x4x5x65x220100012x1210100-20 x5100101-30 x4200-2103cjzj00-200-1表表5 5即新解为即新解为Tx)2,2(c c）将其加到最终单纯形表上得表（将其加到最终单纯形表上得表（6 6）012321003/43/147 24102321103/13/20111003/23/1003/13/27

15、1/7pBpcj320000cBxBbx1x2x3x4x5x62x24/3012/3-1/3 003x110/3 10-1/3 2/3000 x5300-11100 x62/300-2/3 1/301cjzj00-1/3-4/3 004x701421继续迭代继续迭代,得表（得表（7 7）表表6 6cj320000cBxBbx1x2x3x4x5x62x24/3012/3-1/3 003x131001/20-1/20 x55/3001/31/21-24x71/300-1/3 1/601/2cjzj000-3/2 0-1/24x700010即新解为即新解为Tx)3/1,3/4,3(表表7 7d d）

16、将其加到最终单纯形表上得表（将其加到最终单纯形表上得表（8 8）03/12123003/43/142 3/203/13/42123103/13/20111003/23/1003/13/221/2pBpcj320000cBxBbx1x2x3x4x5x62x24/3012/3-1/3 003x110/3 10-1/3 2/3000 x5300-11100 x62/300-2/3 1/301cjzj00-1/3-4/3 004X24/31/302/31/3表表8 8因因x x2 2已变化为已变化为x x/2 2，故用单纯形法算法将，故用单纯形法算法将x x/2 2替换出基变替换出基变量中的量中的x

17、x2 2，并在下一个表中不再保留，并在下一个表中不再保留x x2 2，得表（，得表（9 9）cj320000cBxBbx1X2x3x4x5x64X21011/2-1/4 003x1310-1/2 3/4000 x5300-11100 x6000-11/201cjzj00-1/2-5/4 00表表9 9此时已经达到最优，新解为此时已经达到最优，新解为Tx)1,3(e)e)此时将原来的最优解带入约束，发现满足，所以此时将原来的最优解带入约束，发现满足，所以最优解不变。最优解不变。运输问题运输问题1 1，试求下表给出的产销不平衡问题的最优解。，试求下表给出的产销不平衡问题的最优解。B1B2B3B4产

18、量A137645A224322A343856销量3322产地销地解：用最小元素法求得初始方案如下解：用最小元素法求得初始方案如下B1B2B3B4B5A123A220A3132产地销地用位势法求检验数知用位势法求检验数知0135 找到闭回路，调整得找到闭回路，调整得B1B2B3B4B5A132A220A3321又用位势法求检验数知又用位势法求检验数知0114 找到闭回路，调整得找到闭回路，调整得B1B2B3B4B5A1320A220A333又用位势法求检验数知所有的检验数都非负，达又用位势法求检验数知所有的检验数都非负，达到最优到最优z=32z=32。2 2，某市有三个面粉厂，他们供给三个面食加

19、工厂所，某市有三个面粉厂，他们供给三个面食加工厂所需的面粉。各面粉厂的产量、面食加工厂加工面粉需的面粉。各面粉厂的产量、面食加工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价的能力、各面食加工厂和各面粉厂之间的单位运价见下表。假定在第见下表。假定在第1 1，2 2，3 3面食加工厂制作单位面面食加工厂制作单位面粉食品的利润分别为粉食品的利润分别为1212元，元，1616元，元，1111元，试确定使元，试确定使总效益最大的面粉分配计划（假定面粉厂和面食加总效益最大的面粉分配计划（假定面粉厂和面食加工厂都属于同一个主管单位）工厂都属于同一个主管单位）123面粉厂产量A310220C4118

20、30B811420食品厂需要量152520食品厂食品厂面粉厂面粉厂解：解：从题意很容易知道，总效益最大实际上是食品利润减去单从题意很容易知道，总效益最大实际上是食品利润减去单位运价之后再求的总效益。再因为面粉的总产量为位运价之后再求的总效益。再因为面粉的总产量为7070，比食，比食品厂的总需求量品厂的总需求量6060多了多了1010个单位，可以认为，多的个单位，可以认为，多的1010个单位个单位最后还是会分配给最后还是会分配给1 13 3个食品厂，所以就需要增加一个虚拟个食品厂，所以就需要增加一个虚拟的食品厂的食品厂4 4。设设xijxij第第i i个面粉厂运到第个面粉厂运到第j j个食品厂的

21、运量，个食品厂的运量，i=1,2,3;j=1,2,3,4i=1,2,3;j=1,2,3,4得下表：得下表：1234面粉厂产量A969920C853830B457720食品厂需要量15252010为使用求解运输问题的表上作业法，用上表中的最大为使用求解运输问题的表上作业法，用上表中的最大数减去其他各数，得下表数减去其他各数，得下表1234面粉厂产量A030020C146130B542220食品厂需要量15252010使用表上作业法，得最优解使用表上作业法，得最优解.整数规划整数规划1 1，分配甲、乙、丙、丁四个人完成，分配甲、乙、丙、丁四个人完成ABCDEABCDE五项任五项任务，每个人完成各项

22、任务的时间如表所示：务，每个人完成各项任务的时间如表所示：ABCDE甲2529314237乙乙3938262 033丙丙3427284 032丁丁2442362345由于任务多于人数，故考虑由于任务多于人数，故考虑：（a a）任务）任务E E必须完成，其他各项可任意选必须完成，其他各项可任意选3 3项完成；项完成；（b b）其中有一人完成）其中有一人完成2 2项，其他每人完成一项。项，其他每人完成一项。分别确定最优方案，使完成任务总时间最少分别确定最优方案，使完成任务总时间最少解解（a a）增加一个虚拟的人，由题目要求，其对应）增加一个虚拟的人，由题目要求，其对应的效率如下的效率如下 M000

23、04523364224324028273433202638393742312925 M000022013191513107130618191217640 M0000160131910131077061819717640 M1000150121800141076051718718640 M5004150810001910132011318318200Z=105Z=105解解（b b）增加一个虚拟的人，由题目要求，其对应）增加一个虚拟的人，由题目要求，其对应的效率如下的效率如下 32202627244523364224324028273433202638393742312925 705741701

24、21910130078051819717540 60463160111800140077041718718540 20023120714001800113001318318100最优方案：甲最优方案：甲B B，乙，乙C C，D D，丙，丙E E，丁，丁A A，Z=131Z=1312 2，用割平面法求解，用割平面法求解 取整,0,205462max21212121xxxxxxxxzcj1100cBxBbx1x2x3x41x15/3105/6-1/31x28/301-2/31/3 cj-zj00-1/6-1/6单纯形迭代得最终单纯形表单纯形迭代得最终单纯形表写出第一行的约束写出第一行的约束3213

25、165431 xxx将上式中所有常数写成正数和一个正分数之和将上式中所有常数写成正数和一个正分数之和321)321(65431 xxx分数项移到右边，整数项移到左边分数项移到右边，整数项移到左边43413265321xxxx 由于左边为整数，所以右边也为整数，所以由于左边为整数，所以右边也为整数，所以0,043 xx所以所以由于由于加入松弛变量加入松弛变量放入单纯形表放入单纯形表3232653243 xx032653243 xx0326532543 xxxcj1100cBxBbx1x2x3x41x15/3105/6-1/61x28/301-2/31/30 x5-2/300-5/61/6 cj-

26、zj00-1/6-1/600 x5001对偶单纯形法继续迭代，得对偶单纯形法继续迭代，得cj1100cBxBbx1x2x3x41x1110001x216/50101/50 x34/5001-1/5 cj-zj000-1/5-1/50 x51-4/5-6/5写出第二行的约束写出第二行的约束5135451542 xxx将上式中所有常数写成正数和一个正分数之和将上式中所有常数写成正数和一个正分数之和分数项移到右边，整数项移到左边分数项移到右边，整数项移到左边513)511(51542 xxx54525151513xxxx 第第53页页v53v可编辑可编辑由于左边为整数，所以右边也为整数，所以由于左边

27、为整数，所以右边也为整数，所以0,054 xx所以所以由于由于加入松弛变量加入松弛变量放入单纯形表放入单纯形表5151515154 xx051515154 xx0515151654 xxxcj1100cBxBbx1x2x3x41x1110001x216/50101/50 x34/5001-1/5 cj-zj000-1/5-1/500 x51-4/5-6/50 x60000 x6-1/5000-1/5-1/51cj1100cBxBbx1x2x3x41x1110001x2301000 x310010 cj-zj00000-10 x51-1-10 x601-10 x4100011-5达到最优，达到最

28、优，Tx)3,1(还可以得到另一个最优解：。还可以得到另一个最优解：。Tx)4,0(目标规划目标规划1 1，已知目标规划问题，已知目标规划问题 0,2 429262)35(min21442332121214433212211121iiddxxddxddxxddxxddxxdPddPdPdPz用图解法求解最优解。用图解法求解最优解。6221 xx9221 xx4221 xx22 x 最优解最优解2 2，某工厂生产，某工厂生产A,SA,S两种型号的微型计算机，他们两种型号的微型计算机，他们都需要经过两道工序，每台计算机所需的加工都需要经过两道工序，每台计算机所需的加工时间、销售利润及该厂每周最大的

29、加工能力如时间、销售利润及该厂每周最大的加工能力如下表：下表：AS周最大加工能力工序1（h/台）46150h工序2（h/台）3275h利润（元/台）300450工厂经营目标的各优先级如下：工厂经营目标的各优先级如下：P1P1：每周总利润不低于：每周总利润不低于1000010000元；元；P2P2：合同要求：合同要求A A型机每周至少生产型机每周至少生产1010台，台，S S型机至型机至少少1515台；台；P3P3：工序：工序1 1每周生成时间最好恰为每周生成时间最好恰为150h,150h,工序工序2 2生生成时间可适当超过其能力；成时间可适当超过其能力；试写出目标规划的模型。试写出目标规划的模

30、型。0,7566 15064151010000450300)()(min21552144212121544332133221121iiddxxddxxddxxddxddxddxxdddPddPdPz解：设生产解：设生产A A，S S机器分别为机器分别为x1,x2x1,x2台，则有台，则有3 3，查找参考书，参阅较复杂问题的模型，查找参考书，参阅较复杂问题的模型图论图论1 1，用避圈法或破圈法求下图的最小树，用避圈法或破圈法求下图的最小树1v2v5v7v8v6v3v4v9v6455447762938131v2v5v7v8v6v3v4v9v645544776293813或选取或选取 去掉去掉),(

31、51vv),(71vv解答：解答：2 2，下图中，下图中 是仓库，是仓库，是商店，求一条是商店，求一条 到到 的最短路的最短路0v1v3v5v7v8v6v9v4v2v2221111117744433366655990v9v0v9v0v1v3v5v7v8v6v9v4v2v222111111774443336665599)0()2()4()7()11()11()13()13()16()19(最优方案可以有几种：最优方案可以有几种：9210,1vvvv94210,2vvvvv9230,3vvvv94230,4vvvvv9430,5vvvv9870,6vvvv3 3，用标号算法求下图的最大流，用标号算

32、法求下图的最大流sv2v4v1v5vTv3v)5(5)3(3)2(3)4(6)0(2)4(5)2(2)4(4)6(6)6(8)3(3)0(2sv2v4v1v5vTv3v)5(5)3(3)2(3)4(6)0(2)4(5)2(2)4(4)6(6)6(8)3(3)0(2),(,1 ssvv)2,(,22svv)1,(,323vv)1,(,434vv)1,(,541vv)1,(,615vv)1,(,75vvTsv2v4v1v5vTv3v)5(5)3(3)2(3)4(6)0(2)4(5)2(2)4(4)6(6)6(8)3(3)0(2得增广链如右图中红色部得增广链如右图中红色部分，调整后得新图如下：分，调

33、整后得新图如下：sv2v4v1v5vTv3v)5(5)3(3)3(3)5(6)0(2)5(5)1(2)4(4)6(6)7(8)2(3)0(2再次标号知：没有增广链存在，故达到最大流。最再次标号知：没有增广链存在，故达到最大流。最大流量为大流量为13134 4，求下图中流值为，求下图中流值为6 6的最小费用流，其中弧旁边的最小费用流，其中弧旁边的数字为的数字为 ,表示容量，表示容量，表示单位流量费用。表示单位流量费用。svTv2v1v3v4v)2,3()3,3()1,3()3,4()1,4()1,7()5,6()4,5(),(ijijdcijcijdsvTv2v1v3v4v)2()3()1()3

34、()1()1()5()4(解：以解：以0 0作为初始流量，得长度网络作为初始流量，得长度网络最短路：最短路：Tsvvvv43调整流量，得新的流量网络调整流量，得新的流量网络svTv2v1v3v4v03303000对新的流量网络，得到长度网络对新的流量网络，得到长度网络svTv2v1v3v4v)2()3()1()3()1()1()5()4()1(最短路：最短路：Tsvvvv23调整流量，得新的流量网络调整流量，得新的流量网络svTv2v1v3v4v03304101对新的流量网络，得到长度网络对新的流量网络，得到长度网络svTv2v1v3v4v)2()3()1()3()1()5()4()1()4(

35、)1(最短路：最短路：Tsvvvvvv2341调整流量，得新的流量网络调整流量，得新的流量网络svTv2v1v3v4v21324303 PERT PERT图图 与与关键路线法关键路线法1 1，下表给出一个汽车库及引道的施工计划：，下表给出一个汽车库及引道的施工计划：作业编号作业内容作业时间（天）紧前作业1清理场地准备施工10无2备料8无3车库地面施工61，24墙及房顶 架预制1625车库混凝土地面保养2436竖立墙架44，57竖立房顶 架468装窗及边墙1069装门4610装天花板12711油漆168，9，1012引道混凝土施工8313引道混凝土保养241214清理场地交工验收411，13请解

36、答请解答（1 1）该工程从施工开始道工程结束的最）该工程从施工开始道工程结束的最短周期；（短周期；（2 2）如果引道混凝土施工工期拖延）如果引道混凝土施工工期拖延1010天，对整个工程进度有何影响？（天，对整个工程进度有何影响？（3 3）若装）若装天花板的施工时间从天花板的施工时间从1212天缩短为天缩短为8 8天，对整个天，对整个工程进度有何影响？（工程进度有何影响？（4 4）为保证工期不拖延，）为保证工期不拖延，装门这项作业最晚应从哪一天开工？（装门这项作业最晚应从哪一天开工？（5 5）如）如果要求该工程必须在果要求该工程必须在7575天内完工，是否应采取天内完工，是否应采取措施，应采取什

37、么措施？措施，应采取什么措施？0401004102400416241234587101194644A160616841213B16CELIGFHJNMDK82412001002844444860247680807660525056484440164410解：作业编号分别对应A,B,C,D,E,F,G,H,I,J,K,L,M,N，PERT 图如下第第81页页（1 1）该工程从施工开始道工程结束的最短周期为）该工程从施工开始道工程结束的最短周期为8080天天可计算出自由时差和总时差可计算出自由时差和总时差若使用公式：若使用公式：),(),(),(jitjitjiRESLS ),(),(),(min

38、),(jitjitkjtjiFESESk 0401004102400416241234587101194644A160616841213B16CELIGFHJNMDK82412001002844444860247680807660525056484440164410002160280126000280)0()0()0()16()0()0()0()12()0()0()6()0()28()0(*表示总时差表示总时差(*)表示自由时差表示自由时差如此可找到关键路线：如此可找到关键路线：A-C-E-F-G-J-K-NA-C-E-F-G-J-K-N（2 2）如果引道混凝土施工）如果引道混凝土施工(L)(

39、L)工期拖延工期拖延1010天，由于此工序天，由于此工序有总时差有总时差2828，所以它的工期拖延，所以它的工期拖延1010天，对整个工程进度天，对整个工程进度无影响。无影响。（3 3）若装天花板（）若装天花板（J J）的施工时间从）的施工时间从1212天缩短为天缩短为8 8天，天，观察它的平行工序观察它的平行工序H H，I I，发现关键路线不会改变，所，发现关键路线不会改变，所以整个工程进度也缩短以整个工程进度也缩短4 4天。天。（4 4）为保证工期不拖延，装门（）为保证工期不拖延，装门（I I）这项作业最）这项作业最晚应从第晚应从第5656天开工天开工（5 5）如果要求该工程必须在）如果要

40、求该工程必须在7575天内完工，在合适的关天内完工，在合适的关键工序上压缩键工序上压缩5 5天工期。天工期。动态规划动态规划1.1.设有设有6 6万元资金用于四个工厂的扩建。已知每个工厂万元资金用于四个工厂的扩建。已知每个工厂的利润增长额同投资数的大小有关，数据见表。如何的利润增长额同投资数的大小有关，数据见表。如何确定对四个工厂的投资数，使得总利润增长额最大。确定对四个工厂的投资数，使得总利润增长额最大。010020030040050060010204260758590202545576570733018396178909540284765748085利润增长额利润增长额工厂工厂投资投资1.

41、1.解：解：设设sksk表示第表示第k k个工厂到第个工厂到第4 4个工厂的投资数。个工厂的投资数。XkXk表示第表示第k k个工厂的投资数个工厂的投资数,则第则第4 4个阶段如下：个阶段如下：fX*01002003004005006000000100282810020047472003006565300400747440050080805006008585600fX*010020030040050060000001002818280200474639470300656567616720040074838689788930050080921041081069010830060085981131

42、2612511895126300第第3 3个阶段：个阶段：fX*0100 200 300400 500 6000000100 2825280200 47534553100300 6772735773200400 899292856592100，200500 108 114 112 1049370114 100600 126 133 134 124112 9873134 200第第2 2个阶段：个阶段：fX*0100 200 300400 500 600600 134 134 134 133128 113 901340，100，200第第1 1个阶段：个阶段：最优方案：最优方案：1 1，0 0，

43、200200，300300，1001002 2，100100，100100，300300，1001003 3，200200，100100，200200，1001004 4，200200，200200，0 0，2002002.2.用动态规划解以下静态问题：用动态规划解以下静态问题：0,93102567max21212122121xxxxxxxxxz解：令解：令k=2,k=2,状态变量：状态变量：k k阶段初各约束条件右端项的剩余值阶段初各约束条件右端项的剩余值R R1k1k,R,R2k2k决策变量：决策变量：x x1 1,x,x2 2，状态转移方程为：状态转移方程为：11212211111291

44、0 xxRRxxRR2122223,0max22122)2(55max),(12222RxRRfRxR 令令k=1,k=1,由于由于k=2k=2时时,21021122xRx 而由第而由第2 2个约束知，个约束知，54821039391111 xxxx所以所以92.7021251943312519433max)210(567max)2(567max)(5481211215480211215480212121548,10min0111111 xxxxxxxxxxxRxxsf此时此时,x,x2 2=0.5=0.5 决策分析决策分析1,1,某钟表公司计划通过它的销售网销售一种低价某钟表公司计划通过它的

45、销售网销售一种低价钟表，计划每块售价钟表，计划每块售价1010元。生产这种钟表有元。生产这种钟表有3 3个个设计方案：方案设计方案：方案1 1需一次投资需一次投资1010万元，以后生产万元，以后生产一个的费用为一个的费用为5 5元，方案元，方案2 2需一次投资需一次投资1616万元，万元，以后生产一个的费用为以后生产一个的费用为4 4元；方案元；方案3 3需一次投资需一次投资2525万元，以后生产一个的费用为万元，以后生产一个的费用为3 3元。对该种钟元。对该种钟表的需求量为未知，但估计有三种可能：表的需求量为未知，但估计有三种可能：E1E13000030000；E2E212000012000

46、0；E3E3200000200000a)a)建立这个问题的收益矩阵；建立这个问题的收益矩阵；b)b)分别用悲观主义、分别用悲观主义、乐观主义和等可能性决策准则决定该公司应采乐观主义和等可能性决策准则决定该公司应采用哪一个设计方案；用哪一个设计方案；c)c)建立机会损失矩阵，并建立机会损失矩阵，并用最小机会损失决策准则决定采取哪一个设计用最小机会损失决策准则决定采取哪一个设计方案。方案。E1E2E3A155090A2256104A3-459115收益矩阵（单位：万）：收益矩阵（单位：万）：E1E2E3A1550909A2256104104A3-459115115乐观准则：乐观准则：选选A3A3E

47、1E2E3A1550909A2256104104A3-459115115悲观准则：悲观准则：选选A1A1E1E2E3A1092525A2231111A39009机会损失矩阵（单位：万）：机会损失矩阵（单位：万）：选选A3A32 2，某工程队承担一个桥梁的施工任务，由于该地区，某工程队承担一个桥梁的施工任务，由于该地区夏季多雨，有三个月时间不能施工。在不施工期内，夏季多雨，有三个月时间不能施工。在不施工期内，该工程队可将施工机械搬走或留在原处。假如搬走，该工程队可将施工机械搬走或留在原处。假如搬走，需华搬迁费需华搬迁费18001800元，若留在原处，一种方案是花元，若留在原处，一种方案是花500

48、500元筑一护堤，防止河水上涨发生高水位侵袭；元筑一护堤，防止河水上涨发生高水位侵袭；若不筑护堤，发生高水位侵袭时将损失若不筑护堤，发生高水位侵袭时将损失1000010000元。元。又若下暴雨发生洪水，则不管是否修护堤，施工机又若下暴雨发生洪水，则不管是否修护堤，施工机械留在原处都将受到械留在原处都将受到6000060000元的损失。如果预测在元的损失。如果预测在这三个月中，高水位的发生率为这三个月中，高水位的发生率为25%,25%,洪水的发生率洪水的发生率为为2%,2%,试依据决策树的方法分析该施工队要不要把试依据决策树的方法分析该施工队要不要把施工机械搬走及要不要修筑护堤。施工机械搬走及要

49、不要修筑护堤。000060000 10000 60000 高水位洪水其他高水位洪水其他筑堤筑不搬不搬25.002.073.073.002.025.01200 3700 1700 1800 500 3 3，某公司经理的决策效用函数如下：，某公司经理的决策效用函数如下：U(-10000)=-U(-10000)=-800,U(-200)=-2,U(-100)=-1,U(0)=0,800,U(-200)=-2,U(-100)=-1,U(0)=0,U(10000)=250,U(10000)=250,他需要决定是否为该公司的财产报他需要决定是否为该公司的财产报火险。据大量统计资料，一年内可能发生火灾的概火

50、险。据大量统计资料，一年内可能发生火灾的概率为率为0.00150.0015，问他是否愿意每年支付，问他是否愿意每年支付100100元保元保1000010000元财产的潜在火灾损失。元财产的潜在火灾损失。00保不保1 2.1 0015.09985.010000 800 发生火灾不发发生火发生火灾不发生火灾0015.09985.0100 100 1 1 MU第第103页页排队论排队论第第104页页1.1.汽车按照平均汽车按照平均9090辆辆/h/h的的PoissonPoisson流到达高速公路的流到达高速公路的一个收费关卡，通过关卡的时间是一个收费关卡，通过关卡的时间是3838秒。由于驾驶人秒。由