《最优化模型的建立步骤.ppt》由会员分享，可在线阅读，更多相关《最优化模型的建立步骤.ppt（94页珍藏版）》请在三一办公上搜索。
1、2011/6,华丽的数模之旅开始了,梦想点燃激情，激情成就未来,本次数学建模集训班（2011年全国大学生数学建模竞赛预备班）共有来自全校13个分院328位同学报名，经过数学建模教练组的认真审查遴选，共有232名同学进入提高班学习。,提高班将分两个班进行，其中提高班1班，将采用上午上课，下午上机练习；提高班2采用下午上课，晚上上机练习方式进行，每周末提高课结束后将会有适当的练习留给大家，请大家务必在次周周三晚21点前上交作业电子版，作业提交邮箱，提高班1：;提高班2：，作业以附件形式提交，文件名：XXX第X次作业,集训班概况及相关要求,上机地点：求中502，503；主要提供给没有电脑的同学使用，
2、并请自备U盘，有电脑的同学也可选择到机房或在宿舍里自行完成，我们需要的是过程，更重要的是实效，因此请每个人都自觉完成。,机房开放时间：每周周六下午、晚上；周日全天；上午：8：3011：30 下午1：3016：30，晚：18：0021：00,个人电脑需要安装的软件：matlab,lingo,spss等,其中word里要把公式编辑器装上，或装上mathtype;,2010 计量数模QQ群：94504719，请大家加入；其中群共享里可以下载到每次课的课件；另外有问题也可以在里面询问，讨论，这是一个大家共同探讨心声的地方。,提高班将在5月底结束，根据个人意愿、提高班表现、校赛成绩等择优选拔120人左右
3、进入暑假全国大学生数学建模竞赛集训队，根据集训效果再选拔约100人左右参加全国比赛，本部组队25支左右，其中现科单独组队58支。,我们的数模之旅。,2010年9月中旬cumcm华山论剑,2010年4月启程,2010年5月底jlmcm小试牛刀,2010年7月中旬cumcm集训第一阶段（3 weeks）,2010年8月下旬cumcm集训第二阶段（15d）,2010年11月mcm&icm集训第一阶段,2011年1月mcm&icm集训第二阶段,2011年2月mcm&icm武林大会,本次提高班的具体安排,1.第6周周六：规划模型、案例及软件求解（王义康）2.第7周周六：统计回归模型及软件求解（刘学艺）3
4、.第8周周日：微分方程模型及软件求解（尚绪凤）4.第10周周六：多元统计模型及软件求解（沈进东）5.第11周周日：排队论模型及蒙特卡洛模拟（柴中林）6.第12周周六：网络优化模型及案例分析（赵承业）第二届中国计量学院数学建模竞赛（5.245.31）,历届竞赛赛题基本解法,历届竞赛赛题基本解法,历届竞赛赛题基本解法,历届竞赛赛题基本解法,规划模型、案例及软件求解,一、引言,二、线性规划模型及软件求解,三、整数规划模型,四、0-1规划模型,五、几种常用的线性规划模型,八、非线性规划模型（暑假）,六、多目标规划模型,七、二次规划（暑假）,在数模竞赛过程中，规划模型是最常见的一,类数学模型.从92-0
5、9年全国大学生数模竞赛试题,的解题方法统计结果来看，规划模型共出现了18,次，占到了近50%，也就是说每两道竞赛题中就有,一道涉及到利用规划理论来分析、求解.,如何来分配有限资源，从而达到人们期望目标的优化分配数学模型.它在数学建模中处于中心的地位.这类问题一般可以归结为数学规划模型.规划模型的应用极其广泛，其作用已为越来越多的人所重视.,一、引言,（一）规划模型的数学描述,规划模型的一般意义,“受约束于”之意,（二）规划模型的分类,1.根据是否存在约束条件 有约束问题和无约束问题。2.根据决策变量的性质 静态问题和动态问题。,3.根据目标函数和约束条件表达式的性质 线性规划，非线性规划，二次
6、规划，多目标规划等。,（1）非线性规划目标函数和约束条件中，至少有一个非线性函数。,（2）线性规划（LP）,目标函数和所有的约束条件都是设计变量的线性函数。,（3）二次规划问题目标函数为二次函数，约束条件为线性约束,5.根据变量具有确定值还是随机值 确定规划和随机规划。,4.根据决策变量的允许值,整数规划（0-1规划）和实数规划。,（三）建立规划模型的一般步骤,1.确定决策变量和目标变量；2.确定目标函数的表达式；3.寻找约束条件。,二、线性规划模型及软件求解,例1：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为4
7、00、600和500，且已知用两种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：,解答,例2：某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15小时/件，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费
8、用最省，该工厂应聘一级、二级检验员各几名？,解 设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：,因检验员错检而造成的损失为：,故目标函数为：,约束条件为：,线性规划模型：,解答,返 回,线性规划模型的求解,Lingo与Lindo求解,Matlab求解,Lingo与Lindo,Lindo与Lingo都是LINDO系统公司开发的专门用于求解最优化问题的软件包。与Lindo相比，Lingo软件主要具有两大优点：（1）除具有LINDO的全部功能外，还可用于求解非线性规划问题，包括非线性整数规划问题。（2）LINGO包含了内置的建模语言，允许以简练、直观的方式描述较大规模的优化问
9、题，模型中所需的数据可以以一定格式保存在独立的文件中。,例1的Lingo求解,model:min=13*x1+9*x2+10*x3+11*x4+12*x5+8*x6;x1+x4=400;x2+x5=600;x3+x6=500;0.4*x1+1.1*x2+x3800;0.5*x1+1.2*x2+1.3*x3900;end,例2的Lingo求解,!例2的Lingo求解;model:min=40*x1+36*x2;5*x1+3*x2=45;x1=9;x2=15;end,例3 加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，
10、买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,时间480小时,至多加工100公斤A1,综上所述,Max z=72x1+64x2；s.t.x1+x250，12x1+8x2480，3x1100，x1，x20,Matlab解答,Lingo模型,这是一个（连 续）线性规划（LP）问题,“LINGO|Solve”求解结果报告,“LINGO|Range”敏感性分
11、析,max=72*x1+64*x2;x1+x2=50;12*x1+8*x2=480;3*x1=100;,灵敏度分析,敏感性分析的作用是给出“Ranges in which the basis is unchanged”，即研究当目标函数的系数和约束右端项在什么范围变化（此时假定其他系数保持不变）时，最优基（矩阵）保持不变。注意：这里LINGO不询问是否进行敏感性分析。如果需要进行敏感性分析，必须用“LINGO|Options”命令打开系统选项对话框，在“General Solver”标签下的“Dual Computations”下拉列表中选中“Prices&Range”，再按下“OK”按钮激活
12、敏感性分析功能。修改了系统选项后，以后只需调用“LINGO|Range”命令即可进行敏感性分析了。,修改运行时的内存限制,激活灵敏度分析,结 论,应该批准用35元买1桶牛奶的投资，但每天最多购买10桶牛奶。可以用低于2元/h的工资聘用临时工人以增加劳动时间，但最多增加53.3333h。若每千克A1的获利增加到30元，则x1系数变为303=90，在允许的范围内，所以不应改变生产计划，但最优值变为9020+6430=3720。,例 4 SAILCO公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是40条，60条，75条，25条，这些需求必须按时满足。每个季度正常的生产能力是40条帆船
13、，每条船的生产费用为400美元。如果加班生产，每条船的生产费用为450美元。每个季度末，每条船的库存费用为20美元，假定生产提前期为0，初始库存为10条船。如何安排生产可使总费用最小？,DEM需求量，RP正常生产的产量，OP加班生产的产量，INV库存量目标函数：,约束条件：能力限制RP(I)40，I=1，2，3，4 产品数量的平衡方程 INV（I）INV（I1）RP（I）OP（I）DEM（I），INV（）10；变量的非负约束,Lingo优化模型,集合,属性,集合的属性相当于以集合的元素为下标的数组,Lingo模型的基本要素,（1）集合段（SETS）（2）目标与约束段（3）数据段（DATA）：作
14、用在于对集合的属性（数组）输入必要的常数数据。格式为：attribute(属性)=value _list(常数列表);常数列表（value _list）中数据之间可以用逗号“,”分开，也可以用空格分开（回车的作用也等价于一个空格）“变量名=?;”运行时赋值（4）初始段（INIT）赋初值（5）计算段（CALC）预处理,MATLAB中有关求解线性规划问题的指令,X=linprog(c,A,b,Aeq,beq)X=linprog(c,A,b,Aeq,beq,vlb,vub)X=linprog(c,A,b,Aeq,beq,vlb,vub,x0)X=linprog(c,A,b,Aeq,beq,vlb,v
15、ub,x0,options)x,fval,exitflag,output=linprog(),用MATLAB优化工具箱解线性规划,命令：x=linprog（c，A，b）,2、模型：min z=cX,命令：x=linprog（c，A，b，Aeq,beq）,注意：若没有不等式：存在，则令A=，b=.,命令：1 x=linprog（c，A，b，Aeq,beq,VLB，VUB）2 x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）,注意：1 若没有等式约束:,则令Aeq=,beq=.2其中X0表示初始点,4、命令：x,fval=linprog()返回最优解及处的目标函数值fval.
16、,解 编写M文件xxgh1.m如下：c=-0.4-0.28-0.32-0.72-0.64-0.6;A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08;b=850;700;100;900;Aeq=;beq=;vlb=0;0;0;0;0;0;vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),To Matlab(xxgh1),解:编写M文件xxgh2.m如下：c=6 3 4;A=0 1 0;b=50;Aeq=1 1 1;beq=120;vlb=3
17、0,0,20;vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),To Matlab(xxgh2),例1的Matlab求解,问题,编写M文件xxgh3.m如下: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),To Matlab(xxgh3),结果:x=0.0
18、000 600.0000 0.0000 400.0000 0.0000 500.0000fval=1.3800e+004 即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800。,例2的Matlab求解,问题,改写为：,编写M文件xxgh4.m如下：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),To Matlab(xxgh4),结果为：x=9.0000 0.00
19、00fval=360即只需聘用9个一级检验员。,注：本问题应还有一个约束条件：x1、x2取整数。故它是一个整数线性规划问题。这里把它当成一个线性规划来解，求得其最优解刚好是整数：x1=9，x2=0，故它就是该整数规划的最优解。若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解。,例3的Matlab求解,问题,max=72*x1+64*x2;x1+x2=50;12*x1+8*x2=480;3*x1=100;,编写M文件如下：c=-72-64;A=1 1;12 8;3 0;b=50 480 100;Aeq=;beq=;%调用linprog
20、函数：x,fval=linprog(c,A,b,Aeq,beq),结果为：x=20.0000 30.0000fval=-3.3600e+003即用20桶牛奶生产X1，30桶牛奶生产X2。,五、几种常用的线性规划模型,设某种物资共有 m 个产地 A1，A2，Am，各产地的产量分别是a1，a2，am；有n 个销地 B1，B2，Bn，各销地的销量分别为b1，b2，bn.假定从产地Ai（i=1，2，m）向销地Bj（j=1，2，n）运输单位物资的运价是cij，问怎样调运才能使总运费最小？,问题1 运输问题,1、产销平衡问题,即,设 xij 表示产地 Ai 运往销地 Bj(i=1,2,m;j=1,2,n)
21、的运量.,2、产销不平衡问题,当,当,问题2 生产组织与计划问题,工厂用 种设备 生产 种产品 在一个生产周期内,已知第 台设备 只能工作 个机时.工厂必须完成产品 至少 件.设备 生产 所需要的机时和成本分别为 试建立相应的数学模型,使设备能在计划周期内完成计划但又使成本达到最低.,模型为,问题3 工厂选址问题,设有 个需求点（城市,仓库,商店等）,有 个可供选择的建厂地址,每个地址最多可建一个工厂.在 地址建立工厂的生产能力为 在 地址经营工厂,单位时间的固定成本为 需求点 的需求量为 从厂址 到需求点 的单位运费为 问应如何选择厂址和安排运输计划,使相应的成本为最小.,模型为,上式中 的
22、意义是:,这样的线性规划称为混合型的整数线性规划.,问题4 设备购置和安装问题,工厂需要 种设备 设备 的单价为 工厂已有第 种设备 台,今有资金元,可用于购置这些设备.该厂有 处可安装这些设备,处最多可安装 台,将一台设备 安装在 处,经济效益为 元,问应如何购置和安装这些设备,才能使总的经济效益最高.,以 表示设备 在 处安装的台数,表示购置,的台数,则模型为,问题5 货郎问题,货郎要到 个地方去卖货.已知两个地方 和 之间的距离为 如何选择一条道路,使得货郎每个地方走一遍后回到起点,且所走的路径最短.,定义,则相应的模型为,问题6 系统可靠性问题,选择 个元件,组成一个并联系统.设第 个
23、位置所用的元件可从集合 中挑选.对元件 用 表示元件 在第 个位置上的花费,表示其可靠性的概率,问应如何配置各位置上的元件,使得系统的可靠性不小于 且使总费用最小.,定义,总费用为 其可靠性为,若记 则上式可写成,相应的模型转化为 规划.,模型为,六、多目标规划模型,在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高.这一类问题统称为多目标最优化问题或多目标规划问题.我们先来看一个生产计划的例子.,投资的收益和风险,二、基本假设和符号规定,三、模型的建立与分析,1.总体风险用所投资的Si中最大的一个风险来衡量,即max qixi|i
24、=1，2,n,4.模型简化：,a.在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a，使最大的一个风险qixi/Ma，可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。,b若投资者希望总盈利至少达到水平k以上，在风险最小的情况下寻找相应的投资组合。,c投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险、收益赋予权重s（0s1)，s称为投资偏好系数.,四、模型1的求解,由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长a=0.001进行循环搜索，编制程序如下：,a=0;while(1.
25、1-a)1c=-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);ax=xQ=-valplot(a,Q,.)axis(0 0.1 0 0.5)hold ona=a+0.001;end xlabel(a),ylabel(Q),To Matlab（xxgh5）,计算结果：,五、结果分
26、析,4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长 很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和 收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20%，所对应投资方案为:风险度 收益 x0 x1 x2 x3 x4 0.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212,3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。,2.当投资越分散时，投资者承担的风险越小，这与题意一致。即:冒险的投
27、资者会出现集中投资的情况，保守的投资者则尽量分散投资。,1.风险大，收益也大。,某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克,工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20名,可获利9万元.今工厂共有原料60千克,工人150名,又由于其他条件所限甲饮料产量不超过8百箱.问如何安排生产计划,即两种饮料各生产多少使获利最大.进一步讨论:1)若投资0.8万元可增加原料1千克,问应否作这项投资.2)若每百箱甲饮料获利可增加1万元,问应否改变生产计划.,作业（用Lingo和Matlab编程求解）,练习一：,展厅保安监控问题海湾艺术馆考虑安装一系列摄像安全系统以减少其保安费用。下图是海湾艺术馆用于展览的8间展厅的示意图。各展厅之间的通道显示为-。一家保安公司建议在一些通道安装双向摄像机。每架摄象机都可以很好地监控通道两侧的展厅。例如：在通道处安装摄象机，则展厅 1 和 4 就可以完全被监控到，等等。管理层用最少数量的双向摄像机覆盖所有的8间展厅。,练习二：,
