一类多重组合优化问题的数学建模论文.doc

一类多重组合优化问题的数学建模毕业论文 目录 摘 要 1 Abstract 2 第一章 绪论 4 1.1课题背景 4 1.2组合优化理论进展 4 1.3本文的设计思想 5 第二章 组合优化理论 6 2.1 定义 6 2.2数学模型 6 2.3特点 6 2.4组合优化的典型问题 7 2.5组合优化问题的求解方法 7 2.5.1线性规划问题 7 2.5.2整数规划模型 11 2.5.3多目标规划模型 12 第三章 应用实例——太阳能小屋设计 13 3.1问题概述 13 3.2问题分析 13 3.3模型假设 14 3.4符号说明 14 3.5 铺设方案分析 15 3.6局部最优铺设方案的确定 15 3.6.1不同侧面光伏电池的选择 16 3.6.2 小屋各个面光照强度的计算 18 3.6.3光伏电池的铺设方法 21 3.6.4变器以及串并联形式的选择 24 3.7 总发电量、经济效益等参数的计算 25 3.7.1 总发电量 26 3.7.2 总经济效益 26 3.73 成本及投资年限的计算 27 总结 28 致谢 29 参考文献 30 附录 31 第一章 绪论 1.1课题背景 在工程技术、经济管理、科学研究和日常生活等诸多领域中，人们经常遇到各种决策问题,如在一系列客观或主观的限制条件下，寻求使所关注的多个或某个指标达到最大（最小）的决策。例如，结构设计要在满足强度要求条件下选择材料的尺寸，使其总重量最轻；资源分配要在有限资源约束下制定各用户的分配数量，使资源产生的总效益最大；运输方案要在满足物质需求和装载条件下安排从各供应点到各需求点的运量和路线，使运输总费用最低；生产计划要按照产品工艺流程和顾客需求，制定原料、零件、部件等订购、投产的日程和数量，尽量降低成本使利润最高。上述决策问题通常称为优化问题。 在给定有限集的所有具备某些条件的子集中，按某种目标找出一个最优子集的一类数学规划，又称组合规划。从最广泛的意义上说，组合规划与整数规划这两者的领域是一致的，都是指在有限个可供选择方案的组成集合中，选择使目标函数达到极值的最优子集。 组合最优化发展的初期，研究一些比较实用的基本上属于网络极值方面的问题 ，如广播网的设计 、开关电路设计、航船运输路线的计划、工作指派、货物装箱方案等。自从拟阵概念进入图论领域之后，对拟阵中的一些理论问题的研究成为组合规划研究的新课题，并得到应用。现在应用的主要方面仍是网络上的最优化问题，如最短路问题、最大（小）支撑树问题、最优边无关集问题、最小截集问题、推销员问题等。 而多重组合优化，则是在完成一个组合优化的基础上，按照纵向思维，层层推进，继续完成下一步组合优化问题，最终达到圆满解决问题的能力。常见的优化方法有无约束优化问题的解法、约束优化问题的解法、线性规划的解法、非线性规划问题的解法。 1.2组合优化理论进展 最优化是个古老的课题，长期以来，人们对最优化问题进行着探讨和研究。早在17世纪，英国科学家Newton发明微积分的时代，就已经提出极值问题，后来又出现Lagrange乘数法。1847年法国数学家Cauchy研究了函数值沿什么方向下降最快的问题，提出最速下降法。1939年前苏联数学家JI.B.KaHTOPOBHU提出了解决下料问题和运输问题这两种线性规划问题的求解方法。人们关于最优化问题的研究工作，随着历史的发展不断深入。但是，任何科学的进步，都受到历史条件的限制，直到20世纪三十年代，最优化这个古老课题并未形成独立的有系统的学科。 20世纪40年代以来，由于生产和科学技术研究突飞猛进地发展，特别是电子计算机日益广泛应用，使最优化问题的研究不仅成为一种 迫切需要，而且有了求解的有力工具，因此，最优化理论和算法迅速发展起来，形成一个新的学科。至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。最优化理论和算法在实际应用中发挥越来越大的作用。 现如今典型的组合优化问题有：旅行商问题(Traveling Salesman Problem－TSP)、加工调度问题(Scheduling Problem，如Flow-Shop，Job-Shop)、0-1背包问题(Knapsack Problem)、装箱问题(Bin Packing Problem)、图着色问题(Graph Coloring Problem)、聚类问题(Clustering Problem)等。这些问题描述非常简单，并且有很强的工程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，以致根本不可能在现有计算机上实现，即所谓的“组合爆炸”。正是这些问题的代表性和复杂性激起了人们对组合优化理论与算法的研究兴趣。 1.3本文的设计思想 针对上述课题背景中所论述的组合优化