Math——线性规划的直观理解

本文是对线性规划的直观理解，不严谨，后续有新的问题/理解持续更新

原始问题

  • 问题描述：
    • 假设你是一个木匠有200单位的木头和90单位的时间
    • 木匠可以制作桌子或者椅子
      • 桌子成本为5单位木头+2单位时间，售价10元
      • 椅子成本为2单位木头+1单位时间，售价3元
  • 目标：在已有资源情况下，最大化收入，应该生产多少桌子和椅子？
  • 问题形式化描述:
    • 假设应该生产\(x_1\)把桌子和\(x_1\)把椅子
      $$
      \begin{align}
      \max \ \ 10x_1 &+ 3x_2 \\
      5x_1 + 2x_2 &<= 200 \\
      3x_1 + \ \ x_2 &<= 90 \\
      x_1,x_2 &>= 0 \\
      \end{align}
      $$
  • 作图法可求得最优解为\(x_1^* = 30, x_2^*=0\)，此时最大收益为300
    • 在二维坐标轴上先画出可行域，然后按照目标直线斜率找到最优点

对偶问题

  • 对偶问题描述：
    • 上述原始问题可以换一个视角看
    • 假设现在你是一个原材料收购商（想要以最低价格收购木匠的原材料）
    • 目标：对单位木头和单位时间进行出价，以最低的价格买完木匠的资源（假设木匠愿意卖出的前提是收购上出价的最小值不小于木匠原始问题中收益的最大值）
      • 实际上最好是刚好等于木匠原始问题的最大收益
  • 对偶问题形式化描述
    $$
    \begin{align}
    \min \ \ 200p_1 &+ 90p_2 \quad – 总付款 \\
    5p_1 + 3p_2 &>= 10 \quad – 一张桌子的资源售价不低于一张桌子的收益 \\
    2p_1 + \ \ p_2 &>= 3 \quad – 一张椅子的资源售价不低于一张椅子的收益 \\
    p_1,p_2 &>= 0 \quad – 售价不为负数 \\
    \end{align}
    $$
  • 其中\(p_1, p_2\)分别称为单位木头和单位时间的影子价格
  • 作图法可求得最优解为\(p_1^* = 0, p_2^* = 3.3\)，此时最小支付金额为300

互补松弛定理的理解

从原始问题的约束视角出发

等价于从对偶问题的解出发

  • 对偶问题中，最优解是\(p_1^* = 0, p_2^* = 3.3\)
    • \(p_1^* = 0\)意味着我们的木材过量了，其实不需要这么多木材，原始问题中，最优解对应的木材约束是松的（\(5x_1^* + 2x_2^*=150 < 200\)）
    • \(p_2^* = 3.3\)说明时间资源非常紧俏，原始问题中，最优解对应的时间约束是紧的（\(3x_1^* + \ \ x_2^* = 90\)）
  • 对应互补松弛的含义：
    • 如果在最优条件下一个约束不等式是松的（木材），那么这个约束对应的影子价格为0。
    • 反过来说，如果某个约束对应的影子价格严格大于0，那么这个约束不等式一定是紧的。
    • 总的来说，原始问题的约束和对偶问题变量(影子价格)总有一个要为0

从对偶问题的约束视角出发

等价于从原始问题的解出发

  • 原始问题中，最优解是\(x_1^* = 30, x_2^*=0\)
    • \(x_1^* = 30\)意味着桌子非常合算，应该多生产桌子，对偶问题中，桌子约束是紧的（\(5p_1^* + 3p_2^* = 10\)）
    • \(x_2^*=0\)以为这椅子不合算，不应该生产椅子，对偶问题中，椅子的约束是松的（\(2p_1^* + \ \ p_2^* = 3.3 > 3\)）
  • 补充互补松弛的含义：
    • 如果在对偶最优条件下一个约束不等式是松的（椅子），那么这个约束对应的原始问题变量最优解（\(x_2^*\)）为0。
    • 反过来说，如果某个原始问题变量（桌子）对应的解（\(x_1^*\)）严格大于0，那么对偶问题中这个约束不等式一定是紧的。
    • 总的来说，对偶问题的约束和对应原始问题变量总有一个要为0

互补松弛定理的公式化

$$
(5p_1^* + 3p_2^* - 10)x_1^* = 0 \\
(2p_1^* + p_2^* - 3)x_2^* = 0 \\
(5x_1^* + 2x_2^* - 200)p_1^* = 0 \\
(3x_1^* + x_2^* - 90)p_2^* = 0 \\
$$

其他相关补充

持续更新

线性规划相关论文推导