数学建模

本文章是个人学习数学建模的日常心得笔记

学习资料：

B站视频： https://www.bilibili.com/video/BV1kC4y1a7Ee?from=search&seid=3914277314245328008

参考书籍：《MATLAB R2016a完全自学一本通》、司守奎《数学建模算法与应用》（主要）、《线性代数》、《概率论》

若文章有写错之处，欢迎指出(⊙o⊙)

（不间期更新）

一、线性规划基本原理与编程实践

（3）隐枚举问题——求解“0-1”整数规划

（4）匈牙利算法——求解指派问题（特殊的“0-1”整数规划）

一、线性规划基本原理与编程实践

1、什么是线性规划？

由约束条件+目标函数组成，如图所示。

如果换作是正经一点说法的话，就是：在一组线性约束条件的限制之下，求一线性目标最大最小值的问题

其中X1，x2是决策变量。

通过一般的式子，我们可以得出线性规划问题的标准式子：

其中式子中： $\large b_{_i{}}\geqslant 0,i=0,1,2.....m$

可行解 满足和约束条件式的解x= $\large [x1,x2,x3...xn]^T$ ,称作是线性规划问题的可行解，而使之目标函数式（1，3）达到最大值的可行解称为最优解

可行域 所有可行解构成的集合称为问题的可行域

2、线性规划的Matlab标准形式

①Matlab线性规划的标准形式为：

式子中，f,x,b,beq,lb,ub为列向量，其中f称为价值向量，b称为资源向量；Aeq,A是矩阵。

②Matlab中求解线性规划的命令：

式子中，x返回决策向量的取值，fval返回目标函数的最优值，f是价值向量；A和b对应线性不等式约束；Aeq和beq对应线性等式约束；lb和ub分别对应决策向量的下界向量和上界向量。

二、整数规划

1、什么是整数规划

数学规划中的变量（部分或全部）限制为整数时，称为整数规划；若在线性规划模型中，变量限制为整数，则称为整数线性规划。

意思就是在线性规划的条件下，添加一个整数的限制！！！

2、一般解题技巧方式

（1）分支定界法

不考虑整数限制先求出相应松弛问题的最优解，若松弛问题无可行解，则ILP无可行解；若求得的松弛问题最优解符合整数要求，则是ILP的最优解；

若不满足整数条件，则任选一个不满足整数条件的变量 $\large x_{i}^{0}$ 来构造 ,新的约束添加到松弛问题中形成两个子问题

$\large x_{i}\leqslant \left [ x_{i}^{0} \right ];x_{i}\geqslant [x_{i}^{0}]+1$

依次在缩小的可行域中求解新构造的线性规划的最优解，并重复上述过程，直到子问题无解或有整数最优解（被查清）。

（2）割平面法

如果松弛问题(P0)无解，则(P)无解；
如果(P0)的最优解为整数向量，则也是(P)的最优解；
如果(P0)的解含有非整数分量，则对(P0) 增加割平面条件：即对(P0)增加一个线性约束，将(P0)的可行区域割掉一块，使得非整数解恰好在割掉的一块中，

但又没有割掉原问题(P)的可解，得到问题(P1)，重复上述的过程。

（3）隐枚举问题——求解“0-1”整数规划

（4）匈牙利算法——求解指派问题（特殊的“0-1”整数规划）

三、非线性规划

1、含义

如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不像线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。

2、一般形式

3、特殊情况——二次规划

若某非线性规划的目标函数为自变量的二次函数，约束条件又全是线性的，就称这种规划为二次规划。

4、番外算法——层次分析法（AHP）

（1）什么是AHP？？

AHP是将决策总是有关的元素分解成目标、·准则、方案等层次，在此基础之上进行定性和定量分析的决策方法。

这种方法的特点是在对复杂的决策问题的本质、影响因素及其内在关系等进行深入分析的基础上，利用较少的定量信息使决策的思维过程数学化，从而为多目标、多准则或无结构特性的复杂决策问题提供简便的决策方法。尤其适合于对决策结果难于直接准确计量的场合。

（2）基本思路

人对一个复杂的决策问题的思维、判断过程大体上是一样的。不妨用假期旅游为例：假如有3个旅游胜地A、B、C供你选择，你会根据诸如景色、费用和居住、饮食、旅途条件等一些准则去反复比较这3个候选地点．首先，你会确定这些准则在你的心目中各占多大比重，如果你经济宽绰、醉心旅游，自然分别看重景色条件，而平素俭朴或手头拮据的人则会优先考虑费用，中老年旅游者还会对居住、饮食等条件寄以较大关注。其次，你会就每一个准则将3个地点进行对比，譬如A景色最好，B次之；B费用最低，C次之；C居住等条件较好等等。最后，你要将这两个层次的比较判断进行综合，在A、 B、C中确定哪个作为最佳地点。