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

一类多重组合优化问题的数学建模毕业论文目录摘 要1Abstract2第一章 绪论41.1课题背景41.2组合优化理论进展41.3本文的设计思想5第二章 组合优化理论62.1 定义62.2数学模型62.3特点62.4组合优化的典型问题72.5组合优化问题的求解方法72.5.1线性规划问题72.5.2整数规划模型112.5.3多目标规划模型12第三章 应用实例太阳能小屋设计133.1问题概述133.2问题分析133.3模型假设143.4符号说明143.5 铺设方案分析153.6局部最优铺设方案的确定153.6.1不同侧面光伏电池的选择163.6.2 小屋各个面光照强度的计算183.6.3光伏电池的铺设方法213.6.4变器以及串并联形式的选择243.7 总发电量、经济效益等参数的计算253.7.1 总发电量263.7.2 总经济效益263.73 成本及投资年限的计算27总结28致谢29参考文献30附录31第一章 绪论1.1课题背景在工程技术、经济管理、科学研究和日常生活等诸多领域中，人们经常遇到各种决策问题,如在一系列客观或主观的限制条件下，寻求使所关注的多个或某个指标达到最大（最小）的决策。例如，结构设计要在满足强度要求条件下选择材料的尺寸，使其总重量最轻；资源分配要在有限资源约束下制定各用户的分配数量，使资源产生的总效益最大；运输方案要在满足物质需求和装载条件下安排从各供应点到各需求点的运量和路线，使运输总费用最低；生产计划要按照产品工艺流程和顾客需求，制定原料、零件、部件等订购、投产的日程和数量，尽量降低成本使利润最高。上述决策问题通常称为优化问题。在给定有限集的所有具备某些条件的子集中，按某种目标找出一个最优子集的一类数学规划，又称组合规划。从最广泛的意义上说，组合规划与整数规划这两者的领域是一致的，都是指在有限个可供选择方案的组成集合中，选择使目标函数达到极值的最优子集。组合最优化发展的初期，研究一些比较实用的基本上属于网络极值方面的问题 ，如广播网的设计 、开关电路设计、航船运输路线的计划、工作指派、货物装箱方案等。自从拟阵概念进入图论领域之后，对拟阵中的一些理论问题的研究成为组合规划研究的新课题，并得到应用。现在应用的主要方面仍是网络上的最优化问题，如最短路问题、最大（小）支撑树问题、最优边无关集问题、最小截集问题、推销员问题等。而多重组合优化，则是在完成一个组合优化的基础上，按照纵向思维，层层推进，继续完成下一步组合优化问题，最终达到圆满解决问题的能力。常见的优化方法有无约束优化问题的解法、约束优化问题的解法、线性规划的解法、非线性规划问题的解法。1.2组合优化理论进展最优化是个古老的课题，长期以来，人们对最优化问题进行着探讨和研究。早在17世纪，英国科学家Newton发明微积分的时代，就已经提出极值问题，后来又出现Lagrange乘数法。1847年法国数学家Cauchy研究了函数值沿什么方向下降最快的问题，提出最速下降法。1939年前苏联数学家JI.B.KaHTOPOBHU提出了解决下料问题和运输问题这两种线性规划问题的求解方法。人们关于最优化问题的研究工作，随着历史的发展不断深入。但是，任何科学的进步，都受到历史条件的限制，直到20世纪三十年代，最优化这个古老课题并未形成独立的有系统的学科。 20世纪40年代以来，由于生产和科学技术研究突飞猛进地发展，特别是电子计算机日益广泛应用，使最优化问题的研究不仅成为一种 迫切需要，而且有了求解的有力工具，因此，最优化理论和算法迅速发展起来，形成一个新的学科。至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。最优化理论和算法在实际应用中发挥越来越大的作用。 现如今典型的组合优化问题有：旅行商问题(Traveling Salesman ProblemTSP)、加工调度问题(Scheduling Problem，如Flow-Shop，Job-Shop)、0-1背包问题(Knapsack Problem)、装箱问题(Bin Packing Problem)、图着色问题(Graph Coloring Problem)、聚类问题(Clustering Problem)等。这些问题描述非常简单，并且有很强的工程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，以致根本不可能在现有计算机上实现，即所谓的“组合爆炸”。正是这些问题的代表性和复杂性激起了人们对组合优化理论与算法的研究兴趣。1.3本文的设计思想针对上述课题背景中所论述的组合优化问题在求解中遇到的难题，本文在求解中将不会采用现有的方法，因为采用这些方法很难再计算上实现。本文将研究的是一类较为特殊的组合优化问题模型，由于现如今对组合优化问题尚未形成系统而成熟的数学研究理论和方法，因此采用传统的数学优化方法很难或者说根本无法解决本文中的太阳能小屋设计这样一个工程设计问题，因为这个问题所要考虑的优化目标过多，很难精确地用传统的数学优化理论解决。因此，本文另辟蹊径。最优化理论与算法是一个重要的数学分支，又称数学规划，它所研究的问题是讨论在众多的方案中什么样的方案最优以及怎样找出最优方案。对工程问题进行优化设计，本质上是根据优化设计理论，采用优化设计算法，运用计算机高质量高速度的完成设计任务。为此，首先要把工程设计问题转化为数学模型，即用数学表达式描述设计工程问题；然后，按照数学模型的特点选择优化设计方法及其计算程序，运用计算机求解最优解，即最优设计方案。因此，工程优化设计包括建立数学模型和运用优化设计方法求解这两个方面的重要内容。工程优化设计成败的关键是从工程实际命题中抽象出的正确的数学模型。这也是本文解决实际问题时所用到的最核心的设计思想，即采用数学建模的方法将实际的太阳能小屋设计的问题转化为一个多重组合优化模型，再利用数学建模的一般思路，借助于计算机程序设计，获得太阳能小屋的最佳设计方案。第二章 组合优化理论2.1 定义组合优化是通过对数学方法的研究去寻找离散事件问题的最优编排、分组、次序或筛选等等，其目标是从组合问题的可行解集中求出最优解，通常可描述为：令为所有状态构成的解空间，为状态对应的目标函数值，要求寻找最优解，使得对于所有的，有。组合优化往往涉及排序、分类、筛选等问题，它是运筹学的一个重要分支。2.2数学模型 设是有限集，是到实数集的映射，即是一个定义在上的函数，求，使得对于任意的有上述问题简称为组合优化问题，简记为：求。一个组合优化问题可以用二元组表示，其中表示可行解区域，中的任何一个元素称为该问题的可行解，表示目标函数，满足的可行解称为该问题的最优解。2.3特点l 组合优化问题的特点一是可行解集合是有限集合，理论上讲，只要将有限个点的目标值逐一比较，该问题的最优解一定可以得到，但是枚举是以时间为代价的。对于问题规模较小，枚举时间是可以接受的；然而，随着问题规模的增大，中解的个数会迅速增大，实际上要想遍历所有的解，几乎是不可能的。设问题的规模为，如果存在一个多项式，使得算法最多执行个基本步骤便可以得到解答，则这种算法称为多项式时间算法。多少年来，人们试图寻找解答各种组合问题的多项式算法，这种研究工作在一些问题上已经取得成功，其中包括最短路问题、最小支撑树问题、网络最大流问题、最小费用流以及运输问题等等。本文最后在寻找逆变器时，采用的便是多项式算法，因为此时逆变器的选择方案有限，可以用枚举的方法获得最佳方案选择。一般来说，组合优化问题通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全(难)问题 非线性的NP完全(难)问题；l 由于组合优化问题的解空间经常是离散的集合，所以组合最优化无法利用导数信息；l 综合上述特点，可以得出，精确地求解组合优化问题的全局最优解的“有效”算法一般是不存在的。因此，才会出现那么多典型的组合优化问题，却没有相应的解决方案和算法。2.4组合优化的典型问题在实际的的生产、生活中，组合优化问题有很多，也出现了一些经典的组合优化问题模型:覆盖问题、装箱问题、背包问题、指派问题、旅行商问题、影片递送问题、最小生成树问题、作业调度问题。2.5组合优化问题的求解方法虽然到目前为止，还没有形成对组合优化问题行之有效的解决方法，但对于某些特定的问题，已经有了比较好的解决方法，我们也相信，随着对组合优化理论的不断研究，以及相关科学技术的发展，对组合优化问题的解决方案会越来越多、越来越有效、越来越系统。以下列举几种典型的方法：完全枚举法、准完全枚举法、降序排列法、贪婪法、随机法、松弛法、分割法、分支定界法、邻域搜索法、 多起点邻域搜索法、人工智能法。从概念上来讲，这里所列的一些方法，有些是具有涵盖关系，比如说降序排列法，也应该属于贪婪法的一种。下面，本文先介绍目前已经发展出来的比较优秀的算法，其中一些算法，本文在求解中将会用到。2.5.1线性规划问题变量确定 称为决策变量，是问题中要确定的未知量 ，决策变量为可控的连续变量约束条件 决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的线性等式或不等式目标函数 决策变量的线性函数，按优化目标分别在目标函数前加上或 。解决线性规划问题常用单纯形法，具体如下：1. 单纯形表法单纯形法求解线性规划的思路：一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或最小值为止。这样问题就得到了最优解。为了确定初始基可行解，要首先找出初始可行基，其方法如下：对于线性规划问题从中一般能直接观察到存在一个初始可行基1 对所有约束条件是“”形式的不等式，可以利用化为标准型的方法，在每个约束条件的左端加上一个松弛变量。经过整理，重新对进行编号，则可得到下列方程组 2 将(*)式与目标函数组成个变量，m+1个方程的方程组。为了便于迭代运算，可将上述方程组写成增广矩阵若将Z看做不参与基变换的基变量，它与的系数构成一个基，这时可采用行初等变换将变换为零，使其对应的系数矩阵为单位矩阵。得到可根据增广矩阵设计下列初始单纯形表10000100将列中的换为，得到新的单纯形表。重复3-6，直到终止。2.5.2整数规划模型整数规划模型比线性规划增加了某些约束条件，来限制全部或部分决策变量必须取整数值。与线性规划相比决策变量是离散的变量。因此对求最优整数解的问题，有必要另行研究。我们称这样的问题为整数规划。解决整数规划问题常采用以下方法：1分支界定解法分支界定法可用于解纯整数或混合的整数规划问题。步骤如下：将要求解的整数规划问题称为问题A，将它与相应的线性规划问题称为B。B没有可行解，这时A也没有可行解，则停止。B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停止。B有最优解，但不符合问题A的整数条件，记它的目标函数值为。用观察法找问题A的一个整数可行解，一般可取试探，求得其目标函数值，并记作。以表示问题A的最优目标函数值；这时有 进行迭代。 第一步：分支，在B的最优解中任选一个不符合整数条件的变量，其值为，以表示小于的最大整数。构造两个约束条件将这两个约束条件，分别加入问题B，求两个后继规划问题。不考虑整数条件求解这两个后继问题。定界，以每个后继问题为一分支标明求解的结果，与其他问题的解的结果中，找出最优目标函数值最大值作为新的上界。从已符合整数条件的各分支中，找出目标函数值为最大者作出新的下界，若无可行解， 。 第二步：比较与剪支，各分支的最优目标函数中若有小于者，则减掉这支，不再考虑。若大于，且不符合整数条件，则重复第一步骤。一直到最后得到2割平面法割平面法首先不考虑变量是整数这一条件，但增加线性约束条件（割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有割掉任何整数可行解。这个方法就是指出怎样找到适当的割平面，使切割后最终得到这样的可行域，它的一个有整数坐标的极点恰好是问题的最优解。解法的关键就是怎样构造一个这样的“割平面”。步骤如下：令是相应线性规划最优解中为分数值的一个基变量，由单纯形表的最终表得到其中（Q是指构成基变量号码的集合），（K指构成非基变量号码的集合）将都分解成整数部分N与非负真分数之和，即而N表示不超过b的最大整数。如：代入(1) 得现在提出变量（包括松弛变量）为整数的条件(当然还有非负的条件)，这时，上式由左边看必须是整数，但由右边看，因为，所以不能为正，即这就是一个切割方程。2.5.3多目标规划模型在多指标的最优化问题背景下所建立起来的数学规划问题即为多目标规划问题。（多目标决策）在实际问题中，可能会同时考虑几个方面都达到最优，比如企业可能会要求产量最高，成本最低，质量最好，利润最大，环境达标等。多目标规划能更好地兼顾统筹处理多种目标的关系，求得更切合实际要求的解。多目标规划可以按照实际情况分主次，轻重缓急来考虑问题。也可直接用数学方法求非劣解。分层序列法将目标按重要性的次序分成最重要的目标、次重要的目标，如，然后按顺序将一个多目标规划问题转化为一系列单目标优化问题来求解。步骤：主要目标的最优集合为，再在集合内求次重要目标的最优解，设此时的最优解集合为，如此继续进行，直到求出最后一个目标函数的最优解。第一步 第二步 第 p步 最后求出的为最优解。 同样的组合优化问题，采用不同的近似求解方法，所得到的解、以及解的精度是不一样的。同样一个算法，用于不同的问题，其性能与效率也不尽相同。某些算法，只要稍微做些改变，就有可能导致解的精度或搜索效率的大幅度提高。因此，对于什么样的问题，应该采用什么样的方法，怎样使用这种方法才更有效果，在这方面人们已经进行了很多的研究。 第三章 应用实例太阳能小屋设计3.1问题概述在设计太阳能小屋时，需在建筑物外表面（屋顶及外墙）铺设光伏电池，光伏电池组件所产生的直流电需要经过逆变器转换成220V交流电才能供家庭使用，并将剩余电量输入电网。不同种类的光伏电池每峰瓦的价格差别很大，且每峰瓦的实际发电效率或发电量还受诸多因素的影响，如太阳辐射强度、光线入射角、环境、建筑物所处的地理纬度、地区的气候与气象条件、安装部位及方式（贴附或架空）等。因此，在太阳能小屋的设计中，研究光伏电池在小屋外表面的优化铺设是很重要的问题。附件1-7提供了相关信息。请参考附件提供的数据，对下列问题，分别给出小屋外表面光伏电池的铺设方案，使小屋的全年太阳能光伏发电总量尽可能大，而单位发电量的费用尽可能小，并计算出小屋光伏电池35年寿命期内的发电总量、经济效益（当前民用电价按0.5元/kWh计算）及投资的回收年限。问题1：请根据山西省大同市的气象数据，仅考虑贴附安装方式，选定光伏电池组件，对小屋（见附件2）的部分外表面进行铺设，并根据电池组件分组数量和容量，选配相应的逆变器的容量和数量。 在求解该问题时，都要求配有图示，给出小屋各外表面电池组件铺设分组阵列图形及组件连接方式（串、并联）示意图，也要给出电池组件分组阵列容量及选配逆变器规格列表。在同一表面采用两种或两种以上类型的光伏电池组件时，同一型号的电池板可串联，而不同型号的电池板不可串联。在不同表面上，即使是相同型号的电池也不能进行串、并联连接。应注意分组连接方式及逆变器的选配。3.2问题分析解决这一问题不仅仅是组合优化理论的应用，太阳能小屋的推广使用对于解决全球的能源危机和环境污染都有十分重要的意义。而太阳能小屋的设计建设具有系统性，在小屋的设计建设过程中，如何利用有限的面积使得光伏发电系统具有高效率低成本，至关重要的是其表面光伏电池的优化铺设和电池组件的联接方式。如果能行之有效的解决此类问题，对于今后类似的有关设计类的问题，都可以采用类似的方法。本题显然是一个组合优化问题，解决的关键是如何处理几个最优的目标，这也是难以处理的地方，采用传统的优化方法很难解决。问题要求采用贴附安装方式对小屋的外表面进行光伏电池的优化铺设。应对不同型号的太阳能板进行分析，计算出不同的光照条件下单位面积的电池板在单位时间内创造的收益和成本，进而可以估算出未来 35 年内各太阳能板的预期收益。然后比较不同光照条件下不同型号的光伏电池的收益，分析出屋顶的不同侧面应优先选择的电池类型。在不同侧面的电池铺设上，可以利用贪心算法来寻找最大覆盖方案，从而获得较大的总发电量。然后，对不同侧面电池组件的串并联方式进行优化设计，尽量减少逆变器成本。最后，求出最终方案下的总效益、发电总量以及回收年限。该问题可以看做是一个全局优化问题。每一种铺设方案都分为三个步骤，即选择光伏电池、选取覆盖方案和光伏组件的串并联。逆变器的选择取决于光伏组件的串并联方式的选择，从而影响整个系统的成本。每一种光伏组件的串联方式都需要一种满足匹配条件且成本最小的逆变器与其相对应。对不同型号光伏电池的选择，覆盖方案的选取和光伏电池的串并联形成了对方案的约束条件，即一个可行域。我们的目标就是找出效益最大的方案。方案难点是决策变量多，利用软件无法在较短的时间内得到全局的最优解。我们将整个设计过程按以上三个步骤分解为三个问题进行求解。根据“贪心算法”的思想，分步骤找出每个子问题的最优解，将得到的局部最优方案作为最终的铺设方案。对于逆变器的选择，用“多项式算法”枚举每一种逆变器选择的方案，在得出的所有结果中，从中比较得出最后的最优选择方案。3.3模型假设 只有处于同一表面并且型号相同的电池板可以串联。 光伏电池在光照强度低于电池表面太阳光辐照阈值时不能工作。 假设大同市在未来35年内的气象条件与典型气象年相同。 假设不考虑周围遮挡物对于小屋光照条件的影响。 （5）逆变器的体积对于铺设方案的影响。3.4符号说明符号描述净利润发电总价值成本太阳光辐射强度没峰瓦电池的价格总发电量3.5 铺设方案分析 该问题是全局优化问题，每一种铺设方案都分为三个步骤，可以按照多重组合优化的思想，即选择光伏电池、选取覆盖方案和光伏组件的串并联。逆变器的选择直接取决于光伏组件的串并联，从而影响整个系统的成本，每一种光伏组件的串联方式都需要一种满足匹配条件且成本最小的逆变器与其相对应。 对同型号光伏电池的选择，覆盖方案的选取和光伏电池的串并联形成了对方案的约束条件，即一个可行域。我们的目标就是找出效益最大的方案。方案难点是决策变量多，利用软件无法在较短的时间内得到全局的最优解。我们将整个设计过程按以上三个步骤分解为三个问题进行求解。根据“贪心算法”的思想，分步骤找出每个子问题的最优解，将得到的局部最优方案作为最终的铺设方案。 3.6局部最优铺设方案的确定目标分析1全年发电量最大其中： 2费用最小其中： 3目标整合：利润最大其中：约束分析1、电路约束（1）逆变器输入电压的峰值小于允许输入电压范围的最大值U(i, j)表示第i个光伏阵列的第 j并联串的电压，表示第i 个光伏阵列的型号逆变器的允许输入电压。（2）光伏电池组的输出功率小于等于逆变器的输入容量表示第个光伏阵列的输出功率，表示第个光伏阵列逆变器的额定电压与额定电流2、面积约束小屋共由六个面组成，以每个面左下角顶点为原点建立坐标系，每个光伏电池阵列的左下角坐标为，第组光伏电池阵列的长为，宽为，则第组光伏电池阵列内部可表示为：东面不可铺设光伏电池的区域可表示为：南面不可铺设光伏电池的区域可表示为：北面不可铺设光伏电池的区域可表示为：面积较大的屋顶不可铺设光伏电池的区域可表示为：则面积约束可表示为： 最优铺设模型3.6.1不同侧面光伏电池的选择选择出不同侧面最优的光伏电池可按以下步骤选择：根据题目中所给条件，写出转换效率，光伏电池的输出功率表达式，分析出单位面积的第种类型光伏电池在特定时间内创造的总利润。 将屋顶斜面等效为它在水平面和铅垂面的投影，屋顶南面与北面的散射辐射强度可以根据各自倾角进行直接计算。得到屋顶南北面的总辐射强度随着时间的变化规律。而由题目所给附件容易得出小屋周围的四个侧面光辐射强度随时间的变化规律。 将积分运算转化为求和运算，借助mathmatica编程得到小屋的不同面上采用不同类型的光伏电池的单位利润。比较不同光照条件下不同型号的光伏电池的收益，分析出不同侧面应优先选择的电池类型。具体操作如下：不同类型的光伏电池有不同的面积、功率以及能量转换效率，无法直接进行比较。从总效益最大的角度来考虑，当面积、气象条件均相同时，我们应该选取同一时间（如一年）内创造的净收益（即产生电能价值与电池成本之差）最大的光伏电池。下面进行具体计算以确定不同光照条件下应该选用的光伏电池的类型。将附件 3 中 24 种不同类型的光伏电池按照表中所给顺序编号为。假设第种类型的太阳能电池时刻接受到的总的太阳光的辐射强度为，面积为，每峰瓦的价格为，时刻光伏电池转换效率为；则与之间存在着一定的函数关系，令光伏电池的输出功率是太阳的辐射强度和转换效率的乘积，即根据实际情况可知，和都是关于的分段函数，当光的辐射强度小于电池表面太阳光辐照阈值(或者)时，光伏电池不工作，从而转换效率和为零；随着光的辐射强度的增加,保持为一常数，随着的增加而线性增加；当光的辐射强度大于一定值时，总的输出功率将保持不变，转换效率将随着光照强度的增加而减小。和与之间的具体函数关系可以根据附件 3 中的数据分析得到。以产品型号为的光电池为例，计算结果如下：根据公式得：将单位面积的第种类型光伏电池在时间内创造的总利润记为单位利润，则上式中，代表第种类型的光伏电池的峰值功率，为计算积分的时间区间，本文中取为35年。3.6.2 小屋各个面光照强度的计算在小屋的不同面上，光照条件存在着很大的差异，这对于光伏电池的选择有重要的影响。为了计算小屋的不同面上单位利润的值进而分析应该选用的电池型号，需要首先计算出不同面上在一年中的光照强度变化规律。 利用题中所给的数据容易得到小屋周围的四个侧面光辐射强度随时间的变化规律。而对于屋顶面，由于它与水平面存在一定的夹角，需要单独进行计算。下面着重分析屋顶的南北面的光辐射强度。 某一平面接受的总的太阳光辐射强度可以分为法向直射辐射强度和水平面散射辐射强度两个方向。直射辐射强度可转化为垂直于屋顶的辐射强度的大小来计算。而屋顶面的散射辐射强度的大小则可按照公式来统一计算。因此，屋顶南面辐射强度的计算关键在于求出方位角和太阳高度角，方位角和太阳高度角的具体计算方法可以参照给定的附件。再利用这两个角度将法向直射的辐射强度转化为垂直于屋顶方向计算，屋顶南面与北面的散射辐射强度的高度角可以根据各自倾角进行直接计算，并将两者相加。最终，可以得到屋顶南北面的总辐射强度随着时间的变化规律。 图1 辐射强度转化示意图如上图所示 每一束光线可以用空间中的向量表示，则X，Y，Z方向的辐射强度分量可以写为，对于屋顶南面，平面上一向量可表示为,从而其法向量可写为,从而 垂直于屋顶方向的辐射强度的可表示为： 顶南接收到的水平面散射的辐射强度可表示为：。 顶南受到的总辐射量= 综上，由上可求得顶南的辐射强度，同理可求得屋顶北的辐射强度。利用题中所给的数据，借助于Mathematica 软件编程得到小屋的不同面上采用不同类型的光伏电池时的单位利润（表1）。 表1 不同面上采用不同类型的光伏电池时的单位利润（元） 太阳能板类型 顶南顶北东南西北A1 1220.99-2197.99-1423.5-183.001-654.346-2376.19A2 1187.81-2190.57-1425.27-199.503-665.251-2366.65A3 1808.07-1988.54-1128.5249.014-274.393-2186.42A4 1198.63-2151.31-1392.46-177.006-638.835-2325.91A5 1085.77-1955.57-1266.63-163.141-582.426-2114.09A6 1079.5-1988.25-1293.32-180.258-603.183-2148.14B1 1809.93-1380.3-692.083546.934.23246-1688.8B2 1814.78-1410.88-715.024537.749-10.975-1722.81B3 1995.77-1149.19-470.742750.687215.692-1453.31B4 1658.07-1254.66-626.307504.9329.44032-1536.33B5 1977.52-1167.45-488.997732.435197.438-1471.57B6 1696.31-1295.14-649.805512.0073.12398-1584.42B7 1673.55-1276.57-640.155505.6063.75401-1561.86C1 1340.46-21.5603301.411813.043625.225-67.9402C2 1183.08-19.1566265.927717.539551.753-60.0957C3 1217.94-19.3783274.023738.812568.189-61.5119C4 1119.85-18.092251.744679.202522.283-56.8416C5 1244.54-20.0523279.817754.852580.468-63.1147C6 695.968-11.3477156.376422.073324.536-35.4335C7 696.992-10.3233157.4423.098325.561-34.409C8 701.763-11.4143157.699425.599327.253-35.6996C9 701.265-11.896157.213425.107326.764-36.1808C10 791.975-12.7674178.058480.353369.382-40.1707C11 818.988-13.0334184.261496.803382.07-41.3657最大值1995.77-10.3233301.411813.043625.225-34.409 上表中的单位利润仅考虑了单位面积的电池成本和发电收入，但并没有考虑平均单位面积的电池需要匹配的逆变器的成本。 由上表可知，对东面应该避免铺设A类和B类电池板，尽量铺设C类；南面也不应铺设A类电池板，尽量铺设B和C类，进一步考虑到南向墙面门窗较多B类电池板尺寸较大，在B和C类中，南面更加适宜铺设C类；对西向铺设B类和C类均有利润，故应优先考虑C类；屋顶前半部分铺设三类电池板均有利润，但B类电池板的利润更大，故顶南面应优先考虑B类电池板。 对于北面和屋顶后面，利润最大值均为负，故不应当铺设。对于东面的最大值仅为301.411元，根据题目所给的房屋数据可知，东向墙面和屋顶后部墙面除去门窗外，可铺设的面积分别为24.23平米（如表2）。在不考虑逆变器费用并完全铺满的的情况下，东墙35年的收益为7303.19元。与其他面相比，相对较小。而逆变器的最低单价（2900元），且如果逆变器需要不止一个时，有可能会导致亏本。因此，东面墙和屋顶后面也不铺设（后文的计算结果也表明东面铺设将会亏损）。 表2 不同部位面积及利润情况屋顶各个面 顶南顶北东南西北最大值1995.77-10.32301.411813.043 625.225 -34.409可铺设面积60.79 14.03 24.23 29.24 26.98 28.12 未考虑逆变器时的最大收益1-144.797303.19 23773.38 16868.57 -967.58 3.6.3光伏电池的铺设方法光伏电池的铺设按以下方式确定：不考虑光伏电池的铺设方法对逆变器总成本的影响,使小屋某一表面的效益最大，亦即表面覆盖的电池总面积达到最大。利用贪心算法找出覆盖率最大的方案。绘制出覆盖效果图，确定不同面所用电池型号及数目。具体实现如下：对于小屋的任何一个表面，以上出了应该选择的光伏电池。利用光伏电池对小屋的某一表面进行铺设时，可行的铺设方法有很多种。不同类型的铺设方法直接决定了总的覆盖面积的大小，即直接影响着总电能收入E。另外，它还会通过影响组件的串并联方式间接影响逆变器的总成本。 和上面的原因相同，在这里我们仍然不考虑光伏电池的铺设方法变化对于逆变器的总成本的影响。因此，在光伏电池型号确定的情况下，为了使小屋某一表面的效益达到最大，只需使该表面覆盖的总电池面积达到最大即可。 于是，该问题转化为给定几种矩形，如何利用这几种矩形实现一个区域的最大覆盖问题。其限制条件为用于覆盖的各个矩形之间不能有交叉。这是一个优化问题，其求解方法有以下几种：线性、非线性规划、贪心算法和智能优化算法等。针对本问题，决策变量较多的问题，采用非线性规划模型时求解的复杂度较高，我们采用贪心算法来进行求解。 贪心算法具有思维复杂度低、代码量小、运行效率高等优点，它的每一步的选择都是当前最佳的选择，但是最终得到的结果不一定是最优解。 取屋顶的南面为例，介绍该问题的贪心思路如下。 1) 问题的分解 屋顶的南面是一个中间挖空了的矩形。利用天窗的四条边界就可以将其分割为8 个子矩形。示意图如下（图 2）：b1天窗b2b3b4天窗b5b6b7b8 这7 个子矩形中每两个相邻的矩形又可以组合成矩形，如等，共 8 种组合。同理，三个相邻的矩形也可以组合一个矩形，如等， 共4 种组合。这样，共生成了20 个矩形。这20个矩形中的每个矩形都有可能为利用贪心算法进行求解时第一步覆盖的对象。 2) 贪心原则 根据表一中的结果，铺设屋顶南面的最佳光伏电池为B 类电池，共7 种。用这7 种电池对生成的20 个子矩形进行覆盖可以有140 种组合方案。利用贪心算法对问题进行求解时，第一次进行的覆盖应选择上述140 中组合覆盖方案中覆盖率（即覆盖面积与总面积之比）最高的那个覆盖。 第一次覆盖完成后，我们需要将未覆盖的区域按照1 中的方法进行重新分割，得到下一步覆盖时可能覆盖的矩形，假设有n 个。对于这n 个矩形，与7 种电池进行重新组合，得到进行第二次覆盖时可能的7n 种方案。根据局部最优的选择原则，我们仍然选其中覆盖率最大的方案进行覆盖。然后，不断重复上述工作，直到无法用这7种电池对屋顶进行覆盖为止。 根据以上分析，利用贪心算法进行求解的步骤可以表示如下： 1. 初始化。令t=1，需要覆盖的区域为R，可以选用的光伏电池为n 个。2. 对需要覆盖的不规则区域R 分割为若干个规则的矩形，得到t 步可能覆盖的矩形为n1 个。 3. 用步骤1 中的n 种类型的光伏电池对步骤2 中得到的n1 个矩形进行覆盖，得到种可能的组合方案，并计算出来每种方案对应的覆盖率。 4. 找出覆盖率最大的那个方案，将其作为第t 步的覆盖方案。 5. 令为覆盖的区域为R，判断能否进行下一次覆盖。若不能，则退出程序，此时的整体覆盖方案即为利用贪心算法得到的较优方案。否则，令t=t+1，转入步骤2。 根据题中所给的小屋的各个面的参数，结合前文中的分析结果，利用Mathmatica 软件进行编程可以得到小屋的不同侧面的较优的覆盖方案。根据计算结果，借助于AotoCAD软件绘制最终的覆盖效果图(图)。该覆盖方案中小屋的不同面所用的电池型号及数目列于表3。 表3 各个侧面用到的电池类型以及数目各个面西面南面顶面所用的电池型号及数量C3电池15 个C7 电池72 个C10 电池30 个B5 电池3个B3电池32个C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3图3小屋屋顶西面铺设效果图 B3图4小屋屋顶南面铺设效果图 图5 小屋南面覆盖效果图 可以看出，利用贪心算法得到的总体覆盖效果较好。但由于贪心算法受初始条件的影响较大，敏感性较强，因此部分地区的覆盖方案需要进行修正，以得到最优的结果。 3.6.4变器以及串并联形式的选择分投入产出公式可得，逆变器的选择将会影响到总的电能收入E和总的逆变器成本Ci。在输入功率相同的条件下，效率高的逆变器的输出功率更大，因而在单位时间内输出的电能也更多，最终得到的电能收入也更多。但是，效率高的逆变器价格也往往更贵。对于一种确定的光伏组件串并联形式，也肯定存在着一种最优的逆变器与其相对应。 不能孤立的对小屋不同面上逆变器的最佳选择进行讨论。逆变器的选择应该与组件的串并联形式以及选用的光伏电池相搭配，满足功率、电压匹配等方面的要求。由于各个逆变器的工作范围差别较大，当覆盖方案确定时，与其相匹配的逆变器可能会非常少。以图4中屋顶的南面覆盖方案为例，经过分析后符合条件的逆变器方案仅仅有3种。对于这些有限的选择方案，我们可以对不同的逆变器方案的成本以及效率进行比较得出最优的逆变器使用方案和组件串并联方案 因此，在逆变器以及串并联形式的选择方面，本文采用穷举法。具体包含两个步骤： 1. 对于5.2.2中得到的小屋的每一个侧面的覆盖方案，我们将首先找出满足电压、电流以及功率限制条件的所有可能的逆变器以及串并联形式选择方案。 2. 对每个方案的逆变器成本和效率进行计算。以成本最低的原则进行选取逆变器和串并联形式。 根据以上步骤，最终可以得到的各个面的串并联形式以及逆变器选择方案（如图6 7所示）。小屋南面的光伏组件较多，这里不列出来，详见附图1。SN7逆变器B5B5B5B3B3B3B3B3B3B3B3B3B3B3B3B3B3B3B3SN15逆变器B3B3B3B3B3B3B3B3B3B3B3B3B3B3B3B3图6 屋顶南面光伏电池串并联形式示意图 C3；lpC3SN12逆变器C3C3C3C3C3C3C3C3C3C3C3C3；lpC3C3图7 西面墙光伏电池串并联形式示意图 3.7 总发电量、经济效益等参数的计算 我们按照贪心算法的思想，分三个步骤找出了一个较优的铺设方案。下面对这种方案的总发电量、总经济效益以及收回成本的时间进行计算。 3.7.1 总发电量 首先将房屋的六个不同的表面进行编号，按照东面、南面、西面、北面、屋顶南面以及屋顶北面的顺序依次编号为1，2，,6。假设房屋的第i 个表面的第j 中类型的电池的数目为个，第i 个平面在时间t 时接受到的光辐射的强度为,则第1 年小屋发出的总电能为：上式中，t 的单位是天； 表示一年中第个面上第种类型的光伏电池发出的总电能，可以离散化到小时后用求和代替进行求解。而的值可以根据表3 直接得到。另外，根据假设3，容易得到小屋35 年内的总发电量：=+=根据题目附表中给出的太原一年内的气象数据，借助mathmatica编程计算得到35 年中小屋各个平面上的总发电量如下（表4）。 表4 35 年内小屋各个平面上的总发电量 类型 小屋的西面 小屋的南面 屋顶的南面 整个小屋 发电量（Kwh）38775.318347.83740534311763.7.2 总经济效益 由投入产出关系得到。光伏电池的总成本为各个面上各种类型的光伏电池的投入之和，即 上式中，和分别表示第种类型的光伏电池的峰瓦数和每峰瓦价格。 逆变器的总成本也有与上面类似的公式，这里不进行推导。小屋各个面上的不同类型的逆变器数量可以通过串并联形式得到（图6、图7、附图1）。利用mathmatica 软件编程得到小屋各个面上35 年的经济效益如下（表5）。 表5 光伏电池总利润类型小屋的西面小屋的南面屋顶的南面整个小屋35 年的总利润(元)6525.13056.957320182783.05 3.73 成本及投资年限的计算 通过分析计算总的发电量、成本和投资回收年限是很容易的，这几个量有以下关系：每块电池的价格=每峰瓦的价格*组件功率电池的成本=电池的块数（n）*每块电池的价格,n=1,2,24投资回收年限=投资总额/年现金净流量投资总额房屋墙面总成本计算过程总成本屋顶南面126700南面7610.4西面14100合计148410.4每年的总发电量 年现金净流量 回收年限 总结在解决引用的太阳能小屋设计问题时，引用利用贪心算法将复杂的全局优化问题进行了分解，使得问题大大简化，而且程序运行效率大大提高；利用 AUTOCAD软件绘制了小屋各个面的覆盖效果图，结果的呈现较为直观明了；综合分析了各个方面的因素对于铺设方案的影响，考虑问题比较全面且结果比较符合实际。 虽然多重组和优化问题的研究已经取得了很大进展，但目前我们所做的工作还远远不够，准确地求解组合优化问题的全局最优解的“有效”算法一般不易找到。因此，很多典型的组合优化问题，至今仍没有发现相应的解决方案和算法。如何选择优化算法，使其能较快收敛于准确解，对工程实践具有重要意义。研究多重组合优化问题对于资源紧缺当今世界意义非凡，我们应该在前人研究的基础上，另辟蹊径，将各种优化算法的优点结合，取长补短，构造出有特色有实用价值的算法。致谢四年的读书生活在这个季节即将划上一个句号，而于我的人生却只是一个逗号，我将面对又一次征程的开始。四年的求学生涯在师长、亲友的大力支持下，走得辛苦却也收获满囊，在论文即将付梓之际，思绪万千，心情久久不能平静。 伟人、名人为我所崇拜，可是我更急切地要把我的敬意和赞美献给一位平凡的人，我的导师。我不是您最出色的学生，而您却是我最尊敬的老师。您治学严谨，学识渊博，思想深邃，视野雄阔，为我营造了一种良好的精神氛围。授人以鱼不如授人以渔，置身其间，耳濡目染，潜移默化，使我不仅接受了全新的思想观念，树立了宏伟的学术目标，领会了基本的思考方式，从论文题目的选定到论文写作的指导,经由您悉心的点拨,再