欢迎来到线性规划的世界！

在算法建模 (Modelling with Algorithms) 的这一章中，你将学会如何做出「最佳」决策。无论是工厂如何在有限资源下实现利润最大化，还是物流公司如何在控制燃料成本的同时提升效率，线性规划 (Linear Programming, LP) 都是他们所依赖的数学工具。别担心一开始会看到很多术语——其实线性规划的核心非常简单，就是找到善用现有资源的最佳方法！

1. 问题建模 (Formulation)

在解决问题之前，我们必须先将它从「文字描述」转译成「数学语言」，这个过程称为建模 (Formulation)。

线性规划的组成要素

  • 决策变量 (Decision Variables)： 代表你可以控制的项目。例如：设 \(x\) 为生产标准款单车的数量，\(y\) 为生产专业款单车的数量。
  • 目标函数 (Objective Function)： 这是你的最终目标。通常是想要极大化 (maximize)（例如利润）或极小化 (minimize)（例如浪费）。公式看起来像这样：\(P = 5x + 8y\)。
  • 限制条件 (Constraints)： 这是你面临的限制（如资金、时间、原料）。它们通常以不等式表示。例如：\(2x + 3y \le 60\)（表示可用的劳动工时）。
  • 非负限制 (Non-negativity)： 在现实世界中，你不可能生产负数量的单车！因此，我们必须加上 \(x \ge 0, y \ge 0\)。

标准型 (Standard Form)

当你的目标是极大化一个线性函数，所有的限制条件皆为小于或等于 (\(\le\)) 一个常数，且所有变量皆为非负数时，该线性规划问题即处于标准型。

重点速览：
变量： 我们要选择什么？
目标： 我们的目标是什么？
限制： 有什么规则必须遵守？

核心观念： 建模就是将文字题目转化为一组方程与不等式的过程。

2. 松弛变量与增广型 (Slack Variables and Augmented Form)

直接处理不等式比较困难，我们更偏好使用等式。为了将 \(\le\) 不等式转换为 \(=\) 等式，我们需要引入一个松弛变量 (slack variable)。

类比：想象你有 50 英镑的预算，你花了 \(x\) 英镑。那剩下的「松弛量」就是你口袋里的零钱。花费 + 余额 = 50 英镑。

运作方式：

如果你的限制条件是 \(2x + y \le 10\)，加上一个松弛变量 \(s_1\) 后会变成：
\(2x + y + s_1 = 10\)，其中 \(s_1 \ge 0\)。
这就是所谓的增广型 (augmented form)（也称为松弛型）。

常见错误： 忘记松弛变量也必须是非负的 (\(s \ge 0\))。

3. 图解法 (2-D 问题)

如果问题只有两个变量 (\(x\) 和 \(y\))，你可以直接在图表上画出来解决！

解题步骤：

  1. 画出直线： 将不等式视为方程（例如，画出直线 \(x + y = 10\)）。
  2. 找出可行解区域 (Feasible Region)： 这是图表上满足所有限制条件的区域。可以将其视为「安全区」。
  3. 处理无解情况： 如果没有任何区域同时满足所有规则，则该问题为不可行 (infeasible)——即无解！
  4. 找到最佳点： 最佳解总是在可行解区域的顶点 (vertex)（角落）。你可以通过以下方式找到它：
    • 顶点测试 (Vertex Testing/Enumeration)： 计算每一个角落的目标函数值进行比较。
    • 目标线法 (Objective Line Method)： 画出一条代表目标函数的直线，并将其平行移动，直到接触到「安全区」最远的边界点。

整数线性规划 (Integer Linear Programming, ILP)

有时变量必须是整数（你不可能卖出半台单车）。这就是整数线性规划 (ILP)。
警告： 最好的整数解可能不是「数学计算结果」最接近的整数。你必须检查可行解区域内附近的所有整数点。

你知道吗？ 尽管我们生活在三维空间中，你依然可以想象三维的线性规划，其可行解区域就像一个立体的晶体，而限制条件则是平面！

4. 单纯形法 (The Simplex Method)

如果有 10 个变量怎么办？你没法画出 10 维的图表！单纯形法 (Simplex Method) 是一种代数算法，它会从可行解区域的一个角落移动到另一个「更好」的角落，直到找到最佳解为止。

关键术语：

  • 单纯形表 (Tableau)： 用于组织方程的表格。
  • 主元 (Pivot)： 表格中用来转换到下一个角落的特定数值。
  • 基变量 (Basic Variables)： 当前顶点中「活跃」的变量。
  • 非基变量 (Non-basic Variables)： 当前顶点中值为零的变量。

运作逻辑：

算法会检查单纯形表的最后一行（目标函数行）。如果出现负数（在极大化问题中），代表我们还有提升利润的空间！我们选择一个主元列与行，执行「列运算」来建立新的表格，并不断重复，直到最后一行所有的数值皆为正数或零。

别担心这看起来很复杂！ 只要把它想成一种系统性的方法，让你不用画图也能检查形状的所有角落。

重点速览： 当目标函数值无法再提升时，单纯形法就会停止。

5. 非标准型问题

有时候规则会改变，以下是处理方法：

  • 大于等于限制 (\(\ge\))： 这需要使用两阶段单纯形法 (Two-Stage Simplex)。在第一阶段，你需要先找到一个合法的起始顶点。
  • 等式限制 (\(=\))： 可以拆解为两个不等式：\(x \le 4\) 与 \(x \ge 4\)。
  • 极小化问题： 大多数软件与单纯形法预设为极大化。若要极小化成本，你可以改为极大化成本的负值！

6. 作为线性规划的网络问题

线性规划最酷的地方在于，它可以解决许多你已经学过的网络问题！

  • 最短路径 (Shortest Path)： 寻找最快路径可以写成一个极小化总距离的线性规划问题。
  • 最大流 (Maximum Flow)： 计算管道流量可以写成一个极大化流量变量的线性规划问题。
  • 配对/分配问题 (Matching/Allocation)： 将工人和工作进行最佳化分配以最小化总成本，这也是经典的线性规划问题。

核心观念： 线性规划是一个「通用」工具——几乎任何涉及线性规则的问题都可以用它来处理。

7. 使用软件

在现实世界中，我们使用电脑来解决复杂的线性规划问题。你需要具备解读输出结果的能力：

  • 最佳值 (Optimal Value)： 最终的「最佳」结果（例如，最大利润 = 500 英镑）。
  • 变量值 (Variable Values)： 每一项应该生产多少数量（例如，\(x=10, y=5\)）。
  • 松弛量 (Slack)： 告诉你某个资源是否被完全使用（松弛量 = 0），还是有剩余（松弛量 > 0）。

总结： 无论是手算、作图还是用电脑求解，线性规划的核心都是压力（限制条件）下的最佳化。只要掌握建模，剩下的就只是遵循算法步骤而已！