数学建模——常考优化类模型总结

优化题型三要素：决策变量、目标函数、约束条件。

• 决策变量：是决策者可以控制的因素，例如根据不同的实际问题，决策变量可以选为产品的产量、物资的运量及工作的天数等。
• 目标函数：是以函数形式来表示决策者追求的目标。例如目标可以是利润最大或成本最小等。
• 约束条件：是决策变量需要满足的限定条件。

应用场景：快递员派送快递的最短路径问题、水资源调度优化问题、高速路口收费站问题、军事行动避空侦查时机和路线选择、物流选址问题、商区分布规划等各个领域。

常见的优化类问题：

• LP（线性规划）
• ILP（整数线性规划）
• BILP（两层的线性整数规划）
• NLP（非线性规划）
• INLP （非线性整数规划）
• QP（二次规划）QCQP()
• IQP（二次整数规划 ）
• PIP（带参数整数规划）
• ZOP（零一规划）
• SOCP(二阶锥规划)
• 图论模型
• 排队论模型
• 神经网络
• 现代优化算法【遗传算法（GA）、粒子群算法（PSO）、模拟退火算法（SA）】

线性规划问题的目标函数及约束条件均为线性函数。目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。

• 内点法
• 单纯形法
• 修正单纯形法

线性优化的一般模型:

线性优化求解方法:

简而言之，目标函数和约束条件均为线性的，即为线性优化。

• 线性优化方法可简单分为两类：单纯形法与内点法。
• 两类方法均可解决数千变量和约束的线性优化问题。
• 单纯形法虽然计算效率很高，但是随着问题规模的扩大其迭代次数会呈指数型增长;
• 内点法在这一点上具有优势，因此电力系统中很多线性优化问题都采用内点法

2.1 单纯线性法

单纯线性法理论依据：

线性规划问题的可行域是 n维向量空间Rn中的多面凸集， 其最优值如果存在必在该凸集的某顶点处达到。顶点所对 应的可行解称为基本可行解。

单纯线性法基本思想：

先找出一个基本可行解，对它进行鉴别，看是否是最优解； 若不是，则按照一定法则转换到另一改进的基本可行解,再鉴 别；若仍不是，则再转换,按此重复进行。因基本可行解的个 数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

步骤：

1）构造一个初始基本可行解。

对已经标准化的线性模型，设法在约束矩阵中构造出 一个m阶单位阵作为初始可行基，相应就有一个初始可行基，相应就有一个初始基本可行解。

2）判断当前基本可行解是否为最优解。

求出用非基变量表示基变量及目标函数的表达式，称之为线性 规划问题的典式（或称为规范式）。在目标函数的典式中，若至 少有一个非基变量前的系数为正数，则当前解就不是最优解；若 所有的非基变量前的系数均为非正数，则当前解就是最优解（指 最大化问题）。 将目标函数的典式中非基变量前的系数称为检验数。故对最大化问题，当所有的检验数< 0时，当前解即为最优解。

3）若当前解不是最优解，则要进行基变换迭代到下一个基本可行解。

这样就得到了一组新的基变量和非基变量，即已从上一个基本可行解迭代到下一个基本可行解。然后求出关于新基矩阵的线性 规划问题的典式，这就完成了基变换的全过程。在新的典式中可求出新基本可行解的取值及目标函数的取值。再回到第2步判断当前新基本可行解是否已达到最优。若已达到最优，停止迭代。若没有达到最优，再进行第3步作新的基变换， 再次进行迭代。如此往复，直到求得最优解或判断无（有界）最优解时停止。

举例说明：

第一步：转化为标准形式

第二步：确定一个初始基本可行解；基本可行解就是满足非负条件的基本解，因此要在约束矩阵A中找出一个可逆的基矩阵。

第三步：从当前基可行解转换为更好的基可行解

从数学角度看， 1, 2的增加将会增加目标函数值，故目前的解并非最优解。为了寻求最优解，我们需要进行基变量的替换。

从目标函数值中 1, 2前的系数看， 1前的系数大于 2前的系数，所以让 1从非基变量转为基变量，称为进基变量

第四步：继续迭代求解

修正单纯形法原理：

在单纯形算法中，若用矩阵来描述数学模型，有：

Max Z=; Ax=b ; x ≥0.

假如有一个初始可行基B ，r（B）=m，剩下n-m个非基 向量记作N ,则A=（B , N ). 在进基、出基的过程中，每步都 需要计算矩阵B 的逆。

修正单纯形法通过对旧的矩阵B 的逆做行变换，来得到新的矩阵B 的逆，从而只需要在迭代的初始需要计算矩阵B 的逆，缩短了求解时间。

如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。当问题中只有非线性的目标函数和未知数取值范围时，称为边界约束条件问题。

1. 下山单纯形法：只使用目标函数，不使用导数函数、二阶导数，鲁棒性强。
2. 改进的BFGS拟牛顿法：需要使用一阶导数函数。该算法性能良好，消耗内存量很小，适合处理大规模问题。
3. 改进的共轭方向法：是利用共轭方向加快收敛速度的性质形成的一种搜索方法
4. （边界）截断牛顿法：不直接表示出Hessian算子，但同时利用Hessian矩阵的信息提高收敛速度和节省内存。
5. 线性近似束优化方法：通过对目标函数和约束条件的线性逼近处理非线性问题。只使用目标函数，不需要导数或二阶导数值。
6. 序贯最小二乘规划算法：根据优先级别将目标分解再依次求解，算法性能良好。
7. 信赖域算法：基本思想是把最优化问题转化为一系列简单的局部寻优问题。

启发式算法是基于直观或者经验构造的算法，在可接受的开销（时间和空间）内给出待解决组合优化问题的一个可行解。

• 遗传算法(GA)：模拟物竞天择的生物进化过程，通过维护一个潜在解的群体执行了多方向的搜索，并支持这些方向上的信息构成和交换。
• 粒子群算法(PSO)：将每个解看作搜索空间中的一个粒子。每个粒子都有一定的速度，其大小根据自身历史经验和种群经验进行动态调整，通过不断地迭代飞行来寻找空间中最优解的位置。
• 模拟退火算法(SA)：用其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解。
• 蒙特卡洛：是一种使用随机数来解决规划问题的方法，其精确度很大程度取决于实验次数。

SPSSPRO：免费在线的数据分析网站，求解线性优化问题，里面有统计建模、机器学习类算法模型，全部可以免费使用，只需要上传数据、拖拽变量即可自动生成结果，免费复制、免费下载。

第一步：输入模型目标函数/约束条件

第二步：点击建立，生成如下模型

第三步：点击分析

覆盖线性/非线性优化、整数优化、启发式算法，功能很强大，省去编程的流程。

相关推荐