最优化模型.ppt
- 文档编号:18764657
- 上传时间:2023-11-03
- 格式:PPT
- 页数:69
- 大小:1.46MB
最优化模型.ppt
《最优化模型.ppt》由会员分享,可在线阅读,更多相关《最优化模型.ppt(69页珍藏版)》请在冰点文库上搜索。
2023/11/3,数学建模,最优化模型,1、最优化方法概述2、无约束最优化3、有约束最优化4、多目标最优化,2023/11/3,数学建模,最优化方法概述,1、最优化理论和方法是近二十多年来发展十分迅速的一个数学分支。
2、在数学上,最优化是一种求极值的方法。
3、最优化已经广泛的渗透到工程、经济、电子技术等领域。
2023/11/3,数学建模,在实际生活当中,人们做任何事情,不管是分析问题,还是进行决策,都要用一种标准衡量一下是否达到了最优。
(比如基金人投资)在各种科学问题、工程问题、生产管理、社会经济问题中,人们总是希望在有限的资源条件下,用尽可能小的代价,获得最大的收获。
(比如保险),2023/11/3,数学建模,数学家对最优化问题的研究已经有很多年的历史。
以前解决最优化问题的数学方法只限于古典求导方法和变分法(求无约束极值问题),拉格朗日(Lagrange)乘数法解决等式约束下的条件极值问题。
计算机技术的出现,使得数学家研究出了许多最优化方法和算法用以解决以前难以解决的问题。
2023/11/3,数学建模,几个概念,最优化是从所有可能方案中选择最合理的一种以达到最优目标的学科。
最优方案是达到最优目标的方案。
最优化方法是搜寻最优方案的方法。
最优化理论就是最优化方法的理论。
2023/11/3,数学建模,经典极值问题,包括:
无约束极值问题约束条件下的极值问题,2023/11/3,数学建模,1、无约束极值问题的数学模型,2、约束条件下极值问题的数学模型,其中,极大值问题可以转化为极小值问题来进行求解。
如求:
可以转化为:
2023/11/3,数学建模,1、无约束极值问题的求解,例1:
求函数y=2x3+3x2-12x+14在区间-3,4上的最大值与最小值。
解:
令f(x)=y=2x3+3x2-12x+14f(x)=6x2+6x-12=6(x+2)(x-1)解方程f(x)=0,得到x1=-2,x2=1,又由于f(-3)=23,f(-2)=34,f
(1)=7,f(4)=142,综上得,函数f(x)在x=4取得在-3,4上得最大值f(4)=142,在x=1处取得在-3,4上取得最小值f
(1)=7,2023/11/3,数学建模,2023/11/3,数学建模,用MATLAB解无约束优化问题,其中等式(3)、(4)、(5)的右边可选用
(1)或
(2)的等式右边.函数fminbnd的算法基于黄金分割法和二次插值法,它要求目标函数必须是连续函数,并可能只给出局部最优解.,常用格式如下:
(1)x=fminbnd(fun,x1,x2)
(2)x=fminbnd(fun,x1,x2,options)(3)x,fval=fminbnd()(4)x,fval,exitflag=fminbnd()(5)x,fval,exitflag,output=fminbnd(),2023/11/3,数学建模,主程序为:
f=2*exp(-x).*sin(x);fplot(f,0,8);%作图语句xmin,ymin=fminbnd(f,0,8)f1=-2*exp(-x).*sin(x);xmax,ymax=fminbnd(f1,0,8),2023/11/3,数学建模,例2有边长为3m的正方形铁板,在四个角剪去相等的正方形以制成方形无盖水槽,问如何剪法使水槽的容积最大?
解,先编写M文件如下:
functionf=fun0(x)f=-(3-2*x).2*x;,主程序为x,fval=fminbnd(fun0,0,1.5);xmax=xfmax=-fval,运算结果为:
xmax=0.5000,fmax=2.0000.即剪掉的正方形的边长为0.5m时水槽的容积最大,最大容积为2m3.,2023/11/3,数学建模,命令格式为:
(1)x=fminunc(fun,X0);或x=fminsearch(fun,X0)
(2)x=fminunc(fun,X0,options);或x=fminsearch(fun,X0,options)(3)x,fval=fminunc(.);或x,fval=fminsearch(.)(4)x,fval,exitflag=fminunc(.);或x,fval,exitflag=fminsearch(5)x,fval,exitflag,output=fminunc(.);或x,fval,exitflag,output=fminsearch(.),2.多元函数无约束优化问题,标准型为:
min,2023/11/3,数学建模,例用fminsearch函数求解,输入命令:
f=100*(x
(2)-x
(1)2)2+(1-x
(1)2;x,fval,exitflag,output=fminsearch(f,-1.22),运行结果:
x=1.00001.0000fval=1.9151e-010exitflag=1output=iterations:
108funcCount:
202algorthm:
Nelder-Meadsimplexdirectsearch,2023/11/3,数学建模,有约束最优化最优化方法分类
(一)线性最优化:
目标函数和约束条件都是线性的则称为线性最优化。
非线性最优化:
目标函数和约束条件如果含有非线性的,则称为非线性最优化。
(二)静态最优化:
如果可能的方案与时间无关,则是静态最优化问题。
动态最优化:
如果可能的方案与时间有关,则是动态最优化问题,2023/11/3,数学建模,有约束最优化问题的数学建模,有约束最优化模型一般具有以下形式:
或,其中f(x)为目标函数,省略号表示约束式子,可以是等式约束,也可以是不等式约束。
2023/11/3,数学建模,根据目标函数,约束条件的特点将最优化方法包含的主要内容大致如下划分:
线性规划整数规划非线性规划动态规划多目标规划,最优化方法主要内容,2023/11/3,数学建模,两个引例,问题一:
某工厂在计划期内要安排生产I、II两种产品,已知生产单位产品所需的设备台时及A、B两种原材料的消耗,如下表所示,该工厂每生产一件产品I可获利2元,每生产一件产品II可获利3元。
问应如何安排计划使该工厂获利最多?
2023/11/3,数学建模,解:
该工厂生产产品Ix1件,生产产品IIx2件,我们可建立如下数学模型:
s.t.,2023/11/3,数学建模,问题二:
某厂每日8小时的产量不低于1800件.为了进行质量控制,计划聘请两种不同水平的检验员.一级检验员的标准为:
速度25件/小时,正确率98%,计时工资4元/小时;二级检验员的标准为:
速度15件/小时,正确率95%,计时工资3元/小时.检验员每错检一次,工厂要损失2元.为使总检验费用最省,该工厂应聘一级、二级检验员各几名?
解设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为:
因检验员错检而造成的损失为:
2023/11/3,数学建模,故目标函数为:
约束条件为:
2023/11/3,数学建模,运用最优化方法解决最优化问题的一般方法步骤如下:
前期分析:
分析问题,找出要解决的目标,约束条件,并确立最优化的目标。
定义变量,建立最优化问题的数学模型,列出目标函数和约束条件。
针对建立的模型,选择合适的求解方法或数学软件。
编写程序,利用计算机求解。
对结果进行分析,讨论诸如:
结果的合理性、正确性,算法的收敛性,模型的适用性和通用性,算法效率与误差等。
2023/11/3,数学建模,线性规划,某豆腐店用黄豆制作两种不同口感的豆腐出售。
制作口感较鲜嫩的豆腐每千克需要0.3千克一级黄豆及0.5千克二级黄豆,售价10元;制作口感较厚实的豆腐每千克需要0.4千克一级黄豆及0.2千克二级黄豆,售价5元。
现小店购入9千克一级黄豆和8千克二级黄豆。
问:
应如何安排制作计划才能获得最大收益。
2023/11/3,数学建模,一、问题前期分析该问题是在不超出制作两种不同口感豆腐所需黄豆总量条件下合理安排制作计划,使得售出各种豆腐能获得最大收益。
二、模型假设1假设制作的豆腐能全部售出。
2假设豆腐售价无波动。
2023/11/3,数学建模,变量假设:
设计划制作口感鲜嫩和厚实的豆腐各x1千克和x2千克,可获得收益R元。
目标函数:
获得的总收益最大。
总收益可表示为:
受一级黄豆数量限制:
受二级黄豆数量限制:
2023/11/3,数学建模,综上分析,得到该问题的线性规划模型,s.t.,2023/11/3,数学建模,用Matlab编程求解程序如下:
X,FVAL,EXITFLAG,OUTPUT=LINPROG(f,A,b)f=-105;A=0.30.4;0.50.2;B=9;8;X,FVAL,EXITFLAG,OUTPUT=LINPROG(f,A,b),X=10.000015.0000FVAL=-175.0000,2023/11/3,数学建模,线性规划,设某工厂有甲、乙、丙、丁四个车间,生产A、B、C、D、E、F六种产品。
根据机床性能和以前的生产情况,得知每单位产品所需车间的工作小时数、每个车间在一个季度工作小时的上限以及单位产品的利润,如下表所示(例如,生产一个单位的A产品,需要甲、乙、丙三个车间分别工作1小时、2小时和4小时)问:
每种产品各应该每季度生产多少,才能使这个工厂每季度生产利润达到最大。
2023/11/3,数学建模,2023/11/3,数学建模,这是一个典型的最优化问题,属线性规划。
假设:
产品合格且能及时销售出去;工作无等待情况等变量说明:
xj:
第j种产品的生产量(j=1,2,6)aij:
第i车间生产单位第j种产品所需工作小时数(i=1,2,3,4;j=1,2,6)bi:
第i车间的最大工作上限cj:
第j种产品的单位利润则:
cjxj为第j种产品的利润总额;aijxj表示第i车间生产第j种产品所花时间总数;,2023/11/3,数学建模,于是,我们可建立如下数学模型:
s.t.,计算结果:
整数规划,如何求解?
2023/11/3,数学建模,运输问题,要从甲城调出蔬菜2000吨,从乙城调出蔬菜2500吨,从丙地调出3000吨,分别供应A地2000吨,B地2300吨、C地1800吨、D地1400吨,已知每吨运费如下表:
问:
如何调拨才能使运费最省?
2023/11/3,数学建模,假设:
假设题目中所给运费已考虑各地间公里数;只考虑运量和运费,不考虑车辆调拨等其它相关因素不考虑车辆返空的费用(或:
所给运费已包含车辆返空的费用)变量说明:
xij:
从第i城运往第j地的蔬菜数量(i=1,2,3;j=1,2,3,4)aij:
从第i城运往第j地的单位运费(i=1,2,3;j=1,2,3,4)bi:
从第i城调出的蔬菜总量cj:
第j地所需蔬菜总量,2023/11/3,数学建模,可以建立如下模型:
s.t.,2023/11/3,数学建模,整数规划,最优化问题中的所有变量均为整数时,这类问题称为整数规划问题。
如果线性规划中的所有变量均为整数时,称这类问题为线性整数规划问题。
整数规划可分为线性整数规划和非线性整数规划,以及混合整数规划等。
如果决策变量的取值要么为0,要么为1,则这样的规划问题称为01规划。
2023/11/3,数学建模,引例.资源分配问题:
某个中型的百货商场要求售货人员每周工作5天,连续休息2天,工资200元/周,已知对售货人员的需求经过统计分析如下表,问如何安排可使配备销售人员的总费用最少?
2023/11/3,数学建模,2023/11/3,数学建模,非线性规划,非线性规划问题的一般数学模型:
其中,为目标函数,为约束函数,这些函数中至少有一个是非线性函数。
2023/11/3,数学建模,应用实例:
供应与选址,某公司有6个建筑工地要开工,每个工地的位置(用平面坐标系a,b表示,距离单位:
km)及水泥日用量d(t)由下表给出目前有两个临时料场位于A(5,1),B(2,7),日储量各有20t假设从料场到工地之间均有直线道路相连
(1)试制定每天的供应计划,即从A,B两料场分别向各工地运送多少水泥,可使总的吨千米数最小
(2)为了进一步减少吨千米数,打算舍弃两个临时料场,改建两个新的,日储量各为20t,问应建在何处,节省的吨千米数有多大?
2023/11/3,数学建模,建立模型,记工地的位置为(ai,bi),水泥日用量为di,i=1,6;料场位置为(xj,yj),日储量为ej,j=1,2;料场j向工地i的运送量为Xij,当用临时料场时决策变量为:
Xij,当不用临时料场时决策变量为:
Xij,xj,yj,多目标规划模型,在许多实际问题中,衡量一个方案的好坏标准往往不止一个,例如设计一个导弹,既要射程最远,又要燃料最省,还要精度最高.这一类问题统称为多目标最优化问题或多目标规划问题.我们先来看一个投资问题的例子.,2023/11/3,数学建模,多目标规划,引例1.投资问题某公司在一段时间内有a(亿元)的资金可用于建厂投资。
若可供选择的项目记为1,2,m。
而且一旦对第i个项目投资就用去ai亿元;而这段时间内可得收益ci亿元。
问如何确定最佳的投资方案?
最佳投资方案:
投资最少,收益最大!
2023/11/3,数学建模,投资最少:
约束条件为:
收益最大:
我们希望购买DVD的总数量最小,即:
由此,可以得到问题三的双目标整数线性规划模型如下:
表2当时最小购买量的值,续上表,我们利用规划模型求得每种DVD的购买量后,需要对其进行可行性校验,测试此结果是否可以满足一个月内比例为95%的会员得到他想看的DVD,且具有尽可能大的总体满意度.,校验方法:
(一)根据订单和求得的DVD购买数量,利用问题二的规划模型进行第一次分配,对分配情况:
租赁的会员,DVD的分配情况,剩余的各种DVD数量作记录;同时将已租赁的会员在满意指数矩阵的指数全变为0,即不考虑对其进行第二次分配.,
(二)随机从第一次得到DVD的会员中抽取60%,将这部分人所还回的DVD与第一次分配余下的DVD合在一起,作为第二次分配时各种DVD的现有量.然后,利用问题二的0-1线性规划模型对第一次未分配到DVD的会员进行第二次分配;,(三)统计出经过两次分配后,得到DVD的会员的比例,若大于95%,则此次分配成功.利用这种算法进行多次随机模拟,若大多数情况下可以使得到DVD的会员大于95%,则认为模型三是合理的.,校验结果:
因为每次检验需时约1小时,我们只对问题三求得的结果进行了7次模拟,其中6次符合要求(观看比例大于95%).下面给出7次模拟得到的观看比例(表3):
表37次模拟结果每次的观看比例列表,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优化 模型