第五章 习 题
5.1某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻井费用最小。若10个井位的代号为s1,s2,s3?s10，相应的钻井费用为c1,c2,?,c10，并且井位选择上要满足下列限制条件：
①或选择s1和s7，或选择钻探s8；
②选择了s3或s4就不能选s5，或反过来也一样；
③在s5,s6,s7,s8中最多只能选两个；试建立这个问题的整数规划模型。
5.2某市为方便学生上学，拟在新建的居民小区增设若干所小学。已知备选校址代号及其能覆盖的居民小区编号如表5–2所示，问为覆盖所有小区至少应建多少所小学，要求建模并求解。
表5–12
备选校址代号 覆盖的居民小区编号 A B C D E F 1，5，7 1，2，5 1，3，5 2，4，5 3，6， 4，6， 5.3一货船，有效载重量为24吨，可运输货物重量及运费收入如表5-13所示，现货物2、4中优先运2，货物1、5不能混装，试建立运费收入最多的运输方案。
表5-13 货物 重量（吨） 1 5 2 9 4 3 8 4 4 7 3 5 10 5 6 23 7 收入（万元） 1 5.4 用分支定界法求解下列整数规划问题
（1）maxz?x1?x2 （2）maxz?2x1?3x2
951?x?x??114214?5x1?7x2?35?1?? ?4x1?9x2?30 ??2x1?x2?3??x,x?0且为整数?12?x1,x2?0且为整数??16
5.5用割平面法求解下列整数规划问题
（1）maxz?4x1?6x2?2x3 （2）maxz?11x1?4x2
?5?4x1?4x2??1x1?2x2?4??x?6x?5x?2x?16?5?1?122 ??2x?x?4?x?x?x?5123??12???x1,x2?0且为整数?x1,x2,x3?0且为整数
5.6用隐枚举法解下列0–1规划问题
（1）maxz?3x1?2x2?5x3?2x4?3x5 （2）maxz?2x1?x2?5x3?3x4?4x5
?x1?x2?x3?2x4?x5?4?3x1?2x2?7x3?5x4?4x5?6?7x?3x?4x?3x?8?345?1 ?x1?x2?2x3?4x4?2x5?0 ??3x4?3x5?3?x?0或1j=1,2?5?11x1?6x2???j?xj?0或1?j=1,2?5??
5.7用匈牙利法求解下列指派问题，已知效率矩阵分别如下：
?38791012???87???13121617? ? ?64?15161415?????84?11121516????910?2103??297?275?
?235?6910??
5.8已知下列五名运动员各种泳姿的运动成绩（各为50米）如表5-14所示，请问如何从中选择一个参加200米混合泳的接力队，使预期比赛成绩最好。
表5-14 单位：秒
仰 泳 蛙 泳 蝶 泳 自由泳 赵 钱 张 王 周 37.7 43.4 33.3 29.2 32.9 33.1 28.5 26.4 33.8 42.2 38.9 29.6 37.0 34.7 30.4 28.5 35.4 41.8 33.6 31.1 5.9分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表5-15所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。
17
表5-15 人 任务 甲 乙 丙 丁 A 25 39 34 24 B 29 38 27 42 C 31 26 28 36 D 42 20 40 23 E 37 33 32 45 5.10 从甲、乙、丙、丁、戊五个人中挑选四人完成四项工作。已知每人完成各项工作的时间如表5-16所示。规定每项工作只能由一个人单独去完成，每个人最多承担一项任务。又假定对甲必须保证分配一项任务，丁因某种原因决定不同意承担第4项任务，在满足上述条件下，如何分配工作，使完成四项工作总的花费时间最少。
表5–16
工作 人 1 2 3 4 甲 乙 丙 丁 戊 10 5 15 20 2 10 5 15 3 15 14 13 15 2 7 6 9 4 15 8 5.11 运筹学中著名的旅行商贩（货朗担）问题可以叙述如下：某旅行商贩从某一城市出发，到其他几个城市推销商品，规定每个城市均需到达且只到达一次，然后回到原出发城市。已知城市i和城市j之间的距离为dij问商贩应选择一条什么样的路线顺序旅行，使总的旅程最短。试对此问题建立整数规划模型。
18
第七章 习题
1. 求下列网络图从起点到终点的最短路线及长度。
70
B1 40 10 C1
60 40 20
30 （1） 40 60 A B2 20 C2 30 10
30
40 30
10 B3 C3
50 30 10 E1 4 F1 3 12 3 2 13 （2） 8 8 5 A E2 F2
7 4 7 7 6 E3 F3 6 8
2. 用动态规划方法求解下列问题：
D1 30 E D2 40 G1 9 10 5 B G2 15 8 G3 7 10 C D (1) max z?x1?x2?x3 ?x1?x2?x3?a ??xj?0 (j?1,2,3)2(2) max z?4x1?9x2?2x3
?x1?x2?x3?10
??xj?0 (j?1,2,3)2(3) min z?x13?x2?x3 ?x1?x2?x3?6 ??xj?0 (j?1,2,3)(4) max z?3x1(2?x1)?2x2(2?x2)
?x1?x2?3 ??x1,x2?0且为整数
19
3. 某公司拟投资600万元对下属四个工厂进行技术改造，各工厂改造后的利润与投资额大小关系如表7-22所示，要求确定各厂投资额，使总利润最大。
表7-22 工 投 资 厂 额 0 1 2 3 4 5 6 0 40 100 130 160 170 170 0 40 80 100 110 120 130 0 50 120 170 200 220 230 0 50 80 100 120 130 140 工厂1 工厂2 工厂3 工厂4 4. 有一部货车沿公路的4个零售店共卸下6箱货物，各零售店因出售货物所得利润如表7-23所示。试求在各零售店各卸下几箱货物，能使获得的总利润最大？最大利润是多少？
表7-23 零 售 数 0 1 2 3 4 5 6 0 4 6 7 7 7 7 0 2 4 6 8 9 10 0 3 5 7 8 8 8 0 4 5 6 6 6 6 店 1 2 3 4 箱 5. 设某机器可在高、低不同负荷下生产。若机器在高负荷下生产，则产品的年产量a和投入生产的机器数量x的关系为a=8x，机器的年折损率β=0.3，若机器在低负荷下生产，则产品年产量b和投入生产的机器数量x的关系为b=5x，机器的年折损率α=0.1。设开始时有完好机器1000台，要求制定一个四年计划，每年年初分配完好机器在不同负荷下工作，使四年总产量达到最大。
6. 某厂生产一种产品，该产品在未来4个月的销售量估计如表7-24所示。该产品的生产准备费为每批500元，每件的生产费用为1元，每件的存贮费为每月1元，假定1月初的存货为100件，5月初的存货为0，求该厂在这4个月内的最优生产计划。
表7-24 月份 销售量（百件）
1 4 2 5 3 3 4 2 20