优化建模方法课件.ppt

关于优化建模方法现在学习的是第1页，共43页2022-9-2 数学模型是对实际所研究问题的一种抽象，基于数学理论和方法，把客观事物的本质属性与其内在联系刻画出来并用数学符号、数学关系式、数学命题、图形图表等来表示的一种表达形式。数学模型数学模型如，牛顿第二 定律：maF 现在学习的是第2页，共43页2022-9-2数学建模过程数学建模过程表述（归纳）求解（演绎）解释验证现实对象与数学模型的关系现实对象与数学模型的关系现在学习的是第3页，共43页2022-9-2机理分析法：机理分析法：以经典数学为工具，分析其内部的机理规律。maF 统计分析法：统计分析法：以随机数学为基础，经过对统计数据进行分 析，得到其内在的规律。如：多元统计分析。系统分析法：系统分析法：对复杂性问题或主观性问题的研究方法。把 定性的思维和结论用定量的手段表示出来。如：层次分析法。数学建模方法数学建模方法现在学习的是第4页，共43页2022-9-2建立数学模型的方法建立数学模型的方法层次分析法层次分析法最小二乘法最小二乘法差分法差分法定性理论法定性理论法优化法优化法变分法变分法回归分析法回归分析法机理分析法机理分析法统计分析法统计分析法聚类分析法聚类分析法主成分分析法主成分分析法马尔科夫预测法马尔科夫预测法系统分析法系统分析法模糊数学法模糊数学法灰色系统法灰色系统法现在学习的是第5页，共43页2022-9-2n优化方法优化方法n数据拟合方法数据拟合方法n差分方程方法差分方程方法n层次分析方法层次分析方法现在学习的是第6页，共43页2022-9-2现在学习的是第7页，共43页2022-9-2（一）优化模型的数学描述（一）优化模型的数学描述下的最大值或最小值，其中下的最大值或最小值，其中.,.,)(mihi210 x.,.,),)()(piggii2100 xx设计变量（决策变量）设计变量（决策变量）目标函数目标函数),.,(nxxxx321x求函数求函数)(xfu 在约束条件在约束条件和和x)(xf x 可行域可行域现在学习的是第8页，共43页2022-9-2.,.,)(.mihtsi210 x.,.,),)()(piggii2100 xx xxfu )(max)min(ortosubjectts .“受约束于”之意现在学习的是第9页，共43页2022-9-2（1）非线性规划）非线性规划目标函数和约束条件中，至少有一个非线性函数。目标函数和约束条件中，至少有一个非线性函数。.,.,)(.mihtsi210 x.,.,),)()(piggii2100 xx xxfu )(min现在学习的是第10页，共43页2022-9-2.,.,.,.,.minnixnibxatsxcuinkikikniii2102111（2）线性规划（）线性规划（LP） 目标函数和所有的约束条件都是设计变量的目标函数和所有的约束条件都是设计变量的线性函数。线性函数。现在学习的是第11页，共43页2022-9-2（3）二次规划问题）二次规划问题目标函数为二次函数，约束条件为线性约束目标函数为二次函数，约束条件为线性约束.,.,.,.,.)(min,nixnibxatsxxbxcxfuinjijijnjijiijniii2102121111现在学习的是第12页，共43页2022-9-2（二）建立优化模型的一般步骤（二）建立优化模型的一般步骤1.确定设计变量和目标变量；确定设计变量和目标变量；2.确定目标函数的表达式；确定目标函数的表达式；3.寻找约束条件。寻找约束条件。现在学习的是第13页，共43页2022-9-2n选址问题选址问题n聘用雇员问题聘用雇员问题n投资问题投资问题n产品配比问题产品配比问题n指派问题指派问题n平板车装箱问题平板车装箱问题（三）优化模型举例（三）优化模型举例现在学习的是第14页，共43页2022-9-2实例实例1 选址问题选址问题 一项工程有一项工程有 个施工点，已知每个施工点对某种材料的需求为个施工点，已知每个施工点对某种材料的需求为 （单位：吨），施工点的位置坐标为（单位：吨），施工点的位置坐标为 （以公里记），（以公里记）， 。( ,)iia b1,2,im 现要设立现要设立 个料场，已知每个料场这种材料的最大容纳量为个料场，已知每个料场这种材料的最大容纳量为 (单位：吨单位：吨)， 。1,2,jn 试确定这试确定这n个料场的位置坐标，及各料场向各施工点的材料个料场的位置坐标，及各料场向各施工点的材料运量，在保证施工需求的条件下，使材料运输的总吨公里最小运量，在保证施工需求的条件下，使材料运输的总吨公里最小。mirnjq现在学习的是第15页，共43页2022-9-21.确定设计变量和目标变量：确定设计变量和目标变量：2.确定目标函数的表达式：确定目标函数的表达式： 设第设第j个料场的位置坐标为个料场的位置坐标为 ，第，第j个料场向第个料场向第i个施工点个施工点的材料运量为的材料运量为 。(,)jjxyijw 第第j个料场到第个料场到第i个施工点的吨公里数为个施工点的吨公里数为ijijw d22()()ijjijidxayb 总吨公里数为总吨公里数为11mnijijijzw d现在学习的是第16页，共43页2022-9-2（1）施工地点的需求：）施工地点的需求：3.寻找约束条件寻找约束条件1, 1,2,nijijwrim（2）各料场的最大容量：）各料场的最大容量：1, 1,2,mijiiwqjn（3）对运量的自然要求：）对运量的自然要求：0,1,2,; 1,2,ijwim jn现在学习的是第17页，共43页2022-9-22211min()()mnijjijiijzwxayb11, 1,2,. . , 1,2,0,1,2,; 1,2,nijijmijiiijwrimstwqjnwim jn数学模型数学模型现在学习的是第18页，共43页2022-9-2问题：问题： 如果还要求每个施工点的如果还要求每个施工点的R公里内至少有一个料公里内至少有一个料场，数学模型又如何？场，数学模型又如何？现在学习的是第19页，共43页2022-9-2 邮局一周中每天需要不同数目的雇员，设周一至少邮局一周中每天需要不同数目的雇员，设周一至少 人，人，周二至少周二至少 人，人， ，周日至少，周日至少 人，又规定应聘者需连人，又规定应聘者需连续工作续工作5天，问邮局每天聘用多少雇员才能既满足需求，又使聘用总天，问邮局每天聘用多少雇员才能既满足需求，又使聘用总人数最少。人数最少。1a实例实例2 聘用雇员问题聘用雇员问题2a7a设邮局周一新聘用雇员为设邮局周一新聘用雇员为 ，1x周二新聘用雇员为周二新聘用雇员为 ，2x周日新聘用雇员为周日新聘用雇员为 ，则目标函数为，则目标函数为7x127zxxx现在学习的是第20页，共43页2022-9-2145671xxxxxa周一周一125672xxxxxa周二周二123673xxxxxa周三周三123474xxxxxa周四周四123455xxxxxa周五周五234566xxxxxa周六周六345677xxxxxa周日周日现在学习的是第21页，共43页2022-9-2145671xxxxxa125672xxxxxa123673xxxxxa123474xxxxxa123455xxxxxa234566xxxxxa345677xxxxxa127min zxxx. .st数学模型数学模型现在学习的是第22页，共43页2022-9-2问题：问题： 上述指全时雇员（每天工作上述指全时雇员（每天工作8小时）。如果邮局也可聘用半时小时）。如果邮局也可聘用半时雇员（每天工作雇员（每天工作4小时，也需连续工作小时，也需连续工作5天）。设全时和半时雇天）。设全时和半时雇员的工资分别为每小时员的工资分别为每小时12元和元和10元，并且限制半时雇员的工作量元，并且限制半时雇员的工作量不应超过总工作量的四分之一，问邮局如何安排聘用方案，使所不应超过总工作量的四分之一，问邮局如何安排聘用方案，使所付工资额最少。付工资额最少。现在学习的是第23页，共43页2022-9-2145671456718()4()8xxxxxyyyyya125671256728()4()8xxxxxyyyyya123671236738()4()8xxxxxyyyyya123471234748()4()8xxxxxyyyyya234562345668()4()8xxxxxyyyyya345673456778()4()8xxxxxyyyyya127127min12 8 ()104 ()zxxxyyy . .st数学模型数学模型123451234558()4()8xxxxxyyyyya123456712345674 5()0.25 8()yyyyyyyaaaaaaa现在学习的是第24页，共43页项目项目A：若每年初投资一元，则两年后收回本利共：若每年初投资一元，则两年后收回本利共 ；2022-9-2 现有一笔资金现有一笔资金 ，今后，今后5年内有以下项目的投资可供选择年内有以下项目的投资可供选择，问如何确定每年初这些项目的投资，使，问如何确定每年初这些项目的投资，使5年末的本利总额最大。年末的本利总额最大。(1)a实例实例3 投资问题投资问题S项目项目B：只能在第：只能在第2年初投资，第五年末收回本利的年初投资，第五年末收回本利的 倍，但投倍，但投资额不能小于资额不能小于 ；R项目项目D：每年初可购：每年初可购1年期债券，利率为年期债券，利率为 。(1)b项目项目C：只能在第：只能在第3年初投资，第五年末收回本利的年初投资，第五年末收回本利的 倍，但倍，但投资额不能超过投资额不能超过 ；Q(1) cd现在学习的是第25页，共43页设设 分别表示第分别表示第 年初这四个项目的投资额，年初这四个项目的投资额，,iiiiA B C Di第第1年初，年初，11ADS第第1年末，年末，1(1)d D第第2年初，年初，2221(1)ABDd D第第2年末，年末，12(1)(1)a Ad D第第3年初，年初，33312(1)(1)ACDa Ad D第第3年末，年末，23(1)(1)a Ad D第第4年初，年初，4423(1)(1)ADa Ad D第第4年末，年末，34(1)(1)a Ad D现在学习的是第26页，共43页第第1年初，年初，11ADS第第1年末，年末，1(1)d D第第2年初，年初，2221(1)ABDd D第第2年末，年末，12(1)(1)a Ad D第第3年初，年初，33312(1)(1)ACDa Ad D第第3年末，年末，23(1)(1)a Ad D第第4年初，年初，4423(1)(1)ADa Ad D第第4年末，年末，34(1)(1)a Ad D第第5年初，年初，534(1)(1)Da Ad D第第5年末，年末，4235(1)(1)(1)(1)a Ab Bc Cd D现在学习的是第27页，共43页4235max(1)(1)(1)(1)za Ab Bc Cd D11222133312442353423(1)(1)(1)(1)(1). . (1)(1)0,0,0,0,1,2,3,4,5iiiiADSABDd DACDa Ad DADa Ad DstDa Ad DBRCQABCDi现在学习的是第28页，共43页2022-9-2 某厂生产某厂生产 种饲料种饲料 ，它们均由，它们均由 种原料种原料 配合而成，配合而成， 在在 中含量（百分比）的上限为中含量（百分比）的上限为 ，下限为，下限为 。若。若 的售价为的售价为 （元（元/千克），千克）， 的成本为的成本为 （元（元/千克），千克）， 的的供应量不超过供应量不超过 ，其中，其中实例实例4 产品配比问题产品配比问题n 试确定各种饲料的产量及其原料配比，使工厂的利润最大。试确定各种饲料的产量及其原料配比，使工厂的利润最大。12,nP PPm12,mQ QQjQiPijuijliPipjQjrjQ1,2, ;1,2,in jmjq 设设 饲料的产量为饲料的产量为 ， 在在 中的比例为中的比例为 。iPiyjQiPijx现在学习的是第29页，共43页2022-9-2建模建模 设设 饲料的产量为饲料的产量为 ， 在在 中的比例为中的比例为 。iPiyjQiPijx1.确定设计变量和目标变量：确定设计变量和目标变量：2.确定目标函数的表达式：确定目标函数的表达式：利润利润= 总收入总收入总成本总成本1niiip yjijiq x yijix y 中中 的含量：的含量：jQiP11nmjijiijq x y现在学习的是第30页，共43页2022-9-2111nnmiijijiiijup yq x y（1）原料供应的约束：）原料供应的约束：3.寻找约束条件寻找约束条件1, 1,2,niijjiy xrjm（2）原料含量的约束：）原料含量的约束：,1,2, ;1,2,ijijijlxu in jm11,1,2,mijjxin现在学习的是第31页，共43页2022-9-2111maxnnmiijijiiijup yq x y数学模型数学模型11, 1,2,1,2, ;1,2,1,1,2,0,0,1,2, ;1,2,niijjiijijijmijjiijy xrjmlxu in jmxinyxin jm. .st现在学习的是第32页，共43页2022-9-2练习练习 指派问题指派问题 设有设有n n项任务要分给项任务要分给n n个人完成，每人完成一项个人完成，每人完成一项。由于每个人的专长不同，完成任务所需的成本也不。由于每个人的专长不同，完成任务所需的成本也不同。若第同。若第 i i 个人完成第个人完成第 j j 个问题的成本为个问题的成本为 CijCij，见下，见下表。表。问题是：问题是：如何分配这些工作任务，使总成本为最小。如何分配这些工作任务，使总成本为最小。现在学习的是第33页，共43页2022-9-2表：每个人员的成本表：每个人员的成本 现在学习的是第34页，共43页2022-9-2s.t.1 , 0.,.,2 , 1, 1.,.,2 , 1, 111ijniijnjijxnjxnixninjijijxCf11min数学模型数学模型现在学习的是第35页，共43页 每辆平板车有每辆平板车有10.2米长的地方装箱（像面包片那样），载重米长的地方装箱（像面包片那样），载重40吨吨。由于货运限制，对。由于货运限制，对 三种包装箱的装载有如下特殊要求：它们三种包装箱的装载有如下特殊要求：它们所占的空间（厚度）不得超过所占的空间（厚度）不得超过302.7厘米。试把包装箱装到平板车上厘米。试把包装箱装到平板车上，使浪费的空间最小。，使浪费的空间最小。2022-9-2 要把要把7种规格的包装箱装到两辆铁路平板车上去，箱子的宽高相种规格的包装箱装到两辆铁路平板车上去，箱子的宽高相同，而厚度和重量不同，下表给出它们的厚度、重量与数量。同，而厚度和重量不同，下表给出它们的厚度、重量与数量。讨论讨论 平板车装箱问题平板车装箱问题567,c c c7c6c5c4c3c2c1c现在学习的是第36页，共43页可见，所有包装箱的厚度为可见，所有包装箱的厚度为27.495米，而两辆包装箱共有米，而两辆包装箱共有20.4米长的地方，显然不能全部装下。这就需要我们优米长的地方，显然不能全部装下。这就需要我们优化。化。设包装箱设包装箱 装到平板车装到平板车1,2的数量分别为的数量分别为 ic12,1,2,7iixxi 7121()iiiiizt xt x厚度函数：厚度函数： 现在学习的是第37页，共43页7121()iiiiizt xt x目标函数：目标函数： 711020, 1,2iijit xj约束条件：约束条件： 厚度约束厚度约束 714000, 1,2iijiw xj重量约束重量约束 21, 1,2,7ijijxni数量约束数量约束 75302.7, j1,2iijit x特殊约束特殊约束 现在学习的是第38页，共43页数学模型：数学模型： 7121max()iiiiizt xt x717121751020, 1,24000, 1,2. . , 1,2,7302.7, j1,20iijiiijiijijiijiijt xjw xjstxnit xx整数整数 现在学习的是第39页，共43页2022-9-22004年-2012年全国研究生数学建模竞赛题目现在学习的是第40页，共43页2022-9-22004年-2012年全国研究生数学建模竞赛题目现在学习的是第41页，共43页2022-9-2现在学习的是第42页，共43页2022-9-2感谢大家观看感谢大家观看现在学习的是第43页，共43页