文档章节

动态规划---->可靠性设计

小强斋太
 小强斋太
发布于 2016/11/09 20:06
字数 720
阅读 3
收藏 0

1、可靠性设计

可靠性设计:一个系统由n级设备串联而成,为了增强可靠性,每级都可能并联了不止一台同样的设备。所以每级用的设备越多系统的可靠性越高。但是设备都是有成本的,假定设备Di的成本是ci,设计该系统允许的投资不超过c,那么,该如何设计该系统(即各级采用多少设备)使得这个系统的可靠性最高。试设计一个动态规划算法求解可靠性设计。

如果第i级的设备Di的台数为mi,那么这mi台设备同时出现故障的概率为(1-ri)mi ,从而第i级的可靠性就变成1-(1-ri)mi 。例如,假定ri=0.99 ,mi=2,于是这一级的可靠性就是0.9999。不过在任何实际系统中, 每一级的可靠性要比1-(1-ri)mi 小一些, 这是由于这些开关线路本身并不是完全可靠的, 而且同一类设备的失误率也不可能是完全独立的(例如, 由于设计不当所造成的失误) 。基于以上分析, 不妨假设第i 级的可靠性由函数φ(mi)给定, 1≤i≤n 。由于系统中每种设备至少有一台,用ui表示最多的台数。

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 )}

S33=  { (0 .63 , 105) }

得S3 = { (0  .36 , 65 ) , (0 , 432 , 80) , ( 0 .54 , 85) , ( 0 .648 , 100) }

最优设计有0  .648 的可靠性, 需用资金100 元。通过对这些Si 的回溯, 求出m1 = 1 ,  m2= 2 , m3 = 2 。

本文转载自:http://www.cnblogs.com/xqzt/archive/2013/05/14/5637094.html

共有 人打赏支持
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
私信 提问
算法设计与分析(二)之动态规划

第一篇: 算法设计与分析之分治思想 动态规划(Dynamic Programming) 求解过程是多阶段决策过程,每步处理一个字问题,可用于求解组合优化问题 适用条件:问题要满足优化原则或最优子结构性质...

wenhui12345
2017/11/12
0
0
算法设计策略----动态规划法

动态规划法:与贪心法类似,动态规划法也是一种求解最优化问题的算法设计策略。它也采取分布决策的方法。但与贪心法不同的是,动态规划法每一步决策依赖子问题的解。直观上,为了在某一步做出...

Superheros
03/10
4
0
常用算法和复杂度总结

一、常用算法和复杂度 算法 名称 复杂度 备注 快速排序 QuickSort(A,p,r) 最坏:O(n2) 平均:O(nlog n) 均衡划分:O(nlog n) 合并排序 MergeSort(A,p,r) O(nlog n) 选最大 FindMax O(n) 选最...

啊莱
2010/01/03
0
0
递归和动态规划

递归算法就是通过解决同一问题的一个或多个更小的实例来最终解决一个大问题的算法。为了在C语言中实现递归算法,常常使用递归函数,也就是说能调用自身的函数。递归程序的基本特征:它调用自...

LoSingSang
03/12
0
0
分治法,动态规划及贪心算法感悟

分治法,动态规划法,贪心算法这三者之间有类似之处,比如都需要将问题划分为一个个子问题,然后通过解决这些子问题来解决最终问题。但其实这三者之间的区别还是蛮大的。 1.分治法 分治法(d...

努力的C
2017/10/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

SRE的含义及与 DevOps 如何关联?

虽然站点可靠性工程师(site reliability engineer SRE)角色在近几年变得流行起来,但是很多人 —— 甚至是软件行业里的 —— 还不知道 SRE 是什么或者 SRE 都干些什么。为了搞清楚这些问题...

linuxCool
12分钟前
1
0
月入3万之一个程序员的转行坎坷历程

陈年往事 “我月入3万,怎么会少少了你一个鸡蛋啊?” 这是2017年9月左右的一个新闻,一位煎饼摊大妈因和顾客争执时脱口而出这样一句话而走红。当时还上了各大新闻的头条。 互联网兴起今天,...

苏南-首席填坑官
34分钟前
1
1
OSChina 周一乱弹 —— 眼看着这颗陨石砸了下来

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子:分享Nachtblut的单曲《Antik》 《Antik》- Nachtblut 手机党少年们想听歌,请使劲儿戳(这里) @mr_chip :上海的初雪之后有点冷 ...

小小编辑
59分钟前
266
7
Confluence 6 修改导航显示选项

选择 子页面(Child pages)来在边栏中查看当前页面的子页面。 选择 页面树(Page tree)来查看整个空间的页面树,扩展当前的页面。 你也可以选择是否完全隐藏导航显示选项或者添加你希望可见...

honeymose
今天
2
0
Ubuntu18.04 安装MySQL

1.安装MySQL sudo apt-get install mysql-server 2.配置MySQL sudo mysql_secure_installation 3.设置MySQL非root用户 设置原因:配置过程为系统root权限,在构建MySQL连接时出现错误:ERROR...

AI_SKI
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部