【数模学习笔记】线性规划（LP）的原理和过程详解

前言和简述

这个模型是用来解决什么问题的？

在一系列线性约束下，寻找能使线性目标函数达到最大值或最小值的决策方案（在有限的资源下，如何做出最优决策以达成特定目标）。适合使用在运筹学、管理科学、经济学等领域。

为什么需要学习这个模型？它在数学建模中的地位或常用性如何？

1. 应用广泛

   举例来说：

   • 生产计划：工厂如何在有限的设备、人力和原材料下，安排生产不同产品的数量，以实现利润最大化？
   • 资源分配：大师兄视频中的中张麻子的问题（第2、3页），如何在有限的人手和子弹下，分配攻碉楼和追替身的人数，以使百姓的士气值最大？
   • 投资组合：大师兄视频中中的投资问题（第9-12页），如何在总资金的限制下，投资不同的资产，以在控制风险的同时，使得净收益最大化？
   • 物流运输：如何安排货物从多个产地运往多个销地，才能使总运输成本最低？
   • 人员排班：如何为医院、航空公司或呼叫中心安排员工班次，以满足不同时段的需求，同时使人力成本最低？

2. 理论成熟，求解方便 LP有非常成熟的理论基础和高效的求解算法。现代计算软件（如大师兄视频中提到的MATLAB的linprog函数）可以快速精确求解，即便规模很大。只要能把问题翻译成LP模型，求解就非常直接了，结果也很可靠。

在数学建模中的地位和常用性

1. 非常基础。入门必学、人人必会。

2. 常用性极高 LP及其衍生模型是数学建模竞赛中出现频率最高的模型之一。

• 直接应用：很多早期的或相对简单的赛题，它的核心就是一个LP问题。
• 作为子问题：在更复杂的问题中，线性规划常常作为一个模块或子问题出现。例如，一个复杂的系统仿真模型可能需要用线性规划来决定每一步的最优策略。
• 作为“基准模型”：有时可以先建立一个简化的线性模型。好处：
  • 快速得到一个大致可行的解。
  • 为更复杂的模型提供一个性能比较的基准。
  • 帮助理解问题的基本结构。

3. 组合模型

   模型组合	协同作用	典型应用场景
   预测模型 + LP	先预测未来，后优化决策	生产计划、库存管理、需求响应
   评价模型 + LP	先量化多维目标，后优化资源分配	项目选择、供应商管理、风险投资
   仿真模型 + LP	规划提供最优策略，仿真检验其稳健性	投资组合风险分析、服务系统设计
   聚类/分类 + LP	先对用户/对象分群，后进行差异化优化	精准营销、客户关系管理

原理

核心思想：可行域上的顶点寻优

LP模型在几何上很好理解。所有的约束条件围成一个区域（在多维空间中），然后这个区域内的所有点都满足所有约束，就被称为可行域。由于所有约束都是线性的，所以这个可行域是一个凸多面体。

目标函数，同样是线性的，可以被看作是空间中一组平行的线或平面。我们的目标是找到可行域中的一个点，使得目标函数线（面）沿着其法线方向移动到最远的位置（最大化）或最近的位置（最小化），同时该线（面）仍然与可行域有交点。

定理指出：如果线性规划问题存在最优解，那么这个最优解一定可以在可行域的某个顶点上找到。 如果存在多个最优解，那么它们至少会包含两个顶点，且连接这些顶点的整条边（或面）上的所有点都是最优解。

它本质上是从一个顶点移动到另一个更好的相邻顶点，直到找不到可以继续改进的顶点，然后停下，此时就找到了最优解。在论文中提及这个几何解释，能体现对模型原理的理解。

---

线性规划的三要素

任何一个LP问题都由三个核心部分构成。

以下的示例我都引用大师兄视频中的张麻子来当例子。

1. 决策变量 需要求解的未知数，代表了决策者可以控制的量。最终的决策方案就由这些变量的值构成。

• 示例
  • 决策变量是：
    • $x_1$: 派去攻打碉楼的人数。
    • $x_2$: 派去追击替身的人数。

2. 目标函数 一个关于决策变量的线性表达式，代表了决策者希望最大化或最小化的目标。它是评价决策方案优劣的唯一标准。

• 示例
  • 目标是使百姓的士气值最大化。
  • $\max \ Z = 40x_1 + 30x_2$

3. 约束条件 一组关于决策变量的线性等式或不等式，代表了各种限制。所有约束条件共同定义了可行解的范围。

• 示例
  • 总共只有6人，即 $x_1 + x_2 \le 6$。
  • 总共1200发子弹，即 $240x_1 + 120x_2 \le 1200$。
  • 两项任务都必须有人执行，即 $x_1 \ge 1, x_2 \ge 1$。

模型的标准数学形式

方便计算机求解，也是符合学术规范，LP问题一般写成下面这样的形式。

一个标准的线性规划模型可以表示如下：

$$ \begin{array}{rll} \text{最小化} & Z = \mathbf{c}^T \mathbf{x} & \\ \text{服从于} & \mathbf{A} \mathbf{x} \le \mathbf{b} & \text{(不等式约束)} \\ & \mathbf{A}_{eq} \mathbf{x} = \mathbf{b}_{eq} & \text{(等式约束)} \\ & \mathbf{lb} \le \mathbf{x} \le \mathbf{ub} & \text{(决策变量的上下界约束)} \end{array} $$ 其中：

• x 是决策变量组成的列向量。
• c 是目标函数中各决策变量的系数组成的列向量。
• A 和 b 分别是不等式约束的系数矩阵和右端项向量。
• A$_{eq}$ 和 b$_{eq}$ 分别是等式约束的系数矩阵和右端项向量。
• lb 和 ub 分别是决策变量的下界和上界向量。

计算步骤

计算过程图：

将问题翻译成LP模型需要的参数。

第一步：根据问题建立数学模型

• 问题描述：张麻子既要攻楼又要追替身，他们一伙6人，总共1200发子弹；每有一人攻楼会给百姓带来40点士气值,每有一人追替身会给百姓带来30点士气值；攻楼每人需240发子弹，追替身每人需120发，问攻楼和追替身各派几个人，能使百姓的士气值最大?
• 模型建立过程：
  1. 决策变量：问题是要“如何分配人手”，所以：
     • $x_1$ = 攻碉楼的人数
     • $x_2$ = 追替身的人数
  2. 目标函数：目标是“使总士气值最大”。
     • 攻碉楼带来的士气: $40x_1$
     • 追替身带来的士气: $30x_2$
     • 总士气: $Z = 40x_1 + 30x_2$
     • 目标函数: $\max Z = 40x_1 + 30x_2$
  3. 所有约束条件：
     • 人力约束：“总共6人” $\implies x_1 + x_2 \le 6$
     • 弹药约束：“总共1200发子弹” $\implies 240x_1 + 120x_2 \le 1200$
     • 任务执行约束：“两项任务都必须执行” $\implies x_1 \ge 1$ 且 $x_2 \ge 1$
     • 隐含约束：人数不能为负，即 $x_1 \ge 0, x_2 \ge 0$ (此例中已被 $x_1 \ge 1, x_2 \ge 1$ 覆盖)

上面就是完整的模型建立。

第二步：转化为求解器标准形式

大部分的标准求解器都要一个特定的标准形式（一般是要最小化问题）。所以需要将上一步模型转化：

1. 目标函数转化：求解 $\max Z$ 等价于求解 $\min -Z$。

   • 原始目标: $\max Z = 40x_1 + 30x_2$
   • 转化后目标: $\min W = -40x_1 - 30x_2$
   • 对应的系数向量 $\mathbf{f}$ (在MATLAB中用 f 表示) 为: $f = \begin{bmatrix} -40 \ -30 \end{bmatrix}$

2. 约束条件转化：所有不等式约束都需要是“小于等于”。

   • $x_1 + x_2 \le 6$ (无需转化)
   • $240x_1 + 120x_2 \le 1200$ (无需转化)
   • $x_1 \ge 1 \implies -x_1 \le -1$
   • $x_2 \ge 1 \implies -x_2 \le -1$

3. 构建矩阵和向量：将转化后的不等式约束写成矩阵形式 $\mathbf{A}\mathbf{x} \le \mathbf{b}$。 $$ \begin{bmatrix} 1 & 1 \ 240 & 120 \ -1 & 0 \ 0 & -1 \end{bmatrix} \begin{bmatrix} x_1 \ x_2 \end{bmatrix} \le \begin{bmatrix} 6 \ 1200 \ -1 \ -1 \end{bmatrix} $$ 所有不等式约束矩阵 $\mathbf{A}$ 和向量 $\mathbf{b}$ 分别为： $$ \mathbf{A} = \begin{bmatrix} 1 & 1 \ 240 & 120 \ -1 & 0 \ 0 & -1 \end{bmatrix} \text{, } \mathbf{b} = \begin{bmatrix} 6 \ 1200 \ -1 \ -1 \end{bmatrix} $$

4. 处理等式和边界约束：

   • 此问题没有等式约束，因此 $\mathbf{A}{eq}$ 和 $\mathbf{b}{eq}$ 为空矩阵。

   • $x_1 \ge 1$ 和 $x_2 \ge 1$ 也可以直接作为决策变量的下界来处理。在这种情况下，下界向量 $\mathbf{lb} = \begin{bmatrix} 1 \ 1 \end{bmatrix}$。如果采用这种方式，则矩阵 $\mathbf{A}$ 和 $\mathbf{b}$ 中就不需要包含后两行。

     两种处理方式是等价的，但如果想要更高效可以考虑用边界约束。

第三步：编写代码并求解

使用MATLAB的 linprog 函数求解转化后的问题。以下是完整的、带有注释的示例代码。

% Matlab

% 线性规划求解示例: "张麻子攻楼"问题

% 1. 定义目标函数系数向量 f
% 原始问题是 max Z = 40*x1 + 30*x2
% 转化为 min W = -40*x1 - 30*x2
f = [-40; -30];

% 2. 定义不等式约束 A*x <= b
A = [1,   1;   % 人力约束: x1 + x2 <= 6
     240, 120]; % 弹药约束: 240*x1 + 120*x2 <= 1200

b = [6;      % 人力上限
     1200];  % 弹药上限

% 3. 定义等式约束 Aeq*x = beq (本例题无)
Aeq = [];
beq = [];

% 4. 定义决策变量的上下界 lb <= x <= ub
% 任务要求约束: x1 >= 1, x2 >= 1
lb = [1; 1];
ub = []; % 无上界

% 5. 调用 linprog 函数求解
% [x, fval] 分别返回最优解(决策变量的值)和最优目标函数值
[x, fval] = linprog(f, A, b, Aeq, beq, lb, ub);

% 6. 解释结果
optimal_x1 = x(1);
optimal_x2 = x(2);
max_morale = -fval; % 将最小化的结果转回最大化士气值

fprintf('最优决策方案:\n');
fprintf('  攻打碉楼的人数 (x1): %.2f\n', optimal_x1);
fprintf('  追击替身的人数 (x2): %.2f\n', optimal_x2);
fprintf('  能达到的最大士气值: %.2f\n', max_morale);

% 注意: 如果解出来是小数，而实际问题要求是整数，
% 则该问题本质上是整数规划(IP)问题。
% LP的解可以作为IP问题的一个参考或松弛解。
% 在本例中，解恰好为整数。
% 求解结果: x1 = 4, x2 = 2, 最大士气值 = 220

运行上述代码，可得最优解为：派4人攻碉楼，2人追替身，可获得最大士气值220。

灵敏度分析

只给出最优解的值远远不够，对解决方案的深度分析也非常重要。

1. 影子价格：LP中最富有洞察力的概念之一。一个约束条件的影子价格，定义为该约束的右端项每增加一个单位，目标函数最优值会产生的变化量。

• 经济学解释：在当前最优生产计划下，多获得一单位的资源，能为你的总目标带来多大的增量。
• 如果人力约束的影子价格是10，意味着增加一个单位的工时（例如1小时），总利润将增加10元。10元就是这一小时人工的边际经济价值。
• 如果某个约束的影子价格为0，这表明该项资源在当前计划下没有用完（即约束是非绑定的）。所以再增加该资源对目标函数没有任何帮助。

在竞赛论文里，不能只列出数值，一定要分析，然后说说建议。

2. 允许范围：影子价格只在一个特定的范围内成立，就是允许范围。求解器通常会给出目标函数系数和约束右端项的“允许增加量”和“允许减少量”。

• 对于约束右端项：资源量可以在多大的区间内变动，而其影子价格保持不变。超出了这个范围，最优的生产组合可能会变，影子价格也会随着变。
• 对于目标函数系数：一个产品的单位利润（或成本）可以在多大的区间内波动，而当前的最优生产计划仍然保持不变。

如果某个关键成本的允许范围非常窄，说明我们的的最优解对该成本的微小波动非常敏感，在建议里就必须警示一下。如果宽泛就说明很稳健。

示例：

约束名	类型	资源上限	状态 (绑定/非绑定)	影子价格	允许增加	允许减少	管理启示
人力资源	$\le$	1000 小时	绑定	50 元/小时	200	150	人力是瓶颈。每增加1小时工时，利润增加50元。建议优先考虑加班或招聘，只要成本低于50元/小时。
材料A	$\le$	500 公斤	非绑定	0 元/公斤	$\infty$	80	材料A有富余。不建议继续采购，甚至可以考虑出售多余的80公斤库存。
市场需求B	$\le$	200 件	绑定	25 元/件	50	30	B产品的市场需求是限制利润的瓶颈。每提升1单位市场需求，利润增加25元。

模型的优缺点

优点

1. 理论成熟，求解高效：LP有坚实的数学理论基础，保证在有限步内找到最优解（如果存在）。对于大规模问题，也能较快完成计算。

2. 模型清晰，易于理解：线性模型的结构简单直观，各个参数的关系一目了然。

3. 应用广泛：可应用于生产计划、资源分配、供应链管理、金融投资、人员调度等领域。

4. 灵敏度分析信息丰富：求解LP不仅能得到最优解，还能附带产出影子价格、容许变化范围等极具价值的灵敏度信息。

缺点

1. 假设过于严格：LP的四大假设（比例性、可加性、可分性、确定性）对于现实世界还是比较难的，太理想了。现实问题可能会包含非线性关系、变量间的交互作用、整数要求和不确定性之类的。

2. 无法处理非线性关系

3. 对不确定性的处理能力有限：难以直接处理随机因素的风险。需要借助更高级的方法弥补。

   可以通过灵敏度分析来应对数据不确定性的弱点，下面会提到。

4. 单目标局限：传统LP只能优化一个目标。而现实中的决策大概率需要权衡多个冲突的目标。

我的思考与总结

模型是工具，洞见才是产品。要借助工具去分析，提出有价值的建议。

参考资料

【大师兄数学建模】第7讲 线性规划_哔哩哔哩_bilibili