数学建模(A题).ppt

夏令营夏令营A题讨论题讨论 孟大志孟大志北京工业大学北京工业大学Tel:13701377108李大潜院士倡导：李大潜院士倡导：问题驱动的应用数学。问题驱动的应用数学。数学建模的目的是科学研究与数学应用。数学建模的目的是科学研究与数学应用。应用数学方法：应用数学方法：数学建模和科学与工程计算构成了数学应数学建模和科学与工程计算构成了数学应用的两大支柱。用的两大支柱。模型是什么？模型是什么？模型：模型：以特定以特定目的目的对事物原型抽象出对事物原型抽象出结构结构并适当并适当表示表示。原型原型 抽象出结构抽象出结构 模型模型结构主义学派（结构主义学派（Bourbaki）：）：数学数学=集合集合+结构结构2.数学是什么？什么？数学模型：原型结构的数学表示。数学模型：原型结构的数学表示。结构化建模方法：结构化建模方法：提供分析的方法提供分析的方法分析结构的方法，分析结构的方法，结构主义分析结构主义分析一、理解问题一、理解问题1、问题的背景、问题的背景注意两句话：注意两句话：“垃圾分类化收集与处理是有利于减少垃圾减少垃圾的产生，有益于环境保护环境保护，同时也有利于资源回收与再利用的城市绿色工程。”“关于组织开展城市餐厨餐厨废弃物资源化利用和无害化处理试点工作的通知”垃圾分类问题关注：1）减少垃圾的产生，有益于环境保护，回收与再）减少垃圾的产生，有益于环境保护，回收与再利用；利用；2）城市厨余垃圾是问题的重点。）城市厨余垃圾是问题的重点。2、问题给出的条件、问题给出的条件 这是一个分类垃圾清运方案的问题，从问题陈述与数据中看出给出三个方面的信息，组成问题的已知条件：清运流程、清运路网和垃圾站的清运流程、清运路网和垃圾站的垃圾量垃圾量。分别分析：1）清运流程结构清运流程结构由于垃圾分类，从前述流程图看出，如果考虑环保，干湿垃圾最好分别清运，流程分别是：厨余垃圾（湿）（附加设备设置方案厨余垃圾（湿）（附加设备设置方案）：垃圾站（脱水处理）垃圾处理中心 （未脱水）转运站干垃圾干垃圾垃圾站 转运站（装箱）垃圾处理中心 2）地理结构：垃圾站与转运站的路网结构。）地理结构：垃圾站与转运站的路网结构。3）垃圾量分布结构：垃圾站的产生量和中专量。）垃圾量分布结构：垃圾站的产生量和中专量。这是一个研究性课题，而一个实际问题，条件通常不清楚，这就要求你去理解问题，完善条件和简化完善条件和简化。1）题目并未给出小区和转运站的确切地理位置，只有街道信息，从而要标出位置，显然具有一定误差，产生问题：误差如何估计误差如何估计？确定地理位置后如何确定路网的长度路网的长度？2）垃圾站的垃圾量分布未知，如何从已经给出的数据资料确定垃圾站的日产生垃圾量？结构的数据化准备结构的数据化准备地理结构数学化表示地理结构数学化表示小区和集散站的坐标小区和集散站的坐标确定：确定：地理结构数学化表示，小地理结构数学化表示，小区和集散站的网络结构表区和集散站的网络结构表示。示。节点距离确定：直线不符节点距离确定：直线不符合实际；测量道路太过复合实际；测量道路太过复杂；一个很好的近似距离杂；一个很好的近似距离确定：节点之间坐标的分确定：节点之间坐标的分量绝对值之和：量绝对值之和：但是要进行误差估计！但是要进行误差估计！二、简化处理与假设二、简化处理与假设首先，经过数据处理，产生了地理结构图。可以看出两点：1）显然，垃圾清运必须划分区域实施）显然，垃圾清运必须划分区域实施，直接的整体优化没有意义。不仅从管理角度理解，而且整体优化的结果，应该与恰当的区域划分恰当，但是计算复杂度将明显降低；2）一些区域显然不需要数学优化处理）一些区域显然不需要数学优化处理，人工直觉的判断也是容易的，解答几乎是唯一的：好的解决方案只在困难问题才使用数学建模方法。复杂区域的划分：复杂区域的划分：这是第一个数学模型，区域划分的准则是什么？应该使得最终的全局最优（经济与环保）。例如例如：1）即如何划分区域即如何划分区域，使得每个区域有一个转运站，满足垃圾对于每个小区送达该转运站的距离最近。2）如何考虑厨余垃圾处理设备与清运问题关系如何考虑厨余垃圾处理设备与清运问题关系？这是一个复杂问题，数学模型是复杂的。3）区域划分一定和厨余垃圾脱水设备的配置有关，但是减少复杂性减少复杂性的方法？（独立性假设？）（独立性假设？）三、结构分析的建模：三、结构分析的建模：1）地理结构，小区和集散站的位置，形成问题的）地理结构，小区和集散站的位置，形成问题的地理结构，量化方法是得到全部坐标。将小区和集地理结构，量化方法是得到全部坐标。将小区和集散站看作节点，节点之间的连线看作边散站看作节点，节点之间的连线看作边+边的长度边的长度值，则问题的结构就对应到数学结构：值，则问题的结构就对应到数学结构：图论中的加权网络结构，只是节点有两类；图论中的加权网络结构，只是节点有两类；2）对于橱余垃圾的处理装置的设置，为了实现成）对于橱余垃圾的处理装置的设置，为了实现成本最低和环保性，这里有一个本最低和环保性，这里有一个优化的结构优化的结构：优化目：优化目标是经济性和环保性；优化变量是节点中的（标是经济性和环保性；优化变量是节点中的（0，1）取值的位置函数；约束条件是：集散点可以放）取值的位置函数；约束条件是：集散点可以放置大型设备，小区放置小型设备；置大型设备，小区放置小型设备；环保性条件环保性条件？这？这是一个重要问题，如何描述这个约束？是一个重要问题，如何描述这个约束？3）清运方案必须沿着公路和街道运输，这个约束）清运方案必须沿着公路和街道运输，这个约束的分析导致的分析导致路径优化的结构路径优化的结构。4）问题的复杂性分析）问题的复杂性分析 上述这些结构的关联性，使得问题的结构变上述这些结构的关联性，使得问题的结构变得复杂，所以需要模型化方法解决之！特别是得复杂，所以需要模型化方法解决之！特别是设设备设置对于清运有直接影响备设置对于清运有直接影响，但是设置的可行方，但是设置的可行方案从穷举的角度看非常多。从而可以有如下两种案从穷举的角度看非常多。从而可以有如下两种基本方案类型：基本方案类型：A.整体优化模型整体优化模型 双优化变量的双目标问题：设备和路径作为双优化变量的双目标问题：设备和路径作为两个实现的变量，而经济性和环保两个目标同时两个实现的变量，而经济性和环保两个目标同时解决。这个模型十分复杂，而且求解十分困难。解决。这个模型十分复杂，而且求解十分困难。B.变量可独立性的优化模型变量可独立性的优化模型 先解决设备的设置，目标是经济性和环保性，先解决设备的设置，目标是经济性和环保性，问题大大简化；然后在固定的设备方案下，路径问题大大简化；然后在固定的设备方案下，路径优化问题。但是这是原问题的近似。优化问题。但是这是原问题的近似。显然，模型显然，模型B比较可行！比较可行！5)集散站归属的小区（垃圾站）的划分集散站归属的小区（垃圾站）的划分均衡性假设：集散站之间收集的垃圾量差异不大，均衡性假设：集散站之间收集的垃圾量差异不大，从而形成约束条件，对每一个小区按照从而形成约束条件，对每一个小区按照“距离距离”定定义形成归属集散站的算法，形成最终的义形成归属集散站的算法，形成最终的“集散站集散站小区子图小区子图”。5）从而对于非橱余类垃圾在）从而对于非橱余类垃圾在“集散站集散站小区子图小区子图”中形成路径优化算法。由于此时每个子图中节点中形成路径优化算法。由于此时每个子图中节点很少，求解十分容易。很少，求解十分容易。6）对于橱余垃圾，关键是）对于橱余垃圾，关键是环保性的量化为经济性环保性的量化为经济性指标指标，从而双目标问题变成单目标问题。这个优化，从而双目标问题变成单目标问题。这个优化问题的解答中，整体进行路径优化问题的建模。其问题的解答中，整体进行路径优化问题的建模。其中设置小型设备的小区，将没有橱余垃圾的单独清中设置小型设备的小区，将没有橱余垃圾的单独清运问题。运问题。