2017年沈阳理工大学机械工程学院825运筹学二考研冲刺密押题
● 摘要
一、选择题
1． 在求解整数规划问题时，不可能出现的是（ ）。
A. 唯一最优解 B. 无可行解 C. 多重最优解 D. 无穷多最优解 【答案】D
【解析】整数规划的可行解的个数是有限的，所以整数规划中不可能出现无穷多最优解。
2． 关于最小费用最大流，求解时不会用到下面哪种方法（ ）。
A.Dijkstra 算法 B.Floyd 算法
C.Ford 一Fulkerson 算法 D. 奇偶点作业法 【答案】D
【解析】奇偶点作业法为中国邮递员问题中寻找欧拉圈时所用的方法，最小费用最大流问题并不涉及此法。
3． 单纯形法中，关于松弛变量和人工变量，以下说法正确的是（ ）。
A. 在最后的解中，松弛变量必须为0，人工变量不必为0 B. 在最后的解中，松弛变量不必为0，人工变量必须为0 C. 在最后的解中，松弛变量和人工变量都必须为0 D. 在最后的解中，松弛变量和人工变量都不必为0 【答案】B
【解析】松弛变量是在约束不等式号的左端加入的，在最后的解中，其值可以不必为0; 人工变量是在原约束条件为等式的情况下加入的，只有基变量中不再含有非零的人工变量时，原问题才有解，所有最后的解中人工变量必须为0。
4． 用单纯形法求解线性规划问题时，满足（ ）对应的非基变量xj 可以被选作为换入变量。
A. 检验数σ>0 B. 检验数σ<0
C. 检验数σ>0中的最大者 D. 检验数σ<0中的最小者 【答案】C
【解析】当某些σ>0时，xj 增加则目标函数值还可以增大，这时要将某个非基变量xj 换到基变量中去，为了使目标函数值增加得快，一般选择σ>0中的大者。
二、计算题
5． 试用外点法求解非线性规划问题:
【答案】构造罚函数
令
得
，因为
因此得
6． 已知线性规划问题
对偶变量
求得
的解为
所以
其对偶问题的最优解为对【答案】原问题的对偶问题为
，试应用对偶问题的性质，求原问题的最优解。
将补松弛性可知
应取等号，即
分别代入对偶问题的各约束条件中，可知，式①和式②为严格不等式，由互
。又因为
，所以根据互补松弛性知，原问题的两个约束条件
解得，
。于是原问题的最优解为
，最优目标函数值为z*=44。
7． 甲、乙、丙三个铁矿石开采基地向A 、B 、C 、D 四个工厂供应原料，各供应地的供应量（万，各需 求地需求量（万吨）和相互之间的运价（百万元万吨）如表所示。由于外在的原因，吨）
工厂D 的原料只能由 铁矿石开采基地丙来供应。请求解满足这一要求的最优调运方案，要求采用最小元素法建立初始调运方案，采用位势法进行方案检验。
表
【答案】该问题属于运输平衡问题。因为工厂D 的原料只能由铁矿石开采基地丙来供应，所以这里规定甲、乙 和D 之间的运价为M ，M 表示足够大的正数。
采用最小元素法得初始调运方案如表所示:（因为基格个数=7-1=6个，故在一空格中填入0）
表
用位势法检验得各空格的检验数（括号内）如表所示: