2016年昆明理工大学质量发展研究院J005运筹学(同等学力加试)复试笔试仿真模拟题
● 摘要
一、计算题
1． 给一个连通的赋权图G ，类似于求G 的最小支撑树的Kruskal 方法，给出一个求G 的最大支撑树的方法。
【答案】类似于避圈法。
第一步选一条最大权边，之后每步均从未被选取的边中选最大权边，加入到树的边的集合中，并要求不能与 已选取的边构成圈（若在某步中存在两条及以上的边都是最大权边，则从中任选一条）。
2． 用图解法求解下列线性规划，并指出该问题所有基可行解在图中的位置。
【答案】如图所示可得阴影部分即为可行域，且可知在A （2，2）处取得最小值18。
，，基可行解有3个，分别是（6，0）（2，2）（0，6）
3． 线性规划问题
当t l =t2=0时，该问题的最优单纯型表如表所示。
表
（l ）确定所有参数，并写出该线性规划问题; （2）当t 2=0时，分析使最优解不变的t 1的变化范围; （3）当t 1=0时，分析使最优基不变的t 2的变化范围。
【答案】（l ）由最优单纯型表得出，x l 和x 3为基变量x B ，则对应初始单纯形表中为:
由最优单纯型表得到由由由由
，得, 得
, 得, 得
（2）x 1是基本量，它的系数变化会影响到检验数的变化。若使最优解不变，应有:
, 解得
, 所以, 求得, 解得, 解得
，即
,
综上，当t l =t2=0时，线性规划为
（3）
将其反映到最终单纯形表中，其b 列数字为:
当b ≥0时问题的最优解不变，解得
4． 求图中所示的网络最大流。
图
【答案】令图中所有弧的可行流为0，同时给图中的中间顶点标上名称，如下图所示（弧旁的数字为
）。
图
用标号算法求最大流 步骤一
，依次给v 2标号（v S ，15），v 6标号（v 2，9），片标号（v 6，（l ）标号过程。先给v s 标号（0，+∞）9）。
（2）调整过程。在网络上寻找增广链
=
，如图双箭头所示。
图