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

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