1、第 1 页 共 14 页北 京 交 通 大 学 考 试 试 题 答 案（A 卷）运筹学 A一、单选题5 分，每题 1 分。二1设甲、乙产品的产量分别为 x1，x2 件，线性规划模型为： max z=3x1+2x2s.t. 2x1+4x21603x1+2x2180x1 , x20标准型及单纯形计算如下： max z=3x1+2x2s.t. 2x1+4x2+x3=1603x1+2x2+x4=180x1 , x2, x3, x460XB B-1b x1 x2 x3 x4x3x4160180234*210010 3 2 0 0X3X14060018/32/310-2/31/3-180 0 0 0 -1
2、x2x1155001103/8-1/4-1/41/2-180 0 0 0 -1最优方案为甲生产 50 件，乙生产 15 件，或甲生产 60 件，乙生产 0 件，或上述两种方式的凸组合。最大利润为 180。15 分，模型 5 分，标准型与初始表 5 分，计算 3 分，结论 2 分。2影子价格分别为 0 和 14 分，各 2 分，计算错误扣 1 分。3产品丙的检验数为1，不值得生产。5 分，公式 2 分，计算 2 分，结论 1 分。第 2 页 共 14 页4原料 B 的灵敏度范围 0-240，最多应购买 60 千克。6 分，公式 2 分，计算 3 分，结论 1 分。三、 （15 分）正确列出运价表
3、如右：7 分最小元素法方案 3 分位势法求检验数 4 分给出正确的调运方案 1 分四、 （10 分）分配甲、乙、丙三个人去完成 A、B、C、D 四项任务，每个人完成各项任务的时间如表所示。其中任务 D 必须完成，且每个人只能完成一项任务，每项任务只能由一个人完成。试确定最优分配方案，使完成任务的总时间最少。正确列出效益表如右：5 分匈牙利法计算结果 3 分给出正确的分配方案 2 分第五题定义状态：s1=x1+s2 s2=x2+s3 s3=x3 故 s1=8（3 分）k=3 时 f3(s3)=Max 4*x3 ，此时 0=x3=s3B1 B2 B3 虚拟A1 6 4 6 0 300A2 6 M
4、5 0 300150 150 200 100B1 B2 B3 虚拟A1 50 150 100 300A2 100 200 300150 150 200 100B1 B2 B3 虚拟A1 +1 300A2 M-4 0 300150 150 200 100任务人 A B C D甲 20 28 30 41乙 35 39 26 20丙 30 27 28 40虚拟 0 0 0 M1 0 0 00 0 0 10 1 0 00 0 1 00 8 10 2115 19 6 03 0 1 130 0 0 M第 3 页 共 14 页即 x3=s3 时 f3(s3)=4s3 （3 分）k=2 时 f2(s2)=Ma
5、x 3*x2+f3(s3)= Max 3*x2+4*(s2-x2) 0=x2=s2即 x2=0 时 f2(s2)=4s2（3 分）k=3 时 f1(s1)=Max x1*x1+ f2(s2)=Maxx1*x1-4*x1+4*s1 ，此时 0=x1=s1由于 s1=8，故 x1=s18 时 f1(s1)=64（3 分）因此，x1=8, x2=0, x3=0 时 z 取得最大值，最大值为 64。 （3 分）第六题用最小数问题求解（3 分） 。理由：将各区域作为点，各区域间的连线作为边，不可以包含圈，目标位所修路纵长最短，最短路问题能解决这一种问题。 （2分）用避圈法求解可得 154, 23876
6、为最佳修路方案，总长 5.2. （5 分）第七题 1 63 5 742A C FB E H ID（6 分）工序 最早可以开工时间 最晚必须完工时间A 0 5B 0 4C 5 12D 5 7E 2 7F 7 14G 7 14H 7 10I 10 14（5 分）关键工序：A-D-H-I（3 分） ，总工期 14（1 分） 。第 4 页 共 14 页北 京 交 通 大 学 考 试 试 题（A 卷）专业： 班级： 学号： 姓名： 课程名称：管理运筹学（A） 20062007 学年第 2 学期 出题教师：丁静之题号 一 二 三 四 五 六 七 总分得分签字一、单选题（每题 2 分，共 10 分，答案一律
7、写在答题纸上，否则无效） 。1. 存贮论研究对象包括（ ） 。AA订货时间和订货数量 B订货数量和订货人员 C订货品种和订货数量 D订货人员和订货费用2. 下列有关图解评审法（GERT）说法正确的是（ ） 。DAGERT 适用于确定型网络计划 BGERT 中不包含回路CGERT 中各事项有严格的时间先后关系 DGERT 只有一个总开工事项3. 经济订购批量（2单次订货费单位时间需求量单位时间单位数量物资存贮费） 12 ，这一结论的产生基于一定的假设，这些假设不包括（ ） 。CA不允许缺货 B存储费率不变 C以特定的速度生产来补充库存 D需求是连续均匀的4. 存贮论模型可按不同方式进行分类，但一
8、般不包括（ ） 。BA确定型存贮模型与随机型存贮模型 B简单存贮模型与复杂存贮模型C单品种存贮模型与多品种存贮模型 D单周期存贮模型与多周期存贮模型5.下列说法正确的是（ ） 。DA动态规划求解的问题可以无后效性，也可以有后效性。B图论中，最大流问题实质是一种非线性规划问题。C割平面解法可以求解纯整数规划问题，也可以求解混合整数规划问题。第 5 页 共 14 页D线性规划中，当约束条件系数矩阵中不含有单位矩阵时，可以采用大 M法求解，也可以采用两阶段法求解，但求解结果一定是相同的。二、（共 30 分）某厂用 A、 B 两种原料生产甲、乙两种产品，生产消耗参数如下。根据生产安排，甲产品每天至少生
9、产 3 吨，乙产品每天至少生产 1 吨。两种原料都需要采购，每吨 A 原料需 2 万元，每吨 B 原料需 3 万元。每吨 A原料可生产 1 吨甲产品和 2 吨乙产品，1 吨 B 原料和 1 吨乙产品可生产 2 吨甲产品。产品原料甲（吨）乙（吨）采购费（万元吨）A 1 2 2B 2 1 3产量（吨） 3 1（1）如何安排两种原料采购（采购的材料都用于生产），使该厂采购总额最小？请建立线性规划模型并用图解法求解；（2）请用对偶单纯形法求解上述模型并指出最小采购总额时两种原料采购数量。（3）假设市场上原料 C 的价格为 4 万元吨，每吨 C 原料可生产 2 吨甲产品和 2 吨乙产品。是否应采购 C
10、原料？请说明理由。三、 （共 10 分）已知某运输问题的产销平衡表如下。产量和销量单位均为：件；运价单位为：元/件。销地单位运价产地B1 B2 B3 产量A1A28745652230销量（件） 25 15 20（1）用最小元素法求出初始调运方案？（2）位势法进行检验，并找到最优运输方案。四、 （共 10 分）派五人去做五项工作，各人做各项工作的能力评分见表。如何分派，总的得分最大？第 6 页 共 14 页评分 工作人员 B 1B 2B 3B 4B 5A 11.3 0.8 0 0 1.0A 20 1.2 1.3 1.3 0A 31.0 0 0 1.2 0A 40 1.05 0 0.2 1.4A
11、51.0 0.9 0.6 0 1.1五、 （共 15 分）现有资金 5 百万元，可对三个项目进行投资，投资额均为整数（单位为百万元） 。其中 2#项目的投资不得超过 3 百万元，1#和 3#项目的投资均不得超过 4 百万元，3#项目至少要投资 1 百万元。每个项目投资五年后，预计可获得的收益如下表所示。如何投资可望获得最大收益？请用动态规划方法求解。 投资额项目0 1 2 3 4 51# 0 3 6 10 12 2# 0 5 10 12 3# 4 8 11 15 18六、 （共 15 分）某高校在某地区有五个不同的校区，包括一个主校区和四个分校区。学校决定在各校区之间铺设光缆以形成校园网。主校
12、区与各分校区之间都要保持光缆连接畅通。四个分校区之间距离较近，可以直接铺设光缆。但主校区与四个分校区距离较远。学校请示相关主管部门后得知，主校区可通过四个中转点铺设光缆然后与分校区 2 相连接，进而再与其它三个分校区保持连接。各校区、各中转点之间的距离如下图所示，单位为公里。没有线条相连接的节点之间不能铺设光缆。为使所消耗的光缆总长度最小，请用图论的知识指出最优铺设方案并说明理由。至少需要多少公里长度的光缆？第 7 页 共 14 页主 校区 中 转点 1 分 校区 4分 校区 3分 校区 2分 校区 1中 转点 4中 转点 3中 转点 230 5030 4050 207015 304 1257
13、39七、 （共10分）某工程项目的工序清单如下（工时单位：天）：工序代号 紧前工序 工时 工序代号 紧前工序 工时ABCDEAAB1512121213FGHICD,ED,EH12151314（1）绘制双代号网络图；（2）计算工序的最早可能开始时间和最迟必须完成时间；（3）指出关键工序和总工期。（4）要将总工期压缩2天，应该如何做？第 8 页 共 14 页2007 年本科试题（A） 64 学时A 卷一、选择题。每题 2 分，共 10 分。 ADCBD二、（1）设 A 原料采购量为 x1, B 原料采购量为 x2。模型如下（8 分）：Min Z= 2 X1+3X2X1+2X232X1- X21X1
14、,X20图解法（7 分）可知：X11 ，X2 2，此时 Z 取得最小值，最小值为 5。即采购 A、B 原料各 1 套，最小采购额为 5 万元。X1X20（2）（10 分）上述模型可化为:Max W= 2 X13X2X12X2X3 32X1 X2 X41X1,X2，X3,X402 3 0 0CB XB b X1 X2 X3 X40 X3 3 1 2 1 0第 9 页 共 14 页0 X4 1 2 1 0 12 3 0 03 X2 32 12 1 12 00 X4 52 52 0 12 112 0 32 03 X2 1 0 1 25 152 X1 1 1 0 15 250 0 85 15最优解为
15、X11，X22，此时 Z 取得最小值，最小值为 5。（3） （5 分）设 C 原料的采购量为 X5，则 P5（2，2） TC54 CB（3，2） B1 5 C 5C B B1 P525 0 故不应该采购 C 原料。加入一个虚设的产地，转化为供需平衡的运输问题，有虚设的产地到销地的运费为在各销地寻找货源所多花的费用。供需平衡表如下。 （4 分）B1 B2 B3 产量（件）A1 8 4 6 22A2 7 5 5 30A3 1 2 2 8销量（件） 25 15 20 60用最小元素发法求的初始运输方案。 （2 分）B1 B2 B3 产量（件）A1 7 15 22A2 10 20 30A3 8 8销量
16、（件） 25 15 20 60上述方案的位势法检验。 位势表B1 B2 B3 vjA1 8 4 8A2 7 5 7A3 1 1ui 0 -4 -2检验数表（2 分）第 10 页 共 14 页B1 B2 B3 vjA1 0 8A2 2 7A3 5 3 1ui 0 -4 -2由检验数可知，上述方案是最优运输方案。（2 分）即由 A1 运往 B1： 7 件，运往 B2：15 件；A2 运往 B1： 10 件，运往 B3：20 件；B1 有 8 件的需求尚未满足，需要在当地寻找货源。总运费 56+70+60+100=286 元四、原效益矩阵转化成最小问题（2 分） 1.06.91420.3.108311.06.91420.3.83划线覆盖全部的零元素（2 分）01.52.01432. 3.01.50调整（2 分） 分派（2 分）
