线性规划

线性规划是一个具有线性目标和仿射不等式约束的优化问题。一个常见的标准形式如下：

\[\begin{split}\begin{array}{ll} \mbox{最小化} & c^Tx \\ \mbox{满足} & Ax \leq b. \end{array}\end{split}\]

这里 \(A \in \mathcal{R}^{m \times n}\), \(b \in \mathcal{R}^m\), 和 \(c \in \mathcal{R}^n\) 是问题数据， \(x \in \mathcal{R}^{n}\) 是优化变量。不等式约束 \(Ax \leq b\) 是逐元素比较。

例如，我们可能有 \(n\) 种不同的产品，每个产品由 \(m\) 个组件构成。 每个条目 \(A_{ij}\) 是构建一个单位产品 \(j\) 所需要的组件 \(i\) 的数量。 每个条目 \(b_i\) 是组件 \(i\) 的总量。每个单位产品 \(j\) 会带来 \(c_j\) 的损失（\(c_j < 0\) 表示利润）。 我们的目标是选择每个产品 \(j\) 的数量，即 \(x_j\)，以便在不超过任何组件预算的情况下最小化损失。

除了解 \(x^\star\)，我们还可以获得对偶解 \(\lambda^\star\)。 正条目 \(\lambda^\star_i\) 表示约束 \(a_i^Tx \leq b_i\) 对于 \(x^\star\) 成立，并且暗示着更改 \(b_i\) 会改变最优值。

示例

在下面的代码中，我们使用 CVXPY 解一个线性规划问题。

# 导入包。
import cvxpy as cp
import numpy as np

# 生成一个随机的非平凡线性规划问题。
m = 15
n = 10
np.random.seed(1)
s0 = np.random.randn(m)
lamb0 = np.maximum(-s0, 0)
s0 = np.maximum(s0, 0)
x0 = np.random.randn(n)
A = np.random.randn(m, n)
b = A @ x0 + s0
c = -A.T @ lamb0

# 定义并求解CVXPY问题。
x = cp.Variable(n)
prob = cp.Problem(cp.Minimize(c.T@x),
                 [A @ x <= b])
prob.solve()

# 打印结果。
print("\n最优值为", prob.value)
print("一个解 x 是")
print(x.value)
print("一个对偶解是")
print(prob.constraints[0].dual_value)

最优值为 -15.220912604467838
一个解 x 是
[-1.10131657 -0.16370661 -0.89711643  0.03228613  0.60662428 -1.12655967
  1.12985839  0.88200333  0.49089264  0.89851057]
一个对偶解是
[0.         0.61175641 0.52817175 1.07296862 0.         2.3015387
 0.         0.7612069  0.         0.24937038 0.         2.06014071
 0.3224172  0.38405435 0.        ]