本章内容：线性规划 整数规划 非线性规划

规划问题 建模思路

无非就是把这些规划化成对应规划的标准形式，然后就可以丢进 MATLAB 里跑了。

线性规划用 linprog。整数线性规划用 intlinprog。二次规划使用 quadprog。

非线性约束中，对于无约束优化用 fminunc 或 fminsearch，对于有约束优化用 fmincon。

对于要求一系列函数中最大值的极小值，可以使用 fminimax。

除此之外，还有 fminbnd、fseminf、fminimax。这些函数都是解决非线性规划问题，但算法不一样。可能平时不用学习，但在实战中如果遇到 fmincon 函数失效的情况，可以考虑使用一下。

注意，MATLAB 不提供解 非线性规划+整数规划 问题的函数，也不支持两个自变量相乘（如 xy <= 3）的问题。如果必要，可以上遗传算法 ga，或使用 LINGO 进行编程。

以上函数的用法类似，可以使用传统的输入参数 $Aeq$、$beq$ 等进行求解，也可以使用 Problem-Based Approach。

函数的使用方法可以用的时候再查表。

非线性约束条件的规划问题转化为线性规划问题的方式可看优化 | 线性规划和整数规划的若干建模技巧 (opens new window)。

蒙特卡罗法的正确性（或者说，有效性？）是由概率统计保证的。假设随机投点投入高值区的概率为 $0.00001$，投 $10^6$ 次，则最优解在高值区的概率为

$1-0.99999^{10^6} = 0.9999546$

例题 线性规划

题目来源：《数学建模算法与应用（第2版）》（司守奎主编）例 1.4

完成下面的线性规划。

$\min z=\left|x_{1}\right|+2\left|x_{2}\right|+3\left|x_{3}\right|+4\left|x_{4}\right|$

$s.t.\left\{\begin{array}{rrrrrr} x_{1}&-x_{2}&-x_{3}&+x_{4}& \leq& -2 \\ x_{1}&-x_{2}&+x_{3}&-3 x_{4}& \leq& -1 \\ x_{1}&-x_{2}&-2 x_{3}&+3 x_{4}& \leq& -\frac{1}{2} \end{array}\right.$

进行变量替换：

$\begin{cases} u_i = |x_i| + x_i \\ v_i = |x_i| - x_i \end{cases}$

问题转化为自变量为 $u_i$ $v_i$ 的线性规划。

使用 Problem-Based Approach 的 MATLAB 代码如下：

u = optimvar('u',4,'LowerBound',0);
v = optimvar('v',4,'LowerBound',0);

absx = (u + v)/2;
x = (u - v)/2;

z = absx(1) + 2*absx(2) + 3*absx(3) + 4*absx(4);
cons1 = x(1) - x(2) - x(3) + x(4) <= -2;
cons2 = x(1) - x(2) + x(3) - 3*x(4) <= -1;
cons3 = x(1) - x(2) - 2*x(3) + 3*x(4) <= -1/2;

prob = optimproblem('Objective',z);
prob.Constraints.cons1 = cons1;
prob.Constraints.cons2 = cons2;
prob.Constraints.cons3 = cons3;

problem = prob2struct(prob);
% problem.options = optimoptions('linprog','Display',"off");
[sol,fval,exitflag,output] = linprog(problem)

解得 sol = [0 4 0 0 0 0 0 0]。由 varindex(prob) 可得 sol 各值和 $u_i, v_i$ 的对应关系。可得除了 $u_2=4$ 以外，其他都是 $0$。

代入 $x_i$ 后可得，当 $x_2 = 0, x_1 = x_3 = x_4 = 0$ 时，$\min z = 4$。

例题 整数规划

题目来源：《数学建模算法与应用（第2版）》（司守奎主编）练习 2.4

设计知识点：整数规划、蒙特卡罗、分布检验

一篇题解：https://docsplayer.com/25899644-Microsoft-word-a-doc.html

看起来是一个整数规划，但是第二问却无从下手。看到上面的题解才发现了有意思的东西。

第一小问

第一小问挺简单的，就是给定了价值矩阵，求一个整数规划。不过题目中仍有 case 的情况，即：

$k_i=\begin{cases} 0 & \sum\limits_{j=1}^4 x_{ij} < 4 \\ 1 & \sum\limits_{j=1}^4 x_{ij} = 4 \end{cases}$

其中 $x_{ij}$ 为 $0-1$ 变量，当第 $i$ 名运动员参加 $j$ 项目时为 $1$。
$k_i$ 也是 $0-1$ 变量，当第 $i$ 名运动员参加全部四项项目时为 $1$。

将这个条件化为线性约束条件时，答案用的很妙：

$0 \leq \sum\limits_{j=1}^4 x_{ij} - 4k_i \leq 3$

如果问这是怎么推出来，其实也可以由 优化 | 线性规划和整数规划的若干建模技巧 (opens new window) 给的大 $M$ 法推。

不过这里由于 $x,y$ 都是 $0-1$ 变量，所以约束条件是不唯一的。不过答案给的这一种比较美观、简洁。

第二小问

第二问的话，有点无从下手，因为价值矩阵是不确定的，没法规划。

有意思的地方就在于，第一问没有让求最乐观情况下的最优解，而最乐观的情况下的最大值，也就比目标值多了 $0.3$。这意味着，运动员在绝大多数地方必须发挥最好，仅有一两次机会发挥不好。夺冠的概率很低很低。

因此，不再追求夺冠率的极大值（毕竟可能也就 $1\times10^{-20}$ 和 $2\times10^{-20}$ 的区别），而是追求期望分数的极大值（前提是该分配下的最乐观情况能够夺冠），即：

$\max S = \text{平均期望的总分数}$

$s.t. \quad \text{最乐观情况的总分数} \geq 236.2$

这种想法还有一种原因，文章在结语里提到，在实际生活中这是一种很自然的想法。

考虑到实际生活中教练基本是按每位运动员平均得分以及稳定程度确定阵容，因此……

第二个有意思的地方在于他对第二问计算得分期望的概率函数换了一个方式建模。我的想法是用蒙特卡罗法模拟足够多次，通过这些数据作出它的曲线。

但是文章模拟了 70 次，然后就交给 lillietest 函数，检验出来是正态分布，接下来就按照正态分布做了。这是我没想到的。这也是数据处理的一个思路，

——说不定就是个正态分布了呢？

建模技巧

非线性约束条件的规划问题转化为线性规划问题的方式可看优化 | 线性规划和整数规划的若干建模技巧 (opens new window)。

选择地购买若干种资产或存银行生息，使净收益尽可能大，总体风险尽可能小。

这里可以进行多目标优化。

另外一种做法就是枚举收益值（如 $\Delta a=0.01$），对于每个收益值求最小风险，然后作函数图。

• 如果非线性规划问题要求实时算法，则可以使用罚函数方法，但计算精度较低。
• 如果非线性规划问题不要求实时算法，但要求精度高，则可以使用 Lingo 软件编程求解或使用 Matlab 的 fmincon 命令求解。

例题 国赛 2009D 会议筹备

知识点：线性规划、整数规划、多目标规划、线性回归。

题目链接：http://special.univs.cn/service/jianmo/sxjmtmhb/2009/1009/864452.shtml 优秀论文：https://wenku.baidu.com/view/d32ba04669eae009581bec2c.html PPT 讲解：https://wenku.baidu.com/view/67e207a6284ac850ad024229.html?rec_flag=default&sxts=1587173703951 上面两个资料各有优缺点，可以对比参考。 优秀论文 2：https://wenku.baidu.com/view/5e238f01de80d4d8d15a4f73.html 简化版的题目的建模，简化为整数建模：https://wenku.baidu.com/view/5c1657c03186bceb19e8bbef.html

请你们通过数学建模方法，从经济、方便、代表满意等方面，为会议筹备组制定一个预订宾馆客房、租借会议室、租用客车的合理方案。

审题：从三个方面分析，应该看出来这是多目标规划。

宾馆的预定与会议室的租借都是 0—1 规划模型，我们在考虑宾馆和会议室的时候，当宾馆预订时，此会议室可以开，也可以不开，但是当某个会议室租借时，对应的宾馆就必须预订。

宾馆和会议室之间的对应关系为 $y_{ij}\leq x_{ij}$。

租车要考虑多少代表参加哪个分组会议，题目中没有这方面的信息，可以按照平均的、随机的方式处理。

题目没有提到的东西，就可以假设为平均的、随机的。用好这些假设，简化问题。

优化的约束条件中有：

$y=\begin{cases} 1 & x > 0 \\ 0 & x = 0 \end{cases}$

显然该约束条件无法在 MATLAB 中直接调用 intlinprog 求解。

可以将约束条件转化为：

$\varepsilon y \leq x \leq My$

其中 $\varepsilon$ 为足够小的数，$M$ 为足够大的数。