（管理科学与工程专业论文）不确定环境中的时间费用均衡理论与应用研究.pdf

摘要 摘要 时问费用均衡问题是为了解决如何在时间或者资源的约束条件下做出最优 决策以平衡工程的完工时间和资源或者费用消耗的一类优化问题。本文主要研 究了包括随机、模糊、混合等几类不确定环境中的时f a j 费用均衡问题，根据不 i 一的决策准则分别建立了优化模型并设计了智能算法。 随机和模糊环境中的时间费用均衡问题在过去几十年里分别得到了一定的 发展，但是根据解决现实问题的需要，建立贴近实际的数学模型和设计相应有 效的算法仍然是研究的重点之一，因此需要引入更多能够反映现实不确定性的 规划思想和更多符合管理优化需求的决策准则。本文考虑了一类在不确定环境 下有时间约束并优化费用的时间费用均衡问题。在随机情况下，本文针对目前 该问题中只考虑以优化期望值为决策准则的欠缺，引入了两类不吲的决策准 则，并据此建立了两类随机模型，分别是随机q 费用最小化模型和概率最大化 模型。针对几类随机函数的求值分别设计了随机模拟的方法，并且嵌入遗传算 法中设计了混合智能算法，通过数值实验证明了算法对解随机环境中的时间费 用均衡模型是有效和稳定的。随后，针对模糊环境下的时间费用均衡问题，本 文引入了可信性理论的思想，建立了三类模糊模型，分别是模糊期望费用最小 化模型、模糊q 费用最小化模型和可信性最大化模型，设计了解上述模型的结 合模糊模拟和遗传算法的混合智能算法，给出了数值实验并对算法有效性和稳 定性进行了说明。随后，本文提出并研究了随机和模糊两种刁i 确定性并存情况 下的时间费用均衡问题，将模糊随机规划引入到该问题中，建立了模糊随机期 望费用最小化模犁、模糊随机( n ：) 费用最小化模型和机会最大化模型，并分 析了模糊随机模型分别退化成随机模型和模糊模型的情况。设计了模糊随机模 拟的方法，并结合遗传算法设计出了混合智能算法，通过数值实验证明了算法 对解模糊随机环境中的时间费用均衡问题是稳定的。更进一步，本文分别引入 了混合规划和不确定规划的相关思想，介纠了在混合环境和不确定环境中的时 间赞用均衡问题，建立了相应的优化模型，并进行了一定的分析。 本文的创新点包括：( 1 ) 分别研究了在随机、模糊、随机和模糊两种彳i 确 定性共存等不确定环境中的时间费用均衡问题，根据不h 决策准则分别建立了 几种数学规划模型；研究了模糊随机模型的退化情况。( 2 ) 介绍了混合环境和 i i a b s t r a c t a b s t r a c t t i m e c o s tt r a d e o f fp r o b l e mi st od e t e r m i n et h eo p t i m a lb a l a n c eb e t w e e nt h et o t a l p r o j e c tc o s ta n dt h ep r o j e c tc o m p l e t i o nt i m eu n d e rs o m e t i m eo rr e s o u r c ec o n s t r a i n t s t h et h e s i ss t u d i e st i m e c o s tt r a d e - o f ! fp r o b l e mu n d e rs o m eu n c e r t a i ne n v i r o n m e n t s ，e s t a b l i s h e ss e v e r a lu n c e r t a i nm o d e l sa c c o r d i n gt od i f f e r e n to p t i m i z a t i o nr e q u i r e m e n t s ， a n dd e s i g n sh y b r i di n t e l l i g e n ta l g o r i t h m st os o l v et h em o d e l s t h o u g hi nt h ep a s tf o r t yy e a r st i m e c o s tt r a d e o f fp r o b l e mi nu n c e r t a i ne n v i r o n 。 m e n t sh a sb e e nd e v e l o p e dq u i c k l y , t ob u i l dm o r eo p t i m i z a t i o nm o d e l st om e e td i f f e r - e n to p t i m i z a t i o nr e q u i r e m e n t si np r a c t i c a lp r o b l e m si sa l w a y sa ni m p o r t a n ti s s u e f o r t h ef a c t t h a ti ns t o c h a s t i ct i m e c o s tt r a d e o f fp r o b l e mo n l yt h ec r i t e r i o no fo p t i m i z i n gt h ee x p e c t e do b j e c t i v ev a l u ew a sa p p l i e d t w oo t h e rd e c i s i o n m a k i n gc r i t e r i aa r e i n t r o d u c e da n dt w os t o c h a s t i cm o d e l s ：s t o c h a s t i cq c o s tm i n i m i z a t i o nm o d e la n dp r o b a b i l i t ym a x i m i z a t i o nm o d e la r ep r o p o s e d a n d t oc o m p u t es e v e r a lt y p e so fs t o c h a s t i c f u n c t i o n si nt h ea b o v em o d e l s ，s t o c h a s t i cs i m u l a t i o n sa l ed e s i g n e da n da r ee m b e d d e d i n t og e n e t i ca l g o r i t h mt oe s t a b l i s hah y b r i di n t e l l i g e n ta l g o r i t h m ，w h o s ee f f e c t i v e n e s s i sp r o v e db ys e v e r a ln u m e r i c a le x p e r i m e n t s t h e nt os u p p l e m e n tm o r eo p t i m i z a t i o n m o d e l sf o rf u z z yt i m e c o s tt r a d e o f fp r o b l e m ，a c c o r d i n gt od i f f e r e n td e c i s i o n m a k i n g c r i t e r i a ，t h et h e s i sb u i l d st h r e ef u z z ym o d e l s ：f u z z ye x p e c t e dc o s tm i n i m i z a t i o nm o d e l ， f u z z yo t c o s tm i n i m i z a t i o nm o d e la n dc r e d i b i l i t ym a x i m i z a t i o nm o d e l ，a n di n t e g r a t e s f u z z ys i m u l a t i o n sa n dg e n e t i ca l g o r i t h mt od e s i g nah y b r i di n t e l l i g e n ta l g o r i t h m ，w h i c h i ss t a b l et os o l v et h em o d e l sb yi l l u s t r a t i n gs o m en u m e r i c a le x p e r i m e n t s f u r t h e r m o r e ， t h et h e s i ss t u d i e st i m e c o s tt r a d e o f fp r o b l e mw i t hm i x e du n c e r t a i n t yo fr a n d o m n e s s a n df u z z i n e s s t h ef u z z yr a n d o mp r o g r a m m i n gi si n t r o d u c e da n dt h r e ef u z z yr a n d o m m o d e l s ：f u z z yr a n d o me x p e c t e dc o s tm i n i m i z a t i o nm o d e l ，f u z z yr a n d o m ( q ，) - c o s t m i n i m i z a t i o nm o d e la n dc h a n c em a x i m i z a t i o nm o d e la r eb u i l t t h ed e g e n e r a t i o nc a s e s a r es t u d i e d ah y b r i di n t e l l i g e n ta l g o r i t h mi sd e s i g n e da n ds o m en u m e r i c a le x a m p l e s a l eg i v e nt os h o wt h ee f f e c t i v e n e s so ft h ea l g o r i t h m f i n a l l y , b a s e do nt h ei n t r o d u c t i o n o ft h ep h i l o s o p h i e so fh y b r i dp r o g r a m m i n ga n du n c e r t a i np r o g r a m m i n g ，s o m em o r e o p t i m i z a t i o nm o d e l so ft i m e c o s tt r a d e o f fp r o b l e ma r e b u i l ta n da n a l y z e d i i i a b s t r a c t i nc o n c l u s i o n ，t h i st h e s i sp r o m o t e st h ed e v e l o p m e n to ft i m e - c o s tt r a d e o f fp r o b l e m w i t h ( 1 ) s e v e r a lt y p e so fn e wo p t i m i z a t i o nm o d e l so ft i m e - c o s tt r a d e o f fp r o b l e mw i t h s t o c h a s t i c ，f u z z ya n df u z z yr a n d o ma c t i v i t yd u r a t i o nt i m e s ，r e s p e c t i v e l y , a n dt h es t u d y o fd e g e n e r a t i o nc a s e so ff u z z yr a n d o mm o d e l s ；( 2 ) t h ea p p l i c a t i o no fh y b r i dp r o g r a m m i n ga n du n c e r t a i np r o g r a m m i n gi nt i m e c o s tt r a d e o f fp r o b l e m ；( 3 ) h y b r i di n t e l l i g e n t a l g o r i t h m si n t e g r a t e db yu n c e r t a i ns i m u l a t i o n sa n dg e n e t i ca l g o r i t h m ，a n dn u m e r i c a l e x p e r i m e n t st os h o wt h ee f f e c t i v e n e s so ft h eh y b r i di n t e l l i g e n ta l g o r i t h m s k e y w o r d s ：t i m e c o s tt r a d e - o f fp r o b l e m ；r a n d o mv a r i a b l e ；f u z z yv a r i a b l e ；f u z z yr a n d o m v a r i a b l e ；g e n e t i ca l g o r i t h m 日录 目录 第1 章引言 1 1 1 选题背景及意义 1 1 2 国内外研究动向 3 1 3 本文的结构安排 7 第2 章时间费用均衡问题及不确定环境中的决策准则 9 2 1 时间费用均衡问题简述 9 2 2 不确定决策准则1 l 2 2 1 随机决策准则1 1 2 2 2 模糊决策准则1 2 2 2 3 模糊随机决策准则1 5 2 3 结束语1 8 第3 章随机时间费用均衡问题的模型与算法1 9 3 1 概述1 9 3 2 随机时间费用均衡模型2 0 3 2 1o 费用最小化模型2 0 3 2 2 概率最大化模型2 l 3 3 混合智能算法2 3 3 3 1 随机模拟2 3 3 3 2 遗传算法2 4 3 3 2 1 表示结构2 6 3 3 2 2 初始化过程2 6 3 3 2 3 评价函数2 6 3 3 2 4 选择过程2 6 3 3 2 5 交义操作2 7 3 3 2 6 变异操作2 7 3 3 3 混合智能算法2 8 v 目录 3 4 数值实验2 8 3 4 1a 费用最小化模型3 0 3 4 2 概率最大化模型3 l 3 5 结束语3 2 第4 章模糊时间费用均衡问题的模型与算法3 3 4 1 概述3 3 4 2 模糊时间费用均衡模型3 4 4 2 1a 费用最小化模型3 4 4 2 2 期望费用最小化模型3 5 4 2 3 可信性最大化模型3 6 4 3 混合智能算法3 7 4 3 1 模糊模拟3 7 4 3 2 混合智能算法3 9 4 4 数值实验4 0 4 4 1q 费用最小化模型4 0 4 4 2 期望费用最小化模型4 2 4 4 3 可信性最大化模型4 3 4 5 结束语4 4 第5 章模糊随机时间费用均衡问题的模型与算法4 5 5 1 概述4 5 5 2 模糊随机时间费用均衡模型4 6 5 2 1 期望费用最小化模型4 6 5 2 2 ( o r ：，p ) 费用最小化模型4 6 5 2 3 机会最大化模型4 7 5 3 模糊随机模型的退化4 8 5 3 1 期望费用最小化模型的退化4 8 5 3 2 ( q ，卢) 费用最小化模型的退化4 9 5 3 3 机会最人化模型的退化5 l v i 目录 5 4 混合智能算法5 2 5 4 1 模糊随机模拟5 2 5 4 2 混合智能算法5 3 5 5 数值实验5 4 5 6 结束语5 6 第6 章其他不确定环境中时间费用均衡问题的研究5 7 6 1 混合时间费用均衡问题介绍5 7 6 1 1 混合规划5 7 6 1 2 混合时问费用均衡模型6 0 6 1 2 1 期望费用最小化模型6 0 6 1 2 2q 费用最小化模型6 0 6 1 2 3 机会最大化模型6 l 6 1 3 混合智能算法6 l 6 2 不确定时间费用均衡问题介绍6 5 6 2 1 不确定规划6 5 6 2 2 不确定时间费用均衡模型6 9 6 2 2 1 期望费用最小化模型6 9 6 2 2 2q 费用最小化模型7 0 6 2 2 3 机会最大化模型7 0 6 3 结束语7 l 第7 章结论7 2 7 1 论文的主要工作7 2 7 2 论文的创新点7 3 7 3 进一步开展的工作7 3 参考文献7 5 致谢8 2 个人简历、发表的学术论文与研究成果8 3 v i i 主要符号对照表 ，叩 p r p o s n e c c r 朋 c h e ( q ，一q ，p r ) ( e ，p ，c r ) 0 蹰 主要符号对照表 随机变量，模糊变量，模糊随机变量， 混合变量，不确定变量 概率测度 可能性测度 必要性测度 可信性测度 不确定测度 机会测度 期望值算子 概率空间 可信性空问 空集 实数集 v i 第1 章引言 1 1 选题背景及意义 第1 章引言 当今的社会是一个信息社会，信息量的爆炸性增长使得不确定性因素在信 息处理和相应现实问题解决中的重要性越来越引起人们的思考。对应到各类优 化问题中，有越来越多的学者从不考虑现实中确实存在的信息中的1 i 确定因素 到开始考虑在问题中引入对不确定凶素的描述并加以分析，从只考虑传统上的 随机性到开始考虑模糊性、粗糙性甚至多重不确定性。研究的优化问题越来越 复杂，而相应地解决这些问题的方法也被不断地提出。而为了解决这些越来越 复杂的问题，各类启发式算法也应运而生，包括遗传算法、禁忌搜索、模拟退 火、进化模拟、神经元网络等各种算法都得到了很好的发展和应用。本文根据 优化问题研究的趋势，研究在考虑工程中不确定因素的情况下的时间费用均 衡问题( t i m e c o s tt r a d e o f f p r o b l e m ) 。作为工程进度优化问题的一个重要分 支，我们针对以往对该问题研究巾建模方面的不足，根据不同的优化要求提出 了几类不确定环境下的数学模型，并且应用启发式算法设计了混合智能算法来 解这些模型。 我们知道，一个工程往往是由很多的子项目组成的，而这些子项目都有自 己的执行时间，并且往往需要一定数量的资源。因而对一个工程来说，往往既 有时间约束，又会有资源( 费用) 的约束。如何在有限的条件下平衡t 程的费 用和完工时间是一个很现实也很有必要研究的问题。早在上1 i = 纪六十年代初 期，k e l l e y 就对确定情况下的时间费用均衡问题进行了研究，揭开了这一4 问题 研究的序幕，同时也是工程进度优化问题研究的开始【1 2 】。 辨证地说，彳i 确定性是绝对的，确定性是相对的。在包括运筹学、管理科 学、信息科学等的众多领域中都存在着主观的或客观的不确定性，比如随机 性、模糊性、粗糙性及多重不确定性等。从而自然地，在这些领域中的很多决 策和优化问题也往往需要考虑不确定性冈素对问题的影响。而对于一个工程来 说，由于外部环境的不确定性，诸如气候的变化、生产率的提升等，各个子项 的不确定 在研究时 合现实的 决策的影响。随机性是时间费用均衡优化问题中第一一类被考虑的不确定性，而 概率论是一门研究各种包含随机性的现象和问题的数学分支学科。时间费用均 衡问题中的参数( 主要是子项目的执行时间) 口j 以很自然地以随机变量来刻 画。早在2 0 世纪6 0 年代，f r e e m a n 就将概率论引入到工程进度优化问题中进行 了研究【3 一。但是在现实中还有很多的不确定事件是不能以随机性来描述的。如 对高度、重量的估计等。模糊集理论是另外一类人们经常用来刻画不确定性的 理论，最早i 扫z a d e h 于上世纪6 0 年代提出【5 1 。现在包括模糊集理论在内的研究模 糊现象的理论已经逐渐成为人们解决不确定问题的重要方法。在上世纪7 0 年代 末，p r a d e 将模糊集理论引入到了工程进度优化问题中进行了研究1 6 。而作为工 程进度优化问题重要分支的时间费用均衡问题，对该问题的研究也越来越多地 引入了不确定的因素。 随着各类优化和决策问题的不断发展，传统的算法在很多情况下已经不能 适应解决各类问题的需要。而随着上世纪计算机技术的飞速发展和各种启发式 算法( 如遗传算法、禁忌搜索、模拟退火、神经元网络等) 的不断涌现，许多 复杂的优化问题已经能够通过计算机应用启发式算法得到解决。虽然目前各类 优化问题方面的很多研究都集中在改进算法的运行的效率上，但是相信随着计 算机技术的不断进步，优化问题中更需要解决的是根据实际的情况提出贴近现 实的优化模型和设计合适的算法。对于时问费用均衡问题来说也是一样，建立 更为贴近实际的模型和设计相应的合适有效的算法也应该是这一问题研究的重 点，而缺少更多符合实际并满足各类优化要求的模型恰恰是目前对该问题研究 的一个欠缺。 本文将对不确定环境中的时间费用均衡问题进行研究。针对不列类型的不 确定性，包括随机性、模糊性以及随机、模糊混合不确定性等，我们针对现实 不同的优化要求和决策准则分别提出三类不确定优化模型，即期望值模型、机 会约束规划模型和相关机会规划模型。针对这些4 i 确定环境下的优化模型，本 文结合对不确定函数模拟的方法( 随机模拟、模糊模拟和模糊随机模拟等) 和 2 第1 章引言 遗传算法等启发式算法分别设计了用于求解的混合智能算法，并分别针对几类 不确定环境下的优化模型设计了数值实验，通过数值实验分析和说明了算法的 有效性和稳定性。此外，我们还针对更加一般化的混合环境和不确定环境下的 时间费用均衡问题进行了分析，指出了未来研究的方向。 1 2 国内外研究动向 时间费用均衡问题是通过决定如何调整工程子项目以平衡整个工程的费用 和总体完工时间的一个优化问题。随着经济和社会的发展，在经过了过去的几 十年的研究以后，时间费用均衡问题已经得到了很大的发展，在很多方面都得 到了丰富的成果。 时间费用均衡问题是工程进度优化问题的一个重要分支，也是该问题中最 早被研究的一个分支问题。k e l l e y 最早对该问题进行了研究，这同样也是工程 进度优化问题研究的开始【1 1 。在【l 】中，k e l l e y 第一个给出了工程费用和子项目 执行时间之间的函数关系，从而建立了t 程进度优化问题及其子问题时间赞用 均衡问题的数学基础。随后，k e l l e y 给出了一种方法来解决一类最小化工程总 费用的确定型时间费用均衡问题f 2 1 。在接下来对时问费用均衡问题的研究中， 工作主要集中在对确定性的环境下该问题的研究【7 ，羽。解时间费用均衡问题，最 常见的解析方法是线性规划和动态规划【9 ，嘲。近年来，随着启发式算法在各个 领域的应用，也有不少学者用启发式算法对时间费用均衡问题进行研究，比如 有些学者用遗传算法对该问题进行了研列- l3 1 。 当今社会是一个真正的信息型的社会。在经济、社会和科技的发展中，充 斥着大量的信息，而各种信息巾总是含有各种各样的不确定性，或者是人为 的，或者是客观存在的。这些形形色色的不确定性也存在于大量的优化和决策 问题中。在问题的不确定因素对问题的求解影响不是很大的情况下，我们可以 假定优化问题所处的环境是确定的，优化模型中的目标函数和约束条件等是清 楚的。而实际1 - _ ，任何一个实际的优化问题的环境都是充满着不确定的因素 的，而且这些不确定的囚素对整个优化问题来说往往是不能忽略的。如果将这 些不确定的因素忽略掉，往往町能引起与原有问题的偏差，由此得到的结果往 往也不能很好地应用到实际中去解决实际问题。因此，明确问题中存在的不确 3 问题中存在的随机性的学科，就是概率论。在经过大量学者几十年的不断发展 之后，概率论的理论得到了极大的发展和完善，并且成功地被应用到包括经 济、金融、军事、工程、管理等各个领域，在各个领域都取得了很好的发展。 由于工程中子项目的执行时间往往是含糊的、不清楚的和不能完全确定的， 工程进度优化问题中也因此往往存在着各种不确定性。最早的不确定型的工 程进度优化问题由于其中的不确定性都被假设为随机性而引入了概率论的思 想。f r e e m a n 首先将概率论引入了工程进度优化问题f 3 ，4 1 。在随后的几十年的研 究中，诸多学者用了很多不同的方法研究随机的- t 程进度优化问题【怍1 6 】。 作为工程进度优化问题的一个重要分支，近些年米，越来越多的学者也 开始对随机环境下的时间费用均衡问题的研究产生了兴趣。w o l l m e r 讨论了 一类随机线性时间费用均衡问题，将一些离散的随机变量应用到问题的研究 中【1 7 1 。在该文中，工程的网络结构被假设为是以图中的弧代表各子项目的， 这样可以简化网络结构，便于问题的讨论。在该网络中，每个子项目的执行 时间以+ 岛来表示，其中，作为决策变量，并且处在一定的范围，钍巧】 中，而已f 是一个期望为0 的有界离散随机变量，并且独立于决策变量玑，。每个 子项目都有一个相关的非负的费用c i f ，代表犰，每降低一单位所需要的费用。 该问题的目标是在满足一定的预算约束的条件下如何决定犰j 使得工程的完工 时间最小。g u t j a h r 等设计了种改进的随机分支定界的方法，并将其应用到 一类特定的随机离散时问费用均衡问题中【1 8 】。在1 1 8 中，子项目的执行时间假 设为卢分布的随机变量哦f ，而也j 的具体分布函数会因为决策者的调整而有所 变化，不同的费用对应着不同的分布函数，即不同的费用对应着子项目的不同 执行时间。s c h o u 应用一种新的方泫建立了几种随机的时间费用均衡模型【归】。 他将文献1 2 0 中的网络作为测试集，得出所谓的惩罚模型在几类解鲁棒性意义 下能够产生最好的结果。l a s l o 提出了一个随机c p m 时间费用均衡模型，并且 讨论了对该模型的四类基础刻画，以及几种对时问费用均衡关系讨论的新的想 泫t 2 1 1 。z h e n g 和n g 通过结合模糊集理论和某种特殊的遗传算法提出了一种新的 方法，其中模糊集理论被用来模拟决策者对子项目时间和费用的预测以及相应 的风险等级1 2 2 。z a h r a i e 和t a v a k o l a n 将时问费用均衡和资源分级配置的概念结 4 第1 章引言 合起来提出了时间费用资源均衡问题，设计了一个随机多目标规划模型【2 3 1 。k e 等根据现实不同的优化要求，设计了三类随机的时间费用均衡模型【2 4 1 。 但是实际上，不确定性并不能单单以随机性来刻画。比如两个城市之间距 离的估计，人的高矮胖瘦等都不能以随机性来描述。在这种情况下，带有主观 性的不确定性往往由模糊性来刻画。模糊集的概念最早是由z a d e h 于1 9 6 5 年提 出的【5 1 。此后，模糊集理论逐渐成为解决实际问题中不确定性的一种新的有效 的办法，而很多学者对模糊集的发展作m 了贡献。1 9 7 5 年，k a u f m a n n 提出了 模糊变量的概念【2 5 1 。随后在1 9 7 8 年z a d e h 引入了可能性理论 2 6 1 。n a h m i a s 用三 条公理定义了可能性测度，并且重新定义了模糊变量的概念，把模糊变量定 义为可能性空间上的实函数【2 刀。而最近，l i u 通过定义乘积可能性测度给出了 第四条公理【2 8 1 。并且l i u 在加上原有的三条公理形成的四条公理的基础上，成 功地建立起了可信性测度的公理化体系【2 9 1 。模糊集的发展和可信性测度的公 理化体系的建立，给我们在现实中应用并且解决模糊环境下很多的现实问题 提供了有效的支持。同样地，在工程进度优化问题中，如果子项目的历史数 据比较齐全，当然可以通过统计的方法给出子项目执行时问的概率分布，从 而以随机变量对其进行刻画；而当7 项目的历史数据缺失或者不足的时候， 子项目的执行时问往往不合适以随机变量来表示时，我们可以通过专家建议 的方式，以模糊变量对其进行刻画。这样，我们就可以引入模糊集的相关理 论来对该优化问题进行研究。1 9 7 9 年，p r a d e 第一次将模糊集理论引入到工程 进度优化问题中，开始了对模糊环境下工程进度优化理论和应用的研，究【6 1 。随 后，d u b i o s 和p r a d e 等将扩展原理应用n f o r d 算法中来研究模糊情况下的工程 进度优化问题【3 0 ，3 1 1 。随后，更多的学者对模糊情况下的工程进度优化问题进行 了研究【3 埘1 。最近这些年米，该问题的研究重点集中在有资源约束条件下的工 程进度优化问题 3 5 - - 3 7 。w a n g 将模糊集理论应用于不精确信息环境下的产品开 放工程问题中【3 8 ，3 9 1 。在w a n g 的文章中，二l 程有一个模糊的等待时问、期限时 间以及模糊的执行时间，这些都以梯形模糊数来表示。h 标则是为每一个子项 目确定一个开始执行时间，使得模糊等待时问约束、期限时间约束和资源约束 都能够满足。h a p k e 和s l o w i n s k i 将模拟退火算法应用到资源约束下的多目标t 程进度优化问题中1 4 0 。0 z d a m a r 和a l a n y a 针对模糊环境卜的软件开发工程建立 了+ 个非线性混合_ 元数学模犁，在文章中分别针对4 种模糊优先准则进行了分 5 第1 章引言 槲4 1 1 。l o n g 和o h s a t o 针对有资源约束的工程进度优化问题设计了一个模糊关键 链方法【4 2 1 。 第一个在模糊时间费用均衡问题的研究上作出贡献的是l e u 等f 4 3 1 。 在【4 3 】中，l e u 等将模糊集理论引入到时间费用均衡问题中，他们假设工程 子项目的执行时间是模糊数，并且以隶属度函数来描述子项日执行时间和相应 费用的模糊关系。进一步地，他们将机会约束规划的思想1 4 4 引入到问题中来刻 画风险等级。j i n 等建立了+ 一个以遗传算法为基础的全模糊优化时间费用均衡问 题，问题中的参数和变量都i f i 模糊数来刻画，并且将设计的模型应用到了一个 船厂建设规划问题中 4 5 1 。e s h t e h a r d i a n 等将模糊逻辑理论引入来表达可接受的风 险程度，从而建立了一个多e l 标模糊时问费用均衡模型【4 6 1 。g h a z a n f a r i 等将可 能性目标规划引入到时问费用均衡问题中【4 7 ，4 引。在目前已有的模糊时间费用均 衡问题中，模糊现象都是以模糊集理论来刻画的，其基础是可能性测度。而实 际上，可能性测度有一个很大的缺陷，就是不具备自对偶性。这就意味着哪怕 一件模糊事件的可能性是1 ，它实现不了的可能性也有可能为1 。这样的一种测 度应用到现实问题中是有缺陷的。而且，自对偶的性质对于定义一个事件的期 望值是必要的，而我们无法通过可能性测度的角度来定义一个事件的期望值， 这就造成了在实际应用上的不足。这些不足我们将通过引入【2 9 】介绍的可信性 理论来弥补。 在2 0 0 4 年的著作中l i u 系统地阐述了不确定性理论的研究内容，把不确定 性理论分为i 类基本的理论部分【2 9 】。这j 类基本的研究不确定性的理论分别是 概率论，可信性理论以及信赖性理论( 基于p a w l a k 提出的粗糙集概念f 4 9 ，5 0 】) 。 在这三类基本理论的基础上还衍生出了双重不确定性理论等其他的相关理论。 而l i u 义把不确定性理论引入到数学规划中并且与之相结合，产生了不确定规 划【5 1 5 2 。彳i 确定性理论的发展与完善以及4 i 确定规划的提出为我们解决彳i 确定 环境下的时间费用均衡问题提供了理论基础和新的解决问题的思路和方法。此 外，求解复杂和大型的优化问题，尤其是含有不确定件的复杂优化问题，往往 不能以传统的算法来解决。而启发式智能算法的提出和不断发展很好地弥补了 传统方法对解这一人类问题的彳i 足。遗传算法、神经元网络、禁忌搜索、模拟 退火等都属于启发式智能算法的范畴，它们都能够很好地解决这些更复杂的问 6 第l 章引言 题。在本文中，我们将应用不确定规划的丰富思想对时间费用均衡问题进行建 模，并结合对不确定函数的模拟和遗传算法设计出混合智能算法求解。 1 3 本文的结构安排 本文将主要研究不确定环境( 包括随机、模糊和模糊随机等) 巾时间费用 均衡问题的优化模型的建立以及相应混合智能算法的设计与求解。文章的结构 安排如下： 第二章我们对不确定环境下的时间费用均衡问题给出了些基本假设，进 行了问题的描述和相关公式的推导。随后我们分别研究了随机、模糊和模糊随 机情况下的各类决策准则。 第三章针对一个随机环境下的时间费用均衡问题，我们根据不同决策准则 建立了两类随机的时间费用均衡模型。为了求解这些模型，我们引入了随机模 拟的方法和遗传算法，进而设计了混合智能算法来求解这些模型。最后，我们 给出几个数值例子来说明了算法对求解这些模型是有效和稳定的。 第四章研究一个模糊环境下的时间费用均衡问题，针对模糊时间费用均衡 模型的欠缺，我们用三个不同的模糊模型来体现不同的建模思想，以满足不同 优化要求的需要。随后设计了结合模糊模拟和遗传算法的混合智能算法来求解 问题。最后，对于这个混合智能算法的有效性，我们通过数值实验进行了验 证。 第五章针对之前没有学者研究过的随机与模糊同时存在的混合不确定环境 下的时间费用均衡问题，我们引入模糊随机规划的思想，建立了三类模糊随机 时间费用均衡模型。随后我们将模糊随机模拟嵌入遗传算法设计了混合智能算 法来求解这些模糊随机模型。最后我们通过数值实验来说明上述设计的算法是 有效和稳定的。 第六章我们进一步扩展不确定环境的涵义。我们分别引入混合规划和不确 定规划( 这里的“不确定”特指某。类测度，而不是泛指的不确定性) 的思 想，分别介绍了在这两类不确定环境下的时间费用均衡模型，并对混合环境下 的时间费用均衡模型设计了智能算法。 7 第1 章引言 在结论部分我们对文章的工作进行了总结，简要的介绍了本论文的一些创 新点，并对下一步可以继续开展的工作进行了展望。 8 第2 章时间费用均衡问题及不确定环境中的决策准则 第2 章时间费用均衡问题及不确定环境中的决策准则 在各类工程中，往往存在着两类消耗，分别是时间消耗和费用( 资源) 消 耗，而且在现实中这两类消耗往往是有限制的。在各类工程问题中，如何在这 两类耗费有限的限制下达到优化目标是跟现实密切相关的一类决策问题。时间 费用均衡问题就是一类解决在时问约束或者资源( 费用) 约束条件下优化目标 的优化问题。时间费用均衡问题在2 0 世纪6 0 年代初提出来以后得到了迅速的发 展，确定环境、随机环境和模糊环境下的情况都有了进展。本报告将对不确定 环境下的有时间约束条件的时间费用均衡问题进行研究，根据不同优化要求建 立模型并设计求解模型的算法。在此之前，我们将首先对时间费用均衡问题进 行描述，根据，。些基本假设和条件推出工程完工时间的公式和工程总费用的公 式，并根据决策需要，给出几类不确定环境下的决策准则，为进一步的建模和 算法设计做好准备。 2 1 时间费用均衡问题简述 通常来说，一个工程可以由一个如图2 1 所示的简单有向联通图来表示。在 工程进度优化问题中，通常对工程的网络结构有两种表示方式，分别是以弧代 表子项目的方式( a c t i v i t y o n t h e a l e ) 和以顶点代表子项日的方式( a c t i v i t y o n t h e n o d e ) 。在本文对时问费用均衡问题的研究中，我们采用相对简单的以弧代 表子项目的方式来进行研究。令g = ( va ) 是一个代表工程的有向联通图，其 中v = 1 ，2 ，礼+ l 】是代表单程碑( 决策点) 的顶点集，a 是代表工程中所 有子项日的弧集，而( i ，) a 代表一条从顶点i 到顶点j 的弧。 我们知道，由于外部环境的不确定性，一个工程的各子项目的执行时问总 是不确定的，从而整个工程的完工时间也存在不确定性。为了能够保证工程在 预期的时间内完工，我们经常需要对工程的某些甚至全部子项目进行调整，这 种情况在我们现实中经常能够遇到。而很多时候管理者在调整子项目的执行时 间的时候往往会伴随着成木的增加或者减少，于是，如何合理调整子项目的执 行时间，使得工程能够保证在预期的时间内完工，同时又能够尽可能地减少成 9 第2 章时间费用均衡问题及不确定环境中的决策准则 图2 1工程示意图 本的增加，就必然是管理者需要面对的一个难题。时问费用均衡问题就是为了 帮助管理者达到工程完工时间和整体费用的均衡而进行的研究。 我们假设子项目( i ，j ) 的正常执行时间是一个不确定变量岛，也就是说白代 表子项目( i ，j ) 在没有管理者的决策影响下的执行时问。在现实工程中，岛的 不确定性来源于外部环境的不确定性，例如天气的影响，生产率的高低等。 相应地，我们假设孑项目( i ，j ) 每天的正常执行费用为g j ，在这里我们假设q f 是一个常数。决策变量x j 表示由于管理者的决策而造成的子项目( i ，j ) 执行 时问的变化，比如由于多招募了一些工人或者启用了更好的设备等决策所造 成的完工时间上的变化。为了简单起见，我们假设决策变量而j 是一个整数； 并且为了更加符合实际，我们假设决策变量耽j 在区间，砒j 】内变化，其中如， 和讹i 也假设足常数。相应地，对每个子项目( i ，j ) 来说，由于管理者的决策而 存在另外的一个相关的费用，我们记为以j 。它代表觑f 每单位变化所产生的额 外费用，也假设为是一个常量。在有了这些参数以后，我们所要研究的时问 费用均衡问题，即是为了取得t 程完t 时间和整体费用的均衡，而决定最佳 的z = z 巧：( i ，j ) a ) 。 我们将所有子项目的正常执行时间简写为专= 毛，：( i ，j ) a ) 。子项 目( i ，j ) 的丌始时间记为互j ( 茁，) ，而为了简单我们假设整个丁程的开_ t 时间 为0 ，即我们假设子项目( 1 ，j ) a 的开始时间为m 1 j ( z ，) = 0 。另外，我们假 设每个子项目只有存所有它之前的子项目都完成以后才能开始执行，并月 1 0