互斥方案

互斥方案（精选7篇）

互斥方案 篇1

资本限量决策在非计算机手段下通常采用排序法或组合法, 在方案较多时, 排序法看起来实用且较简单, 但实际上非常复杂, 且工作量非常大。而在组合法下由于可能的组合非常多, 决策者往往不会列出所有可能的组合, 因而有可能漏掉最优组合方案, 从而导致决策失误, 因此利用先进的计算机技术求解资本限量决策问题十分必要。

目前, 有学者提出利用Excel规划求解功能来解决单期资本限量决策和多期资本限量决策问题。资本限量决策方案一般属于独立方案, 但有时部分方案也可能存在互相排斥的情况, 增加了决策的难度。本文主要探讨如何利用Excel规划求解功能来解决部分方案互斥情况下的资本限量决策问题, 以帮助决策者提高决策质量和效率。

一、设计部分方案互斥的资本限量问题单元格

设计单元格就是在Excel工作表中确定目标变量与决策变量、约束条件的具体位置及其相互联系。目标变量是反映决策目标的指标, 决策变量是决定决策的变量, 约束条件是对目标变量或决策变量的要求。例如, 某企业有A、B、C、D、E五个可供选择的投资项目, 其中B与C、D和E为互斥方案, 该企业当前最大资金供应量为400万元, 各方案初始投资额、净现值等有关资料如图1所示 (金额单位:万元) 。另外, 各方案不允许部分投资, 即要么投资、要么不投资。要求确定能够使净现值为最大且投资额不超过资本限量的最佳投资组合。

上例中:投资组合的净现值即为目标变量;所选择的方案及其投资比例即为决策变量;投资组合的投资总额不大于资本限额即为约束条件。此外, 各方案不允许拆细投资、B与C互斥、D和E互斥也是约束条件。

1. 确定决策变量单元格。

决策变量单元格表示方案是否被选中的位置, 方案是否被选中是待定的, 因此决策变量单元格一般称之为可变单元格。由于各方案不允许部分投资, 因此可变单元格的值为0或1, 即如果选中该项目, 相应单元格的值为1, 否则为0。本例选择D2:D6为可变单元格。

2. 确定目标变量单元格及其函数。

本例选择单元格E2作为目标变量单元格, 表示所选中项目的净现值总额;同时需要明确目标变量单元格与决策变量单元格之间的关系。由于所选方案的净现值合计等于各方案净现值乘以所选方案的投资比例 (考虑到各方案不允许部分投资, 应是整体投资, 故被选中方案的投资比例为1) , 因此在E2单元格输入计算公式“=SUMPRODUCT (C2:C6, D2:D6) ”。该式表示D2:D6列与C2:C6列的对应单元格相乘后的和, 即所选择项目的净现值总额, 初始状态为0。

3. 确定投资支出单元格及其函数。

本例选择单元格F2表示所选中项目的投资支出总和, 并输入其计算公式“=SUMPRODUCT (B2:B6, D2:D6) ”。该式表示B2:B6列与D2:D6列的对应单元格相乘后的和, 初始状态为0。同时选择G2作为资本限量单元格, 输入400。

4. 确定反映方案关系的单元格。

如图2所示, 本例以H2:H6作为表示各方案之间独立与互斥关系的单元格, 由于方案B与C存在互斥关系, 为了保证方案B与方案C只能取其一, 在单元格H3中输入“=D3+D4”, 在下面的约束条件中我们令H3取值小于或等于1, 在单元格D3和D4取值为1或0的情况下, D3和D4数值相加之和也小于或等于1, 这意味着D3和D4只能取其一, 即取值为1, 或均为0, 从而保证了方案B与方案C只能取其一或者都不取;同理, 由于方案D与方案E存在互斥关系, 所以在单元格H5中输入“=D5+D6”。

二、输入部分方案互斥下资本限量决策的约束条件

在工作表中确定了规划求解的各个要素所处的单元格后, 需要确定并输入规划求解的各个约束条件。

1. 进入规划求解对话框。在加载宏的Excel工具菜单下选择规划求解命令, 出现规划求解对话框, 如图3所示:

2. 输入目标变量单元格及其取值要求。

进入规划求解对话框后, 在设置目标单元格的位置输入目标变量单元格的绝对地址, 也就是存放所选方案组合的净现值总额的单元格, 即$E$2。由于要求所选方案净现值合计为最大, 所以在取值时要求选择最大值按钮。

3. 输入可变单元格。

在规划求解对话框中的可变单元格引用位置输入可变单元格为D2:D6, 具体见图3。

4. 添加资本支出约束条件。

在规划求解对话框中单击添加按钮, 出现添加约束的对话框, 在单元格引用位置栏存放选中方案投资支出合计数单元格的绝对地址$F$2, 在约束值栏输入资本限量单元格的地址$G$2, 两者的逻辑关系选择“>=”, 如果投资项目资本支出和资本限量均用正数表示, 则逻辑关系应选择“<=”, 表示选中项目投资支出合计数“G2”不大于资本限量“H2”, 如图4所示:

5. 添加选中方案投资比例的约束。

本例中不允许部分投资, 被选中方案投资比例为100%或1, 未选中方案投资比例为0, 因此表示各方案投资比例或投资与否的可变单元格取的单元格引用位置输入可变单元格的地址D2:D6, 在逻辑关系处选择“bir”, 表示按二进制计数, 如图5所示:

6. 添加方案相互排斥的条件。

由于本例中方案B与方案C是相互排斥的, 因而二者只能取其一。为此在图5中单击添加, 并在添加约束对话框的单元格引用位置输入H3, 在约束值位置输入“1”, 在逻辑关系栏选择“<=”, 如图6所示:

由于H3的公式为“=D3+D4”, D3、D4的取值要么为1, 要么为0, 在约束条件中进一步要求D3与D4之和不大于1, 表示D3、D4对应的方案只能取其一, 或者都不取。同理, 本例中方案D与方案E也是互相排斥的, 需要继续添加条件, 在图6中单击添加按钮, 在添加约束对话框中的单元格引用位置选择输入H5, 在约束值位置选择输入“1”, 在逻辑关系栏选择输入“<=”, 如图7所示:

然后单击确定按钮返回规划求解对话框, 如图8所示:

三、部分方案互斥下资本限量决策模型选择与求解

完成上述约束条件添加并返回规划求解参数对话框后, 单击规划求解参数对话框中的选项按钮, 在出现的规划求解选项对话框 (见图9) 中需要进一步确定求解模型。

在资本限量决策中, 目标变量净现值合计 (F (x) ) 与各方案

从函数关系上看, 目标变量即净现值合计与决策变量的选中方案投资比例之间的关系属于一次函数, 属于线性关系。因此, 在规划求解选项对话框中选择“采用线性模型”, 其他默认。然后返回规划求解对话框, 如图9所示:

单击规划求解对话框中的求解按钮, 进行最后的运算得出结果, 如图10所示。项目A、B、D的值为1, 为选中项目, 此时总投资支出为395万元, 不大于资本限额, 该投资组合的净现值合计为170.2万元, 表示在不超过资本限额400万元的情况下, ABD组合能够使净现值达到最大。

就上例而言, 由于可供选择的方案较少, 实际上通过观察就可以确定最佳的投资组合, 但在实际工作中, 面临的方案较多且存在互斥的情况下, 运用Excel进行资本限量决策的优点就会彰显出来:减轻了脑力劳动和节省了工作量、决策程序清晰、保证决策结果的正确性。

摘要：在方案较多、部分方案存在互斥情况下的资本限量决策一直被视为难题, 这是因为这种决策程序复杂、组合较多, 容易导致决策效率低下甚至遗漏最优组合方案。本文研究了运用Excel规划求解功能解决部分方案互斥条件下资本限量决策的求解问题, 以提高部分方案互斥条件下资本限量决策的质量和效率。

关键词：部分方案互斥,资本限量决策,Excel,规划求解

参考文献

[1].中国注册会计师协会.财务成本管理.北京:经济科学出版社, 2007

[2].董黎明.用Excel实现资本预算的线性规划解决法.中国管理信息化, 2006;9

[3].郁玉环.Excel“规划求解”多方案组合排队投资决策中的应用.中国管理信息化, 2009;4

互斥方案 篇2

互斥方案[1]是指各个方案之间存在着互不相容、互相排斥的关系, 各个方案可以相互代替, 方案具有排他性。互斥方案按照计算期的不同可以分为计算期相同的互斥方案、计算期不同的互斥方案和无限计算期的互斥方案。 计算期不同的互斥方案在项目决策中是最常见到的, 针对计算期不同的互斥方案来说, 由于计算其不同所带来的在时间上具有的不可比性, 使直接采用净现值法和差额内部收益率来进行比选方法失效, 考虑到时间可比这一条件的限制, 计算期不同的互斥方案比选常用的方法有:最小公倍数法、研究期法和净年值法。

1 最小公倍数法、研究期法介绍

最小公倍数法 ( 又称方案重复性假设法) 。最小公倍数法是以各备选方案计算期的最小公倍数作为比选方案的共同计算期, 并假设各个方案均在这样一个共同的计算期内重复进行。对各方案计算期内各年的净现金流量进行重复计算, 得出各个方案在共同的计算期内的净现值, 以净现值较大的方案为最佳方案。

研究期法就是通过研究分析, 直接选取一个适当的计算期作为各个方案共同的计算期, 这个计算期可以选择寿命期最短方案的寿命或以寿命期最长方案的寿命期做为相互比选的共同寿命期, 也可以规定各个方案统一的计划服务年限, ( 计划服务年限不一定等同于各个方案的寿命) 计算各个方案在该计算期内的净现值, 以净现值较大的为优。

2 最小公倍数法、研究期法计算过程

案例:两个互斥方案的初始投资、年净收益及计算期如表1 所示。 试在折现率i=10%的条件下应用净现值选择方案。

解法一: 取两个方案计算期最小公倍数12 年作为计算时间。 在12 年内, A方案共有3 个周期, 重复实施两次。B方案共有两个周期, 重复实施一次。

NPVA=-100-100 ( P/F.10%, 4) -100 ( P/F.10%, 8) +40 ( P/A.10%, 12) =57.6 万元

NPVB=-200-200 ( P/F.10% , 6) +53 ( P/A.10% , 12) =48.2万元

解法二: 选择方案中较短的计算期作为共同的研究期, 即n=4, 计算各参数的净现值。

NPVA=-100+40 ( P/A, 10%, 4) =26.8 万元

NPVB= ( -200 +53 ( P/A , 10% , 6) ( A/P, 10% , 6) ( P/A, 10%, 4) =22.4 万元

从以上两种解法可以看出, 应选择方案A。

3分析

上述案例比选符合互斥方案比选概念[2], 即如果用0~1 变量xj代表方案是否被选中, 则当

且成立时, m个方案互斥。

最小公倍数法有效地解决了计算期不同的互斥方案之间净现值的可比性问题, 但是其中假设之一[3]:假设企业在项目最小公倍寿命之后的存续期间将进行相同的投资方案, 不考虑目前企业作何方案选择, 然而, 目前的方案选择有可能会对企业项目再投资过程中的项目选择产生重大影响, 因而在实际问题中, 这一假设基本不成立;假设之二: 备选项目在最小公倍寿命期间进行多次重复投资, 经济学的基本假设性公理提出--资源稀缺性、理性经济人、有限理性, 那么该假设就违反了该公理, 因为客观上来说备选方案中一定会存在一个是最优方案;假设之三:要求决策者至少能预测出在最小公备寿命期内的企业相关情况, 但是该假设在实际中也是不成立的。

资金[1]是时间的函数, 资金随着时间的推移而增值, 其增值的这部分资金就是原有资金的时间价值。 从这一概念出发考虑应用最小公倍数法的计算期不同的互斥方案比选中我们可以看出, 备选项目在最小公倍寿命期间进行多次重复投资过程中因为时间价值因素影响, 现实中, 除了第一次投资 ( 以上述案例A为例) 100 万元外, 其他两次投资依然维持在100 万元是不实际并且不科学的, 最小公倍数法中-市场条件并未改变, 但是在现实中, 随着时间的推移, 各行各业的发展, 市场条件一定是水涨船高, 是一个变量。

在一些特殊项目中, 方案计算期过长, 利用最小公倍数法计算出来的共同计算期有几十年甚至过百年, 最小公倍寿命法失去其严谨性, 例如:在15%的折现率下, 50 年后10000 元仅和现值9 元。

综上, 并不是所有的方案都可以运用最小公倍数法考虑, 现实情况例如:可再生能源开发型项目, 方案的重复实施假定不再成立, 最小公倍数法不再适用。 其实, 在实际中, 方案可重复实施的并不常见。 而且在方案多次重复实施过程中, 计算期过长, 甚至可能会超过项目所生产产品的市场寿命, 其建设项目评价参数会随着时间的推移而发生变化。 例如:在现代企业的运营和发展过程中, 根据市场形势的变化、企业经营和战略发展的需要, 合理的安排项目建设, 是保持企业市场竞争力和长远发展能力的重要手段。而项目的决策、实施和运营效果, 都与项目资金的筹集问题有关。从我国的实际情况来看, 银行贷款是项目筹资的主要渠道。 那么, 在最小公倍数法的计算期中, 银行贷款利率就是一个不可忽视的因素。 其变化严重影响着整个计算期净现值的大小。 这样就降低了所计算方案经济效果指标的可靠性和真实性。 2000 年以来银行贷款利率变动如表2。

通过表2 我们可以看到银行贷款利率的波动情况, 显然, 在整个最小公倍数法的计算期内银行贷款利率具有很大变动, 应用到其中也会带来很大差异。

研究期法直接选择互斥方案中年限最短或最长的方案的计算期作为互斥方案的共同研究期, 通过比较各个方案在该计算期内的净现值来对方案进行比较。解法二式一中可以看出B方案已知一个周期内的年值求其现值, 与期初投资加一起作为总现值, 再已知此现值求其在一个周期内的年值, 已知此年值, 再求与方案A相同计算期的现值。其计算的方案周期相对较短, 可以避免其经济评价参数像在解法一中那样随着时间发生的变化。 但是其计算过程略微复杂, 对于初学者来说其理解和运用都有一定难度。

4 结论、待研究问题

通过以上案例及其分析过程可得, 计算期不同的互斥方案进行比选中, 应用最小公倍数法与研究期法均考虑了时间的可比性, 应用过程中考虑到有些项目不能重复实施, 并且考虑评价参数随时间变化, 因而与研究期法相比, 最小公倍数法不仅考虑了时间的可比性而且克服了项目不可重复实施以及建设项目评价参数随时间发生变动的缺点。 因此在计算期的不同的互斥方案比选过程中, 相比最小公倍数法, 研究期法使用范围更加广泛。

同时, 最小公倍数法在其运用过程中, 根据最小公倍数法计算出来的共同寿命周期应该有一定的年限限制, 而目前, 各相关教材等并未对其作出相关说明。 这也是有待解决的一个问题。

参考文献

[1]王恩茂.工程经济学[M].科学出版社, 2010.

[2]宋伟, 赵国杰.能用等额投资换算法评价投资额不等的互斥方案吗[J].基建管理优化, 2002.

[3]沈星元.最小公倍寿命法的缺陷及修正[J].财会通讯, 2006.

[4]国家发展改革委建设部发布建设项目经济评价方法与参数[M].三版.中国计划出版, 2006.

[5]李春好, 曲九龙.项目融资[M].二版.科学出版社, 2004.

[6]霍晓燕.互斥方案比选时NPV与NPVR指标优劣对比[J].科技创新论坛, 2010.

[7]程秋林.关于方案比选中经济评价指标选取的探讨[J].有色冶金设计与研究, 2012.

[8]姜彦福.论寿命不等的互斥投资方案的经济比较原理与方法[J].数量经济技术经济研究, 1990.

浅谈事件的互斥、对立和独立 篇3

如果两个事件A与B不可能同时发生, 即满足A∩B=Φ, 则称A与B互斥;如果A与B有且仅有一个发生, 即满足A∩B=Φ, A∪B=Ω, 则称A与B对立;如果A与B满足P (A∩B) =P (A) P (B) , 则称A与B独立.

这三个概念都是考虑两个事件之间的相互关系, 我们不妨就从数学上的“关系”角度来考虑这三个概念, 看它们是否符合“等价关系”, 也即看它们是否有反身性、对称性和传递性.具体的, 对集合Ω, 设R是关于Ω中的元素的条件, 如果Ω中的两个元素A与B满足条件R, 则称A与B有关系R, 记为ARB, 否则称A与B无关系R.如果对Ω中任意的元素A, 都有ARB, 则R有反身性;如果ARB, 则BRA, 则称R有对称性;如果ARB, 且BRC, 则ARC, 则称R有传递性.下面我们就来具体讨论一下, 互斥、对立、独立之间是否满足反身性、对称性和传递性.

反身性:

如果A与A互斥, 由定义可知:A∩A=Φ, 则A为不可能事件Φ, 也就是说与自身互斥的事件只能是不可能事件.

如果A与A对立, 由定义:A∩A=Φ且A∪A=Ω, 即A=Φ, 并且A=Ω, 矛盾, 也就是说一个事件不可能与自身对立.

如果A与A独立的话, 则有独立性的定义可知:P2 (A) =P (A) , 即:P (A) =0或P (A) =1, 如果P (A) =0, 则A的选择有很多, 例如A=Φ∪N, 其中N为零测度集, 即P (N) =0, 一个特别的情形就是A=Φ.对于P (A) =1的情形, 我们可以取A=ΩN, 其中P (N) =0.总之, 如果A与A独立的话, 则A的选择可能有无穷多种, 显然并不是所有事件都能与自身独立, 例如概率小于1的事件不可能与自己独立.

由此我们可以得到:互斥、对立、独立不满足反身性.

对称性:

如果A与B互斥, 显然B与A也是互斥的, 这是因为两个事件的交运算满足交换律.

如果A与B对立, 显然B与A也是对立的, 这是因为两个事件的交运算和并运算 (有时也称为和运算) 满足交换律.

如果A与B独立, 显然B与A也是独立的, 这是因为两个事件的交运算和两个数的乘法运算满足交换律.

由此我们可以得到互斥、对立和独立都满足对称性, 这是由交运算、并运算和两个数乘法运算的可交换性所决定的.

传递性:

如果A与B互斥, B与C互斥, 则A与C可能相容, 也可能互斥.例如, 取Ω={1, 2, 3, 4}, 如果A={1}, B={2}, C={3}, 则A与B, B与C, A与C都是互斥的;如果A={1, 2}, B={4}, C={1, 3}, 则A与B互斥, B与C互斥, 但A与C不是互斥的, 图示如下.

如果A与B对立, B与C对立, 则A=C, 而不是A与C对立.事实上, 因为A与B对立, 所以B=A, 若B与C对立, 即与C对立, 因此, C=A==A, 其中表示A的对立事件.

如果A与B独立, 且B与C独立, 则A与不一定独立.我们通过举例来说明.

例取Ω={ω1, ω2, ω3, ω4}, 四个基本事件是等可能发生的, 也就是说, P ({ω1}) =P ({ω2}) =P ({ω3}) =P ({ω4}) =

第一种情况:取事件A={ω1, ω2}, B={ω1, ω3}, C={ω1, ω4}, 则由古典概型的计算公式:P (A∩B) =P (A) P (B) , P (B∩C) =P (B) P (C) , P (A∩C) =P (A) P (C) , 即事件A, B, C是两两独立的.

第二种情况:取事件A={ω1, ω2}, B={ω1, ω3}, C={ω1, ω4}, 则由古典概型的计算公式:P (A∩B) =P (A) P (B) , P (B∩C) =P (B) P (C) , 但是我们有P (A∩C) =P (Φ) =0≠=P (A) P (C) , 即事件A与B, B与C是相互独立的, 但A与C不是独立的.

所以, 我们可以得到:互斥、对立和独立都不满足传递性.

综上所述, 互斥、对立和独立都是满足对称性, 而不满足反身性和传递性, 所以它们都不是等价关系.

下面我们来讨论一下互斥、对立和独立的相互关系.首先, 我们来看一下互斥和对立之间的关系.从互斥和对立的定义可以看出, 如果两个事件是对立的, 则它们一定是互斥的, 反之不成立.事实上, 对立是一种特殊的互斥.

典型例题:对飞机连续射击两次, 每次发射一枚炮弹, 设A={两次都击中}, B={每次都没有击中}, C={恰有一次击中}, D={至少有一次击中}, 其中彼此互斥的事件是:A与B, A与C, B与C, B与D, 对立事件是:B与D.

下面我们主要来看一下对立和独立的关系.

如果两个事件A与B对立, 则P (A∩B) =0, 所以要使得A与B独立, 则P (A) 与P (B) 至少有一个为0, 例如, A=Φ, B=Ω时, A与B独立, 需要指出的是, 此时的A与B并不是唯一确定的, 我们可以取A=N, B=Ω-N, 其中, N是任意满足P (N) =0的事件 (即N是任意的概率为0的集合) , 则A与B是对立并且是独立的.但是如果P (A) P (B) >0, 则A与B不可能是独立的, 即如果两个事件对立, 它们的独立性是无法判断的.

如果两个事件A与B独立, 则A与B的可能对立, 也可能不对立.例如, 取A=B=Φ, 或者A=B=Ω, 则A与B独立, 但它们显然不是对立的;如果我们取A=Φ, B=Ω, 则A与B独立, 并且A与B是对立的.事实上, 我们要从P (A∩B) =P (A) P (B) 得到A∩B=Φ是不可能的, 因为前者刻画的是事件的概率之间的关系, 而后者刻画的是事件本身之间的关系.

互斥方案 篇4

如今, 互联网上有大量的资源供用户使用, 这些资源很多都是临界资源。互联网上大量进程都要使用这些临界资源。由于临界资源共享时要互斥访问, 这就使得这些进程在访问临界资源时要互斥进入自己的临界区。

进程互斥进入临界区算法设计时要注意三点: (1) 互斥访问 (mutual exclusion) [1,2,3], 即是每次只能有一个进程进入自己的临界区, 同一时间不能两个或两个以上进程进入临界区。 (2) 空闲让进 (progress) , 即是当没有进程在临界区执行, 有一些进程要进入临界区时, 只有那些不在remainder section中执行的进程有权决定谁进入临界区, 并且这决定不能无限推迟。 (3) 有限等待 (bounded waiting) , 即是进程从申请进入临界区到进入临界区这段时间是一段有限的时间, 进程不能无限等待进入。

互联网上共享临界资源进程只有遵循以上三点, 进程执行的结果才不会出错。也只有在遵循以上三点的基础上, 互联网上的应用程序才能为用户提供可靠的资源访问。

目前, 对进程互斥分布式算法设计主要分为三类, 即 (1) permission-based (e.g.Lamport, Ricart-Agrawala, Singhal, Maekawa) , 思想是每一个进程在进入临界区之前要得到所有其他进程的准许。 (2) token-based (Suzuki-Kazami, Raymond, Naimi-Trehel, Neilsen-Mizuno, Chang, Singhal and Liu) , 思想是整个系统有一个token, 只有得到token的进程才能进入临界区。 (3) Quorum based, 思想是所有进程中, 部分进程决定某进程是否可以进入临界区。

2. bakery算法设计的思想

Bakery算法是一种简单的处理n个进程互斥进入临界区的算法。它基于面包店里普遍使用的一种算法。顾客进入面包店的时候首先得到一个服务号码, 得到最小号码的顾客首先得到服务。基于这一思想, bakery算法处理N个进程互斥时对共享变量的读写采用原子操作来实现, 每个进程都拥有一个属于自己的共享变量。这个共享变量指示本进程在等待进入临界区的位置, 只有当本变量指示等待队列的头部时, 本进程才优先进入临界区。只有本进程才可以对属于自己的共享变量读写, 别的进程只能读。Bakery算法代码如图1。

在本算法中, 不同顾客可能得到同一个号码。为此, 我们有定义1。

定义1:有二元组 (number[i], i) 和 (number[j], j) , 当number[i]

定义1的意思是:顾客i的服务号码number[i]<顾客j的服务号码number[j]时, 或者顾客i和顾客j的服务号码相等, 但i<时, 顾客i先服务。在图1中, Bakery算法满足下面三个申明。

申明 (1) (进程互斥)

申明 (2) (空闲让进)

申明 (3) (有限等待)

max (Time (i) boundwait) = (N-1) * (T1+T2) 其中Time (i) boundwait为进程i从申请进入临界区到进入临界区的等待时间。

T1为执行a2:num[i]=max (num[0], num[1], …, num[N-1]) +1所用时间;

T2为执行临界区代码所用时间。

3. 用快速算法对bakery算法的改进

bakery算法解决了n个进程互斥问题, 满足进程互斥时三要点。但bakery算法存在以下实际的缺点。

(1) 总是有进程在临界区时, 进程申请进入临界区的服务号将无限变大 (unbounded number) 。

(2) 使用的共享变量多, 两个共享数组有2N个共享变量, 在分布式环境下使得进程之间信息交换量增大。

(3) 程进入临界区之前要和N-1个进程的服务号进行比较, 不管是否有别的进程要进入临界区, 这无疑会使进程的运行速度变慢。

为此我们提出了进程互斥的快速算法 (fast for n processes) , 可以有效地解决以上bakery算法存在的问题。

为了引入快速算法, 先还是引入快速算法的简单情况, 两个进程的快速算法。可以把bakery算法分成六个部分:start, doorway, ticket assignment, wait section, critical section and final。Start即执行算法初始化代码, 进程i在doorway处即进程i执行完了choosing[i]=true, ticket即执行Number[i]=1+max (Number[1], ..., Number[N]) , wait section即互斥循环, critical section即临界区, final即出临界区善后代码。而快速算法的思想是设置gate1和gate2, 只有同时得到gate1和gate2进程优先进入临界区, 并且后得到者优先进入临界区。在快速算法中我们假定对共享变量的操作都是原子操作。图2是两个进程的快速算法。

断言1:┐ (csp∧csq) 是重言式 (进程互斥) 。

证明:反正法。假设 (csp∧csq) 为真。

由 (1) 、 (2) 得 ( (gate1=p) ∨ (waitq=false∧gate2=p) ) ∧ ( (gate1=q) ∨ (waitp=false∧gate2=q) ) 真, 得 ( (gate1=p) ∧ (gate1=q) ) ∨ ( (gate1=p) ∧ (waitp=false∧gate2=q) ) ∨ ( (gate1=q) ∧ (waitq=false∧gate2=p) ) ∨ ( (waitq=false∧gate2=p) ∧ (waitp=false∧gate2=q) ) ……分配律

(3) 为真。

式子 (3) 中用∨连接的每一项都是假。 (gate1=p) ∧ (gate1=q) 为假, 而 (gate1=p) ∧ (waitp=false∧gate2=q) 时csp和csq不能同时成立, 所以此式也为假, 同理 (gate1=q) ∧ (waitq=false∧gate2=p) 为假, 而 (waitq=false∧gate2=p) ∧ (waitp=false∧gate2=q) 也为假, 得到矛盾。

断言2:两个进程的快速算法满足空闲让进的原则。

证明: (1) 当p已经执行到临界区而q刚执行 (不同时执行算法时) , p进入临界区。

(2) 当p, q同时到达时, 记late (p, gate1) 为p后写gate1, 记late (q, gate1) 为q后写gate1, 记late (p, gate2) 为p后写gate2, 记late (q, gate2) 为q后写gate2。

(2.1) late (p, gate1) ∧late (p, gate2) 时, csp为真;

(2.2) late (p, gate1) ∧late (q, gate2) 时, csq为真;

(2.3) late (q, gate1) ∧late (q, gate2) 时, csq为真;

(2.4) late (q, gate1) ∧late (p, gate2) 时, csp为真, 证明完毕。

断言3:两个进程的快速算法满足有限等待的原则。

证明: (1) 当p已经执行到临界区而q刚执行 (不同时执行算法时) , p进入临界区。两进程直接进入临界区, 不用等待其他进程。

(2) 当p, q同时到达时,

(2.1) late (p, gate1) ∧late (p, gate2) 时, csp为真, p直接进入临界区;q阻塞在q4, 等待时间为p执行临界区的时间 (常数) 。

(2.2) late (p, gate1) ∧late (q, gate2) 时, csq为真, q等待常数时间;p阻塞在p2, 等待时间为q执行临界区的时间 (常数) 。

(2.3) late (q, gate1) ∧late (q, gate2) 时, csq为真, q直接进入临界区;q阻塞在q2, 等待时间为p执行临界区的时间 (常数) 。

(2.4) late (q, gate1) ∧late (p, gate2) 时, csp为真, p等待常数时间, q阻塞在q2, 等待时间为p执行临界区的时间 (常数) 。证明完毕。

快速算法n个进程情况只需对两个进程情况稍加修改, 引入数组wait[n], n个进程都竞争gate1, gate2。算法如图3。

显然, 快速算法n个进程情况跟快速两个进程的情况一样, 满足互斥、空闲让进、有限等待三要点, 显然有下面断言。

断言4:如果csi为真, 则坌j (1…N) j≠i, ┐csj是重言式 (进程互斥) 。

断言5:N个进程的快速算法满足空闲让进的原则。

证明: (1) 当N个进程两两不同时到达时, 各进程直接进入临界区。

(2) 当N个进程同时到达时, 最后写gate2的进程首先进入临界区, 剩下N-1个进程最后写gate2的进程首先进入临界区。

断言6:N个进程的快速算法满足有限等待的原则。

证明:各个进程的平均等待的时间为O (N2) , 满足有限等待。

4. 快速算法的性能和优势分析

我们对快速算法的性能和优势总结以下几点。

(1) 总是有进程在临界区时, 不会出现进程申请进入临界区的服务号将无限变大 (unbounded number) 的情况, 因为快速算法n个进程情况没有用到服务号。

(2) 使用的共享变量只有N个, 即wait[0…N-1], 比bakery算法的2N个共享变量少N个, 大大减少在分布式环境下进程之间信息交换量。

(3) bakery算法中, 当没有别的进程进入临界区时, 本进程进入临界区之前要和N-1个进程的服务号进行比较, 而快速算法此情况下本进程直接进入临界区, 提高了速度;当有N个进程竞争进入临界区时, 快速算法中各个进程少max (Number[1], ..., Number[N]) 操作, 同时少本进程同其他进程号比较操作, 大大提高了进程的执行速度。

5. 结论

对bakery算法进行改进后的快速算法克服了服务号将无限变大 (unbounded number) 的弊端, 同时减少了分布式环境进程之间的信息交换量, 提高了进程的执行速度, 而且满足进程互斥设计时的互斥, 空闲让进、有限等待三要点。快速算法的引入将大大提高互联网上的资源共享的效率, 提高互联网应用程序的运行效率。

摘要：本文简要地介绍了bakery算法进程互斥思想, 指出它存在的三个缺点。然后在满足进程互斥设计三要点的前提下, 提出快速互斥算法, 并且对它的性能和优点给出证明, 指出快速算法能够很好地解决bakery算法的缺点。

关键词：bakery算法,快速算法,进程互斥,空闲让进有限等待

参考文献

[1]Chen, Y, Welch, J.Self-Stabilizing Mutual Exclusion Us-ing Tokens in Mobile Ad Hoc Networks.Proceedings of the6th in-ternational workshop on Discrete Algorithms and methods for mo-bile computing and communications, 2002:34-42.

[2]Sujata Banerjee.A New Token Passing Distributed Mutual Exclusion Algorithm.Proceedings of the Intl.Conf.on Distributed Computing Systems (ICDCS) , 1996.

互斥方案 篇5

逻辑函数的表示形式既可以采用基于" 与/或/非" 运算的传统Boolean形式和基于" XOR/AND"运算的Reed - Muller ( RM) 形式。在RM形式中, 由于" XOR" 运算具有模2 加功能, 且" XOR" 运算对输入的跳变十分敏感, 因此相比于用AND/OR结构形式实现的电路, 基于XOR/AND形式实现的逻辑电路在算术运算实现, 电路可测试性等方面有明显优势[1]。目前, 涉及RM逻辑的电路综合与优化已引起越来越多研究者的兴趣, 研究所涉及的内容包括RM逻辑的功耗优化、面积优化、延时优化等几个方面[2,3]。但无论是功耗、面积和延时优化, 固定极性的RM逻辑展开方法作为一种基本操作方法, 大量存在于RM逻辑电路极性优化过程中, 其转换速度对整体优化方案的效率有直接影响[4]。

在逻辑函数固定极性RM展开中常用的方法有系数表映射法、系数矩阵法、列表法等[5,6], 其中列表法因有较高的转换效率, 且便于计算机实现而常被采用。常用的列表法是基于最小项[7], 而逻辑函数的最小项数量与2n成正相关, 其中n是输入的变量数。因此基于最小项的列表法不适合对输入变量比较多的大电路进行固定极性RM逻辑表达式转化。在大电路的FPRM转化中, 文献[8, 9]分别给出了相应的快速算法。文献[8]的转换算法对于在处理输入冗余度很大 ( 即构成逻辑函数的乘积项中很多变量没有出现) 且多输出函数中每个乘积项对应的多个输出取"1" 的个数很少, 或者只有一个为"1" 这类逻辑函数具有很高的效率。文献[9]的方法是在结合基于最小项的列表法和文献[8]的方法的基础上提出的。该方法先将待转换的逻辑函数转化为不相交乘积项, 一般情况下, 逻辑函数的不相交乘积项的数量远小于最小项数, 因此文献[9]的方法可以处理更大的电路。但与其他列表技术一样, 都存在乘积项的展开和去重步骤, 因此当乘积项的数量很大时, 每一次乘积项的展开后的查重都是一个耗时的过程, 进而影响算法的效率。

本文通过引入乘积项的极性运算, 乘积项关于极性的位相交运算和乘积项位互斥运算, 结合不相交乘积项的性质, 提出了一种新的由" AND/OR" 形式逻辑函数表达式到固定极性" XOR/AND" 的RM表达式的转换方法。该方法可以实现大电路的"AND / OR" 形式向固定极性的" XOR / AND" 的RM表达式的转换, 且相比于文献[8, 9]的方法, 就有更快的运算速度, 并且实验显示, 本方法在实现同一电路的不同极性转化时, 运算的时间非常接近, 即算法对待转化电路的极性不敏感。由于极性转化是实现RM逻辑面积和功耗优化的关键步骤[10~12]。因此, 本文的方法将有助于大电路的RM逻辑功耗优化和面积优化。

2 基本概念

逻辑函数f可以表示为如下式所示的Reed -Muller ( RM) 形式:

在RM逻辑函数中, 变量可以以原变量形式出现, 也可以以反变量的形式出现。变量的这二种形式可以利用下式 ( 2) 来表示:

对于RM逻辑函数f, 利用上式可以使得f的任何一个变量xi, 在任何一个乘积项中, 它的取值形式保持一致。f的极性值用H表示, 其中H等于各个 δi构成的二进制的值。

定义1RM逻辑的固定极性表示。RM逻辑函数的每个变量只能以原变量或反变量中其中一种形式出现, 则展开式称为固定极性RM ( fixed polarity Reed - Muller, FPRM) 展开式。

定义2位极性运算。用Υk (pi, H) 表示乘积项pi与极性H之间的第k位"位极性"运算, 并规定当[pi]k=[H]k时, 有Υk (pi, H) =4, 否则Υk (pi, H) =[pi]k。

定义3乘积项关于极性H的位相交运算。用Λk ( pi, pj, H) 表示乘积项pi, pj关于极性H的第k位的相交运算, 并且规定 Λk ( 2, 4, 1) = 2, Λk ( 2, 4, 0) = 2, Λk ( 2, 2, 1) = 2, Λk ( 2, 2, 0) = 2, Λk ( 4, 2, 1) =0, Λk ( 4, 2, 0) = 1, Λk ( 4, 0, 1) = 2, Λk ( 4, 1, 0) = 1, 其他组合下的 Λk ( pi, pj, H) =Ø, 表示pi, pj不相交。

定义4乘积项关于极性H的位互斥运算。Γk ( Υk ( pi, H) , Υk ( pj, H) , H) 表示乘积项pi, pj关于极性H的第k位互斥运算, 其中 Υk ( pi, H) , Υk ( pj, H) 的取值为0, 1, 2 或4, H的取值为0 或1; 则规定Γk ( 4, 0, 1) = 2, Γk ( 4, 2, 1) = 0, Γk ( 4, 1, 0) = 2, Γk ( 4, 2, 0) = 1, Γk ( 4, 4, 1) = 4, Γk ( 4, 4, 0) = 4, 其他 Υk ( pi, H) , Υk ( pj, H) 和H组合, Γk ( Υk ( pi, H) , Υk ( pj, H) , H) 都没有意义, 用“/”表示。

3 逻辑函数FPRM转换技术

基于列表技术的逻辑函数的FPRM转换主要包含三个主要步骤, 即 ( 1) 将最小项或不相交项与极性表达式H进行位" XOR" 运算, 得到新的乘积项; ( 2) 对新的乘积项的某些变量进行展开, 得到另外的2s- 1 个乘积项, s为需要展开的变量的个数; ( 3) 成对去掉相同的乘积项, 即去重。上述3 个步骤中, 如果s比较大, 比如超过20, 则展开的乘积项的个数是百万级的, 而相同乘积项的去掉过程是在百万级数量的乘积项的搜索中实现的。因此步骤 ( 2) 和 ( 3) 是一个耗内存和耗时间的过程。而本文中, 上述算法中的步骤 ( 2) 和 ( 3) 通过乘积项的相交和互斥运算实现。转换算法步骤如下:

步骤1 将n变量逻辑函数f的所有乘积项转换为不相交乘积项, 得到f的不相交乘积项集合Cdis;

步骤2 利用位极性操作 Υk ( p, H) 运算, 完成Cdis中任意乘积项p中的每一个变量与极性表达式H中对应的值的位极性操作, 并将结果存于集合Cp中;

步骤3 在Cp中任取一个乘积项pi, 利用 Λk ( pi, pj, H) 检查pi与Cp中其他任意乘积项pj的相交情况, 若乘积项pi和pj中的任意一位变量都有 Λk ( pi, pj, H) ≠Ø, 则pi和pj相交, 否则pi和pj不相交。若pi和pj相交, 执行步骤4; 若pi和pj不相交, 执行步骤6;

步骤4 依次搜索pi中各位的取值, 如pi中第k位取值为4, 则生成一个新的乘积项pk, 其中乘积项pk的前 ( k - 1) 位为pi和pj相交的结果, 即 Λu ( pi, pj, H) , 0 ≤ u < k, pk的第k位的值为pi和pj顺序互斥的结果, 即 Γk ( Υk ( pi, H) , Υk ( pj, H) , H) , pk的第 ( k+ 1) 位到 ( n - 1) 位复制pi的第 ( k + 1) 位到 ( n -1) 位的值, 若pk≠ pi, 则将pk存于Cp中, 重复这个过程直到搜索完pi中的每一位变量;

步骤5 互换pi和pj的位置, 重复步骤4 的操作, 将新生成的乘积项全部存到Cp中, 并删除原来的乘积项pi和pj;

步骤6 重复步骤3 到步骤6 直到Cp中所有乘积项中任意二个都不相交为止;

步骤7 根据乘积项中"4" 的个数将各个乘积项进行展开, 各个乘积项展开的项数为2s个, 其中每个乘积项中取值为4 的位分别用"0" 和"1" 代替, 并以二进制方式展开, 并将展开位中取值与极性表达式H中对应位相同的位用" -" 替换, 同时将"2"对应的位也用" -" 替换, 得到的就是极性为H下的RM逻辑表达式。

步骤1 将f中各个乘积项分别转换为不相交乘积项, 例5 中, 各乘积项已经不相交, 因此得到Cdis={ ( 1201) , ( 0021) , ( 0210) } ;

步骤2 对Cdis中的各个乘积项进行如表4 所示的位极性运算, 得到Cp= { ( 1244 ) , ( 4024 ) , ( 4210) } ;

步骤3 判断Cp中任意两个乘积项是否相交。在Cp中, 由于乘积项p'1和p'2在变量x1对应的位有Λ1 ( p'1, p'2, H) = Λ1 ( 2, 0, 1) = , 因此乘积项p'1和p'2不相交; 检查乘积项p'1和p'3, 对于任意一位变量都有 Λk ( p'1, p'3, H) ≠Ø, 则p'1和p'3相交;

步骤4 和步骤5 对相交的乘积项p'1和p'3执行互斥运算, 具体过程见表5;

完成步骤4 和步骤5 后, Cp的内容更新为{ ( 4024) , ( 1224) , ( 1212) , ( 2210) } ;

步骤6 检查Cp中各个乘积项的相交情况, 发现Cp中任意乘积项都不相交;

步骤7 对Cp中各个乘积项取值为"4" 的位进行展开, 过程见表6。

由表7 得到极性为5 的RM表达式为: f ( x0, x1, x2, x3) = ⊕∑ ( 3, 4, 5, 8, 9, 10, 12, 13) , 对应的乘积项表示形式为{ ( 1 - - - ) , ( 1 - 1 - ) , ( 1 - -0) , ( - 0 - - ) , ( - 0 - 0) , ( 10 - - ) , ( 10 - 0) , ( -- 10) } , 与表6 的结果一致。

4 实验结果与分析

本文算法用C语言编程实现。所用的计算机配置为Windows XP操作系统3. 29GHz和2. 85GB的内存。表8 为本文的算法与文献[8]和文献[9]方法的比较结果。表中i/o /p表示测试电路的输入/输出/乘积项数, 文献[8]和[9]的结果用On -set个数来表述, 而本文用对应的FPRM表达式的乘积项个数来表示, 因此二者结果不一样。表格中的时间单位是s。表中" < 1ms" 表示算法显示的运算时间为0。在处理parity电路时, " - - " 表示文献[8]没有提供该电路的数据, 而用文献[9]的方法时, 超过600s还没有输出结果。

从表8 和表9 的结果可得出本文算法的特点: ( 1) 以不相交乘积项为基础实现逻辑函数的FPRM转化, 相比最小项为基础的列表法, 可以避免随着输入变量增长引起最小项数量指数级增加而导致算法效率低下甚至无法工作; ( 2) 从表7 可以看出, 列表法在完成乘积项的极性运算后, 有一个乘积项展开这个步骤。在表7 中是对p ⊕ H运算后取值为"0"的位进行二进制展开。因此, 当乘积项数量很多, 且p ⊕ H运算后, 每一项中" 0" 的个数很多时, 上述的展开过程会产生数量庞大的乘积项, 进而影响算法速度。电路parity就是这样一个电路, 它有16 位输入, 32768 个乘积项, 这些乘积项实际上是海明距为2 的最小项。因此用表7 所示的列表法在处理该电路时, 不但需要处理很多的乘积项数量很多, 而且p⊕ H运算后, 每一项展开后得到的新的乘积项也很多, 从而导致列表法在处理此类电路时效率很多, 甚至无法工作; ( 3) 本文的方法避开了列表法相同乘积项搜索和成对删除操作, 即去重。从表6 可以看出, 在本文算法中, 只需要对取值为"4" 的位进行二进制展开, 就可以得到对应的FPRM下的乘积项的表示形式。展开后的乘积项由于是互斥运算后的结果, 因此不可能相同, 所以可以省掉去重的步骤。上述的原因使得本文的算法在处理乘积项数量多, 输入变量数量大的电路时比列表法速度要快的原因; ( 4) 从表9 可以看出, 将同一个电路转化成不同极性下的FPRM表达式时, 本文算法耗时很接近, 即该算法的运算速度对待转换的极性不敏感。

5 结论

本文通过引入乘积项关于极性的位相交运算以及乘积项关于极性的位互斥运算, 并结合不相交乘积项的性质, 提出了一种新的从" AND/OR" 形式逻辑函数表达式到FPRM表达式的转换方法。该方法在实现大电路的FPRM表达式的转换过程中, 避开了以往列表法在完成乘积项的极性运算后乘积项展开以及相同乘积项搜索并成对删除去重等工作, 使得算法在满足能够处理大规模电路要求的同时仍能实现对乘积项数量较大电路的处理。实验结果表明, 本文算法在处理乘积项数量较多, 输入变量个数较大的函数运算速度更快。提出的算法在实现同一电路的不同极性转化时, 运算的时间非常接近, 即算法对待转化的极性不敏感。

摘要：针对目前将逻辑函数从AND/OR形式转化成固定极性Reed-Muller (FPRM) 过程中存在的不足, 通过引入乘积项关于极性的位互斥运算, 该文提出一种基于乘积项互斥运算的FPRM转换方法。该方法只需要对互斥运算后的乘积项进行展开, 就可以得到对应极性下的FPRM的表示形式, 省去了列表法中相同乘积项的搜索和删除过程。提出的算法用C语言编程实现, 并用MCNC标准电路进行测试。实验结果表明所提算法在处理输入变量个数较大的电路时运算速度更快, 并且算法对待处理电路的极性不敏感。

关键词：Reed-Muller (RM) 逻辑,固定极性,乘积项互斥运算,极性转换

参考文献

[2]Mc Kenzie L, Almaini A E A, Miller J F, et al.Optimization of Reed-Muller logic functions[J].International Journal of Electronics Theoretical and Experimental, 1993, 75 (3) :451-466.

[3]Lozano C C, Falkowski B J, Luba T.Fixed Polarity Linearly Independent Expansions for the Representation of Quaternary Functions[J].Multiple-Valued Logic and Soft Computing, 2012, 19 (4) :307-324.

[4]Wang Xiang, Lu Ying, Zhang Yi, et al..Probabilistic modeling during power estimation for mixed polarity Reed-Muller logic circuits[C].IEEE International Conference on Green Computing and Communica-tions, Beijing, China, 2013:1414-1418.

[5]张会红, 汪鹏君, 俞海珍.基于新型极性转换技术的XNOR/OR电路面积优化[J].电子与信息学报, 2012, 34 (7) :1767-1772.

[6]Jankovic D, Stankovic R S, Moraga C.Optimization of polynomial expressions by using the extended dual polarity[J].Computers, IEEE Transactions on, 2009, 58 (12) :1710-1725.

[7]李辉, 汪鹏君, 王振海.混合极性列表技术及其在MPRM电路面积优化中的应用[J].计算机辅助设计与图形学学报, 2011, 23 (3) :527-533.

[8]Wang L, Almani A E A.Fast conversion algorithm for very large Boolean functions[J].Electronics letters, 2000, 36 (16) :1370-1371.

[9]王玉花, 王伦耀, 夏银水.基于不相交项并行列表技术的FPRM实现[J].电子与信息学报, 2014, 36 (9) :2258-2264.

[10]Yang M, Xu H, Almaini A E A.Optimization of mixed polarity Reed-Muller functions using genetic algorithm[C]//Computer Research and Development (ICCRD) , 2011 3rd International Conference on.IEEE, 2011, 3:293-296.

[11]杨萌, 徐红英, Almaini A E.针对混合极性的并行表格技术的遗传算法[J].计算机辅助设计与图形学学报, 2011, 23 (11) :1938-1943.

互斥方案 篇6

在投资项目评价实践中, 投资主体常常面临的不是单个项目的决策, 而是一组项目群的取舍。由于受项目群中项目之间的非独立性、不可分性及资源的约束, 因此对项目群的决策比对单个项目的决策要复杂得多。根据构成项目群的项目之间的关系, 可以将它们划分为三种类型:独立型项目、互斥型项目和混合型项目。

所谓独立型项目是指构成项目群的各个项目之间的相容性, 只要没有资源约束, 它们就可以共存。

互斥型项目是指在项目群中, 能够且只能够选择其中的一个项目, 一旦选择了其中的任意一个项目, 就必须放弃其他项目, 不能同时选择两个或两个以上的项目。

混合型项目是指项目群由若干独立型项目组成, 而这些独立型项目又是依赖若干互斥型子项目来实现。对于没有资源约束的独立项目群的选择, 只需要考虑这些项目是否满足可行性的评价, 实际上和独立方案的评价没有差别。对于混合型项目群和有资源约束的独立方案项目群, 通过一定的转换, 可以将其转变为互斥型的项目群 (傅家骥, 2007) 。因此, 如果能够对互斥型方案的项目群进行科学的评价与选择, 就能够比较好地解决项目群方案的选优问题。

然而, 在互斥型项目群中往往在效率型指标值 (如IRR) 和价值型指标值 (如NPV) 之间存在冲突。比如某企业进行技术改造, 有两个方案可供其选择:A方案需要投资200万元, 经过测算每年可获得收益65万元, 受益期8年, 残值为0;B方案需要投资300万元, 经过测算每年可获得收益87万元, 受益期8年, 残值为0, 假定基准收益率为14%, 该企业到底应该选择哪个方案?

我们不难计算出A方案的净现值 (NPV) 和内部收益率分别为101.5万元及28%, B方案的净现值和内部收益率分别为103.6万元和23.7%。如何从A、B方案中做出科学的选择, 是我们在实际工作中经常遇到的问题, 虽然有不少文献对这样的问题进行了一些有价值的讨论, 但还不完善。本文提出了一种兼顾价值与效率的综合评价方法, 针对此问题进行了一些有意义的探索, 以期能够抛砖引玉。

二、文献综述

互斥方案的经济效果评价是寻求合理的经济技术方案的基本方法, 也是投资项目进行可行性研究及决策 (如选址、项目规模的确定、产品方案、工艺流程、主要设备选择等) 经常面临的问题, 是项目评估的重要组成部分。在国家计委和建设部1993年颁布的《建设项目经济评价方法与参数》第5章及评价方法说明中规定, 互斥方案评价以净现值法、差额内部收益率法作为标准。

余绪缨在其《管理会计学》中提出:互斥方案的选优, 要用差量分析原理进行方案比较, 增量投资如能获得规定达到的最低收益率, 则增量投资在经济上是可取的。从增量净现值看, 如果差额净现值 (△NPV) 大于等于零, 则投资较多的方案优, 反之则投资较小的方案优;从差额内部收益率看, 如果差额内部收益率 (△IRR) 大于等于零, 则投资较多的方案优, 反之则投资较小的方案优。

傅家骥教授在其《工业技术经济学》一书中也作了类似的论证。他提出, 对寿命周期相同的互斥方案, 可以用△NPV或△IRR来优选;对寿命周期不同的互斥方案, 可以采用净年值的方法来优选。

事实证明, 用△NPV或△IRR来优选, 与选择NPV大于等于0且NPV最大的方案最优的结论是一致的。因此, 无论是对寿命周期相同的互斥方案采用△NPV或△IRR来优选, 还是对寿命周期不同的互斥方案采用净年值的方法来优选, 其评选的基础都是基于价值型的指标, 忽视了效率型指标的评价。

三、模型构建及分析

既然对于寿命周期相同的互斥方案, 使用△IRR或△NPV与使用NPV完全一脉相承 (对于寿命周期不同的互斥方案, 一般都使用NAV法) , 那么其结论就必定相同。问题是这两种方法是否合理?

联系到前面的实例, A方案的净现值 (NPV) 和内部收益率 (IRR) 分别为101.5万元及28%, B方案的净现值 (NPV) 和内部收益率 (IRR) 分别为103.6万元和23.7%, △IRR为14.6%, △NPV为2.1万元。按照增量方法应该选B方案。然而从净现值的绝对值来看, A方案投资200万元, 在满足基准收益率为14%的前提下, 8年内获得附加收益现值101.5万元;而B方案投资300万元, 在满足基准收益率为14%的前提下, 8年内获得附加收益现值103.6万元。B方案多投资100万元, 比A方案仅多得收益现值2.1万元, 投资多50%, 而获得的收益现值仅多2.1/101.5=2%。试想, 如果面临资金紧缺的状况, 则不宜认为这个追加投资的方案是科学的。资源约束在现实生活中是普遍存在的, 如果我们在进行技术经济分析中无视资源有效的事实, 那是不妥的。

因此, 对互斥型方案进行比较与选择时, 既要考虑到赚钱的绝对额的多少——价值型指标值, 又应该考虑赚钱的效率的高低——效率型指标值。可行的办法就是视决策人对价值型指标和效率型指标的重视程度, 分别给出权重系数, 然后进行综合加权, 得到一个价值—效率综合指标, 通过综合指标值来决策 (姜向阳, 2003) 。

1. 建模方法及过程。

本文以NPV代表价值型指标、IRR代表效率型指标为例, 介绍这种综合评价方法的建模过程。当然, 价值型指标取净年值或净终值、效率型指标选用外部收益率或净现值率指数时, 其评价方法和过程也类似。

第一, 求出各方案的净现值, 并进行归一化处理。

第二, 求出各方案的IRR, 并进行归一化处理。

第三, 根据资金的精确程度依“9/9～9/1标度法”给出NPV和IRR相应的分值, 进而计算出权重。资金越紧缺, IRR的权重越大;资金越宽裕, NPV的权重越大。

第四, 计算各方案的综合值。

第五, 评判方案优劣并对方案进行选择, 综合得分分值大的方案优。

2. 实例分析。

某企业进行技术改造, 有两个方案可供选择:A方案需要投资200万元, 经过测算每年可获得收益65万元, 受益期8年, 残值为0;B方案需要投资300万元, 经过测算每年可获得收益87万元, 受益期8年, 残值为0。假定基准收益率为14%, 该企业到底应该选择哪个方案。

资金紧缺程度依9/9～9/1标度法给出, 假定资金极度紧缺, 则可得表2:

可求出方案A、B的综合值如下:

因为0.537>0.463, 因此选A方案。

假定资金极度充裕, 则可得下表3:

A、B方案的综合得分:

由于0.500 5>0.499 5, 因此选择B方案。

当项目的寿命周期不相等时, 可以将指标NPV用净年值NAV替代, 其他过程相同。

3. 结果分析。

当资金非常紧缺时, 投资者更加关注资金的使用效率, 因此选择A方案;当资金比较充裕时, 投资者更加关注资金的规模效应, 因此选择B方案。

资金稀缺程度不同, 决策者的选择亦有变化, 这是比较符合实际情况的。

四、结论

价值—效率综合评价方法较好地解决了价值型指标和效率型指标之间的矛盾, 决策者能够依据项目资金的供应状况, 兼顾价值和效率, 把客观数据和主观经验有机结合起来, 为决策者提供了一个比较实用的科学方法。如果互斥方案的寿命周期相同, 投资者对价值型指标选取既可用NPV又可用NAV, 结论一致;如果互斥方案的寿命周期不相同, 价值型指标一般应选用NAV指标。

摘要：现有的互斥方案评选方法使用较多的是增量净现值法和增量内部收益率法, 事实上它们选择的结果与运用NPV选择的结果别无二致, 均无法解决价值型指标和效率型指标之间的矛盾, 无法反映资金的充裕或紧缺状况。本文提出了一种兼顾价值与效率的综合评价方法, 旨在解决这类难题。

关键词：互斥方案,NPV,归一化

参考文献

[1].傅家骥.工业技术经济学.北京:清华大学出版社, 2007

[2].姜向阳.系统效应值法及其在投资决策中的应用.中国西部科技, 2003;4

互斥方案 篇7

关键词：分布式系统,资源共享,临界区,进程互斥

目前, 在计算机技术中, 分布式系统的应用非常广泛, 相对于传统的集中式系统, 分布式系统是若干独立计算机的集合, 这些计算机对于用户来说就像是单个相关系统。分布式系统最主要的目标是使用户能够方便地访问远程资源, 并且以一种受控的方式与其它用户共享这些资源。那么, 如何能使多个用户安全有效的访问共享资源, 就成了分布式系统设计中一个重要的课题。就实现而言, 分布式系统中每一个单独的计算机中都包含了至少一个相关进程, 而需要共享的资源相对于多个进程而言往往位于其他主机之内。因此, 如同单机系统中的多进程互斥, 对于资源共享的分布式系统, 仍不可避免地就要使用临界区编程。当一个进程必须访问 (主要是更新) 一个共享数据结构时, 它要先进入一个临界区以达到互斥, 在保证没有其他进程同时使用该共享数据结构的情况下, 才能访问该共享数据结构。本文对Andrew S.Tanenbaum等提出的分布式进程互斥算法做了部分改进, 改进后的算法减少了一个进程进入或退出一个临界区所需的消息数目, 减少了进程进入临界区的延迟, 同时也减少了某些进程崩溃对算法的影响。

1设计思想

本算法的工作过程如下:当一个进程想进入一个临界区时, 它构造一个消息, 其中包含它要进入的临界区的名字, 它自身的进程号及当前时间。然后, 它将该消息通过网络发给其他所有的进程。这里假设消息的传输是可靠的, 也就是说, 每个消息都能准确无误地发送到目的地。如果可能, 可以使用可靠的组通信来代替单个消息。

当一个进程接收到来自另一个进程请求进入某个临界区的消息时, 它根据自身与消息中请求的临界区的相关状态来决定它要采取的动作。首先, 我们定义以下三条规则:

(1) 若接收者不在临界区, 也不想进入临界区, 它就忽略这个消息, 不做任何应答。

(2) 若已有接收者已经在临界区中, 则它就向发送者发回一个NO消息, 表示不允许请求者进入该临界区, 同时将该请求放入等待队列中。

(3) 若接收者想进入临界区但尚未进入时, 它将对收到的消息的时间戳与包含在它自身发给其它进程的消息中的时间戳进行比较。时间戳最早的那个进程获胜[1]。如果收到的消息的时间戳比较早, 那么接收者进程进入等待状态或自阻塞, 同时也不向发送者做任何回复。如果收到的消息的时间戳晚于自己消息的时间戳, 那么, 它就把收到的消息放入它的等待队列中, 也不向发送者回复任何消息 (因为对方已知道自己的时间戳较晚, 已自阻塞) 。

在发送了请求进入临界区的消息之后, 进程等待回复, 如果没有任何其他进程回复给它NO消息, 同时它也没有收到任何早于它的时间戳的相同临界区请求消息, 根据我们前面的3条规则, 可以认为现在没有任何进程占用该临界区, 那么它就可以进入该临界区;相反, 如果它收到了消息NO, 说明此时已有进程占用该临界区, 那么它就继续等待或阻塞自己。当占用临界区的进程退出临界区时, 它检查等待该临界区的消息队列, 并向队列最前端的消息的属主进程发送OK消息, 以通知该进程临界区可用;如果得不到相应的回复, 它就继续寻找下一个消息直到有进程接收或队列为空。也就是说, 当前使用完毕临界区的进程必须通知等待该临界区的进程使用临界区, 如此一直传递直到结束。对于等待临界区而处于等待或阻塞状态的进程而言, 根据刚才的规则, 它将等到一个允许使用临界区的消息OK (来自它前一个进程) , 尔后它即可进入临界区。这里有一个问题, 即要求如果有回复消息 (比如NO消息) 话, 请求进程必须在足够快的时间内得到该消息, 否则请求进程就会误判, 从而“闯”入临界区, 互斥失败。要保证该现象不出现, 必须设定合理的进程等待时间, 这要根据物理网络的实时情况做具体分析。

下面我们分三种情况说明这种算法的原理。

第一种情况:没有任何冲突, 即没有任何进程当前占用临界区, 则请求临界区的进程得不到任何响应, 根据规则, 请求进程进入临界区。算法正常工作。

第二种情况:两个进程同时试图进入同一个临界区。设这两个进程分别为进程0和进程2。如图1所示。

(a) 两个进程同时希望进入同一个临界区; (b) 进程0具有最早的时间戳, 所以它获胜, 进程2自阻塞; (c) 当进程0退出临界区时, 它发送一个OK消息, 表示进程2现在可以进入临界区。

进程0给每个进程发送一个具有时间戳8的请求, 然而与此同时, 进程2给每个进程发送一个具有时间戳12的请求。除此之外, 没有其它进程要求占用该临界区, 也没有进程正在占用该临界区, 如图1 (a) 所示。进程1不想进入临界区, 所以它不理会这个消息。进程0和进程2都发现它们之间有冲突 (因为彼此都收到了对方的消息) , 然后都比较时间戳。进程0发现自己获胜了, 而且它没有收到任何不允许进入临界区的NO消息, 这时它把进程2的消息放入等待队列中, 然后自己进入临界区。同时进程2由于在时间戳比较中败北而自我阻塞, 如图1 (b) 所示。当进程0退出临界区时, 它把进程2的请求从队列中删除, 并给进程2发送一个OK消息, 允许进程2进入临界区, 则进程2被OK消息唤醒进入临界区, 如图1 (c) 所示。该算法之所以能工作是因为它规定了在产生冲突的情况下, 具有最早时间戳的进程获胜, 并且每个进程都对时间戳的顺序达成了一致。

第三种情况:仍然是有两个进程同时试图进入同一个临界区。但比上述第二种的情况稍有不同。如图2所示。

这一次, 进程2比进程0早发消息, 使得进程0在自己的发送请求之前收到了进程2的请求, 如图2 (a) , 这时, 进程0在知道临界区已经被占用的情况下仍然必须发出自己的请求消息, 其目的是为了能把自己排入等待队列。进程2在接收到进程0的请求时, 会发现自己已经在临界区中, 它就会给进程0发送一个NO消息, 同时把进程0的请求消息放入自己的等待队列中, 如图2 (b) 。下面的处理方式与前者相同, 进程0等待进程2退出的消息OK, 接过临界区的使用权, 如图2 (c) 。

(a) 进程2先发出临界区请求消息, 进程0时间戳比较失败; (b) 进程0仅仅给进程2发出临界区请求消息, 进程2以NO消息应答, 并把进程0排入等待队列; (c) 当进程2退出临界区时, 它发送一个OK消息, 表示进程0现在可以进入临界区。

对于其他情况, 譬如多个进程抢夺同一个临界区的情况, 基于时间戳的排序, 最后的结果和前两种情况相同, 此处不再赘述。

2接力算法的性能分析

由于本算法主要是对Tanenbaum等提出的分布式进程互斥算法的一个改进, 从而我们从分布式互斥算法的三个关键性质来考察该算法的性能, 并与前者做出比较。设该分布式系统中共有n个进程。首先, 某个需使用某临界区的进程使用该算法向其它每个进程发送1个请求进入消息, 这样需要n-1个请求进入消息, 回复消息最少0个 (没有回复, 临界区可用) , 最多1个NO消息 (临界区不可用) 或1个OK消息 (临界区被释放) , 总共有n-1～n+1个消息。则同样可计算得进入临界区前的延迟 (按消息数) 为n-1～n+1。

我们把该算法与Tanenbaum等提出的算法在性能上作比较, 如表1。

从表1可以看出, 本算法使用的消息数目要比Tanenbaum等提出的算法少将近一倍, 而且进程崩溃对算法的影响降低, 可以说, 在性能上本算法略优。

3本算法的不足之处

和Tanenbaum等人提出的算法一样, 这个算法仍然有它的不足之处, 如果发给请求临界区的进程的NO消息丢失, 就会造成请求进程的误解, 从而访问临界区。同样, 如果OK消息丢失, 就会造成等待进程的死等。因此, 我们要求每次消息传输都必须是有保障的, 不能丢失消息, 或者用应答来保证消息传输的可靠性。

4结论

本算法在改进Tanenbaum等提出的算法的基础上提出了新的有关于分布式系统中资源共享的互斥控制的思想及方法, 在系统内有较多进程需要访问临界区的时候, 该算法能大量节省网络通信的消息数量, 具有一定的实用性。但由于分布式系统本身的复杂性, 仍然有一些不足之处, 如前面提到的消息传输需要使用另外的机制来保障其可靠性等, 有待于进一步改进。

参考文献

[1]Tanenbaum A S, van Steen M.分布式系统——原理与范型.杨剑峰等译.北京:清华大学出版社, 2004

[2]Hamilton G, Kougiouris P.The spring nucleus:a microkernel for ob-jects.SMLI TR-93-14, April1993

[3]Ahamad M, Kordale R.Scalable consistency protocols for distributed services.IEEE Trans Par Distr Syst, 1999;10 (9) :70—97

[4]Anderson T, Dahlin M, Neefe J, et al.Serverless network file sys-tems.ACMTrans Comp Syst, 1996;14 (1) :41—79