阿杰，我给你整理一份 线性规划（Linear Programming, LP）单纯形法精解，从概念、标准形式、单纯形表、操作步骤到示例分析，条理清晰、重点突出。

---

一、线性规划概念

• 定义：线性规划是一种数学优化问题，目标是 在满足线性约束条件下，使线性目标函数最大化或最小化。
• 标准形式：

Maximize Z=c1x1+c2x2+⋯+cnxn\text{Maximize } Z = c_1 x_1 + c_2 x_2 + \dots + c_n x_n

约束条件： {a11x1+a12x2+⋯+a1nxn≤b1a21x1+a22x2+⋯+a2nxn≤b2⋮x1,x2,…,xn≥0\begin{cases} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \le b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n \le b_2 \\ \vdots \\ x_1, x_2, \dots, x_n \ge 0 \end{cases}

注：≤ 型约束是最常用的标准形式，方便转化为单纯形表。

---

二、单纯形法概念

• 目标：从初始基本可行解出发，通过一系列的 基变量入基、非基变量出基 操作，逐步优化目标函数，直到达到最优解。
• 关键思想：沿着可行域的顶点（极点）移动，每次都选择 目标函数最优方向。

---

三、标准化与引入松弛变量

• 对于约束：

a1x1+a2x2≤ba_1 x_1 + a_2 x_2 \le b

引入 松弛变量 s≥0s \ge 0： a1x1+a2x2+s=ba_1 x_1 + a_2 x_2 + s = b

这样可以将不等式变成等式，便于单纯形表计算。

---

四、单纯形表结构

基变量	x1x_1	x2x_2	…	s1s_1	…	RHS
s1s_1	a11	a12	…	1	…	b1
s2s_2	a21	a22	…	0	…	b2
…	…	…	…	…	…	…
Z	-c1	-c2	…	0	…	0

• RHS：右端常数（约束 b）
• Z 行：目标函数的负系数（求最大值时）
• 基变量：当前可行解中非零变量

---

五、单纯形法操作步骤

1. 构建初始单纯形表
   • 引入松弛变量
   • 基变量初始为松弛变量，RHS 即为 b
2. 选择入基变量（Pivot Column）
   • 选择 Z 行中最小的负数列（最大化问题）
3. 选择出基变量（Pivot Row）
   • 用 RHS / 对应列元素 计算比值，取最小正比值
   • 对应行的基变量出基
4. 枢轴操作（Pivot Operation）
   • 将入基变量对应列变为单位列
   • 调整表格，其余行减去合适倍数
5. 检查最优性
   • Z 行没有负数 → 已达最优解
   • 有负数 → 回到第 2 步
6. 读解
   • 基变量对应的 RHS 为最优值
   • 非基变量为 0

---

六、示例解析

问题： Maximize Z=3×1+5×2\text{Maximize } Z = 3x_1 + 5x_2

约束： {x1+2×2≤63×1+2×2≤12×1,x2≥0\begin{cases} x_1 + 2x_2 \le 6 \\ 3x_1 + 2x_2 \le 12 \\ x_1, x_2 \ge 0 \end{cases}

步骤 1：引入松弛变量 {x1+2×2+s1=63×1+2×2+s2=12×1,x2,s1,s2≥0\begin{cases} x_1 + 2x_2 + s_1 = 6 \\ 3x_1 + 2x_2 + s_2 = 12 \\ x_1, x_2, s_1, s_2 \ge 0 \end{cases}

---

步骤 2：初始单纯形表

基变量	x1	x2	s1	s2	RHS
s1	1	2	1	0	6
s2	3	2	0	1	12
Z	-3	-5	0	0	0

---

步骤 3：选择入基变量

• Z 行最小负数：-5 → x2 入基

步骤 4：选择出基变量

• 比值：
  • s1：6 / 2 = 3
  • s2：12 / 2 = 6
• 取最小正比值 → s1 出基

步骤 5：枢轴操作 → 更新表格

更新后表格（省略计算细节）：

基变量	x1	x2	s1	s2	RHS
x2	0.5	1	0.5	0	3
s2	2	0	-1	1	6
Z	-0.5	0	2.5	0	15

---

步骤 6：检查最优性

• Z 行无负数 → 已达最优解

最优解： x1=0,x2=3,Zmax=15x_1 = 0, x_2 = 3, Z_{\text{max}} = 15

---

七、单纯形法注意事项

1. 退化（Degeneracy）
   • RHS 中最小比值为 0，可能导致循环，需要使用 Bland’s Rule
2. 无界解（Unbounded）
   • 入基列对应比值全部 ≤ 0 → 无界
3. 可行解不存在
   • 初始松弛变量 RHS < 0，需要人工变量（Big-M 法 / 两阶段法）
4. 最大化 vs 最小化
   • 最小化问题可转化为最大化 −Z-Z 问题

---

八、总结

• 单纯形法核心：
  1. 基变量入基，非基变量出基
  2. 沿可行域顶点逐步优化目标函数
  3. 终止条件：目标函数系数全非负
• 应用：
  • 生产计划、运输优化、资源分配、网络流等
• 技巧：
  • 构建标准形式 → 构造初始表 → 枢轴操作 → 检查最优性 → 读解