优化模型.ppt

第一章组合优化模型【PPT】第一章第一章模模型型§§1 关于模型关于模型1§§2 数学模型数学模型§§3 组合优化模型组合优化模型第一章第一章组合优化模型组合优化模型模型（模型（model ）是所研究的系统、过程、事物或）是所研究的系统、过程、事物或由于研究目的的不同，对于同一个对象系统，由于研究目的的不同，对于同一个对象系统，概念的一种表达形式概念的一种表达形式 .可以建立完全不同的模型，分别反映该系统的不同侧面；出于相同的研究目的，对于同一个对象系统，也可能建立不同的模型，反映不同的研究角度、考察因素和价值取向度、考察因素和价值取向.§§§§1 1 关于模型关于模型关于模型关于模型一、模型的概念一、模型的概念2模型不是研究对象本身，而是对研究对象的一种模型不是研究对象本身，而是对研究对象的一种统，也可能建立不同的模型，反映不同的研究角抽象，它反映现实中对象系统的主要特征，但它又高于现实，因而具有同类问题的共性 .于现实，因而具有同类问题的共性 .抽象，它反映现实中对象系统的主要特征，但它又高可以建立完全不同的模型，分别反映该系统的不同侧面；出于相同的研究目的，对于同一个对象系§§§§1 1 关于模型关于模型关于模型关于模型二、模型的本质二、模型的本质从系统概念上看，模型是系统中各种关系的表达形式形式 . 因此，建立模型要从状态和过程两个方面去寻找、把握和描述各系统要素之间的相互关系找、把握和描述各系统要素之间的相互关系 .从系统概念上看，模型是系统中各种关系的表达因此，建立模型要从状态和过程两个方面去寻3状态状态：事物在某个时刻所处的状况或表现形态表现形态状态和过程是相对的状态和过程是相对的 .：事物在某个时刻所处的状况或过程过程：事物状态的变化在时间上的持续和空间上的延伸续和空间上的延伸：事物状态的变化在时间上的持过程和状态两者紧密联系、不可分割，状态决定和影响过程，过程又决定和影响新的状态定和影响过程，过程又决定和影响新的状态 .过程和状态两者紧密联系、不可分割，状态决从认识论上看，模型是作为认识与实践活动的中介从认识论上看，模型是作为认识与实践活动的中介 .模型既是认识的表达，又是实践活动的先导 .模型参与认识世界和改造世界的不断的循环往复过程，既是认识不断深化的体现，又是实践活动不断过程，既是认识不断深化的体现，又是实践活动不断拓展的体现拓展的体现 .模型既是认识的表达，又是实践活动的先导 .模型参与认识世界和改造世界的不断的循环往复第一章第一章组合优化模型组合优化模型4现实世界现实世界认识（信息）认识（信息）模型模型实践活动实践活动概念化概念化用信息载体表达用信息载体表达决策（行动方案）决策（行动方案）产品和服务产品和服务模型化过程示意图模型化过程示意图§§§§1 1 关于模型关于模型关于模型关于模型从信息论上看，模型和认识之间存在密切的反馈关系关系 . 从已知信息可以通过模型加工产生出新的信息，相关信息的积累可以从量变产生质变，形成新的概念，促使认识深化概念，促使认识深化 . 从信息论上看，模型和认识之间存在密切的反馈从已知信息可以通过模型加工产生出新的信息，相关信息的积累可以从量变产生质变，形成新的5因此，模型的建立和完善不仅要注重对系统物质形态和能量形态的认识、把握和描述，而且也依赖于对系统相关信息不断的采集、积累和加工，这就是用模型研究问题的现实活动模型研究问题的现实活动 .因此，模型的建立和完善不仅要注重对系统物质形态和能量形态的认识、把握和描述，而且也依赖于对系统相关信息不断的采集、积累和加工，这就是用三、模型的分类三、模型的分类1、原样模型、原样模型原样模型原样模型是在工程开发末期建立的一种具象实体，是具有实物形态的模型 .体，是具有实物形态的模型 .是在工程开发末期建立的一种具象实第一章第一章组合优化模型组合优化模型6它与目的工程在结构和过程方面基本相同 .它与目的工程在结构和过程方面基本相同 .原样模型经过试验改进和完善后便是所要开发的目的工程的目的工程 .原样模型经过试验改进和完善后便是所要开发新产品的样机、新著作的原稿新产品的样机、新著作的原稿…§§§§1 1 关于模型关于模型关于模型关于模型2、相似模型、相似模型系统分析和设计人员常常借助于这些图形模型来开发、构建一个新系统的想象力和创造力，逐步引申出与之有关的问题和需要进一步探索的问题，使所要开发的系统变得越来越清晰、越来越具体 .开发的系统变得越来越清晰、越来越具体 .相似模型相似模型是根据不同系统间的相似规律（包括几何相似、逻辑相似和过程相似等）而建立的用于研究的模型的模型 .是根据不同系统间的相似规律（包括几何相似、逻辑相似和过程相似等）而建立的用于研究出与之有关的问题和需要进一步探索的问题，使所要图形模型图形模型、图形模型图形模型图形模型图形模型可以表达非常丰富的内容，主要有：可以表达非常丰富的内容，主要有：地球仪地球仪、地球仪地球仪、（没有严格的规范）（没有严格的规范）、船体放船体放、船体放船体放称为不严格图称为不严格图系统分析和设计人员常常借助于这些图形模型来开发、构建一个新系统的想象力和创造力，逐步引申73、样模型、飞机风洞实验模拟模型等等拟模型等等样模型、飞机风洞实验模①① 图画图画——一种可以示形的图形；②② 草图草图——一种可以示意的图形；③③ 框图框图——一种可以表示系统的部分之间或部分与整体之间联系的图形；与整体之间联系的图形；一种可以示形的图形；一种可以示意的图形；一种可以表示系统的部分之间或部分④④ 逻辑图逻辑图——一种可以反映因素或对象间逻辑关系的图形；的图形；⑤⑤ 工程图工程图——一种可以反映物体确定的结构和顺序关系的图形；关系的图形；⑥⑥ 图论图图论图包括图论所定义的无向图包括图论所定义的无向图 G(V，它或能解释某些客观现象它或能解释某些客观现象，，或能预测未来的发展规⑥⑥ 图论图图论图——包括图论所定义的无向图包括图论所定义的无向图G(V，有向图有向图 G(V，，A)、加权有、加权有(无律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略优策略或较好策略 .一种可以反映因素或对象间逻辑关系数学模型是用数学的语言、方法去近似地刻画实际是用数学的语言、方法去近似地刻画实际 ,是由数字、字母或其他数学符号组成的，描述现实对象数量规律的数学公式、图形或算法象数量规律的数学公式、图形或算法 .是对现实对象本质属性的抽象而又简洁的刻画，是对现实对象本质属性的抽象而又简洁的刻画，它或能解释某些客观现象它或能解释某些客观现象，，或能预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最如：程序流程图、控制关系图制关系图 etc.如：建筑工程图、如：建筑工程图、铁路站场配置图铁路站场配置图或能预测未来的发展规铁路站场配置图铁路站场配置图 etc.无)向图向图G(V，如：程序流程图、控（有严格确定的结构形式和规范）形式和规范）一种可以反映物体确定的结构和顺序（有严格确定的结构，E) 、，E) 、，w).、、关系关系称为严格图称为严格图数学模型是由数字、字母或其他数学符号组成的，描述现实对第一章第一章组合优化模型组合优化模型8，A(E)，4、数学模型、数学模型数学模型数学模型是指运用数学符号和公式来表达、研究对象系统的结构或过程的模型 .对象系统的结构或过程的模型 .是指运用数学符号和公式来表达、研究或能预测未来的发展规Go back§§§§2 2 数学模型数学模型数学模型数学模型Example 1七桥问题七桥问题18世纪的德国有个哥尼斯堡城，在流贯全城的普雷尔河两岸和河中两个岛之间架设了七座桥，把河的两岸和两岛连接起来，能否有这样一种走法，它通过两岸和两岛连接起来，能否有这样一种走法，它通过每座桥一次且仅一次每座桥一次且仅一次 .世纪的德国有个哥尼斯堡城，在流贯全城的普雷尔河两岸和河中两个岛之间架设了七座桥，把河的该问题由该问题由Euler在1736年解决年解决在9Solution :ABCD显然，解决该问题时，两岸和岛的大小、形状以及桥的长短曲直都无关，重要的是什么？的是什么？对问题进行数学抽象：对问题进行数学抽象：显然，解决该问题时，两岸和岛的大小、形状以及桥的长短曲直都无关，重要把两岸和两岛都看做顶点把两岸和两岛都看做顶点，把两岸和两岛都看做顶点把两岸和两岛都看做顶点，当作边，于是得到一无向图当作边，于是得到一无向图 .，将连接这些顶点的桥将连接这些顶点的桥，将连接这些顶点的桥将连接这些顶点的桥第一章第一章组合优化模型组合优化模型10每块陆地间有几座桥几座桥每块陆地间有则七桥问题就成为无向图中是否存在通过每一边一次且仅一次的路（即一笔画）问题 .一次且仅一次的路（即一笔画）问题 .则七桥问题就成为无向图中是否存在通过每一边§§§§2 2 数学模型数学模型数学模型数学模型ABCDEuler 在他的论文中证明在他的论文中证明：问题原型七桥问题七桥问题：一个图中存在一笔画的充要条件是同时满足：充要条件是同时满足：有无解？有无解？一个图中存在一笔画的1、图是连通的；、图是连通的；无无( ( 一次过七座桥不可能一次过七座桥不可能) )2、、与图中每一顶点（可能有两点例外）相连的边（线度）必须是偶数条 .（线度）必须是偶数条 .问题原型数学模型一笔画问题一笔画问题数学模型解解无无解解( ( 一笔画不可能一笔画不可能) )( ( 一笔画不可能一笔画不可能) )数学抽象数学抽象逻辑推理逻辑推理翻译回去翻译回去11与图中每一顶点（可能有两点例外）相连的边这是关于图论的第一篇论文的第一篇论文这是关于图论见图可知，与四个顶点相连的边都是奇数条，因而不可能存在通过每条边一次且仅一次的画法，即一笔画不存在 . 故七桥问题不可能有解笔画不存在 . 故七桥问题不可能有解 .见图可知，与四个顶点相连的边都是奇数条，因而不可能存在通过每条边一次且仅一次的画法，即一( ( 一次过七座桥不可能一次过七座桥不可能) )这是利用数学模型分析和解决问题的一个成功范例这是利用数学模型分析和解决问题的一个成功范例一、数学模型的特点一、数学模型的特点1、、高度的抽象性数学方法不仅要抛开事物的次要属性，突出事物的本质属性，而且要舍弃事物的物质和能量方面的具的本质属性，而且要舍弃事物的物质和能量方面的具体内容体内容，，只考虑其数量关系和空间形式只考虑其数量关系和空间形式，体内容体内容，，只考虑其数量关系和空间形式只考虑其数量关系和空间形式，这些数量关系和空间形式作进一步的抽象，加以形式化和符号化，以便能够进行逻辑推理和数值运算化和符号化，以便能够进行逻辑推理和数值运算 .高度的抽象性数学方法不仅要抛开事物的次要属性，突出事物，同时还要把同时还要把，同时还要把同时还要把第一章第一章组合优化模型组合优化模型12这些数量关系和空间形式作进一步的抽象，加以形式这种高度的抽象性，实质是对事物认识上的高度概括和深化，对同类问题包含更多的经验和理解概括和深化，对同类问题包含更多的经验和理解 .这种高度的抽象性，实质是对事物认识上的高度§§§§2 2 数学模型数学模型数学模型数学模型2、、高度的精确性高度的精确性数学方法的高度精确性表现在三个方面：数学方法的高度精确性表现在三个方面：一是一是表达各种因素、变量和它们之间的关系相当明确、清楚；明确、清楚；二是二是逻辑推演和运算规则十分严密；逻辑推演和运算规则十分严密；三是是结论非常确定结论非常确定是是结论非常确定结论非常确定 .表达各种因素、变量和它们之间的关系相当三13数学方法可以处理多变量、关系复杂的问题，可在有意义的范围内获得令人满意的计算精度在有意义的范围内获得令人满意的计算精度 .数学方法可以处理多变量、关系复杂的问题，可特别适合于揭示事物的量的规定性，成为定量研究的有力工具究的有力工具 .特别适合于揭示事物的量的规定性，成为定量研3、、应用的普适性应用的普适性数学方法的高度抽象和精确，使之比任何一种科学方法的应用范围都更为广泛学方法的应用范围都更为广泛 .只存在尚未运用数学方法的领域而不存在不能运只存在尚未运用数学方法的领域而不存在不能运用数学方法的领域用数学方法的领域用数学方法的领域用数学方法的领域 .许多相同形式的数学模型可用于不同的实际问题，具有重要类比和借鉴意义题，具有重要类比和借鉴意义 .数学方法的形式化和数学模型缺乏直观性、形象性和实时感数学模型缺乏直观性、形象性和实时感数学方法的高度抽象和精确，使之比任何一种科第一章第一章组合优化模型组合优化模型14许多相同形式的数学模型可用于不同的实际问公理化，使模型本身、计算过程和计算结果都便于交流，数学模型易变动，便于修改和改变计算关系，分析和求解问题速度快，求解成本低 .析和求解问题速度快，求解成本低 .数学方法的形式化和公理化，使模型本身、计算过程和计算结果都便于交流，数学模型易变动，便于修改和改变计算关系，分§§§§2 2 数学模型数学模型数学模型数学模型二、数学模型分类二、数学模型分类数学模型分类的方法很多，如：数学模型分类的方法很多，如：1、、按所研究问题的性质分类按所研究问题的性质分类⑴⑴ 静态模型与动态模型静态模型与动态模型15⑵⑵ 确定型模型与随机型模型确定型模型与随机型模型⑶⑶ 连续模型与离散模型连续模型与离散模型⑷⑷ 线性模型与非线性模型线性模型与非线性模型⑸⑸ 宏观模型与微观模型宏观模型与微观模型2、、按模型的解的特征分类按模型的解的特征分类解析模型与数值模型解析模型与数值模型3、、按模型所用的数学方法分类按模型所用的数学方法分类初等模型、微分方程模型、差分方程模型、优初等模型、微分方程模型、差分方程模型、优化模型等化模型等化模型等化模型等第一章第一章组合优化模型组合优化模型164、按模型研究的实际范畴分类、按模型研究的实际范畴分类人口模型、生态系统模型、交通流模型、经济模型、基因模型等模型、基因模型等5、按对实际问题了解的程度分类、按对实际问题了解的程度分类白箱模型、灰箱模型、黑箱模型白箱模型、灰箱模型、黑箱模型人口模型、生态系统模型、交通流模型、经济§§§§2 2 数学模型数学模型数学模型数学模型三、数学建模的基本步骤三、数学建模的基本步骤数学模型因问题不同而异，对同一问题，从不同角度、不同要求出发，甚至问题的解表示结构不同，都可以建立不同的数学模型都可以建立不同的数学模型. 建立数学模型也没有固定的方法、标准定的方法、标准 . 不同的实际问题，建模模式千差万不同的实际问题，建模模式千差万别别. 在此介绍通常的几个步骤：在此介绍通常的几个步骤：1、、明确问题明确问题数学模型因问题不同而异，对同一问题，从不同角度、不同要求出发，甚至问题的解表示结构不同，建立数学模型也没有固合理地、有目的地注意精度注意精度合理地、有目的地17数学建模问题直接来源各领域实际，往往含糊不清（目的、条件、类型清（目的、条件、类型 etc.）行全面的、深入细微的调查和研究行全面的、深入细微的调查和研究. 明确所解决问题的性质，着手收集数据；的性质，着手收集数据；数学建模问题直接来源各领域实际，往往含糊不）. 首先，要对该问题进首先，要对该问题进明确所解决问题2、、合理假设合理假设现实问题错综复杂，涉及面非常之广现实问题错综复杂，涉及面非常之广. 一个数学模型面面俱到、无所不包地反映一个现实是不可能的，即使可能，也因其过于复杂而很难求解，也是没的，即使可能，也因其过于复杂而很难求解，也是没有必要的有必要的所以所以，，要作要作合理合理的假设有必要的有必要的 . 所以所以，，要作要作合理合理的假设作假设的依据通常是出于对问题内在规律的认识作假设的依据通常是出于对问题内在规律的认识,或来自对数据或现象的分析，也可以是二者的综合或来自对数据或现象的分析，也可以是二者的综合. 善于辨别问题的主次，抓住主要因素，通过合理假设善于辨别问题的主次，抓住主要因素，通过合理假设,使问题简化以便进行数学描述使问题简化以便进行数学描述 .假设是在模型的建立、求解和分析过程中完善假设是在模型的建立、求解和分析过程中完善 .一个数学模型面面俱到、无所不包地反映一个现实是不可能的假设的假设 .1、简化问题、简化问题2、限定适用范围、限定适用范围相关的因素相关的因素但也不能忽略实质但也不能忽略实质通常开始让问题尽通常开始让问题尽可能简化可能简化可能简化可能简化第一章第一章组合优化模型组合优化模型18§§§§2 2 数学模型数学模型数学模型数学模型3、、建立模型建立模型建模时，要分清问题的类型恰当使用数学工具；抓住问题的本质简化变量之间的关系抓住问题的本质简化变量之间的关系 .建模时，要分清问题的类型恰当使用数学工具；用什么样的方法建立数学模型，没有绝对的标用什么样的方法建立数学模型，没有绝对的标准；；数学模型的形式可以是多种多样数学模型的形式可以是多种多样，准准；；数学模型的形式可以是多种多样数学模型的形式可以是多种多样，格、图形、算法格、图形、算法 .模型的优劣在于是否采用了恰当的方法，合理地描述了实际问题，而不在于是否用到了高深的数学工具具 .数学建模是一个过程数学建模是一个过程 .准，数学公式数学公式、，数学公式数学公式、、表、表表表19模型的优劣在于是否采用了恰当的方法，合理地描述了实际问题，而不在于是否用到了高深的数学工4、、模型求解模型求解不同的模型要用到不同的数学工具求解不同的模型要用到不同的数学工具求解 . 这就要求从事实际工作者对相应的数学分支知识有一定的了解解 . 可借助计算机，特别是利用数学工具软件可借助计算机，特别是利用数学工具软件 .5模型分析模型分析5、、模型分析模型分析这就要求从事实际工作者对相应的数学分支知识有一定的了robustness第一章第一章组合优化模型组合优化模型20对模型求出的解进行数学上的分析，有助于对实际问题的解决际问题的解决 .如如：：① 结果的误差分析① 结果的误差分析分析误差来源：建模假设的误差；数据测量的误差；分析误差来源：建模假设的误差；数据测量的误差；结果是否符合特定的统计规律结果是否符合特定的统计规律③ 模型对数据的灵敏度分析③ 模型对数据的灵敏度分析模型的结果是否会因数据的微小改变而发生大的变化模型的结果是否会因数据的微小改变而发生大的变化模型的结果是否对某一假设非常依赖模型的结果是否对某一假设非常依赖⑤ 不同模型间的对比分析⑤ 不同模型间的对比分析对模型求出的解进行数学上的分析，有助于对实误差是否在允许的范围内误差是否在允许的范围内②② 结果的统计分析结果的统计分析④ 对假设的鲁棒性分析④ 对假设的鲁棒性分析近似求解方法的误差；计算工具的舍入误差近似求解方法的误差；计算工具的舍入误差 .§§§§2 2 数学模型数学模型数学模型数学模型6、、模型检验模型检验将求解结果和分析结果翻译回到实际问题之中，与实际现象、实际数据进行比较，检验是否与实际吻合合 . 如果吻合较好，则模型及其结果可以应用于实际问题；如果吻合不好，则需要对模型进行修正问题；如果吻合不好，则需要对模型进行修正 .、改进模型改进模型吻合不好，问题常常出现在模型假设上吻合不好，问题常常出现在模型假设上 . 可能由于假设了过于苛刻的条件，或者忽略了一些不该忽略的因素的因素. 所以所以, 要对实际问题中的主次因素再次分析要对实际问题中的主次因素再次分析,对模型进行修改、补充、完善对模型进行修改、补充、完善 . 需要多次反复才能达到比较满意的程度。