《第28讲 运筹学初步》由会员分享，可在线阅读，更多相关《第28讲 运筹学初步（9页珍藏版）》请在金锄头文库上搜索。
1、第28讲 运筹学初步（二）本讲主要研究分配工作问题。实际工作中经常会碰到分配工作的问题。由于工作任务的性质不 同，每个人的工作能力不同，因而完成这些任务所需的时间和花费的 代价也不同。我们希望通过合理分配工作，使所用时间最少或花费代 价最小。例1甲、乙两厂生产同一规格的上衣和裤子，甲厂每月用16天生 产上衣，14天做裤子，共生产448套衣服（每套上衣、裤子各一件）； 乙厂每月用12天生产上衣，18天生产裤子，共生产720套衣服。两厂 合并后，每月（按30天计算）最多能生产多少套衣服？分析与解：应让善于生产上衣或裤子的厂充分发挥特长。甲厂生 产上衣和裤子的时间比为8：7,乙厂为2：3,可见甲厂善
2、于生产裤子， 乙厂善于生产上衣。因为甲厂30天可生产裤子448*14X30 = 960 （条），乙厂30天 可生产上衣720*12X30=1800 （件）960V1800，所以甲厂应专门生 产裤子，剩下的衣裤由乙厂生产。设乙厂用x天生产裤子，用（30-x，天生产上衣。由甲、乙两厂 生产的上衣与裤子一样多，可得方程960 + 720*18Xx=720*12X（30-x），960+40x = 1800-60x，100x = 840，x=8.4 （天）。两厂合并后每月最多可生产衣服960 + 40X8.4 = 1296 （套）例2某县农机厂金工车间共有77个工人。已知每天每个工人平均 可加工甲种部件
3、5个，或乙种部件4个，或丙种部件3个。每3个甲种部 件、1个乙种部件和9个丙种部件恰好配成一套。问：分别安排多少人 加工甲、乙、丙三种部件时，才能使生产出来的甲、乙、丙三种部件 恰好都配套？分析与解：如果采用直接假设，那么就要用三个字母分别代替加 工甲、乙、丙三种部件的人数，这已经超出了我们的知识范围。由题 目条件看出，每套成品中，甲、乙、丙三种部件的件数之比是3：1：9, 因为是配套生产，所以生产出的甲、乙、丙三种部件的数量之比也应 是 3：1：9。设每天加工乙种部件x个，则加工甲种部件3x个，丙种部件9x 个。从而? 1可知，扣工甲种部件应安排护人，加工乙种部件应安排討人，加工丙种部9件应
4、安排拿人？依题意可得方程119-k. + + -：盘=77,320X = 77jx = 20o?1 a将x. = 20依次代入护，xfl x,得33 . -k = -X.0=12/.(A.),1 1 、-2.0 = 5 (A),9x=20= 60 CA) o加工甲、乙、丙三种部件应分别安排12人、5人和60人。例3有4辆汽车要派往五个地点运送货物，右图O中的数字分别 表示五个地点完成任务需要的装卸工人数，五个地点共需装卸工20 人。如果有些装卸工可以跟车走，那么应如何安排跟车人数及各点的 装卸工人数，使完成任务所用的装卸工总人数最少？分析与解：可用试探法。因为五个地点中需装卸工最多的是5个 人
5、，所以如果每辆车跟5个工人，那么每辆车到达任何一个地点，都 能正常进行装卸。由此得到，跟车人数的试探范围是15个人。若每车跟车5人，则各点不用安排人，共需20人；若每车跟车4人，则原来需5人的点还需各安排1人，共需18人；若每车跟车3人，则原来需5人的点还需各安排2人，原来需4人的 点还需各安排1人，共需17人；同理可求出，每车跟车2人，共需18人；每车跟车1人，共需19 人。可见，安排每车跟车3人，原来需5人的两个点各安排2人，原来 需4人的点安排1人，这时所用的装卸工总人数最少，需17人。在例3中，我们采用试探法，逐一试算，比较选优。事实上，此 类题目有更简捷的解法。假设有m个地点n辆车（
6、nWm），m个地点 需要的人数按从多到少排列为A1三A2$A3$三Am，则需要的最少总人数就是前n个数之和，即A1+A2 An。这时每车的跟车人数可以是An+1至An之间的任一数。具体到 例3, 5个点4辆车，5个点中需要人数最多的4个数之和，即5 + 5+4 + 3=17 （人）就是需要的最少总人数，因为A4=A5=3,所以每车跟车 3人。若在例3中只有2辆车,其它条件不变，则最少需要5 + 5=10（人）， 因为A2=5, A3=4，所以每车跟车5人或4人。当每车跟车5人时，所有 点不再安排人；当每车跟车4人时，需要5人的两个点各安排1人，其 余点不安排人。注：如果车辆数大于地点数，即nm
7、，则跟车人数是0,各点需 要人数之和就是总共需要的最少人数。例4有17根11.1米长的钢管，要截成1.0米和0.7米的甲、乙两种 长度的管子，要求截成的甲、乙两种管子的数量一样多。问：最多能 截出甲、乙两种管子各多少根？分析与解：要想尽量多地截出甲、乙两种管子，残料应当尽量少。 一根钢管全部截成1.0米的，余下0.1米，全部截成0.7米的，余下0.6 米。如果这样截，再要求甲、乙管数量相等，那么残料较多。怎样才能减少残料，甚至无残料呢？我们可以将1.0米的和0.7米的在一根钢管上搭配着截，所得残料长度（单位：米）见下表：讓工：2,.3：4.&.6-781011.12-1.0米11109:8：?
8、6.5：45.S100.7 氷：.0-1.3：4 :.&7.1-0；1.1131415残料610. 40-0:3.(J. 6ci： 20. 50.10.400.-30. &由上表看出，方法3和方法10没有残料，如果能把这两种方法配 合起来，使截出的甲、乙两种管子数量相等，那么就是残料最少的下 料方案了。设按方法3截x根钢管，按方法10截y根钢管。这样共截得甲 管（9x + 2y）根，乙管（3x+13y）根。由甲、乙管数量相等，得到9x + 2y = 3x + 13y，9x-3x= 13y-2y，6x=11y。由此得到x：y二11：6。用方法3截11根钢管，用方法10截6根钢 管是符合题意的截法
9、，共可截得甲、乙管各9X11 + 2X6=111 （根）或 3X11 + 13X6=111 （根）例5给甲、乙二人分配A，B两项工作，他们完成这两项工作所需 要的时间如下表:.A-B甲8乙.46第一列第二列第一行 第二行怎样分配工作才能使完成这两项工作所需的总时间最少?分析与解：因为不同的人要做不同的工作，所以上表中不同行、 不同列的两数之和对应一种方案，共两种:(1) 甲做A、乙做B,需要7+6=13 (时)；(2) 甲做B、乙做A,需要4 + 8=12 (时)显然后一种方案优于前一种方案。为了能够处理更复杂的问题，我们将上例的数量关系尽量简化。如果把表中第一行的两数都减去该行的最小数7,变
10、成0和1,那 么上面(1) (2)各式也各减少7,不影响它们之间的大小关系，即不 影响最优方案的确定。同理，第二行都减去该行的最小数4,变成0和2,也不影响最优 方案的确定。经上述变换后，原表变成左下表：AB甲01乙02AB甲o:0乙01此时，再将第二列都减去该列的最小数1,变成0和1,同样不影响最优方案的确定，原表变为右上表。不同行、不同列的两个数之和代表一种方案，因为0 + 0 V0+1，所以最优方案为乙做A、甲做B。上面的化简过程可表示为:第行、0 1第2行、0 1第2列、0 0减74 61 J减4 減10 1总结上面的方法：对于n个人n项工作的合理分配问题：(1) 先将各行都减去该行中
11、最小的数；(2) 再将各列都减去该列中最小的数；(3) 最后选择不在同一行，也不在同一列的n个0即可。在实施上述变换后，如果仍选不出n个不同行也不同列的0，因 为我们的目的是选取一组不同行、不同列的n个数，使这n个数之和 尽量小，既然得不到n个0,可用表中最小的数代替0 (见例6)。例6给甲、乙、丙三人分配A，B，C三项工作，他们完成这三项 工作的时间如下表:A.B.-0甲4 9；7乙715.13丙5129完成这三项工作所需总时间最少是多少?分析与解：半J J各行磁5 12 9各列减该行最小数0 Q.33因为没有三个不同行也不同列的0,我们用右下角的1代替0,此 时，O内的三个数就是我们要找的
12、最佳方案，即甲做B、乙做A、丙 做C。所需总时间为9 + 7 + 9=25 （时）练习281. 某种健身球由一个黑球和一个白球组成一套。已知两个车间都 生产这种健身球，甲车间每月用；的时间生产黑球，三的时间生产白球，每月生产前01套;乙车间每片用的时间生产黑球，g的时间生产白球，每月生产300套。现在两个车间联合起来生产，每月最多能生产多少套健身球？2. 某车间有铣床5台、车床3台、自动机床1台，生产一种由甲、 乙两种零件各1个组成的产品。每台铣床每天生产甲零件10个，或者 生产乙零件20个；每台车床每天生产甲零件20个，或者生产乙零件30 个；每台自动机床每天生产甲零件30个，或者生产乙零件
13、80个。这些 机器每天最多可生产多少套产品？3. 车过河交渡费3元，马过河交渡费2元，人过河交渡费1元。某 天过河的车、马数目的比为2：9,马、人数目的比为3：7,共收得渡 费945元。问：这天渡河的车、马、人的数目各多少？4. 有4辆汽车要派往七个地点运送货物，右图中的数字分别表示 这七个地点完成任务需要的装卸工人数。如果装卸工可以跟车，那么 最少要安排多少名装卸工才能完成任务？5. 有一批长4.3米的条形钢材，要截成0.7米和0.4米的甲、乙两 种毛坯，要求截出的甲、乙两种毛坯数量相同。如何下料才能使残料 最少？6. 用10米长的钢筋做原材料，截取3米和4米长的钢筋各100根， 至少要用多少根原材料？7. 给甲、乙、丙分配A，B，C三项工作，他们完成这三项工作的 时间如下表。怎样分配工作才能使完成这三项工作所需总时间最少？ 最少用多少时间？作时C甲y巧9乙78丙.住97
