第5章运输与指派答案.pdf

第第5章章 运输与指派问题运输与指派问题 5.1 求表 5-53 的运输问题 表表5-53 B1 B2 B3 B4 ai A1 5 3 8 6 16 A2 10 7 12 15 24 A3 17 4 8 9 30 bj 20 25 10 15 【解解】最小元素法求的初始方案 16 204 91011 ，检验的位势值（令 3 0u ） 5 3 8 6 -1 10 7 12 15 6 17 4 8 9 0 4 4 8 9 检验数中有 142223 2,3,2 *4 911 调整量 4，调整后方案 16 204 51015 再检验（令 3 0u ） 5 3 8 6 -1 10 7 12 15 3 17 4 8 9 0 7 4 8 9 检验数中有 1114 1,2 16* 515 调整量 15，调整后方案 115 204 2010 再检验（令 2 0v ） 5 3 8 6 3 10 7 12 15 7 17 4 8 9 4 3 0 4 3 检验数中只有 11 1 *1 204 调整量 1，调整后方案 115 195 2010 再检验（令 1 0u ） 5 3 8 6 0 10 7 12 15 5 17 4 8 9 2 5 2 6 6 非基变量的检验数： 121323243134 1,2,1,4,10,1全部大于 0，所以此 方案为最优调运方案，其调运费用为 1 5 15 6 19 105 720 4 10 8480 5.2 求表 5-54 所示运输问题的最优方案 表表5-54 B1 B2 B3 B4 ai A1 10 5 2 3 70 A2 4 3 1 2 80 A3 5 6 4 4 30 bj 60 60 40 20 【解】 最小元素法求初始方案，并依次调整 3040 *204020 30 20 1060* 204020 30 10 6010 30*3020 30 30 3040* 303020 30 20 104020 3050 30 前面 4 个方案的检验略，最后方案的检验（令 1 0u ）如下 10 5 2 3 0 4 3 1 2 -2 5 6 4 4 -1 6 5 2 3 非基变量的检验数： 112324323334 4,1,1,2,3,2全部大于 0，所以上面 最后方案为最优调运方案，其调运费用为 10 540 220 330 450 330 5610 5.3 求下列运输问题的最优解 （1）C1目标函数求最小值； （2）C2目标函数求最大值 1 3592 50 6485 25 11 13 127 30 15452040 C 2 7101520 60 14139630 58710 90 60305040 C (3)目标函数最小值。B1的需求为 30b150，B2的需求为 40，B3的需求为 20b360， A1不可达 B4，B4的需求为 30 50 20 70 10948 2356 794 【解】 （1）添加虚拟产地，产销平衡表为 3592 50 6485 25 11 13 127 30 0000 15 15452040 最小元素法得到的初始方案为 1040 25 5520* 15 ，依次调整 5 15*35 25 5205 15 5 15530 25 2010 15* 15 152015 25 525 15 最后方案的位势值（令 1 0u ） ： 35920 64851 11 13 1275 00007 3572 非基变量的检验数： 132123243132414244 2,4,2,4,3,3,4,2,5 最优调运费用15 320 5 15 225 45 1225 7510 （2）最大大元素法求得初始方案为 2040 30 303030 其位势值（令 3 0u ） ： 7101520 8 1413969 58710 0 58712 非基变量的检验数： 111221232433 6,6,4,7,15,2 全部小于 0， 所以初始方案就是最优方案，其调运费用为 20 1540 2030 1430 530 830 72120 （3）先建立产销平衡表 B11 B12 B2 B31 B32 B4 ai A1 4 4 9 7 7 70 A2 6 6 5 3 3 2 20 A3 8 8 4 9 9 10 50 虚拟 M 0 M M 0 M 40 bj 30 20 40 20 40 30 180 初始方案 302020 20 04010 040 ，检验（令 1 0u ） 4 4 9 7 7 0 6 6 5 3 3 2 -4 8 8 4 9 9 10 4 M 0 M M 0 M -4 4 4 0 7 4 6 检验数中有 34 2 ，需调整 2020 0* 0 302020 20 40010 040 令 1 0u 得位势值 4 4 9 7 7 0 6 6 5 3 3 2 -6 8 8 4 9 9 10 2 M 0 M M 0 M -4 4 4 2 7 4 8 非基变量的检验数 13152122232425313235 7,3,8,8,9,2,5,2,2,3 所以调整后的方案为最优方案，其费用为 30 420 420 720 240 40 9 10 10640 5.4（1）建立数学模型 设 xij(i=1,2,3;j=1,2)为豪华、中档、普通三种型号的客车每天发往 B1，B2两城市的车辆数， 则 111221223132 112131 122232 1112 2122 3132 max40(806560505040) 404040400 404040600 5 10 15 0(1,2,3;1,2) ij Zxxxxxx xxx xxx xx xx xx xij (2)写平衡运价表 将第一、 二等式两边同除以 40， 加入松驰变量 x13,x23和 x33将不等式化为等式， 则平衡表为： B1 B2 B3 ai 豪华 中档 普通 80 60 50 65 50 40 0 0 0 5 10 15 bj 10 15 5 为了平衡表简单，故表中运价没有乘以 40，最优解不变 （3）最大大元素法求得初始方案 5 55 105 ，其位势值 80650 80 60500 60 50400 50 01050 非基变量的检验数 12132331 5,30,10,0 全部小于等于 0， 故初始方案就是 最优调度方案，其具体调度为： 每天发 5 辆豪华车、5 辆中档车到 B1城市，发 5 辆中档车、10 辆普通车到 B2城市，多 了 5 辆普通车，最大收入为 z*=40（580+560+550+1040）=54000（元） 5.5（1）设 xij为第 i 月生产的产品第 j 月交货的台数，则此生产计划问题的数学模型为 111213142144 11213141 12223242 13233343 14243444 11121314 21222324 31323334 41424344 min1.151.31.450.98 50 40 60 80 65 65 65 65 0,( , ij ZxxxxMxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xi j 1,4) （2）化为运输问题后运价表（即生产费用加上存储费用）如下，其中第 5 列是虚设销地费 用为零，需求量为 30。 1 2 3 4 5 ai 1 2 3 4 1 M M M 1.15 1.25 M M 1.3 1.4 0.87 M 1.45 1.55 1.02 0.98 0 0 0 0 65 65 65 65 bj 50 40 60 80 30 (3)用表上作业法，最优生产方案如下： 5015 251030 605 65 即一月份生产 65 台，当月交货 50 台，二月份交货 15 台；二月份生产 35 台，当月交货 25 台，四月份交货 10 台；三月份生产 65 台，当月交货 60 台，四月份交货 5 台，4 月份生产 65 台当月交货。最小费用 *50 1 15 1.1525 1.25 10 1.5560 0.875 1.0265 0.98235z 万元。 5.6 略 5.7 求解下列最小值的指派问题，其中第（2）题某人要作两项工作，其余 3 人每人做一项 工作 （1） 2015106 25101835 26181220 159612 C 【解】 1269156039603(0) 20121826806148(0)65 35181025258013258(0)4 610152004914(0)495 最优解 1 1 *, *43 1 1 XZ （2） 2053453122 2556473020 2159443325 2752413826 C 【解】虚拟一个人，其效率取 4 人中最好的，构造效率表为 A B C D E 甲 26 38 41 52 27 乙 25 33 44 59 21 丙 20 30 47 56 25 丁 22 31 45 53 20 虚拟 20 30 41 52 20 最优解： 1 1 *1 1 1 X ，最优值 Z*=165 最优分配方案：甲完成 C、D 两项，乙完成 E 项，丙完成 A 项，丁完成 B 项。 5.8 求解下列最大值的指派问题： （1） 2612816 19131318 20101415 176910 C 【解】 10961778110625(0) 15141020561004(0)40 181313191660(0)000 1681226101814091280 行列 4 221(0) 0(0)00 04(0)4 51240 1 11(0)0 0(0)01 (0)405 4113(0) 最优解 1 1 *, *6 14 182664 1 1 XZ （2） 96510 485 710912 615716 9868 C 【解】 16 965107101160 485128110 71091296740 615716101900 9868781080 用最大元素 减, 并添 加虚拟任务 09460 5111(0) 25(0)40 3(0)200 (0)7380 列 05420 517(0) 21(0)00 7(0)604 (0)3340 =4 04310 5(0)60 310(0)1 8(0)605 02230 =1 最优解 11 11 *4411 11 11 XXZ 或； 第 5 人或第 1 人不安排工作。 5.9 学校举行游泳、自行车、长跑和登山四项接力赛，已知 五名运动员完成各项目的成绩（分钟）如表 5-57 所示如 何从中选拔一个接力队，使预期的比赛成绩最好 【解】设 1, 0, ij ij x ij 第 人参加第 项目 第 人不参加第 项目 则数学模型为 1112131454 11121314 21222324 31323334 41424344 51525354 1121314151 1222324252 1323334353 14243444 min2043332928 1 1 1 1 1 1 1 1 Zxxxxx xxxx xxxx xxxx xxxx xxxx xxxxx xxxxx xxxxx xxxxx 54 1 01,1,2,5;1,2,3,4 ij xij 或 表 5-57 成绩表(分钟) 游泳 自行车 长跑 登山 甲 20 43 33 29 乙 15 33 28 26 丙 18 42 38 29 丁 19 44 32 27 戊 17 34 30 28 添加虚拟项目进行求解 204333290 153328260 18