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

1、 数学与统计学院（系） 专业 2009 级 班 学号 姓名 密封线山东大学 运筹学 (A卷) 课程试卷 课程号 2011-2012 学年 第一 学期题号一二三四五六七八总分复核人得分得分阅卷人 一、判断题（每小题1分，共10分）（1）割平面方法可以解决混合整数线性规划问题。（ ）（2）动态规划只能用来解决和时间有关的问题。( )（3）用单纯形法求解标准形式的线性规划问题时，检验数大于零的变量都可以被选作进基变量。( )（4）分枝定界法在需要分枝时必须满足：一是分枝后的各子问题必须容易求解；二是各子问题解的集合必须覆盖原问题的解。（ ）（5）某线性规划问题有最优解，若让其右端常数项值发生变化，则

2、新的对偶问题可能无可行解。（ ）（6）一个图G是树的充分必要条件是边数最少的无孤立点的图。（ ）（7）在二分图中，最大基数对集的边数等于最小覆盖的点数。（ ）（8）关键工序一定没有机动时间。（ ）（9）矩阵对策中当局势达到平衡时，任何一方单方面改变自己的策略（纯策略或混合策略）将意味着自己更少的赢得或更大的损失；（ ）（10）非完全信息没有价值。（ ）得分阅卷人二、填空题（每空4分，共24分）1 、已知某线性规划如下：其最优解为 。2、网络计划图中节点4的最早时间和最晚时间分别为3和5，节点7的最早时间和最晚时间分别为13和13，工序（4，7）的工时为8，则工序（4，7）的机动时间为 （单位：

3、天）。3、某风险性决策模型如下：（单位：万元）： 状态方案S1S20.70.3甲产品乙产品5832若用期望值准则决策，应选择生产 ，完全信息的价值 。4、已知矩阵对策A的值，则矩阵对策C的值_ _，其中，。 。欲求矩阵对策A的解可以通过求解如下一对对偶规划得到： 和 。得分阅卷人三、（10分）某公司总部有一部货车沿着公路给4个零售店卸下5箱货物，如果表示零售店得到箱货物的利润，试求使总利润最大的动态规划递推方程（要求给出状态变量、决策变量、状态转移方程、最优值函数、递推公式等信息）。第 1 页共 3 页 数学与统计学院（系） 专业 2009 级 班 学号 姓名 密封线山东大学 运筹学 （A卷）

4、 课程试卷 课程号 2011-2012 学年 第一 学期得分阅卷人四、（14分）已知下表为求解某线性规划问题的最终单纯形表，表中、为松弛变量，原问题是对z求极大，且约束都为形式，变量都有非负性要求。要求： x1 x2 x3 x4 x5 -z基-40 0 -4 0 -4 -2 x3x15/25/20 1/2 1 1/2 0 1 -1/2 0 -1/6 1/3(1) 直接由表写出对偶问题的最优解。（2）若要求所有变量取整数，求对应整数规划的解。（3）若原线性规划中，当目标函数x2的系数由c2变为c2+5时，最优解是否改变？若改变，求出新的最优解。得分阅卷人五、（10分）某台机器可连续工作4年，也可

5、于每年末卖掉，换一台新的。已知于各年初购置一台新机器的价格及不同役龄机器年末的处理价如表所示。又新机器第一年运行及维修费为0.3万元，使用13年后机器每年的运行及维修费用分别为0.8，1.5，2.0万元。试确定该机器的最优更新策略，使4年内用于更换、购买及运行维修的总费用为最省。（提示：转化为最短路径问题，用Dijkstra算法求解）j第一年第二年第三年第四年年初购置价使用了j年的机器处理价2.52.02.61.62.81.33.11.1 第 2 页共 3 页 数学与统计 学院（系） 专业 2009 级 班 学号 姓名 密封线山东大学 运筹学 （A卷） 课程试卷 课程号 2011-2012 学年 第一 学期六、（12分）某运输问题数据如下表。要求：(1)用伏格尔法求初始基本可行解。(2)对上面伏格尔法求得的初始基本可行解，求出各非基变量的检验数。并说明该解是否为最优解。得分阅卷人 销地产地B1B2B3B4产量/tA18610935A291213750A3149165