运筹学期末考试试卷(AB)卷

1、-作者xxxx-日期xxxx运筹学期末考试试卷(AB)卷【精品文档】福建农林大学考试试卷 （ A ）卷 学年 第 学期课程名称： 运 筹 学 考试时间 120分钟 专业 年级 班 学号 姓名 题号一二三四五六七八九总得分得分评卷人签字复核人签字得分一、填空题（每空2分，共10分）1. 目标规划模型中，对目标约束，求最大的目标函数为。2. 增广链上的调整量 大于 零。3. 用Dijkstra算法求解最短路问题时，距离矩阵的元素必须满足 非负要求 。4. 线性规划的退化基本解的非零分量 至多m 个。5. 树是 无圈 的连通图。得分二、单项选择题（选择正确答案的字母填入空格，每小题2分，共10分）1

2、. 线性规划的基本解中，非基变量取 C 值。A零 B非零C非负 D非正 B 下定义的。A零流 B可行流C不可行流 D非零流3. 在约束为的线性规划中, ，则基的最小数目为 D 。A B0Cm D14. 互为对偶的两个线性规划问题，如果其中一个无有限最优解，则另外一个 A 。A无可行解 B有可行解C有最优解 D无有限最优解5. 如果目标规划问题（OP）没有满意解，则 A 。A（OP）无可行解 B（OP）有可行解C（OP）有无穷多最优解 D（OP）可能有可行解得分四、问答题（每小题5分，共20分）1. 对偶单纯形法的求解要点。建立初始规范型（检验数非正，有负的限定常数），转。解的检验：出现无可行解

3、特征，停止；限定常数非负，转单纯型法；其他转。进行基变换，转。2.最大流算法中流量调整量的确定。设为可行流，在f下进行标号，如果无法给vt标上号，为最大流，无需确定流量调整量，否则。3.网络计划中时差的计算。可以据下图计算：ESijEFijLSijLFij(Lj)TFijFFijEj4. 最短路问题的基础数据与求解内容。距离矩阵；最短路线，最短路长。得分五、（第一小题2分，第二小题5分，第三小题3分，共10分）对：要求：1. 写出；2. 用单纯形法或对偶单纯形法确定或的最优解；3. 从或的最终表出发，据对偶理论直接确定或的解。：解：1. ：2. 选择用单纯形法或确定的最优解；cj2 1 0 0

4、 cBxBbx1 x2 x3 x4 00x3x41015 1 1 00 1 0 110/1-z02 1 0 0cj2 1 0 0 cBxBbx1 x2 x3 x4 20x1x41015 1 1 00 1 0 1-z-200 -1 -2 0。选择用对偶单纯形法确定的最优解；cj-10 -15 0 0 cBxBby1 y2 y3 y4 00y3y4-2-1-1 0 1 0-1 -1 0 1w0-10 -15 0 0 - - -cj-10 -15 0 0 cBxBby1 y2 y3 y4 -100y1y4 211 0 -1 00 -1 -1 1w200 -15 -10 0 得分六、对图1，求网络图的

5、最大流。（共10分）vsvtv1v2v3(4,0)(6,0)(3,0)(8,0)(3,0)(5,0)(8,0)(cij,fij)图1解： 取，用标号法确定如图2所示,由图2知，见图3。用标号法确定如图3所示,由图3知，见图4。用标号法确定如图4所示,由图4知，不存在，故。vsvtv1v2v3(0,4)(0,6)(0,3)(0,8)(0,3)(0,5)(0,8)图2(-,+)(vs,6),5)(v1,6),5)(v3,6),5)vsvtv1v2v3(0,4)(6,6)(0,3)(6,8)(0,3)(0,5)(6,8)图3(-,+)(vs,4),5)(v2,4),5)vsvtv1v2v3(4,4)

6、(6,6)(0,3)(6,8)(0,3)(4,5)(6,8)图4(-,+)得分七、对表1，用动态规划方法确定最优策略（共10分）考虑一辆汽车三年的设备更新策略，开始时现有汽车的机龄为2年，取1，其余有关数据见表1。试制定三年中的设备更新策略，使三年内的净收入最大。表1年代期 前第一年第二年第三年阶 段1 2 31 2 32 3 3机 龄2 3 40 1 20 1 0收 入20 18 1822 21 2027 2529运行费用10 10 116 6 85 65更新费用38 38 4030 32 3731 3533解：模型假设略。34*18-110295-4007K*2208029537+012K

7、1256029535+019K23*1810727538+1915K*12161227532+1927K12*2010+1522-638+2725K*得分八、（10分）表2是某厂原材料和产品规格的基础数据，要求建立一个线性规划模型，以确定净收入最大的产品方案。（不求解）表2产品规格要求原料成本单价（元/kg）可用量（kg）甲 乙 丙原材料ABC80 5020 60 50300200100200025001500加工费（元/kg）售价（元/kg）模型略，具体可参考P38例11。得分九、视图1的问题中为aij的长度，要求用Dijkstra算法确定vs到vt的最短路。 （共10分）解1：用标号法：vsvtv1v2v38123143914图5最短路线，最短路长17。解2：列表求解：i js123ts0128+1+0314+2+0393+014t+0i js123t1，2345最短路线，最短路长17。得分九、（10分）某部门在今后5年内考虑给下述项目投资，已知：项目1，从第1年到第4年年末可以投资，并于次年年末收回本利106，但每年的投资限额为3万元；项目2，第0年年末可以投资，并于第5年年末收回本利151；项目3，从第2年年末可以投资，并于第5年年末收回本利150；项目4，5年内每年年初可以购买公债，并于当年