北京化工大学2021年复试 运筹学 样题.pdf

《运筹学》试题样题 第 1 题（10 分）判断下列说法是否正确, 在括号内写明对错。 (1) 增加约束条件时, 线性规划模型的可行域不扩大。( ) (2) 线性规划问题的对偶问题的对偶问题是原问题。 ( ) (3) 动态规划的逆推与顺推解法得到相同的最优解。( ) (4) 若某种资源的影子价格等于k ,在其他条件不变的情况下,当该种资源增加 5 时， 相应的目标函数值将增大 5 k 。( ) (5) 加非负权无向连通图中任两点间必存在最短路径。 ( ) 第 2 题（10 分）填空 (1) 若原问题为无界解，则对偶问题的解是 。 (2) 任何图中, 奇次顶点的个数为 。 (3) 无向连通多重图 G 有欧拉通路的充分必要条件为 。 (4) 在一个网络中，可行流f  是最大流，当且仅当 。 (5) 对于多阶段决策问题来说，状态不仅要描述过程的具体特征，而且一个根本的 要求是必须满足 。 第 3 题（20 分）下表 1 是某求极大化线性规划问题计算得到的单纯形表。表中无人工变 量，a ,a ,a ,d ,c ,c 为待定常数，d 0 。试说明这些常数分别取何值时，以下结论成立。 1 2 3 1 2 （1）表中解为惟一最优解； （2 ）表中解为最优解，但存在无穷多最优解； （3 ）该线性规划问题具有无界解； （4 ）表中解非最优，为对解改进，换入变量为x1 ，换出变量为x6 表 1 基 b x1 x2 x3 x4 x5 x6 x3 d 4 a1 1 0 a2 0 x4 2 -1 -3 0 1 -1 0 x6 3 a3 -5 0 0 -4 1 cj  zj c1 c2 0 0 -3 0 第 4 题（10 分）用破圈法或避圈法求下图 1 的最小生成树，并指出其权重和。 V2 5 V5 6 6 4 5 5 V6 V1 3 2 V8 4 V3 7 图 1 4 3 4 8 V4 V7 3 第 5 题（15 分）求下图 2 的网络最大流和最小截集，弧旁数字为容量。 12 V1 V3