数学与应用数学毕业论文.doc

唐山师范学院本科毕业论文题 目 关于模糊约束的多目标线性规划解法的探究学 生 刘海艳指导教师 李宝凤 助教 年 级 05数学专接本4班专 业 数学与应用数学系 别 数学与信息科学系 唐山师范学院数学与信息科学系2007年5月郑重声明 本人的毕业论文（设计）是在指导教师李宝凤老师的指导下独立撰写完成的。如有剽窃、抄袭、造假等违反学术道德、学术规范和侵权的行为，本人愿意承担由此产生的各种后果，直至法律责任，并愿意通过网络接受公众的监督。特此郑重声明。毕业论文（设计）作者（签名）： 年 月 日 目 录标题1中文摘要11 引言12 问题的提出13 在模糊约束下的多目标线性规划的一般模型14 对在模糊约束下的多目标线性规划问题的求解24.1 构造评价函数将多目标线性规划问题转化为单目标线性规划问题24.1.1 判断矩阵法确定权系数24.1.2 线性加权和法44.2 构造模糊目标集将单目标线性规划转化为普通线性规划54.2.1 预备知识54.2.2 求解步骤55 推广了的多目标模糊线性规划66 事例97 总结12参考文献13致谢14附录.15外文页17 关于模糊约束的多目标线性规划解法的探究刘海艳摘 要 该文主要研究了在模糊约束下的多目标线性规划问题的一般模型及其解法。其基本步骤是首先将在模糊约束下的多目标线性规划问题通过线性加权和法将其变为单目标模糊线性规划问题，再通过构造模糊目标集将单目标模糊线性规划问题转化为普通单目标线性规划问题，然后求解单目标线性规划，此时单目标线性规划问题的解是原问题的模糊满意解。接着讨论推广了的多目标模糊线性规划问题：目标函数带有“模糊性”或目标函数和约束条件都带有模糊性的多目标模糊线性规划问题的解法。最后用实例验证这种方法。关键词 多目标线性规划 模糊约束 评价函数 模糊目标集1 引言在实际生活中，人们经常会遇到同时追求多个目标的最优化问题，比如设计一个新产品人们总希望在一定条件下能选择具有质量好，产量高和利润大的方案。在这类问题中，人们总希望能够使多个目标都达到最优，然而由于多个目标不能同时兼得，甚至有些目标间还可能相互矛盾，往往不像单目标规划那样存在绝对最优解，一般决策者通过对各个目标值的满意程度（或偏好）来确定某些满意解为最终解，为此，前人们提出了求解该类问题的模糊折衷算法以及两阶段算法1-2并证明了这两种方法求得的解是模糊有效解。然而，在实际的多目标线性规划问题中，约束条件往往又有一定的变动范围，而不是确定的上界或下界，也就是说约束条件带有某种伸缩即所谓的“模糊”约束。使用模糊约束的目的在于希望在一定“保证率”下适当的增大目标函数值。在模糊约束条件下，如何确定各目标的解使总体相对最优，以达到决策者的满意程度，这就是该文所要讨论的在模糊约束下多目标线性规划问题，首先将在模糊约束下的多目标线性规划通过线性加权和法将其变为单目标模糊线性规划，再通过构造模糊目标集将单目标线性规划转化为普通单目标线性规划，然后求解普通线性规划，所求得的解就是在模糊约束下的多目标线性规划问题的。2 问题的提出在普通的多目标线性规划问题中，目标约束和变量约束都是明确的，但实际问题中往往是一种模糊的状态，约束条件带有某种伸缩性，如生产工时可以上浮或下浮，设备可以超负荷运转，对这些问题在一般情况下是不能忽略的，而普通的多目标线性规划是无法解决这类问题的，从而也就难以实现资源的优化配置，于是人们提出了多目标模糊线性规划，它可以弥补普通多目标线性规划的不足。3 在模糊约束下的多目标线性规划的一般模型 max (1)s.t. 令c= ， a=, =, =, =，=, 则问题(1)可简记成max =cxs.t.其中=叫决策变量，=叫向量目标函数，=叫伸缩指标向量。多目标线性规划问题不像单目标线性规划问题存在绝对最优解，但是我们可以寻找满足决策者的有效解，为了解决该类问题，我们需要将多目标线性规划问题转化为单目标线性规划问题，寻找满足决策者的有效解。4 对在模糊约束下的多目标线性规划问题的求解4.1 构造评价函数将多目标线性规划问题转化为单目标线性规划问题构造评价函数的方法主要有线性加权和法、极大极小法、理想点法3-4。这里通过线性加权和法来构造评价函数，其基本思想是，根据各个目标在问题中的重要程度，分别赋予它们一个数，并把这个数作为该目标的系数，然后把这些带系数的函数相加的和函数作为评价函数。权系数的相对大小表示各目标的相对重要程度，重要的目标应赋予较大的权数，不重要的目标应赋予较小的权数。因此权系数的确定就成为本方法求得有效解的关键。在数学建模中，层次分析法是要比较若干因素对同一目标的影响，从而确定它们在目标中占的比重，即权重，采用的是比较法来构造判断矩阵5。这种方法比较有效，这里也采用判断矩阵法来确定权系数。4.1.1 判断矩阵法确定权系数该法是首先用数字1至9标出对两两目标的比较判断，然后构造所谓判断矩阵，再计算出所有目标的权系数。引进1至9的比例标度，见下表。表1 判断矩阵标度及其含义如下表标度含义135792、46、8倒数表示两个因素相比，具有同样的重要性表示两个因素相比，一个因素比另一个因素稍微重要表示两个因素相比，一个因素比另一个因素明显重要表示两个因素相比，一个因素比另一个因素强烈重要表示两个因素相比，一个因素比另一个因素极端重要上述两相邻判断的中值上述两相邻判断的中值相应两因素交换次序比较的重要性为确定多目标线性规划问题中的m(2)个目标的权系数，需要把目标相对于目标(=1,2,，m)的判断数作为元素组成mm阶矩阵a=.称为问题(1)的判断矩阵a具有如下性质：0, =, =1,2,，m，=称a为正的互反矩阵。当a的元素满足传递性，=时，称a为完全一致性矩阵 因第个目标(=1,m)相对其它各目标的判断数：表示相对于其它各目标的重要程度。则目标在整个问题中的重要程度可用它们的几何平均值给出，即=，=1,m对进行规范化后得, =1,m 即为问题的一组权系数(1) 求权系数的计算步骤step1 a中元素按行相乘得 step2 将开m次方根得 step3 将各方根规范化得 即为一组权系数由于客观事物的复杂性和人们认识事物的多样性，在实际问题中，要求判断矩阵a满足完全一致性是困难的，但要求人们的判断有大体的一致性是应该而且必要的。若判断偏离完全一致性过大，计算出的各目标的权系数对问题的反应将“失真”，这样也就失去了确定权系数的意义。因此就需要对矩阵a作一致性检验。(2) 一致性检验一致性比率记为cr，cr=ci/ri。其中ci=叫做一致性指标，ri叫平均随机一致性指标，对于1至9阶的判断矩阵ratty给出ri的值见下表表2 平均随机一致性指标rin1 2 3 4 5 6 7 8 9ri0 0 0.58 0.90 1.12 1.24 1.32 1.41 1.45最大特征根用来计算当cr，对应的有x中一个模糊集，其隶属函数取为 =对每一个约束条件，对应的有x中的一个模糊子集，其隶属函数为 令 为了兼顾模糊约束集与模糊目标集，可采用进行模糊判决，再利用最大隶属原则求=将看作变量并要求，以及要求来求，于是最终可将问题(2)转化为下面的普通线性规划问题：max s.t. (3)利用单纯形法求普通线性规划问题(3)的解就是多目标线性规划问题(2)的解。5 推广了的多目标模糊线性规划 以上讨论的是目标函数是明确的，而约束条件带有“模糊性”的多目标模糊线性规划问题的解法。但有时候在决策时决策者为了增大目标值，使目标函数带有“模糊性”而约束条件是明确的，或目标函数和约束条件都带有“模糊性”的多目标线性规划问题。这两种规划的模型为模型(4)和模型(5)：max (4)s.t. 。其中是对每一个目标，在其约束下求出的最优值，是目标函数的伸缩指标。max (5)s.t. 其中是对每一个目标，在其约束下求出的最优值，是目标函数的伸缩指标，=是约束条件的伸缩指标。对于模型(4)与模型(5)同样采用模糊集的隶属函数将其转化为普通的线性规划。在模型(4)中，对每一个目标，在其约束下求出最优值，。再作每个目标函数的模糊目标集，其隶属函数是记，求，使达到最大，于是得到新的线性规划问题max s.t. (6)在模型(5)中，对每一个目标，在其约束下求出最优值，。再作每个目标函数的模糊目标集，其隶属函数是对每一个约束条件，对应的有x中的一个模糊子集，其隶属函数为 记，采用进行模糊判决，求，使达到最大，于是得到新的线性规划问题max s.t. (7)求解模型(6)、模型(7)的解是模型(4)、模型(5)的模糊最优解。6 事例下面就模型(2)应用到事例上。例：某厂生产a、b两种产品，若生产a产品，每单位需加工2个机时，产品b每单位需加工1个机时，工厂每周开工时间最多约为140机时（伸缩程度为20机时），根据市场预测产品a每周需求量最多约为60个单位，产品b为100单位（伸缩程度为10），产品a的利润为300元/单位，产品b的利润为120元/单位 ，问如何安排生产能使每周生产的产品数量多，利润大，并且加工机时尽量少。（）设为产品a的每周生产单位数，为产品b的每周生产单位数，为每周生产的产品数量，为每周的利润，为每周加工机时数，则有下面的多目标模糊线性规划max= +max=300+120min=2+ (8)s.t. 该问题各目标的判断矩阵a=各目标在问题中的重要程度=1.25992105 =2.289428485 =0.346690637进行规范化后的=0.323385855 =0.587631097 =0.088983047这时就是问题(8)的一组权系数。检验权系数是否可以被接受。矩阵的最大特征根为=3.009202707一致性指标ci=0.0046013553, 当n=3时平均随机一致性指标ri=0.58一致性比率cr=ci/ri=0.0079333680.1满足一致性，所以确定出的权系数可以被接受，为了计算方便取（）于是将多目标规划问题(8)转化为单目标规划问题(9)max =s.t. (9)先解线性规划问题max (10)s.t. 用单纯形法解此线性规划问题得=60，=20，=12250。此时，原问题的模糊最优解为，解线性规划问题max (11)s.t. 用单纯形法解此线性规划问题得=70，=20，z=14051，=14051-12250=1801。此时，原问题的模糊最优解为，再解线性规划问题max s.t.用大m法求解max +0+0+0+0-m+0s.t. =70，=30，=1=180.170+72.230=14773经过用模糊约束后比以前的12250多了2523。此时，原问题的模糊最优解为，7 总结以上讨论了在模糊约束下的多目标线性规划问题的解法以及推广了的多目标模糊线性规划问题：目标函数带有“模糊性”或目标函数和约束条件都带有模糊性的多目标模糊线性规划问题的解法。最后用实例验证这种方法。从上例可以看出，利用模糊线性规划讨论最优化问题比普通线性规划更灵活，对于单目标线性规划可以增大目标函数值，对于多目标线性规划，由于决策者的偏好，给每个目标加权后得到的单目标线性规划在模糊约束下虽然增大了目标函数值，但是不能增大所有的目标函数值，增大其中某些目标函数值时要降低另一些目标函数的值，但这在实际的决策中也是符合决策者的意图的。所以在以后还需要更深入的研究有关多目标模糊线性规划的解法，探讨它在各方面的应用以实现资源的优化配置。 参考文献1 李荣钧.多目标线性规划模糊算法与折衷算法分析j.运筹与管理,2001,3:13-182 李学全 李辉.多目标线性规划的模糊折衷算法j.中南大学学报,2004,3:514-5173 胡毓达著.实用多目标最优化m.上海:上海科技出版社,19904 解可新等著.最优化方法m.天津:天津大学出版社,19975 刘来福 曾文艺编著.数学模型与数学建模m.北京:北京师范大学出版社,20026 彭祖赠 孙韫玉编著.模糊数学及其应用m.武汉:武汉大学出版社,20027 宋晓秋.模糊数学原理与方法m.徐州:中国矿业大学出版社,20048 谷源盛主编.运筹学m.重庆:重庆大学出版社,20019 李录书.多目标运输问题的fuzzy线性规划解法j.运筹与管理,1994,1:11-1510 刘洪.运用线性规划理论解决模糊线性规划问题j.鞍山师范学院学报,1994,3:42-4411 李学全 李辉.带权值的模糊多目标线性规划j.经济数学,2003,4:81-8512 李惠玲.精益求精的最优化m.南宁:广西教育出版社,1999致 谢我的论文是在指导教师李宝凤的悉心指导下完成的。李宝凤老师严谨的治学态度、精益求精的工作作风、诲人不倦的高尚师德、严以律己、宽以待人的崇高风范、平易近人的人格魅力对我将是永远的鞭策。我在撰写毕业论文（设计）期间的工作，从选题到完成，每一步都是在李宝凤老师全面、具体的指导下进行的，倾注了老师大量的心血。李宝凤老师渊博的学识、敏锐的思维、民主而严谨的作风，使我受益匪浅，终生难忘。在此，谨向导师表示崇高的敬意和衷心的感谢。本论文的顺利完成也离不开各老师、同学和朋友的关心和帮助。在此，感谢本组的葛卫军老师、王东华老师、樊海燕老师和冯玉芬老师的帮助和支持，也感谢我的同学和朋友们。附录a问题(10)的单纯形表 c180.1 72.20 0 0 0 0 0 2 11 00 1 1 0 0 0 1 0 0 0 1 140 60 10070 60 0 0 0 0 0=0180.1 72.2 0 0 0 0 180.1 0 0 11 00 11 -2 00 1 00 0 1 20 60 100 20 100180.1 00 180.1 0=108060 72.20 -180.1 072.2 180.1 0 0 11 00 01 -2 00 1 0-1 2 1 20 60 80180.1 72.272.2 35.7 0=12250 0 0-72.2 -35.7 0附录b问题(11)的单纯形表 c180.1 72.20 0 0 解 比 0 0 0 2 11 00 1 1 0 0 0 1 0 0 0 1 160 70 11080 60 0 0 0 0 0=0180.1 72.2 0 0 0 0 180.1 0 0 11 00 11 -2 00 1 00 0 1 20 70 110 20 100180.1 00 180.1 0=126070 72.20 -180.1 072.2 180.1 0 0 11 00 01 -2 00 1 0-1 2 1 20 70 90180.1 72.272.2 35.7 0=14051 0 0-72.2 -35.7 0the study of the solution on multi-objective linear programming problem under fuzzy constraintliu haiyan directed by assistant li baofengabstract this paper mainly presents the general model and solution of multi-objective linear programming problem under fuzzy constraint.the basic steps may be presented as follows: firstly, multi-objective linear programming problem under fuzzy constraint is changed to single-objective linear programming problem under fuzzy constraint by linear weighted sum method;secondly, single-objective linear programming problem under fuzzy constraint i