2016年清华大学经济管理学院846运筹学考研内部复习题及答案
● 摘要
一、填空题
1． 运输问题任一基可行解非零分量的个数的条件是_____。 【答案】小于等于行数+列数-1
【解析】任意运输问题的基可行解可变量个数为:行数+列数一l 。然而基变量也可能等于0，所以运输问题 任一基可行解非零分量的个数小于等于行数+列数一1。
2． 某整数规划模型，解其松弛问题得到最优解。若其中某分量x j 二场为非整数，用分支定界法求解时，针对 该分量构造的两个约束条件应为:_。 【答案】
【解析】由分支定界法的原理可以，良容易得至“结果，其中〔b j 〕为不大于bj 的最大整数。
二、选择题
3． 线性规划可行域为封闭的有界区域，最优解可能是（ ）。 A. 唯一的最优解 B. 一个以上的最优解 C. 目标函数无界 D. 没有可行解 【答案】AB
【解析】可行域非空，故有可行解; 可行域封闭，故目标函数有界，有一个或多个最优解。 4． 无约束最优化问题
）问题的（ ）。
A. 全局最优解 B. 局部最优解 C. 极点 D .K-T点 【答案】B
【解析】局部最优解即在X*的某邻域，满足
，则称X*是函数的局部最优解。
中，如果在X*的某个领域内满足
，则X ’是
三、计算题
5． 某工厂设计的一种电子设备由A 、B 、C 三种元件串联而成，己知三种元件的单价分别为2万 元、3万元、1万元，单件的可靠性分别为0.7、0.8、0.6，要求设计中使用元件的总费用不超过10万元，问应 如何设计使设备的可靠性最大? （请使用动态规划方法求解）
【答案】设各种元件的个数为x 1，x2，x3，则根据变量的个数，将该问题分为3阶段。设状态变量为s 1，s 2，s 3，s4并计 s 1=10; x 1，x2，x3为各阶段的决策变量; 各阶段的指标函数按乘法方式结合。令最优值函数f k （s k ）表示第k 阶段的 初始状态为s k ，从第k 阶段至第3阶段的最大值，f 4（s 4）=1。
得模型为
则有用逆推方法
最优解为
由
x 2* =1，
解得
由
数, s 1=10,
即购买三种元件分别为3件、1件、1件。 6． 己知运价表如表所示:
表
解得
，
且为整
，但1≤x 2≤s 2/3，s 2 ≤
10-2*1=8
设
求解总运费最小的最优解（注:求解方法不限，要求写出必要的计算过程）。
【答案】此问题是一个产销不平衡的运输问题，首先增加一个假想的产地戊，其产量为30，运价为0，化为产销平衡问题如表所示:
表
采用伏格尔法，求得初始解如下:
表
采用位势法检验，得下表:
表
表中还有负检验数，说明未得最优解，用闭回路法进行改进，如表所示:
表
确定调入量θ=min（50，20，30）=20。按闭回路上的正负号，加入和减去20，得到调整方案，如表所示:
表