线性规划的对偶理论及其应用示例
字数 3336 2025-10-27 12:20:21

线性规划的对偶理论及其应用示例

我将为您讲解线性规划中的核心理论——对偶理论，并通过一个具体的应用示例来说明其原理和计算过程。

题目描述

考虑一个简单的线性规划问题（我们称之为原始问题，Primal Problem）：
最大化目标函数：\(Z = 5x_1 + 4x_2\)
需要满足的约束条件：

  1. \(x_1 + 2x_2 \leq 6\)
  2. \(3x_1 + 2x_2 \leq 12\)
  3. \(x_1, x_2 \geq 0\)

我们将为这个原始问题构建其对偶问题（Dual Problem），并解释两者之间的关系。

对偶理论的基本概念

对偶理论是线性规划的核心内容之一。每一个线性规划问题（称为原始问题）都有一个与之对应的另一个线性规划问题（称为对偶问题）。它们之间存在着深刻的数学联系：

  • 如果原始问题是求最大值，则对偶问题就是求最小值，反之亦然。
  • 原始问题的约束条件数量决定了对偶问题中变量的个数。
  • 原始问题的目标函数系数会成为对偶问题约束条件的右端项。
  • 原始问题约束条件的右端项会成为对偶问题的目标函数系数。

步骤一：构建对偶问题

根据对偶理论的转换规则，我们可以从原始问题推导出对偶问题。

  1. 确定对偶变量：原始问题有两个约束条件（不算非负约束），因此对偶问题将有两个变量，我们记为 \(y_1\) 和 \(y_2\)，分别对应第一个和第二个约束条件。
  2. 确定对偶问题的目标：原始问题是最大化问题，因此对偶问题是最小化问题。原始问题约束的右端项是6和12，所以对偶问题的目标函数是 \(W = 6y_1 + 12y_2\)（我们的目标是最小化W）。
  3. 确定对偶问题的约束：
    • 原始问题有两个变量 \(x_1\) 和 \(x_2\)，所以对偶问题有两个约束条件。
    • 每个约束的系数由原始问题中对应变量的系数列向量决定。
      • 对于 \(x_1\)，其系数列向量是 \([1, 3]^T\)。因此，第一个对偶约束为：\(1 \cdot y_1 + 3 \cdot y_2\)。这个约束的不等号方向和数值需要根据原始问题来确定。
      • 原始问题是最大化，并且原始变量 \(x_1\) 有非负约束（\(x_1 \geq 0\)）。根据对偶规则，这种情况下，对偶约束的不等号方向应为 \(\geq\)，并且右边是 \(x_1\) 在原始目标函数中的系数，即5。
      • 所以，第一个对偶约束是：\(y_1 + 3y_2 \geq 5\)。
    • 同理，对于 \(x_2\)（系数列向量为 \([2, 2]^T\)，非负），第二个对偶约束是：\(2y_1 + 2y_2 \geq 4\)。
  4. 确定对偶变量的符号约束：原始问题的约束都是“≤”类型，根据对偶规则，对应的对偶变量 \(y_1\) 和 \(y_2\) 都应是非负的，即 \(y_1, y_2 \geq 0\)。

综合以上，我们得到对偶问题为：
最小化目标函数：\(W = 6y_1 + 12y_2\)
需要满足的约束条件：

  1. \(y_1 + 3y_2 \geq 5\)
  2. \(2y_1 + 2y_2 \geq 4\)
  3. \(y_1, y_2 \geq 0\)

步骤二：求解原始问题（使用图解法）

为了验证对偶理论，我们先求解原始问题。

  1. 画出可行域：由约束条件 \(x_1 + 2x_2 \leq 6\)，\(3x_1 + 2x_2 \leq 12\) 和 \(x_1, x_2 \geq 0\) 围成的区域。
  2. 找出顶点：可行域是一个四边形，顶点分别为：
    • A: (0, 0)
    • B: (4, 0) （由 \(3x_1+2x_2=12\) 和 \(x_2=0\) 解得）
    • C: (3, 1.5) （由 \(x_1+2x_2=6\) 和 \(3x_1+2x_2=12\) 联立解得）
    • D: (0, 3) （由 \(x_1+2x_2=6\) 和 \(x_1=0\) 解得）
  3. 计算各顶点的目标函数值：
    • Z(A) = 50 + 40 = 0
    • Z(B) = 54 + 40 = 20
    • Z(C) = 53 + 41.5 = 15 + 6 = 21
    • Z(D) = 50 + 43 = 12
  4. 结论：原始问题的最优解在点C(3, 1.5)，最大目标函数值 \(Z^* = 21\)。

步骤三：求解对偶问题（使用图解法）并验证对偶理论

现在我们来解对偶问题。

  1. 画出可行域：由约束条件 \(y_1 + 3y_2 \geq 5\)，\(2y_1 + 2y_2 \geq 4\) 和 \(y_1, y_2 \geq 0\) 围成的区域。这是一个无界的区域。
  2. 找出顶点：这个无界区域有两个明显的顶点（由约束线的交点形成）：
    • P1: (5, 0) （由 \(y_1+3y_2=5\) 和 \(y_2=0\) 解得）
    • P2: (1, 1) （由 \(y_1+3y_2=5\) 和 \(2y_1+2y_2=4\) 联立解得。将第二式除以2得 \(y_1+y_2=2\)，与第一式相减得 \(2y_2=3\) => \(y_2=1.5\)？这里计算有误，让我们重新计算：方程组为 y1 + 3y2 = 5 和 y1 + y2 = 2。两式相减：(y1+3y2) - (y1+y2) = 5-2 => 2y2 = 3 => y2=1.5。代入 y1+y2=2 得 y1=0.5。所以P2应该是 (0.5, 1.5)）
  3. 计算目标函数值：
    • W(P1) = 65 + 120 = 30
    • W(P2) = 60.5 + 121.5 = 3 + 18 = 21
  4. 由于是最小化问题，并且可行域无界，我们需要检查目标函数值是否会趋向于无穷小。沿着某个方向（例如y2增大），W值会增大。因此，最小值出现在顶点P2。
  5. 结论：对偶问题的最优解在点(0.5, 1.5)，最小目标函数值 \(W^* = 21\)。

步骤四：分析对偶理论的关键结论

通过对比两个问题的解，我们可以验证对偶理论的核心结论：

  1. 弱对偶定理：对于任何原始问题的可行解和对偶问题的可行解，原始问题的目标函数值（Z）总是小于或等于对偶问题的目标函数值（W）。在我们的例子中，任何可行的Z都≤21，任何可行的W都≥21。
  2. 强对偶定理：如果原始问题有最优解，那么对偶问题也有最优解，并且两者的最优目标函数值相等。这正是我们计算的结果：\(Z^* = W^* = 21\)。
  3. 互补松弛定理：这个定理描述了最优解时原始和对偶约束的“松紧”关系。在最优解处：
    • 如果一个原始约束是严格不等式（“松”的），那么对应的对偶变量必须为0。
    • 如果一个对偶约束是严格不等式（“松”的），那么对应的原始变量必须为0。
    • 在我们的例子中：
      • 在原始最优解(3, 1.5)处，两个约束都是“紧”的（等号成立：3+3=6，9+3=12），所以对应的对偶变量 \(y_1\) 和 \(y_2\) 可以大于0（事实上它们分别是0.5和1.5）。
      • 在对偶最优解(0.5, 1.5)处，两个约束也都是“紧”的（等号成立：0.5+4.5=5，1+3=4），所以对应的原始变量 \(x_1\) 和 \(x_2\) 可以大于0（事实上它们分别是3和1.5）。

总结

对偶理论不仅是一个优美的数学理论，更具有重要的实际应用价值。例如，对偶变量可以被解释为资源的“影子价格”，即某种资源每增加一个单位所能带来的目标函数（如利润）的增量。在本例中，\(y_1^*=0.5\) 表示第一个约束对应的资源每增加1单位，最大利润Z可增加0.5单位；\(y_2^*=1.5\) 表示第二个约束对应的资源更为宝贵。这为管理者进行资源定价和分配决策提供了科学的依据。

线性规划的对偶理论及其应用示例 我将为您讲解线性规划中的核心理论——对偶理论，并通过一个具体的应用示例来说明其原理和计算过程。 题目描述 考虑一个简单的线性规划问题（我们称之为原始问题，Primal Problem）： 最大化目标函数：\( Z = 5x_ 1 + 4x_ 2 \) 需要满足的约束条件： \( x_ 1 + 2x_ 2 \leq 6 \) \( 3x_ 1 + 2x_ 2 \leq 12 \) \( x_ 1, x_ 2 \geq 0 \) 我们将为这个原始问题构建其对偶问题（Dual Problem），并解释两者之间的关系。 对偶理论的基本概念 对偶理论是线性规划的核心内容之一。每一个线性规划问题（称为原始问题）都有一个与之对应的另一个线性规划问题（称为对偶问题）。它们之间存在着深刻的数学联系： 如果原始问题是求最大值，则对偶问题就是求最小值，反之亦然。 原始问题的约束条件数量决定了对偶问题中变量的个数。 原始问题的目标函数系数会成为对偶问题约束条件的右端项。 原始问题约束条件的右端项会成为对偶问题的目标函数系数。 步骤一：构建对偶问题 根据对偶理论的转换规则，我们可以从原始问题推导出对偶问题。 确定对偶变量 ：原始问题有两个约束条件（不算非负约束），因此对偶问题将有两个变量，我们记为 \( y_ 1 \) 和 \( y_ 2 \)，分别对应第一个和第二个约束条件。 确定对偶问题的目标 ：原始问题是最大化问题，因此对偶问题是最小化问题。原始问题约束的右端项是6和12，所以对偶问题的目标函数是 \( W = 6y_ 1 + 12y_ 2 \)（我们的目标是最小化W）。 确定对偶问题的约束 ： 原始问题有两个变量 \( x_ 1 \) 和 \( x_ 2 \)，所以对偶问题有两个约束条件。 每个约束的系数由原始问题中对应变量的系数列向量决定。 对于 \( x_ 1 \)，其系数列向量是 \( [ 1, 3]^T \)。因此，第一个对偶约束为：\( 1 \cdot y_ 1 + 3 \cdot y_ 2 \)。这个约束的不等号方向和数值需要根据原始问题来确定。 原始问题是最大化，并且原始变量 \( x_ 1 \) 有非负约束（\( x_ 1 \geq 0 \)）。根据对偶规则，这种情况下，对偶约束的不等号方向应为 \( \geq \)，并且右边是 \( x_ 1 \) 在原始目标函数中的系数，即5。 所以，第一个对偶约束是：\( y_ 1 + 3y_ 2 \geq 5 \)。 同理，对于 \( x_ 2 \)（系数列向量为 \( [ 2, 2]^T \)，非负），第二个对偶约束是：\( 2y_ 1 + 2y_ 2 \geq 4 \)。 确定对偶变量的符号约束 ：原始问题的约束都是“≤”类型，根据对偶规则，对应的对偶变量 \( y_ 1 \) 和 \( y_ 2 \) 都应是非负的，即 \( y_ 1, y_ 2 \geq 0 \)。 综合以上，我们得到对偶问题为： 最小化目标函数：\( W = 6y_ 1 + 12y_ 2 \) 需要满足的约束条件： \( y_ 1 + 3y_ 2 \geq 5 \) \( 2y_ 1 + 2y_ 2 \geq 4 \) \( y_ 1, y_ 2 \geq 0 \) 步骤二：求解原始问题（使用图解法） 为了验证对偶理论，我们先求解原始问题。 画出可行域：由约束条件 \( x_ 1 + 2x_ 2 \leq 6 \)，\( 3x_ 1 + 2x_ 2 \leq 12 \) 和 \( x_ 1, x_ 2 \geq 0 \) 围成的区域。 找出顶点：可行域是一个四边形，顶点分别为： A: (0, 0) B: (4, 0) （由 \( 3x_ 1+2x_ 2=12 \) 和 \( x_ 2=0 \) 解得） C: (3, 1.5) （由 \( x_ 1+2x_ 2=6 \) 和 \( 3x_ 1+2x_ 2=12 \) 联立解得） D: (0, 3) （由 \( x_ 1+2x_ 2=6 \) 和 \( x_ 1=0 \) 解得） 计算各顶点的目标函数值： Z(A) = 5 0 + 4 0 = 0 Z(B) = 5 4 + 4 0 = 20 Z(C) = 5 3 + 4 1.5 = 15 + 6 = 21 Z(D) = 5 0 + 4 3 = 12 结论 ：原始问题的最优解在点C(3, 1.5)，最大目标函数值 \( Z^* = 21 \)。 步骤三：求解对偶问题（使用图解法）并验证对偶理论 现在我们来解对偶问题。 画出可行域：由约束条件 \( y_ 1 + 3y_ 2 \geq 5 \)，\( 2y_ 1 + 2y_ 2 \geq 4 \) 和 \( y_ 1, y_ 2 \geq 0 \) 围成的区域。这是一个无界的区域。 找出顶点：这个无界区域有两个明显的顶点（由约束线的交点形成）： P1: (5, 0) （由 \( y_ 1+3y_ 2=5 \) 和 \( y_ 2=0 \) 解得） P2: (1, 1) （由 \( y_ 1+3y_ 2=5 \) 和 \( 2y_ 1+2y_ 2=4 \) 联立解得。将第二式除以2得 \( y_ 1+y_ 2=2 \)，与第一式相减得 \( 2y_ 2=3 \) => \( y_ 2=1.5 \)？这里计算有误，让我们重新计算：方程组为 y1 + 3y2 = 5 和 y1 + y2 = 2 。两式相减： (y1+3y2) - (y1+y2) = 5-2 => 2y2 = 3 => y2=1.5 。代入 y1+y2=2 得 y1=0.5 。所以P2应该是 (0.5, 1.5)） 计算目标函数值： W(P1) = 6 5 + 12 0 = 30 W(P2) = 6 0.5 + 12 1.5 = 3 + 18 = 21 由于是最小化问题，并且可行域无界，我们需要检查目标函数值是否会趋向于无穷小。沿着某个方向（例如y2增大），W值会增大。因此，最小值出现在顶点P2。 结论 ：对偶问题的最优解在点(0.5, 1.5)，最小目标函数值 \( W^* = 21 \)。 步骤四：分析对偶理论的关键结论 通过对比两个问题的解，我们可以验证对偶理论的核心结论： 弱对偶定理 ：对于任何原始问题的可行解和对偶问题的可行解，原始问题的目标函数值（Z）总是小于或等于对偶问题的目标函数值（W）。在我们的例子中，任何可行的Z都≤21，任何可行的W都≥21。 强对偶定理 ：如果原始问题有最优解，那么对偶问题也有最优解，并且两者的最优目标函数值相等。这正是我们计算的结果：\( Z^* = W^* = 21 \)。 互补松弛定理 ：这个定理描述了最优解时原始和对偶约束的“松紧”关系。在最优解处： 如果一个原始约束是严格不等式（“松”的），那么对应的对偶变量必须为0。 如果一个对偶约束是严格不等式（“松”的），那么对应的原始变量必须为0。 在我们的例子中： 在原始最优解(3, 1.5)处，两个约束都是“紧”的（等号成立：3+3=6，9+3=12），所以对应的对偶变量 \( y_ 1 \) 和 \( y_ 2 \) 可以大于0（事实上它们分别是0.5和1.5）。 在对偶最优解(0.5, 1.5)处，两个约束也都是“紧”的（等号成立：0.5+4.5=5，1+3=4），所以对应的原始变量 \( x_ 1 \) 和 \( x_ 2 \) 可以大于0（事实上它们分别是3和1.5）。 总结 对偶理论不仅是一个优美的数学理论，更具有重要的实际应用价值。例如，对偶变量可以被解释为资源的“影子价格”，即某种资源每增加一个单位所能带来的目标函数（如利润）的增量。在本例中，\( y_ 1^ =0.5 \) 表示第一个约束对应的资源每增加1单位，最大利润Z可增加0.5单位；\( y_ 2^ =1.5 \) 表示第二个约束对应的资源更为宝贵。这为管理者进行资源定价和分配决策提供了科学的依据。