2017年江苏科技大学经济管理学院821运筹学考研仿真模拟题
● 摘要
一、填空题
1． 如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k ，最优调运方案是否会发生变化: _____。
【答案】不发生变化
【解析】如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k ，最优调运方案中各变量的 检验数均不发生变化，所以最优调运方案不发生变化。
2． 若x 为某极大化线性规划问题的一个基可行解，
用非基变量表达其目标函数的形式为
则X 为该LP 最优解的条件是:_____。
【答案】
。
【解析】求极大化问题，则当所有非基变量的检验数均为非正时，即得最优解。线性规划最优时要求非基变 量检验数小于等于0，所以
3． 无向连通图G 是欧拉图的充要条件是_____。
【答案】G 中无奇点
4． 图G=（V ，E ）有生成树的充分必要条件是_____。
【答案】G 是连通图
【解析】图G 是连通图，如果G 不含圈，那么G 本身是一个树，从而G 使它自身的一个支撑树。现设G 含圈，任取一个圈，从圈中任意地去掉一条边，得到G 的一个支撑子图Gl 。如果Gl 不含圈，那么Gl 是G 的 一个支撑树，如果Gl 仍含圈，那么从Gl 中再任取一个圈，如此重复，最终可以得到G 的一个支撑子图Gk ， 它不含圈，于是Gk 就是G 的一个支撑树。
二、证明题
5． 证明:（1）若
（2）若
和
和
是对策G 的两个解，则是对策G 的两个解，则是G 的解，所以
①
同理，因为
是G 的解，所以
②
由不等式①可知
第 2 页，共 55 页
。
和
也是对策G 的解。
【答案】（1）因为
③
由不等式②可知
由不等式③与不等式④可知
（2）由（1）证明过程中不等式③和不等式④可知即
也是解。
6． 证明:r （x ）二x12+x22是严格凸函数。
【答案】首先求导为（2x l ，2x 2:） 求海塞矩阵
，
故
④
，即可知
。
为正定矩阵，所以f （x ）为严格凸函数
7． 设G=（V ，E ）是一个简单圈，令
证明:（l ）若（2）若
，则G 必有圈； ，则G 必有包含至少
条边的圈。
，
（称
为G 的最小次）。
（3）设G 是一个连通图，不含奇点。证明:从G 中丢失任一条边后，得到的图仍是连通图。 【答案】（l ）因为G （V ，E ）是一个简单圈，故该图中无环，也无重复边。若假设G 中无圈，则G 可能是树或非连通图，这两种情况均存在悬挂点，即
相矛盾。故假设不成立， 所以，G 必有圈。
（2）若
，设与
对应的点为v k ，则v k 必与
，也至少与
个端点相连。由（l ）的结论知，
个端点构成圈）
。
G 中必有圈（由于对圈中的连通图而言，v k 至少与
这
的次至少为
个端点不构成圈，那么在端点处必向外延伸（因为最小次为外某点相连）经连通链而到另一端点，对该圈而言，边数大于少于占
条边的圈。
个端点相连。如果v k 与v i 这
， 不与其中某点相连，必与其
条，故G 必定 是包含不
（3）证明:因为G 连通且不含奇点，故d （v ）=2n，且该图中无悬挂点。由题（l ）的结论知，G 必有圈。又因为G 是连通的，所以从G 中去掉任一条边，都必在某一圈中。而从圈中去掉任一条边，所得图仍是连通图。
三、计算题
8． 试用最速下降法求函数对计算，求出极 大点，再以出发的寻优过程。
【答案】令
则求f （x ）的极大点即求F （x ）的极小点。
第 3 页，共 55 页
的极大点。先以为初始点进行
为初始点进行两次迭代，最后比较从上述两个不同初始点
（1）为为初始点，取精度度=0.1，则
令，则所以
，所以x （1）为极小点，即（2, 0）为f （x ）的极大
T
点。
（2）
以
为初始点，取精度；两次迭代的结果：
，采用相同的方法进行两次迭代，有：
。
两次的步长：
比较:一般的，二元二次凸函数的等值线是椭圆，椭圆的圆心即为极小值，（l ）中负梯度方向直指圆心，且初值点与圆心在同一水平直线上，所以收敛很快; （2）中的搜索路径呈直角锯齿状，所以收敛较慢。
9． 某产品有12道加工工序，它们之间的顺序关系如下:工序A 、B 、C 是同时开始的工序; 工序A 、B 的 紧后工序是D ; 工序B 的紧后工序是E 、F 、H ; 工序F 、C 的紧后工序是G ; 工序E 、H 的紧后工序是I 、J ; 工 序C 、D 、F 、J 的紧后工序是K ; 工序K 的紧后工序是L ; 产品在工序I 、G 、L 完成后完工。画出该问题的网络 计划图。
【答案】该问题的网络计划图如图所示。
图
10．判断表1和表2中给出的调运方案能否作为用表上作业法求解时的初始解? 为什么?
表1 表2
第 4 页，共 55 页
相关内容
相关标签