DOI:10.12677/PM.2018.81009,PDF,HTML,XML,被引量下载: 2,186浏览: 13,972
作者:王小春^*：太原师范学院数学系，山西 晋中
关键词:最优化模型；线性规划模型；非线性规划模型；整数规划模型；Optimization Model；Linear Programming Model；Nolinear Programming Model；Integer Programming Model

文章引用：王小春. 数学建模实验中三种优化模型的分析[J]. 理论数学, 2018, 8(1): 55-63. https://doi.org/10.12677/PM.2018.81009

1. 引言

在20世纪中期，数学建模 [1] 就在欧美国度首次被发现，而在中国的呈现稍晚些，但是大约在80年代初始咱们国家也就有了。它的核心即是创立数学模型 [2] ，使得问题获得最优化的解决。而数学建模最关键而又最难的是模型的建立。建造模型是一种创作，成功的模型往往是科技和创作的结果。

在建模前就要做一些准备工作，比如：认识须要处理题目的现实状态以及现实成果，尽可能多的了解处理东西的种种相关知识；接着用数学思想来分析问题的最本质的内在联系，把数学思维与问题的全过程充分结合；最后用数学语言的形式来描述具体问题，并且所描述的结果有具体的要求；首先是符合数学理论和习惯，其次是清晰准确。

本文主要罗列了三的优化方法：线性、非线性 [3] 以及整数规划模型 [4] 。并通过一些实例详细说明。

2. 优化模型

最优化方法 [5] ，也称做运筹学方法，是数学的一个分支，是上世纪二次大战前后慢慢累积成的一门学科。最优化方法最核心的内容是通过运用数学方法来对各种系统的优化途径以及方案进行研究，为决策者提供科学决策依据，以便做出合理科学的决策。

从数学角度上来说，最优化方法的本质就是一种求极值的方法，具体的说就是在一组约束条件为等式或者不等式的情形下，使得系统的目标函数要么达到最大值，要么达到最小值。常用的优化方法有线性、非线性以及整数规划模型。

2.1. 线性规划模型

线性规划 [6] 是探究由线性等式或不等式构成的约束条件下的极值题目，可以解决种种规划、出产、运输等科学解决与工程范畴方面的问题。它的主要算法是单纯形法。

线性规划问题的特点：第一，题目都是用代表性的变量表现一个方案，这组代表性变量的值就代表详细的方案，这些变量的取值是不能为负数的。第二，存在必然的约束前提，该前提可以用线性函数来表现。第三，都有一个要求到达的目标，他可以用决策变量的线性函数来表现，这个函数称为目标函数，按题目的差别，要求目标函数实现最大化或者最小化。下面，通过几个例子来说明一下。

2.1.1. 数学表示

在线性规划的一般形式中，有n个变化的量，m个约束前提，这个前提是等式，变化的量非负，要求函数的最小值，这个表达式为：

$\begin{array}{l}\min f=c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n\\ s.t.\{\begin{array}{l}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n=b_1\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n=b_2\\ ⋮\\ a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n=b_m\\ x_1,x_2,\cdots ,x_n\ge 0;b_i\ge 0\left(i=1,2,\cdots ,m\right)\end{array}\end{array}$(1)

在这个表达式中，满足各约束前提的右端项 $b_i\ge 0$，不然两边乘以“−1”，可简写为

$\begin{array}{l}\min f=C^{\text{T}}X\\ s.t.\{\begin{array}{l}AX=B\\ x_i,b_j\ge 0\left(i=1,2,\cdots ,n;j=1,2,\cdots ,m\right)\end{array}\end{array}$(2)

$A={\left(a_{ij}\right)}_{m\times n}$约束前提的系数矩阵，一般 $n\ge m>0$， $C={\left(c_1,c_2,\cdots ,c_n\right)}^{\text{T}}$为价值向量， $B={\left(b_1,b_2,\cdots ,b_m\right)}^{\text{T}}$称为资源向量， $X={\left(x_1,x_2,\cdots ,x_n\right)}^{\text{T}}$为决策向量。

知道了标准型之后，任意一个形式的数学模型都可以转化为标准型来求解 [7] 。

2.1.2. MATLAB实现

这个模型的MATLAB命令是linprog，假设该规划题目的数学模型 [8] 为

$\begin{array}{l}\min f^{\text{T}}x\\ s.t.\{\begin{array}{l}A\ast x\le b\hfill \\ Aeq\ast x=beq\hfill \\ lb\le x\le ub\hfill \end{array}\end{array}$(3)

式中， $f,x,b,beq,lb$和 $ub$为向量， $A$和 $Aeq$为矩阵。这里，须要指出的是，MATLAB中给的量和矩阵的值是从上往下进行的，行中间用“;”离隔每行元素可用“，”也可用空格，矩阵右上角用“’”表现转置运算。

Linprog函数 [9] 的调用格式如下：

1) $\left[x,fval\right]=linprog\left(f,A,b\right)$，解线性规划题目的 $\min f^{\text{T}}x$，前提为 $A\ast x\le b$，返回解 $x$处所要求解的值 $fval$。

2) $\left[x,fval\right]=\left(f,A,b,Aeq,beq\right)$，解线性规划题目的 $\min f^{\text{T}}x$，前提为 $A\ast x\le b$，但增加了一个前提，即 $Aeq\ast x=beq$；若不等式不存在，则令A = ,、b = ,，同时返回解 $x$处的目标函数值 $fval$。

3) $\left[x,fval\right]=linprog\left(f,A,b,Aeq,beq,lb,ub\right)$，求解线性规划题目的 $\min f^{\text{T}}x$，约束前提为 $A\ast x\le b$及 $Aeq\ast x=beq$，并定义变量 $x$lb(下界)和ub(上界)，使 $x$一直在该范畴内，若不存在，则令A = ,、B = ,，即令返回解 $x$处的所求函数值 $fval$。

4) $\left[x,fval\right]=linprog\left(f,A,b,Aeq,beq,lb,ub,x_0\right)$，求该题的 $\min f^{\text{T}}x$，有一个前提是 $A\ast x\le b$，和 $Aeq\ast x=beq$，同样也有下界和上界，有一个初始 $x_0$，同时执行上一环中的最后一步。

5) $\left[x,fval\right]=linprog\left(f,A,b,Aeq,beq,lb,ub,x_0,options\right)$，求该题的 $\min f^{\text{T}}x$，也有前提是 $A\ast x\le b$，以及 $Aeq\ast x=beq$，同样有上下界和初始值 $x_0$，不同的是用 $options$使指定的参数到达最小化，同时执行上一环中的最后一步。

6) $x=linprog\left(\mathrm{...}\right)$，仅输出解 $x$的值，不输出所求的函数值 $fval$。

2.1.3. 运输问题

某工场出产甲、乙两种产物，有要求：1 kg产物甲须要用材料A 5 kg，材料B 6 kg；生产1 kg产物乙需要材料A 3 kg，材料B 7 kg，材料C 5 kg。若1 kg产物甲和乙的价钱划分为6万和5万，三种材料的限制分别为100 kg、160 kg、180 kg。试求出使得总销售达到最高的方法？

解：令出产产物甲的数目为 $x_1$，出产产物乙的数目为 $x_2$，由要求可得模型：

$\max 6x_1+5x_2$

$s.t.\{\begin{array}{c}5x_1+3x_2\le 100\\ 6x_1+7x_2\le 160\\ 5x_2\le 180\\ x,x_2\ge 0\end{array}$(4)

这个题目要使所求的函数值达到最大，则根据MATLAB的标准 [10] 进行转化，即让所求函数最小，即：

$\min -6x_1-5x_2$

$s.t.\{\begin{array}{c}5x_1+3x_2\le 100\\ 6x_1+7x_2\le 160\\ 5x_2\le 180\\ x,x_2\ge 0\end{array}$(5)

MATLAB求解程序清单为：

» $f={\left[-6,-5\right]}^{\prime }$

$A={\left[5,3;6,7;0,5\right]}^{\prime }$；

$b={\left[100,160,180\right]}^{\prime }$；(6)

$lb={\left[0,0\right]}^{\prime }$；

$\left[x,fval\right]=linprog\left(f,A,b,\square ,\square ,lb\right)$

结果输出为：

$x=$

$12.9412$

$11.7647$(7)

$fval=$

$-136.4706$

说明生产产品甲、乙的数量分别为12.9 kg、11.76 kg时，创造的最高总售价为136.47万元。

2.2. 整数规划模型

在之前所说的线性题目中，有时候解是分数有时候却是小数，也有时会出现针对一些的题目要求解不能是上述情况(称为整数解)。例如，要求机器的台数、工场的人数或卸货的车辆数等。通常称这种题目为整数规划(Integer Programming)，简称IP，它是规划论中的一个分支。

该规划中，全部的量均取整数时就叫做纯整数规划(Pure Integer Programming)；部分变化的量取整数的称混合整数规划 [11] (Mixed Integer Programming)；变化的量只取0或1两种值的规划称为0--1规划。

2.2.1. 数学表示

$\begin{array}{l}\max \left(或\min \right)z={\displaystyle \underset{j=1}{\overset{n}{\sum }}{c}_j{x}_j}\\ s.t.\{\begin{array}{l}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{a}_{ij}{x}_{ij}\le \left(=,\ge \right)b_i\left(i=1,2,\cdots ,m\right)}\\ x_j\ge 0\left(j=1,2,\cdots ,n\right)\\ x_1,x_2,\cdots ,x_n中部分或全部取整数\end{array}\end{array}$(8)

2.2.2. MATLAB实现

由于整数规划的解法有很多，所以，用MATLAB实现的方法也有很多，下面将会结合具体的事例来阐述。

2.2.3. 限制问题

某工场打算要出产甲、乙两种衣服，得知制作甲、乙衣服须要耗损A、B两种材料，A、B两种材料的耗损以及进价按下表1所示：(A最多只能用8 m，B最少要用6 m)

试问：工厂应分别生产多少件甲、乙，才能使得所花的钱最少？

解：设工厂应分别生产甲、乙种衣服 $x_1,x_2$件，根据题意建立如下数学模型：

$\begin{array}{l}\min z=x_1+4x_2\\ s.t.\{\begin{array}{l}2x_1+x_2\le 8\hfill \\ x_1+2x_2\ge 6\hfill \\ x_1,x_2\ge 0且为整数\hfill \end{array}\end{array}$(9)

在MATLAB命令 [12] 窗口输入：

» $f={\left[1,4\right]}^{\prime }$；

$A=\left[2,1;-1,-2\right]$；

$b=\left[8,-6\right]$；(10)

$lb=\left[0,0\right]$；

$\left[x,fval\right]=linprog\left(f,A,b,\square ,\square ,lb\right)$

结果输出为：

$x=$

$\begin{array}{l}3.3333\\ 1.3333\end{array}$(11)

$fval=$

$8.6667$

不符合题意，确定分支 $x_1\le 3$和 $x_1\le 3$两部分。

表1. A、B两种材料的耗损和进价

1) 先考虑 $x_1\le 3$的部分，即求解

$\begin{array}{l}\min z=x_1+4x_2\\ s.t.\{\begin{array}{l}2x_1+x_2\le 8\hfill \\ x_1+2x_2\ge 6\hfill \\ x_1\le 3\hfill \\ x_1,x_2\ge 0且为整数\hfill \end{array}\end{array}$(12)

在MATLAB命令窗口中输入

» $f={\left[1,4\right]}^{\prime }$;

$A=\left[2,1;-1,-2;1,0\right]$;

$b=\left[8,-6,3\right]$；(13)

$lb=\left[0,0\right]$；

$\left[x,fval\right]=linprog\left(f,A,b,\square ,\square ,lb\right)$

结果为：

$x=$

$\begin{array}{l}3.0000\\ 1.5000\end{array}$(14)

$fval=$

$9.0000$

仍然不满足全部为整数解的要求。

2) 考察分支 $x_1\le 3$，再加上限制 $x_2\le 1$，求解

$\begin{array}{l}\min z=x_1+4x_2\\ s.t.\{\begin{array}{l}2x_1+x_2\le 8\hfill \\ x_1+2x_2\ge 6\hfill \\ x_1\le 3\hfill \\ x_2\le 1\hfill \\ x_1,x_2\ge 0且为整数\hfill \end{array}\end{array}$(15)

在MATLAB命令窗口中输入：

» $f={\left[1,4\right]}^{\prime }$；

$A=\left[2,1;-1,-2;1,0;0,1\right]$;

$b=\left[8,-6,3,1\right]$;(16)

$lb=\left[0,0\right]$；

$\left[x,fval\right]=linprog\left(f,A,b,\square ,\square ,lb\right)$

结果出现错误信息提示，但仍输出为：

$x=$

$\begin{array}{l}3.0000\\ 1.5000\end{array}$(17)

$fval=$

$9.0000$

因为有信息错误，说明该解有问题，而且也不符合整数解要求，继续求解：

3) 考察分支 $x_1\le 3$和 $x_2\ge 2$，即求解

$\begin{array}{l}\min z=x_1+4x_2\\ s.t.\{\begin{array}{l}2x_1+x_2\le 8\hfill \\ x_1+2x_2\ge 6\hfill \\ x_1\le 3\hfill \\ x_2\ge 2\hfill \\ x_1,x_2\ge 0且为整数\hfill \end{array}\end{array}$(18)

在MATLAB命令窗口中输入：

» $f={\left[1,4\right]}^{\prime }$；

$A=\left[2,1;-1,-2;1,0;0,1\right]$;

$b=\left[8,-6,3,-2\right]$;(19)

$lb=\left[0,0\right]$;

$\left[x,fval\right]=linprog\left(f,A,b,\square ,\square ,lb\right)$

结果出现错误信息提示，但仍输出为：

$x=$

$\begin{array}{l}2.0000\\ 2.0000\end{array}$(20)

$fval=$

$10.0000$

此时，解全部为整数，但是否为最优解尚需对其他没有考察的分支进行进一步的计算，最后得到结论，即

$x_1^{\ast }=x_2^{\ast }=2,z^{\ast }=10$(21)

2.3. 非线性规划模型

之前所说的这两种规划的目标函数和约束前提中，函数均为线性的，但在现实中另有大量的题目，其目标函数或约束前提很难用线性来表达，其中包括了很多的非线性函数，则称这种规划为非线性规划问题。

2.3.1. 数学表示

实际中所碰到的题目多半是非线性的，其数学表达式 [13] 为：

$\begin{array}{l}\min \left(或\max \right)f\left(x_1,x_2,\cdots ,x_n\right)\\ s.t.\{\begin{array}{l}g\left(x_1,x_2,\cdots ,x_n\right)\ge \left(=,\le 0\right)\hfill \\ x_j\ge 0\hfill \\ i=1,2,\cdots ,m\hfill \\ j=1,2,\cdots ,n\hfill \end{array}\end{array}$(22)

2.3.2. MATLAB实现

当要求的变量只有一个，且没有约束的限制时，常用到的MATLAB函数为 $f\min bnd$、 $f\min search$、 $f\min unc$，用于求多变量无约束非线性规划的MATLAB函数为 $f\min search$、 $f\min unc$。

1) $f\min bnd$命令用 $f\min bnd$可求区间 $\left[x_1,x_2\right]$内单变量函数的最小值，工程应用中常用的格式如下：

① $\left[x,fval\right]=f\min bnd\left(fun,x_1,x_2\right)$，返回区间上最小解 $x$及解 $x$处的所求函数值。

② $\left[x,fval\right]=f\min bnd\left(fun,x_1,x_2,options\right)$，采用 $options$参数指定的优化参数进行最小化，若没有设置 $options$选项，可令 $options=\square$，同时返回最小解 $x$及解 $x$处的目标函数值。

③ $x=f\min bnd\left(\mathrm{...}\right)$，仅返回解 $x$的数值，不返回目标函数值。

2) $f\min unc$命令利用 $f\min unc$可求解单变量及多变量函数的最小值，工程中常用的格式如下：

① $\left[x,fval\right]=f\min unc\left(fun,x_0\right)$，给定初始值 $x_0$，返回所求函数极小值 $x$和所求函数值。

② $\left[x,fval\right]=f\min unc\left(fun,x_0,options\right)$，给定初始值 $x_0$，用 $options$参数指定的优化参数进行最小化，若没有设置 $options$选项，可令 $options=\square$，同时返回目标函数的极小值 $x$和目标函数值。

③ $x=f\min unc\left(\mathrm{...}\right)$，仅返回解 $x$的数值，不返回目标函数值。

3) $f\min search$命令利用 $f\min search$可求的问题和 $f\min unc$一样，工程中常用的格式如下：

① $\left[x,fval\right]=f\min search\left(fun,x_0\right)$，给定值 $x_0$，返回所求函数极小值和所求函数值。

② $\left[x,fval\right]=f\min search\left(fun,x_0,options\right)$，给定初始值 $x_0$，用 $options$参数指定的优化参数进行最小化，若没有设置 $options$选项，可令 $options=\square$，同时返回目标函数的极小值 $x$和目标函数值。

③ $x=f\min search\left(\mathrm{...}\right)$。仅返回解 $x$的数值，不返回目标函数值。

4) 参数说明

① $fun$为目标函数，若对应的函数采用 $M$文件表示，即 $fun=\text{'}myfun\text{'}$，则 $myfun.m$必须采用下面的形式，即

$functionf=myfun(\; x\; )$

$f=\mathrm{...}$

② $$，为优化参数选项，可以通过 $optimset$函数设置或改变这些参数。

5) 注意事项

① 三个函数均可能只输出局部最优解。

② 三个函数均只对变量为实数的题目进行优化。

③ $f\min bnd$函数和 $f\min unc$函数要求目标函数必需连续。

④ 若变量为复数，对于 $f\min unc$函数和 $f\min search$函数来说，需将相应的复数分为实部和虚部两部分分别进行优化计算。

2.3.3. 工程应用实例

某工场有个边长为5 m的正方形铁板，欲制成一个方形无盖水槽，问在它的4个角处剪去多长时，能使水槽的容纳的水最多?

解：设裁去的正方形的边长为 $x$，则水槽的容积为 $f\left(x\right)={\left(5-2x\right)}^{2}x$，分析可知，裁去的正方形的边长不超过2.5 m，即 $x$位于区间 $\left(0,2.5\right)$上。现要求确定该区间上的一个 $x$，使 $f\left(x\right)$到达最大，根据MATLAB的要求，将目标函数最小化，即获得如下函数模型 [14] ：

$\min -f\left(x\right)=-{\left(5-2x\right)}^{2}x$

1) MATLAB求解程序清单一：

» $\left[x,fval\right]=f\min bnd\left(\text{'}-{\left(5-2\ast x\right)}^{^}2\ast x\text{'},0,2.5\right)$(23)

结果输出为：

$x=$

$0.8333$(24)

$fval=$

$-9.2593$

2) MATLAB求解程序清单二：

首先，在 $M-file$ $editor$中编写如下 $M$文件：

$functionf=myfun(\; x\; )$

$f=-{\left(5-2x\right)}^{^}2\ast x$;(25)

以文件名字 $myfun3\_1$存在MATLAB目次下的work文件夹中。然后，在MATLAB命令窗口中调用 $f\min bnd$函数：

» $\left[x,fval\right]=f\min bnd\left(\text{'}myfun3\_1\text{'},0,2.5\right)$

结果同样输出为：

$x=$

$0.8333$(26)

$fval=$

$-9.2593$

可见，减掉正方形的边长为0.8333 m时，水槽能容纳的水最多，且最多为9.2593 m³。

这篇文章主要总结了数学建模中的优化模型，将常用的优化模型分为了三类：线性规划、整数规划以及非线性规划模型。分成了四大部分来罗列这三种模型，第一，先总结模型的概念，第二，模型一般的表达式，第三模型在MATLAB中的实现，最后，结合实例建立了模型并且用MATLAB求解出最优结果。

参考文献

[1]	杨桂元, 李天胜, 徐军. 数学建模应用实例[M]. 合肥: 合肥工业大学出版社, 2007.
[2]	陈怀琛, 龚杰民. 线性代数实践及MATLAB入门[M]. 北京: 电子工业出版社, 2009.
[3]	章绍辉. 数学建模[M]. 北京: 科学出版社, 2011.
[4]	姚泽清, 郑旭东, 赵颖. 全国大学生数学建模竞赛题与优秀论文评析[M]. 北京: 国防工业出版社, 2012.
[5]	《运筹学》教材编写组. 运筹学(修订版) [M]. 北京: 清华大学出版社, 1990.
[6]	姜启源. 数学模型(第二版) [M]. 北京: 高等教育出版社, 1993.
[7]	王沫然. MATLAB 5.X与科学计算[M]. 北京: 清华大学出版社, 2000.
[8]	吴翊, 吴梦达, 成礼智. 数学建模的理论与实践[M]. 长沙: 国防科技大学出版社, 1999.
[9]	谢金星, 薛毅. 优化建模与LINDO/LINGO软件[J]. 北京: 清华大学出版社, 2005.
[10]	张宜华. 精通MATLAB5 [M]. 北京: 清华大学出版社, 2000.
[11]	唐焕文, 贺明峰, 编. 数学模型引论(第二版) [J]. 北京: 高等教育出版社, 2002.
[12]	陈桂明, 戚红雨, 潘伟. MATLAB数理统计(6.X) [M]. 北京: 科学出版社, 2002.
[13]	陈理荣. 数学建模导论[J]. 北京: 北京邮电大学出版社, 1999.
[14]	李火林, 等. 数学模型及方法[M]. 南昌: 江西高校出版社, 1997.