KNOWECON WIKI

ARTICLE

线性规划

线性规划 (Linear Programming) 线性规划（Linear Programming，简称LP），是 运筹学 (Operations Research) 和 数学规划 (Mathematical programming) 中的一个重要分支。它是一种数学方法，用于在满足一组线性 等式 和 不等式 约束 (Constraints) 条件下，对一个线

浏览 32 更新 2025-10-26

线性规划 (Linear Programming)

线性规划（Linear Programming，简称LP），是 运筹学 (Operations Research) 和 数学规划 (Mathematical programming) 中的一个重要分支。它是一种数学方法，用于在满足一组线性 等式 和 不等式 约束 (Constraints) 条件下，对一个线性的 目标函数 (Objective Function) 进行优化（求其最大值或最小值）。

线性规划是解决现实世界中资源分配和决策问题的强大工具，其理论基础坚实，算法成熟，应用领域极其广泛。

线性规划问题的构成要素

一个典型的线性规划问题由以下三个核心部分组成：

  1. 决策变量 (Decision Variables)：这些是问题中需要求解的未知量，代表了决策者可以控制的数量。例如，生产多少单位的产品A，或者向某条运输路线分配多少货物。我们通常用 x1,x2,…,xn x_1, x_2, \ldots, x_n 来表示。
  1. 目标函数 (Objective Function)：这是一个关于决策变量的线性函数，是我们需要最大化或最小化的目标。例如，最大化总利润、最小化总成本。其一般形式为：
Z=c1x1+c2x2+⋯+cnxnZ = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n

其中，c1,c2,…,cn c_1, c_2, \ldots, c_n 是已知的常数，分别代表每个决策变量对目标值的贡献系数（如单位利润或单位成本）。

  1. 约束条件 (Constraints)：这些是决策变量必须满足的限制条件，通常由资源、技术、市场需求等因素决定。它们被表示为关于决策变量的一组线性等式或不等式。例如，可用的原材料总量有限，或生产时间不能超过规定时长。其一般形式为：
{a11x1+a12x2+⋯+a1nxn≤b1a21x1+a22x2+⋯+a2nxn≤b2⋮am1x1+am2x2+⋯+amnxn≤bm \begin{cases} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \le b_2 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n \le b_m \end{cases}

其中 aij a_{ij} 和 bi b_i 是已知的技术系数和资源限制。约束也可以是 ≥ \ge 或 = = 的形式。

此外，大多数线性规划问题还包含 非负性约束 (Non-negativity Constraints)，即要求所有决策变量都大于或等于零 (xj≥0 x_j \ge 0 )，因为在现实世界中生产数量、分配资源等通常不能为负。

线性规划的标准型

为了方便算法求解，通常将线性规划问题转化为标准形式。一个LP问题的 标准型 (Standard Form) 定义如下：

  • 目标： 最大化 (Maximization)
  • 约束： 所有约束都是等式 (Equalities)
  • 变量： 所有决策变量都非负
MaximizeZ=cTxSubject toAx=bx≥0\begin{array}{ll} \text{Maximize} & Z = c^T x \\ \text{Subject to} & Ax = b \\ & x \ge 0 \end{array}

其中：

  • x x 是包含决策变量 x1,…,xn x_1, \ldots, x_n 的列向量。
  • cT c^T 是包含目标函数系数 c1,…,cn c_1, \ldots, c_n 的行向量。
  • A A 是一个 m×n m \times n 的技术系数矩阵。
  • b b 是包含约束右侧常数 b1,…,bm b_1, \ldots, b_m 的列向量，且要求 b≥0 b \ge 0 。

任何一个线性规划问题都可以通过引入 松弛变量 (Slack Variables) 和 剩余变量 (Surplus Variables) 等技巧转化为标准型。

一个简单的例子：生产计划问题

假设一个家具厂生产桌子和椅子两种产品。

  • 每张桌子需要2小时的木工时间和1小时的油漆时间，利润为＄160。
  • 每把椅子需要1小时的木工时间和1小时的油漆时间，利润为＄100。
  • 工厂每周有100小时的木工时间和80小时的油漆时间可用。

工厂的目标是制定生产计划以实现利润最大化。

步骤 1: 定义决策变量

  • 设 x1 x_1 为每周生产桌子的数量。
  • 设 x2 x_2 为每周生产椅子的数量。

步骤 2: 建立目标函数 目标是最大化总利润 Z Z ：

MaximizeZ=160x1+100x2\text{Maximize} \quad Z = 160x_1 + 100x_2

步骤 3: 建立约束条件

  • 木工时间约束：2x1+1x2≤100 2x_1 + 1x_2 \le 100
  • 油漆时间约束：1x1+1x2≤80 1x_1 + 1x_2 \le 80
  • 非负性约束：x1≥0,x2≥0 x_1 \ge 0, \quad x_2 \ge 0

完整的线性规划模型即为：

MaximizeZ=160x1+100x2Subject to2x1+x2≤100x1+x2≤80x1≥0,x2≥0\begin{array}{ll} \text{Maximize} & Z = 160x_1 + 100x_2 \\ \text{Subject to} & 2x_1 + x_2 \le 100 \\ & x_1 + x_2 \le 80 \\ & x_1 \ge 0, x_2 \ge 0 \end{array}

图解法 (Graphical Method)

对于只有两个决策变量的问题，我们可以使用图解法来直观地理解和求解。

  1. 绘制可行域 (Feasible Region)：在二维坐标系中，将每个不等式约束视为一条直线，并确定该直线所界定的半平面。所有约束条件的半平面的交集构成一个多边形区域，这个区域被称为 可行域。可行域内的任何一点都代表一个满足所有约束条件的解。在数学上，这个区域是一个 凸集 (Convex Set)，更具体地是一个 凸多边形。
  1. 绘制目标函数线：对于目标函数 Z=160x1+100x2 Z = 160x_1 + 100x_2 ，我们可以将其改写为 x2=−160100x1+Z100 x_2 = -\frac{160}{100}x_1 + \frac{Z}{100} 。这是一族斜率为 −1.6 -1.6 的平行线。Z Z 的值越大，直线在 x2 x_2 轴上的截距越大，即直线离原点越远。
  1. 寻找最优解：我们将目标函数线在可行域内沿着使其增大的方向（对于最大化问题，即远离原点的方向）平行移动。当这条线即将离开可行域时，它所接触到的最后一个点（或边）就是最优解。

基本定理： 线性规划问题的最优解（如果存在）必然在可行域的某个 顶点 (Vertex) 上取得。如果目标函数线与可行域的一条边平行，则该边上的所有点都是最优解，此时存在无穷多个最优解。

对于上述例子，可行域的顶点为 (0, 0), (50, 0), (20, 60), (0, 80)。将这些顶点代入目标函数：

  • Z(0, 0) = 0
  • Z(50, 0) = 160(50) + 100(0) = 8000
  • Z(20, 60) = 160(20) + 100(60) = 3200 + 6000 = 9200
  • Z(0, 80) = 160(0) + 100(80) = 8000

最优解为 x1=20,x2=60 x_1=20, x_2=60 ，最大利润 Z=＄9200 Z = ＄9200 。这意味着工厂每周应生产20张桌子和60把椅子。

求解方法

对于超过两个变量的问题，图解法不再适用。主要的求解 算法 包括：

  • 单纯形法 (Simplex Method)：由 George Dantzig 于1947年提出，是解决线性规划问题最经典、最著名的算法。它是一种迭代算法，从可行域的一个顶点开始，沿着边移动到相邻的、能使目标函数值改善的另一个顶点，直到找不到可以进一步改善的顶点为止，此时就达到了最优解。
  • 内点法 (Interior-Point Methods)：自20世纪80年代（如 Karmarkar's algorithm）发展起来的一类算法。与单纯形法在可行域的“边界”上移动不同，内点法通过在可行域的“内部”寻找路径来逼近最优解。对于超大规模的线性规划问题，内点法通常比单纯形法更有效率。

对偶理论 (Duality Theory)

线性规划中一个极为深刻和有用的概念是 对偶 (Duality)。每一个线性规划问题（称为 原始问题 (Primal Problem)）都有一个与之相对应的 对偶问题 (Dual Problem)。

  • 如果原始问题是最大化问题，其对偶问题就是最小化问题。
  • 原始问题的每个约束对应对偶问题的一个变量。
  • 原始问题的每个变量对应对偶问题的一个约束。
  • 原始问题的目标函数系数向量是对偶问题的约束右侧向量，反之亦然。

强对偶定理 (Strong Duality Theorem) 指出，如果原始问题有最优解，那么其对偶问题也一定有最优解，并且它们的最优目标函数值相等。

对偶变量通常具有重要的经济解释，被称为 影子价格 (Shadow Prices) 或边际价值。影子价格表示当某个约束的资源限制量（即约束右侧的常数 bi b_i ）增加一个单位时，最优目标函数值的增量。这为 敏感性分析 (Sensitivity Analysis) 和资源价值评估提供了关键信息。

扩展与相关领域

线性规划是数学规划的基础，其思想和方法被扩展到更复杂的问题：