欢迎来到线性规划 (Linear Programming)！
你有没有想过物流公司是如何找出最便宜的路线，或者工厂是如何精确决定产品产量以获得最大利润的？这正是线性规划 (Linear Programming, LP) 的核心所在！这是一门在有限资源下作出最佳选择的数学艺术。在「算法建模 (Modelling with Algorithms)」这一部分，我们将利用线性规划把现实生活中的「应用题」转化为电脑（或聪明的学生）可以解决的数学问题。
1. 基本构建：问题建模 (Formulating the Problem)
在开始解决问题之前，我们需要掌握线性规划的语言。每个问题都包含三个主要部分：
决策变量 (Decision Variables)
这是你可以控制的事项。例如，如果你经营一家烘焙坊，你的变量可能是：
设 \(x\) = 制作巧克力蛋糕的数量。
设 \(y\) = 制作香草蛋糕的数量。
重要提示： 在线性规划中，变量必须代表数值，且通常是非负的（你不可能烘焙负 5 个蛋糕！）。
目标函数 (Objective Function)
这是你的目标。你是想获得最多利润（最大化 Maximisation）还是花费最少成本（最小化 Minimisation）？
例子： 如果每个巧克力蛋糕带来 £5 利润，每个香草蛋糕带来 £3 利润，你的目标就是最大化 \(P = 5x + 3y\)。
约束条件 (Constraints)
这是你的限制（即“规则”）。例如你可能只有 10kg 面粉或 8 小时的烤箱使用时间。
例子： 如果一个巧克力蛋糕用 2kg 面粉，香草蛋糕用 1kg，而你总共有 10kg 面粉：
\(2x + 1y \le 10\)
标准型 (Standard Form)
当满足以下条件时，线性规划问题处于标准型：
1. 你正在最大化一个线性函数。
2. 所有约束条件都写成“小于或等于”(\(\le\)) 一个常数。
3. 所有变量均为非负 (\(x, y \ge 0\)) 且为连续的（暂时来说，你可以制作 2.5 个蛋糕）。
快速回顾：
• 变量： 我在决定什么？（必须是数字！）
• 目标： 我的目标是什么？（最大化或最小化）
• 约束条件： 我的限制是什么？
2. 松弛变量 (Slack Variables) 与增广型 (Augmented Form)
算法喜欢处理等式 (\(=\)) 而非不等式 (\(\le\))。为了修正这一点，我们使用松弛变量 (Slack Variables)。
你可以把“松弛变量”想像成“剩余”的资源。如果你有 10kg 面粉，用了一些来烘焙，那么松弛变量 \(s\) 就是架子上闲置的面粉。
因此，\(2x + y \le 10\) 会变成 \(2x + y + s = 10\)。
当我们把这些松弛变量加入所有约束条件时，我们称之为增广型 (Augmented Form)。这是使用单纯形法 (Simplex Method) 的第一步！
3. 图解法 (Solving Graphically)（二维问题）
如果你只有两个变量 (\(x\) 和 \(y\))，你可以把问题画在图表上。别担心你的绘图技巧生疏，这一切都在于区域的划分！
可行域 (Feasible Region)
当你在图上标示出所有约束条件时，所有规则都能满足的重叠区域就称为可行域。在这个形状内的任何一点都是可能的解。
无可行解 (Infeasibility)： 如果你的约束条件太严格，导致没有任何区域能满足所有规则，那么该问题就是无可行解的（你实际上无法同时满足所有规则）。
寻找最优点 (Optimal Point)
“最佳”点通常位于可行域的顶点 (Vertices)（角位）。你可以通过两种方式找到它：
1. 目标线法 (Objective Line Method)： 画一条代表你目标的线（例如 \(5x + 3y = 15\)）。使用尺子将这条线沿着图表向改善的方向平行移动。当它离开可行域之前接触到的最后一个角位，就是你的最优点！
2. 枚举法 (Enumeration)： 将每一个角位的坐标代入你的目标函数，看看哪一个给出最大或最小值。
整数解怎么办？
有时你不能制作 2.5 个蛋糕；你需要整数。这就是整数线性规划 (Integer Linear Programming, ILP)。
常见错误： 直接将小数答案四舍五入到最接近的整数可能会让你得到一个位于可行域之外的点！相反，你应该检查小数解附近的“晶格点”(Lattice points，即整数坐标)。
4. 单纯形法 (The Simplex Method)
当你拥有三个或更多变量时，图解法就不管用了（除非你能看到四维空间！）。单纯形法是一种在可行域的各个角位之间进行代数“行走”，直到找到最佳点的方法。
单纯形表 (The Tableau)
我们将数字整理成一个称为单纯形表的网格。
• 基变量 (Basic Variables)： 这些是目前“拥有”约束条件的变量（通常在开始时是松弛变量）。
• 非基变量 (Non-Basic Variables)： 这些被设定为零。
• 主元 (The Pivot)： 为了移动到更好的角位，我们选择一个主元。我们选择一列（通常是利润行中负数值最大的那一列），然后使用“比值测试 (Ratio test)”来选择行。
几何基础
单纯形法的每一次行运算，实际上都是让你从可行域的一个角位移动到相邻且更好的角位。如果你在最大化问题的目标行中找不到负数，你就已经到达了山顶——你已经找到了最优解！
非标准问题（两阶段单纯形法）
如果约束条件是“大于或等于”(\(\ge\)) 或“等于”(\(=\)) 怎么办？标准单纯形法在这里会遇到困难。
我们使用两阶段单纯形法 (Two-Stage Simplex Method)。我们建立“人工变量 (Artificial Variables)”来找到起始点（第一阶段），一旦我们进入可行域，再解决实际问题（第二阶段）。
注：此课程大纲不需要知道“Big-M 法”——只需要两阶段法！
5. 现实世界中的线性规划：网络问题
线性规划是一个“通用算法”。你在本课程中学习的许多其他问题都可以写成线性规划形式：
• 最短路径： 最小化路径上的权重总和。
• 最大流： 最大化从源点到汇点移动的“货物”总量。
• 关键路径： 在项目网络中找出最长路径。
• 运输问题： 最小化将货物从多个工厂运送到多个商店的成本。
6. 使用软件
在现实世界中，线性规划问题拥有成千上万个变量，我们使用电子表格中的“规划求解 (Solver)”。
你的任务： 你需要能够观察并解读电脑输出的数据。
• 哪些变量是“基变量”？
• 是否还有剩余的松弛量 (Slack)（闲置资源）？
• 最终的目标函数值 (Objective value)是多少？
总结与重点
• 建模是关键： 如果你定义变量或约束条件错误，数学也救不了你！时刻检查：“\(x\) 是否代表一个具体数字？”
• 可行域： 图表上的“允许区域”。
• 松弛变量： “剩余的资源”。
• 单纯形法： 一种通过代数方式从角位跳转到角位，以寻找最高利润或最低成本的方法。
• 整数问题： 小心四舍五入；检查附近的整数点！
如果单纯形表一开始看起来充满了数字，别担心。请记住：每一个步骤都只是一种华丽的说法，意指“让我们尝试形状的另一个角位吧！”