2018年太原科技大学经济与管理学院836运筹学考研核心题库
● 摘要
一、填空题
1． 若对偶问题为无界解，则原问题:_____。
【答案】无可行解
【解析】任一对偶问题的可行解都是原问题的上界，而原问题的任意可行解都是对偶问题的下界。若对偶问题为无界解，则原问题的目标函数即没有可行解。
2． 某极小化线性规划问题的对偶问题的最优解的第1个分量为y l =-12，则该问题的第1个约束条件的右端常数项的对偶价格为:_____。
【答案】-12
【解析】由对偶问题的经济解释可知，原问题约束条件的右端常数项的对偶价格等于对偶问题的最优解中相 应的分量的值。
3． 若x 为某极大化线性规划问题的一个基可行解，
用非基变量表达其目标函数的形式为
则X 为该LP 最优解的条件是:_____。
【答案】
。
无界，即无限小，则z 无解，
【解析】求极大化问题，则当所有非基变量的检验数均为非正时，即得最优解。线性规划最优时要求非基变 量检验数小于等于0，所以
4． 网络中如果树的节点个数为z ，则边的个数为_____。
【答案】z-l
【解析】由树的性质可知，树的边数=数的节点数-1
二、判断题
5． 整数规划问题最优解的目标函数值一定优于其相应线性规划问题最优解的目标函数值。（ ）
【答案】×
【解析】因为附加了整数条件，其可行域比其相应线性规划问题的可行域减小，故整数规划问题最优解的目 标函数值一定不优于其相应线性规划问题最优解的目标函数值。
6． 对于一个有n 个变量，m 个约束方程的标准线性规划SLP ，其基可行解的数目恰好是个。（ ）
【答案】×
【解析】其基解的个数最多是个，且一般情况下，基可行解的数目小于基解的个数。 7． 若需将某工程项目工期缩短到了10天，简单可行的方法是:任意找出该项目网络中一条关键路线，采取 必要措施将其缩短到10天即可。
【答案】√
【解析】若网络计划图的计算工期大于上级要求的工期时，必须根据要求计划的进度，缩短工程项目的完工 工期。主要采取以下措施，增加对关键工作的投入，以便缩短关键工作的持续时间，实现工期缩短。 ①采取技术措施，提高工效，缩短关键工作的持续时间，使关键线路的时间缩短; ②采取组织措施，充分利用非关键工作的总时差，合理调配人力、物力和资金等资源。 8． 如果线性规划问题无最优解，则它也一定没有基可行解。（ ）
【答案】×
【解析】当问题的解为为无界时，此时该规划问题无最优解，但存在基可行解。
三、计算题
9． 求解六个城市旅行推销员问题，其距离矩阵如表所示，设推销员从1城出发，经过每个城市一次且仅一次，最后回到1城，问按怎样的路线走，使总的行程最短。
表
【答案】从1城出发最后回到l 城中间要经过五个城市，因此将该问题划分5个阶段，阶段变量k=l，2，3，4，5; 记从
示到达i 城之前中途所经过的城市的 集合，则有
表示由1城到i 城的中间城市集合; S 表。
因此，可选取（i ，S ）作为描述过程的状态变量，决策为由一个城市走到另一个城市，并定义最优值函数人（i ，S ）为从1城开始经由k 个中间城市的S 集到i 城的最短路线的距离，则可
写出动态规划的递推关系为
边界条件为由边界条件可知
（l ）当k=l时，从1城开始，中间经过一个城市到达i 城的最短距离为
（2）当k=2时，从1城开始，其间经过两个城市（此两城市的顺序任意）到达i 城的最短距离为
所以，所以，所以，所以，所以，所以，所以，所以，
。
。为最优决策函数，它表示从1城开始经k 个中间城市的s
集到i 城的最 短路线上紧挨着i 城前面的那个城市。
。
。
。
。
。
。
。