数学建模 - 规划问题

一、线性规划（LP）

1.1 标准型

线性规划可以转化成标准型，但是可以发现有两种标准型，分别对应软件程序和数学形式，如下所示：

LP 求解器一般接口

数学形式

1.2 决策变量建模

1.2.1 时间段

对于投资的模型，一般会有 “一年收益、两年收益” 的问题，然后就会弄不清在 2023 年投资的一年期，到底是在 2023 年收钱，还是在 2024 年收钱。

为了让这个问题弄清，我们可以设在 “年初” 投资，那么收益就可以用于第二年 “年初” 的投资。

1.2.2 二维决策变量

有一些问题，没法用 $x_0, x_1, \cdots , x_n$ 这种模型去表示决策变量，有的时候很复杂，比如说运输问题

1.3 灵敏度分析

灵敏度分析已经复习过无数次了，这里总结一下。

灵敏度分析应该是某个参数（或者说约束条件）对于决策变量（而不是目标函数）的影响，这是因为决策变量对于目标函数的影响显而易见。我们更想看的是，到底约束条件是如何影响决策过程的。

我们可以在求出带着参数的决策变量最优解，比如说如下所示

然后会发现现在 $x_1$ 和 $x_2$ 都受到 $a$ 的影响了。

然后其实有一个导数就已经很说明问题了，但是我们依然利用了某种归一化的手段让其更加合理

$$\frac{\frac{dx}{x}}{\frac{da}{a}} = \frac{dx}{da} \times \frac{a}{x}$$

1.4 多目标规划

有些时候目标函数并不止有一个，比如说在投资的时候，我们不但希望投资的回报高，而且希望风险低，所以我们一般有两种解决办法，以投资问题为例

第一种方式是可以给其中一个目标设置一个 “接受限度”，比如说 “风险最高不超过多少” 或者 “收益最低不低于多少”

第二种是分配给两个不同的目标不同的权重，然后将其综合成同一个目标，如下所示

1.5 trick

1.5.1 整型规划

1.5.2 绝对值最小化

绝对值最小化，利用的变量替换，我们用两个正变量去表示原来的变量，如下所示

原方程

变形后

1.5.3 最大最小问题

原本目标方程是希望求解一个最大值的最小值，我们可以对于 “最大值” 进行翻译，将其表示为 “比每一个值都大 “，这样的求解就会变得自然，如下所示

可以变形成

1.5.4 变量取值范围不连续

严格讲并不能很好的解释这个问题，只是实现了在 “一定区间 “和 “零” 之间的不连续问题，通过引入一个布尔值来控制范围

1.5.5 或条件

可以采用一个较大的罚值结合一个布尔值完成 “或” 操作

1.5.6 条件约束

其实我们在 1.5.5 已经获得了 “或” 的表达方式，同时对于一个约束条件的取反，是一个很显然的事情，那么其实我们已经可以用 $\{\lor, \neg\}$ 就已经可以表示所有的逻辑运算了，比如说

$$p \rightarrow q = \neg p \lor q$$

所以才有了下面的操作

---

二、非线性规划

2.1 理论

2.1.1 无约束问题

对于目标函数，可以去求它的 Hesse 矩阵，也就是如下所示

当 Hesse 矩阵在为正定矩阵时，同时 $f$ 的导数为 0，那么就达到了局部最小值。这并不奇怪，这是因为正定阵揭示了 Hesse 矩阵在进行过相合变换（本质是一个二次型在不同基下发生的变换）后可以规约到一个比较正的矩阵，因为二阶导数暗示了往某个方向走（可以看做发生 $dxdy$ 的偏移），目标函数会发生的变化，如果无论怎么走，都是为正的，那么就说明当前的极值是极小值。

2.1.2 等式约束问题

Hesse 矩阵求解的是无约束问题下的极值，我们现在希望求解有等式约束条件下的目标函数极值，那么就可以采用拉格朗日（Langrange）乘子法，其核心思想是利用利用原有的目标函数和等式约束条件，再加入一些新的变量，构造出一个新的目标函数，我们再按照无约束的方式去求解。

其 “行得通” 的原因是因为在进行 “让导数等于 0 ” 这个运算，会使得约束条件再次出现（因为约束条件也是等值形式的）。对于如下形式

$$min \space f(x) \quad \quad st. \space\space h_i(x) = 0 \quad(i = 0, 1, \cdots, n)$$

我们构造这样的函数

$$L(x, \lambda_i) = f(x) + \lambda_1h_1(x) + \lambda_2h_2(x) + \cdots + \lambda_nh_n(x)$$

我们除了要对 $x$ 求导外，还要对 $\lambda_i$ 求导（也就是让 $x$ 和 $\lambda_i$ 都等价于自变量），那么求导就会有如下结果

$$\left[\begin{matrix} f^\prime(x)\\ h_1(x)\\ h_2(x)\\ \cdots\\ h_n(x) \end{matrix}\right] = 0$$

恰好对于 $\lambda$ 求导的结果搞好形成了原约束条件。

2.1.3 不等式约束问题

不等式约束没法 “借着导数为 0 ” 的东风完成构造，不等式不容易进行构造（没准可以先依靠积分，然后再在二阶导 Hesse 矩阵的正定性处发挥作用）。

所以我们采用更加工程化的方法，采用罚惩法来避免不等式的不成立，如下所示

2.1.4 凸优化问题

可以看到无论是有约束的还是没有约束的问题，这种通用的求解方法都会变得极其复杂，所以我们对于非线性优化并没有太大的把握。

凸优化属于是一种特殊的非线性规划，它的性质极好，更加方便我们的求解。其中一个很有用的性质就是 “局部最优解一定是全局最优解”。