《优化模型实训》PPT课件.ppt

提 要,1,2,几类典型优化问题及其软件解法,3,举例,4,最优化概论,MATLAB优化工具箱简介,最优化概论,当今，“优化”无疑是一个热门词。做宏观经济规划要优化资源配置，搞企业经营管理要优化生产计划，作新产品设计要优化性能成本比。就是在人们的日常生活中，优化的要求也比比皆是，消费时，如何花尽可能少的钱办尽可能多的事，出行时，如何走最短的路程到达目的地，等等。总而言之，在经济如此发展，竞争如此剧烈，资源日渐紧张的今天，人们做任何事，无不望求事半功倍之术，以求或提效、或增收、或节约等等之目标。,一、最优化概念,所有类似的这种课题统称为最优化问题，研究解决这些问题的科学一般就总称之为最优化理论和方法另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同，学科分枝很多，因此这个学科名下到底包含哪些分枝，其说法也不一致。比较公认的是：“规划论”（包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划等），“组合最优化”，“对策论”及“最优控制”等等。,数学建模竞赛中的优化问题,2000B 钢管订购和运输问题二次规划2001B 公交车优化调度2001C 基金使用的最优策略-线性规划2002B 彩票中的数学2003B 露天矿生产的车辆安排问题 2004A 奥运会临时超市网点设计问题 2004D 公务员招聘工作中录用方案多目标规划2005B DVD在线租赁2006A 出版社的资源配置问题 2007A 乘公交，看奥运 2008B 高等教育学费探讨2009B 眼科病床的合理安排,数学建模竞赛中的优化问题,2002B，彩票中的数学约束非线性规划,从数学上来看，所谓最优化问题可以概括为这样一种数学模型：给定一个“函数”，F(X)，以及“自变量”X应满足的一定条件，求X为怎样的值时，F(X)取得其最大值或最小值。通常，称F(X)为“目标函数”，X应满足的条件为“约束条件”。约束条件一般用一个集合D表示为：XD。求目标函数F(X)在约束条件XD下的最小值或最大值问题，就是一般最优问题的数学模型,无约束最优化问题,目标函数,二、最优化问题的一般形式,约束最优化问题,约束函数,最优解；最优值,三、最优化问题分类,分类1：无约束最优化 约束最优化,非线性规划：目标函数与约束函数中至少有一个是变量x的非线性函数；,线性规划：目标函数与约束函数均为线性函数；,分类2：线性规划 非线性规划,三、最优化问题分类(续）,分类3（根据决策变量、目标函数和要求不同）,整数规划动态规划网络规划随机规划几何规划多目标规划,三、最优化问题分类(续）,函数最优化组合最优化,分类,函数最优化：决策变量是一定区间内的连续变量,组合最优化：决策变量是离散状态，同时可行域是由有限个点组成的集合,典型组合优化问题：旅行商问题；加工调度问题；0-1背包问题；图着色问题,四、求解最优化问题的方法,（1）传统优化方法-基于导数的优化方法 无约束规划：梯度法、共轭梯度法、拟牛顿法 约束规划：序列二次规划法，罚函数法 线性规划：单纯形方法等（2）现代优化方法-智能优化方法 遗传算法，模拟退火法，蚁群算法，粒子群算法 神经网络算法，禁忌搜索算法等,为了使系统达到最优的目标所提出的各种求解方法称为最优化方法。,最优化方法通常采用迭代法求最优解，过程是：,五、构造数值优化算法的一般过程,或,迭代公式,六、最优化方法的基本结构,七、搜索算法结构框图,八、最优化方法解决问题的步骤,（1）确定变量，写出目标函数和有关约束条件，建立数学模型。（2）分析模型，搞清它属于运筹学哪一分枝，选择合适的最优化方法；（3）编程求解；尽量利用现有的数学软件或最优化软件，比如 Matlab，Mathematica，Lindo，Lingo等，来计算。（4）最优解的验证和实施。,九、MATLAB优化工具箱简介,1.功能（1）求解无约束条件非线性极小值；（2）求解约束条件下非线性极小值，包括目标逼近问题、极大-极小值问题和半无限极小值问题；（3）求解二次规划和线性规划问题；（4）非线性最小二乘逼近和曲线拟合；（5）非线性系统的方程求解；（6）约束条件下的线性最小二乘优化；（7）求解复杂结构的大规模优化问题。,2.常用函数：,3.Options选项说明,输入参数中可以用options，用于所有函数，其中包括有一下参数。（1）Display：结果显示方式，off不显示，iter显示每次迭代的信息，final为最终结果，notify只有当求解不收敛的时候才显示结果。（2）MaxFunEvals：允许函数计算的最大次数，取值为正整数。（3）MaxIter：允许迭代的最大次数，正整数。（4）TolFun：函数值（计算结果）精度，正整数。（5）TolX：自变量的精度，正整数。而且可以用函数optimset创建和修改。,4.输出变量说明,eg1 在区间（0，2）上求函数sin(x)的最小值：,eg2 对边长为3m的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？,学会使用fminbnd函数:功能：找到固定区间内单变量函数的最小值。,线性规划问题及其MATLAB解法,1.线性规划的一般形式,或,线性规划问题及其MATLAB解法,2.线性规划的matlab解法,问题形式1：min z=CTx S.t.Ax b,指令：（x，z）=linprog(f,A,b),问题形式2：min z=CTx S.t.Ax b Aeqx=beq,指令：（x，z）=linprog(f,A,b,Aeq,beq),线性规划问题及其MATLAB解法,问题形式3：min z=CTx S.t.Ax b Aeqx=beq lb x ub,指令：（x，z）=linprog(f,A,b,Aeq,beq,lb,ub),注：若没有不等式约束,可用 替代A和b,若没有等式约束,可用 替代Aeq和beq,若某个xi下无界或上无界,可设定-inf或 inf；,例:,min Z=4x1+3x2,s.t.,解：程序如下,c=4,3;a=1,1;b=5;vlb=-6;-1;%lower bound of vector x%vub=10;4;%upper bound of vector x%X,z=linprog(c,a,b,vlb,vub),例题：裁料问题 在某建筑工程施工中需要制作10000套钢筋，每套钢筋由2.9m、2.1m和1.5m三种不同长度的钢筋各一根组成，它们的直径和材质不同。目前在市场上采购到的同类钢筋的长度每根均为7.4m，问应购进多少根7.4m长的钢筋才能满足工程的需要？,首先分析共有多少种不同的套裁方法，该问题的可能材料方案如表所示。表 材料方案表,设以xi(i=1,2,8)表示按第i种裁料方案下料的原材料数量，则可得该问题的数学模型为：,首先输入下列系数：f=1;1;1;1;1;1;1;1;Aeq=2 0 0 0 0 0 0 0 0 2 1 0 3 2 1 0 1 0 1 3 0 2 3 4;beq=10000 10000 10000;lb=zeros(8,1);,然后调用linprog函数：x,fval,exitflag,output,lambda=linprog(f,Aeq,beq,lb);,习题1：生产计划的最优化问题 某工厂生产A和B两种产品，它们需要经过三种设备的加工，其工时如表所示。设备一、二和三每天可使用的时间分别不超过12、10和8小时。产品A和B的利润随市场的需求有所波动，如果预测未来某个时期内A和B的利润分别为4和3千元/吨，问在那个时期内，每天应安排产品A、B各多少吨，才能使工厂获利最大？表生产产品工时表,习题2：厂址选择问题 考虑A、B、C三地，每地都出产一定数量的原料，也消耗一定数量的产品（见表）。已知制成每吨产品需3吨原料，各地之间的距离为：A-B：150km，A-C：100km，B-C：200km。假定每万吨原料运输1km的运价是5000元，每万吨产品运输1km的运价是6000元。由于地区条件的差异，在不同地点设厂的生产费用也不同。问究竟在哪些地方设厂，规模多大，才能使总费用最小？另外，由于其它条件限制，在B处建厂的规模（生产的产品数量）不能超过5万吨。表 A、B、C三地出产原料、消耗产品情况表,1.整数线性规划一般形式,依照决策变量取整要求的不同，整数规划可分为纯整数规划、混合整数规划、01整数规划。,整数线性规划(ILP)及其lindo解法,部分或者全部为整数,多目标规划及其求解方法,多目标规划的一般形式,则称为线性多目标规划。,其中x=(x1,x2,xn)为一个n维向量；fi(x)为目标函数，hj(x)g i(x)为约束函数。,求解多目标规划的方法,1、降维法，即把多目标 化为比较容易求解的单目标或双目标，如主要目标法、线性加权法、极大极小法、理想点法等；2、分层序列法，即把目标按其重要性给出一个序列，每次都在前一目标最优解集内求下一个目标最优解，直到求出共同的最优解。3、层次分析法，是由美国运筹学家沙旦于70年代提出的，这是一种定性与定量相结合的多目标决策与分析方法，对于目标结构复杂且缺乏必要的数据的情况更为实用。,主要目标法,其基本思想是：在多目标问题中，根据问题的实际情况，确定一个目标为主要目标，而把其余目标作为次要目标，并且根据经验，选取一定的界限值。这样就可以把次要目标作为约束来处理，于是就将原来的多目标问题转化为一个在新的约束下的单目标最优化问题。,线性加权法,其基本思想是：按照多目标fi(x)(i=1,2,m)的重要程度，分别乘以一组权系数j(j=1,2,m)然后相加作为目标函数而构成单目标规划问题。即,其中,极大极小法,其基本思想是：对于极小化的多目标规划，让其中最大的目标函数值尽可能地小.为此，对每个 xR，我们先求诸目标函数值fi(x)的最大值，然后再求这些最大值中的最小值。即构造单目标规划：,为权值系数向量。于是多目标规划问题化为：,理想点法,对于多目标规划：,s.t gj(x)0 j=1,2,n,先设计与目标函数相应的一组目标值理想化向量,再设为一松弛因子标量。设,在Matlab的优化工具箱中，fgoalattain函数用于解决此类问题。其数学模型形式为：min F(x)-weight goalc(x)0 非线性不等式约束ceq(x)=0 非线性等式约束 A xb 线性不等式约束 Aeq x=beq 线性等式约束 lbxub其中，x,weight,goal,b,beq,lb和ub为向量，A和Aeq为矩阵，c(x),ceq(x)和F(x)为函数,调用格式：x=fgoalattain(F,x0,goal,weight)x,fval,attainfactor,exitflag,output,lambda=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options)说明：F为目标函数；x0为初值；goal为F达到的指定目标；weight为参数指定权重；A、b为线性不等式约束的矩阵与向量；Aeq、beq为等式约束的矩阵与向量；lb、ub为变量x的上、下界向量；nonlcon为定义非线性不等式约束函数c(x)和等式约束函数ceq(x)；options中设置优化参数。x返回最优解；fval返回解x处的目标函数值；attainfactor返回解x处的目标达到因子；exitflag描述计算的退出条件；output返回包含优化信息的输出参数；lambda返回包含拉格朗日乘子的参数。,例1：投资组合模型,市场上有n种资产Si(i=1,2,n)可以选择，现用数额为M的相当大的资金作一个时期的投资。财务人员分析估算出这一时期内购买Si的平均收益率为ri,风险损失率为qi,在多项投资组合中，总体风险可用投资的Si中最大的一个风险来度量。购买Si时要付交易费，费率pi(不买无须付费).当购买额不超过给定值ui时，交易费按购买ui计算.另外，假定同期银行存款利率是r0,既无交易费又无风险。(r0=5%),试给该公司设计一种投资组合方案，即用给定达到资金M,有选择地购买若干种资产或存银行生息，使净收益尽可能大，使总体风险尽可能小。,已知n=4时的相关数据如下:,基本假设,1.投资数额M相当大,为了便于计算，假设M=1;2.投资越分散，总的风险越小；3.总体风险Si用投资项目中最大的一个风险来度量；4.n种资产Si之间是相互独立的；5.在投资的这一时期内,ri,pi,qi,r0为定值，不受意外因素影响；6.净收益和总体风险只受ri,pi,qi影响，不受其他因素干扰。,符号规定,Si 第i种投资项目，如股票，债券ri,pi,qi 分别为Si的平均收益率,风险损失率，交易费率ui Si的交易定额,r0 同期银行利率xi 投资项目Si的资金,a 投资风险度Q总体收益,Q总体收益的增量,模型的建立与分析,1.总体风险用所投资的Si中最大的一个风险来衡量,即max qixi|i=1，2,n2购买Si所付交易费是一个分段函数,即 pixi xiui 交易费=piui xiui而题目所给定的定值ui(单位:元)相对总投资M很小,piui更小,可以忽略不计,这样购买Si的净收益为(ri-pi)xi,净收益尽可能大,建立模型,总体风险尽可能小,多目标规划问题,采用主要目标法化为单目标规划,方法一.固定风险水平，优化收益 在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a，使最大的一个风险qixi/Ma，可找到相应的投资方案。,模型一线性规划模型,若投资者希望总盈利至少达到水平k以上，在风险最小的情况下寻找相应的投资组合。,模型二线性规划模型,方法二：固定盈利水平，极小化风险,采用线性加权法化为单目标规划,投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险、收益赋予权重s（0s1)，s称为投资偏好系数.,模型三线性规划模型,模型一的求解,将具体数据代入,模型一如下:,由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长a=0.001进行循环搜索，编制程序如下：,a=0;while(1.1-a)1 c=-0.05-0.27-0.19-0.185-0.185;Aeq=1 1.01 1.02 1.045 1.065;beq=1;A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026;b=a;a;a;a;vlb=0,0,0,0,0;vub=;x,val=linprog(c,A,b,Aeq,beq,vlb,vub);a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001;end xlabel(a),ylabel(Q),计算结果：,风险大，收益也大。曲线上的任一点表示该风险水平的最大可能收益。对于不同风险的承受能力，选择该风险水平下的最优投资组合。,在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是：a*=0.6%，Q*=20%。,此时所对应投资方案为:风险度=0.0060；收益=0.2019；x0=0，x1=0.2400，x2=0.4000，x3=0.1091，x4=0.2212,习题1：某化工厂拟生产两种新产品A和B，其生产设备费用分别为：A，2万元/吨；B，5万元/吨。这两种产品均将造成环境污染，设由公害所造成的损失可折算为：A，4万元/吨；B，1万元/吨。由于条件限制，工厂生产产品A和B的最大生产能力各为每月5吨和6吨，而市场需要这两种产品的总量每月不少于7吨。试问工厂如何安排生产计划，在满足市场需要的前提下，使设备投资和公害损失均达最小。该工厂决策认为，这两个目标中环境污染应优先考虑，设备投资的目标值为20万元，公害损失的目标为12万元。,习题2：某厂生产两种产品A和B，已知生产A产品100kg需8个工时，生产B产品100kg需10个工时。假定每日可用的工时数为40，且希望不雇临时工，也不加班生产。这两种产品每100kg均可获利100元。此外，有个顾客要求每日供应他B种产品600kg。问应如何安排生产计划？,习题3：某工厂因生产需要欲采购一种原材料，市场上的这种原料有两个等级，甲级单价2元/千克，乙级单价1元/千克。要求所花总费用不超过200元，购得原料总量不少于100千克，其中甲级原料不少于50千克，问如何确定最好的采购方案。,定位问题设某城市有某种物品的10个需求点，第i个需求点Pi的坐标为（ai,bi）,道路网与坐标轴平行，彼此正交。现打算建一个该物品的供应中心，且由于受到城市某些条件的限制，该供应中心只能设在x界于5，8，y界于5，8的范围内。问该中心应建在何处为好？Pi点的坐标为：ai:1 4 3 5 9 12 6 20 17 8 bi:2 10 8 18 1 4 5 10 8 9设供应中心的位置为（x,y），要求它到最远需求点的距离尽可能小，由于此处应采用沿道路行走的距离，可知用户Pi到该中心的距离为|x-ai|+|y-bi|，从而可得目标函数如下,约束非线性规划,一般形式：,其中，f(x)为多元实值函数;g(x)，ceq(x)为向量函数,并且f(x),g(x),ceq(x)中至少有一个函数是非线性函数（否则成为线性规划问题）。,