运筹学基础及应用
P43例13 、混合配料问题:某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如表1-19所示。问该厂每月生产这三种牌号糖果各多少千克，使该厂获利最大。试建立这个问题的线性规划的数学模型。
表1-19
甲乙丙原料成本(元/kg) 每月限制用量(kg) A 2.00 2000 ?60% ?30%
B 1.50 2500
C 1.00 1200 ?20% ?50% ?60%
0.50 0.40 0.30 加工费(元/kg)
3.40 2.85 2.25 售价(元/kg)
P44例14、投资项目的组合问题:兴安公司有一笔30万元的资金，考虑今后三年内用于下列项目的投资:
(1) 三年内的每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年投资;
(2) 只允许第一年初投入，于第二年末收回，本利合计为投资额的150%，但此类投资限额不超过15万元;
(3) 允许于第二年初投入，于第三年末收回，本利合计为投资额的160%，但限额投资20万元;
(4) 允许于第三年初投入，年末收回，可获利40%，但限额为10万元。
试为该公司确定一个使第三年末本利和为最大的投资组合方案。
P44例15、生产、库存与设备维修综合计划的安排:红光厂有2台车床，1台钻床，1台磨床，承担4中产品的生产任务(已知生产各种产品所需的设备台时及生
产单位产品的售价如表,,20所示(对各种产品今后三个月的市场最大需求(小于最大需求量时即可全部销出)及各产品在今后三个月的生产成本分别如表1,21和表1,22所示(
上述设备在1~3月内各需进行一次维修,具体安排为:2台车床于2月份、3月份各维修一台,钻床安排在2月份维修,磨床安排在3月份维修.各设备每月工作22天.每天2班,每班8h,每次维修占用半各月时间.又生产出来的产品当月销售不出去(超过最大需求量)时,可在以后各月销售,但需付每件每月储存费5元.但规定每月底各种产品储存量均不得超过100件.1月初各产品无库存,要求3月底各产品均库存50件.试安排该厂各月的生产计划,使总的利润为最大.
表,,20 a值单位:h ij
i ? ? ? ? j
车床 ,., ,., ,.,
钻床 ,., ,., ,.,
磨床 ,., ,., ,.,
售价(元,件) ,, ,, ,, ,,
表 1,21 最大需求量单位:件 K ? ? ? ? j
1月 200 300 200 200 2月 300 200 0 300 3月 300 100 400 0
表,,22 产品成本单位:元,件
K ? ? ? ? j
,月 ,, ,, ,, ,, ,月 ,, ,, ,, ,, ,月 ,, ,, ,, ,,
P81例1、某食品公司经销的主要产品之一是糖果。它下面设有三个加工厂，每天的糖果生产量分别为:A1—7t,A2—4t,A3—9t.该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为:B1—3t,B2—6t,B3—5t,B4—6t.已知
从每个加工厂到各销售门市部每吨糖果的运价如表3—1所示，问该食品公司应如何调运，在满足各门市部销售需要的情况下，使总的运费支出为最少。
表3—1
B1 B2 B3 B4 加工厂\门市部
A1 3 11 3 10
A2 1 9 2 8
A3 7 4 10 5
P95例2、设有A1、A2、A3三个产地生产某种物资，其产量分别为7t、5t、
7t，B1、B2、B3、B4四个销地需要该种物资，销量分别为2t、3t、4t、6t，又知各产销地之间的单位运价见表3—25，试决定总运费最少的调运方案。
表3—25 单位运价表单位:元/t
B1 B2 B3 B4 产地\销地
A1 2 11 3 4
A2 10 3 5 9
A3 7 8 1 2
P96例3、设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同，已知各化肥厂年产量，各地区年需要量及从各化肥厂到各地区单位化肥的运价如表3—29所示，试决定使总的运费最节省的化肥调拨方案。
表3—29 运价:万元/万t
化肥厂\需求地区 ? ? ? ? 产量(万t)
A 16 13 22 17 50
B 14 13 19 15 60
C 19 20 23 50
30 70 0 10 最低需求(万t)
50 70 30 最高需求(万t) 不限
P98例4、在本章的例1中，如果假定:(1)每个工厂生产的糖果不一定直接发运到销售点，可以将其中几个产地的糖果集中一起运;(2)运往各销地的糖果可以先运给其中几个销地，再转运给其他销地;(3)除产、销地之外，中间还可以有几个转运站，在产地之间、销地之间或产地与销地之间转运。已知各产地、销地、中间转运站及相互之间每吨糖果的运价如表3—33所示，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将三个厂每天生产的糖果运往销售地，使总的运费最少。
表3—33
产地中间转运站销地
A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4
A1 1 3 2 1 4 3 3 11 3 10 产地
A2 1 3 5 2 1 9 2 8 ——
A3 3 1 2 3 7 4 10 5 ——
T1 2 3 1 1 3 2 2 8 4 6 中间转运站
T2 1 5 1 1 1 4 5 2 7 —
T3 4 2 3 1 2 1 8 2 4 —
T4 3 2 3 2 1 2 1 2 6 —
B1 3 1 7 2 4 1 1 1 4 2 销地
B2 11 9 4 8 5 8 1 2 1 —
B3 3 2 10 4 2 2 2 4 2 3
B4 10 8 5 6 7 4 6 2 1 3
P108例2、有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁
)如表4—1所示。四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间(h应如何分配，使这四个人分别完成这四项任务总的时间为最小。
表4—1
工作\人甲乙丙丁
2 10 9 7 译成英文
15 4 14 8 译成日文
13 14 16 11 译成德文
4 1
5 13 9 译成俄文
P120例3、东方大学计算机实验室聘用4名大学生(代号1、2、3、4)和两名研究生(代号5、6)值班答疑。已知每人从周一至周五每天最多可安排的值班时间及每人每h值班的报酬如下表4—7所示:
表4—7
学生代号报酬(元/h) 每天最多可安排的值班时间
周一周二周三周四周五
1 10.0 6 0 6 0 7
2 10.0 0 6 0 6 0
3 9.9
4 8 3 0 5
4 9.8
5 5
6 0 4
5 10.8 3 0 4 8 0
6 11.3 0 6 0 6 3
该实验室开放时间为上午8:00至晚上10:00，开放时间内须有且仅须一名学生值班。规定大学生每周值班不少于8h，研究生每周不少于7h，每名学生每周值班不超过3次，每
次值班不少于2h，每天安排值班的学生不超过3人，且其中必须有一名研究生。试为该实验室安排一张人员的值班表，使总支付的报酬为最少。
P121例4 红星日用化工厂为发运产品，下一年度需6种不同容积的包装箱。每种包装箱的需求量及生产一个的可变费用如下表4—8所示:
表4—8
1 2 3 4 5 6 包装箱代号
0.08 0.1 0.12 0.15 0.20 0.25 容积
500 550 700 900 450 400 需求量(个)
5.0 8.0 10.0 12.1 1
6.3 18.2 可变费用(元/个)
由于生产不同容积包装箱时需进行专门准备、下料等，生产某一容积包装箱的固定费用均为1200元。又若某一容积包装箱数量不够时，可用比它容积大的代替。试问该化工厂应订做哪几种代号的包装箱各多少个，使费用最节省。
P122例5 春江市计划为新建的5个居民小区中的两个分别各设立一所小学。表4—9给出了各小区内及各小区间的平均不行时间(min)及各居民小区的小学生人数。要求为该市提供决策建议，两所小学应分别建于哪两个居民小区，以及各居民小区学生应分到哪所小学上学，使学生总的上学步行时间为最短。
表4—9
小学位于该区小学生数至其他区步行时间(min)
1 2 3 4 5
1 200 5 20 15 25 10
2 180 20 4 20 15 25
3 300 15 20 6 25 15
4 160 2
5 15 25 4 12
5 350 10 25 15 12 5
P123例6 清源市下设八个区，表4—11给出救护车从一个区至另一个区的车程时间(min)。该市拟建救护中心，要求各区离救护中心的车程时间必须在8min之内。试为该市提供决策建议:至少建多少个救护中心，建于何处, 表4—11 单位:min
2 3 4 5 6 7 8 从\至
1 8 9 11 13 14 8 15
2 10 12 1
3 11 17 14
3 7 7 8 12 10
4 8 7 10 9
5 8 14 16
6 10 7
7 12
P125习题四
4.1、试利用0—1变量对下列各题分别表示成一般线性约束条件。
(a)x1+x2?2或2*x1+3*x2?5。
(b)变量x只能取值0、3、5或7中的一个。
(c)变量x或等于0，或?50。
(d)若x1?2，则x2?1，否则x2?4。
(e)以下四个约束条件中至少满足两个:x1+x2?5，x1?2，x3?2，x3+x4?6。
4.2、某钻井队要从以下10个可供选择的井位中确定5个钻井探油，目的使总的钻探费用最小。若10个井位代号为s1，s2，……，s10，相应的钻探费用为
c1，c2，……，c10，并且井位的选择上要满足下列条件:
(1)或选择s1和s7，或选择钻探 s8;
(2)选择了s3或s4就不能选s5，或反过来也一样;
(3)在s2、s6、s9、s10中最多只能选两个。
试建立这个问题的数学模型。
4.4、已知下列五名运动员各种姿势的游泳成绩(各为50m)如表4—13所示。试问如何从中选拔一个4*50m混合泳的接力队，使预期的比赛成绩为最好。
表4—13 单位:s
赵钱张王周
37.7 32.9 38.8 37.0 35.4 仰泳
43.4 33.1 42.2 34.7 41.8 蛙泳
33.3 28.5 38.9 30.4 33.6 蝶泳
29.2 26.4 29.6 28.5 31.1 自由泳
4(5 P125分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每个人完成各项任务的时间如表4-14所示。由于任务数多余人数，故考虑:
(a) 任务E必须完成，其它四项中可任选3项完成;
(b) 其中有一人完成两项，其他每人完成一项;
(c) 任务A由甲或丙完成，任务C由丙或丁完成，任务E由甲、乙或丁完成，且规定4人中丙或丁完成两项任务，其他每人完成一项;
试分别确定最优分配方案，使完成任务的总时间最少。
表4—14 单位:h
A B C D E 人任
务
25 29 31 42 37 甲
39 38 26 20 33 乙
34 27 28 40 32 丙
24 42 36 23 45 丁
4(6 P126某物资有m个生产点(i=1,……，m)，第i个生产点产量为a(i),该物资销往n个需求点，第j个需求点销量为b(j)(j=1,……，n),有?a(i)??b(j),已知从各生产点到各需求点，需经p个中间编组站之一转运(k=1,……，p),若启用第k个编组站，不管转运量多少，均发生固定费用f(k).已知第k个中间编租站转运的最大容量限制为q(k),用c(ik)和c(kj)分别表示从i到k和从k到j的单位物资的运输费用，试确定一个使总费用为最小的该种物资的调运方案。
4(10 一条多品种流水线上要轮换生产5种不同零件，表4-15给出了一开始生产某个零的准备时间及从生产一个零件转换生产另一个零件时所需的设备调整时间。试确定分枝定界法找出上述5个零件轮换生产的顺序，使总的准备及设备调整时间为最短。
表4—15 单位:h
1 2 3 4 5 开始生产 4 5 8 9 4 1 - 7 12 10 9 2 6 - 10 14 11 3 10 11 - 12 10 4 7 8 15 - 7 5 12 9 8 16 -
4.13 需生产2000件某种产品，该种产品可利用A.B.C.D设备中的任意一种加工。已知每种设备的生产准备结束费用，生产该产品时的单件成本以及每种设备限定的最大加工数量(件)如表4-16所示，诗建立该问题的数学模型并求解。
表4-16
设备准备结束费(元) 生产成本(元/件) 生产能力(件) A 1000 20 900 B 980 24 1000 C 800 16 1200 D 700 28 1600 4(14有10种不同零件，它们都有可以在设备A，或在设备B或在设备C上加工，其单件加工费用表4-17。又只要有零件在上述设备上加工，不管加工1种或多种，分别发生的一次
性准备费用为dA,dB,dC元，若要求:
1。上述10种零件每种加工1件;
。若第1种零件在设备A上加工，则第2种零件应在设备B 或C上加工。反之若第12
种零件在设备B或C上加工，则第2种零件应在设备A 上加工;
3。零件3，4，5必须在A，B，C三台设备上加工;
4。在设备C上加工的零件种数不超过3种.试对此问题建立整数规划的数学模型，目标是使总的费用为最小
表4-17
零件 1 2 3 4 5 6 7 8 9 10 设备
A a a a a a aaa a a 73568910241
B b b b b b bbb b b 73568910241
C c c c c C Ccc c c 73568910241
4.15 鞍山街邮局从周一到周日每天所需值班人员如表4—18所示: