﻿ 数学建模实验中三种优化模型的分析

# 数学建模实验中三种优化模型的分析The Analysis of Three Optimal Models in Mathematical Modeling Experiment

Abstract: The mathematical modeling, the model of the mathematical common sense of the real problem, obtains the optimal decision plan. In these practical problems, for example, the production plan of the factory, the reasonable use of the material topic, which can create the optimization model. And then we solve it in an optimal way find the optimal decision. They are different in different ways. This paper presents three commonly used optimization models; Linear programming, nonlinear programming, and integer programming model. Some examples are given in detail.

1. 引言

2. 优化模型

2.1. 线性规划模型

2.1.1. 数学表示

$\begin{array}{l}\mathrm{min}f={c}_{1}{x}_{1}+{c}_{2}{x}_{2}+\cdots +{c}_{n}{x}_{n}\\ s.t.\left\{\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}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}⋮\\ {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)

$\begin{array}{l}\mathrm{min}f={C}^{\text{T}}X\\ s.t.\left\{\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×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}}$ 为决策向量。

2.1.2. MATLAB实现

$\begin{array}{l}\mathrm{min}{f}^{\text{T}}x\\ s.t.\left\{\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)

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

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

2) $\left[x,fval\right]=\left(f,A,b,Aeq,beq\right)$ ，解线性规划题目的 $\mathrm{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)$ ，求解线性规划题目的 $\mathrm{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)$ ，求该题的 $\mathrm{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)$ ，求该题的 $\mathrm{min}{f}^{\text{T}}x$ ，也有前提是 $A\ast x\le b$ ，以及 $Aeq\ast x=beq$ ，同样有上下界和初始值 ${x}_{0}$ ，不同的是用 $options$ 使指定的参数到达最小化，同时执行上一环中的最后一步。

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

2.1.3. 运输问题

$\mathrm{max}\text{}6{x}_{1}+5{x}_{2}$

$s.t.\text{}\left\{\begin{array}{c}5{x}_{1}+3{x}_{2}\le 100\\ 6{x}_{1}+7{x}_{2}\le 160\\ 5{x}_{2}\le 180\\ x,{x}_{2}\ge 0\end{array}\text{}$ (4)

$\mathrm{min}\text{}-6{x}_{1}-5{x}_{2}$

$s.t.\text{}\left\{\begin{array}{c}5{x}_{1}+3{x}_{2}\le 100\\ 6{x}_{1}+7{x}_{2}\le 160\\ 5{x}_{2}\le 180\\ x,{x}_{2}\ge 0\end{array}\text{}$ (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,\text{\hspace{0.17em}}\square ,\text{\hspace{0.17em}}\square ,\text{\hspace{0.17em}}lb\right)$

$x=$

$12.9412$

$11.7647$ (7)

$fval=$

$-136.4706$

2.2. 整数规划模型

2.2.1. 数学表示

$\begin{array}{l}\mathrm{max}\left(或\mathrm{min}\right)z=\underset{j=1}{\overset{n}{\sum }}{c}_{j}{x}_{j}\\ s.t.\left\{\begin{array}{l}\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实现

2.2.3. 限制问题

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

» $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,\text{\hspace{0.17em}}\square ,\text{\hspace{0.17em}}\square ,\text{\hspace{0.17em}}lb\right)$

$x=$

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

$fval=$

$8.6667$

Table 1. The material consumption and purchase price of A, B two kinds materials

1) 先考虑 ${x}_{1}\le 3$ 的部分，即求解

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

» $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,\text{\hspace{0.17em}}\square ,\text{\hspace{0.17em}}\square ,\text{\hspace{0.17em}}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}\mathrm{min}z={x}_{1}+4{x}_{2}\\ s.t.\left\{\begin{array}{l}2{x}_{1}+{x}_{2}\le 8\hfill \\ {x}_{1}+2{x}_{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)

» $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,\text{\hspace{0.17em}}\square ,\text{\hspace{0.17em}}\square ,\text{\hspace{0.17em}}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}\mathrm{min}z={x}_{1}+4{x}_{2}\\ s.t.\left\{\begin{array}{l}2{x}_{1}+{x}_{2}\le 8\hfill \\ {x}_{1}+2{x}_{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)

» $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,\text{\hspace{0.17em}}\square ,\text{\hspace{0.17em}}\square ,\text{\hspace{0.17em}}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. 数学表示

$\begin{array}{l}\mathrm{min}\left(或\mathrm{max}\right)f\left({x}_{1},{x}_{2},\cdots ,{x}_{n}\right)\\ s.t.\left\{\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实现

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

$\left[x,fval\right]=f\mathrm{min}bnd\left(fun,{x}_{1},{x}_{2}\right)$ ，返回区间上最小解 $x$ 及解 $x$ 处的所求函数值。

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

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

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

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

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

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

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

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

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

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

4) 参数说明

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

$functionf=myfun\left( x \right)$

$f=...$

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

5) 注意事项

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

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

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

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

2.3.3. 工程应用实例

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

1) MATLAB求解程序清单一：

» $\left[x,fval\right]=f\mathrm{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求解程序清单二：

$functionf=myfun\left( x \right)$

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

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

$x=$

$0.8333$ (26)

$fval=$

$-9.2593$

[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.

Top