精华内容
下载资源
问答
  • 优化模型的建模过程和方法
    千次阅读 多人点赞
    2021-08-19 12:11:00

    这里总结了一些数学建模的常用模型和算法,我们给出了相应的模型(算法)描述、相关内容的网页链接,部分模型(算法)给出了全国大学生数学建模竞赛中使用该模型(算法)的优秀论文的例子。

    常见模型

    微分方程模型

    模型描述:
    微分方程模型是指,在机理分析的基础上,建立关于未知变量、未知变量的导数以及自变量的方程(方程组),通过求解,得到未知变量的变化情况的模型。
    在建立微分方程的时候,可以利用已知的物理定律(例如:牛顿加热定理)、平衡或增长关系(人口增长规律)等,常见的例子有:传染病模型、经济增长模型、正规战与游击战、药物在体内的分布与排除、香烟过滤嘴的作用、人口预测和控制、烟雾的扩散与消失、万有引力定律的发现等。
    参考网页:
    百度文库.
    https://wenku.baidu.com/view/601e0a3ef56527d3240c844769eae009591ba26c.html
    百度文库,以四个例子讲解.
    https://wenku.baidu.com/view/884af5c69ec3d5bbfd0a744a.html
    道客巴巴,以多个例子讲解.
    http://www.doc88.com/p-0751499527286.html
    优秀论文实例:
    2019年 A240 高压油管压力波动的稳定控制 一文:针对问题一,利用燃油压力与密度关系式,推导燃油密度变化,通过燃油压力与密度关系式推得压力变化,使微小时段无穷逼近于零,建立微分方程模型。

    元胞自动机模型

    模型描述:
    元胞自动机模型是网络动力学模型中最常用的一种。许多复杂的问题都可以通过元胞自动机来建立模型,元胞自动机实质上是定义在一个具有离散、有限状态的元胞组成的元胞空间上,并按照一定的局部规则,在离散的时间维度上演化的动力学系统。元胞又可称为单元、细胞,是元胞自动机的最基本的组成部分。元胞具有以下特点:1)元胞自动机最基本的单元。2)元胞有记忆贮存状态的功能。3)所有元胞状态都按照元胞规则不断更新。
    参考网页:
    讲解特别详细.
    https://max.book118.com/html/2015/0613/18964031.shtm
    B站,两个例子讲解.
    https://www.bilibili.com/read/cv4587910/
    CSDN,两个例子含代码.
    https://blog.csdn.net/weixin_43102634/article/details/102996254
    优秀论文实例:
    2019年 C137 基于系统模拟的机场出租车决策与安排模型 一文:针对上车点的设置问题,以乘车效率为优化目标,安全因素为约束条件,上车点数量为决策变量,建立单目标优化模型。通过合理制定机场出租车乘车区运行规则,利用元胞自动机的方法,进行计算机模拟,得到各方案对应的乘车效率。

    动态规划模型

    模型描述:
    动态规划方法属较科学有效的模型,它的基本思想是,把一个比较复杂的问题分解为一系列同类型的更易求解的子问题,便于应用计算机。整个求解过程分为两个阶段,先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值,然后再顺序地求出整个问题的最优策略和最优路线。计算过程中,系统地删去了所有中间非最优的方案组合,从而使计算工作量比穷举法大为减少。
    参考网页
    道客巴巴,概念讲解全面.
    https://www.doc88.com/p-6896483301441.html?r=1
    道客巴巴,以一个例子讲解.
    https://www.doc88.com/p-272181986541.html?r=1
    CSDN,简单例子含代码.
    https://blog.csdn.net/qq_43649786/article/details/98843408
    优秀论文实例:
    2020年 B108 基于动态规划、统计分析、静态博弈的穿越沙漠游戏策略设计 一文:针对问题一,先将游戏机制转化为python程序,模拟后发现了对游戏状态及其转移规律的数学表示后论证了动态规划模型的合理性。

    决策树模型

    模型描述:
    决策树通过把实例从根节点排列到某个叶子节点来分类实例,叶子节点即为实例所属的分类。树上的每一个节点说明了对实例的某个属性的测试,并且该节点的每一个后继分支对应于该属性的一个可能值。
    决策树可以做分类、回归,数据从上往下在树中游走,叶子节点就是最终的预测值or回归值
    参考网页:
    豆丁网,讲解全面.
    https://www.docin.com/p-661084110.html
    博客园,以例子讲解.
    https://www.cnblogs.com/zhwa1314/p/12128769.html
    博客园,以例子讲解.
    https://www.cnblogs.com/listenfwind/p/10199720.html
    优秀论文实例:
    2020年 C109 基于梯度下降的决策树算法与非线性规划的信贷风险评估与信贷策略模型 一文:针对问题一,首先基于附件的交易票据数据挖掘出各企业的多项经营与财务指标,并进行筛选。之后对于传统的决策树模型进行改进,对于原模型添加正则项函数以抑制决策树的复杂性,利用集成学习思想将多个决策树模型进行叠加,基于梯度下降算
    法进行迭代优化,得到最终的集成模型。

    主成分分析

    模型描述:
    在实际问题研究中,多变量问题是经常会遇到的。变量太多,无疑会增加分析问题的难度与复杂性,而且在许多实际问题中,多个变量之间是具有一定的相关关系的。 因此,人们会很自然地想到,能否在相关分析的基础上,用较少的新变量代替原来较多的旧变量,而且使这些较少的新变量尽可能多地保留原来变量所反映的信息?
    主成分分析是把原来多个变量划为少数几个综合指标的一种统计分析方法。
    参考网页:
    知乎,讲解详细,SPSS应用为例子.
    https://zhuanlan.zhihu.com/p/63139206
    百度文库.
    https://wenku.baidu.com/view/f19495b5001ca300a6c30c22590102020640f2d5.html
    豆丁网,一个例子讲解.
    https://www.docin.com/p-1023576770.html
    优秀论文实例:
    2020年 C142 银行对中小微企业的信贷策略 一文:在模型建立方面,对于问题一,本组建立了三级七类的企业风险衡量指标体系,并建立了基于主成分分析的信贷风险评价模型和基于非线性规划的最优信贷策略决策模型。

    图论和网路模型

    模型描述:
    图论作为优化问题的一个分支,是通过优化方法来解决图或网络中出现的诸如最短路径问题,最小生成树,最大流,最小流问题等。除了传统意义上的图,很多问题都可以转化为图论问题。比如图像拼接问题,就是将图像按照边缘的吻合度来进行拼接。可以将每个图像碎片视为图的节点,将碎片边缘的吻合度作为图中节点之间的距离,从而将图像拼接问题转化为图论问题。
    参考网站:
    百度文库.
    https://wenku.baidu.com/view/41ff73a06d175f0e7cd184254b35eefdc9d31575.html
    豆丁网.
    https://www.docin.com/p-2142865988.html
    CSDN,含详细代码实现.
    https://blog.csdn.net/weixin_41213648/article/details/92802864

    排队论模型

    模型描述:
    排队论又称为随机服务系统。抽象地说,可以将有输入和输出的一个整体称为一个系统,将进入该系统希望得到某种服务的人或物称为顾客,提供某种服务的人或设施称为服务台。顾客进入到系统后等待接受服务,当其需要的服务得到满足后离开该系统。由于顾客达到该系统般都是随机的,到达后接受服务的时间也是随机的,所以也称排队论为随机服务系统理论,并可将排队论看成概率与统计研究的种具体的问题。该理论要研究的是排队系统运行的效率以及如何改进排队系统使得顾客接受服务的质量得到提升。
    参考网站:
    (CSDN,代码和数学公式)https://blog.csdn.net/weixin_43102634/article/details/102996193
    (百度文库,PPT)https://wenku.baidu.com/view/35cd84768762caaedc33d430.html
    (豆丁网,书本详细讲解)https://www.docin.com/p-487580791.html

    时间序列分析

    模型描述:
    研究时间序列主要目的:进行预测,根据已有的时间序列数据预测未来的变化。时间序列预测关键:确定已有的时间序列的变化模式,并假定这种模式会延续到未来。预测步骤:
    第一步:确定时间序列所包含的成分,确定时间序列的类型。第二步:找出适合此类时间序列的预测方法。第三步:对可能的预测方法进行评估,以确定最佳预测方案。第四步:利用最佳预测方案进行预测。
    参考网页:
    CSDN,详细讲解.
    https://blog.csdn.net/mengjizhiyou/article/details/82683448
    百度文库.
    https://wenku.baidu.com/view/b39e7778168884868762d68c.html
    豆丁网,详细讲解.
    https://www.docin.com/p-681357029.html

    常用算法:

    模拟退火算法

    算法描述:
    模拟退火算法是基于Monte-Carlo迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部最优解能概率性地跳出并最终趋于全局最优。
    原理:模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。根据Metropolis准则,粒子在温度T时趋于平衡的概率为e(-ΔE/(kT)),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制,包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。
    步骤:
    模拟退火算法新解的产生和接受可分为如下四个步骤:
    第一步是由一个产生函数从当前解产生一个位于解空间的新解;为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法,如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响。
    第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生,所以目标函数差的计算最好按增量计算。事实表明,对大多数应用而言,这是计算目标函数差的最快方法。
    第三步是判断新解是否被接受,判断的依据是一个接受准则,最常用的接受准则是Metropolis准则: 若ΔT<0则接受S′作为新的当前解S,否则以概率exp(-ΔT/T)接受S′作为新的当前解S。
    第四步是当新解被确定接受时,用新解代替当前解,这只需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值即可。此时,当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时,则在原当前解的基础上继续下一轮试验。
    参考网页:
    博客园,内容浅显易懂.
    https://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html
    CSDN,以实例说明,含代码.
    https://blog.csdn.net/qq_34554039/article/details/90294046
    知乎,含详细代码注释.
    https://zhuanlan.zhihu.com/p/23094323

    优秀论文实例:
    2019年 B136 齐心舞动“同心鼓”,齐力牵起“协力绳”——同心鼓运动模型的理论分析与策略研究 一文:对于问题四,针对给定排球偏斜竖直方向运动的特殊情况,分析调整鼓面倾角与倾向的解决方法,并以此建立多目标规划的最佳策略模型,基于模拟退火算法的相关思想,通过分析约束条件及目标函数,针对团队协作策略的有效性与协调性进行全局优化。
    2020年 A212 回焊炉温曲线优化控制 一文:对于问题三,以题目中的界限以及各温度区设定温度值和传送带过炉速度的范围限制为约束条件,以炉温曲线超1℃到峰值温度所覆盖的面积为优化目标,建立单目标优化模型来求取面积的最小值,利用模拟退火算法迭代20000次进行求解,得到最优方案。

    遗传算法

    算法描述:
    遗传算法(Genetic Algorithm, GA)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。
    其主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法,不需要确定的规则就能自动获取和指导优化的搜索空间,自适应地调整搜索方向。
    遗传算法以一种群体中的所有个体为对象,并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中,选择、交叉和变异构成了遗传算法的遗传操作;参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。
    参考网页:
    简书,算法步骤详细.
    https://www.jianshu.com/p/ae5157c26af9
    CSDN,讲解生动.
    https://blog.csdn.net/u010451580/article/details/51178225
    CSDN,代码详细.
    https://blog.csdn.net/weixin_41122036/article/details/99621870
    优秀论文实例:
    2020年 A195 基于一维热传导方程的回焊炉炉温模型 一文:根据问题三要求与制程界限约束,将该问题转换为关于温区温度和过炉速度的单目标多变量最优化问题并使用遗传算法(Genetic Algorithn)求解。基于MATLAB的GA工具箱进行算法的编程实现。

    BP神经网络

    算法描述:
    BP网络是一种多层前馈神经网络,它的名字源于在网络训练中,调整网络权值的训练算法是反向传播算法(即BP学习算法).
    BP网络是一种具有三层或者三层以上神经元的神经网络,包括输入层,隐含层和输出层,上下层之间实现全连接,而同一层的神经元之间无连接,输入层神经元和隐含层神经元之间的是网络的权值,即两个神经元之间的连接强度.隐含层或输出层任一神经元将前一层所有神经元传来的信息进行整合,通常还会在整合的信息中添加一个阈值.当一对学习样本提供给输入神经元后,神经元的激活值(该层神经元输出值)从输入层经过各隐含层向输出层传播,在输出层的各神经元获得网络的输入响应,然后按照减少网络输出与实际输出样本之间误差的方向,从输出层反向经过各隐含层回到输入层,从而逐步修正各隐含权值,这种算法称为误差反向传播算法,即BP算法。
    参考网页:
    CSDN,代码实例.
    https://blog.csdn.net/sunyueqinghit/article/details/81703931
    百度文库.
    https://wenku.baidu.com/view/ca5041bc178884868762caaedd3383c4ba4cb45e.html
    CSDN,数学原理讲解.
    https://blog.csdn.net/fanxin_i/article/details/80212906
    优秀论文实例:
    2020年 C142 银行对中小微企业的信贷策略 一文:对于问题二,建立了基于BP神经网络的信誉评价指数预测模型。

    插值和拟合算法

    算法描述:
    插值和拟合是数学建模中,处理数据时常常用到的方法。插值:求过已知有限个数据点的近似函数。拟合:已知有限个数据点,求近似函数,不要求过已知数据点,只要求在某种意义下它在这些点上的总偏差最小。插值和拟合都是要根据一组数据构造一个函数作为近似,由于近似的要求不同,二者的数学方法上是完全不同的。插值的方法多种多样,拟合问题除了用最小二乘,还可以用机器学习、深度学习算法来实现,但要注意过拟合问题。
    参考网页:
    CSDN,详细数学推导.
    https://blog.csdn.net/qq_29831163/article/details/89504179
    CSDN,两个例子,简单代码实现.
    https://blog.csdn.net/narcissus2_/article/details/99779464
    百度文库.
    https://wenku.baidu.com/view/5c7c38a6b04e852458fb770bf78a6529657d3571.html

    聚类分析算法

    算法描述:
    聚类分析是一种定量方法,从数据分析的角度看,它是对多个样本进行定量分析的多元统计分析方法,可以分为两种:对样本进行分类称为Q型聚类分析,对指标进行分类称为R型聚类分析。从数据挖掘的角度看,又可以大致分为四种:划分聚类,层次聚类,基于密度的聚类和基于网格的聚类。无论是从那个角度看,其基本原则都是:希望族(类)内的相似度尽可能高,族(类)间的相似度尽可能低(相异度尽可能高)。实现聚类分析的算法有很多,可以参考下面的网页。
    参考网页:
    CSDN,详细分类.
    https://blog.csdn.net/qq_39422642/article/details/78821812
    CSDN,代码详解.
    https://blog.csdn.net/qq_45149408/article/details/107168874
    CSDN,SPSS聚类分析方法.
    https://blog.csdn.net/qq_40875849/article/details/103987505

    更多相关内容
  • 数学建模优化模型详解

    万次阅读 多人点赞 2022-03-09 21:51:29
    全文共8090个字,码字总结不易,老铁们来个三连:点赞、关注、评论作者:[左手の明天] 原创不易,转载请联系作者并... 这些问题都是“最优化问题”,也是数学建模中的典型问题,解决最优化问题的数学方法就是“最优化..

    全文共8090个字,码字总结不易,老铁们来个三连:点赞、关注、评论
    作者:[左手の明天]
     原创不易,转载请联系作者并注明出处
    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    “优化”是生活中经常使用的词:坐出租车时希望司机不绕弯路、走优化路线;逛超市时考虑各种优惠活动,希望获得最大优惠;企业推出新产品要综合考虑成本与市场吸引力,对资金进行优化配置,等等。 这些问题都是“最优化问题”,也是数学建模中的典型问题,解决最优化问题的数学方法就是“最优化方法”。

    最优化方法的出发点是系统思维,最优化方法的基本思路是在一定的约束条件下,保证各方面资源的合理分配, 最大限度地提升系统某一性能或系统整体性能,最终实现最理想结果。运用最优化方法建立并求解数学模型,主要包括以下步骤:

    (1)明确目标,分析问题背景,确定约束条件,搜集全面的客观数据和信息;
    (2)建立数学模型,构建变量之间的数学关系,设立目标函数;
    (3)分析数学模型,综合选择最适合该模型的优化方法;
    (4)求解模型,通常借助计算机和数学分析软件完成;
    (5)对最优解进行检验和实施。

    目录

    数学规划的一般模型

    MATLAB 求解优化问题的主要函数

    模型及基本函数

    优化函数的输入变量

    优化函数的输出变量

    无约束最优化问题

    数学描述

    解析解法和图解法

    数值解法

    全局最优解和局部最优解

    带约束最优化问题

    线性规划问题

    情况一

    情况二

    二次规划问题

    非线性规划问题

    定义

    求解算法1:间接法

    求解算法2:直接法

    求解算法3:最速下降法(steepest descent method)

    Matlab求解步骤

    示例

    0-1规划问题

    钢管的订购与运输问题

    问题

    问题1的基本模型和解法

    总费用最小的优化问题

    基本模型:二次规划

    Floyd算法求解步骤 

    最优化方法在数学建模中的应用 

    梯度下降法

    惩罚函数法

    遗传算法

    蚁群算法


    数学规划的一般模型

    其中,x~决策变量;f(x)~目标函数;gi(x)≤0~约束条件


    MATLAB 求解优化问题的主要函数

    模型及基本函数

    优化函数的输入变量

    优化函数的输出变量


    无约束最优化问题

    数学描述

    解析解法和图解法

     举例:用解析和图解法求解下列方程

    <<syms t; 
    y=exp(-3*t)*sin(4*t+2)+4*exp(-0.5*t)*cos(2*t)-0.5;
    ezplot(y,[0 4])
    y1=diff(y);
    ezplot(y1,[0 4])
    t0=solve(y1)
    y2=diff(y1);
    b=subs(y2,t,t0)

    数值解法

     命令形式1:

    x=fminsearch(fun,x0)   %简单形式
    
    [x,f,flag,out]=fminsearch(fun,x0,opt,p1,p2,…) %一般形式

    功能:与fsolve()中的参数控制形式类似。

    注:若函数时多元的,要表达成向量的形式。

    命令形式2:

    x=fminunc(fun,x0)   %简单形式
    
    [x,f,flag,out]=fminunc(fun,x0,opt,p1,p2,…) %一般形式

    功能:与fsolve()中的参数控制形式类似。

    举例:

    >>f=inline('(x(1)^2-2*x(1))*exp(-x(1)^2-x(2)^2-x(1)*x(2))','x');
    x0=[0,0];
    ff=optimset;ff.Display='iter';
    x=fminsearch(f,x0,ff)
    
    >>x=fminunc(f,x0,ff)
    

    全局最优解和局部最优解

    一元函数极小

    X=fminbnd(fun,x1,x2)

    多元无约束极小

    X=fminunc(fun,x0) (牛顿法)
    X=fminsearch(fun,x0)

    举例1:(初值的影响力)设目标函数为

     试观察不同的初值得出的最小值。

    >> f=inline('exp(-2*t)*cos(10*t)+exp(-3*(t+2))*sin(2*t)','t');
    t0=1;[t1,f1]=fminsearch(f,t0)
    
    t1=0.92275390625000,f1=-0.15473299821860
    
    >> t0=0.1;[t2,f2]=fminsearch(f,t0)
    
    t2=0.29445312500000,f2=-0.54362463738706
    
    
    >> syms t; 
    y=exp(-2*t)*cos(10*t)+exp(-3*(t+2))*sin(2*t);
    ezplot(y,[0,2.5]); axis([0 2.5 -0.6 1])

    举例2:对边长为3米的正方形铁板,在四个角剪去相等的正方形以制成方形无盖水槽,问如何剪法使水槽的容积最大?

    建立模型: 

    设剪去的正方形的边长为x,,则水槽的容积为:

    建立无约束优化模型为:

    模型求解:

    先编写M文件如下:

    function f=myfun(x)
    f=-(3-2*x).^2*x;

    调用fminbnd:

    [x,fval]=fminbnd(@myfun,0,1.5)

    运算结果为:

    x = 0.5000,fyal =2.0000.

    即剪掉的正方形的边长为0.5米时水槽的容积最大,最大容积为2立方米。


    带约束最优化问题

    线性规划问题

    目标函数:

     约束条件:

    情况一

    目标函数:

    其中,C为价值向量

    约束条件:

     其中,b为资源向量;X为决策变量向量

    其中:

     

    命令形式1:

    [X,lag,how]=lp(C,A,b,v1,v2,x0)

    功能:

    • C,A,b的意义如矩阵表示里参数;
    • v1,v2表示决策变量的上界和下界(其维数可以小于X,但表示前几个分量的上下界);
    • x0表示初始值;X时输出最优解;
    • lag是lagrange乘子,维数等于约束条件的个数,非零的向量是起作用的约束条件;
    • how给出错误信息:infeasible(无可行解),unbounded(无界解),ok(求解成功).

     举例:

    >> c=[13,-1,5];
    A=[-1,-1,0;0,1,1];
    b=[-7,10];
    v0=[2,0,0];
    [X,lag,how]=lp(c,A,b,v0)
    

    情况二

    目标函数:

     约束条件:

    命令形式2:  

    [X,f,flag,c]=linprog(C,A,b,Aeq,Beq,xm,xM,x0,opt)

    功能:各个参数的解释如前,若各个约束条件不存在,则用空矩阵来代替。

    • x: 解
    • f: 最优值
    • flag:大于零表示求解成功,否则求解出问题
    • c:求解信息
    • x0:搜索点的初值
    • opt:最优化控制项

    举例1:

    >> c=[-2,-1,-4,-3,-1];
     A=[0 2 1 4 2;3 4 5 -1 -1];
     b=[54,62];
     Ae=[];Be=[];
     xm=[0,0,3.32,0.678,2.57];
     ff=optimset;
     ff.LargeScale='off';
     ff.TolX=1e-15;
     ff.Display='iter';
     [X,f,flag,c]=linprog(c,A,b,Ae,Be,xm,[],[],ff)
    

    举例2:某车间生产A和B两种产品,为了生产A和B,所需的原料分别为2个和3个单位,所需的工时分别为4个和2个单位。现在可以应用的原料为100个单位,工时为120个单位。每生产一台A和B分别可获得利润6元和4元。应当生产A和B各多少台能获得最大利润?

    分析:

     模型建立:

    设生产A产品x1 台,生产B产品 x2台

     模型求解:

    f=[-6,-4]';
    A=[2 3;4 2];
    B=[100;120];
    Ae=[];
    Be=[];
    xm=[0,0];
    ff=optimset;
    ff.LargeScale='off'; % 不用大规模问题求解
    ff.TolX=1e-15;
    ff.TolFun=1e-20; 
    ff.TolCon=1e-20;
    ff.Display='iter';
    [x,f_opt,key,c]=linprog(f,A,B,Ae,Be,xm,[],[],ff)

    举例3:(任务分配问题)某车间有甲、乙两台机床,可用于加工三种工件。假定这两台车床的可用台时数分别为 800 和 900,三种工件的数量分别为 400、600 和 500,且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务,才能既满足加工工件的要求,又使加工费用最低?

    模型建立:

    设在甲车床上加工工件 1、2、3 的数量分别为 x1、x2、x3,在乙车床上加工工件 1、2、3 的数量分别为 x4、x5、x6。可建立以下线性规划模型:

    模型求解:

    f = [13 9 10 11 12 8];
    A = [0.4 1.1 1 0 0 0
    0 0 0 0.5 1.2 1.3];b = [800; 900];
    Aeq=[1 0 0 1 0 0
    0 1 0 0 1 0
    0 0 1 0 0 1];
    beq=[400 600 500];
    vlb = zeros(6,1);
    vub=[];
    [x,fval] = linprog(f,A,b,Aeq,beq,vlb,vub)

    举例4:某厂每日 8 小时的产量不低于 1800 件。为了进行质量控制,计划聘请两种不同水平的检验员。一级检验员的标准为:速度 25 件/小时,正确率 98%,计时工资 4 元/小时;二级检验员的标准为:速度 15 小时/件,正确率 95%,计时工资 3 元/小时。检验员每错检一次,工厂要损失 2 元。为使总检验费用最省,该工厂应聘一级、二级检验员各几名?

    模型建立:

    设需要一级和二级检验员的人数分别为 x1、x2 人,则应付检验员的工资为:

     因检验员错检而造成的损失为:

    故目标函数为:

    约束条件为:

     

     线性规划模型:

     

     模型求解:

    c = [40;36];
    A=[-5 -3];
    b=[-45];
    Aeq=[];
    beq=[];
    vlb = zeros(2,1);
    vub=[9;15];
    %调用 linprog 函数:
    [x,fval] = linprog(c,A,b,Aeq,beq,vlb,vub)

    结果:

    x =
    9.0000
    0.0000
    fval =360

    即只需聘用 9 个一级检验员。

    二次规划问题

    目标函数:

    约束条件: 

    命令形式:

     [X,f,flag,c]=quadprog(H,C,A,b,Aeq,Beq,xm,xM,x0,opt)

    功能:

    各个参数的解释如前,若各个约束条件不存在,则用空矩阵来代替。

    举例:

     

    >> c=[-2,-1,-4,-3,-1];
      A=[0 2 1 4 2;3 4 5 -1 -1];
      b=[54,62];
      Ae=[];Be=[];
      xm=[0,0,3.32,0.678,2.57];
      ff=optimset;
      ff.LargeScale='off';
      ff.TolX=1e-15;
      ff.Display='iter';
      [X,f,flag,c]=linprog(c,A,b,Ae,Be,xm,[],[],ff)
    

    非线性规划问题

    定义

    如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题.

    一般形式:

     其中

     

     是定义在 En 上的实值函数,简记:

     

    其它情况:

    求目标函数的最大值或约束条件为小于等于零的情况,都可通过取其相反数化为上述一般形式.

     

    其中X为n维变元向量,G(X)与Ceq(X)均为非线性函数组成的向量,其它变量的含义与线性规划、二次规划中相同.

    求解算法1:间接法

    在非线性最优化问题当中,如果目标函数能以解析函数表示,可行域由不等式约束确定,则可以利用目标函数和可行域的已知性质,在理论上推导出目标函数为最优值的必要条件,这种方法就称为间接法(也称为解析法) 。 一般要用到目标函数的导数。

    求解算法2:直接法

    直接法是一种数值方法。这种方法的基本思想是迭代,通过迭代产生一个点序列{ X(k) },使之逐步接近最优点。 只用到目标函数。 如黄金分割法、Fibonacci、随机搜索法。

    迭代法一般步骤

     注意:数值求解最优化问题的计算效率取决于确定搜索方向P (k)和步长的效率。

    求解算法3:最速下降法(steepest descent method)

    由法国数学家Cauchy于1847年首先提出。在每次迭代中,沿最速下降方向(负梯度方向)进行搜索,每步沿负梯度方向取最优步长,因此这种方法称为最优梯度法。

    特点:

    方法简单,只以一阶梯度的信息确定下一步的搜索方向,收敛速度慢; 越是接近极值点,收敛越慢; 它是其它许多无约束、有约束最优化方法的基础。 该法一般用于最优化开始的几步搜索。

    最速下降法算法:

    Matlab求解步骤

    用Matlab求解上述问题,基本步骤分三步:

    1. 首先建立M文件fun.m,定义目标函数F(X):

    function f=fun(X); 
    f=F(X);

     3. 建立主程序.非线性规划求解的函数是fmincon,命令的基本格式如下:       

    (1) x=fmincon(‘fun’,X0,A,b)    
    
    (2) x=fmincon(‘fun’,X0,A,b,Aeq,beq)    
    
    (3) x=fmincon(‘fun’,X0,A,b, Aeq,beq,VLB,VUB)          
    
    (4) x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’)
    
    (5) x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’,options)
    
    (6) [x,fval]= fmincon(...)
    
    (7) [x,fval,exitflag]= fmincon(...)  
    
    (8) [x,fval,exitflag,output]= fmincon(...)

    输入参数的几点说明:

    模型中如果没有A,b,Aeq,beq,VLB,VUB的限制,则以空矩阵[ ]作为参数传入;

    nonlcon:如果包含非线性等式或不等式约束,则将这些函数编写一个Matlab函数

    nonlcon就是定义这些函数的程序文件名;

    不等式约束  G(x)<=0

    等式约束     Ceq(x)=0.

    如果nonlcon=‘mycon’ ; 则myfun.m定义如下

    function [G,Ceq] = mycon(x)
    
    G= ... % 计算非线性不等式约束在点x处的函数值
    
    Ceq= ... %计算机非线性等式约束在点x处的函数值 

    示例

    例子1:

    2个不等式约束, 2个等式约束 3个决策变量x1,x2,x3 如果nonlcon以‘test’作为参数值,则程序test.m如下

    function [G,Ceq]=test(x)
    G(1)=x(1)*x(1)+x(2)*x(2)+x(3)*x(3)-100
    G(2)=60-x(1)*x(1)+10*x(3)*x(3)
    Ceq(1)=x(1)+x(2)*x(2)+x(3)- 80
    Ceq(2)=x(1)^3+x(2)*x(2)+x(3)- 80
    

    注意:

    [1] fmincon函数提供了大型优化算法和中型优化算法。默认时,若在fun函数中提供了梯度(options参数的GradObj设置为’on’),并且只有上下界存在或只有等式约束,fmincon函数将选择大型算法。当既有等式约束又有梯度约束时,使用中型算法。

    [2] fmincon函数可能会给出局部最优解,这与初值X0的选取有关。

    例子2:

     1.先建立M文件 fun.m,定义目标函数:

    function f=fun(x);
    
    f=exp(x(1)) *(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);

     2.再建立M文件mycon.m定义非线性约束:

    function [g,ceq]=mycon(x)
    
    g=[1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10];
    
    ceq=[];

    3.主程序为:

    x0=[-1;1];
    A=[];b=[];
    Aeq=[1 1];
    beq=0; 
    vlb=[];
    vub=[];
    [x,fval]=fmincon('fun4',x0,A,b,Aeq,beq,vlb,vub,'mycon')

    4.运算结果为:

    x = -1.2250    1.2250        
    
    fval = 1.8951

    0-1规划问题

    数学描述:自变量的取值只能为0或1

    matlab解:

    X=bintprog(f,A,B,Aeq,Beq)

    小规模问题可以穷举

    举例:求解下面的0-1线性规划问题

     

    f=[-3,2,-5]; A=[1 2 -1; 1 4 1; 1 1 0; 0 4 1]; 
    B=[2;4;5;6];
    x=bintprog(f,A,B,[],[])'

    钢管的订购与运输问题

    要铺设一条A1→A2 →……→ A15的输送天然气的主管道,如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有 。图中粗线表示铁路,单细线表示公路,双细线表示要铺设的管道(假设沿管道或者原来有公路,或者建有施工公路),圆圈表示火车站,每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。

    为方便计,1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管,至少需要生产
    500个单位。钢厂Si在指定期限内能生产该钢管的最大数量为Si个单位,钢管出厂销价1单位钢管为pi万元,如下表:

     1单位钢管的铁路运价如下表:

     

    1000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元(不足
    整公里部分按整公里计算)。钢管可由铁路、公路运往铺设地点(不只是运到点A1,A2,……,A15 ,而是管道全线)。

    问题

    (1)制定钢管的订购和运输计划,使总费用最小.
    (2)分析对购运计划和总费用影响:哪个钢厂钢管销价的变化影响最大;哪个钢厂钢管产量上限的变化影响最大?
    (3)讨论管道为树形图的情形

    问题1的基本模型和解法

    总费用最小的优化问题

     

    基本模型:二次规划

    Floyd算法求解步骤 

     Floyd算法过程描述如下:

    • 1、 首先S以边集M初始化,得到所有的直接连通代价;
    • 2、 依次考虑第k个结点,对于S中的每一个S[i][j],判断是否满足:S[i][j]>S[i][k]+S[k][j],如果满足则用S[i][k]+S[k][j]代替S[i][j],此为第k步;
    • 3、 k循环取遍所有结点,算法结束时,S为最终解。

     


    最优化方法在数学建模中的应用 

    梯度下降法

    梯度下降法是经典的最优化方法之一[4],其核心思想是高等数学中的导数理论。 梯度下降法实现最优化的原理是,每次迭代更新目标函数时,都以该变量导数(即梯度)的反方向作为更新参数的方向,最终解一定会收敛于最优解。 这个原理类似于走下坡路时,总是沿着最陡峭的方向向下走,最后就一定会走到坡底。梯度下降法的实现简单, 但是求解计算时间长,因此基于梯度下降法发展了很多改进算法,包括随机梯度下降法、小批量梯度下降法等,能够有效改善计算成本高的问题。

    惩罚函数法

    惩罚函数法,指的是引入惩罚因子和惩罚函数的最优化方法[5]。 具体来说,惩罚函数的思想是:将最优化问题中的约束条件视为围墙,而迭代更新的解视为在围墙内运动的粒子,一旦粒子靠近围墙,对应的惩罚因子数值就会增大,导致惩罚函数值增大,反之,粒子远离围墙时,惩罚函数值就减小。 建立了这种惩罚机制后,在每次迭代过程中,模型为了“避免被惩罚”,逐渐趋近于约束边界,从而找到了最优解。惩罚函数法对模型的训练虽然“简单粗暴”,但是原理直观、实现门槛低,是实际工程中备受青睐的最
    优化方法。

    遗传算法

    不同于梯度下降法和惩罚函数法,遗传算法并非依据导数理论提出的算法[6],而是一种模拟生物在自然届中进化规律的一种智能算法。 自然界的生物进化遵循适者生存和优胜劣汰,即能够适应环境变化或基因变异的个体才能够参与到进化。 遗传算法的优化原理与之类似:每一次迭代时,通过计算各个个体的适应度,从中随机地选择两个个体作为父母,繁殖后代,同时诱发子代的染色体变异,重复迭代,当出现最大适应度的子代时,即认为获得了最优解,循环结束。与梯度下降法、惩罚函数法相比,遗传算法以生物进化为原型,收敛性较好,在计算精度要求时,具有计算时间少、鲁棒性高的优势。

    蚁群算法

    与遗传算法类似,蚁群算法也是受启发于生物的一种最优化方法[7]。 生物科学家发现蚂蚁经过的路上都会有一种特殊物质,并且蚁群中的蚂蚁对该物质高度敏感,由于该物质浓度越高,代表着路途长度越短,想要走“捷径”的蚁群们都会选择浓度较高的道路行走,“捷径”经过的蚂蚁越多,特殊物质的浓度就越高,物质浓度积累到一定程度,所有蚂蚁都会被吸引到最佳捷径上来,都能以最快速度找到食物了。 蚁群算法解决最优化问题,就是利用了其分布计算和信息正反馈的特点。

    展开全文