线性规划 · 深度手册

分类：优化类 ｜难度：★☆☆ 入门｜编号：lp

一、这是什么（一句话用途）

目标与约束都是线性的资源分配 / 排产

二、核心思想

线性规划（LP）是优化理论的起点：目标函数和所有约束都是线性的。几何上，可行域是一个凸多面体，而线性目标函数的极值点必定出现在多面体的某个顶点上——这正是单纯形法的依据。LP 建模能力极强（生产排程、运输、投资组合、配料），且有成熟求解器（单纯形、内点法）保证在多项式或准多项式时间内给出全局最优。理解 LP 是理解整个优化体系的钥匙。

三、数学原理与推导

标准型：

$\max\ c^T x\quad \text{s.t.}\ Ax\le b,\ x\ge0$

引入松弛变量 $s\ge0$ 使 $Ax+s=b$ 。单纯形法从一个顶点基本可行解出发：基变量 $x_B=B^{-1}b$ （ $B$ 为基矩阵），非基变量为 0。检验数（ reduced cost）

$\bar{c}_j=c_j-c_B^T B^{-1}A_j$

若所有 $\bar{c}_j\le0$ （最大化）则当前基最优；否则选正检验数最大的非基变量入基，按比值法则 $\theta=\min_i (B^{-1}b)_i/(B^{-1}A_j)_i$ 确定出基变量，转轴（pivot）得新顶点，迭代至最优。对偶理论给出影子价格 $\lambda=c_B^T B^{-1}$ ，表示资源边际价值。

四、建模 / 求解步骤

设决策变量
写目标函数
列线性约束(≤ /= / ≥)
标准化(加松弛 / 人工变量)
单纯形 / 求解器求最优

五、关键公式速查

max/min cᵀx，s.t. Ax≤b, x≥0

六、典型示例

两种产品用有限工时 / 原料 → 最大化利润。

完整算例（数字演示，照着算一遍）

场景：max z=3x+5y s.t. x+2y≤8, 3x+y≤9, x,y≥0。

顶点枚举：(0,0)=0, (0,4)=20, (3,0)=9, (2,3)=21。

结论：最优 (x,y)=(2,3)，z*=21（单纯形法同解）。

七、Python 实现示例

import os, numpy as np
import pandas as pd
HERE = os.path.dirname(os.path.abspath(__file__))
df = pd.read_csv(os.path.join(HERE,"..","datasets","lp.csv"))
# 目标：max profit；约束：资源消耗 <= 资源上限
profit = df["profit"].to_numpy(dtype=float)
use = df[["r1","r2"]].to_numpy(dtype=float)
from scipy.optimize import linprog
# 转最小化
res = linprog(-profit, A_ub=use.T, b_ub=np.array([100,80]),
              bounds=[(0,None)]*len(profit), method="highs")
print("最优产量:", np.round(res.x,2))
print("最大利润=%.1f"%(-res.fun))

配套文件：py_lp.py（需 numpy / pandas；与下方数据集配套练习）

八、MATLAB 实现示例

%% 线性规划示例（MATLAB/Octave，需 Optimization Toolbox）
df = readtable('..\datasets\lp.csv');
profit = table2array(df(:,4)); use = table2array(df(:,2:3));
f = -profit'; A = use'; b = [100;80];
lb = zeros(size(f));
x = linprog(f, A, b, [], [], lb);
fprintf('最大利润=%.1f\n', -f'*x);

配套文件：m_lp.m（基础 MATLAB / Octave 即可运行）

九、练手数据集（可下载）

3 种产品的资源消耗(r1,r2)与利润，资源上限各 100/80。用于线性规划求最大利润产量。

字段：product, r1, r2, profit
行数：3 行
下载：lp.csv

十、常见误区与避坑清单

变量非负约束别忘了
等式约束要处理
无界 / 无解要识别

十一、结果怎么解读

看对偶价格(影子价格)指导资源投入。

十二、常与谁搭配

整数约束见 ip。

十三、论文写作技巧（怎么把它写进论文）

把 线性规划 写进论文，核心不是堆公式，而是讲清「为什么用它、结果怎么呈现、如何对比」三件事。

1. 动机怎么写（为什么用它而不是别的）

先把问题「数学化」：决策变量、目标函数、约束条件——这一步写清楚比算法本身更重要。再说明为何用线性规划求解：连续可导用梯度 / 解析法，组合 / 非凸 / 黑箱用启发式（GA / PSO / SA）。

2. 结果怎么写（图表与指标）

放「收敛曲线（迭代 vs 目标值）」+「最优解参数表」+「约束是否满足」三件套。若是多目标，放 Pareto 前沿散点图。

3. 可直接套用的写作话术

中文模板：针对<问题>，本文采用 线性规划 进行目标与约束都是线性的资源分配 / 排产。该方法能够自动刻画<优势>，在处理<场景>时相较<对比方法>更具<特点>。
英文模板：To address , we adopt 线性规划 to 目标与约束都是线性的资源分配 / 排产. Benefiting from its ability to , it outperforms on .

4. 同类易踩的写作坑

务必说明约束是否全部满足、是否陷入局部最优（可多次随机初始化对比）；别把无约束结果当约束最优报。

5. 典型论文段落范例（可直接参考 / 改写）

下面是一段可直接套用的论文表述，已按本算法定制，填空处（…）替换成你的真实数值即可。

将配送中心选址建模为带容量约束的总成本最小化问题，本文采用线性规划求解，得到 5 个选址及其服务分配方案，目标值较贪婪启发式降低 12.4%，且全部约束满足。

We formulate the distribution center location as a total-cost minimization problem with capacity constraints and solve it via 线性规划, yielding 5 sites and their service assignments. The objective is 12.4% lower than a greedy heuristic while satisfying all constraints.

十四、相关手册（延伸阅读）

整数规划 · 优化类

十五、本手册导航

上一篇：移动平均 · 预测类
下一篇：图论最短路 · 优化类
返回：算法深度手册库｜资料站首页

本手册由「算法深度手册生成器」自动产出，配套提供 Python / MATLAB 双版本示例与可下载练手数据集。