信息与计算机科学毕业论文

1、本科毕业论文本科毕业论文(设计设计) 生活中的一些最优化问题研究生活中的一些最优化问题研究 院院 （系）（系）数学与计算科学学院 专专 业业信息与计算科学 学学 号号08251001133 学生姓名学生姓名游佳能 指导教师指导教师柴啸龙 提交日期提交日期2012 年 5 月 20 日 2012-jx16- 广广 东东 商学院商学院 毕业论文毕业论文( (设计设计) )成绩评定表成绩评定表 毕业论文（设计）指导教师评语及成绩毕业论文（设计）指导教师评语及成绩 成绩成绩 指导教师签名指导教师签名 年年 月月 日日 毕业论文（设计）复评教师评语及成绩毕业论文（设计）复评教师评语及成绩 成绩成绩 复评

2、教师签名复评教师签名 年年 月月 日日 毕业论文（设计）答辩评语及成绩毕业论文（设计）答辩评语及成绩 成绩成绩 答辩委员会主席签名答辩委员会主席签名 年年 月月 日日 毕业论文（设计）总成绩（五级记分制）毕业论文（设计）总成绩（五级记分制） 院（系）负责人签名院（系）负责人签名 年年 月月 日日 title: some optimization problem research in life major: information and computing science applicant: jia-neng you supervisor: xiao-long chai 内容摘要内容摘要

3、数学与我们日常生活密切相关，日常生活中的许多问题来源于数学 思想的应用。在掌握一定的数学基础的前提下，结合日常当中可能出现 的数学问题，通过适当的规划安排，运用数学原理求解出行之有效的最 优化方案。 本文的主要研究方向是通过对日常生活中经常涉及到的若干最优化 问题进行归纳总结，分析其所涉及的数学原理并将其推广应用到其他生 活案例当中去。本文的主要贡献是通过对运输成本问题和效益分配问题 的最优化分析，详细地介绍了表上作业法和 shapley 值法的求解过程， 指出了模型存在的缺陷和不足，并对模型进行修改以及推广应用。 关键词关键词: : 最优化；表上作业法；shapley 值；推广应用 abst

4、ract mathematics 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 arise in day-to-day which, through appropriate planning arrangements, th

5、e 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 promote the application to which the case of other life to go.the main c

6、ontribution 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 that the model defects and deficiencies,and to modify the model and applic

7、ation. keywords: optimization; tabular method; shapley method; application 目目 录录 1 1 研究的意义研究的意义与与目的目的 .1 1 2 2 研究现状分析研究现状分析 .1 1 2.1 研究的方法 .1 2.2 研究现状 .2 3 3 本文研究方向本文研究方向 .2 2 3.1 运输调配方向 .3 3.2 效益分配方向.3 4 4 运输调配问题最优化研究运输调配问题最优化研究 .3 3 4.1 初始方案的给定 .4 4.2 最优性检验与方案的调整 .6 4.3 表上作业法的总结 .8 4.4 表上作业法的改进及其推

8、广应用 .9 5 5 效益分配问题最优化研究效益分配问题最优化研究 .1212 5.1 n 人合作对策和 shapley 值.12 5.2 shapley 值的推广应用.14 5.3 shapley 值法存在的缺陷.16 5.4 其他求解方法.17 5.4.1 协商解 .17 5.4.2 raiffa 解 .18 6 6 传统模型的改进设想传统模型的改进设想 .1818 6.1 最小元素法的改进设想 .18 6.2 效益分配的改进设想 .20 7 7 总结与展望总结与展望 .2020 7.1 本文的主要贡献 .20 7.2 本文主要的改进方案 .21 7.3 研究展望 .21 参考文献参考文献

9、 .2222 致谢致谢 .2323 生活中的一些最优化问题研究生活中的一些最优化问题研究 1 1 研究的意义与目的研究的意义与目的 最优化问题，是指在日常生活中通过适当的规划安排，使得完成一件事所 用的费用最少、路线最短、时间最短、产值最高、容积最大等的效率与分配问 题，也就是要在各种方案中，寻求一个最节约、合理的方案。解决这类问题要 注意两点: 一是明确问题，即通过问题描述中已知的数量关系把生活问题转化 为单纯的数学问题，我们称之为数学建模的过程；二是建模后的求解问题，即 用相关的数学知识求解出最优的处理方案1。 数学与我们日常生活密切相关，日常生活中的许多问题来源于数学思想的 应用。在掌握

10、一定的数学基础的前提下，结合日常生活当中可能出现的数学问 题，通过适当的规划安排，运用数学原理求解出行之有效的最优化方案。本文 通过对日常生活中经常涉及到的若干最优化问题进行归纳总结，分析其所涉及 的数学原理并将其推广应用到其他生活案例当中去2。因而，引导学生学习应 用数学，从众多的解决方案中寻求到最优化的方案，使他们感受到数学的应用 价值，是一种能够调动高校学生积极学习数学的办法3。 2 2 研究现状分析研究现状分析 2.1 研究的方法 不同类型的最优化问题可以有不同的最优化方法，即使同一类型的问题也 可有多种最优化方法。反之，某些最优化方法可适用于不同类型的模型。目前， 最优化问题的求解方

11、法大致可分成解析法、直接法、数值计算法。解析法： 这种方法只适用于目标函数和约束条件有明显的解析表达式的情况。求解方法 是：先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等 式，一般是用求导数的方法或变分法求出必要条件，通过必要条件将问题简化， 因此也称间接法。直接法：当目标函数较为复杂或者不能用变量显函数描述 时，无法用解析法求必要条件。此时可采用直接搜索的方法经过若干次迭代搜 索到最优点。这种方法常常根据经验或通过试验得到所需结果。对于一维搜索 (单变量极值问题)，主要用消去法或多项式插值法；对于多维搜索问题(多变量 极值问题)主要应用爬山法。数值计算法：这种方法也是一种直

12、接法。它以梯 度法为基础，所以是一种解析与数值计算相结合的方法4。 2.2 研究现状 最优化一般可以分为最优设计、最优计划、最优管理和最优控制等四个方 面。最优设计:世界各国工程技术界,尤其是飞机、造船、机械、建筑等部门都 已广泛应用最优化方法于设计中，从各种设计参数的优选到最佳结构形状的选 取等，结合有限元方法已使许多设计优化问题得到解决5。最优计划:现代国民 经济或部门经济的计划，直至企业的发展规划和年度生产计划，尤其是农业规 划、种植计划、能源规划和其他资源、环境和生态规划的制订,都已开始应用最 优化方法。一个重要的发展趋势是帮助领导部门进行各种优化决策。最优管理： 一般在日常生产计划的

13、制订、调度和运行中都可应用最优化方法。随着管理信 息系统和决策支持系统的建立和使用，使最优管理得到迅速的发展。最优控制： 主要用于对各种控制系统的优化。例如，导弹系统的最优控制，能保证用最少 燃料完成飞行任务,用最短时间达到目标;再如飞机、船舶、电力系统等的最优 控制，化工、冶金等工厂的最佳工况的控制。计算机接口装置不断完善和优化 方法的进一步发展，还为计算机在线生产控制创造了有利条件。最优控制的对 象也将从对机械、电气、化工等硬系统的控制转向对生态、环境以至社会经济 系统的控制6。 3 3 本文研究方向本文研究方向 虽然现今最优化问题研究渐趋成熟，也应用到很多不同的领域，但对日常 生活存在的

14、最优化问题的研究仍存在一定的空缺。本文将通过对日常生活中经 常涉及到的一些最优化问题进行归纳总结，分析其所涉及的数学原理并将其推 广应用到其他生活案例当中去。因而，如何运用最优化原理解决生活中存在的 实际问题将是本文研究的主要方向，主要针对生活中的运输成本问题和效益公 平分配问题进行研究分析7。 3.1 运输调配方向 运输成本问题涉及了很多生活领域，生产运输、物流运输、仓库调配等等， 但其主要的数学模型都是相似的，因此掌握这种问题的解决方法有着重要的作 用。文中通过对生产运输问题进行分析，运用表上作业法列出详细的求解过程， 并进行推广应用8。 3.2 效益分配方向 在日常的社会生活中，若干实体

15、相互合作结成联盟或集团，常能比个体单 独行动获得更多的经济利益或社会效益。但是效益公平分配问题经常成为他们 合作的阻碍，如何合理地分配这些效益是促进合作的前提，也能给合作带来更 多的效益。文中通过对合作效益分配问题进行分析研究，运用 shapley 法列出 详细的求解过程，并对模型进行修改推广。 4 4 运输调配问题最优化研究运输调配问题最优化研究 运输问题是社会经济生活和军事活动中经常出现的优化问题，是特殊的线 性规划问题，它是早期的线性网络最优化的一个例子。最早研究这类问题的 hitchcock以及后来的koopmans独立地提出运输问题并详细地对该问题加以讨论； 同时kahtopobny

16、也围绕着运输问题作了大量的研究，因此运输问题又称为 hitchcock问题或kantorvich问题。运输问题不仅代表了物资合理调运、车辆合理 调度等问题，有些其他类型的问题经过适当变换后也可以归结为运输问题，如 指派问题、最短路问题、最小费用流问题可转化为运输问题或转运问题9。 运输问题在运筹学教学过程中占有重要地位，并且得到了众多学者的广泛 关注，取得了许多重要的研究成果。但就在常用的运筹学教材中仅仅介绍运输 问题的基础知识，对于运输问题的前沿发展涉及甚少，这远远不能反映当前对 运输问题的深入研究。为此，在介绍运输问题的基本理论和方法的基础上，运 用表上作业法对类似问题进行推广运用10。

17、【例 1】某食品加工公司经销的主要产品之一是酸奶。该公司下面设有三个加 工厂，每天酸奶的生产量分别为：，。该公司把这些酸 1 7at 2 4at 3 9at 奶分别运往四个地区的门市部进行销售，各地区每天的销售量分别为： ，。已知从每个加工厂到对应的各销售门市部 1 3bt 2 6bt 3 5bt 4 6bt 每吨酸奶的运价如表 4-1 所示，问该食品公司该如何调运，在满足各门市部销 售需要的前提下，使得总运费支出达到最少。 表 4-1 1 b 2 b 3 b 4 b 1 a 2 a 3 a 3 11 3 10 1 9 2 8 7 4 10 5 以下运用表上作业法求解运输问题，首先给出一个初始

18、方案，一般来讲，这个 方案不会是最好的。因此需要给出一个判别准则，并对初始方案通过不断地调 整、改进，一直到求得最优方案为止10。 先列出这个问题的的产销平衡表和单位运价表，见表 4-2 和表 4-3 表 4-2 产销平衡表 1 b 2 b 3 b 4 b产量 1 a 2 a 3 a 7 4 9 销量3 6 5 6 表 4-3 单位运价表 1 b 2 b 3 b 4 b 1 a 2 a 3 a 3 11 3 10 1 9 2 8 7 4 10 5 4.1 初始方案的给定 给定初始方案的方法有很多，一般希望方法简便易行，尽量能给出较好的 方案，减少迭代的次数，这里采用最小元素法。最小元素法的基本

19、思想是就近 供应，即从单位运价表中最小的运价开始确定供销关系，依此类推，一直到给 出全部方案为止10。 门市部 加工厂 销地 产地 销地 产地 第一步：从表 4-3 的单位运价表中找出最小运价为 1（如果有两个最小运价时 任选其一） ，即从生产的酸奶首先供应需求。由于每天生产 4t，每天 2 a 1 b 2 a 1 b 需要 3t,即每天生产的除了要满足全部需求之外，还剩下 1t。因此在表 4- 2 a 1 b 2 中（，）的交叉格中填上数字 3，表示调运 3t 酸奶给，再在表 4-3 2 a 1 b 2 a 1 b 中将所在的这一列运价划去，表示已经满足的需求，无需继续调运给它。 1 b 1

20、 b 第一步得到的结果如表 4-4 和表 4-5 所示。 表 4-4 1 b 2 b 3 b 4 b产量 1 a 2 a 3 a 3 7 4 9 销量3 6 5 6 表 4-5 1 b 2 b 3 b 4 b 1 a 2 a 3 a 3 11 3 10 1 9 2 8 7 4 10 5 第二步：从表 4-5 中未划去的元素之中找出最小的运价为 2，即每天剩余的 2 a 酸奶要供应给。每天需要 5t，每天只能供应 1t，因此在表 4-4（， 3 b 3 b 2 a 2 a ）交叉处填写 1，划去表 4-5 所在的这一行运价，表示生产的酸奶已 3 b 2 a 2 a 分配完，其结果见表 4-6 和

21、表 4-7. 表 4-6 1 b 2 b 3 b 4 b产量 1 a 2 a 3 a 3 1 7 4 9 销量3 6 5 6 销地 产地 销地 产地 销地 产地 表 4-7 1 b 2 b 3 b 4 b 1 a 2 a 3 a 3 11 3 10 1 9 2 8 7 4 10 5 第三步：同理再从表 4-7 中未划去的元素之中找出最小的元素为 3，即生产 1 a 的酸奶应优先满足需求。每天生产 7t，还缺 4t。因此在表中 3 b 1 a 3 b （，）交叉格内填上 4，由于的需求此时已经满足，在表 4-7 中划去 1 a 3 b 3 b 所在列的元素。 3 b 这样一步一步地进行下去，直到

22、单位运价表上所有元素都被划去为止，这时在 产销平衡表上可以得到一个调动方案（见表 4-8） ，这个调动方案总的运费为 86 元。 表 4-8 1 b 2 b 3 b 4 b产量 1 a 2 a 3 a 4 3 3 1 6 3 7 4 9 销量3 6 5 6 4.2 最优性检验与方案的调整 最小元素法给出的是运输问题的一个基可行解，需要通过最优性检验判别 该解的目标函数值是否达到最优，当为否时，应进行调整得到优化。检验的方 法常用的有闭回路法和位势法，这里采用闭回路法。运输问题中的闭回路是指 调运方案中的一个空格和几个有数字格的水平和垂直之间的连线包围成的封闭 回路11。 构建闭回路是为了计算解

23、中各非基变量（对应空格）的检验数，方法是令 某一非基变量取值为 1，通过变动原基变量的值找出一个的可行解，将其与原 来的基可行解进行比较。在表 4-8 中给出了一个调运方案中， （，）是空 1 a 1 b 销地 产地 销地 产地 1 格，即为非基变量。令，相应地为了找到新的可行解，原有基变量中 11 x 11 1x 需减 1，加 1，减 1，见表 4-9。表中由（，） ， （，） ， 13 x 23 x 21 x 1 a 1 b 1 a 3 b （，） ， （，）4 个格的水平和垂直连线围成的闭回路，该闭回路除（ 2 a 3 b 2 a 1 b ，）为空格之外， （，） ， （，） ， （，）

24、均有数字的格。将 1 a 1 b 1 a 3 b 2 a 3 b 2 a 1 b 新可行解与原来解费用比较：从 0 变成 1，运费加 3 元，减 1，运费减少 11 x 13 x 3 元，加 1，运费加 2 元，减 1，运费减少 1 元，由此新可行解较原来解 23 x 21 x 运费增加了（3-3+2-1）=1 元，称为检验数，将其填入检验数表中（表 4-10） 的（，）相应的交叉格位置。类似地（，）为空格，可通过该空格找 1 a 1 b 3 a 1 b 出一条其余顶点都有数字格的闭回路，求得其相应的检验数为（7-1+2-3+10- 5）=10，将其填入检验数表 4-10 的（，）的交叉格位置

25、，因为任意的非 3 a 1 b 基向量均可表示为基向量的唯一线性组合，因此通过任一空格可以找到，并且 只能找到唯一的闭回路，并计算得到对应表 4-8 中解全部非基变量的检验数12。 表 4-9 1 b 2 b 3 b 4 b产量 1 a （+1）4（-1） 37 2 a3（-3） 1（+1） 4 3 a639 销量3656 表 4-10 检验数表 1 b 2 b 3 b 4 b 1 a 2 a 3 a 12 1 -1 10 12 销地 产地 33 2 销地 产地 如果检验数表中所有的数字都大于等于零，表明对调运方案作出任何改变 都不会导致运费减少，即给定的方案为最优方案。但在表 4-10 中，

26、 （,） 2 a 4 b 格的检验数是负的，说明方案仍需进一步调整。改进的方法是从检验数为负数 的格出发（当存在两个以上负数检验数时，从绝对值最大的负检验数格出发） ， 这里是从（,）格出发，作一条除该空格以外其余顶点都为有数字格而组 2 a 4 b 成的闭回路。在这条闭回路上，按照以上讲的方法对运量作最大限度的调整。 从表 4-9 看出，为了把生产的酸奶调运给，就要相应减少调运给的 2 a 4 b 2 a 3 b 酸奶和调运给的酸奶，才能得到新的平衡。这两个格内，较小运量为 1， 1 a 4 b 因此最多只能调运 1t 酸奶给。由此得到一个新的调运方案（见表 4-11） 。 2 a 4 b

27、这个新方案的运费为 85 元。 表 4-11 1 b 2 b 3 b 4 b 产量 1 a 2 a 3 a 5 2 3 1 6 3 7 4 9 销量3 6 5 6 表 4-11 给出的调运方案是否达到最优，仍需对这个方案的每一个空格求出 其检验数（见表 4-12） 。由于检验数表中所有的检验数大于等于零，因此肯定 表 4-11 给出的方案是最优方案。 表 4-12 检验数表 1 b 2 b 3 b 4 b 1 a 2 a 3 a 0 2 2 1 9 12 4. 3 表上作业法的总结 运输问题成本最优化解决方法主要有三个步骤，可以用以下流程图总结出 来，见图 4-1。 销地 产地 销地 产地 否

28、 分析实际问题列出产销 平衡表及单位运价表 确定初始调运方案 求检验数 所有检验数0 找出绝对值最大的负检验数用 闭回路调整，得出新的调运方 案 得到最优方案 算出总的运价 是 图 4-1 表上作业法计算步骤框图 4.4 表上作业法的改进及其推广应用 前面所讲的表上作业法的计算理论，都是以产销平衡为前提的，即 。但实际问题中大部分产销是不平衡的。为了更好地应用表上作业 11 mn ij ij ab 法，就需要把产销不平衡的问题转化成产销平衡的问题13。 当产大于销时，运输问题的数学模型可写为 11 mn ij ij ab () (4.1a) 11 min mn ijij ij zc x s.t

29、. 1 1 (1,.,)(4.1 ) (1,., )(4.1 ) 0(4.1 ) n iji j m ijj i ij xa imb xbjnc xd 如果总的产量大于销量，可以考虑多余的物资在那一个产地库存的。设是 ,1i n x 产地的库存量，于是可以得到 i a (4.2) 1 ,1 11 nn iji nij jj xxxa (1,.,)im (4.3) 1 m ijj i xb (1,., )jn ,11 111 mmn i nijn iij xabb 令 (4.4) ijij cc (1,.,;1,., )im jn 0 ij c (1,.,;1,.,1)im jn 将(4.2)-

30、(4.4)分别代入或替换(4.1a)-(4.1d)，得到 (4.5a) 1 ,1 1111111 min mnmnmmn ijijijiji niijij ijijiij zc xc xcxcx s.t 1 1 1 (1,.,)(4.5 ) (1,., )(4.5 ) 0(4.5 ) n ij j m ijj i ij xa imb xbjnc xd 由于（4.5）模型中，是一个产销平衡的运输问题。因 1 1 111 mnn iini ijj abbb 此当产量大于销量时，只需增加一个假想的销地 j=n+1(实际上库存销地的单位 运价，就可以转化成为一个产销平衡的运输问题。类似地，当销量大于

31、,1 0 i n c 产量时，可以在产销平衡中增加一个假想的产地，该地产量为1im ，在单位运价表中令从该假想产地到各销地的运价，同 11 () nm ji ji ba 1, 0 mj c 样可以转化成为一个产销平衡的运输问题。 【例 2】设有三个产地生产某种物资，三个产地的产量分别为 123 ,a a a 7t、5t、7t，四个销地需要该种物资，销量分别为 1234 ,b b b b 2t、3t、4t、6t，又知各产销地之间的单位运价见表 4-13，试解出总运费最少 的调动方案。 表 4-13 单位运价表 1 b 2 b 3 b 4 b 1 a 2 a 3 a 2 11 3 4 10 3 5

32、 9 7 8 1 2 【解】产地总产量为 19t，销地总销量为 15t，因此这是产销不平衡的运输问题。 可按照上述方法转化成为产销平衡的运输问题，转化之后其产销平衡表和单位 运价表分别见表 4-14、见表 4-15. 表 4-14 产销平衡表 库存 1 b 2 b 3 b 4 b产量 1 a 2 a 3 a 7 5 7 销量2 3 4 6 4 表 4-15 单位运价表 库存 1 b 2 b 3 b 4 b 1 a 2 a 3 a 2 11 4 4 0 10 3 9 9 0 7 8 2 2 0 销地 产地 销地 产地 销地 产地 对表 4-14、表 4-15 可以用表上作业法计算求出最优方案如表

33、 4-16 表 4-16 最优方案 库存 1 b 2 b 3 b 4 b 产量 1 a 2 a 3 a 2 3 2 3 2 4 3 7 5 7 销量2 3 4 6 4 5 5 效益分配问题最优化研究效益分配问题最优化研究 在日常的社会生活中若干实体（如个人、公司、协会等）相互合作结成联 盟或集团，常能比个体单独行动获得更多的经济利益或社会效益。但是效益公 平分配问题经常成为他们合作的阻碍，如何合理地分配这些效益是促进合作的 前提，也能给合作带来更多的效益14。 【例 3】设有甲乙丙三人经商。若单独经营，每人仅能获利 1 万元；甲乙合作 可获利 7 万元；甲丙合作可获利 5 万元；乙丙合作可获利

34、 4 万元；三人合作则 可获利 11 万元。问三人合作时怎么合理地分配 11 万元的收入。 【解】设甲乙丙三人各得万元，从题目中给定的条件我们可列出满足条 123 ,x x x 件的一组方程 123 11xxx 123121323 ,1,7,5,4x x xxxxxxx 根据上述这两组方程可求出许多组满足条件的解组，如 等 123 ()(5,3,3),(4,4,3),(4,3.5,3.5)xxx 这种求解的方案最为普遍，但仍存在一定的局限性，当条件不够多的时无法求 出最优的解组。以下将介绍一种其他的方法求解这类问题。 5.1 n 人合作对策和 shapley 值 n 个人从事一项经济活动，对于

35、他们之中的若干人组合的每一种合作（单 人也视为一种合作） ，都可以得到一定的效益，仅当人们之间的利益是非对抗性 时，合作中人数的增加不会引起其效益的减少。这样全体 n 个人的合作将带来 销地 产地 更大的效益。n 个人的集合以及各种合作的效益就构成 n 人合作对策，shapley 值是分配这个效益的一种方案15。定义如下： 设集合，如果对于 i 的任一子集 s 都对应着一个实值函数 v(s)，1,2,.,in 满足 (5.1)()0v (5.2) 121212 ()( )(),v ssv sv sss 称为n 人合作对策，v 为对策的特函数。, i v 在上面所述的经济活动中，i 定义为 n

36、人集合，s 为 n 人集合中的任一种合 作，v(s)为合作中 s 的效益。 用表示 i 的成员 i 从合作的最大效益 v(i)中应得到的一份收入。 i x 叫做合作对策的分配，满足 12 ,., n xx xx 1 ( ) n i i xv i ，( ) i xv i1,2,.,in shapley 值由特征函数 v 确定，记作。对于任意的子 12 ( )( ),( ),.,( ) n vvvv 集 s，记，即 s 中各成员的分配。对一切，满足的 x( ) i i s x sx si( )( )x sv s 组合的集合称的核心。当核心存在时，即所有的 s 的分配都小于 s 的效益。, i v

37、可以将 shapley 值作为一种特定的分配，即。 1( )i vx shapley 值 12 ( )( ),( ),.,( ) n vvvv ， （5.3）( )(| |)( )( ) i i ss vw sv sv s i 1,2,.,in （5.4） (| |)(| | 1)! (| |) ! nss w s n 其中是i中包含i的所有子集，|s|是子集 s 中的元素数目（人数） ，w(|s|)是 i s 加权因子，si 表示 s 去掉 i 后的集合。 接下来利用这组公式计算例 3 给出的三人经商问题的分配，以此来解释公式的 用法和意义。 甲乙丙三人记为，经商获利的定义为 i 上的特征函

38、数，即1,2,3i ()0, (1)(2)(3)1, (1,2)7, (1,3)5, (2,3)4vvvvvvv 。容易验证 v 满足(5.1)和(5.2)。为计算首先找出 i 的所有子集( )10v i 1( ) v ，然后 s 跑遍，将计算结果记入表 5-1.最后将表中末行 1: 1 , 1,2 , 1,3 , si 1 s 相加得到。 1( ) 4v 元 表 5-1 三人经商中甲的分配的计算 1( ) v s1 1,2 1,3 i v(s)1 7 5 10 v(s1)0 1 1 4 v(s)-v(s1)1 6 4 6 |s|1 2 2 3 w(|s|)1/3 1/6 1/6 1/3 w(

39、|s|) v(s)-v(s1)1/3 1 2/3 2 同样按照 shapley 值方法可以计算出，。所以， 2( ) 3.5v万元 3( ) 2.5v万元 甲乙丙三人合作合理的分配分别为 4 万元、3.5 万元、2.5 万元。 5.2 shapley 值的推广应用 【例 4】设沿河有三城镇 1，2，和 3，地理位置如图 2 所示。污水需要处理后 才能排入河中。三个城镇既可以单独建立污水处理厂，也可以联合建厂，用管 道将污水集中进行处理（污水由河流上游的城镇向下游城镇输送） 。用 q 表示污 水量（t/s） ，用 l 表示管道长度（km） ，按照经验公式，建立处理厂的费用为 ，铺设管道费用为已知

40、三城镇污水量为 0.712 1 73pq千元 0.51 2 0.66pql 千元 的数值如图 5-1 所示。试从节约总投资的角度为三城镇制 123 5,3,5,qqql 定最优的污水处理方案。如果联合建厂，各城镇如何分担费用。 图 5-1 三城镇地理位置示意图 【解】三城镇污水处理共有以下 5 种方案，以下计算出投资费用以作比较。 （1） 分别建厂。其投资分别 为： 0.712 (1)73 5230,(2)160,(3)230ccca 总投资 1 (1)(2)(3)620dccc （2）1，2 合作，在城 2 建厂。投资为： 0.7120.51 (1,2)73 (53)0.66 520350c

41、 总投资 2 (1,2)(3)580dcc （3）2，3 合作，在城 3 建厂。投资为： 0.7120.51 (2,3)73 (53)0.66 338365c 总投资 3 (1)(2,3)595dcc （4）1，3 合作，在城 3 建厂。投资为： 0.7120.51 (1,3)73 (55)0.66 558463c 这个费用超过 1，3 分别建厂的费用。合作没有效益，不可能(1)(3)460cc 实现。 （5）三城合作，在城 3 建厂。总投资为： 0.7120.510.51 5 (1,2,3)73 (535)0.66 5200.66 (53)38556dc 比较结果千元最小，所以应选择联合建厂

42、方案。接下来的问题是如何 5 556d 分担费用。 5 d 总费用中有 3 部分： 5 d 联合建厂费为； 0.712 1 73 (535)453d 城 1 至 2 的管道费为； 0.51 2 0.66 (53)2030d 城 2 至 3 的管道费为. 0.51 3 0.66 (53)3873d 城 3 提出，由三城按污水量比例 5:3:5 分担，是为城 1，2 铺设 1 d 2 d 3 d 的管道费，应当由他们担负；城 2 同意，并提出由城 1，2 按污水量之比 3 d 5：3 分担，则应当由城 1 自己担负；城 1 提不出反对意见，按上述办法各城 2 d 应当分担的费用： 123 20km

43、 38km 河流 1 5 3174 13 d 城分担费用为 13 53 2132 138 dd城分担费用为 132 53 1250 138 ddd城分担费用为 结果表明城 2，3 分担的费用均比单独建厂费用 c(2)，c（3）小，而城 1 分的费用却比 c(1)大。显然，城 1 不能同意这种分担总费用的办法。 为促成三城联合建厂以节约总投资，应当寻求合理分担总费用的方案。三 城的合作节约了投资，产生了效益，是一个 n 人合作对策问题，可以运用 shapley 值法合理地分配这个效益。 把分担费用转化成分配效益，就不会出现城 1 联合建厂分担的费用反比单 独建厂费用高的情况了。将三城分别记为 i

44、=(1，2，3)，联合建厂比单独建厂 节约的投资定义为特征函数。于是有 ()0, (1)(2)(3)0vvvv (1,2)(1)(2)(1,2)230 16035040vccc (2,3)(2)(3)(2,3)16023036525,vccc (1,3)0v ( )(1)(2)(3)(1,2,3)230 16023055664v icccc 三城联合建厂的总效益为 64 千元。用 shapley 值作为这个效益的分配标准， 城 1 应分得的份额的计算结果列入表 5-1 中，得到。类似 1( ) v 1( ) 19.7v千元 地算得。不难验证，。 23 ( )32.1( )12.2vv， 123

45、 ( )( )( )64( )vvvv i 表 5-1 污水处理问题是的计算 2( ) v s 1 1,2 1,3 i v(s) 0 40 0 64 v(s1) 0 0 0 25 v(s)-v(s1) 0 40 0 39 |s| 1 2 2 3 w(|s|) 1/3 1/6 1/6 1/3 w(|s|) v(s)-v(s1) 0 6.7 0 13 最后，同理运用 shapley 值法可以算出在联合建厂方案总投资额 556 千元中各 城分担费用为：城 1 是；城 2 是 1 (1)( )230 19.7210.4cv ；城 3 是。 2 (2)( )127.9cv 3 (3)( )217.8cv

46、 5.3 shapley 值法存在的缺陷 shppley 值法以严格的条件为基础，在处理合作对策的分配问题时比较公正 合理等，但是它需要知道所有合作方的获利，即需要定义的所有1,2,.,in 子集（共个）的特征函数，这实际上是很难做到的。如 n 个单位共同合作治2n 理污染，第 i 方单独治理的投资和 n 方共同合作治理的投资 y，这通常是已 i y 知的。为了度量第 i 方在合作中的“贡献” ，还常需要设法知道第 i 方不参加时 其余 n-1 方所需的投资。特征函数应定义为共同合作的获利，即节约的投资， i z 有( )0(1,2,. ),v iin 显然除此之外还有很多无法获取，无法应 1

47、 ( ), ( ) n iji ij i v iyy v i iyz ( )v s 用 shapley 值方法求解。 5.4 其他求解方法 以下仍以例 3 提出的三人经商问题为例，介绍两种其它的解决方法。 【例 4】我们只知道全体合作的获利，记作，及无 i 参加时其他 n-1 方( )v ib 合作的获利，记作试确定各方对全 12 ( )(1,2,., )( ,.,). in v i ib inbb bb，且记 体合作获利的分配，记得在三人经商问题， 12 ( ,.,). n xx xx * 11,(4,5,7),bb 求 123 ( ,).xx x x 5.4.1 协商解16 分配分别按照以

48、下两步进行。先从 n 个 n-1 方合作的获利求出各方分配的下限 ，即求解 12 ( ,.,) n xx xx 11 1 1 . n i i n inn i xxb xxb 得到 1 1 ,1,2,., 1 n iii i xbb in n 再求出按下限分配后全体合作获利的剩余为，它通常是较小的部分，x 1 n i i bx 经过协商将其平均分配，于是最终的分配结果为 11 11 () nn iiiii ii b xxbxbb nnn 剩余，它等价于 1 0 n i i bx 1 1 1 n i i bb n 对三人经商问题，(4,3,1),(5,4,2)xx 5.4.2 raiffa 解 h

49、oward raiffa 提出的解决办法按以下的步骤进行17： （1）按照 n 个 n-1 方合作的获利得到了各方分配的下限，即协商解中的，作x 为分配的前提； （2）当 j 方加入（原来无 j 的）n-1 方合作时，计算获利的增加，即 j 方的边际 效益17，就是最小距离解中的上限； jj xbb （3）按两步分配：首先先由 j 方和无 j 方的 n-1 方平分，然后 n-1 方再等分， j x 即 ,1,2,., , 22(1) jj jii xx xxxin ij n 其中 n-1 方是在的基础上分配的；x （4）j 取 1,2,n，再重复第 3 步，然后求和、平均，得到最终分配为 (5

50、.5) 111 ,1,2,., 22(1) i iij j i xn xxxin nnn 将，代入，(5.5)式可表为xx 1 231 ,1,2,., 2(1) n iii i bn xbbin nnn a1 a2 a3 o b1 b2 b3 b4 对三人经商问题， 2115 (4,3,1),(7,6,4),(4,3,2). 31212 xxx 6 6 传统模型的改进设想传统模型的改进设想 6.1 最小元素法的改进设想 表上作业法是求解运输成本最优化问题的常用而有效的方法，但是表上作 业法求解过程比较复杂，而且如果供求双方数量比较多，检验数的计算和闭回 路的调整更容易出错。因此，如果初始方案的

51、给定能尽可能地趋向最优化，在 运输成本预算比较充裕的情况下可以直接采用初始方案。 初始方案给定的方法最常用的是最小元素法，而最小元素法的物资配送是 满足运输配送的每一次单位运价都最小化，但从整体上考虑，它并不能保证总 运价达到最小，也不能在第一时间满足需求点的一定量的物资需求。因此，本 文将对最小元素法的配送过程进行调整，首先通过对物资配送环节进行改进， 可以在第一时间满足某些需求点的物资需求，然后通过增加一临时节点c（该 点是离需求方较近的一点） ，对所有供应点经过一定阶段配送后的剩余物资进行 重新分配，这样可以使运输总成本得到优化。 图 6-1 传统的最小元素法配送网络 a1 a2 a3

52、o b1 b2 b3 b4 c 图 6-2 改进后的最小元素法配送网络 6.2 效益分配的改进设想 在经济生活中，效益分配问题最常见的是合作分配利益问题，前面主要介 绍了 shapley 值效益分配法，但这种方法主要的缺陷是需要知道合作各方在活 动中的“贡献” ，还有总的合作效益，这在实际生活中是难以评估的，因为一个 项目还没开展，其效益很难作出准确的评估。这里将通过合作各方以往的工作 效益制定一定的分配标准，在项目完成之后总效益算出来再进行分配。 设有三个工程师甲乙丙共同合作参与完成一个项目，甲乙丙一个月的工作 效益是分别是、（假设三人一个月的工作时间一样，而且工作效益变 1 x 2 x 3

53、 x 动不大） ，项目完成时三人的工作时间分别为、，总的效益为 ，则三 1 t 2 t 3 ts 人应分配的效益之比为： (6.1) 332211321 :txtxtxsss 明显，由前提条件可以得到： (6.2)ssss 321 由式(6.1)和式(6.2)可以得到甲乙丙三人分配的效益分别为： s txtxtx tx s 332211 11 1 s txtxtx tx s 332211 22 2 s txtxtx tx s 332211 33 3 7 7 总结与展望总结与展望 7.1 本文的主要贡献 数学与我们日常生活密切相关，日常生活中的许多问题来源于数学思想的 应用。在掌握一定的数学基础

54、的前提下，结合日常当中可能出现的数学问题， 通过适当的规划安排，运用数学原理求解出行之有效的最优化方案。通过对日 常生活中经常涉及到的若干最优化问题进行归纳总结，分析其所涉及的数学原 理并将其推广应用到其他生活案例当中去18。 本文的主要贡献有以下几个方面：首先，本文主要选取了生活中较具有代 表性的运输成本问题和效益分配问题进行最优化研究，分别详细地介绍了表上 作业法和 shapley 值法的求解过程。然后，根据这两种求解方法的局限性和普 遍性进行分析，指出了这两种模型存在的缺陷和不足，最后，针对模型存在的 缺陷分别提出了相应的改进方法，并将其推广应用到其他不同的领域19。 7.2 本文主要的

55、改进方案 运用表上作业法解决运输成本问题存在着一定的局限性，主要应用于产销 平衡的运输问题，但实际问题中产销往往是不平衡的。为了应用表上作业法计 算，就需要把产销不平衡的问题化成产销平衡的问题。当总的产量大于销量时， 可以考虑将多余的物资在那一个产地就地库存，此时需要在产销平衡表上增加 一个假想的销地，通过这样的修改，原先不平衡的运输问题就转化成为产销平 衡问题了。当总的销量大于产量时，同理可以在产销平衡表中增加一个假想的 产地，同时在单位运价表上设定该假想产地到各销地的运价为零，同样转化成 为产销平衡的运输问题。通过这样的转化问题就能顺利解决了20。 shapley 值方法严格的公理为基础，在处理合作对策问题时具有公平、合理 等特点，但是它需要知道所有合作的获利，合作方越多，需要的信息就越大， 在实际上这些信息往往难以完全提供。协商解法计算相对简单，且便于理解， 但通常偏袒强者，可用于各方实力相差不大的情况。raiffa 解法考虑了分配的 上下限，又吸取了 shapley 的思想，在一定的程序上保护弱者。因此，只要根 据问题提供的条件和要求，运用相应的