2008年哈尔滨工业大学运筹学考研真题及答案
一、选择题（答案可能不惟一，只有把正确答案全部选出才得分，不倒扣分。
每题4分，共32分）
1．对于一对互为对偶的线性规划模型，下面说法正确的是（）。
A．如果其中的一个模型有可行解，则其对偶问题一定有可行解
B．原问题的目标函数值一定不大于对偶问题的目标函数值
C．如果其中的一个问题有最优解，则其对偶问题一定有最优解
D．如果原问题有m个约束条件，则其对偶问题也有m个约束条件
【答案】C
2．对于一个线性规划问题，哪种情况可以判断属于无界解问题？（）
A．最终表的基变量中存在人工变量
B．该问题的对偶问题存在无界解
C．该问题的对偶问题无可行解
D．该问题的可行域非空，且其对偶问题无可行解
【答案】D
3．关于产销不平衡运输问题的说法，正确的是（）。
A．产销不平衡运输问题表示一个运输网络中，所有产地的总产量与销地的总销量不相等
B．对于产大于销的问题，虚设一个销地相当于在运输问题的约束条件中增加一个松
弛变量
C．如果不希望将产地A(i)的货物运往销地B(j)，则可设相应的单位运价c(i，j) =M，M是某个正数
D．与虚设的产地（或销地）相关的运价，不管什么情况，均应该设为0
【答案】A
4．关于影子价格的说法，正确的是（）。
A．某种资源的影子价格是一种计划经济下的资源价格
B．影子价格反映的是某种资源对利润贡献的稀缺性
C．如果某种资源的影子价格等于0，则增加该种资源的供应量，利润就会增加D．如果某种资源的影子价格为0，则该种资源的市场价格为0
【答案】B
5．关于目标规划的说法，下列正确的是（）。
A．任何一个线性规划，都可以改写成一个目标规划问题
B．目标规划不存在无可行解的情形
C．目标规划的求出的解被称为“满意解”
D．目标规划可能具有无界解
【答案】A
6．关于线性规划求解的两阶段法，下列说法正确的是（）。
A．第一阶段的最优目标函数值一定等于0
B．如果第一阶段的最优目标值=0，则线性规划问题肯定有可行解
C．两阶段法的实质是为了寻找一个不含人工变量的初始基可行解
D．如果第一阶段的最优解中含有人工变量，则线性规划问题无可行解
【答案】BC
7．运输问题表上作业法中关于“闭回路”的说法，正确的是（）。
A．闭回路的顶点数肯定为偶数个
B．如果产销平衡表中，对应的变量位置，不能组成闭回路，则对应的列向量组彼此线性无关
C．表上作业法中，采用闭回路进行方案调整时，确定了进基变量后，也可能找到不止一个闭合回路
D．如果产销平衡表中某些位置组成闭回路，则相应变量对应的系数列向量线性相关【答案】ABD
8．在求解整数规划问题中，关于割平面方法的说法，正确的是（）。
A．割平面法的用意是让整数规划的最优解，通过若干次“割平面”操作，成为一个线性规划问题的顶点
B．割平面方法实质上是通过不断剔除线性规划劣解的方法来求出最优解
C．割平面法实质上是一种隐枚举法
D．割平面法适用于一切整数线性规划的求解
【答案】A
二、简答题（共2道题，每题14分，共28分）
1．考虑一个（线性）目标规划在计算机上求解的问题。
假设手头只有一个线性规划的求解软件，想要仅仅借助该软件来实现对目标规划的求解，请问你的策略是什么（不超过200字）？
解：先以第一级目标为目标函数，以原来的约束为约束，求解一个线性规划；其次，将已经实现的第一个目标作为一个附加约束，以第二级目标为目标函数，再求解一个线性规划。
以此类推，逐次求解k 个线性规划（k 为优先级的个数），即可求出目标规划的满意解。
2．考虑两个企业的资源整合问题。
如果每个单位单独组织生产，各自的效益和，往往小于把两个单位的生产要素进行重组，然后再统筹生产带来的收益高。
因此，资产重组，往往能够带来“双赢”的格局，企业自身也希望通过合并，做大做强。
问题是，每个企业可能会故意夸大其利润水平，从而希冀分得更多的合作收益。
请谈谈你的设想，用以协调其中可能出现的问题（不超过300字，可用符号表述你的想法）？
解：让两个企业单独汇报独立生产能获得的利润，分别记为z 1、z 2。
如果，12z z z +≤则将合作后的额外收益，按照z 1、z 2的比例进行分配。
这样的分配方式，两12(z z z -+)个企业说真话，是一个均衡策略。
三、计算或建模
（一）计算题
1．考察一个线性规划问题，其初始表如表所示。
请回答如下问题：
（1）继续迭代一次。
（5分）
（
2）如果上表中的线性规划问题的最终表如表所示，那么右端常数项b =[10，16]
T 在什么范围内变化时，最优基保持不变？（10分）
解：
（1）进一步迭代一次，结果如表所示。
（2）设，则为保持最优基不变，则需满足以下条件：
12(,)T b b b
1112212121211122111020
b b b B b b b b b b b b -⎛⎫⎛⎫--⎛⎫ ⎪ ⎪== ⎪ ⎪ ⎪ ⎪⎝⎭-+-⎝⎭⎝⎭
⎧-≥⎪⎨⎪-+≥⎩2．考虑采用分枝定界法求解的一个整数规划问题（目标函数为最大化问题）
，其中变量、取整数。
该问题的求解由子问题1开始，如图所示。
1x 2x 请回答：
（1）在当前状态下，如何对整数规划的最优解进行定界。
（5分）
（2）如果进行分枝，应该在哪个问题（从子问题2和子问题3中选择）上附加约束？附加的两个约束分别是什么？（5分）
解：（1）设整数规划的最优目标值为Z *，则对其定界范围为：
*3841
Z ≤≤（2）如果进行分支，从子问题2开始附加约束，附加的两个约束为：
2221
x x ≥⎧⎨≤⎩3．一个建筑工地现场，如图所示，其中A 、…、G 表示的是需要混凝土的施工点，路。
