满意度函数的动态建立及灵敏度分析毕业论文

1、西 南 交 通 大 学 本科毕业设计（论文） 满意度函数的动态建立及灵敏度分析 年 级:2004 级 学 号:20043561 姓 名: 专 业:信息与计算科学 指导老师: 院 系 数学系 专 业 信息与计算科学 年 级 2004 级 姓 名 吴婷婷 题 目 满意度函数的动态建立及灵敏度分析 指导教师 马淑霞 评 语 指导教师 (签章) 评 阅 人 评 语 评 阅 人 (签章) 成 绩 答辩委员会主任 (签章) 年 月 日 毕业设计（论文）任务书毕业设计（论文）任务书 班 级 计算一班 学生姓名 吴婷婷 学 号 20043561 发题日期：2008 年 3 月 10 日 完成日期： 5 月 3

2、0 日 题 目 满意度函数的动态建立及灵敏度分析 1、本论文的目的、意义: 本文的目的在于：建立一个普遍适用的满意度函数，对于建立的满意度函数进 行灵敏度分析。 本文的意义在于：满意度原理作为比最优化更一般的理论，可作为独立的理论 出现，也可以引入到优化等理论中发挥作用。如果作为一套独立的理论，满意理论 对应的问题空间就是满意问题，满意问题覆盖了很多类问题，满意问题的求解思路 可为这些问题的求解提供一定的指导。同时，满意度原理更加适合于作为一种准则 渗透到其他的一些学科领域和问题求解过程中，为人们解决问题提供一种新的思路。 2、学生应完成的任务 (1)了解“满意”原理的背景知识及发展现状 (2

3、)掌握最优化基本理论和相关内容；熟悉满意度原理及其相关基本知识； (3)查找并提出满意度函数的动态建立方法； (4)对于建立的满意度函数进行灵敏度分析； (5)查找相应的资料,完成论文。 3、论文各部分内容及时间分配：(共 17 周) 第一部分 查阅资料及相关文献 ,进行整理, (2 周) 第二部分 学习最优化理论和满意度原理的相关知识. (3 周) 第三部分 提出具有可行性的思想框架 (5 周) 第四部分 构建一般性满意函数并建立动态满意度函数 (3 周) 第五部分 修改论文和制作答辩时文档 (2 周) 评阅及答辩 (2 周) 备 注 指导教师： 年 月 日 审 批 人： _ 年 月 日 摘

4、 要 随着科学技术的不断发展以及人们对自然科学和对自身处理问题过程本质的认 识的不断加深，人们发现传统的优化理论和优化技术在求解许多问题上困难重重， 于是人们开始把当今其他科技领域的研究成果引入到优化理论和优化算法中，自从 h.a.simon 提出用满意方案代替最优方案的思想，提出了令人满意准则后，人们纷 纷追求满意，而不是最优，从而开辟了一个崭新的知识体系。虽然满意问题无处不 在，但由于缺乏坚实的数学理论基础，其形式化和分析工作都非常困难。满意方法 更加趋向于启发式方法，而不是传统的数学推导。 本文的目的在于系统的研究满意问题中满意度函数的建立，以求找到一个普遍 适用的满意度函数。文章从几种

5、满意度的定义开始，提出了满意度函数的四种建立 方法。在此基础上引出满意度函数的动态建立方法。同时，灵敏度分析的概念也涉 及在文章的最后，为满意度函数的建立提供了定性分析。 满意度原理具有普遍性、模糊性、智能性以及相对性等特点，更能反映人类的 人性化本质。满意度原理不仅包容了最优化原理，而且也适用于推理机、知识获取、 人工智能、模式识别、管理工程及可靠性等领域。而满意度函数的设计在满意优化 中更是占有重要地位。本文针对问题的不同情况,提出几种满意度函数的建立方法。 对于满意优化在现实问题中的应用以及满意度原理的进一步推广具有一定的推动作 用。 关键词：满意度，满意度函数，灵敏度分析 abstra

6、ct with the development of the science ，we understand the natural science and the problems of essence that we deal with., we found that there were a lot of problems in optimization theory and technology in traditional ways. naturally, people introduced many useful achievements to this field. since h

7、.a.simon, who proposed to replace optimization plan with satisfactory one., after simons theory, people turned to satisfactory degree, which made another brand-new knowledge system. though satisfactory problems are common to see, formalization and analysis of it are difficult because of lack of math

8、ematical foundation. satisfactory method is close to inspiring method rather than traditional mathematical reasoning. the purpose of this paper is to build up satisfactory functions in satisfactory problems systematically in order to find a proper satisfactory function which will be effective at any

9、 time.from the beginning of several ways to define satisfactory degree,the paper bring up the forms of satisfactory functions and ways to build up them. on the basis of this,it leads to dynamic conditions.moreover, sensitivity analysis is including in the final article which for provides a qualitati

10、ve analys for the establishment of satisfaction function. satisfactory theory is famous for its universality, fuzziness ,intelligence and relativity, which reflect humanity. the satisfactory theory includes theory of optimizaiton, inference engine , intellectual captune,artificial intelligence, patt

11、ern recognition， management engineering and security. the design of satisfactory functions plays an important part in satisfactory optimization. this paper proposed several ways to define satisfactory functions under different occasions. it has done some work in popularizaiton of satisfactory optimi

12、zation in our real life and satisfactory degree theory. keywords: satisfactory degree, the design of the satis-factory-degree, sensitivity analysis 目 录 第一章 绪论.1 1.1 令人满意准则的提出.1 1.2 满意度原理的发展阶段9.1 1.3 满意度原理研究的发展趋势.3 1.4 本文研究的主要内容和意义.3 第二章 基本概念.5 2.1最优化问题.5 2.2 满意标准.5 2.3满意度.5 2.3.1 基于模糊数学的定义.6 2.3.2 基

13、于线性取值的满意度的定义.6 2.3.3 基于模糊神经计算的定义.7 2.3.4 基于遗传算法的满意度的定义.7 2.3.5 满意度的性质.8 2.3.6 满意度函数的表示.8 2.4 灵敏度分析.8 2.4.1 灵敏度分析的概念.8 2.4.2 灵敏度分析的应用价值.9 第三章 满意度函数的建立及动态建立.10 3.1 满意度函数的表示9.10 3.1.1 单调减函数(戒上型).10 3.1.2 单调增函数(戒下型).12 3.2 建立满意度函数的基本准则.13 3.3 满意度函数的建立方法9.14 3.3.1 基于目标函数的直接法.14 3.3.2 利用模糊逻辑构造满意度函数.14 3.3

14、.3 利用神经网络确定满意度函数.15 3.3.4 按照解的搜索代价建立满意度函数.17 3.4 满意度函数的动态建立.18 第四章 灵敏度分析.20 4.1 灵敏度分析一般研究的问题2.20 4.1.1 改变系数向量c.20 4.1.2 改变右端向量b.21 4.1.3 改变约束矩阵a.22 4.1 关于动态满意度函数的灵敏度分析.22 总 结.23 参考文献.24 致 谢.26 附录一：外文翻译原文.27 附录二：译文.39 第一章 绪论 1.1 令人满意准则的提出 人们处理实际问题时，衡量处理问题质量的依据往往是满意性而不是最优性。 “令人满意准则”是诺贝尔经济学奖获得者 h.a.sim

15、on 在经济组织决策研究中提出 的概念，他在 1947 年发表的管理行为中提出了用满意决策代替最优决策的思想， 然后又把满意解的寻求过程命名为“satisficing”,提出了令人满意准则,从而开辟 了一个崭新的知识体系。满意准则的提出把人们从纯理性思维的研究方式带到了一 个有限理性的状态，为人们解决问题提供了崭新的途径。 人们在处理实际问题时，衡量解的质量依据往往是满意性而不是最优性。 h.a.simon 曾以地里摘玉米的实例进行了说明：在某块地里要找一颗最大的玉米是 很困难的，需要把地里所有的玉米进行测量，再加以比较才能确定。显然此工作量 和玉米地面积成正比，面积越大，工作量越大。但是，如

16、果找的玉米不要求最大， 而是比较大，即按通常的说法，到地里去摘一颗大玉米，问题就简单多了。这时， 工作量和土地面积的大小基本无关。8 1.2 满意度原理的发展阶段9 h.a.simon 提出令人满意准则之后，满意度的概念虽然在决策管理领域中引起 了一定的反响，但对满意度函数在理论上的研究并没有发展出一套系统的理论体系。 随着越来越多满意思想在实际工程问题中的应用，对其理论上的关注日趋明显。 满意度研究的发展大致可以分为三个阶段。 (1) 萌芽阶段(感性阶段) 从令人满意准则这一概念的提出开始，满意度原理即受到了人们的普遍关注， 有限理性、满意度、满意解等概念开始对决策和优化等领域产生影响，但人

17、们主要 停留在满意度原理的价值、意义和对满意度本身概念的理解和接受上，在学术研究 和工程应用领域没有受到足够的重视。 (2) 理论研究阶段 最初对满意理论进行较系统研究的是日本的 m.d.mesarovie 和 t.matsuda 等。 他们在 20 世纪 80 年代对满意决策进行了一些理论研究，从数学角度定性地分析了 满意决策的满意特性、代数特性及分析和分解的方法。1013 mesarovic 研究了一种系统合成和系统控制的满意方法。他试图表示拓扑中的 不确定特性。他将一个容忍函数 t 定义如下: :t ua 这里 u 是一个不确定集合，a 是一个评估函数或值的集合。 m.d.mesarov

18、ic 和 t.matsuda 讨论了协同原则、满意控制和协同操作的选择， 研究了满意控制理论。其中性能函数和容忍函数映射为一个实数的值域集合。在某 不确定(扰乱)范围内，如果它的属性函数小于或等于给定的容忍函数，则一个控制 被认为是满意的。 任平教授借助模糊逻辑定义了满意度、满意解，开始了满意度的形式化表示的 研究。他把满意度思想引入到优化领域并产生了满意优化的概念和理论雏形。 靳蕃教授从模糊神经计算智能系统输出解的一般性评定满意度的需要出发，给 出了满意度的几种表示方式，定义了具体可用的计算公式，对满意度概念的系统化 及其在神经网络等计算智能中的应用方面做出了贡献。 m.a.goodrieh

19、 在博士论文a theory of satisfieing control中对满意控 制进行了系统研究，把满意作为一种关系来处理，通过定义满意关系、过滤器，建 立了一套满意控制理论，并成功地把满意控制理论应用到一些经典的控制中，解决 了经典控制理论无法解决的一些问题。 (3) 应用阶段 和多数理论一样，满意理论在没有完全成熟的情况下，逐渐受到多个领域的关 注，比较典型的就是优化、控制、管理、决策、资源分配、任务调度等。 大多数满意研究是通过修改原理论体系中的部分内容，把满意的思想引入到相 关应用领域中出现的。这方面的研究成果比较多。 1985 年 hopfield 提出一种基于满意准则原理的全

20、互联型神经网络模型，比较 成功地解决了一些大规模组合优化难题。14 靳蕃教授把分区计算后再组合起来求满意度的方法应用到 tsp 的求解中，在较 短的时间内得到了满意度很高的解，提高了求解质量和速度。15 另外，金炜东在列车的操纵优化16，罗刚在 pid 和 mimo 控制17，席裕庚在复 杂工业控制18，马丰宁在遗传算法19，郭耀煌在多目标群决策问题20等中都有满意 度的应用。 1.3 满意度原理研究的发展趋势 满意度原理研究总的发展趋势如下： (l)从概念到系统令人满意准则被注意的时候，也只是从人们实际生活中提炼出 来的一个抽象概念，是人工智能学科对人的活动研究的成果，随着满意度研究的深 入

21、，满意理论逐渐出现了与数学方面相关的研究成果，并有发展成为一种系统科学 的趋势。 (2)从理论到工程应用虽然满意度原理来源于对人类处理问题的一般思维和行为 方式的研究，但当满意度思想提出来之后，人们发现把它应用到和人类活动相关的 具体领域却很困难，因此满意度原理早期的研究偏向理论。经过 20 多年的发展，满 意度原理开始和具体工程相结合，满意优化、满意决策、满意控制、满意知识系统、 满意分配都有具体的应用。 (3)从单学科领域(决策科学领域)到多学科领域 h.a.simon 提出让满意解代替最 优解，是针对决策科学领域的，开始的研究也主要集中在决策领域，后来人们发现 满意度本身不应该局限于决策

22、科学，它应该是一种普遍的、系统的原理，可以适用 于许多与人类活动相关的科学领域，如优化、决策、控制、知识系统、分配等。 1.4 本文研究的主要内容和意义 在人类发展历程中，某种程度上讲，自然智能一直处于一种让科学技术无论如 何都望尘莫及的境界，就是说科学技术无论如何发展都不能超越人类自身和自然界 的智能，而在人类处理问题的过程中，一些科学研究的成果对人类的发展起到了巨 大的推动作用，如最优化理论就是一个例子。但是当人们在经过了许多的研究、计 算、分析之后，却经常发现一些对人类智能来讲简单的问题在科学研究中却复杂化 了，因此人工智能(或称经典人工智能)以及后来发展起来的计算智能，开始研究自 然智

23、能；同时，令人满意准则也在科学研究领域开始产生影响。 本文通过研究满意度的特性，分析满意度函数的建立方法，就满意优化问题展 开讨论，最终得出了满意度函数的动态建立方法。 文章开始对所涉及到的学科和满意度原理的发展方向做了系统的介绍；第二章 基于要讨论的内容给出了基本的概念，比如满意标准的含义，满意度的几种定义方 法等；第三章是满意度函数建立部分。首先介绍了满意度函数的表示形式，并提出 了满意度函数的几种建立方法，章节末尾引出怎样建立动态满意度函数。最后，本 论文针对引出的动态满意度函数中变化的参数进行定性分析，解析其变化时给优化 结构带来的影响。 第二章 基本概念 2.1最优化问题 最优化问题

24、可简单地描述为：在给定条件下求一函数的极值点。 在形式上，最优化问题一般可表示为： (2-1) min, . .0,0 n f xxe sth xg x 表示 x 为 n 维欧氏空间中的一个点或为一个 n 维向量。 n xe 2.2 满意标准 姚新盛在其满意度原理研究的论文中定义了满意标准9。 引用定义 1 满意标准是用来衡量用户对问题的解的满意程度的一个基准体系。 满意标准可以是模糊的，也可以是精确的。满意标准根据具体问题和研究领域 确定。就一般而言，满意标准可以是一个映射关系，它把问题的解映射为用户对解 的满意程度，把客观的一个解集和用户的主观评价结合了起来。一般采用 c 表示满 意标准。

25、 性质 l(主观性)满意标准需要依据用户对具体问题的侧重点不同加以确定。 性质 2(多重性)对同一个问题，可以具有多个满意标准。 例: 可以作为评价学生成绩 c 的一个满意标准。 100,60 0,60 cc g c 是评价学生成绩 c 的另外一个满意标准。 ,90100 ,8090 ,7080 ,6070 ,60 ac bc gcc dc e c 2.3满意度 满意度和满意解一直是满意理论中研究最多、应用最广的概念。先后出现过多 种满意度、满意解的定义，下面介绍几种主要的定义形式。 2.3.1 基于模糊数学的定义 暨南大学的任平教授利用模糊数学的方法对满意度进行了定义8： 考虑论域 u 到目

26、标值集合 v 的一个映射 :f uv u 为全体可能解或可能策略的集合，v 是衡量解或策略的某种标准集。 定义 v 的一个 fuzzy 子集为“满意” ，其隶属函数为： g :0,1 g v 令为 u 的 fuzzy 子集，有 c 引用定义 2 对满足的任一值，称,cg 01 ,mu ucf ug 为 f 在上的-水平的满意解集。其中，分别为，的-水集。 ccg c g 即 , cg cu uuugv vv 引用定义 3 考虑的一 fuzzy 子集，其隶属函数规定为： c m sup,01 m u m u 则称为 f 在上的满意解。这时，就是解 u 的满意度。 m c c u 这个定义反映了满

27、意度具有模糊性这一本质。但似乎局限于隶属度的表 示方式，并没有正确反映满意度的本质内涵。 2.3.22.3.2 基于线性取值的满意度的定义基于线性取值的满意度的定义 基于线性取值的满意度定义较多，比较早的是胡思继教授，他在探讨铁路运输 计划指令性指标按纵向从上到下或从下到上进行分解的方法时，给出了如下的定义 21： 引用定义 4 设为指标数值，与分别为指标的最佳解和最差解，则指 i f h i f s i f 标的满意度为: i f s ii i hs ii ff ff 很明显，这个定义是针对具体环境提出的。对一般应用来说，很多情况下，解 的最佳和最差的先验知识无从得知。所以，这种定义不具有通

28、用性。 2.3.3 基于模糊神经计算的定义 靳蕃教授从模糊神经计算智能系统输出解的一般性评定满意度的需要出发，按 照解的离散和连续性质，实时和非实时要求，给出了几种不同的满意度表示方法15。 引用定义 5 设离散解集为有效解集，对解的某种性能 12 , n xx xx i xx 评价用表示，定义子集 i q x , ii xx q xq xxx 则当模糊神经计算智能系统(fncis)输出解时，其满意度定义为 i x 1 ii i xxx s x xx 式中表示集合中元素的数目。 引用定义 6 设表示的解概率密度函数，则当获得质 q ab qqq 量为的解为时，满意度为 i x q i x 1

29、b xi q i q s xq dq 上述两种满意度与时间无关，称为静态满意度。而下面定义的用来刻画神经网 络在一定时间内输出解的满意程度，称为动态满意度。 引用定义 7 设 fncis 在时刻输出可供选择的解数为，在单位时间 0 0t 0 n t 后获得可供选择的解数为，则该系统在时刻输出解的动态满意度为t 0 n tt 0 t 0 0 0 d n t st n tt 这几个满意度的定义反映了智能信息系统在解空间中搜索时的满意停止条件或 准则，即当搜索过程己几乎找不到解时就应该停止搜索了，此时可认为已经找到整 个解空间的满意解了。从其在 tsp 中的应用可以知道，其满意度定义是合理可行的。

30、2.3.4 基于遗传算法的满意度的定义 马丰宁等定义了类似于动态满意度的遗传算法中的满意度19。 引用定义 8 满意度是与遗传次数有关的指标函数 s 0 / s t t smhm a 其中:a 为代码串空间，为第 t 次遗传所覆盖的集合，表示的 t ha t m h t h 测度，s 为遗传次数。体现了 ga 的结果与最优解的“靠近距离” 。此靠近距离不是 ga 解的值与最优解的值之间的差距，而是选取 ga 解的范围指标。 2.3.5 满意度的性质 由满意度的定义可以看出，它还有以下性质: (l)相对性满意度是在给定满意标准下的满意度。一个问题可能存在多个满意标 准，对于不同的标准，满意度可能

31、不同。同时对一个独立的解，其满意度是没有意 义的。只有讨论两个或两个以上的解时，满意度才有意义。 (2)一般性满意度的定义没有限定其具体的数学表现形式，目的就是定义本身只 需要体现其内涵，至于其表现形式，完全可以根据问题本身由用户确定。 (3)唯一性满意度是在给定满意标准下的满意度。对于一个确定的标准，每个解 具有唯一的一个满意度和它对应。 由于满意度集合是人们对问题的一组解的满意程度的集合，因而满意度必定是 一维空间的量，满意度集合是一个一维集合，它可以是模糊集合也可以是清晰集合。 2.3.6 满意度函数的表示 从满意度的概念可以看出，满意度并没有给出具体的数学表达式，这正反映了 满意度原理

32、不同于最优化理论的一个方面。满意度需要根据具体问题的不同采用不 同的形式，可以根据具体情况采用线性表示、模糊集合的隶属度表示、解集的元素 比例表示等多种方式。同时对于不同的问题，它具有不同的数学特性和表示方式， 针对具体问题，其满意度的获取也将采取不同的方法。 2.4 灵敏度分析 2.4.1 灵敏度分析的概念 通常决策过程中所预测的自然状态概率及计算出的损益值，都不会十分精确， 因此，往往需要对这些变动是否影响最优方案的选择进行深入研究，这就是所谓的 灵敏度分析。 2.4.2 灵敏度分析的应用价值 在大多数实际问题中,线性规划问题的数据不能精确地知道,通常是根据经验估 计或用预测方法得到。因此

33、,某些数据可能需要修改；有时,还可能增加新变量或新 约束。遇到上述情况时,要考虑某些变化对最优解的影响,并不需要从头开始计算,只 需修改原问题的最优解中相应的部分,以便得到条件变化后新问题的解,再判断所得 到的解是否还是新问题的最优解。如果不是,可继续求解。而灵敏度分析就是研究产 品结构优化问题中,数据或约束条件发生变化时,最优结构所受到的影响。 第三章 满意度函数的建立及动态建立 3.1 满意度函数的表示9 满意度是衡量人们在某个标准下对其选择(或行为)满意程度的一种度量。可以 说任何能表示解的质量的量都可用来表示满意度，但是为了满足科研和工程计算的 需要，对一些常用的、易操作的、比较合理的

34、表示形式进行量化的描述和研究非常 必要。 根据满意度的合成原则，对于一般的复杂问题，虽然有许多因素对满意度产生 影响，但我们总可以从某些简单方面开始分析，进而可以通过一维满意度的某些合 成运算来获取多维满意度。 下面给出几种一维满意度函数的表示形式。考虑到满意度函数表示形式存在的 单调性，同时，为了表达形式的一致性，式中的满意度取值范围均为0，l，在实 际应用中，满意度范围可以是用户己定义的某个合理值。 3.1.1 单调减函数(戒上型) l)降半矩形函数 1, 0, da s d da (2)降半-函数 1, 0 , k d a da s dk eda 其中 (3)降半正态函数 s d 1 0

35、 d s d 1 0 a d /al k 1 s d 0 a d a 3 1图降半矩形函数32图降半函数图3-3 降半正态函数 2 1, 0 , k d a da s dk eda ，其中 (4)降半柯西函数 1, 10,0 , 1 da s d da da (5)降半阶梯函数 1 12 23 3 1, , , 0, da p ada s d q ada da 1 a0 a d s d s d 1 0 2 a 3 a d p q 34图降半柯函数35图降半阶梯函数 (6)降半梯形函数 2 12 21 2 1, , 0, da ad s dada aa da (7)降半岭形函数 1 12 12

36、21 2 1, 11 sin, 222 0, da aa s ddada aa da s d 1 1 0 dd 1 a 1 a 2 a 2 a s d 0 36图降半梯形函数37图降半岭形函数 3.1.2 单调增函数(戒下型) (l)升半矩形函数 0, 1, da s d da (2)升半-函数 0, 1, k d a da s d eda (3)升半正态函数 2 0, 1, k d a da s d eda 0 s d s d s d 1 1 00 aaa /al k ddd 1 3 8图升半矩形函数39图升半函数3 10图升半正态函数 (4)升半柯西函数 0, 1 , 1 da s d d

37、a da (5)升半阶梯函数 1 12 23 3 0, , , 1, da p ada s d q ada da a 0 0 s d 1 1 p q 1 a 2 a 3 a d d 3 11图升半柯西函数 3 12图升半阶梯函数 s d (6)升半梯形函数 1 12 21 2 0, , 1, da da s dada aa da (7)升半岭形函数 1 12 12 21 2 0, 11 sin, 222 1, da aa s ddada aa da s d s d 00 dd 1 a 2 a 2 a 1 a 12 /2aa 3 13图升半梯形函数3 14图升半岭形函数 3.2 建立满意度函数的

38、基本准则 (1)真实性、正确性和合理性。满意度函数应能如实反映用户对解的评价体系要 求； (2)实用性。满意度函数要够用、要能用； (3)简洁性。合理的满意度函数应该是在使用上尽量简单,适合于分析计算。 3.3 满意度函数的建立方法9 3.3.1 基于目标函数的直接法 在许多情况下,对解的满意程度是对目标满意程度的一种直接体现,因此建立和 目标函数有直接联系的满意度函数比较比较合理，也能反映问题的需要。特别是对 于目标函数具有解析表达式、量化程度高的问题,满意度的建立就更加容易。可以考 虑采用线性函数等类似方式直接或间接由目标函数导出满意度。下面是由目标函数 导出满意度的一些原则: (l)在满

39、意度函数中，各目标函数的作用应保持合理的数量级比例，才能保证各 个目标具有相应合理的重要程度和变化趋势。 (2)解的满意程度的变化应在满意度函数中反映出来。 (3)具备完备性，对于每一个解必须存在和它对应的满意度。 由目标函数转化为满意度函数，可以采用线形函数、指数函数或目标函数的某 种组合形式。 对于理想的最好解和最差解已知的情况，如果解空间和满意度集合有某种函数 映射关系，可以采用拟线性函数(就是线性函数的某种扩充形式)进行表示。 下例是一个线性函数的满意度表示： min maxmin dd sf dd 式中:是当前得到的解,表示最差解,即满意度最小的解;表示最好解,d min d max

40、 d 即满意度最大的解。 对于复杂的目标函数情况,满意度可能是目标函数的某种组合形式,即 12 ,., n sf f xfxfx 式中:(i =1,2,n)是目标函数。 i f x 3.3.2 利用模糊逻辑构造满意度函数 有些问题,其满意度函数不清晰,或者其目标函数或约束函数具有模糊性,那么建 立模糊的满意度函数可能更适用,更能反映问题的本质。利用模糊逻辑建立满意度有 两种方法。 (1)对于解和评价集都具有模糊性的情况,利用模糊关系的隶属度来表示其满意 度。 通过建立目标评价集的一个模糊子集来实现从解到评判集再到满意集的一个映 射,其中评判集元素的隶属度就是待求的满意度。这个方法可以参考任平教

41、授和罗刚 博士的一些工作8,17。 (2)在多数情况下,问题的解清晰存在,但是评判的标准是模糊的,所以这里我们 通过建立半模糊映射获取满意度。 设,称 fuzzy 关系为 u 到的半 fuzzy 映射,如果 uf x vf y fuv v ，是 u 到的映射。当是 u 到的半 fuzzy 映射时,记为0,1 fvf v :f uv 如果，是 u 到的单射,称为半 fuzzy 单射;0,1 f v:f uv 如果，是 u 到的满射,称为半 fuzzy 满射;如 0,1 ,()fuv f v:f uv 果既是半单射又是半满射,称为半 fuzzy 双射。f:f uv 为了方便,用表示的隶属函数,此外

42、,由分解定理,有 f f 0,1 , f f x ycx y 其中: 1 1, 0,1 f f f x y c x y 这里的就是我们要获取的解的满意度。, f x yx 3.3.3 利用神经网络确定满意度函数 bp 神经网络具有很强的函数映射能力，擅长处理那种规律隐含在一大堆数据中 的映射逼近问题，特别适用于那些需要通过学习的自适应可调的实时性问题，例如 模式识别、自适应控制和模糊决策等。 对于一些问题，可能存在理想(或事实)的最好解和最差解，或者存在部分解和 满意度之间的关系，对蕴涵的这种关系，可以通过 bp 神经网络来得到。比如，对于 多数多目标优化问题，其任一目标，一般存在理想的最优解

43、，因此对于该目标来说， 具有最高的满意度，但由于多目标问题之间可能存在一定的冲突，因此对整个问题 来说最优解一般不存在。然而就每个具体问题而言，用户对于不同的解具有不同的 满意程度，就是说，解和满意度之间可能存在一种隐含的映射关系。 基于解和满意度之间的隐含映射关系，在己知的部分解及其满意度构成的数据 集基础上，可以应用基于神经网络的方法构造满意度。数据集的部分元素作为训练 数据训练神经网络，另外一部分作为验证元素。考虑如表 3-1 所示的输入数据集。 表中显示被考虑数据点的坐标值及其满意度。表中的 x，y 数据点表示两个坐标值， 表达了一个二维问题。 1 p 2 p 3 p 4 p 5 p

44、6 p 7 p x0.0000.4170.7500.8930.9720.9870.997 y-0.900-0.752-0.781-0.858-0.951-0.975-0.995 s0.0000.6600.9380.9890.9991.0001.000 表 3-1 部分坐标点和其满意度的数据集 因为每个数据点被赋予相应的满意度，用表中部分数据和它的满意度去模拟坐 标位置和满意度之间的关系，这样就建立了一个神经网络，如图 3-15 所示。然后用 数据集和满意度值继续训练网络。这个过程反复进行，直到神经网络能模拟所有的 输入输出数据。神经网络的性能通过验证数据集来验证。一旦神经网络己完善，它 的最终

45、结构就用来确定任一解的满意度。 3 15bp图确定满意度函数的神经网络 输入层(解参数)隐层()输出层满意度 ij w 3.3.4 按照解的搜索代价建立满意度函数 由求解代价来衡量解的满意度，求解代价迅速增加的时刻可能是满意解基本找 到的一种象征。 对于求解代价对问题较重要的一些情况，如玉米地里寻找大玉米的问题，搜索 过程本身具有一定的代价，但是如果搜索代价远远超过了问题解本身的价值，那么 这个问题求解的意义就不大了。此时建立与问题搜索过程的代价相关的满意度函数 比较合理。 在满意度函数的建立过程中，满意度函数的自变量可能是搜索代价或搜 索代价的某种函数形式，而满意度可以采取前面介绍的某种满意

46、度形式。 引用定义 9 搜索代价函数 对于整个解空间来讲，有 dw ii c xcxcx 式中:为搜索所花费的代价;为搜索已经花费的代价;为 i c x i x d c i x i x w i cx 搜索将要花费的而没有花费的代价。 i x 在某个搜索时刻，对于解，有且只能有一个，符合择一定理。 i x d i cx w i cx 那么当采用某算法进行搜索时，如果对可能的搜索代价可以估计，则可以采用 下面的方式计算满意度: d i i dw ij cx s x cxcx 建立与搜索代价有关的动态满意度的算法可以是： (1)申请一个解的存储队列(或链表),随机产生解并填充队列; (2)采用某种搜

47、索算法进行解的搜索,对找到的每个解,依次和队列中的解进行比 较,并替换其中满意度最小的那个解; (3)对队列中保留时间长的解的满意度进行一定的调整(增加); (4)经历过一定的搜索时间后,如果队列中的元素在给定时间内保持不变,就可以 认为找到了满意解。 算法中队列长度、满意度的调整以及停止时间等参数的确定需根据具体问题本 身来确定。 3.4 满意度函数的动态建立 对于一般化的函数族，我们可以通过某种构造方法，来建立一个构造函数，以 便之后满意度函数建立的使用。在给定的优化模型中，所建构造函数中的参数可以 通过对该优化问题的寻优过程来逐步确定。 对于优化问题 (3-4-1) 1 min,f xx

48、r 定义假设给定函数族，通过建立对该函数族的某种 12 ( ),( ),( ) m xxx 构造来完成满意度函数的表达，称为满意度函数的构造函数 12 ( ),( ),( ) m xxx 族，简称构造函数族。 定义若一个满意度函数是由构造函数族通过线性形式表达的，则这个满意 度函数称为线性构造满意度函数。 定义评价函数 假设有函数族 121 , mm x xxx 令 (3-4-2) 121 1210 mm mm xa xaxa xa xa 按照某种算法，通过迭代，可得到问题(3-4-1)的最优解集合。其 * 12 , n x xx 中, 表示第 次迭代得到的最优解。 * i x1,2,ini

49、将解集合依次代入(3-4-2)式，可得到关于的一个线性 * 12 , n x xx 01 , m a aa 方程组，解得的值，再重新代入(3-4-2)式可得幂函数的具体表达 01 , m a aa x 式。 不难证明，在点附近，。因此可用逼近，求得最优 * k x f xx x f x 解。 此时，称为问题(3-4-1)的评价函数。 x 定义 4 动态满意度函数 对于评价函数，可以找到一个映射，把映射成满意度函数 xg x ，即。若该满意度函数以时间为某个变量，则 0,1s x :0,1gxs x s x 称为动态满意度函数。 s x 例如，建立函数 *, , iii q x t t 其中，是

50、问题(3-4-1)中第 次迭代得到的最优解； * i xi 是经过某算法得到时的迭代次数； i t * i x 是得到时花费的时间。 i t * i x 如果满足下列性质： *, , iii q x t t 1.关于， 单调增加； *, , iii q x t t i t i t 2. .是关于的凸函数； *, , iii q x t t * i x 3.在点处收敛。 *, , iii q x t t * k x 则问题(3-4-1)的满意度函数可写为： *, , iii x s x q x t t 这就是关于问题(3-4-1)的动态满意度函数。 第四章 灵灵敏度分析 4.1 灵敏度分析一般研

51、究的问题2 在许多实际问题中，数学模型中的数据未知，需要根据实际情况进行估计和预 测，既然是估计，就很难做到十分准确。除此之外，也往往会遇到数据确定但是会 变化的情况。因此，需要研究数据的变化对最优解产生的影响，这对解决实际问题 有重要意义。 例如：我们考虑问题 (4-1) min . .st cx axb x0 下面简要介绍 ，的变化所带来的影响。cab 4.1.14.1.1 改变系数向量改变系数向量c 设线性规划(4-1)的最优解为，目标函数的最优值， -1 b x = b b n x= 0 1 f b c b b 其中是最优可行基，分两种情形讨论。b (1)非基变量的系数改变为 k x

52、k c k c 这时，不变，因此不改变。 b c jj z -1 b c b p 如果，那么原来的最优解也是新问题的最优解，且最优值仍为。0 kk z c 1 b c b b 如果，改变后为进基变量。把原来的换成，然后用单0 kk z c k x kk zc kk z c 纯形法求解问题的最优解。 (2)设为基变量，改变为。 t k xx bk c k c 由于基变量的系数向量改变，因此影响到各判别数，改变后的判别数是 b c (4-1-1-1) t jjjjkktjj jjkktj zccccc zcccy -1-1 bb c b pceb p 当时，jk (4-1-1-2) jjjjkkt

53、j zczcccy 当时，因此有jk1 tk y 0 kk zc (4-1-1-3) 0 kkkkkkkk zczccczc 目标函数值是 (4-1-1-4) 111t t kktkk ccccb bbb c b bceb bc b b 由(4-1-1-3)式至(4-1-1-5)式可知，改变为后，我们可以通过对原来单纯 k c k c 形法的一些改变来求得新问题的最优解。 4.1.24.1.2 改变右端向量改变右端向量b 设改变为。这一改变直接影响到原解的可行性。设改变以前最优基为。bbbb 改变以后必出现下列两种情形之一：b (1) 1 0 b b 这时，原来的最优基仍是最优基，而基变量的取

54、值(或者说最优解)和目标函数 最优值将发生变化。 我们用表示的改变量，记作bb (4-1-2-1) bbb 改变为后，新问题的最优解是bb ， (4-1-2-2) -1 b x = bb+b n x= 0 目标函数的最优值是 (4-1-2-3)f -1 b c bb+b = wb+wb 由此可知 (4-1-2-4) i i f w b 如果把约束看作资源限制，则上式表明，给出每增加一个单位第 种资源所 i wi 引起的最优值的改变量，因此称为第 种资源的影子价格或边际价格，这个经济 i wi 解释是很有用的。 (2) 1 b b0 这时，原来的最优基对于新问题来说不再是可行基。但所有判别数仍小

55、于或b 等于零，因此现行的基本解是对偶可行的。这样，只要把原来的最优表的右端列加 以修改，代之以 (4-1-2-5) -1 -1 b b b c b b 就可以用对偶单纯形法求解新问题。 4.1.34.1.3 改变约束矩阵改变约束矩阵a 有下列两种情形： (1)非基列改变为 j p j p 这一改变直接影响判别函数和单纯形表中第列，改变后，有 jj zcj j y ， jjjj zcc -1 b c b p ， jj -1 yb p 如果，则原来的最优解也是新问题的最优解。0 jj zc 如果，则原来的最优基，在非退化的情形下，不再是最优基。这时，0 jj zc 需将列改为，判别数改为，然后把

56、作为基变量，继续迭代。 j y j y jj zc jj zc j x (2)基列改为 j p j p 改变中的基向量可能引起严重后果，原来的基向量集合用取代后，有可a j p j p 能线性相关，因而不再构成基，即使线性无关，可以构成基，它的逆与原来基矩阵 的逆可能差别很大。由于基向量的改变将带来全面影响，因此在这种情况下，一 1 b 般不去修改原来的最优表，而是重新计算。 4.1 关于动态满意度函数的灵敏度分析 设计一个函数，对问题(1)的满意度函数中变量的灵敏度可用函数的差分来表示 为： i m x x 式中，表示某个设计函数，表示差分。越大，设计函数 m x *, , iiii x t

57、 tx 对变量越敏感，对影响程度越大。表示函数对变量的单 m x i x i x m x m x i x 调性,如果,表示对单调递减；如果,表示对单调递增。0 m x i x0 m x i x 总总 结结 本文综述了满意度原理的产生、发展现状，在定义满意标准、满意度等概念的 基础上，研究了满意度的表示方法。满意度原理可用到被处理问题的诸多环节，一 个确定问题，并没有限定其满意度函数的选择方式。然而在实际应用中，给出满意 度函数的具体表达式却是非常必要的。所以本文系统的研究了满意度函数在不同情 况下的表现形式，为满意度原理的系统化提供了部分依据。 本文定义了满意度原理的几个基本概念；通过对满意度

58、的表示、特点的分析， 揭示了满意度原理的本质特性。 本文引用了基于目标函数的、基于模糊数学的、基于神经网络的几种满意度的 建立方法，一定程度上完善了满意度原理的理论体系。并且在此基础上建立了通过 优化变量、迭代时间、迭代次数的函数族形成的一般性优化问题的动态满意度。动 态满意度的建立是通过利用构造函数的特性，在问题寻优的基础上一步步形成的。 最后，本文对所建立的动态满意度以差分的形式给出了关于其变量的灵敏度分 析。灵敏度分析的意义在于使建立的动态满意度函数更全面和系统，具有进一步的 研究价值。 本文待深入解决的问题还有：如何把人类的满意偏好在设计应用中体现出来;； 如何确立满意度函数的可行域；

59、 如何实现满意问题的规范化、程序化。 满意问题代表了非常广泛的问题类型，把满意度原理应用到具体问题的求解过 程中，发挥其作用，是满意度研究得到验证的保证，也是加速其发展的动力。 参考文献 1. 盛昭瀚，曹忻.最优化方法基本教程.东南大学出版社，1990 2. 陈宝林. 最优化理论与算法.第二版.清华大学出版社，2005：122157 3. 薛嘉庆. 最优化原理与方法.冶金工业出版社，1992 4. 刑文训，谢金星. 现代优化计算方法.清华大学出版社，1999 5. 黄红选，韩继业. 数学规划，2006 6. 魏荣桥.运筹学.第三版.清华大学出版社，2005.4770 7. 胡适耕，施保昌.最优

60、化原理.武汉:华中理工大学出版社，2000 8. 任平.优化理论中的令人满意准则.模糊数学，1983，(4)：111 一 112 9. 姚新胜. 满意优化原理及其在机械工程领域中的应用研究.西南交通大学博 士论文.2002 10. mesaroviemd，takaharay.onaqualitativetheoryofsatisfaetorycontrol. informationseienees，1972，4(4):291 一 313 11. matsudat，thkatsu5.charaeterizationofsatisfieingdeeisioneriterion. informati