《信息与计算机科学毕业论文.doc》由会员分享，可在线阅读，更多相关《信息与计算机科学毕业论文.doc（29页珍藏版）》请在三一办公上搜索。
1、广 东商学院2012-JX16-本科毕业论文(设计)生活中的一些最优化问题研究院 （系）数学与计算科学学院专 业信息与计算科学学 号08251001133学生姓名游佳能指导教师柴啸龙提交日期2012年5月20日毕业论文(设计)成绩评定表毕业论文（设计）指导教师评语及成绩成绩 指导教师签名 年 月 日毕业论文（设计）复评教师评语及成绩成绩 复评教师签名 年 月 日毕业论文（设计）答辩评语及成绩成绩 答辩委员会主席签名 年 月 日毕业论文（设计）总成绩（五级记分制） 院（系）负责人签名 年 月 日TITLE: Some Optimization Problem Research in LifeMA
2、JOR: Information and Computing ScienceAPPLICANT: Jia-Neng YOUSUPERVISOR: Xiao-Long CHAI内容摘要数学与我们日常生活密切相关，日常生活中的许多问题来源于数学思想的应用。在掌握一定的数学基础的前提下，结合日常当中可能出现的数学问题，通过适当的规划安排，运用数学原理求解出行之有效的最优化方案。本文的主要研究方向是通过对日常生活中经常涉及到的若干最优化问题进行归纳总结，分析其所涉及的数学原理并将其推广应用到其他生活案例当中去。本文的主要贡献是通过对运输成本问题和效益分配问题的最优化分析，详细地介绍了表上作业法和Sha
3、pley值法的求解过程，指出了模型存在的缺陷和不足，并对模型进行修改以及推广应用。关键词: 最优化；表上作业法；Shapley值；推广应用AbstractMathematics to our daily lives are closely related to many of the problems in our daily life from the application of mathematical thinking. Master the mathematical basis of the premise of the mathematical problems that may
4、arise in day-to-day which, through appropriate planning arrangements, the use of mathematical principles for solving optimization program effective.The main research directions to daily life often related to certain optimization problem to summarize,analyze its mathematical principles involved and p
5、romote the application to which the case of other life to go.The main contribution of this paper is the optimization analysis on transportation costs and efficiency of the distribution of the mostdetailed description of the solution process of the tabular method and the Shapley Value,pointed out tha
6、t the model defects and deficiencies,and to modify the model and application.Keywords: Optimization; Tabular method; Shapley method; Application目 录1研究的意义与目的12研究现状分析12.1研究的方法12.2研究现状23本文研究方向23.1运输调配方向33.2 效益分配方向34运输调配问题最优化研究34.1初始方案的给定44.2最优性检验与方案的调整64.3表上作业法的总结84.4表上作业法的改进及其推广应用95效益分配问题最优化研究125.1 n人
7、合作对策和Shapley值125.2 Shapley值的推广应用145.3 Shapley值法存在的缺陷165.4 其他求解方法175.4.1协商解175.4.2 Raiffa解186传统模型的改进设想186.1最小元素法的改进设想186.2效益分配的改进设想207总结与展望207.1本文的主要贡献207.2本文主要的改进方案217.3研究展望21参考文献22致谢23生活中的一些最优化问题研究1研究的意义与目的最优化问题，是指在日常生活中通过适当的规划安排，使得完成一件事所用的费用最少、路线最短、时间最短、产值最高、容积最大等的效率与分配问题，也就是要在各种方案中，寻求一个最节约、合理的方案。
8、解决这类问题要注意两点: 一是明确问题，即通过问题描述中已知的数量关系把生活问题转化为单纯的数学问题，我们称之为数学建模的过程；二是建模后的求解问题，即用相关的数学知识求解出最优的处理方案1。数学与我们日常生活密切相关，日常生活中的许多问题来源于数学思想的应用。在掌握一定的数学基础的前提下，结合日常生活当中可能出现的数学问题，通过适当的规划安排，运用数学原理求解出行之有效的最优化方案。本文通过对日常生活中经常涉及到的若干最优化问题进行归纳总结，分析其所涉及的数学原理并将其推广应用到其他生活案例当中去2。因而，引导学生学习应用数学，从众多的解决方案中寻求到最优化的方案，使他们感受到数学的应用价值
9、，是一种能够调动高校学生积极学习数学的办法3。2研究现状分析2.1研究的方法不同类型的最优化问题可以有不同的最优化方法，即使同一类型的问题也可有多种最优化方法。反之，某些最优化方法可适用于不同类型的模型。目前，最优化问题的求解方法大致可分成解析法、直接法、数值计算法。解析法：这种方法只适用于目标函数和约束条件有明显的解析表达式的情况。求解方法是：先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用求导数的方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法。直接法：当目标函数较为复杂或者不能用变量显函数描述时，无法用解析法求必要条件。此时可采用直接搜索的方法
10、经过若干次迭代搜索到最优点。这种方法常常根据经验或通过试验得到所需结果。对于一维搜索(单变量极值问题)，主要用消去法或多项式插值法；对于多维搜索问题(多变量极值问题)主要应用爬山法。数值计算法：这种方法也是一种直接法。它以梯度法为基础，所以是一种解析与数值计算相结合的方法4。2.2研究现状最优化一般可以分为最优设计、最优计划、最优管理和最优控制等四个方面。最优设计:世界各国工程技术界,尤其是飞机、造船、机械、建筑等部门都已广泛应用最优化方法于设计中，从各种设计参数的优选到最佳结构形状的选取等，结合有限元方法已使许多设计优化问题得到解决5。最优计划:现代国民经济或部门经济的计划，直至企业的发展规
11、划和年度生产计划，尤其是农业规划、种植计划、能源规划和其他资源、环境和生态规划的制订,都已开始应用最优化方法。一个重要的发展趋势是帮助领导部门进行各种优化决策。最优管理：一般在日常生产计划的制订、调度和运行中都可应用最优化方法。随着管理信息系统和决策支持系统的建立和使用，使最优管理得到迅速的发展。最优控制：主要用于对各种控制系统的优化。例如，导弹系统的最优控制，能保证用最少燃料完成飞行任务,用最短时间达到目标;再如飞机、船舶、电力系统等的最优控制，化工、冶金等工厂的最佳工况的控制。计算机接口装置不断完善和优化方法的进一步发展，还为计算机在线生产控制创造了有利条件。最优控制的对象也将从对机械、电
12、气、化工等硬系统的控制转向对生态、环境以至社会经济系统的控制6。3本文研究方向虽然现今最优化问题研究渐趋成熟，也应用到很多不同的领域，但对日常生活存在的最优化问题的研究仍存在一定的空缺。本文将通过对日常生活中经常涉及到的一些最优化问题进行归纳总结，分析其所涉及的数学原理并将其推广应用到其他生活案例当中去。因而，如何运用最优化原理解决生活中存在的实际问题将是本文研究的主要方向，主要针对生活中的运输成本问题和效益公平分配问题进行研究分析7。3.1运输调配方向运输成本问题涉及了很多生活领域，生产运输、物流运输、仓库调配等等，但其主要的数学模型都是相似的，因此掌握这种问题的解决方法有着重要的作用。文中
13、通过对生产运输问题进行分析，运用表上作业法列出详细的求解过程，并进行推广应用8。3.2 效益分配方向在日常的社会生活中，若干实体相互合作结成联盟或集团，常能比个体单独行动获得更多的经济利益或社会效益。但是效益公平分配问题经常成为他们合作的阻碍，如何合理地分配这些效益是促进合作的前提，也能给合作带来更多的效益。文中通过对合作效益分配问题进行分析研究，运用Shapley法列出详细的求解过程，并对模型进行修改推广。4运输调配问题最优化研究运输问题是社会经济生活和军事活动中经常出现的优化问题，是特殊的线性规划问题，它是早期的线性网络最优化的一个例子。最早研究这类问题的Hitchcock以及后来的Koo
14、pmans独立地提出运输问题并详细地对该问题加以讨论；同时KahTopoBny也围绕着运输问题作了大量的研究，因此运输问题又称为Hitchcock问题或Kantorvich问题。运输问题不仅代表了物资合理调运、车辆合理调度等问题，有些其他类型的问题经过适当变换后也可以归结为运输问题，如指派问题、最短路问题、最小费用流问题可转化为运输问题或转运问题9。运输问题在运筹学教学过程中占有重要地位，并且得到了众多学者的广泛关注，取得了许多重要的研究成果。但就在常用的运筹学教材中仅仅介绍运输问题的基础知识，对于运输问题的前沿发展涉及甚少，这远远不能反映当前对运输问题的深入研究。为此，在介绍运输问题的基本理
15、论和方法的基础上，运用表上作业法对类似问题进行推广运用10。【例1】某食品加工公司经销的主要产品之一是酸奶。该公司下面设有三个加工厂，每天酸奶的生产量分别为：，。该公司把这些酸奶分别运往四个地区的门市部进行销售，各地区每天的销售量分别为：，。已知从每个加工厂到对应的各销售门市部每吨酸奶的运价如表4-1所示，问该食品公司该如何调运，在满足各门市部销售需要的前提下，使得总运费支出达到最少。表4-1加工厂门市部 3 11 3 101 9 2 87 4 10 5以下运用表上作业法求解运输问题，首先给出一个初始方案，一般来讲，这个方案不会是最好的。因此需要给出一个判别准则，并对初始方案通过不断地调整、改
16、进，一直到求得最优方案为止10。先列出这个问题的的产销平衡表和单位运价表，见表4-2和表4-3表4-2 产销平衡表产地销地 产量749销量3 6 5 6表4-3 单位运价表产地销地 3 11 3 101 9 2 87 4 10 54.1初始方案的给定给定初始方案的方法有很多，一般希望方法简便易行，尽量能给出较好的方案，减少迭代的次数，这里采用最小元素法。最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，依此类推，一直到给出全部方案为止10。第一步：从表4-3的单位运价表中找出最小运价为1（如果有两个最小运价时任选其一），即从生产的酸奶首先供应需求。由于每天生产4t，每
17、天需要3t,即每天生产的除了要满足全部需求之外，还剩下1t。因此在表4-2中（，）的交叉格中填上数字3，表示调运3t酸奶给，再在表4-3中将所在的这一列运价划去，表示已经满足的需求，无需继续调运给它。第一步得到的结果如表4-4和表4-5所示。表4-4销地产地 产量3749销量3 6 5 6表4-5销地产地 3 11 3 101 9 2 87 4 10 5第二步：从表4-5中未划去的元素之中找出最小的运价为2，即每天剩余的酸奶要供应给。每天需要5t，每天只能供应1t，因此在表4-4（，）交叉处填写1，划去表4-5 所在的这一行运价，表示生产的酸奶已分配完，其结果见表4-6和表4-7.表4-6产地
18、销地 产量3 1749销量3 6 5 6表4-7产地销地 3 11 3 101 9 2 87 4 10 5第三步：同理再从表4-7中未划去的元素之中找出最小的元素为3，即生产的酸奶应优先满足需求。每天生产7t，还缺4t。因此在表中（，）交叉格内填上4，由于的需求此时已经满足，在表4-7中划去所在列的元素。这样一步一步地进行下去，直到单位运价表上所有元素都被划去为止，这时在产销平衡表上可以得到一个调动方案（见表4-8），这个调动方案总的运费为86元。表4-8销地产地 产量 4 33 1 6 3749销量3 6 5 64.2最优性检验与方案的调整最小元素法给出的是运输问题的一个基可行解，需要通过最
19、优性检验判别该解的目标函数值是否达到最优，当为否时，应进行调整得到优化。检验的方法常用的有闭回路法和位势法，这里采用闭回路法。运输问题中的闭回路是指调运方案中的一个空格和几个有数字格的水平和垂直之间的连线包围成的封闭回路11。 构建闭回路是为了计算解中各非基变量（对应空格）的检验数，方法是令某一非基变量取值为1，通过变动原基变量的值找出一个的可行解，将其与原来的基可行解进行比较。在表4-8中给出了一个调运方案中，（，）是空格，即为非基变量。令，相应地为了找到新的可行解，原有基变量中需减1，加1，减1，见表4-9。表中由（，），（，），（，），（，）4个格的水平和垂直连线围成的闭回路，该闭回路除
20、（，）为空格之外，（，），（，），（，）均有数字的格。将新可行解与原来解费用比较：从0变成1，运费加3元，减1，运费减少3元，加1，运费加2元，减1，运费减少1元，由此新可行解较原来解运费增加了（3-3+2-1）=1元，称为检验数，将其填入检验数表中（表4-10）的（，）相应的交叉格位置。类似地（，）为空格，可通过该空格找出一条其余顶点都有数字格的闭回路，求得其相应的检验数为（7-1+2-3+10-5）=10，将其填入检验数表4-10的（，）的交叉格位置，因为任意的非基向量均可表示为基向量的唯一线性组合，因此通过任一空格可以找到，并且只能找到唯一的闭回路，并计算得到对应表4-8中解全部非基变量
21、的检验数12。表4-9产地销地产量31（+1）34（-1）373（-3）21（+1）4639销量3656表4-10 检验数表产地销地 1 2 1 -110 12如果检验数表中所有的数字都大于等于零，表明对调运方案作出任何改变都不会导致运费减少，即给定的方案为最优方案。但在表4-10中，（,）格的检验数是负的，说明方案仍需进一步调整。改进的方法是从检验数为负数的格出发（当存在两个以上负数检验数时，从绝对值最大的负检验数格出发），这里是从（,）格出发，作一条除该空格以外其余顶点都为有数字格而组成的闭回路。在这条闭回路上，按照以上讲的方法对运量作最大限度的调整。从表4-9看出，为了把生产的酸奶调运给
22、，就要相应减少调运给的酸奶和调运给的酸奶，才能得到新的平衡。这两个格内，较小运量为1，因此最多只能调运1t酸奶给。由此得到一个新的调运方案（见表4-11）。这个新方案的运费为85元。表4-11产地销地 产量 5 23 1 6 3749销量3 6 5 6表4-11给出的调运方案是否达到最优，仍需对这个方案的每一个空格求出其检验数（见表4-12）。由于检验数表中所有的检验数大于等于零，因此肯定表4-11给出的方案是最优方案。表4-12 检验数表销地产地 0 22 19 124. 3表上作业法的总结运输问题成本最优化解决方法主要有三个步骤，可以用以下流程图总结出来，见图4-1。图4-1 表上作业法计
23、算步骤框图否分析实际问题列出产销平衡表及单位运价表确定初始调运方案求检验数所有检验数0找出绝对值最大的负检验数用闭回路调整，得出新的调运方案得到最优方案算出总的运价是4.4表上作业法的改进及其推广应用前面所讲的表上作业法的计算理论，都是以产销平衡为前提的，即。但实际问题中大部分产销是不平衡的。为了更好地应用表上作业法，就需要把产销不平衡的问题转化成产销平衡的问题13。当产大于销时，运输问题的数学模型可写为 (4.1a)s.t.如果总的产量大于销量，可以考虑多余的物资在那一个产地库存的。设是产地的库存量，于是可以得到 (4.2) (4.3)令 (4.4) 将(4.2)-(4.4)分别代入或替换(
24、4.1a)-(4.1d)，得到 (4.5a)s.t由于（4.5）模型中，是一个产销平衡的运输问题。因此当产量大于销量时，只需增加一个假想的销地j=n+1(实际上库存销地的单位运价，就可以转化成为一个产销平衡的运输问题。类似地，当销量大于产量时，可以在产销平衡中增加一个假想的产地，该地产量为，在单位运价表中令从该假想产地到各销地的运价，同样可以转化成为一个产销平衡的运输问题。【例2】设有三个产地生产某种物资，三个产地的产量分别为7t、5t、7t，四个销地需要该种物资，销量分别为2t、3t、4t、6t，又知各产销地之间的单位运价见表4-13，试解出总运费最少的调动方案。表4-13 单位运价表产地销
25、地 2 11 3 410 3 5 97 8 1 2【解】产地总产量为19t，销地总销量为15t，因此这是产销不平衡的运输问题。可按照上述方法转化成为产销平衡的运输问题，转化之后其产销平衡表和单位运价表分别见表4-14、见表4-15.表4-14 产销平衡表产地销地 库存产量757销量2 3 4 6 4表4-15 单位运价表销地产地 库存2 11 4 4 010 3 9 9 07 8 2 2 0对表4-14、表4-15可以用表上作业法计算求出最优方案如表4-16表4-16 最优方案产地销地 库存产量2 3 2 3 2 4 3757销量2 3 4 6 45效益分配问题最优化研究在日常的社会生活中若干
26、实体（如个人、公司、协会等）相互合作结成联盟或集团，常能比个体单独行动获得更多的经济利益或社会效益。但是效益公平分配问题经常成为他们合作的阻碍，如何合理地分配这些效益是促进合作的前提，也能给合作带来更多的效益14。【例3】设有甲乙丙三人经商。若单独经营，每人仅能获利1万元；甲乙合作可获利7万元；甲丙合作可获利5万元；乙丙合作可获利4万元；三人合作则可获利11万元。问三人合作时怎么合理地分配11万元的收入。【解】设甲乙丙三人各得万元，从题目中给定的条件我们可列出满足条件的一组方程根据上述这两组方程可求出许多组满足条件的解组，如等这种求解的方案最为普遍，但仍存在一定的局限性，当条件不够多的时无法求
27、出最优的解组。以下将介绍一种其他的方法求解这类问题。5.1 n人合作对策和Shapley值n个人从事一项经济活动，对于他们之中的若干人组合的每一种合作（单人也视为一种合作），都可以得到一定的效益，仅当人们之间的利益是非对抗性时，合作中人数的增加不会引起其效益的减少。这样全体n个人的合作将带来更大的效益。n个人的集合以及各种合作的效益就构成n人合作对策，Shapley值是分配这个效益的一种方案15。定义如下：设集合，如果对于I的任一子集s都对应着一个实值函数v(s)，满足 (5.1) (5.2)称为n人合作对策，v为对策的特函数。在上面所述的经济活动中，I定义为n人集合，s为n人集合中的任一种合
28、作，v(s)为合作中s的效益。用表示I的成员i从合作的最大效益v(I)中应得到的一份收入。叫做合作对策的分配，满足，Shapley值由特征函数v确定，记作。对于任意的子集s，记，即s中各成员的分配。对一切，满足的x组合的集合称的核心。当核心存在时，即所有的s的分配都小于s的效益。可以将Shapley值作为一种特定的分配，即。Shapley值， （5.3） （5.4）其中是I中包含i的所有子集，|s|是子集s中的元素数目（人数），w(|s|)是加权因子，si表示s去掉i后的集合。接下来利用这组公式计算例3给出的三人经商问题的分配，以此来解释公式的用法和意义。甲乙丙三人记为，经商获利的定义为I上的
29、特征函数，即。容易验证v满足(5.1)和(5.2)。为计算首先找出I的所有子集，然后s跑遍，将计算结果记入表5-1.最后将表中末行相加得到。表5-1 三人经商中甲的分配的计算s1 1,2 1,3 Iv(s)1 7 5 10v(s1)0 1 1 4v(s)-v(s1)1 6 4 6|s|1 2 2 3w(|s|)1/3 1/6 1/6 1/3w(|s|) v(s)-v(s1)1/3 1 2/3 2同样按照Shapley值方法可以计算出，。所以，甲乙丙三人合作合理的分配分别为4万元、3.5万元、2.5万元。5.2 Shapley值的推广应用【例4】设沿河有三城镇1，2，和3，地理位置如图2所示。污
30、水需要处理后才能排入河中。三个城镇既可以单独建立污水处理厂，也可以联合建厂，用管道将污水集中进行处理（污水由河流上游的城镇向下游城镇输送）。用Q表示污水量（t/s），用L表示管道长度（km），按照经验公式，建立处理厂的费用为，铺设管道费用为已知三城镇污水量为的数值如图5-1所示。试从节约总投资的角度为三城镇制定最优的污水处理方案。如果联合建厂，各城镇如何分担费用。图5-1 三城镇地理位置示意图20km河流38km213【解】三城镇污水处理共有以下5种方案，以下计算出投资费用以作比较。（1） 分别建厂。其投资分别 为：总投资（2）1，2合作，在城2建厂。投资为：总投资（3）2，3合作，在城3建厂
31、。投资为：总投资（4）1，3合作，在城3建厂。投资为：这个费用超过1，3分别建厂的费用。合作没有效益，不可能实现。（5）三城合作，在城3建厂。总投资为：比较结果千元最小，所以应选择联合建厂方案。接下来的问题是如何分担费用。总费用中有3部分：联合建厂费为；城1至2的管道费为；城2至3的管道费为.城3提出，由三城按污水量比例5:3:5分担，是为城1，2铺设的管道费，应当由他们担负；城2同意，并提出由城1，2按污水量之比5：3分担，则应当由城1自己担负；城1提不出反对意见，按上述办法各城应当分担的费用：结果表明城2，3分担的费用均比单独建厂费用C(2)，C（3）小，而城1分的费用却比C(1)大。显然
32、，城1不能同意这种分担总费用的办法。为促成三城联合建厂以节约总投资，应当寻求合理分担总费用的方案。三城的合作节约了投资，产生了效益，是一个n人合作对策问题，可以运用Shapley值法合理地分配这个效益。把分担费用转化成分配效益，就不会出现城1联合建厂分担的费用反比单独建厂费用高的情况了。将三城分别记为I=(1，2，3)，联合建厂比单独建厂节约的投资定义为特征函数。于是有三城联合建厂的总效益为64千元。用Shapley值作为这个效益的分配标准，城1应分得的份额的计算结果列入表5-1中，得到。类似地算得。不难验证，。表5-1 污水处理问题是的计算s1 1,2 1,3 Iv(s)0 40 0 64v
33、(s1)0 0 0 25v(s)-v(s1)0 40 0 39|s|1 2 2 3w(|s|)1/3 1/6 1/6 1/3w(|s|) v(s)-v(s1)0 6.7 0 13最后，同理运用Shapley值法可以算出在联合建厂方案总投资额556千元中各城分担费用为：城1是；城2是；城3是。5.3 Shapley值法存在的缺陷Shppley值法以严格的条件为基础，在处理合作对策的分配问题时比较公正合理等，但是它需要知道所有合作方的获利，即需要定义的所有子集（共个）的特征函数，这实际上是很难做到的。如n个单位共同合作治理污染，第i方单独治理的投资和n方共同合作治理的投资Y，这通常是已知的。为了度
34、量第i方在合作中的“贡献”，还常需要设法知道第i方不参加时其余n-1方所需的投资。特征函数应定义为共同合作的获利，即节约的投资，有显然除此之外还有很多无法获取，无法应用Shapley值方法求解。5.4 其他求解方法以下仍以例3提出的三人经商问题为例，介绍两种其它的解决方法。【例4】我们只知道全体合作的获利，记作，及无i参加时其他n-1方合作的获利，记作试确定各方对全体合作获利的分配，记得在三人经商问题， 求5.4.1协商解16分配分别按照以下两步进行。先从n个n-1方合作的获利求出各方分配的下限，即求解得到 再求出按下限分配后全体合作获利的剩余为，它通常是较小的部分，经过协商将其平均分配，于是
35、最终的分配结果为剩余，它等价于对三人经商问题，5.4.2 Raiffa解Howard Raiffa提出的解决办法按以下的步骤进行17：（1）按照n个n-1方合作的获利得到了各方分配的下限，即协商解中的，作为分配的前提；（2）当j方加入（原来无j的）n-1方合作时，计算获利的增加，即j方的边际效益17，就是最小距离解中的上限；（3）按两步分配：首先先由j方和无j方的n-1方平分，然后n-1方再等分，即其中n-1方是在的基础上分配的；（4）j取1,2,n，再重复第3步，然后求和、平均，得到最终分配为 (5.5) 将，代入，(5.5)式可表为对三人经商问题，6传统模型的改进设想6.1最小元素法的改进设想表上作业法是求解运输成本最优化问题的常用而有效的方法，但是表上作业法求解过程比较复杂，而且如果供求双方数量比较多，检验数的计算和闭回路的调整更容易出错。因此，如果初始方案的给定能尽可能地趋向最优化，在运输成本预算比较充裕的情况下可以直接采用初始方案。初始方案给定的方法最常用的是最小元素法，而最小元素法的物资配送是满足运输配送的每一次单位运价都最小化，但从整体上考虑，它并不能保证总运价达到最小，也不能在第一时间满足需求点的一定量的物资需求。因此，本文将对最小元素法的配送过程进行调整，首先通过对物资配送环节进行改进，可以在第一时间满足某些需求点的物资需求，然后通过增加一临时
