不确定规划及进一步的研究问题.pdf

《不确定规划及进一步的研究问题.pdf》由会员分享，可在线阅读，更多相关《不确定规划及进一步的研究问题.pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 f。一 t o 第1 0 卷 第6 期 指 挥技 术学 院 学 报 1 9 9 9年 1 2月 J o u r n a l o f I n s t i t u t e o f C o mma n d a n d T e c h n o l o g y Vo 1 1 0 No 6 De e 1 99 9 不确定规划及进一步的研究问题 整业L(清华大学数学科学系)摘要首先舟绍 了 确 定规划理 论，然后给 出了求解 一般不确定 规划模型 的基 于(随机或模 糊)模拟 的遗传算 法。最后 列举 了一 些可进 一步研 究的问题。关键词随机规划模糊规划；遗传算法 分 类号0 2 2 1 3 1 什 么

2、是不确定规划 数学规 划是 运筹 学的一个重要分支。经 典数学规划理论 与方法包括 线性规 划、非线性规 划、多目标规划、目标规划、动态规划等。这类规划在描述现实世界事实时，一切信息均看作确 定性的，使得从数学关系上描述它们的规划模型也具有确定性。然而，在管理科学、工程技术、军事决策等诸多领域都存在人为的或客观的不确定性，而这些领域都存在着大量 的优化问题。所 以不确定环境下的优化理论具有理 论价值和广泛 的应 用前 景。我们称不 确定 环境 下的优化 理论为不确定规划。不确定规划的研究内容包括不确定环境下的建模理论、算法及其应用。鉴 于不确定规划模型 的复杂性，经典 的算法是 无效 的。因而

3、不确定规划理论 不得不 引入智能算 法，如遗传算法、神经元网络及模拟退火法等。另外，计算机科学的高速发展给本学科带来了深 远影响，这不仅表现在 已有的不确定规划模型可 以由计算机求解，更重要 的是高速发展 的计算 机和不断涌现 的智 能算法如何促进不 确定规划 的进步及更广泛 的应用。2 不确定规划模 型 不确定因素的存在使复杂的决策系统通常含有随机或模糊参数。对于随机规划问题中出 现 的随机 变量，采用 的方法随要求而不同。最 自然 的方法是取这些随机变量所对应的 函数 的数 学期望。这种在期望约束下使 目标函数的概率期望值达到最优的模型称为期望值模型。第二类是机会约束规划，由C h a m

4、e s 和 C o o p e r 1 提出，其允许所作决策在一定程度上不 满足约束条件，但该决策使约束条件成立的概率或可能性不小于某一置信水平 ct。典型的机会 约 束规划可 以表示 成下 面的形式。ma x f st Ch f ，)f)-卢 Ch g (，)0，=1，2，P)口 收穑 日期：1 9 9 9 0 5 1 0 第一作者 t 男1 9 6 5 年生教授1 0 0 0 8 4 北京 维普资讯 http:/ 第 6朔 刘 宝碇，等：不确 定规 划及 进一 步 的研 究问题 1 0 3 其中 x是决策向量，是随机或模糊参数，a和 口 分别是对约束和 目标事先给定的置信水平，C h )表

5、示()中事件成 立的概率或可能性。作为机会约束规划的推广，此类 规划可 以表示成 f m a x E A，J s t-一 l C h，1 ，#)且，i 一1，2，【C h ，#)0 q，一 1，2，P 这里 晟，i 一1，2 ，表示对第 个 目标事先给定的置信水平。根据决策者给定的优先结构 和 目标水平，我 们也可 以把随机或模糊 系统化成机会 约束 目标规划。fra in P J(“+v,d 7)J s _t 一 1 c h ，)+=b =1，2，I C h g j(x，)o)，J一1，2，户 L ，计 0，f 一 1，2，这里 P =优先因子，表示各个 目标的相对重要性，且对所有的，有 P

6、 j P J+，“=对应优 先因子 第 f 个目标正偏差的权重因子，一对应优先因子 第 f 个 目标负偏差的权重因子，d I+一目标 i 偏离 目标值的正偏值，d 7一目标 f 偏离 目标值的负偏差，一目标约束中的机会 函数或普通实值函数，g =实际约束条件中的函数，b =目标 i 的目标值，1 一优先权个数，m =目标约束条件个数，P 一实际约束条件个数。正、负偏差 和 d 的值是下列不等式成立的最 小非负值。f C h 日一(x，)【C h ，)一 b)，一 1，2 ，第三种不确定规划，即相关机会规划，由L i u Z 提出。一个复杂的决策系统通常要完成多 项任务，称之为 事件，决 策 者

7、往 往希望 这些 事件实现 的概率或可 能性(即机会 函数)尽可能 的 大。相关机会规划是使事件的机会函数在不确定环境下达到最大的优化理论 有关相关机会 规划 的实 例及应用 见文 献“。不确定环境下典型的相关机会规划可以表示为；f r D _ a ，(z)s-t (g flx，#)0，J一 1，2，P 其中 z是一个n维决策向量，是一个随机或模糊向量，f )是一个事件的机会函数，g (z，#)0，一1，2，P是不确定环境 值得注意的是，在相关机会规划模型中，不确定环境所 描 述的可行 集并 不假定是确定的或清晰的。此类规划的模 型可以表示成 f ma x f(x)=，1)，2(z)，)s t

8、 L ，#)0，一 1，2，P 其 中，)是 由 个 函数=(x)，f：1，2，构成 的 向量，在 个 函数(x)中有些是机 会 函数。带有随机 或模糊 参数 的相关机 会 目标规 划可以看 成是复杂不确定决策系统 中的 目标 规划 的扩展。在管理 目标确定以后，目标 函数是在 一定优先 结构 中极 小化 偏差 根据决策者制 定的优先结构和 目标水平，我们可吼把随机或模糊决策系统建成相关机会目标规划，维普资讯 http:/ 指挥 技术学院 学报 1 9 9 9芷 m i n P (+)1 1 St (x)+d；-一 一 b ，i一 1，2，g ，)0，一 1，2，P ，0，i一1，2，这里 P

9、 J一优先因子，表示各个 目标 的相对重要性，且对 所有的 J，有 P，P ，u I，一对 应优先 因子 J第 i 个 目标正偏差 的权重 因子，一对应优先 因子 第 i 个 目标负偏差 的权重 因子，d J十 一目标 i 偏离 目标值的正偏差，d 目标 i 偏离 目标值的负偏差，一目标约束中的机会函数 或普通实值函数，g 一系统约束条件中的函数，b 一目标 i 的目标值，1 一优先权个数，一目 标约束条件个数，P一实际约束条件个数。从规划论 的角度 出发，我们不仅 重载 了随机与模糊 的概念，为随机规 划和 模糊 规划提供统 一的原理 不确定规划，而且将它 们推 广到多 目标规 划和 目标规

10、划 领域。另外，传统的数学规划模型提供清晰向量作为最优解使一些 目标达到最优值。但是，如果 从实际的需要出发，有时我们应该提供模糊决策而不是清晰决策。B o u c h o n-Me u n i e r 等0 总结 了各种各样的极大化建立在模糊集上的数值函数的方法。B u c k l e y和 Ha y a s h i 通过选 择一个 最优的模糊集去极大化一个实值函数，为此设计了模糊遗传算法，并应用到模糊优化问题、模 糊极大流问题、模糊 回归以及模糊控制等领域。更一般地，L i u和 1 w a mu r a 9 提供了带有模糊 决策的机会约束规划的理论框架，而 L i u 口 建立了带有模糊

11、决策的相关机会规划等一系列模 型，并为求解这些模糊模型设计了基于模糊模拟的遗传算法。3 应用遗传算 法求解不确定规划 经典方法根据概率论以及可能性理论，把不确定规划转化为它们的确定 清晰等价类，然 后和传统的求解确定性规划的方法求解。显然，这种方法只能解决一些特殊类型的不确定规划 模型。随着计 算机 的飞速发 展和智能算法 的不 断涌现，许多复杂 的优化 问题完全可 以通过计 算 机和智能算法得以解决。这里我 们给 出求解 一般不 确定规划模型 的基于模拟 的遗传 算法 如下：步骤 0 输入 参数种群规模 p o ps i z e、交叉 概率 P 和变异概率 P 步骤 1 产生 p o p s

12、 i z e 个初始染色体，其中可能使用模拟检验染色体可行性；步骤 2 对染色体进行交叉和变异操作，其中可能使用模拟检验后代的可行性-步骤 3 使用模拟技术计算所有染色体的目标值 步骤 4 根据 目标值使用基于序的评价函数计算所有染色体的适应度-步骤 5 旋转赌轮选择染色体 步骤 6 重复 步骤 2到步骤 5 直 到给 定的循环次数；步骤 7 把最好的染色 俸作为最 优解。4 进一 步研究 问题 目前，智能技术的基本框架 已经形成，在解决各种问题的求解和和应 用中展现了它的特 点 和魅力，同时也暴露 了在应用技术上 的许多不 足和缺 陷。客观地说，智能 技术 尽管 有各种新策 略和新提案不断地

13、被提出，但它们几乎都是针对持定问题求而言的，对它们的评估主要基于对 维普资讯 http:/ 第 6期 刘宝碇 等：不确定规划及进一步的研究问题 1 0 5 比实验，其 中缺乏 深刻 而具有 普遍 意义的理 论分析，有 必要进行 基本理 论的 开拓 和进 一 步深 化。下面主要 概述 不确定规 划现阶段 研究课题的几个方面。不确 定规划模型 的扩 充：目前 已有三大类不确定规划 期望值模型，机会约束规划和相 关机会规划。从理论 上说，还应有其它类型的不确定规划。不 确定规划 模型 的数 学性 质：如灵敏度分析，上下界的估计，对偶 定理，最优性条件及各种 确 定或清 晰的等价类等。模型的计算问题：

14、我们已尝试过基于随机 模糊模拟的遗传算法，但它 目前只能适用于小 规模 的问题，所以有必要作进一步的改善 以适应更大规模的问题。此外，我 们还可 以根据模型 的数学性质，设计一些特殊的传统算法，并考虑应用模拟退火法，神经元网络以及并行算法等 不确定规划的进一步的应用：例如考虑供给分配问题，生产过程，存储网络，资金预算，系 统可靠性，环境保护，模式识别，质量控制，风险分析等 参考文献 1 Cha r n e s A W W Cop e r Ch a n c e n s t m j ne d pr o g r a mm i ng-M a n a g e me n t Sc i e nc e，1 9

15、5 9，1(6)73 7 9 2 L i u B De p e n d e n t c h a n c e p r o g r a mmi n g：Ac l a s s 0 f s t o e h a s t ic p r o g r a mmi n g C o mp u t e r s&M a t h e ma t i c s w i t h Ap p l i c a t i o n s 1 99 7，1 2(3 4)89 1 0 4 3 Liu B-Un c e r t a in P r og r a mmi n g J o h n W il e y S o n s Yo r k 1 9

16、9 9 4 Liu B-a n d c Ku D e p e n d e n t-c h a n c e g o a l p r o g r a mmi n g a n d a n a p p l i c a ti o n J o u r n a l o f S y s t e ms E n g i n e e ri n g E l e c t r o n,s-19 9 3，2(4)4 e 47 5 Li u BDe p e ud e m-c h a nc e g oa l pr og r am ming a i d i t s g n e t lo a l go r i t hm b a s

17、 e d a pp r o a c hMa t he ma t i c a l a n d Co mp u t e r Ma d e 1 J ng，1 9 96，7(24)43 5 2 6 Li u BK1 wa mur B M o d e l l ing s t oc h as t i o de c i o n s y s t e ms us i n g d e p e nd e nt c h a n c e p r o gr a mmi n gEur o p e a n】0 ur na l o f Op e r a t i o na l Re s e R r e h，19 9 7，1(1

18、01)1 9 3 2 03 7 Bou e ho n M e unier BV Kr e l n o vie hALok s hl n HTNgu y e n-Ont h ef o r mu l a t i o n of op t i mi z a t i o n u n de r1 e a t m c o n s t r a i nt s (wi t h c o n t r ol i n m i n d)Fuz z y Se t s a n d Sy s e m s，1 9 9 6(8 1)5 4 29 8 B u c k l e y J J Y t-hy a s h i F u z z y

19、 g e n e t ic a l g o rit h m a n d a p p l k a ri o n s F u z z y S e y s a n d S y 6 t e mil-1 9 9 4(6 1)1 2 9 1 3 6 9 Li u B De p en de n t-c ha n c e pr og r am mingwi t hf u z z y d e e i o ns I EEETr a n s a e t i o ns o nFu z z y sy s t e ms，1 9 9 9-3(7)：35 4 3 舳 1 o 刘宝碇，赵瑞清随机规划与横糊规划北京：清华大学出版

20、社1 9 9 8 Unc e r t a i n Pr o g r a m m i ng a nd Fur t he r Re s e a r c h Pr ob l e ms Li u Ba o d i n g Z b a o Ru i q i ng (Dep a r t me n t 0 f App l i e d M a t ha me t i c s-Ts n u日Un i v e r s i t y)Ab s t r a c t By u n c e r t a i n p r o g r a mmi n g we me a n t h e o p t i mi z a t i o

21、n t h e o r y i n g e n e r a l l y u n c e r t a i n (r a n d o m f u z z y r a n d o mg r a y e t c )e n v i r o n me n t s St o c h a s t i c p r o g r a mmi n g a n d f u z z y p r o g r a mmi n g a r e t wo we l l k n o wn s u b t o p i c s o f un c e r t a i n pr o g r a mmi n g Th e ma i n p

22、u r p o s e o f t h i s p a p e r i s t o p r e s e n t a b r i e f i n t r o d u c t i o n t o u n e e t a i n p r o g r a mmi n g So me f u r t h e r r e s e a r c h pr o b 一 1 e ros a p p e a r i n t h i s a r e a a r e a l s o p o s e d Ke y wo r d s s t o c ha s t i c p r o g r a mmi n g；f u z z y p r o g r a mm i n g：g e n e t i c a l g o r i t h m(责任 编辑：程万毒)维普资讯 http:/