2017年哈尔滨工业大学威海校区850运筹学考研导师圈点必考题汇编
● 摘要
一、选择题
1． 单纯形法中，关于松弛变量和人工变量，以下说法正确的是（ ）。
A. 在最后的解中，松弛变量必须为0，人工变量不必为0
B. 在最后的解中，松弛变量不必为0，人工变量必须为0
C. 在最后的解中，松弛变量和人工变量都必须为0
D. 在最后的解中，松弛变量和人工变量都不必为0
【答案】B
【解析】松弛变量是在约束不等式号的左端加入的，在最后的解中，其值可以不必为0; 人工变量是在原约束条件为等式的情况下加入的，只有基变量中不再含有非零的人工变量时，原问题才有解，所有最后的解中人工变量必须为0。
2． 设线性规划
A. 基本可行解
B. 基本可行最优解
C. 最优解
D. 基本解
【答案】A
【解析】可行解包括基可行解与非基可行解。
3． 单纯形法求解最大化线性规划问题，如果存在“左端≥右端常数”的约束条件，对此约束条件应引入（ ）。
A. 可控变量
B. 环境变量
C. 人工变量
D. 松弛变量
【答案】D
【解析】约束方程为“≥”不等式，则可在“≥”不等式左端减去一个非负剩余变量（也可称松弛变量）。
有可行解，则此线性规划一定有（ ）。
4． 用线性规划制定某一企业的生产计划问题，两种资源的影子价格分别为y 甲=5，y 乙=8，说明这两种资源在该企业中的稀缺程度为:（ ）。
A. 甲比乙更稀缺
B. 甲和乙同样稀缺
C. 乙比甲更稀缺
D. 甲和乙都不稀缺
【答案】C
【解析】影子价格是对系统内部资源稀缺程度的一种客观评价，某种资源的影子价格越高，说明该资源在系统内越稀缺，增加该资源的供应量对系统目标函数值的贡献也越大。
二、简答题
5． 简述割平面法的基本思想。
【答案】这个方法的基础仍然是用解线性规划的方法去解整数规划问题，首先不考虑变量xi 是整数这一条件， 但增加线性约束条件（用几何术语，称为割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当
，使切割后最终得 到这样的可行域，它的一个有整数坐标的极点的割平面（不见得一次就找到）
恰好是问题的最优解。
6． 一个运输问题，如果其单位运价表的某一行元素分别加上一个常数，最优调运方案是否发生变化，试说明理由（用表或直接用公式）;
【答案】最优方案不会发生变化。因为在计算任意空格的检验数时，若其通过变化行的一个基格，则其必经过两个基格，
则
最优方案不发生变化。
三、计算题
7． 试写出下述非线性规划问题的K-T 条件并进行求解：
【答案】（1）原非线性规划问题可改写成：
目标函数和约束函数的梯度为：
对第一、二个约束条件分别引入广义拉格朗日乘子条件:
和，并令K-T 点为X*，则有K-T
为解该方程组，考虑以下几种情形: ①令
②令
③令
④令，则无解； ，则，则，则是K-T 点，目标函数值为-4； ，是K-T 点，目标函数值为-4； ，是K-T 点，目标函数值为0；
由于该非线性规划问题不是凸规划，且K-T 条件只是确定某点为最优点的必要条件，而非充分条件，所以1 或5不一定是全局极小点。
（2）原非线性规划问题可改写成:
目标函数和约束函数的梯度为:
对第一、二个约束条件分别引入广义拉格朗日乘子件:
为解该方程组，考虑以下几种情形: ①令
②令
③令
④令 则无解 则 则不是K-T 点。 不是K-T 点 为K-T 点，其目标函数值
=3是该问题的全局极小点。 和，并令K-T 点为X*，则有K-T 条由于该非线性规划问题是凸规划，所以
8． 试写出下述二次规划的K-T 条件：
其中A 为
列向量。
【答案】原二次规划可改写为： 矩阵，H 为矩阵，C 为n 维列向量，b 为m 维列向量，变量X 为n 维