跳到主要内容

线性规划

一、直观理解：在多边形可行域的顶点上找最好的点​

线性规划（Linear Programming, LP）研究的是：决策变量连续取值，目标函数是线性的，约束也是线性的，在这样的可行域里寻找最优解。

可以把可行域想象成一块由平面切割出来的凸多面体（二维时就是凸多边形）。目标函数 cTxc^\mathsf{T}x 像一组平行的等高线；平移这组等高线，最后碰到的可行点就是最优解。几何上可以证明：若最优解存在，则至少有一个顶点（基本可行解）是最优的。单纯形法正是在顶点之间移动；内点法则从可行域内部走向边界最优。

例如工厂用原料生产甲、乙两种产品：利润线性、原料消耗线性、产量非负，这就是经典 LP。最优方案往往落在「原料恰好用尽」之类的约束交点上，而不是可行域内部——内部还可以沿利润上升方向继续改进。

线性规划是数学建模优化问题的首选起点：能写成 LP 就不要先上整数规划或智能优化。

二、适用场景与优缺点​

类型说明
适用场景生产计划、配料、运输、财务规划、网络流松弛、资源分配；目标与约束均可线性表示；变量可连续（吨、小时、资金）或允许分数解再解释。
核心优点凸问题，局部最优即全局最优；算法成熟（linprog）；对偶变量（影子价格）可解释资源边际价值；灵敏度分析方便；规模大时仍相对高效。
局限与缺点无法直接表达「必须整数」「若…则…」等逻辑（需整数规划）；强非线性关系不能硬线性化后不验证；数据误差会沿线性结构放大。

使用 LP 前通常需要确认：

  1. 目标是否真是线性（注意人均、比例、乘积项）；
  2. 约束是否线性，有无「至少选一个」等逻辑；
  3. 变量下界、上界是否完整；
  4. 单位是否统一，系数数量级是否悬殊；
  5. 最优解为分数时业务上是否可接受。

三、核心原理：标准形、对偶与最优性​

1. 一般形式​

常见写法（MATLAB linprog 与之一致，默认最小化）：

min⁡xcTxs.t.Aineqx≤bineqAeqx=beqℓ≤x≤u\begin{aligned} \min_{x}\quad & c^\mathsf{T}x \\ \text{s.t.}\quad & A_{\mathrm{ineq}}x \le b_{\mathrm{ineq}} \\ & A_{\mathrm{eq}}x = b_{\mathrm{eq}} \\ & \ell \le x \le u \end{aligned}

最大化问题化为 min⁡−cTx\min -c^\mathsf{T}x。≥\ge 约束两边乘 −1-1 变为 ≤\le。

2. 可行域与顶点​

可行域 X={x∣上述约束}X=\{x\mid \text{上述约束}\} 是凸集。若 XX 非空且目标在 XX 上有界，则存在最优解；无界则可沿某射线目标趋于 −∞-\infty（对最小化）。

3. 对偶问题与影子价格​

原问题（以不等式型为例）的对偶把「约束资源」变成对偶变量 y≥0y\ge 0。强对偶成立时，原最优值等于对偶最优值。最优对偶变量 yi∗y_i^* 的含义是：

第 ii 个资源右端项增加一个微小单位时，最优目标的改进率（影子价格）。

若某约束在最优解处松弛（有松弛量），其影子价格通常为 0——再增加该资源短期内无益。

4. 求解思路（概念层）​

  • 单纯形法：顶点跳转，基变量与非基变量交换；
  • 内点法：沿中心路径逼近最优面，大规模稀疏问题常用；
  • MATLAB linprog 会按问题规模自动选择算法。

建模者不必手写单纯形，但应能读懂：不可行、无界、最优、以及约束活跃与否。

四、关键决策：建模时容易决定成败的点​

1. 变量与目标方向​

明确每个 xjx_j 的业务含义与单位；确认是 min 还是 max。利润最大化却忘记改符号，是最常见的低级错误。

2. 约束是否写全、写紧​

漏掉非负约束、产能上界或原料衡算，会得到荒唐解。多余约束一般无妨，但错误约束会扭曲最优。

3. 大系数与尺度​

10810^{8} 与 10−610^{-6} 同框可能导致数值病态。可对变量或约束做缩放，使系数大致落在相近量级。

4. 何时必须离开 LP​

变量必须整数、存在固定成本（开/关）、分段线性但需逻辑选择、双线性项等，应升级到整数或非线性规划。

5. 用 LP 做检验​

即使最终是 MILP，也先求 LP 松弛：若松弛已不可行，整数模型必不可行；若松弛最优解碰巧全整数，则已得整数最优。

五、MATLAB 示例​

经典生产计划：生产桌子与椅子，利润分别为 5 与 3；木料、工时受限。

max⁡5x1+3x2s.t.6x1+3x2≤100（木料）3x1+6x2≤80（工时）x1,x2≥0\begin{aligned} \max\quad & 5x_1+3x_2 \\ \text{s.t.}\quad & 6x_1+3x_2\le 100 \quad \text{（木料）}\\ & 3x_1+6x_2\le 80 \quad \text{（工时）}\\ & x_1,x_2\ge 0 \end{aligned} 
% linprog 默认最小化，故目标取负
c = [-5; -3];

A = [
    6, 3;   % 木料
    3, 6    % 工时
];
b = [100; 80];

Aeq = [];
beq = [];
lb = [0; 0];
ub = [];   % 无显式上界

options = optimoptions("linprog", "Display", "iter");
[x, fval, exitflag, output, lambda] = linprog( ...
    c, A, b, Aeq, beq, lb, ub, options);

profit = -fval;  % 还原最大化利润

fprintf("exitflag = %d\n", exitflag);
fprintf("最优产量：桌子 = %.4f，椅子 = %.4f\n", x(1), x(2));
fprintf("最大利润 = %.4f\n", profit);

% 不等式约束的影子价格（对偶）
disp("木料、工时约束的 lambda.ineqlin：");
disp(lambda.ineqlin);

% 资源使用量与松弛
usage = A * x;
slack = b - usage;
disp("资源使用 / 松弛：");
disp([usage, slack]);

运输问题也可写成 LP（决策为路线流量 xijx_{ij}，供求平衡为等式约束）。小规模时直接列 AeqAeq 即可；大规模可考虑专门网络算法。

% 两供应点、两需求点的最小费用运输（示意）
% 变量顺序：x11, x12, x21, x22
cost = [2; 3; 4; 1];  % 单位运费
% 供应：x11+x12=20, x21+x22=15
% 需求：x11+x21=10, x12+x22=25
Aeq = [
    1, 1, 0, 0;
    0, 0, 1, 1;
    1, 0, 1, 0;
    0, 1, 0, 1
];
beq = [20; 15; 10; 25];
lb = zeros(4, 1);
[xShip, fShip, flagShip] = linprog(cost, [], [], Aeq, beq, lb, []);
fprintf("运输 exitflag=%d，最小费用=%.4f\n", flagShip, fShip);
disp(reshape(xShip, 2, 2)');  % 行=供应点，列=需求点

六、如何解释结果​

完整报告建议包含：

  1. 决策变量含义与最优取值（带单位）；
  2. 最优目标值（利润、成本、时长等业务语言）；
  3. exitflag：1 通常表示找到最优；负值表示不可行或无界等，需查文档；
  4. 活跃约束：松弛接近 0 的约束是瓶颈；
  5. 影子价格：哪些资源最值钱，扩大哪项投入最划算；
  6. 灵敏度（可选）：目标系数或右端在何范围内最优基不变；
  7. 若解为分数，说明业务上如何圆整或是否改整数规划。

对偶解释示例：若木料影子价格为 0.50.5 而工时为 00，则在当前最优附近，略微增加木料可提升利润，而加班工时暂时无益。

七、常见误区​

1. 最大化忘记取负​

linprog 只做最小化。目标符号反了，得到的是「最差」方向上的顶点。

2. 约束方向写反​

「至少供应 100」写成 ≤\le 会导致虚假可行或错误最优。每个约束应用业务语言复查。

3. 把比例约束误当成线性​

x1/(x1+x2)≥0.3x_1/(x_1+x_2)\ge 0.3 在分母可变时不是线性的；可改写为 x1≥0.3(x1+x2)x_1\ge 0.3(x_1+x_2)（在 x1+x2>0x_1+x_2>0 时）才能保持线性。

4. 不可行时盲目换算法​

先做约束诊断：放宽可疑约束、检查单位、供求是否平衡。算法换来换去解决不了模型写错。

5. 无界解当成功​

目标可任意优说明缺约束（如漏掉资源或需求）。必须补全模型，不能把 exitflag 对应无界的情况当结果。

6. 分数解直接当人数​

「生产 3.7 人」无意义时应建整数规划，而不是强行四舍五入却不检查可行性与最优性损失。

八、小结​

线性规划的核心思想可以概括为：

在线性等式/不等式刻画的凸可行域上，优化线性目标；最优解可在顶点取得，对偶变量给出资源的边际价值。

它是优化建模的默认首选：能 LP 则 LP。建模重点在变量、目标、约束的正确翻译，而不是求解器本身。得到数值后，务必用活跃约束、影子价格和业务常识解释「为什么是这个方案」，并在整数性、非线性或逻辑约束出现时，再升级到更合适的模型类。