2016年安徽工业大学能源与环境学院运筹学(同等学力加试)考研复试题库
● 摘要
一、计算题
1． 下表为某标准形线性规划（min 型）的单纯形表如表所示。
表
问a 、c 、d 和e 、f 的取值范围，使: （1）该表是最优解表（2）原LP 最优值无界（3）尚需继续旋转【答案】解：（1）最优解表（2）最优值无界
（3）需继续旋转
2． 考察一个线性规划问题，其初始表如表所示。
表
【答案】（l ）进一步迭代一次，结果如表所示
表
（2）设b=（b 1，b 2）认广，则为保持最优基不变，则需满足以下条件:
T
3． 求如图所示的网络最小费用最大流，每条弧旁的数字为
。
图
【答案】给网络中的中间点加上名称，如图所示。 （l ）取
为初始可行流。
（2）依照下列方法构造有向赋权图，如图所示。
并求出从v s 到v t 的最短路（v s ，
v 2，v 4，v t ），如图所示（双箭头即为最短路）。
图
（3）在原网络D 中，与这条最短路相应的增广链为（4）
，如图所示。
。
图
（5）构造有问赋权图，井求出从v s 到v t 的最短路最短路）。
，如图所示（其双箭头即为
图
（6）在原网络中，与这条最短路相应的增广链为（7）在
上调整流量，令
，得
，如图所示。
。
图
（8）构造有向赋权图，并求出从v s 到v t 的最短路，如图所示。因为图己不存在从v s 到v t 的最 短路，故币单位）。
为网络的最小费用最大流。其最大流量为
，而最小费用为
（货