问题的数学模型与算法

研究生课程：研究生课程：问题的数学模型与方法问题的数学模型与方法(2011年上学期 )授课：黎自强授课：黎自强 (教授教授 )联系电话：联系电话：ate 湘潭大学信息工程学院湘潭大学信息工程学院主要内容：1. 目标函数优化问题1.1 遗传算法求解复杂布局问题1.2 拉格郎日算子求解圆柱体碰撞检测问题2. 偏微分方程数值求解2.1 铸件凝固过程的温度场模拟Date 湘潭大学信息工程学院湘潭大学信息工程学院1. 目标函数优化问题1.1.1 工程背景和科学问题的提出 1.1.2 布局优化问题研究进展 1.1.3 航天器布局方案设计研究进展 1.1.4 用遗传算法求解布局问题1.1 复杂布局问题复杂布局问题Date 湘潭大学信息工程学院湘潭大学信息工程学院1.1.1 工程背景和科学问题的提出 a) 发达国家航天器发展现状美国与欧洲空间局自 80年代起，致力于用计算机技术解决航天器舱的待布物总体布局问题的研究，其关键理论、方法、技术至今仍处于保密状态。近年来有用协同优化法设计航天器的保护装置和得到 NASA资助的用遗传算法进行航天器的设计，但很少涉及布局设计的内容。根据我国人员出国考察获悉，以卫星布局设计为例，目前美国设计效率比我国快 20倍以上，但是其性能和空间利用率对比不详。Date 湘潭大学信息工程学院湘潭大学信息工程学院b) 国内航天器发展现状我国航天器设计多以人工设计为主，参考样图或资料，用计算机辅助绘图（二、三维），然后用国外软件进行三维造型模装，再用国外软件进行三维动力学验算。若不合适，用人工修改设计，最后建造 1:1实物模型，进行实验验证。Date 湘潭大学信息工程学院湘潭大学信息工程学院c) 人工设计存在的问题：v 性能不易保证或非优化；v 空间利用率低；v 设计成本高；v 设计周期长。过去卫星曾因总体布局不当，动不平衡过大，曾造成过早报废的恶果。况且我国还要研制更复杂的空间站，其布局设计尤为重要。 Date 湘潭大学信息工程学院湘潭大学信息工程学院d) 科学问题的提出从理论上说，航天器布局设计，可归结出 “可数学模型化 ” 和 “ 不可或难数学模型化 ” 两类问题。前者属很难的带性能约束的三维布局优化问题；后者多属工程复杂系统问题，涉及人脑思维模型问题，解决方法有二种：v 一是人工智能，基于智能的知识模型及其推理；v 二是人机结合 (Man-Machine Synergy)或人机合作(Human-Computer Cooperation)。航天器布局设计属交叉学科前沿课题的基础理论和应用基础研究，具有重要的科学意义。 Date 湘潭大学信息工程学院湘潭大学信息工程学院1.1.2 布局优化问题研究进展 布局问题 (Layout Problem)属于复杂的组合优化问题，即使最简单的一维布局也属于 NPC问题。自 1831年高斯 (Gauss)研究布局问题开始，虽然经过几代人的努力，但迄今尚无成熟的理论和有效的数值计算方法。 从理 论 上 讲 ，布局 问题 可分 为 切段(Cutting-Stock)问题 和装填 (Packing)问题。Date 湘潭大学信息工程学院湘潭大学信息工程学院按照布局物体的布局维数分类a) 一维布局问题 b) 二维布局问题 c) 三维布局问题 Date 湘潭大学信息工程学院湘潭大学信息工程学院a) 一维布局问题 一维布局问题中典型的例子是在给定长度的棒料上，切割长度不等的若干短棒，此类问题通常称为切段问题 (Cutting-Stock Problem)。 解决方法：lFaggioli 5利用启发式算法提出了切段排序问题的数学模型和一个三步解法； lVasko 6和 Nitsche 7 分别利用树搜索算法和松弛算法来解决一维切段问题；lPetridis Vassilios等 8利用遗传算法以动态的方式把问题的约束合并到适应度函数中。Date 湘潭大学信息工程学院湘潭大学信息工程学院b) 二维布局问题 二维布局问题包括：l一刀切问题将某些不同大小的小矩形按照一刀切的原则排放在一个大矩形板材上，使面积浪费最小，这是剪床落料、玻璃切割、纸张切割中遇到的主要问题。所谓一刀切，是指切割总是从矩形板材的一边开始一直切到其对边，即每切一刀都将一个矩形分割成两个小矩形 l底盘装载问题底盘装载问题来源于运输、搬运中的货物摆放或装箱。将多个相同大小的立体箱子放入一立方体容器中，且要求放入的箱子越多越好。Date 湘潭大学信息工程学院湘潭大学信息工程学院l矩形布局问题 (Rectangle Packing Problems) 矩形布局问题是将许多大小不同的二维矩形布置在一个大的矩形中，使面积覆盖率最大，这是大规模集成电路设计中所碰到的主要问题。l圆布局问题 (Circle Packing Problems)圆布局问题是将许多大小相同或不同的圆布置在一个大的圆形、三角形或矩形容器中，使面积覆盖率最大 39。这类问题大量地存在于几何、化学、生物学、工程和优化中，已经引起人们的很大关注 40。 通常不等圆装填问题还需满足一定的性能约束条件，譬如：惯性、平衡性、和稳定性约束等，我们把这种问题称为带性能约束的不等圆装填问题。Date 湘潭大学信息工程学院湘潭大学信息工程学院l二维不规则图形布局问题 (2-D Irregular Graph Layout Problems)二维不规则图形布局问题是指将许多任意形状、大小的二维形体布置在一任意形状的二维平面内以使某一性能最优，如板材下料，服装裁剪等。处理这类问题通常是把不规则图形套排在一些形状比较规则的简单图形中，然后用这些简单的图形在给定的平面内排样，以降低问题的复杂程度。 Date 湘潭大学信息工程学院湘潭大学信息工程学院三维布局问题 三维布局问题包括：v无性能约束的三维布局问题 (3-D Layout Problems with Non-Behavioral Constraints)无性能 约 束三 维 布局 问题 是指将尽量多的不同形状、尺寸的三 维 物体放入到一 长 方体（或 圆 柱体）容器中，例如背包 问题 、 集装箱 问题 。v带性能约束的三维布局问题 (3-D Layout Problems with Behavioral Constraints) 。带性能约束三维布局问题是指将任意形状、大小和性能的三维实体摆放在一个任意形状、大小的三维容器中，以满足某些约束或使某些目标最优 Date 湘潭大学信息工程学院湘潭大学信息工程学院例子 约束 底盘装载和船舶配载问题 汽车驾驶舱布局问题 集成电路 (VLSI)的布局规划 航天器舱布局方案设计问题 Date 湘潭大学信息工程学院湘潭大学信息工程学院带性能约束布局问题的算法 l启发式算法 (Heuristic Algorithm) v 拟物拟人法 v 拟实验综合启发式算法 v 八叉树结构与定位 定序函数相结合的启发式算法 v GENET模型 v Montreuil模型 v 膨胀算法 Date 湘潭大学信息工程学院湘潭大学信息工程学院l图论 法 (Graph Theory) 图论作为组合数学的重要组成部分，在许多领域有着广泛的应用。该方法一般将带性能约束布局问题分两步来求解。第一步，求出相邻拓扑关系的无尺寸的平面布局，即根据待布物之间的确定位置关系构造一个图，图中节点代表各待布物，连接节点的边表示待布物之间的确定位置关系。第二步，根据布局图，利用优化算法求出待布物之间的具体尺寸。 Date 湘潭大学信息工程学院湘潭大学信息工程学院l模拟退火算法 (Simulated Annealing Algorithm) l演化算法 (Evolutionary Algorithm) 上述四种方法基本上是用数学方法求解数学模型问题。 l人工智能 (包括专家系统 )(Artificial Intelligence including Expert System)l人机交互、人机结合与人机协同算法 (Human-Computer Interaction, Combination and Cooperation Algorithm) Date 湘潭大学信息工程学院湘潭大学信息工程学院布局问题评述及其策略和求解算法的发展前景现在的复杂布局研究存在如下问题： v从布局策略上讲，传统的计算机辅助布局的思路，多将实际问题化为简化的数学模型用计算机算法求解。由于数学模型过于简化，即使能求得结果，但距离解决实际问题相差甚远，因为实际的工程影响因素复杂，存在不可（或难以）数学模型化的问题； v从布局问题模型的描述上讲，布局问题的有效、精确表达是解决问题的前提和基础。目前多用数学模型，若模型简单则不能概括必要内容，若模型过于复杂，又无法求解。另外，缺乏包含数学、仿真、符号的复合模型研究，缺乏将工程复杂布局问题从一个复杂工程系统角度去研究； Date 湘潭大学信息工程学院湘潭大学信息工程学院v从求解方法上讲，复杂的布局问题求解困难在于存在组合爆炸，如何解决成为关键。但由于以往研究人员各自研究领域及知识背景的不同，很难甚至无法与其他求解方法协同进行设计求解。解决此问题，目前常见的途径是寻找好的算法或者是算法集成；v从优化布局方案的评价上讲，尚未建立一套科学和有效的布局方案评价体系，这给布局优化过程中的方案选择和决策带来困难； v从研究难度和规模上讲，存在的问题是：对一、二维布局研究多，三维布局研究少，尤其是对三维带性能约束布局研究少；对小型问题研究多，对中大型问题研究少；v从实用化上讲，实践应用深度和广度有待提高。 Date 湘潭大学信息工程学院湘潭大学信息工程学院关于布局策略布局策略的安排是问题求解的前提或出发点。布局策略的表现形式是数学模型，然后采取相应的算法。目前带性能约束布局问题中常用的布局策略大多数是采用传统的计算机辅助设计的思想，即将实际问题简化为单一的数学模型，这种单一的模型往往长于描述问题的某方面的特点，而不善于表达问题的综合属性，也缺少科学有效的布局方案评价体系；特别是对于复杂的三维问题这种布局策略的局限性更为突出；因此即使能算出结果，可能与实际问题相差很远。 Date 湘潭大学信息工程学院湘潭大学信息工程学院l求解算法的发展前景 航天器舱布局方案设计目前国外（如欧、美）主要有三种方法：一是演化算法；二是虚拟（现实）设计；三是协同设计。其中关键因素是 “ 算法 ” 与 “ 人 ” 。无论是虚拟设计还是协同设计，若无有效的布局算法，并发挥人的作用，尤其是对于如此复杂工程设计，是无法完成高质量设计的。人机结合和人机交互的思想充分发挥了人机各自的特长，将这些思想用于其它算法的求解，能够得到生动的用户界面，并将人的知识实时地加入到算法中，使算法快速、有效地解决带性能约束布局问题。对于求解工程复杂布局问题，对解决人机合作的 “ 可操作性 ” 问题，提供了一种方法或途径。演化算法、仿真技术、虚拟设计、人工智能、人机结合或人机交互算法的集成综合的方法，对带性能约束布局算法的发展将会有很大的推动。 Date 湘潭大学信息工程学院湘潭大学信息工程学院1.1.3 航天器布局设计研究进展航天器（卫星、飞船、空间站） (如图 1.5)是由有效载荷、结构、热控制、姿态与轨道控制、电源、跟踪遥测与遥控、数据管理等分系统所组成，分系统又由各自的仪器、设备和部件组成；组件（部件）形式多样、数量繁多；设备与设备之间、分系统与分系统之间有各种不同的机、电、液、气接口，并有传动、管线、缆线相连；所以航天器是一个复杂工程系统 126-128。其布局方案设计是研究如何充分利用航天器有限的空间，布置尽可能多的组件和仪器、设备，并满足其内部和周围环境的各种约束要求的问题 ,这是一个多学科交叉课题。Date 湘潭大学信息工程学院湘潭大学信息工程学院1.5礼炮号空间站Date 湘潭大学信息工程学院湘潭大学信息工程学院航天器总体布局方案设计航天器总体布局方案设计的目的是在选定构型（组件或子系统）基础上将航天器上的仪器设备布置在各舱段的合适位置（如图 1.6和 1.7）。对于载入过程中使用的和需要返回地面的仪器设备应当布置在返回舱，仅在载入前使用的设备可以布置在轨道舱或仪器设备舱，以降低卫星或飞船的结构质量。在进行总体布局方案设计之前，要对航天器的功能要求进行分析，选择组件或子系统，然后确定组件或子系统之间的相互位置关系，并使总系统具有一个协调完善的造型；最后从多个布局方案中择优选取。航天器的总体布局是全局性的重要问题，不但要考虑到航天器各组件或子系统之间的各种约束，而且还要考虑航天器同各种外部因素（如空间环境）之间的约束，尽量达到功能合理、结构紧凑、层次清晰、比例协调等要求。总体上要符合航天器总体设计的要求。 Date 湘潭大学信息工程学院湘潭大学信息工程学院图 1.6 联盟号飞船Date 湘潭大学信息工程学院湘潭大学信息工程学院图 1.7空间站各舱段示意图Date 湘潭大学信息工程学院湘潭大学信息工程学院图 1.8空间站实验舱标准柜Date 湘潭大学信息工程学院湘潭大学信息工程学院图 1.9标准柜待布物优化图Date 湘潭大学信息工程学院湘潭大学信息工程学院航天器舱布局方案设计 航天器舱布局方案设计是研究在满足各种工程技术条件的前提下，如何将各种仪器和设备最优地布置在航天器舱体内（或外） (如图 1.7和 1.8)， 使得布局评价指标达到最优或满足工程结束准则。它属于带性能约束的三维布局优化问题，具有不确定性、高度非线