问题的数学模型与算法

《问题的数学模型与算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、研究生课程：问题的数学模型与方法(2011年上学期)授课：黎自强(教授)联系电话：131872216572021/7/21湘潭大学信息工程学院主要内容：1.目标函数优化问题1.1遗传算法求解复杂布局问题　1.2拉格郎日算子求解圆柱体碰撞检测问题2.偏微分方程数值求解2.1铸件凝固过程的温度场模拟2021/7/21湘潭大学信息工程学院1.目标函数优化问题1.1.1工程背景和科学问题的提出1.1.2布局优化问题研究进展1.1.3航天器布局方案设计研究进展1.1.4用遗传算法求解布局问题1.1复杂布局问题2021/7/21湘潭大学信息工程学院1.1.1工程背景和科学问题的提出a)发

2、达国家航天器发展现状美国与欧洲空间局自80年代起，致力于用计算机技术解决航天器舱的待布物总体布局问题的研究，其关键理论、方法、技术至今仍处于保密状态。近年来有用协同优化法设计航天器的保护装置和得到NASA资助的用遗传算法进行航天器的设计，但很少涉及布局设计的内容。根据我国人员出国考察获悉，以卫星布局设计为例，目前美国设计效率比我国快20倍以上，但是其性能和空间利用率对比不详。2021/7/21湘潭大学信息工程学院b)国内航天器发展现状我国航天器设计多以人工设计为主，参考样图或资料，用计算机辅助绘图（二、三维），然后用国外软件进行三维造型模装，再用国外软件进行三维动力学验算。若不合适

3、，用人工修改设计，最后建造1:1实物模型，进行实验验证。2021/7/21湘潭大学信息工程学院c)人工设计存在的问题：性能不易保证或非优化；空间利用率低；设计成本高；设计周期长。过去卫星曾因总体布局不当，动不平衡过大，曾造成过早报废的恶果。况且我国还要研制更复杂的空间站，其布局设计尤为重要。2021/7/21湘潭大学信息工程学院d)科学问题的提出从理论上说，航天器布局设计，可归结出“可数学模型化”和“不可或难数学模型化”两类问题。前者属很难的带性能约束的三维布局优化问题；后者多属工程复杂系统问题，涉及人脑思维模型问题，解决方法有二种：一是人工智能，基于智能的知识模型及其推理；二是人

4、机结合(Man-MachineSynergy)或人机合作(Human-ComputerCooperation)。航天器布局设计属交叉学科前沿课题的基础理论和应用基础研究，具有重要的科学意义。2021/7/21湘潭大学信息工程学院1.1.2布局优化问题研究进展布局问题(LayoutProblem)属于复杂的组合优化问题，即使最简单的一维布局也属于NPC问题。自1831年高斯(Gauss)研究布局问题开始，虽然经过几代人的努力，但迄今尚无成熟的理论和有效的数值计算方法。从理论上讲，布局问题可分为切段(Cutting-Stock)问题和装填(Packing)问题。2021/7/21湘潭大

5、学信息工程学院按照布局物体的布局维数分类a)一维布局问题b)二维布局问题c)三维布局问题2021/7/21湘潭大学信息工程学院a)一维布局问题一维布局问题中典型的例子是在给定长度的棒料上，切割长度不等的若干短棒，此类问题通常称为切段问题(Cutting-StockProblem)。解决方法：Faggioli[5]利用启发式算法提出了切段排序问题的数学模型和一个三步解法；Vasko[6]和Nitsche[7]分别利用树搜索算法和松弛算法来解决一维切段问题；PetridisVassilios等[8]利用遗传算法以动态的方式把问题的约束合并到适应度函数中。2021/7/21湘潭大学信息工

6、程学院b)二维布局问题二维布局问题包括：一刀切问题将某些不同大小的小矩形按照一刀切的原则排放在一个大矩形板材上，使面积浪费最小，这是剪床落料、玻璃切割、纸张切割中遇到的主要问题。所谓一刀切，是指切割总是从矩形板材的一边开始一直切到其对边，即每切一刀都将一个矩形分割成两个小矩形底盘装载问题底盘装载问题来源于运输、搬运中的货物摆放或装箱。将多个相同大小的立体箱子放入一立方体容器中，且要求放入的箱子越多越好。2021/7/21湘潭大学信息工程学院矩形布局问题(RectanglePackingProblems)矩形布局问题是将许多大小不同的二维矩形布置在一个大的矩形中，使面积覆盖率最大，这

7、是大规模集成电路设计中所碰到的主要问题。圆布局问题(CirclePackingProblems)圆布局问题是将许多大小相同或不同的圆布置在一个大的圆形、三角形或矩形容器中，使面积覆盖率最大[39]。这类问题大量地存在于几何、化学、生物学、工程和优化中，已经引起人们的很大关注[40]。通常不等圆装填问题还需满足一定的性能约束条件，譬如：惯性、平衡性、和稳定性约束等，我们把这种问题称为带性能约束的不等圆装填问题。2021/7/21湘潭大学信息工程学院二维不规则图形布局问题