1、可靠性设计
可靠性设计:一个系统由n级设备串联而成,为了增强可靠性,每级都可能并联了不止一台同样的设备。所以每级用的设备越多系统的可靠性越高。但是设备都是有成本的,假定设备Di的成本是ci,设计该系统允许的投资不超过c,那么,该如何设计该系统(即各级采用多少设备)使得这个系统的可靠性最高。试设计一个动态规划算法求解可靠性设计。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISPrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdsATOfd3bkFGazxCMx8VesATMfhHLlN3XnxCMwEzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5CNhFDO0YTOkVTZ1EmNygTZkBTO3EjMxYzN1gDZkNmZx8CX3AzLchDMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjL5M3Lc9CX6MHc0RHaiojIsJye.png)
2、例子
设计一个由设备D1,D2 ,D3 组成的三级系统。每台设备的成本分别为30元,15元和20元, 可靠性分别是0.9 , 0.8 和0.5 , 计划建立该系统的投资不得超过105元。假定, 若i级有mi台设备Di并联, 则该级的可靠性φ(mi) = 1-(1-ri)mi 。上述条件可以表示为: c=105; c1=30 , c2=15 , c3=20 ; r1=0.9 , r2=0.8 , r3=0.5。由此立即可得: u1=2 , u2 =3 ,u3 =3。
求解过程
Sij 表示对第i个设备选择 j 个
Si 包含了第i个设备所有可能的情况。
S(i,j),Si的值都是前面代表可靠性,后面代表价格。
支配:花了更多的钱,可靠性反而低,可以删除。
S11 = { (0 .9 , 30) } S12 = {( 0 .99 , 60) } 得S1 = { (0 .9 , 30) , ( 0 .99 , 60) } 由S21 = { (0 .72 , 45 ) , (0 .792 , 75) } S22 = {( 0 .864 , 60 )} S23 = {( 0 .8928 , 75) } 得S2 = { (0 .72 , 45 ) , (0 .864 , 60) , ( 0 .8928 , 75) } 注意: S22中已删去了由(0 .99 , 60 )所得到的序偶( 0 .9504 , 90) 。因为这只剩下15 元, 不足以让m3 = 1。 说明: 归并时由于( 0 .792 , 75 )受( 0 .864 , 60 )支配, 故舍去。 由 S31= { (0 .36 , 65 ) , (0 .432 , 80) , ( 0 .4464 , 95) } S32= { (0 .54 , 85 ) , (0 .648 , 100 )} |