北 京 交 通 大 学 考 试 试 题 答 案（A卷）——运筹学A
一、单选题
5分，每题1分。 二
1．设甲、乙产品的产量分别为x1，x2件，线性规划模型为：
max z=3x1+2x2
s.t. 2x1+4x2?160 3x1+2x2?180
x1 , x2?0
标准型及单纯形计算如下：
max z=3x1+2x2 s.t. 2x1+4x2+x3=160 3x1+2x2+x4=180
x1 , x2, x3, x4?60 x1 x2 x3 x4 2 3 3 0 1 0 0 1 0 4* 2 2 8/3 2/3 0 1 0 0 1 0 0 1 0 0 0 1 0 -2/3 1/3 -1 XB B-1b x3 x4 160 180 0 X3 40 X1 60 x2 x1 -180 15 50 -180 3/8 -1/4 -1/4 1/2 0 -1 最优方案为甲生产50件，乙生产15件，或甲生产60件，乙生产0件，或上述两种方式的凸组合。最大利润为180。
15分，模型5分，标准型与初始表5分，计算3分，结论2分。 2．影子价格分别为0和1
4分，各2分，计算错误扣1分。
3．产品丙的检验数为－1，不值得生产。 5分，公式2分，计算2分，结论1分。
第 1 页 共 14 页
4．原料B的灵敏度范围0-240，最多应购买60千克。 6分，公式2分，计算3分，结论1分。 三、（15分）
①正确列出运价表如右：7分 B1 B2 B3 虚拟 ②最小元素法方案3分 A1 6 4 6 0 300 ③位势法求检验数4分 A2 6 M 5 0 300 ④给出正确的调运方案1分
150 150 200 100 A1 A2 B1 150 B2 M-4 150 B3 +1 200 100 虚拟 A1 A2
四、（10分）分配甲、乙、丙三个人去完成A、B、C、D四项任务，每个人完成各项任务的时间如表所示。其中任务D必须完成，且每个人只能完成一项任务，每项任务只能由一个人完成。试确定最优分配方案，使完成任务的总时间最少。
①正确列出效益表如右：5分 ②匈牙利法计算结果3分 ③给出正确的分配方案2分
任务 A B C D 0 0 0 0 8 10 21 1 人 0 0 0 1 15 19 6 0 20 28 30 41 甲 乙 丙 虚拟 35 30 0 39 26 20 27 28 40 0 0 M 0 0 1 0 0 1 0 0 3 0 0 0 1 0 13 M B1 50 100 B2 150 B3 × 虚拟 300 0 300 100 300 × 300 100 × 200 150 150 200
第五题
定义状态：s1=x1+s2 s2=x2+s3 s3=x3 故 s1<=8（3分） k=3时f3(s3)=Max {4*x3} ，此时 0<=x3<=s3
第 2 页 共 14 页
即x3=s3时 f3(s3)=4＊s3（3分）
k=2时f2(s2)=Max {3*x2+f3(s3)}= Max {3*x2+4*(s2-x2)} 0<=x2<=s2 即x2=0时 f2(s2)=4＊s2（3分）
k=3时f1(s1)=Max {x1*x1+ f2(s2)}=Max{x1*x1-4*x1+4*s1} ，此时 0<=x1<=s1 由于s1<=8，故x1=s1＝8时 f1(s1)=64（3分）
因此，x1=8, x2=0, x3=0时z取得最大值，最大值为64。（3分）
第六题
用最小数问题求解（3分）。理由：将各区域作为点，各区域间的连线作为边，不可以包含圈，目标位所修路纵长最短，最短路问题能解决这一种问题。（2分） 用避圈法求解可得1－5－4, 2－3－8－7－6为最佳修路方案，总长5.2. （5分）
第七题
A12CD4F7IB（6分） 工序 A B C D E F G H I 3E5H6 最早可以开工时间 0 0 5 5 2 7 7 7 10 最晚必须完工时间 5 4 12 7 7 14 14 10 14 （5分） 关键工序：A-D-H-I（3分），总工期14（1分）。
第 3 页 共 14 页