最优化赛题是数学建模大赛中最常见的问题类型之一。一般说来，凡是寻求最大、最小、最远、最近、最经济、最丰富、最高效、最耗时的目标，都可以划入优化问题的范畴。MATLAB 优化工具箱和全局优化工具箱对多个优化问题提供了完整的解决方案，前者涵盖了线性规划、混合整型线性规划、二次规划、非线性优化、非线性最小二乘的求解器，后者囊括了全局搜索、多初始点、模式搜索、遗传算法等求解算法。


本讲主要介绍如何使用优化工具箱求解数学建模中标准的优化模型。更多的内容，欢迎大家浏览 MathWorks 官网以及 MATLAB 软件文档。

1.
 聊一聊最优化问题

最优化即在一定的条件下，寻求使目标最小（大）的设计参数或决策。在优化问题中有两个关键对象：目标函数和约束条件（可选）。常规优化问题，其数学表达可以描述为：






其中x 为长度n的决策变量向量，f(x) 为目标函数，G(x) 为约束函数。

求解目标函数的最小（大）值，一个高效而精确的解决方案不仅取决于约束条件和变量数量，更取决于目标函数和约束函数的特性。明确优化类型是确认优化方案的前提，让我们看一下这些特性如何划分：









常见的目标函数有：


线性规划：被广泛的应用于变量之间可线性表示的财务、能源、运营研究等现代管理领域中。

混合整数线性规划：扩展了线性规划问题，增加了最优解中部分或全部变量必须是整数的约束。例如，如果一个变量代表要认购的股票数量，则只应取整数值。同样，如果一个变量代表发电机的开/关状态，则只应取二进制值（0
 或 1）。

二次规划：目标函数或约束函数为多元二次函数。此优化应用于财务金融中投资组合优化、发电厂发电优化、工程中设计优化等领域。

最小二乘：分为线性和非线性，通过最小化误差的平方和寻找变量的最优函数匹配。非线性最小二乘优化还可用于曲线拟合。


2. 优化求解器太多了，怎么选？

对 MATLAB 提供的各类优化问题的算法，我们称之为求解器（Solver）。根据其求解目标，被分为四大组：


极小值优化组：找到目标函数出发点 x0 附近的局部极小值


多目标优化组：找到最小化一组函数的最大值或指定的值


方程求解组：找到非线性方程 f(x) = 0 出发点 x0 附近的解


最小二乘法（曲线拟合）组：最小化平方和

仅优化工具箱就提供了近 20 种求解器，面对如此繁多的选项，用户往往一头雾水。幸好，MATLAB 提供了简单明了的参考工具 —— 优化决策表。可谓一表在手，优化不愁：




上表中*表示算法由全局工具箱提供。此外，多目标优化与方程组求解器并未被此表列举，更多求解器的选择方案，可以点击阅读原文查看。

3. 写出漂亮、高效的代码

确认优化策略后，就可以开工写代码了。下面让我们通过一个例子，了解编写高效优化算法代码的步骤和注意事项。

[题目]

- 目标函数




-  约束函数（所有变量为正）





[解答]

a. 首先，根据题目确认这是一个线性规划问题。而线性规划的通用数学表达式和MATLAB标准形式为：




 创建符合标准格式的A、b、Aeq、beq、lb、ub参数，才可以顺利的运行优化算法。

b. 对于线性规划的优化求解步骤（也适用于其他优化方案），建议如下：

    1 ) 选择优化求解器

    2 ) 将所有变量合并为一个向量

    3 ) 创建边界约束（lb，ub）

    4 ) 创建线性不等式约束（A，b）

    5 ) 创建线性等式约束（Aeq，beq）

    6 ) 创建目标函数

    7 ) 优化问题求解

    8 ) 结果检验

c. MATLAB
 代码和注释：







d. 优化结果：




e. 如果结果不满意，可以调整优化选项，迭代计算。

4. 整数规划求解神器

在优化问题中， 经常会遇到整数规划问题， 尤其是0-1规划问题， MATLAB 对于整数规划问题，有个专门的求解器 intlinprog。 该函数不仅可以求解一般的整数规划问题，还可以求解混合整数规划问题，也就是决策变量既可以是整数也可以是小数，只要指定是整数的决策变量的编号就是可以。 通过一个具体的例子，
 来看看这个函数的使用。

求解的问题是：




求解的代码是：




运行代码， 可很快得到最优解 x = [1 0 1]。


5. 受欢迎的图形化应用

MATLAB 在数据分析领域如此受欢迎，除了其提供丰富的内置算法集，还有各类友好的应用界面。在优化工具箱中，也有这么一个强大的工具—— Optimization
 App，可以在 MATLAB Apps 窗口或者运行 optmitool 命令打开。它是一个交互式的图形化应用工具，无需手写代码，直接在图形界面中设置各类求解器、配置目标函数、约束条件，即可运行优化算法并使中间结果和最终结果可视化。




在 Optimization App 中，只需点击菜单栏中的 File > Generate Code，即可将 App 中的各项设置自动生成
 MATLAB 代码，用户可实现算法的复用和二次开发。


此外，面对越来越复杂的优化问题，如何加快算法的运行也是我们经常听到的问题。针对这个需求，可以结合 MATLAB 并行计算工具箱，利用电脑的多核硬件资源，实现算法加速，有兴趣的用户可以点击阅读原文观看视频做更多的了解。
                                                
                
                                                

                

                    

       离散型问题是建模竞赛中的主流题型，如果判断所研究的问题是组合优化问题， 那么就大概率需要全局优化算法了。历年赛题中， 比较经典的这类问题有灾情巡视、公交车调度、彩票问题、露天矿卡车调度、交巡警服务平台、太阳影子定位等等。可见全局优化问题的求解算法在数学建模中的重要性，这一讲重要就介绍 MATLAB 全局优化技术及相关实例。

1. MATLAB 全局优化概况

MATLAB 中有个全局优化工具箱 ( Global Optimization Toolbox ) ，该工具箱集成了几个主流的全局优化算法，包含全局搜索、多初始点、模式搜索、遗传算法、多目标遗传算法、模拟退火求解器和粒子群求解器，
 如图 1 所示。对于目标函数或约束函数连续、不连续、随机、导数不存在以及包含仿真或黑箱函数的优化问题，都可使用这些求解器来求解。




图 1 MATLAB 全局优化工具箱包含的求解器

另外，还可通过设置选项和自定义创建、更新函数来改进求解器效率。可以使用自定义数据类型，配合遗传算法和模拟退火求解器，来描绘采用标准数据类型不容易表达的问题。利用混合函数选项，可在第一个求解器之后应用第二个求解器来改进解算。

2. 遗传算法

遗传算法可以说是典型的通过变化解的结构以得到更优解的算法，适应能力比较强，现已经典的旅行商问题（TSP）为例， 来看看如何使用 MATLAB 来实现遗传算法。


旅行商问题的数据


load(’usborder.mat’,‘x’,‘y’,‘xx’,‘yy’);

plot(x,y,‘Color’,‘red’); hold on;

cities = 40;

locations = zeros(cities,2);

n = 1;
while (n <= cities)

    xp = rand*1.5;

    yp = rand;

    if inpolygon(xp,yp,xx,yy)

        locations(n,1) = xp;

        locations(n,2) = yp;

        n = n+1;

    end
end

plot(locations(:,1),locations(:,2),‘bo’);






计算城市间的距离


distances = zeros(cities);

for count1=1:cities

    for count2=1:count1

        x1 = locations(count1,1);

        y1 = locations(count1,2);

        x2 = locations(count2,1);

        y2 = locations(count2,2);

        distances(count1,count2)=sqrt((x1-x2)^2+(y1-y2)^2);

        distances(count2,count1)=distances(count1,count2);

    end
end





定义目标函数


FitnessFcn = @(x) traveling_salesman_fitness(x,distances);



my_plot = @(options,state,flag) traveling_salesman_plot(options, …

    state,flag,locations);



设置优化属性并执行遗传算法求解


options = optimoptions(@ga, ’PopulationType’, ‘custom’,‘InitialPopulationRange’, …

                            [1;cities]);


options = optimoptions(options,‘CreationFcn’,@create_permutations, …

                        ‘CrossoverFcn’,@crossover_permutation, …

                        ‘MutationFcn’,@mutate_permutation, …

                        ‘PlotFcn’, my_plot, …

                        ‘MaxGenerations’,500,‘PopulationSize’,60, …

                        ‘MaxStallGenerations’,200,‘UseVectorized’,true);


numberOfVariables = cities;

[x,fval,reason,output] = …

    ga(FitnessFcn,numberOfVariables,[ ],[ ],[ ],[ ],[ ],[ ],[ ],options);




3. 模拟退火算法


模拟退火（SA）算法也是经典的全局优化算法之一，它脱胎于自然界的物理过程，奇妙地与优化问题挂上了钩。这里将以求解经典的 Peaks 问题为例，介绍如何使用 MATLAB 中的 SA 算法。


用模拟退火(SA)算法求解Peaks问题


clc, clear, close all



定义优化问题


peaks

problem = createOptimProblem(’fmincon’,…

                             ‘objective’,@(x) peaks(x(1),x(2)), …

                             ‘nonlcon’,@circularConstraint,…

                             ‘x0’,[-1 -1],…

                             ‘lb’,[-3 -3],…

                             ‘ub’,[3 3],…

                             ‘options’,optimset(‘OutputFcn’,…

                                                @peaksPlotIterates))



用一般最优算法求解



[x,f] = fmincon(problem)





x =


  
 -1.3474    0.2045

f =

   -3.0498





用 SA 算法寻找全局最小值


problem.solver  = ’simulannealbnd’;

problem.objective = @(x) peaks(x(1),x(2)) + (x(1)^2 + x(2)^2 - 9);

problem.options = saoptimset(’OutputFcn’,@peaksPlotIterates,…

                             ‘Display’,‘iter’,…

                             ‘InitialTemperature’,10,…

                             ‘MaxIter’,300)


[x,f] = simulannealbnd(problem)





x
 =

    0.2280   -1.5229

f =

  -13.0244




4. 全局优化求解器汇总

MATLAB 全局优化算法的各求解器如下表所示。 在建模比赛中， 建议大家先了解各算法的原理， 这样当遇到具体问题的时候， 就可以根据问题的特征判断哪个或哪几个算法比较合适， 如果不好判断， 不妨全部尝试一下， 做个算法比较也是比较常见的事情， 这样得到的结果更酷， 摘要也更有内容啦。




以上只是简单介绍一下建模中常用全局优化算法的MATLAB实现方法，点击阅读原文查看关于更多的MATLAB全局优化技术和MATLAB帮助文档。
                                                
                
                                                

                

                    

   

        最优化赛题是数学建模大赛中最常见的问题类型之一。一般说来，凡是寻求最大、最小、最远、最近、最经济、最丰富、最高效、最耗时的目标，都可以划入优化问题的范畴。MATLAB 优化工具箱和全局优化工具箱对多个优化问题提供了完整的解决方案，前者涵盖了线性规划、混合整型线性规划、二次规划、非线性优化、非线性最小二乘的求解器，后者囊括了全局搜索、多初始点、模式搜索、遗传算法等求解算法。


本讲主要介绍如何使用优化工具箱求解数学建模中标准的优化模型。更多的内容，欢迎大家浏览 MathWorks 官网以及 MATLAB 软件文档。

1.
 聊一聊最优化问题

最优化即在一定的条件下，寻求使目标最小（大）的设计参数或决策。在优化问题中有两个关键对象：目标函数和约束条件（可选）。常规优化问题，其数学表达可以描述为：






其中x 为长度n的决策变量向量，f(x) 为目标函数，G(x) 为约束函数。

求解目标函数的最小（大）值，一个高效而精确的解决方案不仅取决于约束条件和变量数量，更取决于目标函数和约束函数的特性。明确优化类型是确认优化方案的前提，让我们看一下这些特性如何划分：









常见的目标函数有：


线性规划：被广泛的应用于变量之间可线性表示的财务、能源、运营研究等现代管理领域中。

混合整数线性规划：扩展了线性规划问题，增加了最优解中部分或全部变量必须是整数的约束。例如，如果一个变量代表要认购的股票数量，则只应取整数值。同样，如果一个变量代表发电机的开/关状态，则只应取二进制值（0
 或 1）。

二次规划：目标函数或约束函数为多元二次函数。此优化应用于财务金融中投资组合优化、发电厂发电优化、工程中设计优化等领域。

最小二乘：分为线性和非线性，通过最小化误差的平方和寻找变量的最优函数匹配。非线性最小二乘优化还可用于曲线拟合。


2. 优化求解器太多了，怎么选？

对 MATLAB 提供的各类优化问题的算法，我们称之为求解器（Solver）。根据其求解目标，被分为四大组：


极小值优化组：找到目标函数出发点 x0 附近的局部极小值


多目标优化组：找到最小化一组函数的最大值或指定的值


方程求解组：找到非线性方程 f(x) = 0 出发点 x0 附近的解


最小二乘法（曲线拟合）组：最小化平方和

仅优化工具箱就提供了近 20 种求解器，面对如此繁多的选项，用户往往一头雾水。幸好，MATLAB 提供了简单明了的参考工具 —— 优化决策表。可谓一表在手，优化不愁：




上表中*表示算法由全局工具箱提供。此外，多目标优化与方程组求解器并未被此表列举，更多求解器的选择方案，可以点击阅读原文查看。

3. 写出漂亮、高效的代码

确认优化策略后，就可以开工写代码了。下面让我们通过一个例子，了解编写高效优化算法代码的步骤和注意事项。

[题目]

- 目标函数




-  约束函数（所有变量为正）





[解答]

a. 首先，根据题目确认这是一个线性规划问题。而线性规划的通用数学表达式和MATLAB标准形式为：




 创建符合标准格式的A、b、Aeq、beq、lb、ub参数，才可以顺利的运行优化算法。

b. 对于线性规划的优化求解步骤（也适用于其他优化方案），建议如下：

    1 ) 选择优化求解器

    2 ) 将所有变量合并为一个向量

    3 ) 创建边界约束（lb，ub）

    4 ) 创建线性不等式约束（A，b）

    5 ) 创建线性等式约束（Aeq，beq）

    6 ) 创建目标函数

    7 ) 优化问题求解

    8 ) 结果检验

c. MATLAB
 代码和注释：







d. 优化结果：




e. 如果结果不满意，可以调整优化选项，迭代计算。

4. 整数规划求解神器

在优化问题中， 经常会遇到整数规划问题， 尤其是0-1规划问题， MATLAB 对于整数规划问题，有个专门的求解器 intlinprog。 该函数不仅可以求解一般的整数规划问题，还可以求解混合整数规划问题，也就是决策变量既可以是整数也可以是小数，只要指定是整数的决策变量的编号就是可以。 通过一个具体的例子，
 来看看这个函数的使用。

求解的问题是：




求解的代码是：




运行代码， 可很快得到最优解 x = [1 0 1]。


5. 受欢迎的图形化应用

MATLAB 在数据分析领域如此受欢迎，除了其提供丰富的内置算法集，还有各类友好的应用界面。在优化工具箱中，也有这么一个强大的工具—— Optimization
 App，可以在 MATLAB Apps 窗口或者运行 optmitool 命令打开。它是一个交互式的图形化应用工具，无需手写代码，直接在图形界面中设置各类求解器、配置目标函数、约束条件，即可运行优化算法并使中间结果和最终结果可视化。




在 Optimization App 中，只需点击菜单栏中的 File > Generate Code，即可将 App 中的各项设置自动生成
 MATLAB 代码，用户可实现算法的复用和二次开发。


此外，面对越来越复杂的优化问题，如何加快算法的运行也是我们经常听到的问题。针对这个需求，可以结合 MATLAB 并行计算工具箱，利用电脑的多核硬件资源，实现算法加速，有兴趣的用户可以点击阅读原文观看视频做更多的了解。

       离散型问题是建模竞赛中的主流题型，如果判断所研究的问题是组合优化问题， 那么就大概率需要全局优化算法了。历年赛题中， 比较经典的这类问题有灾情巡视、公交车调度、彩票问题、露天矿卡车调度、交巡警服务平台、太阳影子定位等等。可见全局优化问题的求解算法在数学建模中的重要性，这一讲重要就介绍 MATLAB 全局优化技术及相关实例。

1. MATLAB 全局优化概况

MATLAB 中有个全局优化工具箱 ( Global Optimization Toolbox ) ，该工具箱集成了几个主流的全局优化算法，包含全局搜索、多初始点、模式搜索、遗传算法、多目标遗传算法、模拟退火求解器和粒子群求解器，
 如图 1 所示。对于目标函数或约束函数连续、不连续、随机、导数不存在以及包含仿真或黑箱函数的优化问题，都可使用这些求解器来求解。




图 1 MATLAB 全局优化工具箱包含的求解器

另外，还可通过设置选项和自定义创建、更新函数来改进求解器效率。可以使用自定义数据类型，配合遗传算法和模拟退火求解器，来描绘采用标准数据类型不容易表达的问题。利用混合函数选项，可在第一个求解器之后应用第二个求解器来改进解算。

2. 遗传算法

遗传算法可以说是典型的通过变化解的结构以得到更优解的算法，适应能力比较强，现已经典的旅行商问题（TSP）为例， 来看看如何使用 MATLAB 来实现遗传算法。


旅行商问题的数据


load('usborder.mat','x','y','xx','yy');

plot(x,y,'Color','red'); hold on;

cities = 40;

locations = zeros(cities,2);

n = 1;
while (n <= cities)

    xp = rand*1.5;

    yp = rand;

    if inpolygon(xp,yp,xx,yy)

        locations(n,1) = xp;

        locations(n,2) = yp;

        n = n+1;

    end
end

plot(locations(:,1),locations(:,2),'bo');






计算城市间的距离


distances = zeros(cities);

for count1=1:cities

    for count2=1:count1

        x1 = locations(count1,1);

        y1 = locations(count1,2);

        x2 = locations(count2,1);

        y2 = locations(count2,2);

        distances(count1,count2)=sqrt((x1-x2)^2+(y1-y2)^2);

        distances(count2,count1)=distances(count1,count2);

    end
end





定义目标函数


FitnessFcn = @(x) traveling_salesman_fitness(x,distances);



my_plot = @(options,state,flag) traveling_salesman_plot(options, ...

    state,flag,locations);



设置优化属性并执行遗传算法求解


options = optimoptions(@ga, 'PopulationType', 'custom','InitialPopulationRange', ...

                            [1;cities]);


options = optimoptions(options,'CreationFcn',@create_permutations, ...

                        'CrossoverFcn',@crossover_permutation, ...

                        'MutationFcn',@mutate_permutation, ...

                        'PlotFcn', my_plot, ...

                        'MaxGenerations',500,'PopulationSize',60, ...

                        'MaxStallGenerations',200,'UseVectorized',true);


numberOfVariables = cities;

[x,fval,reason,output] = ...

    ga(FitnessFcn,numberOfVariables,[ ],[ ],[ ],[ ],[ ],[ ],[ ],options);




3. 模拟退火算法


模拟退火（SA）算法也是经典的全局优化算法之一，它脱胎于自然界的物理过程，奇妙地与优化问题挂上了钩。这里将以求解经典的 Peaks 问题为例，介绍如何使用 MATLAB 中的 SA 算法。


用模拟退火(SA)算法求解Peaks问题


clc, clear, close all



定义优化问题


peaks

problem = createOptimProblem('fmincon',...

                             'objective',@(x) peaks(x(1),x(2)), ...

                             'nonlcon',@circularConstraint,...

                             'x0',[-1 -1],...

                             'lb',[-3 -3],...

                             'ub',[3 3],...

                             'options',optimset('OutputFcn',...

                                                @peaksPlotIterates))



用一般最优算法求解



[x,f] = fmincon(problem)





x =


  
 -1.3474    0.2045

f =

   -3.0498





用 SA 算法寻找全局最小值


problem.solver  = 'simulannealbnd';

problem.objective = @(x) peaks(x(1),x(2)) + (x(1)^2 + x(2)^2 - 9);

problem.options = saoptimset('OutputFcn',@peaksPlotIterates,...

                             'Display','iter',...

                             'InitialTemperature',10,...

                             'MaxIter',300)


[x,f] = simulannealbnd(problem)





x
 =

    0.2280   -1.5229

f =

  -13.0244




4. 全局优化求解器汇总

MATLAB 全局优化算法的各求解器如下表所示。 在建模比赛中， 建议大家先了解各算法的原理， 这样当遇到具体问题的时候， 就可以根据问题的特征判断哪个或哪几个算法比较合适， 如果不好判断， 不妨全部尝试一下， 做个算法比较也是比较常见的事情， 这样得到的结果更酷， 摘要也更有内容啦。




以上只是简单介绍一下建模中常用全局优化算法的MATLAB实现方法，点击阅读原文查看关于更多的MATLAB全局优化技术和MATLAB帮助文档。