交大运筹学2套往年试卷及答案包含各题型期末考试绝对有用.doc

北 京 交 通 大 学 考 试 试 题 答 案（A卷）运筹学A一、单选题5分，每题1分。二1设甲、乙产品的产量分别为x1，x2件，线性规划模型为： max z=3x1+2x2s.t. 2x1+4x2160 3x1+2x2180x1 , x20标准型及单纯形计算如下： max z=3x1+2x2s.t. 2x1+4x2+x3=160 3x1+2x2+x4=180x1 , x2, x3, x460XBB-1bx1x2x3x4x3x4160180234*2100103200X3X14060018/32/310-2/31/3-180000-1x2x1155001103/8-1/4-1/41/2-180000-1最优方案为甲生产50件，乙生产15件，或甲生产60件，乙生产0件，或上述两种方式的凸组合。最大利润为180。15分，模型5分，标准型与初始表5分，计算3分，结论2分。2影子价格分别为0和14分，各2分，计算错误扣1分。3产品丙的检验数为1，不值得生产。5分，公式2分，计算2分，结论1分。4原料B的灵敏度范围0-240，最多应购买60千克。6分，公式2分，计算3分，结论1分。三、（15分）B1B2B3虚拟A16460300A26M50300150150200100正确列出运价表如右：7分最小元素法方案3分B1B2B3虚拟A150150100300A2100200300150150200100位势法求检验数4分给出正确的调运方案1分B1B2B3虚拟A1+1300A2M-40300150150200100四、（10分）分配甲、乙、丙三个人去完成A、B、C、D四项任务，每个人完成各项任务的时间如表所示。其中任务D必须完成，且每个人只能完成一项任务，每项任务只能由一个人完成。试确定最优分配方案，使完成任务的总时间最少。正确列出效益表如右：5分匈牙利法计算结果3分给出正确的分配方案2分任务人ABCD甲20283041乙35392620丙30272840虚拟000M100000010100001008102115196030113000M第五题定义状态：s1=x1+s2 s2=x2+s3 s3=x3 故 s1=8（3分）k=3时f3(s3)=Max 4*x3 ，此时 0=x3=s3即x3=s3时 f3(s3)=4s3（3分）k=2时f2(s2)=Max 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为最佳修路方案，总长5.2. （5分）第七题（6分）工序最早可以开工时间最晚必须完工时间A05B04C512D57E27F714G714H710I1014（5分）关键工序：A-D-H-I（3分），总工期14（1分）。北 京 交 通 大 学 考 试 试 题（A卷）专业： 班级： 学号： 姓名： 课程名称：管理运筹学（A）20062007学年第2学期 出题教师：丁静之题号一二三四五六七总分得分签字一、 单选题（每题2分，共10分，答案一律写在答题纸上，否则无效）。1. 存贮论研究对象包括（ ）。AA订货时间和订货数量 B订货数量和订货人员 C订货品种和订货数量 D订货人员和订货费用2. 下列有关图解评审法（GERT）说法正确的是（ ）。DAGERT适用于确定型网络计划 BGERT中不包含回路CGERT中各事项有严格的时间先后关系 DGERT只有一个总开工事项3. 经济订购批量（2单次订货费单位时间需求量单位时间单位数量物资存贮费）12，这一结论的产生基于一定的假设，这些假设不包括（ ）。CA不允许缺货 B存储费率不变 C以特定的速度生产来补充库存 D需求是连续均匀的4. 存贮论模型可按不同方式进行分类，但一般不包括（ ）。BA确定型存贮模型与随机型存贮模型 B简单存贮模型与复杂存贮模型C单品种存贮模型与多品种存贮模型 D单周期存贮模型与多周期存贮模型5.下列说法正确的是（ ）。DA动态规划求解的问题可以无后效性，也可以有后效性。B图论中，最大流问题实质是一种非线性规划问题。C割平面解法可以求解纯整数规划问题，也可以求解混合整数规划问题。D线性规划中，当约束条件系数矩阵中不含有单位矩阵时，可以采用大M法求解，也可以采用两阶段法求解，但求解结果一定是相同的。二、（共30分）某厂用A、B两种原料生产甲、乙两种产品，生产消耗参数如下。根据生产安排，甲产品每天至少生产3吨，乙产品每天至少生产1吨。两种原料都需要采购，每吨A原料需2万元，每吨B原料需3万元。每吨A原料可生产1吨甲产品和2吨乙产品，1吨B原料和1吨乙产品可生产2吨甲产品。 产品原料甲（吨）乙（吨）采购费（万元吨）A122B213产量（吨）31（1）如何安排两种原料采购（采购的材料都用于生产），使该厂采购总额最小？请建立线性规划模型并用图解法求解；（2）请用对偶单纯形法求解上述模型并指出最小采购总额时两种原料采购数量。（3）假设市场上原料C的价格为4万元吨，每吨C原料可生产2吨甲产品和2吨乙产品。是否应采购C原料？请说明理由。三、（共10分）已知某运输问题的产销平衡表如下。产量和销量单位均为：件；运价单位为：元/件。销地单位运价产地B1B2B3产量A1A28745652230销量（件）251520（1）用最小元素法求出初始调运方案？（2）位势法进行检验，并找到最优运输方案。四、（共10分）派五人去做五项工作，各人做各项工作的能力评分见表。如何分派，总的得分最大？评分 工作人员BBBBBA1.30.8001.0A01.21.31.30A1.0001.20A01.0500.21.4A1.00.90.601.1五、（共15分）现有资金5百万元，可对三个项目进行投资，投资额均为整数（单位为百万元）。其中2#项目的投资不得超过3百万元，1#和3#项目的投资均不得超过4百万元，3#项目至少要投资1百万元。每个项目投资五年后，预计可获得的收益如下表所示。如何投资可望获得最大收益？请用动态规划方法求解。投资额项目 0 1 2 3 45 1# 0 3 6 10 12 2# 0 5 10 12 3# 4 8 11 1518六、（共15分）某高校在某地区有五个不同的校区，包括一个主校区和四个分校区。学校决定在各校区之间铺设光缆以形成校园网。主校区与各分校区之间都要保持光缆连接畅通。四个分校区之间距离较近，可以直接铺设光缆。但主校区与四个分校区距离较远。学校请示相关主管部门后得知，主校区可通过四个中转点铺设光缆然后与分校区2相连接，进而再与其它三个分校区保持连接。各校区、各中转点之间的距离如下图所示，单位为公里。没有线条相连接的节点之间不能铺设光缆。为使所消耗的光缆总长度最小，请用图论的知识指出最优铺设方案并说明理由。至少需要多少公里长度的光缆？七、（共10分）某工程项目的工序清单如下（工时单位：天）：工序代号紧前工序工时工序代号紧前工序工时ABCDEAAB1512121213FGHICD,ED,EH12151314（1）绘制双代号网络图；（2）计算工序的最早可能开始时间和最迟必须完成时间；（3）指出关键工序和总工期。（4）要将总工期压缩2天，应该如何做？ 2007年本科试题（A）64学时A卷一、选择题。每题2分，共10分。 ADCBD二、（1）设A原料采购量为x1, B原料采购量为x2。模型如下（8分）：Min Z= 2 X1+3X2 X1+2X23 2X1- X21 X1,X20图解法（7分）可知：X11，X22，此时 Z取得最小值，最小值为5。即采购A、B原料各1套，最小采购额为5万元。（2）（10分）上述模型可化为:Max W= 2 X13X2 X12X2X3 3 2X1 X2 X41 X1,X2，X3,X402300CBXBbX1X2X3X40X3312100X41210123003X2321211200X4525201211203203X210125152X11101525008515最优解为X11，X22，此时 Z取得最小值，最小值为5。（3）（5分）设C原料的采购量为X5，则P5（2，2）TC54 CB（3，2） B15 C5CB B1 P525 0 故不应该采购C原料。加入一个虚设的产地，转化为供需平衡的运输问题，有虚设的产地到销地的运费为在各销地寻找货源所多花的费用。供需平衡表如下。（4分）B1B2B3产量（件）A184622A275530A3 1228销量（件）25152060 用最小元素发法求的初始运输方案。（2分）B1B2B3产量（件）A171522A2102030A3 88销量（件）25152060上述方案的位势法检验。 位势表B1B2B3vjA1848A2757A3 11ui0-4-2 检验数表（2分）B1B2B3vjA108A227A3 531ui0-4-2由检验数可知，上述方案是最优运输方案。（2分）即由A1运往B1： 7件，运往B2：15件；A2运往B1： 10件，运往B3：20件；B1有8件的需求尚未满足，需要在当地寻找货源。总运费56+70+60+100=286元四、原效益矩阵 转化成最小问题（2分） 划线覆盖全部的零元素（2分） 调整（2分） 分派（2分） （2分）最优分配方案：A1-B1,A2-B3,A3-B4A4-B5,A5-B2, 最大的得分：1.3+1.3+1.2+1.5+0.9=6.2五、（6分）按投资项目划分3个阶段，sk表示从k阶段到第三阶段可以用于投资的资金，xk为第k个项目的投资金额。则状态转移方程为，基本方程为：（2分）k=3 x3s3g3(x3)f3(s3)x3123412345481115154811151512344（2分）k=2 x2s2g2(x2)+ f3(s3)f2(s2)x20123123450+40+80+110+150+155+45+85+115+1510+410+810+1112+412+84914182101222（2分）k=1 x1s1g1(x1)+ f2(s2)f1(s1)x10123450+213+186+1410+912+4210,1（3分）最优方案两个：项目1不投资，项目投资2百万，项目3投资3百万；项目1投资1百万，项目投资2百万，项目3投资2百万；最大收益为21。六、解题思路（5分）：要保持主校区与各分校区之间光缆的畅通，必须使得这五个节点之间保持连通。图中，主校区与分校区2之间距离较远，其中可通过几个中转点进行连接，但这些中转点不是必须都纳入保持连通。因此，可将四个分校区作为一部分（四个分校区作为四个点，它们相互间的连线作为边，各边的距离作为该边的权），求它们的最小树。然后将主校区、分校区2和四个中转点作为一部分（主校区、分校区2和四个中转点作为六个点，它们相互间的连线作为边，各边的距离作为该边的权），求主校区到分校区2的最短路。最小树、最短路中所包含的边即为铺光缆的路径，最小树的权与最短路长之和为光缆的总长度。（4分）V0至V2间的最短路为：V 0V 6V 8V2，路长为85公里。（4分）最小树为：V1V2，V2V3，V1V4，权为6公里。（2分）所以光缆铺设路径为：主校区中转站2中转站4分校区2分校区1分校区4和分校区2分校区3，共需要光缆91公里。七、（1）（5分）132BA5CDE4FGH671512121213121513I14（2）（2分）工序代号ESLF工序代号ESLFABCDE001515121514422727FGHI2727274054544054（3）（2分）关键工序A、D、H、I，总工期是54天。（4）（1分）应在关键工序上压缩2天。第 14 页 共 14 页