（运筹学与控制论专业论文）若干背谬问题的探讨.pdf

摘要 y 摘要 若干背谬问题的探讨 文章以启发式算法为序，揭开了本论文关于系统中背谬问题讨论的序幕。 背谬现象被讨论得最多的是网络中的b r a e s s 背谬。关于b r a e s s 背谬主要的讨 论被放在对网路条件分析的上面而本论文关于b r a e s s 背谬的讨论重点放在b r a e s s 背谬出现的内因上。论文的第二部分通过对比均衡状况下的流量分布与最优化的流 量分布揭示了b r a e s s 产生的原因。 论文的第三部分是讨论e j b i 1 务器中的背谬现象。现今e j b 协议在三层数据 结构中已被广泛使用。文章对e j b 服务器的服务性能进行了讨论。例证了当顾客请 求被随机响应的时候，会有一种替换背谬产生；但是当服务器可以将需要服务的顾 客请求按照e j b 容器的性能进行分配的时候，这种背谬现象将可以被规避。 论文的第四部分是讨论公司运营系统中的背谬现象。通过详细的讨论发现， 尽管质量被认为是公司的命脉，但是有时也会出现”过犹不及”的收场。 关键词：背谬b r a e s s 背谬替换背谬质量因子 譬警诒t 游、弹姆鲻辫 细垒空公精 aj b s t r 8 c e a b s t r a c t s e v e r a ld i s c u s s i o n so ns y s t e mp a r a d o x e s t h ed i s c u s s i o na b o u tp a r a d o x e si nt h et h e s i si sb e g i n n i n gw i t hd e s c r i b i n ga h e u r i s t i ca l g o r i t h m t h ee m p h a s i so fm a n yd i s c u s s i o n sa b o u tp a r a d o x e sw a so ri s l a i do i l _ t h e b r a e s sp a r a d o x a n df u r t h e rn l o r e ，t h ee m p h a s i so fm a n yd i s c u s s i o n sa b o u tt h e b r a e s sp a r a d o xw e r eo ra r ep l a c e do nn e t w o r k sc h a r a c t e r s r a t h e rt h et h e s i si s p a r t i a lt ot h ef a c t o rw h a tl e a d st h ep a r a d o x t l l r o u g hc o m p a r i n g t h ed i s t r i b u t i o n o ft h ef l o wo nt h ee q u i l i b r i u mc o n d i t i o nw i t ho nt h eo p t i m u mc o n d i t i o n ，w ee x p o s e t h er e a s o no ft h eb r a e s 3p a r a d o xo nt h es e c o n ds e c t i o n t h ep a r a d o xi nt h es e r v e rb a s e do ne j bi sd i s c u s s e do nt h et h i r ds e c t i o n n o wt h ea r c h i t e c t u r eo f e j bi sw i d e l ya p p l i e d t h r o l i g ha n a l y z i n gs e r v i c ea b i l i t i e so f d i f f e r e n ts e r v e s ，o n ep a r a d o xn a m e dt h er e p l a c e dp a r a d o xe m e r g e n c e s r a t h e ri ft h e c l i e n tc a l lb ea s s i g n e do ns e r v i c ea b i l i t i e so fe j bc o n t a i n e r s ，t h er e p l a c e dp a r a d o x c a nb ea v o i d e d t h ep a r a d o xi nt h eo p e r a t i o nm a n a g e m e n to ft h ec o m p a n yi si l l u s t r a t e d i nt h ef o r t hs e c t i o n t h r o u g ht h ed e t a i l e dd i s c u s s i o n ，w ed r a wac o n c l u s i o nt h a t t h r o u g hq u a l i t yi sa i li m p o r t a n tf a c t o rt ot h ec o m p a n yy e tt h e f i n a li sn o ta l w a y sa 8 w e i m a g e s k e yw o r d s ：p a r a d o x ，b r a e s sp a r a d o x ，r e p l a c ep a r a d o x ，q u a l i t yf a c t o r 第一篇简介 希腊神话中特洛亚王子帕里斯得到海伦的同时也为特洛亚带来了十年的战争浩劫。 安危相易，祸福相生。世事变幻无常，祥瑞有时偏偏是灾难的端倪，薄利不巧成了 惨败的先驱。同样对于一个系统来说，看似增益的举止也许将适得其反的招致背谬 的收场。本文以一个启发式算法的例子为引，对系统中的背谬问题展开了讨论。文 中主要分析了三个系统：网络系统、e j b 服务器系统和公司的运营系统。 i 1 启发式算法的尴尬 启发式算法对于一些复杂的组合优化问题或实际问题能够较快速的给出一个较好的 解。但是也正是因为启发式算法给出的解不是问题的最优解，所咀用启发式算法去 求解问题的时候，不可避免的会出现一些意想不到的效果。请看下面的例子。 例1美国一个配送中心每天必须服务于1 3 个卖场，如图1 1 所示。表1 1 中 给出了配送中心到各个卖场以及各卖场之间的距离。依据配送中心的规定：如果两 个卖场之间的距离大于6 0 英里，则送货车不可以连续的经过这两个卖场。并且这里 从卖场l 到卖场j 的距离，等于从卖场j 到卖场i 的距离( ，j = 0 ，l ，1 3 ) 。卖场对于 配送中心货物的需求列在表1 2 中，一个卖场需求的货物只可以被配送中心的一辆 卡车所满足，而不可以被配送中心两辆或者多辆卡车所拆分满足，稷设配送中心的 卡车数目不受限制。己知的条件有：每辆卡车的限载量是1 0 吨；每辆卡车每天上路 的管理费用是1 0 0 美元( 包括搬运费用，保险费等等) ；开动卡车每英里路要l 美元 ( 包括司机的薪水、汽油费等) 。配送中心想找寻一种送贷方式使得所有的卖场需 求得到满足并且总费用尽可能的小。 l ! 旦垄茎墨造鲤! ! 些! 表1 1 o o o 0 ：配送中心；1 1 3 ：卖场 图1 1 配送中心和卖场示意图 l ! 星垄茎蔓望堕堕些! 表1 2 我们用启发式算法产生可行解。算法如下：选取离配送中心最近的未被服务 的卖场作为每辆卡车送货的第一个卖场，之后卡车在其负载允许的情况下为离其现 在所在卖场撮近的卖场送货，只要卡车负载允许就可以继续为其它卖场送货，卡 车可以不断为卖场服务。直到剩下的卖场距离太远或是卡车负载不允许时，卡车 回到配送中心。因而我们选取卖场l l 作为卡车1 送货的第一个卖场。接着考虑离卖 场1 1 最近的卖场：卖场2 是离卖场n 最近的卖场，但是卖场n 和卖场2 需要货物的总 和超过了一辆卡车的负载能力，所以我们考虑卡车到达卖场1 1 之后到达卖场1 0 。卖 场1 0 和卖场l l 所需货物的总和已经达到了卡车的最大负载量1 0 吨。卡车从卖场1 0 回 到配送中心。卡车2 在剩下的卖场中选择为离配送中心最近的卖场5 送货，之后为 离卖场5 最近的未被服务的卖场6 送货，再后为卖场6 最近的未被服务的卖场9 送货， 卡车2 不能再为其它未被服务的卖场送货，因为它已经达到虽大载货量，卡车2 回 配送中心。以此类推，直到所有的卖场所需货物都被卡车送到。计算卡车l 按路 径0 - 1 1 1 0 - 0 送货的费用c o s t = 1 0 0 + 1 ( 1 6 + 2 4 + 4 2 ) = 1 8 2 美元。1 0 0 美元是卡车的 固定费用，后面的是卡车运行路程所带来的费用( 1 美元英里) 。其它卡车费用同 理可以计算。按照这种启发式算法得到的如表1 3 左边的配送方案，这个配送方案的 总费用是1 3 0 5 美元。 如果例题1 中的卖场6 因为种种原因关闭了，用同样的启发式算法计算，得到 相应的配送路线( 见表1 3 右边) ，此时总费用是1 3 0 7 美元。因此从表1 3 中可以清 楚的发现，出现了背谬现象一一用同样的启发式算法设计卡车送货路线系统，配送 中心少为一个卖场服务，卡车送货的总费用反而增加了。 l ! 翌堡墨叁堕堡塞! 表1 3 配送中心为1 3 个卖场服务配送中心为1 2 个卖场服务 卡车卖场费用( 美元)卡车卖场费用( 美元) l0 - 1 1 1 0 - 01 8 2l m l l 一1 0 - 01 8 2 20 - 5 - 6 9 一o1 7 42 0 5 - 4 01 7 2 30 - 1 2 - 7 01 6 93 o _ 1 2 7 - 01 6 9 4o 2 1 01 9 74 0 9 - 2 02 0 1 5m 4 - 3 。o2 1 55 o - 8 01 7 0 6o 一8 o1 7 06 o - 1 1 3 _ 02 1 7 70 1 3 - 01 9 87 0 _ 3 01 9 6 配送路线的总费用： 1 3 0 5 配送路线的总费用：1 3 0 7 尽管一直没有人对启发式算法会产生背谬给出一个明确的讨论，但是每一个 应用启发式算法去解决问题的人却熟知启发式算法始终无法像问题的最优解那样尽 善尽美的道理。而面对一些优化问题，我们不知道如何去求其最优解，或者求其最 优解过程过于复杂，这时候启发式算法还是具有举足轻重的优势，它通过快速的求 解出问题的次优解帮助人们解决问题。在带来速度的同时，我们也应当意识到启发 式算法毕竟不是最优解，它不可避免的存在背谬现象。所以一旦实践需要应用启发 式算法的时候，我们应该采用适当的模拟方法去规避会使得背谬现象出现的启发式 算法。 i 2 背谬现象的研究 前面我们给出了一个产生背谬现象的启发式算法。启发式算法会产生背谬这一点并 不难理解，而且启发式算法千变万化，所以它的背谬难以引起热切的讨论。背谬现 象被讨论得最多的是在网络中。在网络中增加一条路一般被看作为缓和网络系统堵 塞状况的一种可行方法。这种措捕的效果似乎是显然的：增加一条路意味着增加一 种选择的可能性，“理所当然”的应该使得网路状况变好，至少认为不会使得网路 l ! 篁堡墨叁塑堡塞! 状况变糟。的确，当网路不拥塞时，增加一条路线确实会对网络系统的通行状况有 所裨益。但是，对于一个拥塞的网络系统来说，其真正的效果将如何如今却有了争 议。 在1 9 6 8 年，b r a e s s 1 提出了一个网路，其增加了一条路后反而增加预期通过 时间。同时，b r a e s s 给出t b r a e s s 背谬的定义【2 】一个逻辑上看似减轻网络负担的 措掩实际上却增加了网络的负担。可能是因为数值例子会给人过于牵强和凑巧的嫌 疑，一开始这个精巧构造的数值例子并没有引起学者们太大的关注。但在1 9 6 9 年， 德国斯图加特城市中心的发展计划却恰恰是因为其经试验模拟【3 1 结果正好出现了 网络背谬现象而不得不被另辟蹊径。科学家们开始意识到，网络中的b r a e s s 背谬也 许不仅仅是一个由精心构造参数而得的特例。它在现实中将有客观存在的可能性。 于是，一些科学家r 例如m u r c h l a n d l 4 】，s t e w a r t 5 ，r 蛐 6 1 ，s t e i n b e r g 幂l z a n g w i l l 7 ， d a f e r m o s 8 j 以及t e i n b e r g 和s t o n e 9 】开始举出相应数值例子来证明现实的生活中孕育 着b r a e s s 背谬现象。随后相应的网络背谬问题在电子网络 1 0 l 、供水网络 1 1 1 以及稳 态排队网络 1 2 1 和动态排队网络f 1 3 】等网络系统中也相继被发现。 事实上，背谬现象应该不仅仅是网络系统的问题。在很多系统中，一些习惯 上认为有好处的举动，其真正的效果也并非每次都是遂人心愿的。 i 2 j 网络中b r a e s s 背谬现象的研究 现有的文章都是通过数值形式举出反例的方法来证明网络中b r a e s s 背谬的现象有可 能会出现的。b r a e s s 背谬现象的出现意味着一种“未蒙其利反受其害”的效果，因 此举出反例的意义在于提醒相关的网络设计人员在实际网络设计中要注意规避这种 背谬现象。 1 9 9 0 年c o h e n 和k e u y 给出了排队网络中出现b r a e s s 现象 1 2 1 的例证，当时讨 论的网络通行条件是顾客仅知道网络的平均排队长度。1 9 9 1 年，k e l l y 1 4 】又给出 了，网络上的顾客即使在知道网络中的瞬时排队状况而不仅仅是网络中的平均排队 状况的情况下，b r a e s s 背谬依旧会出现的例证。1 9 9 7 年c a l , ，e n 1 3 例证了动态排队 网络的b r a e s s 背谬的出现。 塑笪星墨墨盟堑塞! 同时，b r a e s s 背谬现象真实的出现在英国电信网络 1 5 1 中：增加了网络中某些 路径的容量，网络状况反而变糟。学者们由此也开始有损网络中b r a e s s 背谬现象的 讨论。1 9 9 4 年，g i b b e n s 对此问题【1 6 】进行了进步的讨论。1 9 9 7 年b e a n 1 t 对于有 损网络中增加一条路径，网络状况反而变糟给出了例证。有趣的是，在有损网络中 调整路径导致状况变稽时总伴随着磁滞效应的产生。k e n y 【1 4 】和g i b b e n s 1 6 1 8 】都 分别对这种现象进行了描述和分析。 可惜的是因为前人证明的结果是基于数值上给出反例的形式所以关 于b r e s s 背谬出现的原因一直没有进行浓墨重彩的讨论，大多只是用一两句话轻描淡 写的带过。本文在后面的第二部分中从顾客达到的均衡与系统最优化之间的差异 出发，对网络中b r a e s s 背谬的成因进行了详尽的讨论和分析。尽管用于讨论的网络 形式比较简单，但是基于参数形式的讨论成功的揭开了b r a e s s 背谬神秘的面纱。 j 2 2e j b 服务器的服务性能 系统背谬不仅仅存在于网络中，还存在于我们所熟知的一些系统中。在后面的章节 中，文章尝试着对e j b 服务器和公司的运营系统展开讨论。因为现在还没有学者关 注这两方面的背谬现象，所以本文希望能够葱到抛砖引玉的作用，引起人们对于这 些方面背谬现象的关注。 一个e j b 服务器可以被看作为一个排队系统。而客户请求被e j b 服务器处理 的过程也是客户请求进入e j b 服务器中被其中的e j b 容器所响应的过程。在下面的 第三部分中，我们将对基于e j b 结构的客户服务模式系统中的e j b , q i ；务器的服务能 力进行讨论。 通过后面的讨论，证明t e j b 服务器对于客户请求的响应也有可能出现背谬 现象：当e j b 服务器中一个e j b 容器合并了原来服务器中两个e j b 容器的事务处理 能力，整个服务器的服务能力却有可能反而下降。但是。如果我们改善这种e j b 服 务器的性能，使其能够对进入它的客户请求进行合理的分配，这种背谬现象将会被 规避。 j 背谬现象的研究 j 2 3 质量在公司中的重要地位 当市场机制日益丰润完善，当同行间的竞争演变成一场场硝烟滚滚的厮杀，当众多 关于产品质量的投诉以排山倒海的气势涌入法院，许多公司开始把产品质量看成为 安身立命的土壤和蓬勃发展的阳光。 质量管理的发展已经走过了一个世纪的时间【1 9 卜从历史来看大约每隔二 十年质量管理的方法就有一个突变。从一开始十九世纪的操作者质量管理，n - - 十 世纪初的工长质量管理，进而发展到二三十年代风靡一时的专职检验员质量管理， 之后就是统计质量控制阶段，到现在已经进入到第五个阶段全面质量管理阶段。 现在公司对于产品质量投入越来越多关注的目光。几乎没有人去质疑产品质 量越高时公司收益将增大的思想。通过后面第四部分的建模和讨论，我们将见到一 个因“矫枉过正”而导致“过犹不及”的背谬例子一一当产品质量增大到一定程度 再继续增大的时候，公司收益不仅没有所冀期的增大。而且反而减小了。 第二篇排队网络中b r a e s s 背谬产生 原因示例 2 1 构造一个简单的排队网络模型 研究排队网络中的b r a e s s 问题一般通过给出反例的方式来证明背谬现象的存 在性。同时在对排队网络q ，b r a e s s 背谬问题展开讨论时，许多研究都借用 了1 9 6 8 年b r a e s s 所构造的排队网络的形状【1 】，即如图2 1 和m 2 2 所示的初始和增广 排队网络形状来进行比较增加一条路的效果。 图2 1 初始排队网络图2 2 增广排队网络 这样构造的一个简单的排队网络中包括两种类型的服务台模 式，f c f s ( f i r s tc o m e ，f i r s ts e r v i c e ) 和i s ( i n f i a i t es e r v i c e ) 。其中f c f s 是m m 1 队 列，i s ：黾m m o o 队列 2 0 】。然后根据各种网络特有的性质来分析顾客在各种网络 上的行为选择，以及网络将达到怎样的均衡。每个进入图2 1 所示的初始捧序网络的 塑塑垄二尘堡璺塑堡坠旦堑堡型! 顾客可以选择的路径有路径a b d f 和路径a c e f 。每个进入图2 2 增广排序网络的顾 客可以选择的路径有路径a b d f ，路径a c e f 和路径a b e f 。 为了阐述捧队网络中b r a s s 背谬产生的原因这里首先构造一种简单的排队 网络来借以说明排队网络中b r a e s s 背缪现象。初始排队网络和增加一条路径之后的 网络依旧分别用图2 1 和图2 2 所示的排队网络图。假设每个人知道网络中其他人的 选择，并且每个人会选择一条使得其预期通过时间最短的路径。如果网络中的每个 人在网路中的路径选择是在其他人保持不变的情况下的最小化自己预期通过时间， 就称此时排队网络达到均衡。因此每个人在网络中的行为可以看作时一种非合作搏 奔( an o n - c o - o p e r a t i v eg a m e ) 。每个人都寻求的是使得自己从入口到出口通过时问 最小化的路径。 若假设服务台b 、c 、d 、e 的服务效率分别是p l 、p 2 、p 3 和m ，则当到达各 个服务台的顾客是期望为$ 的泊松流时，顾客在各个服务台的期望服务时问分别 是i 毒( ( p 1 ) 、击、土p a 和u 上a - - 一x f , z 纵) 。 2 j j 排队网络达到均衡时的情况 当有流量为2 a 通过图2 1 所示的初始捧队网络时，如果从a r b 的顾客服从参数 为。的泊松分布，则通过路径a b d f 的期望通过时间为i 南+ 击，通过路径a c e f 的 期望通过时间为击+ 面= 砖两a 令t 1 为初始排序网络的预期时阃，则达到均衡时 有： t l = i l i + 石1 = 面1 + i 毫两 ( 2 _ 1 1 ) p l z弘3 也弘4 一t z 一o j 同时为了确保初始排队网络中的每一条路径上的流量都不为0 ，有下面的不等式成 立： 0 工 卢1 2 a ，0 2 a 一嚣( p 4 a ，0 z 2 a( 2 1 2 ) 当有流量为2 a 通过图2 2 所示的增广排队网络时，如果从a 到b 的顾客服从 的泊松分布参数为 1 ，从b 至 j d 的顾客服从的泊松分布参数为 2 ( 2 1 ) ，则通 过路径a b d f 期望的通过时间为百+ 去，在通过路径a c e f 的期望通过时间 为击+ 石1 未丽，在通过路径a b e f 期望通过时间为i 石+ 石= i 墨丽。令t 2 为增 塑塑垄二尘堕苎塑堡坠旦堑塑型! ! 广排序网络的预期通过时同，则达到均衡时有： t 。= 万+ 石1 = 面1 + 百柄= 万毛十万抵( 。工s )2 2 。五忑+ 石2 面+ 五了二t 西两2 石丙十五_ = _ 西- 二i 五( 2 - 1 3 ) 为了保证增广排队网络中的每一条路径上的流量都不为0 ，有下面的不等式成立： 0 a i m ，0 2 a a 2 p 4 ，0 a 2 a i 2 a( 2 1 4 ) 2 j 2 分析排队网络达到均衡时的流量要求 首先，分析增广排队网络。根据等式( 2 1 3 ) 可得出其预期平均通过时间： t ：= 壶+ 磊1 ( 2 - 1 5 ) 肛2“3 并且有 l1ll 石。鬲= 7 a i i = 面而2 石p 2p 1 一p 4 一【z 一 2 jp 3 即 a t = p l p 2 ，a 2 = 2 a 一( # 4 一p 3 )( 2 1 ，6 ) 将( 2 1 6 ) 代入到( 2 1 4 ) 中的不等式中有： p 1 一p 2 = a l 2 a( 2 1 ，7 ) 纵一p 3 = 2 a a 2 0( 2 1 9 ) 将不等式( 2 1 7 ) 与不等式( 2 1 ，8 ) 相加得： ( 弘l 十# q ) 一( p 2 + 肛3 ) 4 ( 2 1 1 0 ) 由不等式( 2 。i 9 ) 与不等式( 2 1 1 0 ) 可得出为了增广排队网络每条路径的流量都不 为0 ，要求输入的流量满足下面的不等式： o 虫! l ! 二些! ! _ 掣 2 a ( 肛。+ p 。) 一( p 2 + 3 ) ( 2 1 1 1 ) 塑塑垄二尘笪苎塑苎坠璺堑堡型 望 由初始排队网络的流量要求不等式( 2 ，1 2 ) 可以推出 0 2 a “l + m( 2 1 1 2 ) 分折排序网络的b r a e s s 背谬问题是将两种排序网络流量通过情况进行比较， 所以这里考虑的流量是同时满足不等式( 2 1 1 0 ) 与不等式( 2 1 1 1 ) 的流量，即要求输 入的两排队网络的流量满足： o 纽蔓生手捌 2 a ( p 1 + p 4 ) 一( 肛2 + p 3 ) ( 2 1 1 3 ) 即有 2 ( _ f 工l + p 4 ) 一( p 2 + 肛3 ) 4 a( 2 1 1 4 ) 2 j 3 比较在排队网络达到均衡时流量通过情况 4 、首先将前面已经求出的初始网络预期通过时间表达式( 2 1 ，1 ) 写成方程组的形 式： ， # 4 - 2 a 一+ x ：南 肘舻。a 2 碍1 + 去 将等式( 2 1 5 ) t 2 = 面1 + 石1 代入上式有 纵忡r 2 k 若慕囊 p - + “a 一2 a 2 石i f 石辜譬与；毒2 孑f f 2 石y 碍+ t 2 ( z - s ) 令七= p l + p 4 2 a ，根据流量条件( 2 1 1 4 ) 有m + 卢3 k + p 3 所以有下面两个不等式成立 所以有 害怒憎柏：耳1 i 乎- i p 2 + 出 者高 11 丽i 而4 # 2 , a 3 c 石南，c 壶+ 去， 0 ，对称轴小于0 ，所以二次方程( 2 1 1 6 ) 有两个不等的负实根。这 说明通过初始捧队网络的期望时间小于通过增广排队网络的期望时间，即增广排 队网络比初始排队网络增加了一条路反而使得网络的通过情况变糟。因此出现 了 3 r a e s s 背谬现象。 2 2 排队网络中b r a e s s 背谬现象的解释 因为一般依据不同的条件进入排队网络的流量会自行的按照某种规律进行分布，所 以很少有人讨论排队网络中最优流量分布是怎样的。为了给出排队网v h 中b r a e s s 背 谬出现原因的详细分析，在这里我们分析了排队网络的最优流量分布。 2 2 1 分析模型的晟优化状态 进入两个捧队网络的流量依旧是2 ，并且这个流量满足排队网络达到均衡时的流量 要求，即f 2 1 1 3 ) 。 首先分析初始网络最优化的流量分布情况。假设有从a 经b 、d i f 的流量 望苎坠塑垡! 星垦塑受盟堡望墨塑篓壁! ! 是z ，则从a 经c 、e 到f 的流量是2 a 一。最优的流量分布是： m 伽m a ：e 石b + 击，击+ 面栖) s u 巧e c t t o l o 0 地一( 2 a z ) 0 z 0 我们先分析最优解的情况 定理2 1 若矿是方程 l111 石_ 二i + 石。面+ 五了= t 面二_ 习 的解，则z + 也是规划问题( 2 2 1 9 ) 的最优解。 证明当z 在可行域中，并且。 矿时有 ( 2 2 1 9 ) i 1 i1111 1 再+ 石 五= + 五2 面+ i = 西f j 巧 鬲：+ 五2 石+ 面= 西两 m 一 去+ 面1 ，面1 +4 一( 2 a可) = 1 一+ 弘2p 4 11 肛1 一茁p 3 ( 2 a 一$ ) 塑堡坠塑垡! 型垫盟堡墨墨塑竖登! 曼 又因为z 一+ 一 卢1 一zp 3p l o + 工3 即可行域中z 矿时的目标函数m 石b 十蕊i ，击十面栖) 的值大于王= 矿时目标函数的值： 综上所述：方程i 南+ 面l = 面1 + 面= 壶两的解z 是规划问题( 2 2 1 9 ) 的最优 解。 口 同时根据方程( 2 1 1 ) 和定理2 1 ，我们可以得知初始排队网络顾客达到均衡时 的流量分布就是该捧队网络取最优解时的流量分布。 下面我们分析增广排队网络最优化的流量分布情况。假设有从a 到b 的流量 是。1 ，从b t j d 的流量是。2 则从a 经b 、d 到f 的流量是现；从a 经b 、e 到f 的流量 是。1 。2 ；从经c 、e 到f 的流量是2 a 一霉1 。可行域是 翌= ( 。l ，z 2 ) i 芦i 一。1 0 ，弘4 一( 2 a a 冶) 0 ，2 ：1 0 ，嚣12z 2 如果。2 ! q - ! 而+ 百= 函习而。弘4 - ( 2 a - z 1 ) 1lll 面+ i - = 可五习石+ 五_ = 下面两 竹1 口工 ( 上j l - z l + 面1 ，石告+ 面刁甄1 = 习，击+ 面i 西1 = 面 m 石与+ 石1 ，石b + 五= ( 去= 孤，茁1 + 面= 去= 可 m 。 石与+ 面1 ，击+ 面= i 去2 可) 所以增广网络的最优流量。2 = z 1 ，而规划问题是一个求最小值的规划问题，它转 化成规划问题中决簧变量是z 1 、可行域为a = z 1 p 1 2 l 0 ，p 4 一( 2 a n ) o ，。l o ) 、目标函数为m 口$ 百b + 击，击+ 面= c 去= 可) ： 依据定理2 1 ，我们有。1 = z 2 = 矿是上述规划问题的最优解； 综上所述：o l = z 2 = 矿是增广排队网络最优化的流量分布。口 通过定理2 1 和定理2 2 发现增加一条路径的增广网络的最优流量分布情况， 竟与初始排队网络的最优流量分布情况一致的。而且，对于增广网络来说，达到均 衡的状态与其的最优流量分布并不一样；初始网络排队网络达到均衡的状态与其的 最优流量分布是一致的。困而b r a e s s 背谬现象也就自然而然的产生了。 通过对构造简单的排队网络模型的分析，一些对网络有所增益的举动是对于 网络的最优流量分布状况有所增益一一至少不会变糟，但是实际流量的分布状况并 不一定会有所改进，甚至有可能会变糟。下面我们分析其他的一些系统，我们会发 现，一些被认为是“常识”的理念也将受到了质疑。 第三篇基于e j b 的三层客户服务 器中的背谬现象 事实上，这里的网络可以看作为一个广义的网络，那么服务系统，供应链流水线 生产都应该包括在其中。下面我们讨论在基于e j b 结构的分布式系统的背谬现象。 3 1 基于e 虺的三层客户服务器结构 图3 l 是一个基于e j b 的三层客户服务器( c l i e n t s e r v e r ，简称c s ) 结构，这是现 在普遍采用的一种c s 结构。 萑 蜒 _ _寥m 钷 图3 1 基于e j b 的三层客户服务器结构 ，) 3 描述客户请求在五增服务器中的状况 所谓三层c s 结构，是指将应用程序划分为三个不同的逻辑层次：表示层、商 务逻辑层和数据层。表示层是应用的用户接口部分，担负着用户与应用间的对话功 能；商务逻辑层相当于应用的本体，将具体的业务处理逻辑地编入程序中；数据层 就是d b m s ，负责管理对数据库数据的读写。- - , 层c s 结构有下述优势：利用单一 的访问点，可以在任何地方访问站点的数据库：对于各种信息源，不论是文本还是 图形都采用相同的界面；所有的信息，不论其基于的平台，都可以用相同的界面访 问；可跨平台操作：减少整个系统的成本；维护升级十分方便：具有良好的开放 性：系统的可扩充性良好：进行严密的安全管理：系统管理简单，可支持异种数据 库，有很高的可用性等。但是由于三层结构的编程复杂，必须采用组件技术来进行 三层应用的开发。所谓组件技术就是将中间层业务逻辑的划分为相对独立的组件。 采用组件技术的优点在于，可以将相对独立的业务逻辑封装起来达到更高层次的软 件复用，从而大大提高编程的工作效率。 而e j b ( e n t e r p r i s ej a v a b e a n s ) 规范就是一个组件事务监控器( c t m ) 的标准服 务器端的组件模型。e j b 规范1 0 是s u n 公司在1 9 9 8 年j a v a o n e 大会期间发布的。软 件厂商根据它来实现e j b 服务器。e j b 组件技术将三层结构中的中间层商务逻辑层 分割戍许多独立的模块，然后将分割的模块封装在不同的e j b 组件中，对外部只提 供它们的功能接口。对于一个e j bj 务器来说，它里面包括具有各种事务处理能力 的e j b 容器。而每个e j b 容器所能处理的事务的性质则由其中e j b 组件的性能来决 定。图3 1 为基于e j b 结构的模型。客户请求进入到e j b 服务器中，根据请求类型的 不同，服务器将客户请求分配到具有相应事务处理能力的e j b 容器中，进行处理。 3 2 描述客户请求在邑b 服务器中的状况 为了描述客户请求在e j b 服务器中被响应的状况。我们首先讨论客户请求队列在一 个e j b 容器中是怎样被响应的。假设e j b 容器中的组件可以提供1 个缓存服务和m 个 平行的事务处理服务。如图3 2 。客户请求在e j b 容器中的响应情况可以用一个排队 网络的模型来表示这个子系统的堵塞状况。 用面表示e j b 容器中m 个e j b 组件的平均工作效率。若k 个客户请求进入这 照堂堕查堡查垄墨! 璺墅墨堡! 堕鉴堡! ! 样的e j b 容器。如果讨论的e j b 容器服务的特征是至少有一个客户需要的e j b 组 件空闲时，新的客户请求才有可能被响应的情形，则均衡状态下的平均运行时间 是善i 2 1 1 。 。一 。= ；j 田洲，卜 f 引 图3 2 客户请求队列在一吟 e j b ：容器的堵塞状况 我们用所需的运行时间除必l e j b 容器处理的客户请求耳将得到一个只 与e j b 容器中组件性质有关，而与进入e j b 容器的总客户请求的无关的数；：b ，在 这里将之定义为该i e j b ：辞器的线性服务系数，用臁示。因此对于一个e j b 容器来 说，如果已经知道它的线性服务系数，那么一定量的客户请求进入谚i e j b 容器所需 的服务时间就等于客户请求的数量与e j b 容器线性服务系数的乘积。 如前面的圈3 1 所示，在一个e j b 服务器中，可能包括几个甚至多个具有同样 事务处理能力的e j b 容器。进入服务器的请求将被这些! e j b 容器中的某个响应。考 虑到e j b 容器处理事务时会对总资源造成一种占用，因此所有客户在e j b 服务器运 行状况用总顾客分布各叶 e j b 容器中各自的平均运行时间求和来衡量。在这里我们 称之为系统服务指数，用s 来表示。同时还定义一个e j b 服务器的服务系数：将其 服务状况指数s 与进a e j b , q t 务器的客户请求总数置的比值定义为e j b 服务器的服 务系数r ，。 在评价两个e j b 服务器服务状况优劣的时候，我们用同样数量的顾客请求进 入要比较的系统，哪一个服务器的各容器运行时间总和( 即系统服务状况指数s ) 越 小，我们认为该服务器越优。因为比较时进入服务器的客户请求数量类型都相同， 根据e j b 服务器的服务系数r s 的定义，所以服务系数越小的e j b 服务器，其服务状 况也越好。 5 1 墨婴笠墨! 查2 堕塞堕垫盟堇墨翌查墨堕生丝 3 3e j b 服务器中客户请求随机的被b 磷器响应 如果，客户请求是被e j b 容器随机的响应，那么客户请求被各个e j b 容器响应的情 况都将等概率的出现 3 ，3i e j b i 务器服务状况 如果e j b 服务器中处理这种客户请求的e j b 容器只有两个：e j b 容器1 ，e j b 容 器2 。并假设m l ，口1 r l 和m 2 ，- 2 ，r 2 分别为e j b 容器1 和e j b 容器2 的e j b _ t t 件个数、 组件的平均工作效率以及线性服务系数，则r 1 = ；蠹，r 2 = 磅1 瓦- 在这种情况 下如果有k 个客户请求进入到e j b 服务器中，那么将会出现k + 1 种可能的分布情 况，即t ，k 一谗= 0 ，1 ，- 一，k ) 个客户请求分别进k e j b 容器l 和e j b 容器2 中， 并且每种分布情况出现的概率只= 譬。这里c 皇是表示这种分布情况可能出现 的客户请求组合数，而2 ”= 函q f 是所有分布情况可能出现的客户请求组台 数之和。对于客户请求分布情况i 0 = 0 ，1 ，k ) ，e j b 服务器的系统服务状况指 数鼠= i r l + ( k i ) r 2 。则系统的平均服务状况指数： s = 鉴。最& = 壶 罐( 0 r 1 + k - r 2 ) + c b ( 1 r 1 + ( k 一1 ) r 2 ) + - - + c z ( k r l + o 兄2 ) 】 = 去2i r l ( o e 是+ 1c _ + + k - 9 嚣) + r 2 ( 曝+ ( 耳一1 ) 曝+ + o c t ) 】 = 去【( r l + 恐) ( o + l 殴+ 2 嚷+ - + k c f ) 1 = 击( r l + r 2 ) 耳( c 是一l + 曝一l + + g 暂k 一- 1 1 ) = 击( r l + r 2 ) k 2 耳一1 = 垦峙血 = ( 去+ 磅1 面，丁k 根据e j b 服务器的服务系数r s 的定义：服务器服务状况指数s 与进入服务的客户请 求数k 的比值所以e j b 服务器的服务系数毋为j ( ；耘+ ；耘) 5 3e b 服务器中客户请求随机的被e j b 窖器响应 舶 假设e j b 服务器中处理某种客户请求的e j b 容器有n 个：e j b 容器1 ，e j b 容 器2 ，e j b 容器n 。他们的线性服务系数分别为r 1 ，r 2 ，r ，又设进 入e j b n r 务器的该种请求数为k 。 引理3 1 且f 硼务器中处理某种客户请求的e 腰容器有n 个：e 磷器1 ，e 船容 器2 ，e j b 容- 器n 。他们的线性服务系数分别为r 1 = 蔫1 ，r 2 = 蠢五，- 岛= 磅1 瓦客户请求随机的进入到各且珊容器中，则e 珥服务器针 对这种客户请求的服务系数兄s 是一个与e j b 服务器中总客户请求数无关，只 与目j b 服务器中处理这种服务的丑瑁容器的性质有关的数，且璐= i 1z t - - l ；耘。 证明为了说明的方便，我们假设客户请求讲类型的服务。如果e j b h 务器中 处理服务类型为p 的客户请求的e j b 容器只有两个，且e j b 容器的服务系数分别 为r 1 和r 2 ，则r s = 鱼专血= 1 司1 面- t - i 蠹) ，引理结论与之相符； 假设e j b 服务器中处理服务类型p 的e j b 容器有m 个的时，e j b 服务器的 服务系数r s = 牮= 石1 冬1 高面，考虑e j b 服务器中再增加一个处理该 种事务的e j b 容器m + l 的情况。那么将会出现耳+ 1 种可能的分布情况出现， 即i k 一 ( i = 0 ，1 ，k ) 分别进入e j b 容器m + 1 和原来的m 个e j b 容器中。k i 个客户请求进入原来的m 个e j b 容器种，可能出现m o 种客户请求的组合。这是 因为m 耳一= ( 1d - 1 + + i ) k - i 而后面式子展开后的组合意义就是k i 个 客户请求分布在m 个e j b 容器中所有的组合数。所以i ，k i “= 0 ，1 ，) 分 别进入e j b 容器m + 1 和原来的m 个e j b 容器中的可能组合数是m “g 0 ，而所有 情况可能的组合数之和相当于是个客户请求进入的m + 1 个e j b 容器的所有可能 组台数为( m + 1 ) “。因此i ，k i ( i = 0 ，1 ，) 分别进k e j b 容器m + 1 和原来 的m 个e j b 容器中，出现的概率是只= ；静，此时e j b 服务器针对这种客户请 求的系统服务状况指数为& = i 品l + ( k i ) r s 。则e j b 服务器的的平均服务状 况指数为： 塑墨堡里墨量主查昱堕垄堕垫塑墼墨r 堕墨堕堡丝 s = 釜。只& = 矸1 邗胁”嚷( o r m + 1 + k 毋) + m 一1 嚷( 1 r m + 1 + 暇一i ) r s ) + + m 0 9 嚣( r m + 1 + o r s ) = 商知【+ l ( 噼+ l c ；：m “1 + 2 嚷舻一2 + + k c k k m ”一) + r s ( k - ? 殳t n + ( 耳一1 ) i 强m x 一1 + t + l c 蚤m 耳一( 耳一1 1 + o l ? 菩m k 一片) 】 = 赤【r m + l ( o + l e 品m 一1 + 2 ( 臻m 片一2 + + k e 置m 一k ) + r s ( k g 嚣m 耳+ ( k 一1 ) g 荽一1 m 一1 + + l g 毛m 一( k - i + o ) 】 = 酉知耳【+ 1 ( 嚷一1 m n l + 璐一1 m 肛2 + 十四k 一- 1 1 m o ) + r s ( g 荽二 r n 耳+ c k - 2 m 耳一1 + + c 晏一1 m 1 ) 1 = ( 1 + - - - 扣l m ) k r , n + i ( 1 + f 孢) 一1 + r s m ( 1 + m ) 耳一1 】 = t f r m + 1 + r s m j = t i i + 1 + 翟l 忍】 = 量骅耳 = 希笛1 而1 此时e j b 服务器的服务系数为岛= 嘉= 示干t 1 嚣1 磅i 瓦，即e j b 服务器中增加一 个e j b 容器时也成立； 综上所述：e j b 服务器中处理某种客户请求的e j b 容器有n 个，如果e j b 容