数学建模案例描述ppt课件

.,1,优化问题建模,.,2,优化问题建模,优化问题概述数学规划模型组合优化模型优化算法介绍评价方法,.,3,优化问题概述,最优化问题优化模型建模步骤,.,4,数学建模中的优化问题,2011-交巡警平台设计2009-眼科病床的合理安排2008高校学生收费问题2007乘公交看奥运2006出版社资源配置问题2005在线租赁问题2004奥运会临时商业网点优化设计2003-露天矿生产的车辆安排问题,.,5,最优化问题,管理-决策-优化最优化问题运用科学的方法从若干可行方案中选择一个方案使某种目标达到最优基本要素：方案可行方案目标,.,6,优化模型,模型要素变量可控因素目标函数优化的动力和依据约束条件内部条件和外部约束,.,7,解决问题的基本步骤,明确问题：涉及的因素、目标和要求基本假设：简化问题，剔除非关键因素分析问题：难点在于确定变量主动变化因素变量被动改变因素目标变量或约束左端不变的因素系数或约束的右端建立模型：设出变量-写出函数关系计算求解：以软件求解为主，必要时编写程序结果分析与应用：结果的可行性、改进方向,.,8,数学规划模型,基本模型整数问题多目标问题非线性问题,.,9,基本模型,模型的形式建模技巧模型的求解结果分析求解软件案例分析,.,10,模型形式,.,11,注意事项,变量一般用x,y,z等符号；系数写在变量前，目标写在约束上面；约束一定要写全，分析中写了模型中也要写；变量非负限制只要可以写就要写上；参数的计算公式不要出现在模型中；同组约束的个数一定要注明能简单的不要复杂，能线性的不要非线性不要出现严格不等号,.,12,建模技巧,问题分析是基础问题让你做什么？问题的目标是什么？问题的限制条件有哪些？问题涉及的主要因素？因素之间的逻辑关系？,.,13,建模技巧,确定变量是关键已知量被动改变量主动改变量变量变量的类型内生变量具有实际的含义逻辑变量表示存在与否、真与假的逻辑关系辅助变量松弛变量、人工变量、对偶变量等,.,14,建模技巧,逻辑关系的数学化是难点确定各种量之间的逻辑关系被动改变量用变量和已知量表出确定被动改变量的约束限制写出逻辑表达式逻辑表达式的形式不超过小于等于不低于大于等于,.,15,逻辑表达式的类型数量关系需求量不超过供给量定义量-某量为若干量的最大值依存关系一个量的取值依赖于另一个量的取值特殊要求两个量不能同时大于0.,.,16,模型的求解,专业软件linGo专业软件速度快、精度高，但变量限制科学计算软件MatlabScilab速度快、输入方式单一，不友好通用软件Excel数据输入方便，变量限制宽松，但速度慢，精度差,.,17,结果分析,结果的合理性是否与实际情况和常识矛盾？结果的灵敏度参数改变对结果的影响改进方案放松假设、改变约束,.,18,求解软件,Lingo软件Excel的规划求解,.,19,LinGo软件,简介使用方法实例,.,20,LinGo简介,用于求解非线性规划（NLPNONLINEARPROGRAMMING）和二次规则（QPQUARATICPROGRAMING）其中LINGO8.0学生版最多可版最多达300个变量和150个约束的规则问题，其标准版的求解能力亦在104量级以上。虽然LINDO和LINGO不能直接求解目标规划问题,但用序贯式算法可分解成一个个LINDO和LINGO能解决的规划问题。,.,21,使用方法,窗口界面基本操作模型输入求解结果分析求解整数线性规划,.,22,窗口界面,.,23,模型输入,直接输入模式与Lindo类似，不同之处有：1）已model:开始以end结束2)目标函数加等号max=3）系数与变量之间加*3*x14）每一个不等式结束后加；5）在之前定义整数变量,.,24,.,25,参数输入模式,Model:Sets:!定义集合EndsetsData:！定义数据Enddata调用函数与计算end,.,26,集合部分,返回,.,27,定义数据,返回,.,28,.,29,调用函数,主要函数：for(set(set_index_list)|condition:expression)sum(set(set_index_list)|condition:expression)min(max)(set(set_index_list)|condition:expression)IF(logical_condition,true_result,false_result),.,30,ABS(X)COS(X)EXP(X)FLOOR(X)LGM(X)ln(X-1)!LOG(X)SIGN(X)-1ifX0.Otherwise,itreturns+1.,.,31,SIN(X)SMAX(X1,X2,.,XN)SMIN(X1,X2,.,XN)TAN(X),.,32,定义变量,BND(下界,变量,上界)定义有界变量FREE(变量)定义自由变量,.,33,求解,求解按钮求解菜单,.,34,.,35,结果,.,36,.,37,整数变量的定义,一般整数变量gin()0-1整数变量Bin()放在end之前单个定义,.,38,案例分析生产运输问题,某公司有甲乙两个工厂，生产A、B两种产品，两种产品均销往南北两个地区，有关数据如表：,市场情况,生产情况,利润最大生产销售计划？,.,39,问题分析-基本因素,产品：类型、总费用、总销售收益、总利润销地：最大销售量、单位销售价格、单位销售费用、销售数量、运入量、总销售费用产地：单位成本、制造工时可利用量、组装工时可利用量、单位使用工时、生产的数量、制造工时使用量、组装工时使用量、运出量、总生产费用产销：单位运输费用、从产地到销地的运量、总运输费用,.,40,问题分析-基本关系,运出量=运到销地总量运入量=从产地运入总量生产数量=运出量销售数量=运入量总销售费用=单位销售费用*销售数量总生产费用=单位成本*生产的数量总运输费用=单位运输费用*运量工时使用量=单位使用工时*生产的数量使用量=可用量销售数量=最大销售量,.,41,总费用=总运输费用+总生产费用+总销售费用总收益=单位销售价格*销售数量总利润=总费用-总收益、基本要素变量：产品A从产地到销地的运输数量xij,i=1,2,j=1,2，产品B从产地到销地的运输数量yij,i=1,2,j=1,2。中间变量：,.,42,目标函数约束条件,.,43,模型,.,44,.,45,.,46,.,47,结果分析,如果要增加利润首先应扩大销售量还是增加工时？如果要扩大销售量应首选南方市场还是北方市场扩大产品销售量是应首选产品A还是产品B？如果增加工时定额，应该首先增加那个工厂的那个车间的定时？当产品B在南方市场的价格发生变化时决策应如何做出？,.,48,.,49,.,50,.,51,.,52,.,53,.,54,销售量增加2个单位,.,55,整数问题,整数问题特征整数规划模型整数规划与线性规划的关系整数规划的求解应用案例,.,56,整数问题特点,特征变量整数性要求来源问题本身的要求引入的逻辑变量的需要性质可行域是离散集合,.,57,图例,最优化方法课件,.,58,整数规划模型,一般整数规划模型0-1整数规划模型混合整数规划模型,.,59,一般整数规划模型,.,60,0-1整数规划模型,.,61,混合整数规划模型,.,62,与线性规划的关系,整数规划,放松的线性规划,可行解是放松问题的可行解,最优值大于等于放松问题的最优值,.,63,.,64,.,65,注释,最优解不一定在顶点上达到最优解不一定是放松问题最优解的邻近整数解整数可行解远多余于顶点，枚举法不可取,.,66,整数规划求解,LinGo整数变量输入BIN（）GIN（）,.,67,应用案例-人力资源分配问题,某个中型百货商场对售货人员（周工资200元）的需求经统计如下表为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？,返回,.,68,模型假设,每天工作8小时，不考虑夜班的情况；每个人的休息时间为连续的两天时间；每天安排的人员数不得低于需求量，但可以超过需求量,.,69,问题分析,因素：不可变因素：需求量、休息时间、单位费用；可变因素：安排的人数、每人工作的时间、总费用；方案：确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。变量：每天开始休息的人数约束条件：1.每人休息时间2天，自然满足。,.,70,3.变量非负约束：,.,71,目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于,.,72,模型,.,73,计算,返回,.,74,.,75,多目标决策问题,应用实例问题模型问题特征,.,76,多目标规划问题,某市计划发展委员会安排下一个年度的重大项目规划，计划一年安排总投资不超过8亿元，经过初期筛选选中12项可供考虑，每个项目需要投资的数量（单位千万元）、建成后的年利润（单位千万元）、每年废物排放量（单位万吨）和租用的劳动力（单位千人）如下表所示，为了保护环境该市签订了环保责任书，承诺新增废物量不超过20万吨，从经济的角度要求利润尽可能的高，从社会发展的角度讲要求新增就业岗位尽量多，问应如何选择投资项目？,.,77,.,78,问题分析,是否投资总投资额总利润废物排放总量劳动力使用总量,投资,.,79,模型,.,80,特征,约束是线性整数约束；目标有两个，均为线性函数；都为求最大,.,81,有效解,多目标的难点有效解弱有效解,.,82,多目标的难点,绝对最优解使每个目标都达到最优的可行解,.,83,绝对最优解不一定存在不同的目标在不同的可行解上达到最优,.,84,有效解,若对于某个可行解x不存在可行解y使得,则称可行解x为有效解,.,85,弱有效解,若对于某个可行解x不存在可行解y使得,则称可行解x为弱有效解,弱有效解包含有效解,.,86,求解有效解的方法,理想点法平方和加权法虚拟目标法线性加权和法最小最大法乘除法优先级法,.,87,理想点法,以单目标最优值为理想值使函数与理想值的差的平方和最小,求理想值写出评价函数求评价函数最优,.,88,平方和加权法,使函数与某一下界的差的平方和最小,确定下界写出评价函数求评价函数最优,.,89,虚拟目标法,返回,使函数与虚拟目标的差的平方和最小,确定下界写出评价函数求评价函数最优,.,90,线性加权平均法,以目标函数的加权平均值为评价函数,确定权系数写出评价函数求评价函数最优,.,91,最小最大法,以最坏的目标函数值为评价函数值,对给定的可行解求最坏的目标函数值求评价函数最优,.,92,乘除法,适用既有求最大又有求最小的多目标问题,写出评价函数求评价函数最优,.,93,优先级法,返回,适用于目标有明显的轻重之分的问题,确定优先级求第一级单目标最优以第一级单目标等于最优值为约束求第二级目标最优,.,94,目标规划,问题模型求解方法应用,.,95,问题,彩虹集团是一家集生产与外贸于一体的大型公司，它在上海和深圳都有自己的生产和销售机构拟在下一年度招聘三个专业的职工170人。具体招聘计划见下表：,应聘人员经严格审核，初选了180人。按适合从事专业，本人志向专业和希望工作的地点共分为6大类。,.,96,.,97,现需要安排人选，希望：集团按计划录用满在各城市适合从事该专业的职员80%以上人员能够从事志向专业80%以上的人员能去意愿城市,.,98,分析,本安排需要确定不同类型的人在不同城市从事不同工作的人数,第一类人分别在上海从事生产、营销和在深圳从事生产、营销的人数,第二类人分别在上海从事营销、财务和在深圳从事营销、财务的人数,第三类人分别在上海从事生产、财务和在深圳从事生产、财务的人数,第四类人分别在上海从事生产、财务和在深圳从事生产、财务的人数,第五类人分别在上海从事营销、财务和在深圳从事营销、财务的人数,第六类人分别在上海从事财务和在深圳从事财务的人数,.,99,显然要求每类聘用人数之和不超过该类总人数，记每类总人数为,则有,在上海和深圳从事生产、营销和财务的人员等于需求人数，即,.,100,从事志向专业的人数满足,在意愿城市工作的人数满足,.,101,求解,.,102,结果,.,103,备注,没有可行的安排，因而必须放松约束。约束分为客观约束（刚性约束）和主观约束（弹性约束）客观约束不可放松主观约束是目标要求，当不能实现时可以降低要求当有多个主观约束时需要确定放松哪一个放松多少可以有可行方案，同时放松的程度越少越好。或者说确定这些主观目标的实现程度。,.,104,解决思路,首先给每一个主观目标两个变量，分别表示其超出量和不足量，分别记为d+、d-，要求两者不同时大于零。然后根据目标的性质对他们提出要求：如果目标是某个量不低于某个值，目标满足时不足量为0，在不能满足目标时要求不足量越小越好。如果目标是某个量不超过某个值，目标满足时超出量为0，在不能满足目标时要求超出量越小越好。如果目标是某个量等于某个值，目标满足时超出量和不足量都为0，在不能满足目标时要求超出量和不足量越小越好。这样就得到了一个关于目标超出量和不足量的多目标规划我们称为目标规划，也称为目的规划。,.,105,实例,上述问题中的刚性约束是每类聘用总人数的限制，其他约束都是弹性约束。需求约束为等式约束，如上海对生产人员的需求约束为,引入超出和不足变量后变为,由于是等式要求，所以要求超出量和不足量都尽量少，等价于,.,106,其他五个需求约束类似可得,分别要求下式达到最小,.,107,志向专业约束为不等式约束，要求不足变量最小，对应约束变为,在意愿城市工作的人数约束夜市不等式约束要求不足变量最小，对应约束变为,.,108,目标规划模型,.,109,.,110,目标的重要性存在明显差异，首先应该保证能满足需要，然后再考虑个人专业发展，最后考虑地域要求。因此把目标分成三个层次，同层次里目标的重要性相当，不同层次有主次之分。同层次里的目标加权求和，得到一个有优先级得多目标规划，写成如下形式,.,111,目标规划,.,112,.,113,案例分析,北方化工厂现在有职工120人，其中生产工人105名。主要设备是2套提取生产线，每套生产线容量为800kg，至