数学建模笔记（姜启源）

线性规划

定义：在一组线性条件限制下，求一线性目标函数最大或最小的问题
标准的matlab形式：$min f^T x,$ $s.t. \begin{cases} A\cdot x \le b\\ Aeq \cdot x = beq \\ lb \le x \le ub \end{cases}$ 其中$f,x,b,beq,lb,u$为列向量，$A，Aeq$为矩阵
matlab相关求解命令为 $[x,val]=linprog(f,A,b,Aeq,beq,lb,ub)$

整数规划

定义：数学规划中的变量（部分或全部）限制为整数时，称为整数规划
分类：根据变量整数是部分还是全部可分为纯整数规划和混合整数规划
求解方法：
1. 分支定界法（纯或混）
2. 割平面法（纯或混）
3. 隐枚举法（01规划）
  - 过滤隐枚举法
  - 分支隐枚举法
4. 匈牙利法（指派问题）
5. 蒙特卡洛法（各种类型）

0-1型整数规划

定义：整数规划的一种特殊情况，变量仅取值0或1 应用范围可分为以下几种情况

相互排斥的约束条件

也就是说题目中的某一种条件只有一个量，如果给了这个1，同类的都为0，较为典型的问题有运输问题，只用一种方式运输，用火车运了，其他的运输栏都为0，其约束条件可进一步简化为 $y_i=\begin{cases} 1,第i个元素起约束作用\\ 0,第i个元素不起作用，i=1,2.....,m\\ \end{cases}$ $a_{i1}x_1+...a_{in}x_nb_i+(1-y_i)M,i=1,2...,m,\ y_1++y_m=1 $ 由约束条件很容易看出，当$y_i$等于1,就只有这个约束起作用，其他的都是多余的

固定费用的问题

在讨论线性规划时，有些问题要求固定费用，这种问题可以通过改变为混合整数规划来解决，数学模型可表示为 $y_i\epsilon\le x_i\le y_i M$ 其中$\epsilon$为充分小的正常数；M为充分大的正常数，表明$x_i>0$时，$y_i$必须为1，$x_i=0$时$y_i$必须为0 $【x_i】$表示采用i方式生产时产量，$y_i$表示是否用第i种方式生产

指派问题

指派问题描述的是分配n个人去做n件事情，每个人做且仅做一件事情，且分配第i个人去做第j件事情，花费$C_{ij}$单位时间，求如何分配使总时间最小，这类问题的关键就是要求出分配矩阵，数学形式可表现为 $x_{ij}=\begin{cases} 1,第i人做第j项工作\\ 0,第i人做第j项工作\\ \end{cases}$ 数学模型为：$min \sum_{i=1}^N \sum_{j=1}^N c_{ij}x_{ij}$ $s.t. \begin{cases} \sum_{i=1}^N x_{ij}=1,i=1,2,...,n\\ \sum_{j=1}^N x_{ij}=1,j=1,2,...,n\\ x_{ij}=0 or 1,i,j=1,...,n \end{cases}$

蒙特卡洛法（随机取样法）

又被称为计算机随机模拟法，它是基于对大量数据的统计结果来实现一些确定性问题的计算
使用该方法必须使用计算机生成相关分布的随机数

整数线性规划的计算机求解

整数规划的求解用Lingo等专用软件比较方便，对于整数线性规划也可以用matlab的intlinprog函数求解，但其的缺点是必须把所有的决策变量化为一维决策变量，变量替换后，约束条件很难写出，最好用lingo
matlab求解混合整数线性规划的命令是
1
【x,fval】=intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
对应以下数学模型 $min_x f^Tx,$ $s.t. \begin{cases} x(intcon)为整数\\ A \cdot x \le b,\\ Aeq \cdot x =beq,\\ lb \le x \le ub \\ \end{cases}$ 式中：$f,x,intcon,b,beq,lb,ub为列向量；A，Aeq为矩阵$

非线性规划

非线性规划模型

定义：如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题
通过投资决策问题归纳非线性规划数学模型的一般形式总资金A元，投资第i个项目花$a_i$元，预计可收益$b_i$元选择最佳投资方案投资决策变量 $x_i=\begin{cases} 1,决定投资第i个项目\\ 0,决定不投资第i个项目\\ \end{cases}$ 则该模型可用下列数学模型表示 $max\, Q = \frac{\sum_{i=1}^n b_i x_i} {\sum_{i=1}^n a_i x_i} s.t. \begin{cases} 0 < \sum_{i=1}^n a_i x_i \le A ,\\ x_i(1-x_i)=0,i=1,...,n\\ \end{cases}$
根据2中例题，非线性规划问题可进一步概括为： $min\,f(x)\\ s.t. \begin{cases} h_j(x)\le0,j=1,2,...,q\\ g_i(x)=0,i=1,2,...,p\\ \end{cases}$ 其中$x=[x_1,...,x_n]^T$为模型的决策变量，$f$为目标函数，$g_i和h_j$为约束函数，$g_i(x)=0$为等式约束，$h_j(x)\le0$为不等式约束
对一个实际问题，要将其规为非线性规划问题时，一般要注意以下几点
1. 确定供选方案
2. 提出追求目标
3. 给出价值标准
4. 寻求限制条件
线性规划与非线性规划的区别：线性规划最优解只能在可行域的边界上达到（特别是顶点），而非线性规划最优解可在可行域任一点达到

非线性规划的matlab表示 $minf(x)\\ s.t. \begin{cases} A\cdot x \le b,\\ Aeq \cdot x=beq,\\ c(x)\le0\\ ceq(x)=0,\\ lb\le x \le ub \end{cases}$ 式中的$f(x)$为标量函数，$A,b,Aeq,beq,lb,ub$为相应维数的矩阵和向量，$c(x),ceq(x)$为非线性向量函数 matlab命令为

1
2
3

[x,fval]=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)
# x返回决策变量x的取值，fval返回目标函数取值，fun是M文件自定义函数f(x),x0是x的初始值
nonlcon是用M文件定义的c(x)ceq(x)，options定义优化参数

### 无约束问题的Matlab解法

在matlab工具箱中，用于求无约束极小值的函数有fminunc和fminsearch，用法分别为

1 2	[x,fval]=fminunc(fun,x0,options) [x,fval]=fminsearch(fun,x0,options) #只能求初始值附近的一个极小值点

约束极值问题

定义：带有约束条件的极值问题，也叫规划问题

二次规划

定义：若某非线性规划的目标函数为自变量x的二次函数，约束条件又全为线性的，称这种规划为二次规划
Matlab中二次规划的数学模型可表述为 $min, x^THx+fTx,\ s.t. \[\begin{cases} Ax\le b\\ Aeq \cdot x=beq,\\ lb\le x\le ub \end{cases}\] H为实对称矩阵，\ $ matlab求解二次规划的命令为
1
[x,fval]=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)

罚函数法

利用罚函数法可以将非线性规划问题的求解转化为求一系列无约束极值的问题，也把这种方法叫做序列无约束最小化技术
罚函数求解非线性规划问题的思想是利用问题中的约束函数作出适当的罚函数，由此构造出带参数的增广目标函数，把问题转换为无约束非线性规划问题，主要有两种形式，一种叫外罚函数法，另一种叫内罚函数法
外罚函数法：考虑问题：$minf(x)\\ s.t.\begin{cases} g_i(x) \le 0,i=1,...,r\\ h_j(x) \ge 0,j=1,...,s\\ k_m(x) =0,m=1,...,t \end{cases}$取一个充分大的数M>0,构造函数$P(x,M)=f(x)+M\sum_{i=1}^nmax(g_i(x),0)-M\sum_{j=1}^nmin(h_j(x),0)+M\sum_{m=1}^n |k_m(x)|$,则以增广目标函数$P(x,M)$为目标函数的无约束极值问题$minP(x,M)$的最优解也是原问题的最优解
1. 如果非线性规划问题要求实时算法，可以使用罚函数算法，但计算精度较低
2. 如果不要求实时算法，要求高精度,可以使用lingo或matlab的fmincon命令求解

matlab求约束极值问题

在matlab工具箱中，用于求解约束最优化问题的函数有fminbnd,fmincon,quadprog,fseminf,fminimax函数

fminbnd函数

1
2
3

[x,fval]=fminbnd(fun,x1,x2,options) 
# 用于求单变量非线性函数在[x1,x2]上极小值
# 返回极小点x和函数的极小值

fseminf函数用于求下列模型 $minf(x),\\ s.t. \begin{cases} A \cdot x \le b,\\ Aeq \cdot x =beq,\\ lb\le x \le ub\\ c(x)\le0\\ ceq(x)\le0\\ K_i(x,w_i)\le0,1\le i\le n \end{cases}其中c(x),ceq(x)为向量函数，K_i(x,w_i)为标量函数,w_1...为附加变量$
1
[x,fval]=fseminf(fun,x0,ntheta,seminfcon,A,b,Aeq,beq,lb,ub)
fun定义目标函数f(x),x0为x初始值，ntheta是半无穷约束$K_i(x,w_i)$个数，函数seminfcon用于定义非线性不等式约束$c(x)$,非线性等式约束$ceq(x)$和半无穷约束$K_i(x,w_i)$的函数，seminfcon有两个输入参量x,s,s是推荐的采样步长可以不使用
fminimax函数用于求下列模型 $min_xmax_iF_i(x),\\ s.t. \begin{cases} A \cdot x \le b,\\ Aeq \cdot x =beq,\\ lb\le x \le ub\\ c(x)\le0\\ ceq(x)=0\\ \end{cases}$ matlab命令为
1
[x,fval]=fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)