线性规划（Linear Programming, LP）

线性规划（Linear Programming, LP）——这是运筹学中最基础且应用最广泛的优化方法之一。

什么是线性规划？

线性规划是在线性约束条件下，求解线性目标函数最大值或最小值的数学优化方法。

标准形式

minimizecTxsubject toAx≤bx≥0 \begin{aligned} \text{minimize} \quad & \mathbf{c}^T \mathbf{x} \\ \text{subject to} \quad & A\mathbf{x} \leq \mathbf{b} \\ & \mathbf{x} \geq \mathbf{0} \end{aligned}minimizesubject to​cTxAx≤bx≥0​

其中：

• x∈Rn\mathbf{x} \in \mathbb{R}^nx∈Rn：决策变量
• c∈Rn\mathbf{c} \in \mathbb{R}^nc∈Rn：目标函数系数
• A∈Rm×nA \in \mathbb{R}^{m \times n}A∈Rm×n：约束矩阵
• b∈Rm\mathbf{b} \in \mathbb{R}^mb∈Rm：约束右端项

核心算法

经典应用案例

1. 生产计划优化

某工厂生产A、B两种产品：

• A产品利润：40元/件，需2小时机器时间 + 1小时人工
• B产品利润：60元/件，需1小时机器时间 + 2小时人工
• 资源限制：机器100小时，人工80小时

模型：
max⁡40x1+60x2s.t.2x1+x2≤100x1+2x2≤80x1,x2≥0 \begin{aligned} \max \quad & 40x_1 + 60x_2 \\ \text{s.t.} \quad & 2x_1 + x_2 \leq 100 \\ & x_1 + 2x_2 \leq 80 \\ & x_1, x_2 \geq 0 \end{aligned}maxs.t.​40x1​+60x2​2x1​+x2​≤100x1​+2x2​≤80x1​,x2​≥0​

2. 运输问题（最小成本流）

将货物从多个仓库运到多个商店，最小化总运输成本。

3. 投资组合优化

在给定风险约束下最大化收益，或在目标收益下最小化风险。

几何解释

线性规划的可行域是凸多面体，最优解必定出现在**顶点（极点）**上。

可行域（阴影多边形） /\ / \ / \ ← 目标函数等值线 / ★ \ （斜向虚线） / 最优解 \ /__________\ 顶点1 顶点2 顶点3

Python 求解示例

importnumpyasnpfromscipy.optimizeimportlinprog# 目标函数系数（注意：linprog默认求最小值，所以取负）c=[-40,-60]# 不等式约束：Ax <= bA=[[2,1],# 机器时间约束[1,2]]# 人工约束b=[100,80]# 变量非负约束bounds=[(0,None),(0,None)]# 求解result=linprog(c,A_ub=A,b_ub=b,bounds=bounds,method='highs')print(f"最优解: x1={result.x[0]:.2f}, x2={result.x[1]:.2f}")print(f"最大利润:{-result.fun:.2f}元")

输出：

最优解: x1=40.00, x2=20.00 最大利润: 2800.00元

对偶理论

每个线性规划（原问题）都有对应的对偶问题：

强对偶定理：若原问题有最优解，则对偶问题也有最优解，且最优值相等。

扩展变体