​如果要问每年的数模比赛，最可能考什么题？那必然是优化问题！

而优化问题中最常见的，就是线性/整数规划问题。即使赛题中有非线性目标/约束，第一想法也应是将其转化为线性。

直白点说，只要决定参加数模比赛，学会建立并求解线性/整数规划问题是非常必要的。

本期主要阐述用Matlab软件求解此类问题的一般步骤，后几期会逐步增加用Mathematica、AMPL、CPLEX、Gurobi、Python等软件求解的教程。

或许你已经听说或掌握了linprog等函数，实际上，它只是诸多求解方法中的一种，且有一定的局限性。

我的每期文章力求"阅完可上手"并"知其所以然"。因此，在讲解如何应用linprog等函数语法前，有必要先了解：

    什么赛题适用线性/整数规划？如何把非线性形式线性化？如何查看某函数的语法？有哪几种求解方法？

把握好这四个问题，有时候比仅仅会用linprog等函数求解更重要。

一、什么赛题适用线性/整数规划

当题目中提到“怎样分配”、“XX最大/最合理”、“XX尽量多/少”等词汇时。具体有：

1. 生产安排

目标：总利润最大；约束：原材料、设备限制；

2. 销售运输

目标：运费等成本最低；约束：从某产地(产量有限制)运往某销地的运费不同；

3. 投资收益等

目标：总收益最大；约束：不同资产配置下收益率/风险不同，总资金有限；

对于整数规划，除了通常要求变量为整数外，典型的还有指派/背包等问题(决策变量有0-1变量)。

二、如何把非线性形式线性化

在比赛时，遇到非线性形式是家常便饭。此时若能够线性化该问题，绝对是你数模论文的加分项。

我在之前写的线性化文章中提到：如下非线性形式，均可实现线性化：

总的来说，具有分段函数形式、绝对值函数形式、最小/大值函数形式、逻辑或形式、含有0-1变量的乘积形式、混合整数形式以及分式目标函数，均可实现线性化。

而实现线性化的主要手段主要就两点，一是引入0-1变量，二是引入很大的整数M。具体细节请参见之前写的线性化文章。

三、如何查看函数所有功能

授之以鱼，不如授之以渔。

学习linprog等函数最好的方法，无疑是看Matlab官方帮助文档。本文仅是抛砖引玉地举例说明几个函数的基础用法，更多细节参见帮助文档。步骤是：

    调用linprog等函数前需要事先安装“OptimizationToolbox”工具箱；在Matlab命令窗口输入“doc linprog”，便可查看语法，里面有丰富的例子；也可直接查看官方给的PDF帮助文档，后台回复“线性规划”可获取。

四、有哪几种求解方法

这里指的是写代码的思路/方法有几种。Matlab帮助文档里也指出了：

Optimization Toolbox工具箱有两种求解优化问题的方法：基于问题和基于求解器。

我编了两个口诀来描述它们的差异："所见即所建"和"参数提前建"。

1. 基于问题——“所见即所建”

含义：写代码时逐行照抄你建立的模型形式，让Matlab去帮你转化成矩阵形式求解；

方法：调用optimproblem，写的代码简单直观；

2. 基于求解器——“参数提前建”

含义：所有输入参数按照矩阵形式提前写好，再让Matlab求解；

方法：调用linprog函数，以矩阵形式传入各个参数，求解时间短。

其实还有其他求解方法，或许有小伙伴用过：在Matlab中先配置Yalmip工具箱，再用Gurobi、CPLEX等求解器求解。该方法敬请期待后续文章。

下面，详细讲解这两种建模方法的思路和求解步骤。

五、基于问题的求解方法步骤

在基于问题的求解方法中：

需要创建优化变量，用这些变量来构建表示目标和约束的表达式，并使用solve函数求解问题。

具体地，举一个求解最大化问题的例子(优化变量为x1、x2)：

该方法无需事先写成矩阵形式，“所见即所建”——模型怎么写，代码就怎么抄。

    在逐行抄之前，先定义问题和变量：起个名字，叫“prob”；默认为最小化问题，所以这里需写上“max”；用“optimvar”创建2行1列的x变量，下界为0；
prob = optimproblem('ObjectiveSense','max'); % 创建优化问题 x = optimvar('x',2,1,'LowerBound',0); %创建两个正变量，即决策变量x1和x2
    创建目标和约束：其中，“prob.Objective”含义是“prob问题的Objective是什么”；同理，三个约束的定义也是用“.”；
prob.Objective = x(1)+2*x(2); % 创建目标函数 prob.Constraints.cs1 = x(1)+5*x(2)<=100; % 创建线性不等式约束 prob.Constraints.cs2 = x(1)+x(2)<=40; % 命名为cs2 prob.Constraints.cs3 = 2*x(1)+x(2)/2<=60; % 命名为cs3
    求解模型：用"solve"函数求解模型，输出x的解sol和目标值f；sol.x可查看x的值；最终x_value=[25; 15]。
[sol,f] = solve(prob); % 求解变量值和目标值 x_value = sol.x

可见，真正建模的代码就第二部分，很简单吧，几乎是逐行照抄了图片中的模型。

虽然该方法简单直观，但缺点是求解时间较长。因为Maltab只会做矩阵运算，它需要帮你把问题转化为矩阵形式，再计算。

六、基于求解器的方法

这里主要指用linprog函数求解线性规划和用intlinprog函数求解整数规划的方法。(默认调用quadprog求解器求解)

1. 线性规划——linprog函数语法

在Matlab命令窗口输入“doc linprog”，可知其语法为：

以第四个为例，线性规划模型与函数各输入参数的对应关系如下：

其中，Aeq中eq含义为equation(等式)，参数options可以写内点法/对偶单纯形法等，一般不用写。

注意：上图是标准化形式，Maltab要求必须整理成如上结构。具体有：

    必须转化为最小化问题；必须是≤，若为≥，左右两边同乘-1。举例：

其中，所有系数必须用矩阵或向量表示；约束1左右同乘-1，变为≤；不等式约束和等式约束分开写。代码如下：

f = [-1 -2]; % 目标函数系数 % 不等式约束 A=[-1 -5; 2 1/2]; b=[-100; 60]; % 等式约束 Aeq=[1 1]; beq=40; % 上界和下界定义 lb=[20, 0]; ub=[inf, 40]; % 求最优变量值x和函数值f [x, f] = linprog(f,A,b,Aeq,beq,lb,ub); % 最后不要忘了添加负号，变回最大值问题 f_value = -f

其中，上界里inf含义是无穷大；目标函数值最后不要忘了添加负号，变回最大值问题。

可见，相比于基于问题的求解方法，该方法需要做好前期工作，严格按照标准化形式输入参数。

2. 整数规划——intlinprog函数语法

在Matlab命令窗口输入“doc intlinprog”，其语法为：

仔细与linprog对比后发现，就多了intcon和x0。其中intcon定义哪个位置上的数为整数，x0是初始值，可不写。

这里给出一个混合整数规划的例子：

其中，x3为binary(二元变量)，其下界为0，上界为1。求解代码为：

f=[-3 -2 -1]; intcon=3; % 定义第三个变量为整数 % 不等式约束 A=[1 1 1]; b=7; % 等式约束 Aeq = [4 2 1]; beq = 12; % 上下界 lb = [0 0 0]; ub = [inf inf 1]; % 求最优变量值x和函数值f [x,f]=intlinprog(f,intcon,A,b,Aeq,beq,lb,ub);

可见，代码并不复杂。但intlinprog函数的缺点是，它要求变量必须是一维变量。

也就是说，若你建模时变量为二维的X ij，那也得想办法降维为Y k。

因此，对于高维复杂的混合整数规划问题，我并不建议用intlinprog函数，后续文章我会给出其他软件的求解方法。

3. 指派问题

该部分展示下如何把二维变量Xij转化为一维的Yk。这部分有点难度，且针对学过指派问题的同学，实在不理解可跳过该部分。

指派问题：分配n人去做n项工作；每人做且只做一项工作；若分配第i人去做第j项工作，需花费Cij成本。
问应如何分配工作使总成本最小？

引入0-1变量xij：若第i人做第j项工作为1，否则为0。模型和成本Cij矩阵如下：

注意，模型看似是两个约束，实则不然。第一个约束是对于任意的i成立，因此实则为3个约束；同理，第二个也是，故共6个约束。

那如何将二维转化为一维呢，很简单，xij有9个值，那我们分别将这9个值对应yk即可。

基于上述分析，便转化为求yk这个一维变量的值，代码如下：

% 目标函数系数由矩阵C变为f C = [3 8 2; 8 4 6; 6 2 10]; [n, ~] = size(C); f = C(:); % 约束的系数矩阵，先全写为0 Aeq = zeros(2*n, n^2); intcon = 1: n^2; % 给等式约束的系数矩阵赋值 for i = 1:n Aeq(i, i:n:n^2) = 1; Aeq(n+i, (i-1)*n+1: n*i) = 1; end beq = ones(2*n, 1); % 给定上下界 lb = zeros(n^2, 1); ub = ones(n^2, 1); % 输出结果 x = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub) x = reshape(x, [n,n])

注意：既然决策变量由xij变为yk，对应地，目标函数的系数矩阵由C变为了f。

七、结语

总结下本文的核心：

    阐述两种建模方法：基于问题和基于求解器；阐述linprog/intlinprog/optimproblem函数语法；阐述如何将二维变量转化为一维变量，以指派问题为例。

更具体的，分别为基于问题和基于求解器的特定编了口诀。前者为所见即所建，后者为参数提前建。

总的来说，本文提到的三个函数对于求解课本上的习题来说，绰绰有余。但对于高维且复杂的问题，有点繁琐且乏力。为此，后续文章我会给出其他软件求解混合整数线性/非线性规划的方法。

祝大家科研节节高。科研小飞期待您的关注转发。不闻不若闻之，闻之不若见之；见之不若知之，知之不若行之。

我是科研小飞，期待您的关注。

最后，本文的“Matlab代码”和“优化工具箱使用文档”放在了百度云，关注我的微信公众号“科研小飞”并在后台回复“线性规划”便可直接下载。

此外，回复“数学建模”可获取2015-2021年研究生数模的赛题、优秀论文、论文模板等；所有资料也同时上传至QQ群，回复“QQ群”获取群号。

微信公众号：KeYanXF（科研小飞）