deepread20｜第21章 线性规划详解

ONEPSOFT | 软考学习知识库

---

deepread20｜第21章 线性规划详解

一、定位

• 章节位置：第 21 章 项目管理科学基础 → 21.2.1 线性规划。
• 知识链条：线性规划是运筹学 " 资源有限求最优 " 的代表，在线性约束下极大/极小化线性目标。三要素：决策变量、目标函数、约束条件。
• 考试分量：综合知识考 " 三要素、适用场景 "；案例/计算偶尔考图解法（2 变量，求最优顶点）。单纯形法是图解法的一般化（>2 变量），理解其 " 建表，选入基，选离基，旋转 " 的迭代逻辑即可，考试以图解法为主。

二、教材原文精摘

以下依据第 4 版教材第 21 章 21.2.1 节（术语保留原貌）。例 21-8 的约束式本次 fetch 未完整录得（仅录 " 求 Smax=x₁+3x₂，约束略，最优解过 B(1,4)，Smax=13"），下方用与之同构的典型例题演示，最优顶点同样为 (1,4)、Smax=13。

• 定义：线性规划主要研究，①在有限资源下制订最优经营方案取得最佳经济效益；②在任务确定下合理安排使消耗资源最少。实质是在线性约束下追求目标函数最大/最小值。
• 三要素：决策变量、目标函数、约束条件。
• 例 21-8（教材结论）：Smax = x₁ + 3x₂，最优解 B(1,4)，Smax = 1 + 3×4 = 13。

三、系统解读（平实分点）

1. 一句话理解：手里的料/工时有限（约束），要产出最大（目标）。把 " 怎么分配 " 设成变量 x₁、x₂，列目标与约束，求最值。
2. 图解法（2 变量）：在坐标纸上画出每条约束（直线），可行域是它们 " 都满足 " 的公共区域，必是凸多边形；最优解一定在顶点上。把目标函数画成 " 等值线 " 平行往外推，最后贴到的顶点就是最优。
3. 单纯形法（通用）：把约束加 " 松弛变量 " 变等式，列表（单纯形表），反复做，①选 Cj−Zj 最大且为正的列入基；②比值最小（RHS/入基列正系数）的行离基；③旋转（高斯消元）得新表，直到 Cj−Zj 全 ≤0 即最优。
4. 为什么顶点最优：线性目标在凸多边形上的极值必在顶点取得（凸性）。所以图解法只需枚举顶点代入目标比较。
5. 土木类比：混凝土总量有限（约束），要生产 A、B 两种构件使利润最大（目标）；或有限台班安排两道工序使产值最大。2 种产品就画图，多了就上单纯形表。

四、工程举例（土木类比 + 数值）

例题（同构例 21-8）：max S = x₁ + 3x₂，约束：x₁ + x₂ ≤ 5，x₂ ≤ 4，x₁,x₂ ≥ 0。

图解法：

可行域顶点 O(0,0)、A(5,0)、B(1,4)、C(0,4)。

顶点	S = x₁+3x₂
O(0,0)	0
A(5,0)	5
B(1,4)	1+12 = 13
C(0,4)	12

最优解 B(1,4)，Smax = 13（等值线 x₁+3x₂=13 恰与可行域相切于 B）。

单纯形法（加松弛 s₁,s₂ ≥0，标准型）：

max S = x₁+3x₂+0s₁+0s₂；x₁+x₂+s₁=5；x₂+s₂=4。

表	Basic	Cb	x₁	x₂	s₁	s₂	RHS
初	s₁	0	1	1	1	0	5
初	s₂	0	0	1	0	1	4
初	Cj−Zj		1	3	0	0
1	x₂	3	0	1	0	1	4
1	s₁	0	1	0	1	−1	1
1	Cj−Zj		1	0	0	−3
2	x₁	1	1	0	1	−1	1
2	x₂	3	0	1	0	1	4
2	Cj−Zj		0	0	−1	−2

第 2 表 Cj−Zj 全 ≤0 → 最优：x₁=1, x₂=4, Smax=13。与图解法一致。

高项概念	土木 / 施工类比
决策变量 x₁,x₂	两种构件/两道工序的产量分配
目标函数	总利润 / 总产值
约束	材料上限、台班上限
顶点最优	资源组合的几个 " 边界方案 " 里挑最好

五、追问引导

• 线性规划三要素是什么？目标函数和约束必须 " 线性 " 意味着什么（不能有 x₁×x₂、x₁²）？
• 为什么图解法只比较 " 顶点 " 就行？可行域一定是凸多边形吗？
• 等值线 x₁+3x₂=S 往外推时，为什么 " 最后贴到 " 的顶点就是最大？若目标线与某条边平行会怎样（多个最优）？
• 单纯形法里松弛变量 s 是啥？它进基/出基分别代表什么（某约束的 " 剩余量 " 被用掉）？
• Cj−Zj 全 ≤0 为什么就最优了？入基列选 Cj−Zj 最大正的，离基行选 RHS/入基列正系数比值最小的，逻辑各是什么？