因为解(3.5,2)满足x2为整数条件，并且目标函数值是两个子问题中最大，故原问题的最
优解为(3.5,2).
(2) 从甲, 乙, 丙, 丁, 戊五人中挑选四人去完成四项工作，已知每人完成各项工作的时间如下表所示。规定每项工作只能由一个人去单独完成，每个人最多承担一项工作，假定甲必须保证分配到工作，丁因某种原因不同意承担第四项工作。在满足上述条件下，如何分配工作，使完成四项工作总的花费时间最少。（20分）
人 工作 甲 乙 丙 丁 戊 10 2 3 15 9 5 10 15 2 4 15 5 14 7 15 20 15 13 6 8 一 二 三 四 18. 解：
10 5 15 20 M 8 3 10 12 M 5 0 7 9 M-3 2 10 5 15 0 0 8 0 7 0 0 8 0 7 0 3 15 14 13 0 ~ 1 13 9 5 0 ~ 1 13 9 5 0 ~ 15 2 7 M 0 13 0 2 M-8 0 13 0 2 M-8 0 9 4 15 8 0 7 2 10 0 0 7 2 10 0 0
4 0 6 8 M-3 0 9 0 7 1 0 13 8 4 0 12 0 1 M-9 0 7 3 10 0 1
此时，费用最小，Z?3?5?5?8?21
其中，丙做第一事， 甲做第二事， 乙做第三事， 戌做第四事
（3）求解0-1规划问题：
*maxz?3x1?2x2?5x3?x1?2x2?x3?2??x1?4x2?x3?4?s..t?x1?x2?3?4x?x?6?23??x1,x2,x3?0或1
解：易看出(x1,x2,x3)?(0,0,0)满足约束条件，故为一个可行解，且相应的目标函数值为z0?0。因为是求极大值问题，应增加一个约束条件（目标值下界）：
求解过程可由下表来表示：
3x1?2x2?5x3?0，
(x1,x2,x3) (0,?0,?0) (0,?0,1)? (0,1,??0) (0,1?,1)? (1,?0,?0) (1,?0,1)? (1,1?,?0) (1,1,1)?? *z 值 0 5 -2 3 3 8 1 6 T过滤条件 a — √ × × × √ × × 约束条件 b c d e √ √ √ √ √ √ √ √ √ √ √ √ √ 修正过滤条件 a z?0 z?5 z?8 ?，最优值z*?8。 从而得最优解x?(1,?0,1)
4. （10分）（二选一）（1）设图中各弧上数为距离，求v1到v9的最短距离与最短路径。 （2）设图中各弧上数为容量，求v1到v9的最大流量。
（1） 标号过程：略；
最短路为：v1→ v2→v6→v9，最短距离为8.5 （2）标号过程：略；
最大流量为6， 最小割集为：(S,T)={(v1,v2),(v4,v7)}，其中S={v1,v4}，T={v2,v3,v5,v6,v7,v8,v9} 割量为：C(S,T)=3+3=6. 最大流量方案（答案不唯一）：f13=3, f14=3, f23=3, f39=3, f47=3, f78=1, f79=2, f89=1，其余为零。
下面二题选一：
下表为一机械加工工序，试画出PERT网络图，并计算时间参数和确定关键路线。 作业代码 作业名称 紧前作业 作业时间（天） A 项目设计 4 — B 外购包装材料 A 8 C 清理场地 A 7 D 外购零配件 A 6 E 机加工2人员培训 A 9 F 木模、铸件 C 15 G 机加工1 D 12 H 机加工2 D、E 8 I 工装制造 G 10 J 装配、调试 B、F、H、I 4
关键工序：A,C,F,J
关键路线：1?2?3?7?8 工程完工期限：38
某农场要决定一块地中选择什么作物，条件如下，如何决策？
（1）分别用乐观法、悲观法、等可能法与最小后悔值法对生产方案作出决策。
（2）根据往年天气资料，旱、正常和多雨三种天气的概率分别为0.2、0.7和0.1，求利润期望最大和后悔期望最小的策略。
答：利润表如下表所示。 蔬菜 旱 0.2 1000 正常 0.7 4000 多雨 0.1 7000 7000 1000 Max min 等可能法 4000 利润期望值 3700 小麦 棉花 2000 3000 5000 6000 3000 2000 5000 6000 2000 2000 3333 3667 4200 6800 乐观法（大中取大）：最佳方案为：蔬菜 悲观法（小中取大）：最佳方案为：小麦或棉花 等可能法：最佳方案为：蔬菜
最大利润期望值法：最佳方案为：棉花
后悔值如下表所示。 蔬菜 小麦 棉花 旱 0.2 2000 1000 0 正常 0.7 2000 1000 0 多雨 0.1 0 4000 5000 2000 4000 5000 Max 损失期望值 1800 1300 500 最小后悔值法：最佳方案为：蔬菜 最小损失期望值法：最佳方案为：棉花
四 、建立下面问题的数学模型（9分）
1. 某造船厂根据合同从当年起连续三年末各提供四条规格相同的大型客货轮。已知该厂这
三年内生产大型客货轮的能力及每艘客货轮成本如下表所示：
年度 1 2 3 正常生产时间内可完成的客货轮数 3 5 2 加班生产时间内可完成的客货轮数 3 2 3 正常生产时每艘成本（万元） 500 600 500 已知加班生产时,每艘客货轮成本比较正常时高出60万元；又知造出来的客货轮若当年不交货,每艘每年积压一年造成损失为30万元。在签定合同时，该厂已积压了两艘未交货的客货轮，而该厂希望在第三年未完成合同还能储存一艘备用。问该厂如何安排每年客货轮的生产量，在满足上述各项要求的情况下总的生产费用最少？
答案：
设第i年正常生产xi艘，加班生产yi艘，交付后储贮zi艘
产销存平衡：
xi?yi?zi?1?zi?4,?i?1,2,3z0?2,z3?10?x1?3,?0?y1?3
加工能力限制：0?x2?5,0?y2?2
0?x3?2,0?y3?3目标函数：w?500x1?600x2?500x3?560y1?660y2?560y3?30(z0?z1?z2)
已知一个工厂生产A、B两类产品，每件产品生产需消耗三种资源，现已知单位产品获利、单位产品消耗资源和当前资源限制如下表:
型号 工序 每周最大 A B 加工能力（小时） 甲（小时/台） 2 乙（小时/台） 1 0 1 0 1 140 60 100 丙（小时/台） 利润（元/台） 30 12
现有下列目标：
1. 要求总利润必须超过 2500 元；
2. 考虑产品受市场影响，为避免积压，A、B的生产量不超过 60 件和 100 件； 3. 由于甲资源供应比较紧张，不要超过现有量140小时。 试建立目标规划模型。
运筹学2020最新试卷带答案
