运筹学复习题库#

第2章 线性规划#

一、选择题#

1. 如果一个线性规划问题有( n )个变量，( m )个约束方程(( m < n ))，系数矩阵的秩为( m )，则基可行解的个数最多为( )。 A. ( m )个 B. ( n )个 C. ( C_n^m ) D. ( C_m^n )

2. 下列图形所包含的区域不是凸集的是( )。 A. 圆形 B. 三角形 C. 圆环 D. 正方形

3. 线性规划模型不包括下列( )要素。 A. 目标函数 B. 约束条件 C. 决策变量 D. 状态变量

4. 线性规划模型中增加一个约束条件，可行域的范围一般将( )。 A. 增大 B. 缩小 C. 不变 D. 不定

5. 若针对实际问题建立的线性规划模型的解是无界的，不可能的原因是( )。 A. 出现矛盾的条件 B. 缺乏必要的条件 C. 有多余的条件 D. 有相同的条件

6. 线性规划可行域的顶点一定是( )。 A. 可行解 B. 非基本解 C. 非可行 D. 是最优解

7. 为什么单纯形法迭代的每一个解都是可行解？答:因为遵循了下列规则( )。 A. 按最小比值规则选择出基变量 B. 先进基后出基规则 C. 标准型要求变量非负规则 D. 按检验数最大的变量进基规则

8. 线性规划标准型的系数矩阵 ( A_{m \times n} )，要求( )。 A. ( \text{rank}(A) = m ) 并且 ( ( m < n ) ) B. ( \text{rank}(A) = m ) 并且 ( m \le n ) C. ( \text{rank}(A) = m ) 并且 ( ( m = n ) ) D. ( \text{rank}(A) = n ) 并且 ( ( n < m ) )

9. 下列错误的结论是( )。 A. 检验数是用来检验可行解是否是最优解的数 B. 检验数是目标函数用非基变量表达的系数 C. 不同检验数的定义其检验标准也不同 D. 检验数就是目标函数的系数

10. 线性规划问题有可行解，则( )。 A. 必有基可行解 B. 必有唯一最优解 C. 无基可行解 D. 无唯一最优解

11. 若目标函数为求max，一个基可行解比另一个基可行解更好的标志是( )。 A. 使( Z )更大 B. 使( Z )更小 C. 绝对值更大 D. ( Z )绝对值更小

12. 如果线性规划问题存在目标函数为有限值的最优解，求解时只需在( )集合中进行搜索即可得到最优解。 A. 基 B. 基本解 C. 基可行解 D. 可行域

13. 如果第( K )个约束条件是“≤”情形，若化为标准形式，需要( )。 A. 左边增加一个变量 B. 右边增加一个变量 C. 左边减去一个变量 D. 右边减去一个变量

14. 若某个 ( b_k \le 0 )，化为标准形式时原不等式( )。 A. 不变 B. 左端乘-1 C. 右端乘-1 D. 两边乘-1

15. 若线性规划问题没有可行解，可行解集是空集，则此问题( )。 A. 没有无穷多最优解 B. 没有最优解 C. 有无界解 D. 有无界解

16. 线性规划具有唯一最优解是指( )。 A. 最优表中非基变量检验数全部非零 B. 不加入人工变量就可进行单纯形法计算 C. 最优表中存在非基变量的检验数为零 D. 可行解集合有界

17. 线性规划具有多重最优解是指( )。 A. 目标函数系数与某约束系数对应成比例 B. 最终表中存在非基变量的检验数为零 C. 可行解集合无界 D. 基变量全部大于零

18. 关于线性规划标准型的特征，哪一项不正确( )。 A. 决策变量全部大于等于0 B. 约束条件全为线性等式 C. 约束条件右端常数无约束 D. 目标函数值求最大

19. 线性规划可行解集合非空时一定( )。 A. 包含原点 B. 有界 C. 无解 D. 是凸集

二、填空题#

1. 线性规划问题中，如果在约束条件中出现等式约束，我们通常用增加 人工变量 的方法来产生初始可行基。

2. 在线性规划问题中，称满足所有约束条件方程和非负限制的解为 可行解。

3. 若线性规划问题的最优基为( B )，则问题的最优值为 ( C_B B^{-1} b )，线性规划的对偶问题的最优解是 *( Y^ = C_B B^{-1} )**，其中 ( C_B ) 是基( B )所对应的基变量在目标函数中的系数向量。

4. 在基本可行解中非基变量一定为 0。

5. 在线性规划问题中，图解法适合用于处理 决策变量 为两个的线性规划问题。

6. 线性规划模型有三种参数，其名称分别为价值系数、技术系数 和 限定数/右端项。

7. 在单纯形法迭代中,任何从基变量中替换出来的变量在紧接着的下一次迭代中 不会 立即入基。

8. 如果把约束方程 ( x_1 + 3x_2 \le 4 ), ( 2x_1 + 5x_2 \ge 5 ) 标准化为 ( x_1 + 3x_2 + x_3 = 4 ), ( 2x_1 + 5x_2 - x_4 + x_5 = 5 ) 时，( x_1 )是 决策 变量，( x_2 )是 决策 变量，( x_3 )是 松弛 变量，( x_4 )是 剩余 变量，( x_5 )是 人工 变量。

9. 线性规划问题的基本可行解与基本解的区别是基本可行解的分量 非负。

10. 求目标最大的LP中，有无穷最优解的条件是 最终单纯形表中存在非基变量的检验数为零。

11. 线性规划单纯形法中确定出基变量采用 最小比值 规则。

12. 原问题和对偶问题均存在可行解，则两者均存在 最优解。

13. 对于右图中的某线性规划问题的约束集合，其可行解为 区域O-( G )-E-D-H内的所有点，基本解为 O, ( G ), E, D, H等所有约束线的交点，基本可行解为 O, ( G ), E, D, H。

三、判断题#

1. 任何一个线性规划都可以转化为标准型。 (✔)

2. 单纯形法中采用最小比值规则确定出基变量。 (✔)

3. 两阶段法第一阶段的目标函数是原线性规划问题的目标函数。 (✘)

4. 对于求最小值线性规划问题，如果所有检验数小于等于0，得到最优解。 (✘)

5. 线性规划问题的标准型可以求最小值。 (✔)

6. 线性规划模型中减少一个约束条件，可行域的范围一定增大。 (✘)

7. 对于求最大值线性规划问题，如果某个非基变量检验数为0，则存在无穷个最优解。 (✔)

8. 单纯形法求解过程中，基变量个数和非基变量个数是变化的。 (✘)

9. 需要求得所有非基变量的检验数才能判断当前解是否是最优解。 (✔)

---

第3章 线性规划的对偶问题#

一、选择题#

1. 使用人工变量法求解极大化的线性规划问题时，当所有的检验数 ( \lambda_j \le 0 )，但在基变量中仍含有非零的人工变量，表明该线性规划问题( )。 A. 有唯一的最优解 B. 有无穷多最优解 C. 为无界解 D. 无可行解

2. 对偶单纯形法解最小化线性规划问题时，每次迭代要求单纯形表中( )。 A. b列元素不小于零 B. 检验数都大于零 C. 检验数都不小于零 D. 检验数都不大于零

3. 如果决策变量数相等的两个线性规划的最优解相同，则两个线性规划( )。 A. 约束条件相同 B. 模型相同 C. 最优目标函数值相等 D. 以上结论都不对

4. 对偶单纯形法的最小比值规则则是为了保证( )。 A. 使原问题保持可行 B. 使对偶问题保持可行 C. 逐步消除原问题不可行性 D. 逐步消除对偶问题不可行性

5. 互为对偶的两个线性规划问题的解存在关系( )。 A. 一个问题具有无界解，另一问题无可行解 B. 原问题无可行解，对偶问题也无可行解 C. 若最优解存在，则最优解相同 D. 一个问题无可行解，则另一个问题具有无界解

6. 原问题与对偶问题都有可行解，则( )。 A. 原问题有最优解，对偶问题可能没有最优解 B. 原问题与对偶问题可能都没有最优解 C. 可能一个问题有最优解，另一个问题具有无界解 D. 原问题与对偶问题都有最优解

7. 线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为( )形式。 A. “≥” B. “≤” C. “>” D. “=”

8. 如果某种资源的影子价格大于其市场价格，则说明( )。 A. 该资源过剩 B. 该资源稀缺 C. 企业应尽快处理该资源 D. 企业应充分利用该资源，开辟新的生产途径

9. 影子价格是指( )。 A. 检验数 B. 对偶问题的基本解 C. 解答列取值 D. 对偶问题的最优解

二、填空题#

1. 已知线性规划问题的数学模型：

   \begin{aligned} \min \quad & w = \sum_{j=1}^\( m \) c_j y_j \\ \text{s.t.} \quad & \sum_{j=1}^\( m \) a_{ij} y_j \ge b_i \quad (i=1,2,\dots,\( n \)) \\ & y_j \ge 0 \quad (j=1,2,\dots,\( m \)) \end{aligned}

   其对偶数学模型的最优解为 ( X^* = (x_1^, x_2^, \dots, x_n^) )，则原数学模型的最优目标函数值为 ( \sum_{i=1}^n b_i x_i^ )。

2. 在互为对偶的两个数学模型中，若其中一个数学模型有最优解，则另一个数学模型 有 最优解。

   ​

   ​

3. 设线性规划问题数学模型如下：

   \begin{aligned} \max \quad & \( z \) = CX \\ \text{s.t.} \quad & AX = b \\ & \( x \) \ge \end{aligned}

   则其对偶数学模型为：

   \begin{aligned} \min \quad & w = b^\( T \) \( Y \) \\ \text{s.t.} \quad & \( A \)^\( T \) \( Y \) \ge C^\( T \) \\ & \( Y \) \text{ 无约束} \end{aligned}

4. 在单纯形法中，初始基可能由 决策、松弛、人工 三种类型的变量组成。

   ​

   ​

5. 若对偶问题为无界解，其原问题为 无可行解。

   ​

   ​

6. 线性规划中的影子价格 ( Y^* = C_B B^{-1} ) 就是对偶问题的 最优解。

   ​

   ​

7. 原问题的第1个约束方程是“=”型，则对偶问题相应的变量是 无约束 变量。

   ​

   ​

8. 互为对偶的两个线性规划问题最优目标函数值 相等。

   ​

   ​

三、判断题#

1. 如线性规划的原问题存在可行解，则其对偶问题也一定存在可行解。 (✘)

2. 如线性规划的对偶问题无可行解，则原问题也一定无可行解。 (✘)

3. 如线性规划的原问题和对偶问题都具有可行解，则该线性规划问题一定具有最优解。 (✔)

4. 资源限量的灵敏度分析主要是研究某一资源限量的变化对最优解的影响。 (✔)

5. 价值系数的灵敏度分析主要是研究某一决策变量价值系数的变化对最优解的影响。 (✔)

6. 原问题与其对偶问题的目标函数一致。 (✘)

7. 人工变量与决策变量的本质相同。 (✘)

8. 互补松弛性提供了已知一个问题的最优解时求解其对偶问题的最优解的方法。 (✔)

9. 原问题是求目标函数最大值，则其对偶问题的目标函数一定是求最小值。 (✔)

10. 互为对偶的两个线性规划问题中，原问题的检验数对应对偶问题的基本解。 (✘)

11. 互为对偶的两个问题，或者同时都有最优解，或者同时都没有最优解。 (✔)

12. 如果原问题有多重解，对偶问题可能有多重解，也可能有唯一解。 (✔)

13. 如果原问题有无界解，则对偶问题无可行解。 (✔)

---

第4章 运输问题#

一、选择题#

1. 在( n )个产地、( m )个销地的产销平衡运输问题中，( )是错误的。 A. 运输问题是线性规划问题 B. 基变量的个数有 ( m )+( n - 1 ) 个 C. 基变量的个数是数字格的个数 D. 每一格在运输图中均有一闭合回路

2. 关于运输问题的说法不正确的是( )。 A. 它可用线性规划的单纯形表求解 B. 它的约束方程数等于基变量的数目 C. 它可用表上作业法求解 D. 它一定有最优解

3. 关于指派问题的决策变量的取值，下列说法正确的是( )。 A. 不一定为整数 B. 不是0就是1 C. 只要非负就行 D. 都不对

4. 求解运输问题中，当供大于求时，可增加一个( )。 A. 虚拟产地 B. 虚拟销地 C. 都可 D. 都不可

5. 产销不平衡的运输问题中，当供大于求时，增加的虚拟销地相当于( )。 A. 亏空 B. 原地库存 C. 异地库存 D. 都不对

6. 运输问题的数学模型中包含( )个约束条件。 A. ( mn ) B. ( m + n ) C. ( m )+( n - 1 ) D. ( mn - 1 )

7. 平衡运输问题即是指( m )个供应地的总供应量( )( n )个需求地的总需求量。 A. 大于 B. 大于等于 C. 小于 D. 等于

8. 下列( )不是确定运输问题初始方案的方法。 A. 西北角法 B. 伏格尔法 C. 最小元素法 D. 闭回路法

9. 运输问题的数学模型属于( )。 A. 0-1规划模型 B. 整数规划模型 C. 网络模型 D. 以上模型都是

10. 在运输方案中出现退化现象，是指数字格的数目（ ）。 A. 等于 ( m + n ) B. 等于 ( m )+( n - 1 ) C. 小于 ( m )+( n - 1 ) D. 大于 ( m )+( n - 1 )

11. 通过什么方法或者技巧可以把产销不平衡运输问题转化为产销平衡运输问题？ A. 非线性问题的线性化技巧 B. 静态问题的动态处理 C. 引入虚拟产地或者销地 D. 引入人工变量

二、填空题#

1. 求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点化为供求平衡问题。

2. 运输问题中求初始基本可行解的方法通常有 西北角、最小元素、伏格尔 三种方法。

3. 运输问题中，求总利润最大时，当运输图所有空格的检验数 ( \le 0 )，得最优解；求总运费最小时，当运输图所有空格的检验数 ( \ge 0 )，得最优解。

4. 运输问题中，当总供应量小于总需求量时，求解时需虚设一个 供应 点，此点的供应量应等于 总需求量 - 总供应量。

5. 运输问题中非基变量的闭回路有 1 条。

6. M个产地，N个销地的产销不平衡运输问题中，基变量个数为 ( m + n )。

7. M个产地，N个销地的产销平衡运输问题中，基变量个数为 ( m )+( n - 1 )。

三、判断题#

1. 对于求费用最小的运输问题，如果某个非基变量检验数小于零，则当前解不是最优解。 (✔)

2. 位势法是根据对偶理论提出的求检验数的方法。 (✔)

3. 不平衡运输问题不一定有最优解。 (✘)

4. 如果运输问题的运价和产销量均为整数，则一定存在整数最优解。 (✔)

5. 产销平衡的运输问题模型有( m + n )个等式约束和( mn )个变量。 (✔)

---

第5章 目标规划#

一、选择题#

1. 要求不超过第一目标值、恰好完成第二目标值，目标函数是( )。 A. ( \min z = p_1 d_1^- + p_2(d_2^- + d_2^+) ) B. ( \min z = p_1 d_1^+ + p_2(d_2^- + d_2^+) ) C. ( \min z = p_1 d_1^+ + p_2(d_2^- + d_2^+) ) D. ( \min z = p_1 d_1^- + p_2(d_2^- - d_2^+) )

2. 下列正确的目标规划的目标函数是( )。 A. ( \max z = d^- + d^+ ) B. ( \max z = d^- - d^+ ) C. ( \min z = d^- + d^+ ) D. ( \min z = d^- - d^+ )

3. 目标函数 ( \min z = p_1(d_1^- + d_2^-) + p_2 d_3^- ) 的含义是( )。 A. 首先第一和第二目标同时不低于目标值，然后第三目标不低于目标值 B. 第二和第三目标同时不超过目标值 C. 第一和第二目标恰好达到目标值，第三目标不超过目标值 D. 首先第一和第二目标同时不超过目标值，然后第三目标不超过目标值

4. 下列线性规划与目标规划之间错误的关系是( )。 A. 线性规划的目标函数由决策变量构成，目标规划的目标函数由偏差变量构成 B. 线性规划模型不包含目标约束，目标规划模型不包含系统约束 C. 线性规划求最优解，目标规划求满意解 D. 线性规划求最大值或最小值，目标规划只求最小值

5. 如果要使目标规划实际实现值不超过目标值，则相应的偏离变量应满足( )。 A. ( d^+ > 0 ) B. ( d^+ = 0 ) C. ( d^- = 0 ) D. ( d^- > 0, d^+ > 0 )

---

第6章 整数规划#

一、选择题#

1. 整数规划问题中，变量的取值可能是( )。 A. 整数 B. 0或1 C. 大于零的非整数 D. 以上三种都可能

2. 在下列整数规划问题中，分支定界法和割平面法都可以采用的是( )。 A. 纯整数规划 B. 混合整数规划 C. 0-1规划 D. 线性规划

3. 下列方法中用于求解分配问题的是( )。 A. 单纯形表 B. 分枝定界法 C. 表上作业法 D. 匈牙利法

4. 下列说法正确的是( )。 A. 整数规划问题最优值优于其相应的线性规划问题的最优值 B. 用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解 C. 用分支定界法求解一个极大化的整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，再进行比较剪枝 D. 分支定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分支迭代求出最优解

5. 资源数大于任务数的目标最小化分派问题需要( )。 A. 增加任务数至等于资源数，并赋任意值 B. 增加任务数至等于资源数，并赋0值 C. 增加任务数至等于资源数，并赋M(无限大)值 D. 可以直接求解

6. 用分枝定界法求最大值的整数规划时( )。 A. 分枝后子问题的最优目标函数值可能变大 B. 分枝后子问题的最优目标函数值可能不变 C. 若某个分枝的最优目标函数值大于其它分支，则该分支得到了最优解 D. 以上说法均不对

二、判断题#

1. 整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标函数值。 (✘)

2. 用分支定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界。 (✔)

3. 指派问题效率矩阵的每个元素都乘上同一个常数( k )，将不影响最优指派方案。 (✔)

4. 指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解。 (✘)

5. 求解0-1规划的隐枚举法是分支定界法的特例。 (✔)

6. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。 (✘)

7. 分支定界法可用于解纯整数或混合的整数规划问题。 (✔)

8. 0-1型整数规划是整数规划中的特殊情形，它的变量( x_i )仅取值0或1。 (✔)

9. 指派问题是整数规划。 (✔)

10. 指派问题可视为一类运输问题。 (✔)

11. 割平面的含义是增加约束方程以缩小整数规划问题( A )对应的线性规划( B )问题的可行域。 (✔)

三、填空题#

1. 若存在非整数解并且目标值 优于 一个整数解的目标值，需要继续分支。

2. 当松弛问题最优解中某个变量 不满足 整数要求时，分支定界法和割平面法都需要添加约束方程。

---

第8章 动态规划#

一、选择题#

1. 用DP方法处理资源分配问题时，通常总是选阶段初资源的拥有量作为决策变量( )。 A. 正确 B. 错误 C. 不一定 D. 无法判断

二、填空题#

1. 设备更新问题中，状态变量通常表示 机器役龄。

2. 动态规划的两种基本解法是 逆推解法 和 顺推解法。

3. 动态规划中反映当前阶段决策产生结果的指标称为 阶段指标。

三、判断题#

1. 在动态规划模型中，问题的阶段数等于问题中的子问题的数目。 (✔)

2. 动态规划中，定义状态时应保证在各个阶段中所做决策的相互独立性。 (✘)

3. 动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做出的决策。 (✔)

4. 对一个动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。 (✘)

5. 动态规划计算中的“维数障碍”主要是由于问题中阶段数的急剧增加而引起。 (✘)

6. 一个动态规划问题若能用网络表达时，节点代表各阶段的状态值，各条弧代表了可行的方案选择。 (✔)

7. 动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策问题。 (✔)

8. 动态规划的最优性原理简而言之就是一个最优策略的子策略总是最优的。 (✔)

9. 动态规划方法有逆序解法和顺序解法之分，其关键在于正确写出动态规划的递推关系式，故递推方式有逆推和顺推两种形式。一般而言，当初始状态给定时，用逆推解法比较方便；而当终止状态给定时，用顺推解法比较方便。 (✔)

10. ( k )阶段指标函数一般也称为( k )子过程指标函数。 (✘)

---

第9章 图与网络#

一、选择题#

1. 下列错误的结论是( )。 A. 流量非负 B. 容量非负 C. 容量不超过流量 D. 发点流出的合流等于流入收点的合流

2. 下列正确的结论是( )。 A. 最大流等于最大流量 B. 可行流是最大流当且仅当存在发点到收点的增广链 C. 可行流是最大流当且仅当不存在发点到收点的增广链 D. 调整量等于增广链上点标号的最大值

3. 连通图( G )有( n )个点，其部分树是( T )，则有( )。 A. ( T )有( n )个点，( n )条边 B. ( T )有( n )个点，( n - 1 )条边 C. ( T )的长度等于( G )的每条边的长度之和 D. ( T )有( n - 1 )个点，( n )条边

4. 求最短路的计算方法有( )。 A. 加边法 B. Floyd算法 C. 破圈法 D. Ford-Fulkerson算法

5. 求最大流的计算方法有( )。 A. Dijkstra算法 B. Floyd算法 C. 加边法 D. Ford-Fulkerson算法

6. 某配电站要向由其供电的五个小区铺设电缆，此时应采用的方法是( )。 A. 最短路线法 B. 最小树法 C. 最大流量法 D. 表上作业法

7. 一个居民住宅区的道路构成图是( )。 A. 树 B. 不连通图 C. 连通图 D. 有向图

8. 关于图论中图的概念，以下叙述( )正确。 A. 图中的有向边表示研究对象，结点表示衔接关系 B. 图中的点表示研究对象，边表示点与点之间的关系 C. 图中任意两点之间必有边 D. 图的边数必定等于点数减1

9. 关于树的概念，以下叙述( )正确。 A. 连通无圈的图必定是树 B. 任一树中，去掉一条边仍为树 C. 树中的点数等于边数减1 D. 含( n )个点的树是唯一的

10. 为了在各住宅之间安装一条供暖管道，若要求所用材料最省，则应采用（ ）。 A. 求最大流量法 B. 求最小支撑树法 C. 求最短路线法 D. 树的逐步生成法

二、判断题#

1. 最大流问题中，弧上的流量不超过弧的容量。 (✔)

2. 对于有向图问题，增广链上所有的弧均为前向弧。 (✘)

三、填空题#

1. 在图论中，称 无圈的 连通图为树。

2. 求最小生成树问题，常用的方法有：破圈法 和 避圈法(Kruskal算法)。