2016年青岛大学自动化工程学院824运筹学(1)考研冲刺模拟题及答案
● 摘要
一、填空题
1． 在灵敏度分析时, 当LP 某系数发生变化使原最优单纯形表中的解为该LP 的一个正侧解，但不是可行解, 为求新的最优解, 处理办法是:____。 【答案】对偶单纯形法
2． 某整数规划模型，解其松弛问题得到最优解。若其中某分量x j 二场为非整数，用分支定界法求解时，针对 该分量构造的两个约束条件应为:_。 【答案】
【解析】由分支定界法的原理可以，良容易得至“结果，其中〔b j 〕为不大于bj 的最大整数。
二、选择题
3． 如果要使目标规划实际实现值不超过目标值，则相应的偏离变量应满足（ ）。 A.d 十>0; B.d 十=0; C.d 一=0; D.d 十>0且d 一>0 【答案】B
【解析】实际实现值不超过目标值，即.
，根据
，可知
4． 对于动态规划，下列说法正确的有（ ）
A. 在动态规划模型中，问题的阶段数等于问题中的子问题的数目 B. 动态规划中，定义状态时应保证在各个阶段中所做决策的相互独立性 C. 对一个动态规划问题，应用顺推成逆推解法可能会得出不同的最优解
D. 假如一个线性规划问题含有8个变量和6个约束，则用动态规划方法求解时将划分为6个阶段，每个阶 段的状态将有一个8维的向量组成 【答案】AB
【解析】对于一个动态规划问题，不论是采用顺推法还是逆推法，只能得到一个唯一的解; 假如一个线性规 划问题含有8个变量和6个约束，则用动态规划方法求解时将按照变量的个数划分为8个阶段，每个阶段的状态 将有一个6维的向量组成。
三、计算题
5． 设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到达目的地，其间的运输成本如图中所标的数字，试求运费最低的路线。
图
【答案】设阶段变量k=1，2，3，4，依次表示4个阶段选择路线的过程; 状态变量s k 表示第k 阶段初可能处的位置; 决策变量x k 表示第k 阶段初可能选择的路线; 最优值函数阶段点s k 开始至终点E 的最少运费， 则有
同理，
由此，可得出三条最优的运输路线:
6． 写出下列线性规划的对偶问题
表示从第k
【答案】
7． 用图解法求解下列线性规划，并指出该问题所有基可行解在图中的位置。
【答案】如图所示可得阴影部分即为可行域，且可知在A （2，2）处取得最小值18。
，，基可行解有3个，分别是（6，0）（2，2）（0，6）
8． 某公司要将一批货从二个产地运到四个销地，有关数据如表所示。
表
现要求制定调运计划，且依次满足: （l ）B3的供应量不低于需要量; （2）其余销地的供应量不低于85%; （3）A 3给B 3的供应量不低于200; （4）A 2尽可能少给B 1;
（5）销地B 2、B 3的供应量尽可能保持平衡。 （6）使总运费最小。
试建立该问题的目标规划数学模型。 【答案】设x if 为A i 到B i 的运量，数学模型为