算法设计 第7讲 线性规划 章节练习

第7讲 线性规划 章节练习

---

一、单项选择题（共30题）

线性规划基本概念与标准形（第1-8题）

第1题线性规划问题的标准形（standard form）的基本要求是：

A. 目标函数为最小化，所有约束为 ≤ 不等式，变量无符号限制
B. 目标函数为最大化或最小化均可，约束由 ≤、=、≥ 混合构成
C. 目标函数为最大化，所有约束为 ≤ 形式，所有变量非负
D. 目标函数为最小化，所有约束为 ≥ 形式，变量可为负

第2题将最小化问题 min cᵀx 转换为标准形（max 形式）时，正确的做法是：

A. 直接改为 max cᵀx
B. 改为 max –cᵀx，最优解 x* 不变
C. 改为 min –cᵀx
D. 保持 min 不变，仅改变约束形式

第3题设某线性规划问题中含有一个自由变量 x（无符号限制），将其转换为标准形时应：

A. 直接令 x 为任意实数
B. 用 x⁺ – x⁻ 替换 x，其中 x⁺ ≥ 0，x⁻ ≥ 0
C. 忽略 x 的符号限制
D. 添加约束 x ≥ 0

第4题将约束 ∑ a_i x_i ≥ b 转换为标准形中的 ≤ 约束时，应：

A. 直接写为 ∑ a_i x_i ≤ b
B. 两边乘以 –1 得 ∑ (–a_i) x_i ≤ –b
C. 添加松弛变量后写为等式
D. 保持 ≥ 不变

第5题标准形线性规划的矩阵形式为 max cᵀx, s.t. Ax ≤ b, x ≥ 0。其中矩阵 A 的维度为：

A. n × m（n 个变量，m 个约束）
B. m × n（m 个约束，n 个变量）
C. n × n
D. m × m

第6题线性规划问题的可行域（feasible region）的几何性质是：

A. 一个凸集（convex set）
B. 一个非凸集
C. 有限个离散点的集合
D. 总是无界的

第7题线性规划中，“无界”（unbounded）是指：

A. 可行域为空集
B. 存在可行解但目标函数值可以无限增大（最大化问题）或无限减小（最小化问题）
C. 变量个数超过约束个数
D. 目标函数为常数

第8题以下哪个优化问题可以转化为线性规划进行求解？

A. 最短路径问题
B. 最大流问题
C. 二分图最大匹配问题
D. 以上都可以

---

松弛形式与基本/非基本变量（第9-16题）

第9题将标准形中的 ≤ 约束转化为松弛形式（slack form）时，引入松弛变量后的约束形式为：

A. ∑ a_i x_i + s = b，s ≥ 0
B. ∑ a_i x_i – s = b，s ≥ 0
C. ∑ a_i x_i + s ≤ b，s ≥ 0
D. ∑ a_i x_i + s ≥ b，s ≥ 0

第10题松弛形式中，基本变量（basic variables）是指：

A. 目标函数中出现的变量
B. 在每个等式约束中单独出现在等式左侧的变量，每个等式恰好对应一个基本变量
C. 取值始终为 0 的变量
D. 系数矩阵中列向量线性无关的变量

第11题松弛形式中，非基本变量（nonbasic variables）是指：

A. 不在任何约束中出现的变量
B. 不在目标函数中的变量
C. 出现在目标函数中、当前被设为 0 的变量
D. 系数为负的变量

第12题在单纯形算法的初始松弛形式中，所有非基本变量被设为：

A. 0
B. 1
C. 对应基本变量的值
D. 随机确定

第13题将标准形转换为松弛形式后，基本变量的值可以通过以下方式计算：

A. 将非基本变量全部设为 0，代入等式约束直接读出基本变量的值
B. 求解完整的线性方程组
C. 通过目标函数反推
D. 随机初始化

第14题设有标准形约束：x₁ + 2x₂ ≤ 5，x₁ ≥ 0，x₂ ≥ 0。引入松弛变量后得到的等式为：

A. x₁ + 2x₂ + s₁ = 5，s₁ ≥ 0
B. x₁ + 2x₂ – s₁ = 5，s₁ ≥ 0
C. x₁ + 2x₂ + s₁ = 5，s₁ 无符号限制
D. x₁ + 2x₂ = 5 + s₁，s₁ ≥ 0

第15题在松弛形式中，设基本变量集合为 B，非基本变量集合为 N。将非基本变量全部设为 0 后得到的解称为基本解（basic solution）。这个基本解：

A. 一定可行（满足所有非负约束）
B. 一定不可行
C. 可能可行也可能不可行，需要检查是否满足所有非负约束
D. 一定是最优解

第16题线性规划松弛形式中，设约束个数为 m，变量总个数（包括松弛变量）为 n，则基本变量的个数为：

A. n
B. m
C. n – m
D. min(m, n)

---

单纯形算法（第17-26题）

第17题单纯形算法每次迭代中的核心"转轴"（pivot）操作包含以下关键步骤：

A. 随机选择一个变量直接设为非基本变量
B. 选择一个进入变量和一个离开变量，通过高斯消元重新表达系统，交换变量的基本/非基本角色
C. 直接求解所有变量的最优值
D. 将所有非基本变量加 1

第18题在单纯形算法（最大化问题）中，选择进入变量（entering variable）的标准通常是：

A. 选择目标函数中系数为负的非基本变量
B. 选择目标函数中系数为正且最大的非基本变量（Dantzig 规则 / STF）
C. 随机选择一个非基本变量
D. 选择约束条件中系数最小的非基本变量

第19题STF 规则（又称 Dantzig 规则）在选择进入变量时，对于最大化问题，优先选择：

A. 目标函数中负系数绝对值最大的非基本变量
B. 目标函数中正系数最大的非基本变量
C. 目标函数中系数绝对值最小的非基本变量
D. 约束中系数最大的非基本变量

第20题选择离开变量（leaving variable）的最小比率检验（ratio test）中，对于进入变量 x_e，在每个约束 i 上计算比率 Δ_i / a_{ie}（其中 a_{ie} > 0），然后：

A. 选择最大比率对应的约束中的基本变量作为离开变量
B. 选择最小比率对应的约束中的基本变量作为离开变量
C. 选择比率最接近 1 对应的约束中的基本变量
D. 选择第一个约束中的基本变量

第21题在最小比率检验中，如果对于某个约束 i 有 a_{ie} ≤ 0（其中 x_e 为进入变量），则该约束：

A. 对 x_e 的增长不构成限制，无需参与比率检验
B. 对应的基本变量被选为离开变量
C. 表示该约束导致问题无解
D. 表示该约束无效

第22题单纯形算法终止（达到最优）的条件是（对于最大化问题）：

A. 所有基本变量都已被选为进入变量
B. 目标函数中所有非基本变量的系数都 ≤ 0
C. 目标函数值不再变化
D. 所有约束都变为等式

第23题若在单纯形算法的某次迭代中，对于选定的进入变量 x_e，所有约束的系数 a_{ie} 都 ≤ 0，这意味着：

A. 当前解已经是最优解
B. 线性规划问题无可行解
C. 线性规划问题无界——x_e 可以无限增大而不违反任何约束，目标函数值趋于无穷
D. 需要重新选择一个进入变量

第24题单纯形算法一次迭代中各步骤的正确顺序是：

A. 选择离开变量 → 选择进入变量 → 执行转轴操作
B. 选择进入变量 → 执行转轴操作 → 选择离开变量
C. 选择进入变量 → 最小比率检验选择离开变量 → 执行转轴操作
D. 执行转轴操作 → 选择进入变量 → 选择离开变量

第25题在单纯形算法的转轴操作中，离开变量所在行称为主元行（pivot row），进入变量所在列称为主元列（pivot column）。转轴操作的结果是：

A. 将主元行对应的约束从系统中删除
B. 通过行变换将主元行中进入变量的系数化为 1，其他行中该变量的系数化为 0，从而实现进入变量与离开变量的角色互换
C. 交换两个约束的顺序
D. 将当前目标函数值归零

第26题以下关于单纯形算法时间复杂度的说法正确的是：

A. 单纯形算法在最坏情况下是指数时间复杂度的（存在 Klee-Minty 反例）
B. 单纯形算法总是多项式时间复杂度的
C. 单纯形算法只能求解变量个数不超过 2 的问题
D. 单纯形算法只能求解无约束问题

---

几何解释与扩展概念（第27-30题）

第27题从几何角度看，线性规划的可行域（标准形 Ax ≤ b, x ≥ 0）是一个：

A. 多面体（polyhedron），是凸集
B. 圆形区域
C. 若干离散点的集合
D. 曲线围成的区域

第28题从几何角度看，单纯形算法从一个顶点出发沿棱边移动到相邻顶点，每次移动后目标函数值的变化是（最大化问题）：

A. 严格增大（或至少不减小）
B. 严格减小
C. 可能增大也可能减小
D. 随机变化

第29题如果线性规划问题的可行域非空且最优目标值有限，则最优解一定：

A. 在可行域的某个顶点（极点/角点）上达到
B. 在可行域的内部达到
C. 在所有可行解上都达到
D. 在坐标原点达到

第30题对于标准形最大化问题 max cᵀx, s.t. Ax ≤ b, x ≥ 0，其对偶问题（dual problem）的形式为：

A. min bᵀy, s.t. Aᵀy ≥ c, y ≥ 0
B. min bᵀy, s.t. Aᵀy ≤ c, y ≥ 0
C. max bᵀy, s.t. Aᵀy ≤ c, y ≥ 0
D. min cᵀy, s.t. Aᵀy ≥ b, y ≥ 0

---

二、判断题（共20题，正确打 ✓，错误打 ✗）

线性规划基本概念与标准形（第1-5题）

1. （ ）标准形要求所有变量非负、所有约束为 ≤ 形式、目标函数为最大化。

2. （ ）将等式约束 ∑ a_i x_i = b 转换为标准形时，可以用两个不等式 ∑ a_i x_i ≤ b 和 ∑ (–a_i) x_i ≤ –b 来等价表示。

3. （ ）线性规划问题中，如果可行域是空集，则该问题称为"无界"（unbounded）。

4. （ ）线性规划问题的可行域一定是凸集。

5. （ ）将最小化问题 min cᵀx 转换为最大化问题时，只需将目标函数系数取反（max –cᵀx），最优解对应的变量取值不变。

松弛形式与基本/非基本变量（第6-10题）

6. （ ）在松弛形式中，基本变量的取值由非基本变量设为 0 后从等式约束中唯一确定。

7. （ ）松弛变量代表约束中尚未使用的"松弛量"（slack），在初始解（x = 0）中松弛变量的值等于对应的 b 值。

8. （ ）在松弛形式中，基本变量和非基本变量的角色在算法运行过程中保持不变。

9. （ ）每个 ≤ 约束对应引入一个松弛变量，用于将该不等式转换为等式。

10. （ ）松弛形式的目的在于将所有约束变为等式且所有变量非负，便于计算机化的代数运算。

单纯形算法（第11-16题）

11. （ ）单纯形算法每次迭代选择一个非基本变量逐渐增大，直到某个基本变量降为 0，然后进行转轴操作。

12. （ ）STF 规则（Dantzig 规则）对于最大化问题，优先选择目标函数中正系数最大的非基本变量作为进入变量。

13. （ ）最小比率检验选择使比率 Δ_i / a_{ie}（a_{ie} > 0）最小的约束对应的基本变量作为离开变量，以确保新的基本解满足所有非负约束。

14. （ ）如果最大化问题中所有非基本变量在目标函数中的系数都 ≤ 0，则当前解是最优解。

15. （ ）单纯形算法在最坏情况下可能需要指数次迭代（如 Klee-Minty 立方体反例），但在实践中通常非常高效。

16. （ ）在单纯形算法的转轴操作中，离开变量变为非基本变量，进入变量变为基本变量。

几何与对偶概念（第17-20题）

17. （ ）从几何角度看，单纯形算法沿着可行域多面体的棱边从一个顶点移动到另一个顶点。

18. （ ）线性规划的对偶问题的对偶问题仍然是原问题。

19. （ ）如果原问题有可行解且对偶问题也有可行解，则由强对偶定理可知，它们的最优目标值相等。

20. （ ）最大流问题可以转化为线性规划问题进行求解。

---

三、参考答案

单项选择题答案

题号	答案	解析
1	C	标准形的三个要求：目标函数最大化（max）、所有约束为 ≤ 形式、所有变量非负（x ≥ 0）。
2	B	将 min cᵀx 等价转化为 max –cᵀx。最优解 x* 保持不变，最优目标值的符号取反。
3	B	令 x = x⁺ – x⁻，其中 x⁺ ≥ 0，x⁻ ≥ 0，即可用两个非负变量替代一个自由变量。此方法会在问题中引入额外的变量和约束。
4	B	∑ a_i x_i ≥ b ⇔ ∑ (–a_i) x_i ≤ –b。两边乘以 –1 将 ≥ 转换为 ≤。
5	B	A 是 m × n 矩阵：m 行对应 m 个约束，n 列对应 n 个变量。
6	A	每个线性不等式定义半个空间（半平面），是凸集；凸集的交集仍是凸集。可行域是多个半空间的交集，故为凸集。
7	B	无界是指可行域非空但目标函数可以无限增大（max）或无限减小（min）。这与"不可行"（可行域为空）不同。
8	D	最短路径的距离约束 d_v ≤ d_u + w(u,v) 是线性的；最大流的容量约束和流量守恒是线性的；二分图最大匹配可转化为网络流，因而也可写为 LP。
9	A	对约束 ∑ a_i x_i ≤ b 引入松弛变量 s ≥ 0，得 ∑ a_i x_i + s = b。s 表示未使用的资源量。
10	B	松弛形式中，每个等式约束的左侧都有一个专属变量（基本变量），该变量的系数为 1，且不出现在其他约束的目标函数中。
11	C	在松弛形式的初始表达中，非基本变量出现在目标函数中。算法中将它们设为 0，然后计算基本变量的值。每次转轴操作交换 B 和 N 中的变量。
12	A	单纯形算法每次迭代都将所有非基本变量设为 0，从等式约束直接计算基本变量的取值。这对应于可行域的一个顶点。
13	A	当非基本变量全为 0 时，每个等式约束左侧只剩一个基本变量，其值等于右侧常数项 b（经代入后）。
14	A	x₁ + 2x₂ ≤ 5 ⇒ x₁ + 2x₂ + s₁ = 5，s₁ ≥ 0。松弛变量 s₁ 测量约束左右两侧的差值。
15	C	基本解可能违反某些非负约束（如某个基本变量为负值），此时该基本解不可行。只有满足所有非负约束的基本解才是可行基本解。
16	B	m 个等式约束对应 m 个基本变量（每个等式一个）。总变量 n = m（基本变量）+ (n-m)（非基本变量）。
17	B	转轴（pivot）操作的核心是选择进入变量和离开变量，然后通过行变换重新表达系统，使进入变量的系数在主元行中为 1、在其他行中为 0，从而实现角色互换。
18	B	对于最大化问题，目标函数中正系数最大的非基本变量增加时，目标值的增长速率最快。Dantzig 规则（STF）选择该变量作为进入变量。
19	B	STF（Steepest-Textbook-First）/ Dantzig 规则：选择目标函数中正系数最大的非基本变量进入。直觉上，该变量每增加一单位对目标值的贡献最大。
20	B	最小比率检验选 Δ_i / a_{ie}（a_{ie} > 0）中最小者对应的基本变量离开。这确保在增加 x_e 时，所有基本变量保持非负，且第一个触及 0 的基本变量离开。
21	A	a_{ie} > 0 时，x_e 增加会使该约束左侧增大，可能使基本变量变为负值；a_{ie} ≤ 0 时，x_e 增加不构成威胁，故无需参与比率检验。
22	B	当所有非基本变量在目标函数中的系数都 ≤ 0 时，增加任何一个非基本变量都会使目标值下降（或不变），因此当前解已是最优（对最大化问题）。
23	C	若所有 a_{ie} ≤ 0，则 x_e 可无限增大而所有基本变量保持非负，目标函数值趋于 +∞，故问题无界。
24	C	正确的顺序：① 根据目标函数系数选择进入变量 → ② 对进入变量执行最小比率检验选择离开变量 → ③ 执行转轴操作更新系统。
25	B	转轴操作通过高斯消元（行变换）将主元行中进入变量的系数化为 1，并将其他行（包括目标函数行）中进入变量的系数化为 0，从而交换 B 和 N 中变量的角色。
26	A	Klee-Minty 构造了一类线性规划问题，单纯形算法在其上需要指数次迭代（2ⁿ 量级）。但实际应用中迭代次数通常为 O(n) 到 O(n³)。
27	A	标准形 Ax ≤ b, x ≥ 0 的可行域是多个半空间的交集，形成一个凸多面体。单纯形算法即在此多面体的顶点间移动。
28	A	单纯形算法保证目标值单调变化：最大化问题中每次沿棱边移动到相邻顶点时目标值严格增大（除非退化），直至达到最优。
29	A	线性规划基本定理：如果 LP 有有限的最优解，则至少有一个最优解出现在可行域的某个顶点（极点）上。单纯形算法正是利用这一性质搜索顶点。
30	A	标准形 max cᵀx, s.t. Ax ≤ b, x ≥ 0 的对偶为 min bᵀy, s.t. Aᵀy ≥ c, y ≥ 0。原问题变量 x 对应不等式约束，对偶变量 y 对应原问题约束。

判断题答案

题号	答案	解析
1	✓	标准形三要素：目标函数为最大化（max）、所有约束为 ≤ 形式、所有变量非负。
2	✓	∑ a_i x_i = b 等价于 ∑ a_i x_i ≤ b 且 ∑ a_i x_i ≥ b。对后者两边乘 –1 转换为标准形：∑ (–a_i) x_i ≤ –b。
3	✗	可行域为空称为"不可行"（infeasible）。"无界"指可行域非空但目标值可无限变化。两者是不同的概念。
4	✓	线性不等式定义半空间（凸集），凸集的交集仍是凸集。因此可行域（多个半空间的交集）一定是凸集。
5	✓	min cᵀx = –max (–cᵀx)。最优解 x* 在两种表述下完全相同，仅最优值变号。
6	✓	松弛形式中，非基本变量设为 0 后，每个等式约束中只剩一个基本变量，其值可直接读出。
7	✓	松弛变量 s = b – ∑ a_i x_i，当所有原变量 x = 0 时，s = b。
8	✗	单纯形算法的每次转轴操作都会交换一个基本变量和一个非基本变量的角色。因此 B 和 N 的内容在迭代中不断变化。
9	✓	每个 ≤ 约束引入一个非负松弛变量，将不等式转化为等式。
10	✓	松弛形式消除了不等式约束，使系统所有约束为线性等式且变量非负，便于计算机化的矩阵运算和单纯形算法实现。
11	✓	选择进入变量 x_e 后逐渐增加其值，同时保持其他非基本变量为 0。当某个基本变量被"推"到 0 时，该基本变量成为离开变量。
12	✓	Dantzig 规则（STF）：选目标函数中正系数最大的非基本变量进入，以单位增长带来最大的目标值增量。
13	✓	最小比率检验保证：在增加 x_e 的过程中，第一个触及 0 的基本变量被选中离开，确保新基本解中所有变量非负。
14	✓	最大化问题中，若所有非基本变量的目标系数 ≤ 0，则增大任一非基本变量只会降低（或不变）目标值，当前解已最优。
15	✓	Klee-Minty（1972）构造了变形立方体反例，单纯形算法需遍历全部 2ⁿ 个顶点。但实践中迭代次数通常约为 2n 到 3n。
16	✓	转轴（pivot）即基变换：离开变量离开基（变为非基本），进入变量进入基（变为基本）。
17	✓	可行域的每个顶点对应一个基本可行解。单纯形算法沿棱边从当前顶点移动到目标值更优的相邻顶点。
18	✓	对偶的对偶（dual of dual）等价于原问题（primal）。这是对偶理论的基本性质之一。
19	✓	强对偶定理（Strong Duality Theorem）：如果原问题和对偶问题都有可行解，则它们的最优目标值相等。如果一方无界，则另一方不可行。
20	✓	最大流的容量约束（f(u,v) ≤ c(u,v)）和流量守恒（∑ f(u,v) = ∑ f(v,u)）均为线性约束，目标函数 max ∑ f(s,v) 也是线性的，可直接写为 LP。