好嘞，阿杰 👍 我给你整理一份 线性规划单纯形法的精解笔记，尽量通俗易懂 + 数学严谨。

线性规划单纯形法精解

一、线性规划问题回顾

线性规划 (Linear Programming, LP) 的标准形式一般写作： Maximize z=cTx\text{Maximize } z = c^T x

约束条件为： Ax≤b,x≥0Ax \leq b, \quad x \geq 0

其中：

• x=(x1,x2,…,xn)x = (x_1, x_2, \dots, x_n) 决策变量
• c=(c1,c2,…,cn)c = (c_1, c_2, \dots, c_n) 目标函数系数
• AA 是约束矩阵，bb 是右端常数向量

目标：在约束范围内，找到使 zz 最大（或最小）的解。

二、基本思想

单纯形法基于一个几何直观：

• 可行解空间是一个凸多面体（由线性约束交集形成）。
• 最优解一定在顶点（基点）处。
• 单纯形法的步骤：
  1. 从一个可行基点出发。
  2. 沿着边移动到更优的基点。
  3. 直到没有更优的方向为止 → 得到最优解。

三、转化为标准形式

为了应用单纯形法，需要把问题转成 标准形式：

1. 所有约束变成 等式： Ax=bAx = b 如果原来是 ≤\leq，就加上 松弛变量 ss： a1x1+a2x2≤b⇒a1x1+a2x2+s=b,  s≥0a_1x_1 + a_2x_2 \leq b \quad \Rightarrow \quad a_1x_1 + a_2x_2 + s = b, \; s \geq 0
2. 变量非负： x≥0,  s≥0x \geq 0, \; s \geq 0

这样我们就得到一个「标准单纯形表」。

四、单纯形表

单纯形法用“表格”来做计算。一个单纯形表通常包含：

• 基变量：当前进入解中的变量（初始是松弛变量）。
• 检验数（z 行的系数）：判断是否有改进空间。
  • 如果所有检验数 ≤0\leq 0，当前解最优。
  • 如果有正数，说明还可以改进。

五、迭代步骤

单纯形法迭代分为 3 步：

1. 选入基变量（Entering variable）
   • 选择目标函数行中 最正的系数（最大检验数）。
   • 对应的变量进入基。
2. 选出基变量（Leaving variable）
   • 对每一行，计算 biaij\frac{b_i}{a_{ij}}（只考虑 aij>0a_{ij} > 0）。
   • 最小比值对应的基变量出基。
3. 更新单纯形表（Pivot）
   • 用高斯消元的方法，把选入变量列变成标准基向量。
   • 更新表格。

然后继续循环，直到没有正的检验数。

六、例题精解

例题：
最大化 z=3×1+2x2z = 3x_1 + 2x_2

约束条件： x1+x2≤4x_1 + x_2 \leq 4 x1≤2x_1 \leq 2 x1,x2≥0x_1, x_2 \geq 0

Step 1: 标准形式

引入松弛变量 s1,s2s_1, s_2： x1+x2+s1=4x_1 + x_2 + s_1 = 4 x1+s2=2x_1 + s_2 = 2

目标函数： z=3×1+2x2z = 3x_1 + 2x_2

Step 2: 初始单纯形表

Step 3: 选入、选出基变量

• 目标行中最大正数是 -3（取绝对值 3） → 选入 x1x_1。
• 计算比值：
  • 4/1=44/1 = 4
  • 2/1=22/1 = 2 → 最小比值，s2s_2 出基。

Step 4: 枢轴运算

把 x1x_1 替换 s2s_2，得到新表。

Step 5: 再次选择

• 目标行最大正数是 -2（取绝对值 2） → 选入 x2x_2。
• 比值：
  • 2/1=22/1 = 2 → s1s_1 出基。

Step 6: 再次枢轴

得到最终表：

Step 7: 结论

• 所有检验数 ≤0\leq 0，最优解得到。
• 最优解： x1=2,  x2=2x_1 = 2, \; x_2 = 2
• 最大值： z=10z = 10

七、总结

1. 单纯形法是 迭代优化，核心就是“进基/出基 + 枢轴”。
2. 几何直观：从一个顶点走到另一个顶点。
3. 算法保证 有限步收敛，除非存在无界解或不可行解。

好嘞，阿杰 👍 我来帮你整理一个 单纯形法手工计算速查表，让你能一步一步操作，不用死记硬背。

📌 单纯形法手工计算速查表（Max 问题标准形式）

1️⃣ 把问题写成标准形式

• 目标函数： max⁡z=c1x1+c2x2+⋯+cnxn\max z = c_1x_1 + c_2x_2 + \cdots + c_nx_n
• 约束条件： a11x1+a12x2+⋯+a1nxn+s1=b1a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n + s_1 = b_1 a21x1+a22x2+⋯+a2nxn+s2=b2a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n + s_2 = b_2 （每个“≤”加一个松弛变量 si≥0s_i \geq 0）

2️⃣ 初始单纯形表（Simplex Tableau）

• 初始基变量：全部是松弛变量。
• z 行写作 −ci-c_i。

3️⃣ 单纯形迭代步骤（Pivot 流程）

Step 1: 选入基变量 (Entering variable)

• 看 z 行（目标函数行）。
• 找到 最负的系数（代表潜在增益最大）。
• 该列对应的变量 → 进基。

Step 2: 选出基变量 (Leaving variable)

• 对该列（进基变量所在列），计算比值： biaij(仅考虑 aij>0)\frac{b_i}{a_{ij}} \quad \text{(仅考虑 \(a_{ij} > 0\))}
• 取最小的比值 → 对应行的基变量 出基。

Step 3: 枢轴运算 (Pivot)

1. 把枢轴元素（进基列 & 出基行的交点）化为 1。
2. 该列其他元素变为 0（做高斯消元）。
3. 更新表格。

4️⃣ 检查最优性

• 如果 z 行所有系数 ≤ 0，则最优解得到。
• 否则回到 Step 1，继续迭代。

5️⃣ 读出结果

• 最优解 = 基变量对应的 b 列值。
• 非基变量 = 0。
• 最优目标函数值 = z 行右下角的常数项。

🔹 单纯形法速查流程图

标准形式化  →  建立初始单纯形表
                ↓
        有正的检验数？ —— 否 → 最优解
                ↓
        选入基变量 (z 行最正)
                ↓
        选出基变量 (最小比值法)
                ↓
        枢轴运算 (高斯消元更新表)
                ↓
                循环

🔸 小口诀

1. 入基看行底，出基算比值
2. 比值取最小，更新做消元
3. 底行全非正，最优解出现