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