运筹学例题及答案

1、运运 筹 筹 帷 帷 幄 幄 之 之 中 中 决决 胜 胜 千 千 里 里 之 之 外 外 作业及答案作业及答案 1。用单纯形法解。用单纯形法解lp问题问题 0, 44 222 . 326max 321 31 321 321 xxx xx xxx ts xxxz 线性规划线性规划 cj6-2300 cbxbbx1x2x3x4x5 0 x422-1210 0 x5410401 cj - zj6-2300 6x111-1/211/20 0 x5301/23-1/21 cj - zj01-3-30 6x1410401 -2x26016-12 cj - zj00-9-2-2 cj6-2300 cbxb

2、bx1x2x3x4x5 达到最优解，且最优解唯一达到最优解，且最优解唯一 2。用大。用大m或两阶段法解或两阶段法解lp问题问题 0, 02 22 6 . 22max 321 32 31 321 321 xxx xx xx xxx ts xxxz cj2-12000-m-m-m cbxbbx1x2x3x4x5x6x7x8x9 -mx76111-100100 -mx82-2010-10010 -mx9002-100-1001 cj-zj 2-m3m-1m+2 -m-m-m000 -mx76103/2-101/210 -1/2 -mx82-2010-10010 -1x2001 -1/2 00 -1/

3、2 001/2 cj-zj 2-m05/2m +3/2 -m-m 1/2m- 1/2 00 - 3/2m +1/2 cj2-12000-m-m-m cbxbbx1x2x3x4x5x6x7x8x9 -mx73400-13/21/21 -3/2-1/2 2x32-201000010 -1x21-1100 -1/2-1/2 01/21 cj-zj 5+4m00 -m 3/2m +3/2 1/2m- 1/2 0 -5/2m- 3/2 - 3/2m+ 1/2 2x13/4100 -1/4 3/81/81/4 -3/8-1/8 2x37/2001 -1/2-1/4 1/41/21/4 -1/4 -1x27

4、/401 0 -1/4-1/8-3/8 1/81/83/8 cj-zj 000 5/4 - 无界解无界解 3，某厂在今后四个月内需租用仓库堆放物资。已知各月份需某厂在今后四个月内需租用仓库堆放物资。已知各月份需 租用仓库面积见表，仓库租借费用随合同期不同而不同，期租用仓库面积见表，仓库租借费用随合同期不同而不同，期 限越长折扣越大，具体数字见表。租借合同每个月月初都可限越长折扣越大，具体数字见表。租借合同每个月月初都可 办理，合同规定具体的租借面积和月数，因此该厂可根据需办理，合同规定具体的租借面积和月数，因此该厂可根据需 要，在任何一个月月初办理合同，每次办理可签一份或多份，要，在任何一个月

5、月初办理合同，每次办理可签一份或多份， 总目标是总的租借费用最低，请建立数学模型并用软件给出总目标是总的租借费用最低，请建立数学模型并用软件给出 结果。结果。 月份1234 所需仓库面 积（100m2） 15102012 合同租借 期限 1个月2个月3个月4个月 租借费用 2800450060007300 解解:设一月初签订合同期限为一个月，两个月，三个设一月初签订合同期限为一个月，两个月，三个 月，四个月的仓库面积分别为月，四个月的仓库面积分别为 ， ， ， ，二月，二月 初签订合同期限为一个月，两个月，三个月的仓库初签订合同期限为一个月，两个月，三个月的仓库 面积分别为面积分别为 ，三月初

6、签订合同期限为一，三月初签订合同期限为一 个月，两个月的仓库面积分别为个月，两个月的仓库面积分别为 ，四月初签，四月初签 订合同期限为一个月的仓库面积为订合同期限为一个月的仓库面积为 。 则则 11 x 12 x 13 x 14 x 232221 ,xxx 3231, x x 41 x 142313 32221241312111 7300)(6000 )(4500)(2800min xxx xxxxxxxz 0 12 20 10 15 41322314 323123221413 232221141312 14131211 ij x xxxx xxxxxx xxxxxx xxxx 计算结果如下计

7、算结果如下 4，某厂生产，某厂生产i,ii,iii三种产品，都分别经过三种产品，都分别经过a,b两道工两道工 序加工。设序加工。设a工序可分别在设备工序可分别在设备a1或或a2上完成，有上完成，有 b1，b2，b3三种设备可用于完成三种设备可用于完成b工序。已知产品工序。已知产品 i可在可在a,b任何一种设备上加工；产品任何一种设备上加工；产品ii可在任何规可在任何规 格的格的a设备上加工，但完成设备上加工，但完成b工序时，只能在工序时，只能在b1设设 备上加工；产品备上加工；产品iii只能在只能在a2和和b2设备上加工。加设备上加工。加 工单位产品所需的工序时间及其它各项数据见表，工单位产品

8、所需的工序时间及其它各项数据见表， 试安排最优生成计划，使该厂获利最大。试安排最优生成计划，使该厂获利最大。 设备 产品 i ii iii 设备有效设备有效 台时台时 设备加工费设备加工费 （元（元/h） a15 10 60000.05 a27 9 12100000.03 b16 840000.06 b24 1170000.11 b3740000.05 原料费（元原料费（元/ 件）件） 售价（元售价（元/件）件） 0.25 0.35 0.50 1.25 2.00 2.80 解：设第解：设第种产品中，分别在种产品中，分别在 上加工的数量依次为上加工的数量依次为 ，第，第种种 产品中分别在产品中分

9、别在a1,b1和和a2,b1 上加工的数量为上加工的数量为 生产生产种产品数量为种产品数量为 。 3 , 2 , 1),(),( 21 jbaba jj 654321 ,;,xxxxxx 87,x x 9 x 0 4000)(7 700011)(4 4000)(8)(6 10000129)(7 600010)(5 )(705. 011)(411. 0)(8 )(606. 0129)(703. 010)(505. 0 )5 . 08 . 2()(35. 02()(25. 025. 1(max 63 952 8741 98654 7321 6395287 41986547321 987654321

10、 j x xx xxx xxxx xxxxx xxxx xxxxxxx xxxxxxxxxxx xxxxxxxxxz 对偶理论对偶理论 1. 已知线性规划问题：已知线性规划问题： 0, 9 6 6 2 83 . 42max 4321 321 432 21 421 4321 xxxx xxx xxx xx xxx ts xxxxz 要求要求：a)写出对偶问题，写出对偶问题，b)已知原问题最有解已知原问题最有解 x*=(2,2,4,0),用互补松弛性求出对偶问题的用互补松弛性求出对偶问题的 最优解。最优解。 解：对偶问题：解：对偶问题： 0, 1 1 4 3 22 . 9668min 4321 3

11、1 43 4321 421 4321 yyyy yy yy yyyy yyy ts yyyyw 将原问题的最优解带入约束，发现第将原问题的最优解带入约束，发现第4个约束为严格个约束为严格 不等式，所以，得不等式，所以，得y4*=0 又因为，原问题最优解的前三个分量都大于又因为，原问题最优解的前三个分量都大于0，所以，所以， 有如下三个等式成立。有如下三个等式成立。 1 4 3 22 3 321 21 y yyy yy 解方程组得对偶问题的最优解为解方程组得对偶问题的最优解为y*=(4/5,3/5,1,0) 2。已知线性规划问题。已知线性规划问题 0, 2 1 8 2 62 . 23max 21

12、 2 21 21 21 21 xx x xx xx xx ts xxz 及最终单纯形表及最终单纯形表 cj320000 cbxbbx1x2x3x4x5x6 2x24/3012/3-1/3 00 3x110/3 10-1/3 2/300 0 x5300-1110 0 x62/300-2/3 1/301 cjzj 00-1/3 -4/3 00 表表1 分析下列各种条件单独变化时，最优解将如何变化。分析下列各种条件单独变化时，最优解将如何变化。 （a）第）第1，2个约束条件的后端项分别由个约束条件的后端项分别由6变变7，8变变4； （b）目标函数变为）目标函数变为 ; （c） 增加一个变量增加一个变

13、量 ，系数为，系数为 （d）问题中变量）问题中变量 的系数变为的系数变为 （e）增加一个新的约束）增加一个新的约束 21 52maxxxz 3 x t pc)2 , 3 , 2 , 1(, 4 33 2 x t )2 , 1 , 2 , 3 , 4( 4 1 x 解：解：a） 0 0 4 1 b 2 5 3 2 0 0 4 1 103/13/2 0111 003/23/1 003/13/2 b 将其加到表（将其加到表（1）的最终单纯形表的基变量）的最终单纯形表的基变量b这一列数这一列数 字上得表（字上得表（2） （表（表2） 表（表（2）中原问题为非可行解，故用对偶单纯形法继续）中原问题为非可

14、行解，故用对偶单纯形法继续 计算得表（计算得表（3） cj320000 cbxbbx1x2x3x4x5x6 2x210/3 012/3-1/3 00 3x11/310-1/3 2/300 0 x5-200-1110 0 x6-4/3 00-2/3 1/301 cjzj 00-1/3 -4/3 00 （表（表3） cj320000 cbxbbx1x2x3x4x5x6 2x220101/32/30 3x111001/3-1/3 0 0 x32001-1-10 0 x60000-1/3 -2/3 1 cjzj 000-5/3 -1/3 0 即新解为即新解为 t x)0 , 0 , 0 , 2 , 2

15、 , 1( 第第25页页 b) 将将cj的改变反应到最终单纯形表上的改变反应到最终单纯形表上,得表（得表（4） cj250000 cbxbbx1x2x3x4x5x6 5x24/3012/3-1/3 00 2x110/3 10-1/3 2/300 0 x5300-1110 0 x62/300-2/3 1/301 cjzj 00-8/3 1/300 继续迭代继续迭代,得表（得表（5） cj250000 cbxbbx1x2x3x4x5x6 5x22010001 2x1210100-2 0 x5100101-3 0 x4200-2103 cjzj 00-200-1 表表5 即新解为即新解为 t x)2

16、 , 2( c） 将其加到最终单纯形表上得表（将其加到最终单纯形表上得表（6） 01 2 3 2 1 003/43/14 7 2 4 1 0 2 3 2 1 103/13/2 0111 003/23/1 003/13/2 7 1 / 7 pbp cj320000 cbxbbx1x2x3x4x5x6 2x24/3012/3-1/3 00 3x110/3 10-1/3 2/300 0 x5300-1110 0 x62/300-2/3 1/301 cjzj 00-1/3 -4/3 00 4 x7 0 1 4 2 1 继续迭代继续迭代,得表（得表（7） 表表6 cj320000 cbxbbx1x2x3

17、x4x5x6 2x24/3012/3-1/3 00 3x131001/20-1/2 0 x55/3001/31/21-2 4x71/300-1/3 1/601/2 cjzj 000-3/2 0-1/2 4 x7 0 0 0 1 0 即新解为即新解为 t x)3/1 , 3/4 , 3( 表表7 d） 将其加到最终单纯形表上得表（将其加到最终单纯形表上得表（8） 03/1 2 1 2 3 003/43/14 2 3/2 0 3/1 3/4 2 1 2 3 103/13/2 0111 003/23/1 003/13/2 2 1 / 2 pbp cj320000 cbxbbx1x2x3x4x5x6

18、2x24/3012/3-1/3 00 3x110/3 10-1/3 2/300 0 x5300-1110 0 x62/300-2/3 1/301 cjzj 00-1/3 -4/3 00 4 x2 4/3 1/3 0 2/3 1/3 表表8 因因x2已变化为已变化为x/2，故用单纯形法算法将，故用单纯形法算法将x/2替换出基变替换出基变 量中的量中的x2，并在下一个表中不再保留，并在下一个表中不再保留x2，得表（，得表（9） cj320000 cbxbbx1x2x3x4x5x6 4x21011/2-1/4 00 3x1310-1/2 3/400 0 x5300-1110 0 x6000-11/2

19、01 cjzj 00-1/2 -5/4 00 表表9 此时已经达到最优，新解为此时已经达到最优，新解为 t x)1 , 3( e) 此时将原来的最优解带入约束，发现满足，所以此时将原来的最优解带入约束，发现满足，所以 最优解不变。最优解不变。 运输问题运输问题 1，试求下表给出的产销不平衡问题的最优解。，试求下表给出的产销不平衡问题的最优解。 b1b2b3b4产量 a137645 a224322 a343856 销量3322 产地 销地 解：用最小元素法求得初始方案如下解：用最小元素法求得初始方案如下 b1b2b3b4b5 a123 a220 a3132 产地 销地 用位势法求检验数知用位势法

20、求检验数知 01 35 找到闭回路，调整得找到闭回路，调整得 b1b2b3b4b5 a132 a220 a3321 又用位势法求检验数知又用位势法求检验数知01 14 找到闭回路，调整得找到闭回路，调整得 b1b2b3b4b5 a1320 a220 a333 又用位势法求检验数知所有的检验数都非负，达又用位势法求检验数知所有的检验数都非负，达 到最优到最优z=32。 2，某市有三个面粉厂，他们供给三个面食加工厂所，某市有三个面粉厂，他们供给三个面食加工厂所 需的面粉。各面粉厂的产量、面食加工厂加工面粉需的面粉。各面粉厂的产量、面食加工厂加工面粉 的能力、各面食加工厂和各面粉厂之间的单位运价的能

21、力、各面食加工厂和各面粉厂之间的单位运价 见下表。假定在第见下表。假定在第1，2，3面食加工厂制作单位面粉面食加工厂制作单位面粉 食品的利润分别为食品的利润分别为12元，元，16元，元，11元，试确定使总元，试确定使总 效益最大的面粉分配计划（假定面粉厂和面食加工效益最大的面粉分配计划（假定面粉厂和面食加工 厂都属于同一个主管单位）厂都属于同一个主管单位） 123 面粉厂产量 a310220 c411830 b811420 食品厂需要量 152520 食品厂食品厂 面粉厂面粉厂 解：解：从题意很容易知道，总效益最大实际上是食品利润减去单从题意很容易知道，总效益最大实际上是食品利润减去单 位运价

22、之后再求的总效益。再因为面粉的总产量为位运价之后再求的总效益。再因为面粉的总产量为70，比食，比食 品厂的总需求量品厂的总需求量60多了多了10个单位，可以认为，多的个单位，可以认为，多的10个单位个单位 最后还是会分配给最后还是会分配给13个食品厂，所以就需要增加一个虚拟个食品厂，所以就需要增加一个虚拟 的食品厂的食品厂4。 设设xij第第i个面粉厂运到第个面粉厂运到第j个食品厂的运量，个食品厂的运量，i=1,2,3;j=1,2,3,4 得下表：得下表： 1234 面粉厂产量 a969920 c853830 b457720 食品厂需要量 15252010 为使用求解运输问题的表上作业法，用上

23、表中的最大为使用求解运输问题的表上作业法，用上表中的最大 数减去其他各数，得下表数减去其他各数，得下表 1234 面粉厂产量 a030020 c146130 b542220 食品厂需要量 15252010 使用表上作业法，得最优解使用表上作业法，得最优解. 整数规划整数规划 1，分配甲、乙、丙、丁四个人完成，分配甲、乙、丙、丁四个人完成abcde五项五项 任务，每个人完成各项任务的时间如表所示：任务，每个人完成各项任务的时间如表所示： abcde 甲2529314237 乙乙3938262 033 丙丙3427284 032 丁丁2442362345 由于任务多于人数，故考虑由于任务多于人数，

24、故考虑： （a）任务）任务e必须完成，其他各项可任意选必须完成，其他各项可任意选3项完成；项完成； （b）其中有一人完成）其中有一人完成2项，其他每人完成一项。项，其他每人完成一项。 分别确定最优方案，使完成任务总时间最少分别确定最优方案，使完成任务总时间最少 解解（a）增加一个虚拟的人，由题目要求，其对应）增加一个虚拟的人，由题目要求，其对应 的效率如下的效率如下 m0000 4523364224 3240282734 3320263839 3742312925 m0000 22013191 513107 13061819 1217640 m0000 16013191 013107 7061

25、819 717640 m1000 15012180 014107 6051718 718640 m5004 1508100 0191013 2011318 318200 z=105 解解（b）增加一个虚拟的人，由题目要求，其对应）增加一个虚拟的人，由题目要求，其对应 的效率如下的效率如下 3220262724 4523364224 3240282734 3320263839 3742312925 70574 17012191 013007 8051819 717540 60463 16011180 014007 7041718 718540 20023 1207140 0180011 3001

26、318 318100 最优方案：甲最优方案：甲b，乙，乙c， d，丙，丙e，丁，丁a， z=131 2，用割平面法求解，用割平面法求解 取整, 0, 2054 62 max 21 21 21 21 xx xx xx xxz cj1100 cbxbbx1x2x3x4 1x15/3105/6-1/3 1x28/301-2/31/3 cj - zj00-1/6-1/6 单纯形迭代得最终单纯形表单纯形迭代得最终单纯形表 写出第一行的约束写出第一行的约束 3 2 1 3 1 6 5 431 xxx 将上式中所有常数写成正数和一个正分数之和将上式中所有常数写成正数和一个正分数之和 3 2 1) 3 2 1

27、( 6 5 431 xxx 分数项移到右边，整数项移到左边分数项移到右边，整数项移到左边 4341 3 2 6 5 3 2 1xxxx 由于左边为整数，所以右边也为整数，所以由于左边为整数，所以右边也为整数，所以 0, 0 43 xx所以所以由于由于 加入松弛变量加入松弛变量 放入单纯形表放入单纯形表 3 2 3 2 6 5 3 2 43 xx 0 3 2 6 5 3 2 43 xx 0 3 2 6 5 3 2 543 xxx cj1100 cbxbbx1x2x3x4 1x15/3105/6-1/6 1x28/301-2/31/3 0 x5-2/300-5/61/6 cj - zj00-1/6

28、-1/60 0 x5 0 0 1 对偶单纯形法继续迭代，得对偶单纯形法继续迭代，得 cj1100 cbxbbx1x2x3x4 1x111000 1x216/50101/5 0 x34/5001-1/5 cj - zj000-1/5-1/5 0 x5 1 -4/5 -6/5 写出第二行的约束写出第二行的约束 5 1 3 5 4 5 1 542 xxx 将上式中所有常数写成正数和一个正分数之和将上式中所有常数写成正数和一个正分数之和 分数项移到右边，整数项移到左边分数项移到右边，整数项移到左边 5 1 3) 5 1 1( 5 1 542 xxx 5452 5 1 5 1 5 1 3xxxx 由于左

29、边为整数，所以右边也为整数，所以由于左边为整数，所以右边也为整数，所以 0, 0 54 xx所以所以由于由于 加入松弛变量加入松弛变量 放入单纯形表放入单纯形表 5 1 5 1 5 1 5 1 54 xx 0 5 1 5 1 5 1 54 xx 0 5 1 5 1 5 1 654 xxx cj1100 cbxbbx1x2x3x4 1x111000 1x216/50101/5 0 x34/5001-1/5 cj - zj000-1/5-1/50 0 x5 1 -4/5 -6/5 0 x6 0 0 0 0 x6-1/5000-1/5-1/51 cj1100 cbxbbx1x2x3x4 1x1110

30、00 1x230100 0 x310010 cj - zj00000-1 0 x5 1 -1 -1 0 x6 0 1 -1 0 x4100011-5 达到最优，达到最优， t x)3 , 1( 还可以得到另一个最优解：。还可以得到另一个最优解：。 t x)4 , 0( 目标规划目标规划 1，已知目标规划问题，已知目标规划问题 0, 2 42 92 62 )35(min 21 442 3321 21 21 443321 22 11 121 ii ddxx ddx ddxx ddxx ddxx dpddpdpdpz 用图解法求解最优解。用图解法求解最优解。 62 21 xx 92 21 xx 42

31、 21 xx 2 2 x 最优解最优解 2，某工厂生产，某工厂生产a,s两种型号的微型计算机，他们两种型号的微型计算机，他们 都需要经过两道工序，每台计算机所需的加工都需要经过两道工序，每台计算机所需的加工 时间、销售利润及该厂每周最大的加工能力如时间、销售利润及该厂每周最大的加工能力如 下表：下表： as周最大加 工能力 工序1（h/台） 46150h 工序2（h/台） 3275h 利润（元/台） 300450 工厂经营目标的各优先级如下：工厂经营目标的各优先级如下： p1：每周总利润不低于：每周总利润不低于10000元；元； p2：合同要求：合同要求a型机每周至少生产型机每周至少生产10台

32、，台，s型机至型机至 少少15台；台； p3：工序：工序1每周生成时间最好恰为每周生成时间最好恰为150h,工序工序2生成生成 时间可适当超过其能力；时间可适当超过其能力； 试写出目标规划的模型。试写出目标规划的模型。 0, 7566 15064 15 10 10000450300 )()(min 21 5521 4421 2 1 21 5443321 33 22 11 21 ii ddxx ddxx ddxx ddx ddx ddxx dddpddpdpz 解：设生产解：设生产a，s机器分别为机器分别为x1,x2台，则有台，则有 3，查找参考书，参阅较复杂问题的模型，查找参考书，参阅较复杂问

33、题的模型 图论图论 1，用避圈法或破圈法求下图的最小树，用避圈法或破圈法求下图的最小树 1 v 2 v 5 v 7 v 8 v 6 v 3 v 4 v 9 v 6 4 5 5 4 4 7 7 6 2 9 3 813 1 v 2 v 5 v 7 v 8 v 6 v 3 v 4 v 9 v 6 4 5 5 4 4 7 7 6 2 9 3 813 或选取或选取 去掉去掉),( 51 vv ),( 71 vv 解答：解答： 2，下图中，下图中 是仓库，是仓库， 是商店，求一条是商店，求一条 到到 的最短路的最短路 0 v 1 v 3 v 5 v 7 v 8 v 6 v 9 v 4 v 2 v 2 2

34、2 11 11 11 7 7 4 4 43 3 36 6 6 5 5 9 9 0 v 9 v 0 v 9 v 0 v 1 v 3 v 5 v 7 v 8 v 6 v 9 v 4 v 2 v 2 2 2 11 11 11 7 7 4 4 43 3 36 6 6 5 5 9 9 )0( )2( )4( )7( )11( )11( )13( )13( )16()19( 最优方案可以有几种：最优方案可以有几种： 9210 , 1vvvv 94210 , 2vvvvv 9230 , 3vvvv 94230 , 4vvvvv 9430 , 5vvvv 9870 , 6vvvv 3，用标号算法求下图的最大流

35、，用标号算法求下图的最大流 s v 2 v 4 v 1 v 5 v t v 3 v )5(5 )3(3 )2(3 )4(6 )0(2 )4(5 )2(2 )4(4 )6(6 )6(8)3(3 )0(2 s v 2 v 4 v 1 v 5 v t v 3 v ) 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 ss vv )2 ,(, 2 2s vv )1 ,(, 3 23 vv )1 ,(, 4 34 vv )1 ,(, 5 41 vv )1 ,(,

36、6 15 vv )1 ,(, 7 5 vvt s v 2 v 4 v 1 v 5 v t v 3 v ) 5( 5 ) 3( 3 ) 2( 3 ) 4( 6 ) 0( 2 ) 4( 5 ) 2( 2 ) 4( 4 ) 6( 6 ) 6( 8) 3( 3 ) 0( 2 得增广链如右图中红色部得增广链如右图中红色部 分，调整后得新图如下：分，调整后得新图如下： s v 2 v 4 v 1 v 5 v t v 3 v ) 5( 5 )3( 3 )3( 3 ) 5( 6 )0( 2 )5( 5 ) 1 ( 2 )4( 4 )6( 6 )7( 8) 2( 3 )0( 2 再次标号知：没有增广链存在，故达

37、到最大流。最再次标号知：没有增广链存在，故达到最大流。最 大流量为大流量为13 4，求下图中流值为，求下图中流值为6的最小费用流，其中弧旁边的最小费用流，其中弧旁边 的数字为的数字为 , 表示容量，表示容量， 表示单位流表示单位流 量费用。量费用。 s vt v 2 v 1 v 3 v 4 v )2 , 3( )3 , 3( )1 , 3( )3 , 4( )1 , 4( )1 , 7( )5 , 6( )4 , 5( ),( ijij dcij c ij d s vt v 2 v 1 v 3 v 4 v )2( )3( )1( )3( )1( )1( )5( )4( 解：以解：以0作为初始流

38、量，得长度网络作为初始流量，得长度网络 最短路：最短路： ts vvvv 43 调整流量，得新的流量网络调整流量，得新的流量网络 s vt v 2 v 1 v 3 v 4 v 0 3 3 0 3 0 0 0 对新的流量网络，得到长度网络对新的流量网络，得到长度网络 s vt v 2 v 1 v 3 v 4 v )2( )3( )1( )3( )1( )1( )5( )4( )1( 最短路：最短路： ts vvvv 23 调整流量，得新的流量网络调整流量，得新的流量网络 s vt v 2 v 1 v 3 v 4 v 0 3 3 0 4 1 0 1 对新的流量网络，得到长度网络对新的流量网络，得到

39、长度网络 s vt v 2 v 1 v 3 v 4 v )2( )3( )1( )3()1( )5( )4( )1( )4( )1( 最短路：最短路： ts vvvvvv 2341 调整流量，得新的流量网络调整流量，得新的流量网络 s vt v 2 v 1 v 3 v 4 v 2 1 3 2 4 3 0 3 pert图图 与与 关键路线法关键路线法 1，下表给出一个汽车库及引道的施工计划：，下表给出一个汽车库及引道的施工计划： 作业编号作业内容作业时间（天）紧前作业 1清理场地准备施工10无 2备料8无 3车库地面施工61，2 4墙及房顶 架预制162 5车库混凝土地面保养243 6竖立墙架4

40、4，5 7竖立房顶 架46 8装窗及边墙106 9装门46 10装天花板127 11油漆168，9，10 12引道混凝土施工83 13引道混凝土保养2412 14清理场地交工验收411，13 请解答请解答（1）该工程从施工开始道工程结束的最）该工程从施工开始道工程结束的最 短周期；（短周期；（2）如果引道混凝土施工工期拖延）如果引道混凝土施工工期拖延 10天，对整个工程进度有何影响？（天，对整个工程进度有何影响？（3）若装）若装 天花板的施工时间从天花板的施工时间从12天缩短为天缩短为8天，对整个天，对整个 工程进度有何影响？（工程进度有何影响？（4）为保证工期不拖延，）为保证工期不拖延， 装

41、门这项作业最晚应从哪一天开工？（装门这项作业最晚应从哪一天开工？（5）如）如 果要求该工程必须在果要求该工程必须在75天内完工，是否应采取天内完工，是否应采取 措施，应采取什么措施？措施，应采取什么措施？ 0 40 10 0 4 10 24 0 0 4 16 24 1 2 3 4 5 87 10 11 9 4 6 44 a 16 0 6 168 4 1213 b 16 c e l i g fh j n m dk 8 24 12 0 0 10 0 2 8 44 44 48 60 24 7680 807660 52 50 56 48 44 40 16 44 10 解：作业编号分别对应a,b,c,d

42、,e,f,g,h,i,j,k,l,m,n，pert 图如下 第第80页页 （1）该工程从施工开始道工程结束的最短周期为）该工程从施工开始道工程结束的最短周期为80天天 可计算出自由时差和总时差可计算出自由时差和总时差 若使用公式：若使用公式： ),(),(),(jitjitjir esls ),(),(),(min),(jitjitkjtjif eses k 0 40 10 0 4 10 24 0 0 4 16 24 1 2 3 4 5 87 10 11 9 4 6 44 a 16 0 6 168 4 1213 b 16 c e l i g fh j n m dk 8 24 12 0 0 10

43、 0 2 8 44 44 48 60 24 7680 807660 52 50 56 48 44 40 16 44 10 00 2 16 0 28 0 12 6 0 0 0 28 0 )0( )0( )0( )16( )0( )0( )0( )12( )0( )0( )6( )0( )28( )0( *表示总时差表示总时差(*) 表示自由时差表示自由时差 如此可找到关键路线：如此可找到关键路线：a-c-e-f-g-j-k-n （2）如果引道混凝土施工）如果引道混凝土施工(l)工期拖延工期拖延10天，由于此工序天，由于此工序 有总时差有总时差28，所以它的工期拖延，所以它的工期拖延10天，对整个

44、工程进度天，对整个工程进度 无影响。无影响。 （3）若装天花板（）若装天花板（j）的施工时间从）的施工时间从12天缩短为天缩短为8天，天， 观察它的平行工序观察它的平行工序h，i，发现关键路线不会改变，所，发现关键路线不会改变，所 以整个工程进度也缩短以整个工程进度也缩短4天。天。 （4）为保证工期不拖延，装门（）为保证工期不拖延，装门（i）这项作业最）这项作业最 晚应从第晚应从第56天开工天开工 （5）如果要求该工程必须在）如果要求该工程必须在75天内完工，在合适的关天内完工，在合适的关 键工序上压缩键工序上压缩5天工期。天工期。 动态规划动态规划 1. 设有设有6万元资金用于四个工厂的扩建

45、。已知每个工厂万元资金用于四个工厂的扩建。已知每个工厂 的利润增长额同投资数的大小有关，数据见表。如何的利润增长额同投资数的大小有关，数据见表。如何 确定对四个工厂的投资数，使得总利润增长额最大。确定对四个工厂的投资数，使得总利润增长额最大。 0100200300400500600 10204260758590 20254557657073 30183961789095 40284765748085 利润增长额利润增长额 工厂工厂 投资投资 1.解：解： 设设sk表示第表示第k个工厂到第个工厂到第4个工厂的投资数。个工厂的投资数。xk 表示第表示第k个工厂的投资数个工厂的投资数,则第则第4个阶

46、段如下：个阶段如下： fx* 0100200300400500600 0000 1002828100 2004747200 3006565300 4007474400 5008080500 6008585600 fx* 0100200300400500600 0000 1002818280 200474639470 3006565676167200 400748386897889300 500809210410810690108300 600859811312612511895126300 第第3个阶段：个阶段： fx* 0100 200 300400 500 600 0000 100 282

47、5280 200 47534553100 300 6772735773200 400 899292856592 100，200 500 108 114 112 1049370114 100 600 126 133 134 124112 9873134 200 第第2个阶段：个阶段： fx* 0100 200 300400 500 600 600 134 134 134 133128 113 90134 0，100，200 第第1个阶段：个阶段： 最优方案：最优方案： 1，0，200，300，100 2，100，100，300，100 3，200，100，200，100 4，200，200，0，

48、200 2. 用动态规划解以下静态问题：用动态规划解以下静态问题： 0, 93 102 567max 21 21 21 2 21 2 1 xx xx xx xxxz 解：令解：令k=2, 状态变量：状态变量：k阶段初各约束条件右端项的剩余值阶段初各约束条件右端项的剩余值r1k,r2k 决策变量：决策变量：x1,x2 ， ，状态转移方程为： 状态转移方程为： 112122 111112 9 10 xxrr xxrr 212 2 2 2 3 ,0max 22122 ) 2 (55max),( 12 2 22 r xrrf r x r 令令k=1,由于由于 k=2时时, 2 10 2 112 2 x

49、r x 而由第而由第2个约束知，个约束知， 5 48 2 10 3939 1 1 11 x x xx 所以所以 92.70212519 4 33 12519 4 33 max ) 2 10 (567max ) 2 (567max)( 5 481 2 1 1 2 1 5 48 0 21 1 2 1 5 48 0 212 1 2 1 5 48 ,10min0 11 1 1 1 1 x x x x xx xx x xx r xxsf 此时此时,x2=0.5 决策分析决策分析 1,某钟表公司计划通过它的销售网销售一种低价钟某钟表公司计划通过它的销售网销售一种低价钟 表，计划每块售价表，计划每块售价10

50、元。生产这种钟表有元。生产这种钟表有3个设个设 计方案：方案计方案：方案1需一次投资需一次投资10万元，以后生产一万元，以后生产一 个的费用为个的费用为5元，方案元，方案2需一次投资需一次投资16万元，以万元，以 后生产一个的费用为后生产一个的费用为4元；方案元；方案3需一次投资需一次投资25 万元，以后生产一个的费用为万元，以后生产一个的费用为3元。对该种钟表元。对该种钟表 的需求量为未知，但估计有三种可能：的需求量为未知，但估计有三种可能： e130000；e2120000；e3200000 a)建立这个问题的收益矩阵；建立这个问题的收益矩阵；b)分别用悲观主义、分别用悲观主义、 乐观主义和等可能性决策准则决定该公司应采乐观主义和等可能性决策准则决定该公司应采 用哪一个设计方案；用哪一个设计方案；c)建立机会损失矩阵，并用建立机会损失矩阵，并用 最小机会损失决策准则决定采取哪一个设计方最小机会损失决策准则决定采取哪一个设计方 案。案。 e1e2e3 a155090 a2256104 a3-459115 收益矩阵（单位：万）：收益矩阵（单位：万）： e1e2e3 a1550909 a2256104104 a3-459115115 乐观准则：乐观准则： 选选a3 e1e2e3 a1550909 a2256104104 a3-459115115 悲观准则：悲观准则： 选选a1 e