2026-08-06-Note

线性规划、整数规划与偏微分方程建模

Ref: assets/2026-08-06/线性规划与整数规划方法.pdf · assets/2026-08-06/偏微分方程.pdf

一、线性规划（LP）

标准形式与三要素

$$\min /\max z=\sum _{j=1}^n{c}_j{x}_j,\text{s.t.}\sum _{j=1}^n{a}_{ij}{x}_j\le b_i(i=1,\dots ,m),x_j\ge 0$$

三要素：决策变量 $x_j$、目标函数（线性）、约束条件（线性 + 非负）。

我的理解

LP 是”最省力的一类优化”：目标和约束全是直线/平面，可行域是多面体，最优解一定出现在顶点上——所以单纯形法只需要沿顶点走，不用扫描无穷多个点。这个”顶点性质”是 LP 好解的根本原因。

建模套路（把现实翻译成线性）

1. 找决策变量：运输量 $x_{ij}$、是否做某事 $y_i\in \{0,1\}$；
2. 写目标：成本最小 / 利润最大；
3. 写约束：资源、需求、供应、逻辑关系。

运输问题（讲义例）：2 个工厂（供应 78、45）→ 3 个销地（需求 43、35、45），单位成本表（13/15/12、11/29/22）：

$$\min z=13x_{11}+15x_{12}+12x_{13}+11x_{21}+29x_{22}+22x_{23}$$ $$\text{s.t.}{x}_{11}+x_{12}+x_{13}=78,x_{21}+x_{22}+x_{23}=45,x_{11}+x_{21}=43,x_{12}+x_{22}=35,x_{13}+x_{23}=45$$

行和 = 工厂供应量，列和 = 销地需求量——这就是”产销平衡运输问题”的标准骨架。

二、整数规划（IP）

分类

类型	变量取值	例子
纯整数规划	全部整数	生产件数
混合整数规划	部分整数	连续产量 + 是否建厂
0-1 规划	0 或 1	选址、指派、排班

0-1 变量建模技巧（重点）

• 选择依赖：选了 A 才能选 B ⟹ $x_B\le x_A$；
• 互斥：A、B 只能选一个 ⟹ $x_1+x_2\le 1$；
• 至少选一个 ⟹ $x_1+x_2\ge 1$；
• 固定成本 / 分段函数：引入 0-1 变量与”大 M”约束；
• 特殊有序集（SOS）：排他性选择。

为什么不能四舍五入

IP 不能靠”先解 LP 再四舍五入”——四舍五入后的点可能不可行，也可能离最优很远。标准解法是分支定界（branch and bound）：把整数变量分裂成子问题、逐枝剪掉不可能的分支；配合割平面（cutting plane）收紧可行域。

求解工具

• 连续 LP：MATLAB linprog、Python scipy.optimize.linprog、LINGO；
• 整数规划：Gurobi / CPLEX / Python PuLP（分支定界、割平面）。

理解

LP 是”连续世界里的线性可加”，IP 是”现实世界里的 是/否 决策”。数模里排班、选址、路径问题本质都是 0-1 整数规划——先想清楚”哪些是决策、哪些是约束”，比会调求解器更重要。

三、偏微分方程（PDE）方法建模

三类经典方程（都从现实问题”长”出来）

方程	形式	起源	参数
波动方程	$\frac{{\partial }^{2}u}{\partial t^2}=a^2\frac{{\partial }^{2}u}{\partial x^2}$	弦振动（离散质点链 → 连续化取极限）	$a^2=T/\sigma$
热传导/扩散	$\frac{\partial u}{\partial t}=k\Delta u$	Fourier 定律 $q=-k\mathrm{grad}u$ / Fick 扩散定律	$k$ 热/扩散系数
Laplace / Poisson	$\Delta u=0$ / $-a^2\Delta u=f$	引力势、稳态场	—

建模套路：微元法

1. 选未知函数 $u(x,t)$（温度 / 浓度 / 位移）；
2. 取一个微元、一个小区间 $[t,t+\Delta t]$，写守恒律：流入 − 流出 = 变化量；
3. 用经验定律（Fourier / Fick / 牛顿第二定律）把”通量”写成梯度的函数；
4. 令 $\Delta x,\Delta t\to 0$，取极限得到 PDE，再补上定解条件。

弦振动就是标准示范：n 个质点 → n 个二阶常微分方程（$y_{k+1}-2y_k+y_{k-1}$ 是离散二阶差商）→ 连续化后差商变成 ${\partial }^{2}y/\partial x^2$。

定解条件与适定性

• 三类边界条件：Dirichlet（第一类，给定函数值）、Neumann（第二类，给定法向导数）、Robin（第三类，$\alpha \partial u/\partial \nu +\beta u=\phi$，混合）；
• 适定性（well-posed）：解存在、唯一、连续依赖初边值（数据小扰动 → 解小扰动）；
• 经典解法：D’Alembert 行波法（波动方程 Cauchy 问题）、分离变量法、Fourier 变换法、Green 函数法、有限差分等数值方法。

案例

案例 1：烟雾的扩散与消失（消光与能见度）

• 扩散方程 $\frac{\partial C}{\partial t}=k\Delta C$（$k$ 扩散系数）；
• 消光规律 $I(l)=I_0{e}^{-\alpha \int Cds}$（光强随烟雾浓度指数衰减）；
• 可见范围 $r(t)=\sqrt{4kt\ln \frac{\alpha Q}{4\pi k\mu t}}$；可见范围最大的时刻 $t_1=\frac{\alpha Q}{4\pi k\mu e}$，烟雾”完全消失”时刻 $t_2=\frac{\alpha Q}{4\pi k\mu }=e\cdot t_1\approx 2.7t_1$。

案例 2：传输线（电报方程）

由 Kirchhoff 定律写出电流/电压的偏微分方程组：

$$V_x=-L{I}_t-RI,I_x=-C{V}_t-GV$$

消去一个变量 ⟹ $u_{xx}-a{u}_{tt}-b{u}_t-cu=0$（$a=LC,b=RC+LG,c=RG$）——一条方程同时含二阶时间、一阶时间和零阶项，是”耗散传输线”的典型形态。

案例 3：高温作业服装热传导（2018 国赛 A 题）

• 多层织物（I/II/III 层）+ 空气层 + 皮肤，逐层建立热传导方程；
• 层间界面用温度连续 + 热流连续衔接；
• 问题归结为带边界条件的 PDE 定解问题，用数值方法（有限差分）求解温度分布。

和差分的关系

PDE 是”把离散规律连续化”，差分方程是”把连续过程离散化”——正好是一对互逆操作。建模时看数据的天然形态：变量按周期记录 → 差分；物理量处处连续 → PDE。