数学建模培训山大课件

优化问题建模1优化问题建模1 优化问题建模010203概况三点击此处输入相关文本内容整体概况概况一点击此处输入相关文本内容概况二点击此处输入相关文本内容2010203概况三整体概况概况一概况二2 优化问题建模优化问题建模n优化问题概述n数学规划模型n组合优化模型n优化算法介绍n评价方法3优化问题建模优化问题概述3 优化问题建模优化问题概述n最优化问题n优化模型n建模步骤4优化问题概述最优化问题4 优化问题建模数学建模中的优化问题n2011-交巡警平台设计n2009-眼科病床的合理安排 n2008高校学生收费问题n2007乘公交看奥运n2006出版社资源配置问题n2005在线租赁问题n2004奥运会临时商业网点优化设计n2003-露天矿生产的车辆安排问题5数学建模中的优化问题2011-交巡警平台设计5 优化问题建模最优化问题n管理-决策-优化n最优化问题 运用科学的方法从若干可行方案中选择一个方案使某种目标达到最优n基本要素：方案 可行方案 目标6最优化问题管理-决策-优化6 优化问题建模优化模型n模型要素 变量可控因素 目标函数优化的动力和依据 约束条件内部条件和外部约束7优化模型模型要素7 优化问题建模解决问题的基本步骤n明确问题：涉及的因素、目标和要求n基本假设：简化问题，剔除非关键因素n分析问题：难点在于确定变量 主动变化因素变量 被动改变因素目标变量或约束左端 不变的因素系数或约束的右端n建立模型：设出变量-写出函数关系n计算求解：以软件求解为主，必要时编写程序n结果分析与应用：结果的可行性、改进方向8解决问题的基本步骤明确问题：涉及的因素、目标和要求8 优化问题建模数学规划模型n基本模型n整数问题n多目标问题n非线性问题9数学规划模型基本模型9 优化问题建模基本模型n模型的形式n建模技巧n模型的求解n结果分析n求解软件n案例分析10基本模型模型的形式10 优化问题建模模型形式11模型形式11 优化问题建模注意事项n变量一般用x,y,z等符号；n系数写在变量前，目标写在约束上面；n约束一定要写全，分析中写了模型中也要写；n变量非负限制只要可以写就要写上；n参数的计算公式不要出现在模型中；n同组约束的个数一定要注明n能简单的不要复杂，能线性的不要非线性n不要出现严格不等号12注意事项变量一般用x,y,z等符号；12 优化问题建模建模技巧n问题分析是基础 问题让你做什么？问题的目标是什么？问题的限制条件有哪些？问题涉及的主要因素？因素之间的逻辑关系？13建模技巧问题分析是基础13 优化问题建模建模技巧n确定变量是关键 已知量 被动改变量 主动改变量变量n变量的类型 内生变量具有实际的含义 逻辑变量表示存在与否、真与假的逻辑关系 辅助变量松弛变量、人工变量、对偶变量等 14建模技巧确定变量是关键14 优化问题建模建模技巧n逻辑关系的数学化是难点 确定各种量之间的逻辑关系 被动改变量用变量和已知量表出 确定被动改变量的约束限制 写出逻辑表达式n逻辑表达式的形式 不超过小于等于 不低于大于等于 15建模技巧逻辑关系的数学化是难点15 优化问题建模n逻辑表达式的类型 数量关系需求量不超过供给量 定义量-某量为若干量的最大值 依存关系一个量的取值依赖于另一个量的取值 特殊要求两个量不能同时大于0.16逻辑表达式的类型16 优化问题建模模型的求解n专业软件linGo 专业软件速度快、精度高，但变量限制n科学计算软件Matlab Scilab 速度快、输入方式单一，不友好n通用软件Excel 数据输入方便，变量限制宽松，但速度慢，精度差17模型的求解专业软件linGo17 优化问题建模结果分析n结果的合理性 是否与实际情况和常识矛盾？n结果的灵敏度 参数改变对结果的影响n改进方案 放松假设、改变约束18结果分析结果的合理性18 优化问题建模求解软件nLingo软件nExcel的规划求解19求解软件Lingo软件19 优化问题建模LinGo软件n简介n使用方法n实例20LinGo软件简介20 优化问题建模LinGo简介n用于求解非线性规划（NLPNONLINEAR PROGRAMMING）和二次规则（QPQUARATIC PROGRAMING）其中LINGO 8.0学生版最多可版最多达300个变量和150个约束的规则问题，其标准版的求解能力亦在104量级以上。虽然LINDO和LINGO不能直接求解目标规划问题,但用序贯式算法可分解成一个个LINDO和LINGO能解决的规划问题。nhttp:/ 优化问题建模使用方法n窗口界面n基本操作 模型输入 求解 结果分析n求解整数线性规划22使用方法窗口界面22 优化问题建模窗口界面23窗口界面23 优化问题建模模型输入n直接输入模式与Lindo类似，不同之处有：1）已model:开始以end结束2)目标函数加等号 max=3）系数与变量之间加*3*x14）每一个不等式结束后加；5）在之前定义整数变量24模型输入直接输入模式与Lindo类似，不同之处有：24 优化问题建模2525 优化问题建模参数输入模式Model:Sets:!定义集合 Endsets Data:！定义数据 Enddata 调用函数与计算 end26参数输入模式Model:26 优化问题建模集合部分返回27集合部分返回27 优化问题建模定义数据返回28定义数据返回28 优化问题建模2929 优化问题建模 调用函数n主要函数：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调用函数主要函数：30 优化问题建模nABS(X)nCOS(X)nEXP(X)nFLOOR(X)nLGM(X)ln(X-1)!nLOG(X)nSIGN(X)-1 if X 0.Otherwise,it returns+1.31ABS(X)31 优化问题建模nSIN(X)nSMAX(X1,X2,.,XN)nSMIN(X1,X2,.,XN)nTAN(X)32SIN(X)32 优化问题建模定义变量nBND(下界,变量,上界)定义有界变量nFREE(变量)定义自由变量33定义变量BND(下界,变量,上界)33 优化问题建模求解n求解按钮n求解菜单34求解求解按钮34 优化问题建模3535 优化问题建模结果36结果36 优化问题建模3737 优化问题建模整数变量的定义n一般整数变量 gin()n0-1整数变量 Bin()放在end之前单个定义38整数变量的定义一般整数变量38 优化问题建模案例分析生产运输问题n某公司有甲乙两个工厂，生产A、B两种产品，两种产品均销往南北两个地区，有关数据如表：参数 市场南方市场北方市场产品A产品B产品A产品B最大销量(件)900120007500 6000单价（元）12171318单位销售费用4534单位运输费用工厂甲1122工厂乙2212市场情况参数市场工厂甲工厂乙产品A 产品B 产品A 产品B生产成本5645制造工时1.5212装配工时322.51.5工时定额制造1200016000 8000 22000装配3000040000生产情况利润最大生产销售计划？39案例分析生产运输问题某公司有甲乙两个工厂，生产A、B两种产 优化问题建模问题分析-基本因素 n产品：类型、总费用、总销售收益、总利润n销地：最大销售量、单位销售价格、单位销售费用、销售数量、运入量、总销售费用n产地：单位成本、制造工时可利用量、组装工时可利用量、单位使用工时、生产的数量、制造工时使用量、组装工时使用量、运出量、总生产费用n产销：单位运输费用、从产地到销地的运量、总运输费用 40问题分析-基本因素产品：类型、总费用、总销售收益、总利润 优化问题建模问题分析-基本关系n运出量=运到销地总量 运入量=从产地运入总量 n生产数量=运出量 销售数量=运入量 n总销售费用=单位销售费用*销售数量 n总生产费用=单位成本*生产的数量 n总运输费用=单位运输费用*运量 n工时使用量=单位使用工时*生产的数量 n 使用量=可用量 销售数量=最大销售量41问题分析-基本关系运出量=运到销地总量运入量=从产 优化问题建模n总费用=总运输费用+总生产费用+总销售费用 n总收益=单位销售价格*销售数量 n总利润=总费用-总收益、n基本要素 变量：产品A从产地到销地的运输数量xij,i=1,2,j=1,2，产品B从产地到销地的运输数量yij,i=1,2,j=1,2。中间变量：42总费用=总运输费用+总生产费用+总销售费用42 优化问题建模目标函数 约束条件43目标函数43 优化问题建模模型s.t.44模型s.t.44 优化问题建模4545 优化问题建模4646 优化问题建模4747 优化问题建模结果分析n如果要增加利润首先应扩大销售量还是增加工时？n如果要扩大销售量应首选南方市场还是北方市场n扩大产品销售量是应首选产品A还是产品B？n如果增加工时定额，应该首先增加那个工厂的那个车间的定时？n当产品B在南方市场的价格发生变化时决策应如何做出？48结果分析如果要增加利润首先应扩大销售量还是增加工时？48 优化问题建模4949 优化问题建模5050 优化问题建模5151 优化问题建模5252 优化问题建模5353 优化问题建模5454 优化问题建模n销售量增加2个单位55销售量增加2个单位55 优化问题建模整数问题n整数问题特征n整数规划模型n整数规划与线性规划的关系n整数规划的求解n应用案例56整数问题整数问题特征56 优化问题建模整数问题特点n特征变量整数性要求n来源 问题本身的要求 引入的逻辑变量的需要n性质可行域是离散集合57整数问题特点特征变量整数性要求57 优化问题建模图例最优化方法课件58图例最优化方法课件58 优化问题建模整数规划模型n一般整数规划模型n0-1整数规划模型n混合整数规划模型59整数规划模型一般整数规划模型59 优化问题建模一般整数规划模型60一般整数规划模型60 优化问题建模0-1整数规划模型610-1整数规划模型61 优化问题建模混合整数规划模型62混合整数规划模型62 优化问题建模与线性规划的关系整数规划放松的线性规划可行解是放松问题的可行解最优值大于等于放松问题的最优值63与线性规划的关系整数规划放松的线性规划可行解是放松问题的可行 优化问题建模6464 优化问题建模6565 优化问题建模注释n最优解不一定在顶点上达到n最优解不一定是放松问题最优解的邻近整数解n整数可行解远多余于顶点，枚举法不可取66注释最优解不一定在顶点上达到66 优化问题建模整数规划求解nLinGo整数变量输入nBIN（）nGIN（）67整数规划求解LinGo整数变量输入67 优化问题建模应用案例-人力资源分配问题n某个中型百货商场对售货人员（周工资200元）的需求经统计如下表 为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？星期 一二三四五六七人数 12151214161819返回68应用案例-人力资源分配问题某个中型百货商场对售货人员（周工 优化问题建模模型假设n每天工作8小时，不考虑夜班的情况；n每个人的休息时间为连续的两天时间；n每天安排的人员数不得低于需求量，但可以超过需求量69模型假设每天工作8小时，不考虑夜班的情况；69 优化问题建模问题分析因素：不可变因素：需求量、休息时间、单位费用；可变因素：安排的人数、每人工作的时间、总费用；方案：确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。变量：每天开始休息的人数 约束条件：1.每人休息时间2天，自然满足。70问题分析因素：不可变因素：需求量、休息时间、单位费用；可变因 优化问题建模 3.变量非负约束：713.变量非负约束：71 优化问题建模目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于72目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人 优化问题建模模型73模型73 优化问题建模计算返回74计算返回74 优化问题建模7575 优化问题建模多目标决策问题 应用实例问题模型问题特征76多目标决策问题应用实例76 优化问题建模多目标规划问题某市计划发展委员会安排下一个年度的重大项目规划，计划一年安排总投资不超过8亿元，经过初期筛选选中12项可供考虑，每个项目需要投资的数量（单位千万元）、建成后的年利润（单位千万元）、每年废物排放量（单位万吨）和租用的劳动力（单位千人）如下表所示，为了保护环境该市签订了环保责任书，承诺新增废物量不超过20万吨，从经济的角度要求利润尽可能的高，从社会发展的角度讲要求新增就业岗位尽量多，问应如何选择投资项目？77多目标规划问题某市计划发展委员会安排下一个年度的重大项目规划 优化问题建模项目123456789101112投资2.45.2116.217213.56.14.8158.530利润0.4132450.71.51.242.36废物0.32333510.51.4224劳动力0.61.122.81.52.60.71.51211.278项目123456789101112投资2.45.2116.2 优化问题建模问题分析是否投资总投资额总利润废物排放总量劳动力使用总量投资 79问题分析是否投资投资79 优化问题建模模 型80模型80 优化问题建模特征约束是线性整数约束；目标有两个，均为线性函数；都为求最大81特征约束是线性整数约束；81 优化问题建模有效解n多目标的难点n有效解n弱有效解82有效解多目标的难点82 优化问题建模多目标的难点绝对最优解使每个目标都达到最优的可行解83多目标的难点绝对最优解使每个目标都达到最优的可行解83 优化问题建模n绝对最优解不一定存在n不同的目标在不同的可行解上达到最优84绝对最优解不一定存在84 优化问题建模有效解若对于某个可行解x不存在可行解y使得则称可行解x为有效解85有效解若对于某个可行解x不存在可行解y使得则称可行解x为有效 优化问题建模弱有效解若对于某个可行解x不存在可行解y使得则称可行解x为弱有效解 弱有效解包含有效解86弱有效解若对于某个可行解x不存在可行解y使得则称可行解x为弱 优化问题建模求解有效解的方法n理想点法n平方和加权法n虚拟目标法n线性加权和法n最小最大法n乘除法n优先级法87求解有效解的方法理想点法87 优化问题建模理想点法 以单目标最优值为理想值使函数与理想值的差的平方和最小n求理想值n写出评价函数n求评价函数最优88理想点法以单目标最优值为理想值使函数与理想值的差的平方和最 优化问题建模平方和加权法使函数与某一下界的差的平方和最小n确定下界n写出评价函数n求评价函数最优89平方和加权法使函数与某一下界的差的平方和最小确定下界89 优化问题建模虚拟目标法返回使函数与虚拟目标的差的平方和最小n确定下界n写出评价函数n求评价函数最优90虚拟目标法返回使函数与虚拟目标的差的平方和最小确定下界90 优化问题建模线性加权平均法 以目标函数的加权平均值为评价函数n确定权系数n写出评价函数n求评价函数最优91线性加权平均法以目标函数的加权平均值为评价函数确定权系数9 优化问题建模最小最大法以最坏的目标函数值为评价函数值n对给定的可 行 解 求最 坏 的 目标函数值n求评价函数最优92最小最大法以最坏的目标函数值为评价函数值对给定的可行解求最坏 优化问题建模乘除法适用既有求最大又有求最小的多目标问题n写出评价函数n求评价函数最优93乘除法适用既有求最大又有求最小的多目标问题写出评价函数93 优化问题建模优先级法返回适用于目标有明显的轻重之分的问题n确定优先级n求第一级单目标最优n以第一级单目标等于最优值为约束求第二级目标最优94优先级法返回适用于目标有明显的轻重之分的问题确定优先级94 优化问题建模目标规划n问题n模型n求解方法n应用95目标规划问题95 优化问题建模问题彩虹集团是一家集生产与外贸于一体的大型公司，它在上海和深圳都有自己的生产和销售机构拟在下一年度招聘三个专业的职工170人。具体招聘计划见下表：专业 生产管理营销管理财务管理人员 202530204035城市 上海 深圳 上海 深圳 上海 深圳应聘人员经严格审核，初选了180人。按适合从事专业，本人志向专业和希望工作的地点共分为6大类。96问题彩虹集团是一家集生产与外贸于一体的大型公司，它在上海和深 优化问题建模类别 人数适合专业意愿专业 意愿城市125生产、营销生产上海235营销、财务营销上海320生产、财务生产深圳440生产、财务财务深圳534营销、财务财务上海626财务财务深圳97类别人数适合专业意愿专业意愿城市125生产、营销生产上海23 优化问题建模现需要安排人选，希望：n集团按计划录用满在各城市适合从事该专业的职员n80%以上人员能够从事志向专业n80%以上的人员能去意愿城市98现需要安排人选，希望：98 优化问题建模分 析本安排需要确定不同类型的人在不同城市从事不同工作的人数 第一类人分别在上海从事生产、营销和在深圳从事生产、营销的人数 第二类人分别在上海从事营销、财务和在深圳从事营销、财务的人数 第三类人分别在上海从事生产、财务和在深圳从事生产、财务的人数 第四类人分别在上海从事生产、财务和在深圳从事生产、财务的人数 第五类人分别在上海从事营销、财务和在深圳从事营销、财务的人数 第六类人分别在上海从事财务和在深圳从事财务的人数99分析本安排需要确定不同类型的人在不同城市从事不同工作的 优化问题建模显然要求每类聘用人数之和不超过该类总人数，记每类总人数为则有在上海和深圳从事生产、营销和财务的人员等于需求人数，即100显然要求每类聘用人数之和不超过该类总人数，记每类总人数为则有 优化问题建模从事志向专业的人数满足在意愿城市工作的人数满足101从事志向专业的人数满足在意愿城市工作的人数满足101 优化问题建模求解102求解102 优化问题建模结果103结果103 优化问题建模备注n没有可行的安排，因而必须放松约束。n约束分为客观约束（刚性约束）和主观约束（弹性约束）客观约束不可放松 主观约束是目标要求，当不能实现时可以降低要求n当有多个主观约束时需要确定放松哪一个放松多少可以有可行方案，同时放松的程度越少越好。或者说确定这些主观目标的实现程度。104备注没有可行的安排，因而必须放松约束。104 优化问题建模解决思路n首先给每一个主观目标两个变量，分别表示其超出量和不足量，分别记为d+、d-，要求两者不同时大于零。n然后根据目标的性质对他们提出要求：n如果目标是某个量不低于某个值，目标满足时不足量为0，在不能满足目标时要求不足量越小越好。n如果目标是某个量不超过某个值，目标满足时超出量为0，在不能满足目标时要求超出量越小越好。n如果目标是某个量等于某个值，目标满足时超出量和不足量都为0，在不能满足目标时要求超出量和不足量越小越好。这样就得到了一个关于目标超出量和不足量的多目标规划我们称为目标规划，也称为目的规划。105解决思路首先给每一个主观目标两个变量，分别表示其超出量和不足 优化问题建模实例上述问题中的刚性约束是每类聘用总人数的限制，其他约束都是弹性约束。需求约束为等式约束，如上海对生产人员的需求约束为引入超出和不足变量后变为由于是等式要求，所以要求超出量和不足量都尽量少，等价于106实例上述问题中的刚性约束是每类聘用总人数的限制，其他约束都是 优化问题建模其他五个需求约束类似可得分别要求下式达到最小107其他五个需求约束类似可得分别要求下式达到最小107 优化问题建模志向专业约束为不等式约束，要求不足变量最小，对应约束变为在意愿城市工作的人数约束夜市不等式约束要求不足变量最小，对应约束变为108志向专业约束为不等式约束，要求不足变量最小，对应约束变为在意 优化问题建模目标规划模型109目标规划模型109 优化问题建模110110 优化问题建模n目标的重要性存在明显差异，首先应该保证能满足需要，然后再考虑个人专业发展，最后考虑地域要求。因此把目标分成三个层次，同层次里目标的重要性相当，不同层次有主次之分。n同层次里的目标加权求和，得到一个有优先级得多目标规划，写成如下形式111目标的重要性存在明显差异，首先应该保证能满足需要，然后再考虑 优化问题建模目标规划112目标规划112 优化问题建模113113 优化问题建模案例分析n北方化工厂现在有职工120人，其中生产工人105名。主要设备是2套提取生产线，每套生产线容量为800kg，至少需要10人看管。该厂每天24小时连续生产，节假日不停机。原料投入到成品出现平均需要10小时，成品率约为60%，该厂只有4吨卡车一辆，可供原材料运输。n该厂目前的产品可分为5类，所用原料15种，根据厂方提供的资料，经整理得表1。114案例分析北方化工厂现在有职工120人，其中生产工人105名。优化问题建模产品1(%)产品2(%)产品3(%)产品4(%)产品5(%)原料价格(元/kg)原料147.144.447.047.144.45.71原料219.219.720.319.719.20.45原料39.45.44.51.78.60.215原料45.518.720.71.919.70.8原料54.07.06.26.16.210.165原料62.81.80.613.90.494.5原料712.03.000.79.61.31.45产品价格(元/kg)7.58.958.3031.89.8115产品1产品2产品3产品4产品5原料价格原料147.144.4 优化问题建模n3.供销情况n根据现有运输条件，原料3从外地购入，每月只能购入一车。n根据前几个月的购销情况，产品1和产品3应占总产量的70%，产品2的产量最好不要超过总产量的5%，产品1的产量不要低于产品3与产品4产量之和。1163.供销情况116 优化问题建模n问题：n请作该厂的月生产计划，使得该厂的总利润最高。n找出阻碍该厂提高生产能力的瓶颈问题，提出解决办法。117问题：117 优化问题建模非线性规划n非线性规划模型n局部最优解n软件计算n凸二次规划118非线性规划非线性规划模型118 优化问题建模非线性规划模型n目标或约束中有一个以上非线性函数119非线性规划模型目标或约束中有一个以上非线性函数119 优化问题建模局部最优解n在邻域内是最优的局部最优n在可行域里是最优的全局最优解n全局最优解一定是局部最优解局部最优解全局最优解120局部最优解在邻域内是最优的局部最优局部最优解全局最优解12 优化问题建模软件计算nLinGo中与线性规划的求解方法相同，注意结果中是局部最优（Local optimal solution)还是全局最优(Global optimum)。121软件计算LinGo中与线性规划的求解方法相同，注意结果中是局 优化问题建模软件计算nExcel中求解非线性规划需要取消线性假设，并且选择算法。122软件计算Excel中求解非线性规划需要取消线性假设，并且选择 优化问题建模问题提问与解答问答HERE COMES THE QUESTION AND ANSWER SESSION123问题提问与解答问答HERECOMESTHEQUESTI 优化问题建模结束语CONCLUSION感谢参与本课程，也感激大家对我们工作的支持与积极的参与。课程后会发放课程满意度评估表，如果对我们课程或者工作有什么建议和意见，也请写在上边，来自于您的声音是对我们最大的鼓励和帮助，大家在填写评估表的同时，也预祝各位步步高升，真心期待着再次相会！124结束语CONCLUSION感谢参与本课程，也感激大家对我 优化问题建模感谢观看Theusercandemonstrateonaprojectororcomputer,orprintthepresentationandmakeitintoafilm125感谢观看125