（管理科学与工程专业论文）基于目标规划理论的电源规划方法研究.pdf

华北电力大学 ( 北京) 硕士学位论文摘要 摘要 目标规划己经成为解决现代化多目标管理决策问题的有效工具。它同样 能够在电源规划中得到很好的应用。 本文在线性规划模型的基础上论述了电源规划的目 标规划模型。论文正 文共分为四章。 第一章论述了目 标规划的研究意义、 研究现状及其应用前景。 第二章论述了目标规划的特点、原理和建模步骤。第三章论述了目标规划的 求解，主要讨论了目 标规划的多阶段单纯形解法和遗传算法解法。第四章论 述了电源规划的目标规划模型及其解法，并给出了实例分析。电源规划的目 标规划模型具有实用价值。结论中给出了本文的创新和不足之处。 关键词 :电 源规划，目 标规划， 单纯形法， 遗传算法 abs tract g o a l p r o g r a m h a s b e c o m e o n e o f t h e m o s t e f f e c t i v e i n s t r u m e n t i n h a n d l i n g t h e m u l t i - g o a l d e c i s i o n - m a k i n g p r o b l e m o f m o d e r n a d m i n i s t r a t i o n . i t c a n a l s o b e w e l l u s e d i n p o w e r g e n e r a t i o n e x p a n s i o n p l a n n i n g t h e p u r p o s e o f t h e d i s s e r t a t i o n i s t o d i s c u s s t h e g o a l p r o g r a m m i n g m o d e l s a n d i t s a p p l i c a t i o n i n e l e c t r i c p o w e r p l a n . t h e d i s s e r t a t i o n c a n b e d i v i d e d i n t o s i x p a r t s . p a r t o n e s u m m a r i z e s t h e m a i n c o n t e n t o f t h i s a r t i c l e . p a r t t w o i n t r o d u c e s t h e r e s e a r c h m e a n i n g o f g o a l p r o g r a m m i n g a n d i t s a p p l i c a t i o n . p a r t t h r e e r a i s e s t h e p r i n c i p a l s a n d f e a t u r e s o f g o a l p r o g r a m m i n g a n d d e t a i l e d i n t r o d u c t i o n h a s a l s o b e e n g i v e n t o t h e p r o c e s s o f e s t a b l i s h i n g t h e g o a l p r o g r a m m o d e l s . p a r t f o u r a n a l y z e s t h e s i m p l e x a l g o r i t h m o f t h e g o a l p r o g r a m m o d e l s a n d t h e g e n e t i c a l g o r i t h m . p a r t f i v e a n a l y z e s t h a t h o w t o u s e g o a l p r o g r a m m i n g m o d e l i n e n e r g y p o w e r p l a n a n d t h a t h o w t o g e t t h e r e s u l t s . i n a d d i t i o n m a t h e m a t i c a l m o d e l s a r e a l s o e s t a b l i s h e d t o c o n d u c t c a s e s t u d y i n a t t e m p t t o o b t a i n s o m e i n s t r u c t i v e a n d e a s i l y o p e r a b l e r e s u l t s a n d c o n c l u s i o n s .p a r t s i x i s t h e c o n c l u s i o n . i n n o v a t i o n s a n d d e fi c i e n c i e s i n d i s s e r t a t i o n a r e g i v e n i n c o n c l u s i o n we i b e n n i n g ( m a n a g e me n t sci ence a n d e n g i n e e r i n g ) d i r e c t e d b y p r o f . z h a n g wc n q u a n k e y w o r d s : p o w e r g e n e r a t i o n e x p a n s i o n p l a n , s i mp l e x a l g o r i t h m , g o a l p r o g r ammi n g ， g e n e t i c a l g o r i t h m 华北电力大学 ( 北京)硕士学位论文 基于目标规划理论的电源规划方法研究 月 u舌 决策的目标随着决策的性质、类型、管理者的哲学观念，特别是随着决策所处 的环境条件而变化，决策往往不可能存在一个单一的目标，而是一系列的多目标决 策问题，目 标规划就是多目 标决策方法的一种，由于它的模型比较符合现代管理决 策的实际， 方法灵活， 有能力处理各种没有统一度量单位、 互相冲突的多目 标问 题， 而且实际应用便于利用电子计算机技术，所以目标规划已经成为解决现代管理规划 中多目 标决策的有效工具。本文针对电力系统中，电源规划这种大型复杂系统的决 策问题， 建立电源规划的目标规划模型， 并给出了问题的解法。 本文正文共分四章， 第一章是目 标规划的研究现状以及综述;第二章是分析了目标规划的原理、目标规 划的特点以及目 标规划的建模步骤;第三章是目标规划的算法，主要讨论了目标规 划的多阶段单纯形法和遗传算法以及目 标规划的求解算法在寻优上的实用性;第四 章是电源规划的目 标规划模型的应用研究，讨论了电 源规划研究的现状，建立了电 源规划的目 标规划模型，并给出了实际算例及其分析。 第 i 页 华北电力大学 ( 北京)硕士学位论文 第一章目标规划概述 1 . 1 目 标规划的研究意义 随着，人们对决策现象研究的深入，线性规划的在一些大型复杂方面呈现出了 许多局限性。人们所面对的往往是多个目 标函数，不同的优先级别，甚至目 标函数 之间存在着一定的关联性与矛盾，在处理这类问题时，往往是以丧失一定的准确性 为代价的。在处理问题的约束时，有时由于硬约束的限制，缺乏必要的灵活性，导 致不存在最优解。再者，决策变量众多，量刚不一，勉强同一化时，降低了解的有 效性。现代决策分析的主要困难就在于处理互相矛盾的多个目标。为此人们在克服 线性规划模型局限性的基础上，提出了目 标规划的方法。 目 标规划预先有一组给定的目 标值，在有限的资源约束条件下，这组目标值也 许能够达到，也许不能达到，决策者尽量合理安排有限资源，使决策结果尽可能地 接近这组预定地目 标值，使决策结果与目 标值的总偏差最小，克服了线性规划有时 无解的局限性。 在大系统中，系统具有复杂性、规模大、混合性、随机性等特点，决策复杂。 尤其象电力系统这样的大系统，研究其规划时，采用抽象化问题，研究其数学上的 决策结果，可以带来巨大的经济效益，利用目标规划来研究电力规划优化的问题具 有重要的理论与实践意义。 1 . 2 目 标规划的研究现状 1 . 2 . 1目标规划的提出和发展历史 目 标规 划首先是在1 9 6 1 年由 查 尔斯( c h a r n e s ) 和库帕( c o o p e r ) 在其著的 管 理模型与线性规划的工业应用 中提出的。 伊杰瑞 ( y i j i r i ) 深入的研究了 查尔斯和 库帕提出的目 标规划的概念，给出了目 标规划的优先等级和优先权因子的概念，并 且还给出了目 标规划的广义逆求解算法。1 9 6 8 年康蒂尼 ( b . c o n t i n i )研究了不确定 性条件下的目 标规划方法。他的研究从数学上提供了把随机方法用到目 标规划的可 能性。 l e e 在其著的 1 9 7 2 年出版的 决策分析用的目标规划一书中介绍了目标规 划的基本概念、解法及其在生产计划、财务决策、市场决策、公司计划、学院计划、 政 府决 策、 医 疗 保 健计划等多 方面的 应用 t ll , i g n i z i 。 在 目 标规 划及其 扩展中， 将目 标规划的应用扩展到整数规划及非线规划领域，给出了目 标规划的对偶求解算 第 2 页 华北电力大学 ( 北京)硕士学位论文 法 和其它一 些效率较高的 求解算法12 1 . s c h n i e d e rj a n s 在其 线性目 标规划中 详细 讨论了目 标规划的应用。i g n i z i o 和c a v a l i e r 在 线性规划一书中 对目 标规划及其 向 人工智能领域的扩展进行了阐述。 1 9 9 6 年5 月在西班牙召开的第二届多目 标规划 与目标规划理论与应用国际会议上，提出了一些在理论和应用方面的新进展，其内 容包括在克服决策变量的量纲不一致性、启发式搜索解法、动态目标规划以及在股 票市场、配送系统设计、投票行为、模糊估计等方面的应用。 随着一些新的算法的引入， 同时也能把一些变量的模糊性、 随机性的表达出来， 进而建立了模糊规划和随机规划的模型，并在实际应用中取得一定的进展。 l i u提 出了相关机会规划并推广到了相关机会多目 标规划和相关机会目 标规划，使事件的 机 会函 数 在不 确定 条 件下达到 最大 值。 u 1 l u h a n d j u l a 对模 糊规划作了 总结， 在 模 糊 环境中，假定模糊约束条件成立的可能性不小于置信水平，得到了模糊机会约束规 划。考虑了模糊线性规划以及模糊多目 标线性规划问题，根据z a d e h 提出的可能性 理论，提出了一系列把机会约束规划转为清晰等价类的思想，给出了模糊相关机会 规划。 a l 邓聚龙、刘思峰等给出了基于灰色理论的灰色规划模型， 在目 标函数和约 束中含有灰色信息。 5 ， 王清印研究了基于u数的u数线性规划， 把信息分为确定性 信息和不确定性信息， 不确定信息包含随机信息、 模糊信息、 灰色信息和未知信息， 把含有上述信息的变量定义为 u数， 。并且分析了 模型的解法，对研究目 标规划带 来了 新的思 考。 6 ， 1 . 2 . 2目标规划的基本要点 目 标规划就是一种多目 标规划技术， 处理带有多个子目标的单目标决策问题， 针对线性规划的局限性提出来的。既能够 也能处理带有多个子目标的多目标决策问 题。基本思想来源于西蒙的目 标满意概念。每一个目 标都有一个要达到的目 标值， 然后使距离这些目 标值的偏差最小化。基本要点主要如下: i )每一个约束条件中引入正负偏差变量，把硬约束 变为软约束。 在目 标规划的 每 个约束条件都引入了相应的正负偏差变量，这就使得线性规划的硬约束变成软 约束，大大增加了求得可行解的机会。 2 )距离各个目 标值的偏差总和最小作为目 标函数。目 标规划将线性规划的中各个 约束条件的右端值约束项变为目标值，而将距离各个目标值的偏差总和最小作 为目标函数，因而目标函数只包含偏差变量，由于每个目标最多只有两个偏差 变量，且目 标数要比决策变量数少的多，所以非常便于处理多目标决策问题。 3 )用划分优先级的方法来处理多个目 标的 相对重要性， 更好适用决策者的判断。 目标规划用划分优先级的方法来处理多个目标的相对重要性，更好适用决策者 定性判断。此外，用划分优先级的方法还可以减少决策变虽之间的量纲不一致 第 3 页 华北电力大学 ( 北京)硕士学位论文 j性问题的发生。 4 )通过变量定界的方法来解决多解问题。在目 标规划中决策变量的数目 往往大大 超过目 标的数目，也常常大于约束条件的数目，求解时易产生多解问题。目标 规划可要求决策者对偏差变量定界，即定出其允许变动的范围，从而可以通过 灵敏度分析来解决多解问题。 1 . 2 . 3目标规划的应用前景 目标规划根据待处理的具体问题，可以从以下几个方面得到不断的发展和完 善。 1 )针对实际问 题发展目 标规划的建模方法。在线性目 标规划日益完善的情况下， 根据实际问题的特点，对非线性规划、整数目标规划 ( 包括全整数、混合整数、 0 -1 规划、 非线性等整数目 标规划) 、 动态目 标规划、 随机目 标划、 模糊目 标规 划、交互作用的目 标规划的模型继续发展完善。 还要进一步解决量纲不一致性、 p a r e t o 效率解，以及优先级过多引起的重复问题等。 2 )改进大型目 标规划的算法。对待单纯形算法，需要发展大型稀疏矩阵的压缩方 法，采用分解或降阶等方法来处理基矩阵的逆矩阵。对待复杂的非线性目 标规 划，发展现代优化算法、启发式算法等取得全局最优解。 3 )开发大型目 标规划问题的实用软件包。 目标规划的广泛应用，离不开实用的目 标规划软件包。它应当具有运算快速、 输入方便、用途广泛、结果直观、易于掌握等特点。 第 a页 华北电力大学 ( 北京)硕士学位论文 第二章目标规划的原理和建模 2 .飞 目 标规划的原理 目 标规划是线性规划的 扩展， 目 标规划首先由 查尔斯( c h a r n e s ) 和库帕( c o o p e r ) 根据不可 解线性规划提出。 以 后在他们的 基础上ij i r i 和i g n i z i 。 等继续研究， 定 义了 处理了多目标的 “ 优先级因子”和同一优先级内各目标的 “ 权， ，并且提出了广义 的“ 逆矩阵” 的算法等， 把目标规划发展成了一个不同于线性规划的数学规划方法。 目标规划主要基于原理如下: 1 .系统性原理 目 标规划强调系统内部各部分之间的相互联系和作用，及由此表现出来的 宏观性质。 分析系统内部各种定量的数据， 各种约束条件的互相之间的依赖性。 从个体之间发现整体的行为和性质，得出全局性的结论。从全局中，考虑变量 的发展，动态之中发现平衡之中的最优，而非静态、机械的现象。 2 .定性分析与定量分析相结合的原理 分析经济现象时，采用量化的数据。获的数据有时采用的是决策者主观分 析数据。在模糊条件下，得到的最优结果，仍需要决策者的主观判断。因而日 标规划结合了定性分析与定量分析。 3 .确定性与随机性互容原理 在一个决定性的系统中可以出现类似于随机的行为过程，是系统内在随机 性 的 一 种 表 现 。 确 定 性 的 规 则 下 面 ， 产 生 不 可 确 定 的 随 机 性 。 我 们 用 确 定 的 函 数来模拟包含有随机性、模糊性、灰色性、未确知性的现象，使确定性与随机 性相容。这也是由经济系统的复杂性所决定的。 2 .2 目 标规划的特点 目 标规划由 线性规划发展而来，它有如下特点: i 目 标规划建立在线性规划的基础上，一些研究线性规划的方法仍可以用在目 标 规划上。例如线性规划中分析灵敏度问题、对偶问题、整数规划问题的方法等 都可借鉴而来. 2 、把硬约束变成软约束来处理，避免了线性规划中的 “ 无可行解”情况，增大了 求可行解的机会。 第 5页 华北电力大学 北京) 硕士学位论文 3 用划分优先级的方法来处理多个目 标的相对重要性，能更好的适应决策者的定 性判断。减少了决策变量之间的量纲不一致问题的发生。 4 ， 目 标规划的研究对象是一般的多目 标决策问题。无论问题是线性的还是非线性 的，变量是连续的还是离散的，它都具有广泛的适应性。 2 . 3 目 标规划的建模 虽然人们根据习惯和经验的不同，目标规划的建模步骤会有不同。但针对一个 实际问题构造一个目标规划模型的步骤基本上可以归结为: 1明确问题。提出问题并限定问题，分析研究对象有关的各种主要因素，并确 定系统的时间空间范围。 z .分析现状。全面、深入地、动态地分析研究对象的现状是解决问题的先决条 件。在分析现状时，既要求有全面的统计分析，又要求有深入的案例研究， 还要动态的发展预测，这三者密切联系、相辅相成。 3建立目 标体系。 建立目 标体系就是明确问题的标的， 是目标规划建模的关键， 既要考虑决策者的意愿， 又要考虑实际的可能 ( 资源约束) 。 多目 标决策有k 个目 标f , ( x ) , ( 1 5 i 5 k ) ， 其中 包括目 标函 数和资 源约束。目 标规划的硬约束是 指必须严格满足的等式约束和不等式约束，如线性规划中所有的约束条件， 不能满足它们时则无可行解。目 标规划的软约束是指，当把约束右端项看作 要追求的目 标值。在达到此目 标时允许发生的正、负偏差变量，它们是软约 束。线性规划问题的目标函数，在给定目标值和加入偏差变量后可变换为软 约束。 资源约束 ( 硬约束)为: 个 ，h , ( x ) ? 4 ( 1 5 x !5; s ) ; 4 。确定决策变量。决策变量是目 标规划中应当为决策者提供数值解答的变量， 它们是决 策者希望能 够加以 控制的 变量。 决策变量x = ( x i , x 2 , . . . x ) t e r ( n 维 欧氏空间) 。 5 ，确定每个目 标的表达式。 确定每一目 标的期望值 ( 和硬约束的右端值) ， 把每 一目标函数和硬约束都加上正、负偏差变量，写成目标表达式。 ( 1 ) 偏差变量心和盯e r , ( m维欧氏 空间)( 1 _ i 5 m ) ; d , 为正偏差变量，表示第i 个约束的超额量， 才为负偏差变量， 表示第i 个约束的不 足量。 要求d ,* . d = 0 ，即每一对d , 和盯中 必须有一个至少为。 。 ( 2 ) 目 标期望值:扩= ( 9 1 1 9 2 , . . . 9 k ) ; 当每一目标值确定后， 决策者的要求是尽量缩小偏离目 标的值， 目 标函数( 达 成函 数) 只能是m i n z = f ( d * , d ) ， 其基 本形式有三种: 第 6页 华北电力大学 ( 北京)硕士学位论文 要求达到目标值，即正、负偏差变量都要尽可能小，这时 m in z = f ( d + + d - ) ( 2 -1 ) 要求不超过目 标值，即允许达不到目 标值，就是正偏差变量尽可能小， 此 时 m i n z = f ( d ) ( 2 一2 ) 要求超过目标值，即超过量不限，但必须使负偏差变量尽可能小，这时 m i n z = f ( d 一 ) ( 2 -3 ) 希望k个日标都达到预定目标值。用软约束表示为: 关 ( x ) + d ; 一 可 = g ; ( 1 - i _ k ) ( 2 一4 ) 硬约束 ( 资源约束)变为软约束: h , ( x ) + 才一 才= 0 ( 1 5 i 5 s ) ( 2 一s ) 把两类约束累加，则共有m ( s + k = m ) 个约束条件，可以表示为: g , ( x ) + d , - d ; = g , ( 1 !- i e m ) ( 2 - - 6 ) 根据问题的要求，按照目标的重要性赋予各目 标相应的优先级，第一和 高优先级赋予硬约束;在同一级目标内根据问题要求和重要性选择相应偏差 变量并赋予相应权数。组合各优先级的目标建立 目标函数。 6 .确定每个目 标表达式中的参数。要根据具体问题，来确定函数表达式。系数 的确定要经过一定的分析和计算，为此甚至还要建立一些操作模型，以便通 过处理大量原始数据来确定目 标规划模型中的参数。 7 .确定其它约束条件。其它约束条件主要包括决策变量的上、下界，即允许决 策变量取值的范围。决策变量的上、下界应当通过对其要求及决策变量的可 能来确定，其下界通常至少要大于零。有时还包括偏差变量的上、下界以及 一些平衡算式。 8 .确定总目 标表达式 1 )设置目 标的优先级。 决策者有k 个目 标， 根据目 标轻重缓急不同分成l ( 1 p r+ , , t = 1 ,2 ,3 . ., l 。 表示p e 比p r. ; 有更高的 优先级。 如果问 题中 有必 须满足的资 源约束， 我们人为的 引进一 个最高 级别的p o ， 应该 在目 标 函 数中出 现的资源约束的 偏差变量， 赋予p 。 优先级。 我们在先满足资 源约束的 条件下，再考虑目标约束。高层次的目 标要比低层次的目 标重要的多，只有高 层次的目 标得到满足之后，才能考虑低层次的日 标。如果发现高层次目 标与低 第 7 页 华北电力大学 ( 北京)硕士学位论文 层次目标发生矛盾时，低层次目标就可能得不到满足。 2 )设置权重。第 1 优先级p r ( 1 _ 1 !5 l ) 中，根据几个目 标的重要性不同， 我们给它 赋予不同的权因子。 j 和听 ，其中1 _ i _ k , l _ 1 _ l 。如果某个权因子为 0 ，则表 示偏差变量在该层目标中不出现。第1 层次的目标函数为: g r ( d - , d - ) = 艺( u ;r d ; + u d . ) ( 1 1 l )( 2 一7 ) d d- g p 1艺0 整个日标规划的目标函数为 mi n z = ( 2 一8 ) 综上所述可得目标规划模型为 m mz 二 二艺p r g r ( d 一 ， d + ) g , ( x ) + d l - 一 d 广 = g r ( 1 s z (、 一 ，、 ) ，二 。 * (、 一 ，d ) s f厂 ( x ) + d l- 一 d 厂 = b ，i = 1 , 2 , . . . m x e c , ( 2 一1 1 ) 式中，k为优先级数，a 为k个优先级的有序向量。 对于赋权重的目标规划，权重需要根据经验对不同的目标加上不同的权重。也 可以应用专家评分法和层次分析法 ( a h p )等方法来确定。 第 9 页 华北电力大学 ( 北京)硕士学位论文 第三章目标规划的算法 对于线性目标规划，一般采用单纯形法求解。对于非线性目标规划，一般采用 近似为线性目标规划的方法，或者采用一些启发式优化算法来求解，包括禁忌搜索 算法、模拟退火算法、遗传算法、神经网络算法和拉格朗日松弛算法等。对于大型 系统而言，由于实际求解的困难，大多采用线性目 标规划方法。本文主要论述目标 规划的多阶段单纯形解法和遗传算法解法。 3 . 1 3. 1 . 1 多阶段单纯形法算法 多阶段单纯形法算法的步骤 多阶段单纯形法求解目 标规划的步骤为: ( 1 ) 建立目 标规划模型的初始表。 先假定初始解在原点，模型约束中所有的负偏差变量都进入初始基。表中 基变量为构成单位系数矩阵的列向量 ( 一般为负偏差变量) ;各阶段的目标函 数系数则是把目 标函数中各级目标的偏差变量的权系数，做旋转变换把对应的 基变量列的系数变为0 的结果。令k = 1 ，转向 ( 2 ) 0 在多阶段单纯形表中，检验数行是按优先级顺序排列的多级目标函数行。 行 系 数 、 ( k = 1 ,2 , . . ., k ; j = 1 ,2 , . . ., n + 2 m ) 为 各目 标 函 数 的 检 验 数( tkl = c k/ - z kj ) o 这 些 行 在 起 始 表中 的 数 据( c ki ) 是 相 应 变 量( 包 括 偏 差 变 量 在 达 成 函 数 中 的 权 系 数)作旋转变换后的值即首先把这些行中对应基变量列的各系数变为零后的数 值。 多阶段单纯形表如表3 一卜 第 1 0 页 华北电力大学( 北京) 硕士学位论文 第三章目标规划的算法 对于线性目标规划，一般采用单纯形法求解。对于非线性目标规划，一般采用 近似为线性目标规划的方法，或者采用一些启发式优化算法来求解，包括禁忌搜索 算法、模拟退火算法、遗传算法、神经网络算法和拉格朗曰松弛算法等。对于大型 系统而言，由于实际求解的困难，大多采用线性目标规划方法。本文主要论述目标 规划的多阶段单纯形解法和遗传算法解法。 3 1 多阶段单纯形法算法 3 1 1 多阶段单纯形法算法的步骤 多阶段单纯形法求解目标规划的步骤为： ( 1 ) 建立目标规划模型的初始表。 先假定初始解在原点，模型约束中所有的负偏差变量都进入初始基。表中 基变量为构成单位系数矩阵的列向量( 一般为负偏差变量) ；各阶段的目标函 数系数则是把目标函数中各级目标的偏差变量的权系数，做旋转变换把对应的 基变量列的系数变为0 的结果。令k = l ，转向( 2 ) 。 在多阶段单纯形表中，检验数行是按优先级顺序排列的多级目标函数行。 行系数( | 】 = 1 , 2 ，k ；j = 1 , 2 ，肝+ 2 m ) 为各目标函数的检验数( = c w 一) 。 这些行在起始表中的数据( c 。) 是相应变量( 包括偏差变量在达成函数中的权系 数) 作旋转变换后的值即首先把这些行中对应基变量列的各系数变为零后的数 值。 多阶段单纯形表如表3 1 ： 第1 0 页 华北电力大学( 北京) 硕士学位论文 表3 1 多阶段单纯形表 一 基变鬣 x 1x i x ，d ；- - d i d ：一d ：b 一 x b l y ny 1 2 弘” y 1 肿1 y i ，肿m_ y 1 ，h + “y l + 月+ 2 m b l ； ： ；!i! ； i 一 x b c n b 。 y m ly m 2 y 删 y m 十i y m “+ y ，+ 1 y m ，月+ 2 一群l l 2 一i + n + 1 。 一i ，一1 一2 一拄l ： ： 一吼 一吼 磊l壤2 稳肿 如卅m 咚，肿m + 1+ 珞，2 ( 2 ) 考察阶段k 的检验数孳亍中所有负元素，且该列中级别较鼗元素没有大予零鲍， 翳该受元素所瑟应戆掰褥作为换入蕊列考虑。濑择这释受元素中豹最小麓耀废豹 非基变量为入基变量( 相应的列为枢列) 。如果有两个以上遮样的最小负元素则 可任选。转入( 3 ) ，如果没有这种负元素的存穗，则转入( 5 ) 。 ( 3 ) 把对应援舞孛大予零懿系数除摆疲行黪右边露羧，取这个舞最枣者对疲魏行蔻 枢行，褶殿的基变量为出基变量，这个系数为椴元素。如聚商有相等的，则选其 中在目标函数中优先级别较高的行为枢行，转入( 4 ) 。 ( 4 ) 按所选枢元素为轴心作旋转变换，把枢元素变为l ，枢列审的其它元豢变先零， 露天蒸交爨取代疆露率鼢出基交量，转入( 2 ) 。 ( 5 ) 如果k = k ，则当前解为最优解，停止计算，否则k = k + l ，转向( 2 ) 。 嚣禄簸麓的多酚袋繁纯形法诗辫如框国3 一l 所示： 攘1 1 菱 华北电力大学( 北京) 硕士学位论文 图3 1 多阶段单纯形法计算流程图 华北电力大学 ( 北京)硕士学位论文 3 .1 . 2关于多阶段单纯形法的讨论分析 不可行解、无界解和不可接受解。当线性目 标规划含有硬约束条件时，如 果任何一个硬约束条件未能满足 ( 相应的第 i 级目 标函数值未能满足) ，问 题会出现不可接受解。这时必须放松一个或几个硬约束条件，来得到可接 受解。 多最优解。 如果两个以上的解的目 标函数值都相同， 则问题具有多最优解。 单纯形法的多最优解的存在情形可由最终表中各级目标函数行中相应于非 基变量的 检验数r j 的整列元素是否为零 来判断。 起始可行基。起始基可行解起始于多阶段单纯形表的目标和约束系数矩阵 中对应的单位矩阵的那一组变量，一般为一组负偏差变量。然而在有的问 题中某些目 标的负偏差变量必须为零，因而不必引入负偏差变量，这时人 为构成一组起始基可行解，可对每一个这种目标引入一个人工变量，并引 进一个令所有人工变量之和为零的等式作为一个硬约束，并在目标函数中 也增加一个具有最高优先级的人工变量之和的目 标函数行。如果该最高目 标函数最优化后的数值为零，则问题存在最优解，转入下一目标计算;否 则问题的解不可接受，停止计算。 有界变量的目 标规划问题和混合整数规划问 题， 在电 源规划中经常用到。 求解参照文献 7 1 - 8 . 3 . 1 . 3多阶段单纯形法的计算机实现 对于单纯形法求解目标规划的计算机实现问 题，除了考虑具体算法外，还要考 虑问 题的 规模， 根据文献 2 . 7 讨论和问 题实际情况， 要解决好以 下问 题: 1 数据处理问 题。问 题的 数据包括基础数据、 生成数据和输出 数据。 基础数 据要符合程序的输入识别;生成数据要根据需要放入内存或外存便于计算 过程中的反复调用，节省计算时间。输出数据要按一定格式打印输出，易 于决策者判断。 2 内存问题。为了使计算方便，除紧凑存储目 标和硬约束条件系数矩阵的原 始数据外，还要存储基逆矩阵、右端常数向量等，这在很大程度上决定了 计算机所能解决的问题的规模。 3 误差问题。对解大问题来说，由于大量次数的迭代所引起的累计误差有时 会破坏解基逆矩阵的正确性而引起一系列的计算错误。解决的办法是设置 对右端常数向量和变换目 标函数系数的检测，如果发现出现严重的情况， 第 1 3 页 华北电力大学 ( 北京)硕士学位论文 则可根据 当前解重新求逆 。 4 )无解和多最优解 调整的办法解决 由于问题允许带有硬约束，可能出现无解，这时用解的 对于多最优解，可以根据决策者的意愿，预先对变量定 界，或者在得出最优解后对某些变量赋予上、下界进行灵敏度分析，使决 策者找到满意的最优解。 3 . 2 遗传算法 ( g a ) 3 . 2 . 1概述 启发式算法相对于最优算法提出，它是一种技术。这种技术使得在可接受的计 算费用内去寻找最好的解，但不一定能够保证所得解的可行性和最优性，甚至多数 情况下，无法阐述所得解同最优解的近似程度。 现代优化算法是 8 0年代初兴起的，它极大的推动了启发式算法的发展，在理 论和实际应用方面都有了较大发展。这些算法包括禁忌搜索算法，模拟退火算法， 遗传算法，人工神经网络算法等。它们在处理一些结构复杂的非线性目标规划方面 发挥了重要作用。 遗传算法是启发式算法的一种。遗传算法 ( g e n e t i c a 工 g o r i t h m)是一种建立在 自然选择原理和自然遗传机制上的迭代式自适应概率性搜索算法。模拟自 然界中生 物优化的发展 ，在人工系统中实现特定目 标的优化。遗传算法擅长全局搜索。遗 传算法由美国密执安 ( mi c h i g a n )大学j . h .h o l l a n d 教授在 1 9 7 5 年发表的论文 “ 自 然和人工系统的 适配系统”中 提出的。 d. e . g o l d b e r g , 发展和完善了 遗传算法系统， 而且成功的应用到搜索、优化及机器学习等领域。 3 . 2 . 2遗传算法的概念和术语说明 遗传算法使用的基本概念和术语如下: 1 )染色体遗传物质的主要载体，指多个基因的集合。 2 )基因型 一一控制生物性状的遗传物质的功能和结构的基本单位，又称遗传 因子。 3 )表现型一一它是由 染色体决定性状的外部表现，或者说，根据遗传因子形 成的个体，我们称为表现型。 4 )个体一一指染色体带有特征的实体称为个体。 5 )群体一一染色体带有特征的个体的集合，称为群体，该集合内的个体数目 称为群体规模。 第 1 4 页 华北电力大学 ( 北京)硕士学位论文 6 )适用度函数一一各个个体自 适用环境程度的函数，称为适应值函数或适应 度函数。 7 )选择一一用某种方法从群体中选择若干个体的操作称为选择。 8 )交叉一一把两个染色体重新组合的操作称为交叉，又称杂交。 9 )变异让遗传因子以一定的概率变化的操作称为变异。 1 0 ) 编码一一从表现型到基因型的映射称为编码。 1 1 ) 解码一一从基因型到表现型的映射称为解码。 1 2 ) 模板一一我们将染色体称为向量。一个给定向量结构，包括关心的分量位 置和值，称为该向量的一个模板。从遗传学的角度来讲，生物体的代代遗 传，使的某些基因和模板得到生存，生存的一个原因就是这些基因和模板 具有很强的适应能力。含有某种模板的染色体具有较大的遗传概率。模板 也保证了遍历的全局性。 3 . 2 . 3遗传算法的基本算子 在遗传算法主要操作算子包括选择、交叉、变异三个基本算子。遗传算法中主 要操作也就是选择、交叉、变异. 1 )选择操作。选择操作是遗传算法的关键，由 某种方法从群体a ( t ) 中选取 n 个个体放入交配池，交配池是用于繁殖后代的双亲个体源。选择的根据是 每个个体对应的优化问题目 标函数转换成的适用度函数值的大小，适用度 函数值大的被选中的机会越多， 选择的作用效果是提高平均适应度函数值。 优胜劣汰的选择机制使得适应度值大的解有较高的存活率。不同的选择策 略对算法的性能也有较大的影响。因此，要慎重选择策略和方法。常用的 选择策略有: 队列 ( r a n k )选择策略; 转盘式 ( r o u l e t t e w h e e l )选择策略: 锦标赛 ( t o u r n a m e n t )选择策略; 确定 性抽样 ( d e t e r m i n i s t i c s a m p l i n g ) 选择策略; 剩余随机抽样 ( s t o c h a s t i c r e m a i n d e r s a m p l i n g ) 选择策略; 随机整体抽样 ( s t o c h a s t i c u n i f o r m s a m p l i n g ) 选择策略。 典型的选择方法有: 适应度函数值比例法。 这种方法利用比例于各个个体适应度函数值的概率来决定其后代遗传的可 能性。若某个个体被选取的概率为p ; 表示为 第 1 5 页 华北电力大学 ( 北京)硕士学位论文 p ; 一位 ， = 1,2 ,.-n / 乞儿 ( 3 一 1 ) 式中，关 为个体i 的 适用度函数 值， n为 群体的 个体数目 。 当选 择概率确 定后，用随机变量试验，产生 0 -1区间内的随机数。由哪个随机变量值 决定哪个个体被选取，于是选择概率大的个体就能多次被选中和参加交 配，它的遗传因子就会在群体中扩大。那些没被选中和选择概率小的个体 就会被淘汰出去。 期望值法。 当个体不是很多时，由于随机变量数的摆动有可能不能正确反映适应 度函数值，这是概率选择上的问题。采用期望值法可以避免这个问题。首 先计算各个个体遗传后代的期望值， 然后， 在被选择的个体期望值减去05 ， 得到新的期望值。 排位次序法。 排位次序法是根据每个个体适应度函数值的大小从大到小排列顺序， 然后利用各位次预先已确定的概率，决定选择和遗传的后代。各个个体的 适应度函数值都已被排序，选择概率不与适应度函数值成比例而是依赖于 1顶 序。由于按顺序所给予的选择概率与适应度函数值不同，这是排位次序 法与适应度函数值比例法和期望值法的不同之处。 最优保存法。 在遗传算法的优化过程中，保存优化问题的最好解，使适应度函数值 高的个体不受交叉和变异的影响，无条件的遗传给后代。 2 )交叉操作。 交叉操作是把两个染色体重新组合的 操作。 交叉操作可以 产生 新的个体，从而需要检索空间中新的点。选择操作每次仅作用于一个个体 上，而交叉操作每次作用在从交配池中随机选取的两个个体上。交叉操作 产生两个子代个体，它们一般与父代个体不同，并且彼此也不同，每个子 代个体都包含两个父代个体的遗传物质。交又操作分为一点交叉、多点交 叉和一致交叉等。由于交又操作可以产生新的个体，因而在遗传算法中起 着核心作用。 3 )变异操作。变异操作是增加群体中个体的操作。它模拟了生物进化过程中 偶然的基因突变现象。基因变异能增加群体中个体的多样性。是以一个很 小的 概率凡从群体 a ( t ) 中随 机选取若干个个体， 对于选中的 个体又随 机选 取染色体中的某一位或者多位进行数码翻转，对于二进制数字串就是某一 位的值 1 变为0 或者值 0 变为 1 。 作为变异的变形有逆位， 所谓逆位就是将 第 1 6 页 华北电力大学 ( 北京)硕士学位论文 染色体中某个部分的数字序列的顺序反转。在染色体数字串上的不同位置 的两个数字或部分数字的位置交换，也是变异的一种方法。变异可以保证 不丢失一些信息，当群体规模较大时，在交叉的基础上引入适当的变异， 不仅能保证引入有用的信息，而且也能适当的提高遗传算法的搜索效率。 变异算子提供了一个恢复群体失去多样性的方法，确保群体继续进化，且 在当前解附近找到更好的解。 遗传算法的搜索能力主要是由 选择和交叉赋予的，变异则保证了算法能 搜索到空间中的每一点，从而使算法结果具有全局最优性。 3 . 2 . 4遗传算法的解题准备工作 遗传算法的解题准备工作如下: 1 )深入了 解优化现象，确立变量表示方法。用遗传算法求解问题，要确定遗 传算法变量的表示方案，并要求对求解的问题有深入的了解，明确问题追 求的日标是什么? 哪些变量是己知的?哪些变量是待求的?相互关系又如 何?要考虑哪些约束条件?等等 2 )确定适应度函数，反映优化问题追求的目 标。 把问题的目 标函数，经过处 理转换为适应度函数，适应度函数要求非负数，因此必须把目 标函数转换 为求非负的最小值形式。 3 拟订控制参数， 遗传算法的控制参数主要有群体规模 n 、 算法执行的最大 代数m、 选择率p s 、 交叉率几、 变异率p m 等参数， 如何确立这些参数， 是 优化问题的关键。 设定停止准则 在遗传算法中可以选用如下条件作为停止准则: 最优个体的适用度函数值达到了问题最优解。 最优个体的适用度函数值和群体的平均适应度函数值经过多次迭代运 算，保持稳定，已不再增加了。 迭代次数达到了算法执行的最大代数。在遗传算法的执行过程中，如果 上述三个条件中有一个得到了满足，则迭代收敛，算法结束。 当遗传算法停止执行时，就可以把当前代中最好的个体指定为遗传算法的 求解结果。 3 . 2 . 5遗传算法的实现步骤。 遗传算法的实现步骤概括起来主要有: 第 1 7 页 华北电力大学( 北京) 硕士攀位论文 染毪体中某个部分鲍数字序捌麴顺序反转。在染色体数字宰上鲍不同位置 豹两个数字或部分数字静位麓交换，毽怒变异酶一静方法。变弊可以保证 不镞失一些信息，当群体规模较大时，在交叉的基础上引入适当的变异， 不仅能保证引入有用的信息，而且也能邋当的提高遗传算法的搜索效率。 交舅簿子握爨了一令滚复群体失去多襻憋瓣方法，确缳群薅继续送托，显 在当前解附近找到更好的解。 避传算法的搜索能力主鬻是由选择和交叉赋予的，变异则保 芷了算法能 搜索到空间中鲍镣一点，从舔馊冀法结果爨毒全局最饯性。 3 2 4 遗传算法的解题准备工作 遗传算法魏瓣题楼铸王l 擘懿下： 1 ) 深入了解优纯现象，确立交爨表示方法。用遗传算法求解问题，疆确定遗 传算法变量的表示方案，并鼷求对求解的问题有深入的了解，明确问题追 求魄目标是什么? 哪些变量懋已知的? 哪魑变量是特求懿? 相互关系又妇 傍? 要考鑫秘塑终束条薛? 簿等 2 ) 确怒适应度函数，反映优化问题追求的目标。把问题的目标函数，经过处 理转换为适应度函数，适应度函数要求非负数，因此必须把目标瀚数转换 隽袋接受熬最小傻形式。 3 ) 拟订控制参数，遗传算法的控制参数主要有群体规模n 、算法执行的最大 代数m 、选择率只、交叉率e 、变异率只等参数，如何确立这些参数，是 优化阀题的关键。 4 ) 设定箨壹准囊 在遗传算法中可以媳用如下条件作为停止准则： 最优个体的适用度函数值达到了问题最优解。 袋傻令葵熬逶稠度露数馕秘嚣薛戆乎均透应度邀数谴经过多次速我运 算，保持稳怒，已不再增加了。 邀代次数达到了算法执行的最大代数。在遗传算法的执行过程中，如果 上述三个条传中有一个褥刭了满足，则迭代收敛，算法结柬。 当滚传算法停史执行霹，裁弼驻怒当意代中最菇的个钵指定为遗传算法韵 求解结果。 3 。2 。5 途传篝法的实凌劳骧。 遗传算法的实现步骤概括起来主骚有 嚣l 夏 华北电力大学( ：i e 京) 硕士学位论文 1 ) 2 ) 3 ) 4 ) 进行染色体编码，随机产生初始群