2016年浙江工商大学信息学院830运筹学考研冲刺模拟题及答案
● 摘要
一、填空题
1． 对于线性规划问题:MaxZ=CX.AX≦b.X ≧0，若B=（P 1，P 2，…，P m ）为A 中m 个线性无关的列向量, 且为该LP 的一个可行基，则对应于基B 的基可行解为:_____，该基可行解为最优解的条件是:_____。 【答案】
，对于一切
有
。
【解析】若B=（P 1，P 2，…，P m ）为A 中m 个线性无关的列向量，此时令非基变
量
， 这时变量的个数等于线性方程组的个数，用高斯消去法，可求得对应
于基B 的基可行解
为
2． Fibonacoi 法在[2，6]区间上取的初始点是_。 【答案】
，
。由最优解的判别定理，若对于一
切
, 则所求得的基可 行解为最优解。
【解析】由Fibonacci 的计算方法可知。
3． 两阶段法中，若第一阶段目标函数最优值不为0，则原问题____。 【答案】无可行解
【解析】第一阶段目标函数值不是0，则说明最优解的基变量中含有非零的人工变量，表明原先性规划问题五可行解。
4． 流f 为可行流必须满足___条件和___条件。 【答案】容量限制条件和平衡条件
【解析】在运输网络的实际问题中可以看出，对于流有两个明显的要求:一是每个弧上的流量不能超过该弧 的最大通过能力（即弧的容量）; 二是中间点的流量为零。因为对于每个点，运出这点的产品总量与运进这点的 产品总量之差，是这点的净输出量，简称为是这一点的流量; 由于中间点只起转运作用，所以中间点的流量必为 零。易而发点的净流出量和收点的净流入量必相等，也是这个方案的总输送量。
二、计算题
5． 求图中所示的网络最大流。
图
【答案】令图中所有弧的可行流为0，同时给图中的中间顶点标上名称，如下图所示（弧旁的数字为
）。
图
用标号算法求最大流 步骤一
，依次给v 2标号（v S ，15），v 6标号（v 2，9），片标号（v 6，（l ）标号过程。先给v s 标号（0，+∞）9）。
（2）调整过程。在网络上寻找增广链
=
，如图双箭头所示。
图
由此得到新的可行流
，如图所示。对新的可行流，重复标号与调整过程。
图
步骤二
，再依次给v 3标号（v s ，10），v s 标号（v 3，9），v 7标号（v 5，（l ）标号过程。先给v s 标号（0，+∞）
9），v 8标号（v 7，9），v t 标号（v 8，9）。v t 己得到标号，因此转入调整过程。 （2）调整过程。在图所示网络上，寻找新的增广
链
，如图中双箭头所示。
，即
图
其他的保持
整过程。
不变。调整后得新的可行流
，如图所示。对此可行流继续标号与调
相关内容
相关标签