《山东大学运筹学(A卷)课程试卷》由会员分享，可在线阅读，更多相关《山东大学运筹学(A卷)课程试卷（3页珍藏版）》请在金锄头文库上搜索。
1、得分阅卷人山东大学 运筹学 (A 卷) 课程试卷 课程号 82154000 2011-2012 学年 第一 学期题号一二三四五六七八总分复核人得分一、判断题（每小题 1 分，共 10 分）（1）割平面方法可以解决混合整数线性规划问题。 （ ） （2）动态规划只能用来解决和时间有关的问题。( ) （3）用单纯形法求解标准形式的线性规划问题时，检验数大于零的变量都可以被选作进基变量。( ) （4）分枝定界法在需要分枝时必须满足：一是分枝后的各子问题必须容易求解；二是各子问题解的集合 必须覆盖原问题的解。 （ ）（5）某线性规划问题有最优解，若让其右端常数项值发生变化，则新的对偶问题可能无可行解。
2、（ ib） （6）一个图 G 是树的充分必要条件是边数最少的无孤立点的图。 （ ） （7）在二分图中，最大基数对集的边数等于最小覆盖的点数。 （ ） （8）关键工序一定没有机动时间。 （ ） （9）矩阵对策中当局势达到平衡时，任何一方单方面改变自己的策略（纯策略或混合策略）将意味着自 己更少的赢得或更大的损失；（ ） （10）非完全信息没有价值。 （ ）二、填空题（每空 4 分，共 24 分）1 、已知某线性规划如下： 5 , 4 , 3 , 2 , 1, 01 2016131534. .1122690912max5432154321ixxxxxxtsxxxxxzi其最优解为 。2、网络计划图
3、中节点 4 的最早时间和最晚时间分别为 3 和 5，节点 7 的最早时间和最晚时间分别为 13 和 13，工序（4，7）的工时为 8，则工序（4，7）的机动时间为 （单位：天） 。 3、某风险性决策模型如下：（单位：万元）：S1S2 状态 方案0.70.3甲产品 乙产品5 83 2若用期望值准则决策，应选择生产 ，完全信息的价值 。4、已知矩阵对策 A 的值，则矩阵对策 C 的值_ _，其中14/59AvCv，。 。 651748521 A 616420142216108 C欲求矩阵对策 A 的解可以通过求解如下一对对偶规划得到：和 。三、 （10 分）某公司总部有一部货车沿着公路给 4 个零
4、售店卸下 5箱货物，如果表示零售店得到箱货物的利润，试求使总)(xpkkkkx利润最大的动态规划递推方程（要求给出状态变量、决策变量、状 态转移方程、最优值函数、递推公式等信息） 。得分阅卷人数学与统计学院（系） 专业 2009 级 班 学号 姓名 密密封封线线第 1 页共 3 页得分阅卷人得分阅卷人山东大学 运筹学 （A 卷） 课程试卷 课程号 82154000 2011-2012 学年 第一 学期四、 （14 分）已知下表为求解某线性规划问题的最终单纯形表，表中、为4x5x松弛变量，原问题是对 z 求极大，且约束都为形式，变量都有非负性要求。 要求：(1) 直接由表写出对偶问题的最优解。
5、（2）若要求所有变量取整数，求对应整数规划的解。（3）若原线性规划中，当目标函数x2的系数由c2变为c2+5 时，最优解是否改变？若改变，求出新的最优解。x1 x2 x3 x4 x5 -z 基-40 0 -4 0 -4 -2 x3 x15/2 5/20 1/2 1 1/2 01 -1/2 0 -1/6 1/3五、 （10 分）某台机器可连续工作 4 年，也可于每年末卖掉，换一台新的。 已知于各年初购置一台新机器的价格及不同役龄机器年末的处理价如表所 示。又新机器第一年运行及维修费为 0.3 万元，使用 13 年后机器每年的 运行及维修费用分别为 0.8，1.5，2.0 万元。试确定该机器的最优
6、更新策 略，使 4 年内用于更换、购买及运行维修的总费用为最省。 （提示：转化为最短路径问题，用 Dijkstra 算法求解）j第一年第二年第三年第四年年初购置价 使用了 j 年的机 器处理价2.5 2.02.6 1.62.8 1.33.1 1.1得分阅卷人数学与统计学院（系） 专业 2009 级 班 学号 姓名 密密封封线线第 2 页共 3 页山东大学 运筹学 （A 卷） 课程试卷 课程号 82154000 2011-2012 学年 第一 学期六、 （12 分）某运输问题数据如下表。要求： (1)用伏格尔法求初始基本可行解。 (2)对上面伏格尔法求得的初始基本可行解，求出各非基变量的检验数。 并说明该解是否为最优解。销地 产地B1B2B3B4产量/tA18610935 A291213750A314916540销量/t45203030得分阅卷人七、 （20 分）从下面粗黑线给出的初始对集出发，分别用匈牙利 算法和最大流算法求下图的最大基数对集。 （给出求解过程）得分阅卷人数学与统计 学院（系） 专业 2009 级 班 学号 姓名 密密封封线线第 3 页共 3 页
