2011-2012山东大学运筹学(a卷)课程试卷

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