运筹学试卷(a).docVIP

中国矿业大学2007～2008学年第一学期 《 运筹学 》试卷（A）卷 考试时间：120 分钟 考试方式：闭卷 班级 姓名 学号 题　号 一 二 三 四 五 六 七 八 总分 得　分 阅卷人 一、判断正误（正确的在括号内打“√”，错误的打“×”，每小题4分，共20分） 1. 若线性规划问题有最优解，则最优解一定在可行域边界上取得。 （ ） 2. 若一线性规划问题及其对偶问题均有可行解，则两者均有最优解，并且原问题与 其对偶问题的最优值相等。 （ ） 3. Dijkastra算法只能求解无负权的网络最短路问题。 （ ） 最大流问题一定存在可行流，但不一定存在最大流。 （ ） 用割平面法求解纯整数规划问题时，松弛变量也要求取整数。 （ ） 二、填空题（每小题4分，共20分） 1. 若线性规划增加一个变量，则其对偶问题的可行域是变大还是变小？ 2. 用表上作业法求解运输问题时，若计算出某空格的检验数是-2，则其经济意义 是 。若从该空格出发 调整，调整量为2，则调整后可使总运费下降 。 3. 目标规划的主要特点是引入了 变量，模型的目标是这些变量的极 （大，小）化，模型的约束中包含这些变量的约束称为 约束，不包含这些 变量的约束称为 约束。 4. 矩阵对策的研究对象是 对策问题，它在纯策略意义下有解 的充要条件是 ，其中 是对策的鞍点。 如果它在纯策略意义下无解，则它在 意义下必有解。 5. 在M/M/1/∞/∞排队系统中，单位时间内到达的平均顾客数为λ，系统对每位顾 客的平均服务时间为，则系统的状态转移方程为 ， 系统中空闲概率为 。 三、（15分）已知如下线性规划： 用大M法求其最优解； 写出其对偶问题，并求出对偶问题的最优解； ③若b变为，最有基是否发生变化，最优解是否发生变化？ 四、（10分）已知某运输问题的产销平衡表，最优调运方案及单位运价表如下： B1 B2 B3 B4 B5 供应量 A1 A2 A3 4 5 4 3 1 1 3 9 4 8 需求量 3 5 4 6 3 B1 B2 B3 B4 B5 供应量 A1 A2 A3 10 20 5 9 10 2 10 10 30 6 1 20 7 10 4 9 4 8 需求量 3 5 4 6 3 若从A1到B3的单位运价变为10，则最优方案是否发生变化，若发 生变化，求出最优方案。 五、（10分）已知如下非线性规划问题： 试建立该问题的动态规划模型（指出阶段的划分、状态变量、决策变量、状态转移方程、指标函数、递推关系式）。（用逆序法，不要求求解） 六、（10分）有如下有向图： 若该图是一容量网络，边上的数字表示相应边的容量。 若，写出边割及其容量； 若源点为vs，汇点为vt，求网络流图的最大流和最小割。 2、若该图表示一道路交通网络，边上的数字表示相邻节点的距离，求从vs到其余各点的最短路径及路长。 七、（5分）求下列指派问题的最小解: 八、（10分）设有矩阵对策，其中，赢得矩