运筹学课程实习

福建农林大学计算机与信息学院

（数学类课程）

课程名称： 课程论文题目：姓 名：

系： 专 业： 年 级： 学 号: 指导教师： 职 称： 课程实习报告

运筹学 系统的可靠性分析

黄明清 应用数学 数学与应用数学

2009 091153033 尤添革 副教授

2011年 12 月1日

系统的可靠性分析

摘要：众所周知，系统不可能是完美的，总是会存在一定的不足，所以我们就不断地完善这个不足，从而提高这个系统的可靠性。通常一个系统的可靠性是受很多的因素影响的，本文章就是将问题理想化，假设了影响系统可靠性的因素只有两个，通过建立数学模型，运用运筹学中的动态规划的思想来解决问题。当然，还对模型推广了，当影响可靠性的因素增加了，那么还是可以利用这个理论去解决，可以利用数学中的降维的方法化为二维的方法求解，这样的方法对我们的实际生活是很有用的。所以通过这个项目，我学会了数学领域与管理学领域的综合，这样对我的知识以及对付实际问题的能力有了更大的提升。本文主要研究了复合系统工作可靠性分析的问题，根据串联系统可靠性的概率值和备用元件的重量双重约束，建立二维的线性整数规划模型，并且运用运筹学中动态规划思想去求问题的解。 关键词：动态规划；可靠性；LINGO

- 1 -

1 问题的提出

若某种机器的工作系统由n个部件串联组成，只要有一个部件失灵，整个系统就不能工作。为提高系统工作的可靠性，在每一个部件上均装有主要元件的备用件，并且设计了备用件自动投入装置。显然备用元件越多，整个系统正常工作的可靠性越大。但备用元件多了，整个系统的成本、重量、体积均相应加大，工作精度也降低。因此，最优化问题是在考虑上述限制条件下，应如何选择各部件的备用元件数，使得整个系统的工作可靠性最大。假设某系统由3个工作部件A、B、C串联而成，3个部件的工作是相互独立的。以下表-1是各部件的故障率，以及增加备用件的单价，如何配置才能使得系统的效率最高。

表-1

故障率

部件单价(万元) 2 问题分析

A 0.3 2 B 0.2 3 C 0.4 1

设部件i(i1,2,,....,n)上装有z1个备用元件时，它正常工作的概率为pi(zi)。因此整个系统正常工作的可靠性，可用它正常工作的概率来衡量，即

ppi(zi)i1n (1)

设装一个部件i的费用为ci，重量为wi，要求总费用不超过C，总重量不超过W，则这个问题的静态规划模型为

Maxppi(zi)i1ns..tczi1ni1niiCWwziizi0,ziZ (2)

这是一个整数规划问题，因zi要求为整数，且目标函数是非线性的，所以该问题属于非线性整数规划问题。而此类问题是较为复杂的问题，但是采用动态规划求解较为方便。 3 模型建立

为利用动态规划求解规划问题,就要构造动态规划模型,根据总费用与总重量这两个约束条件,就可取二维状态变量,采用两个状态变量符号xk,yk来表达,其中

xk表示由第k到n个部件所容许使用的总费用；

- 2 -

yk表示由第k到n个部件所容许使用的总重量。

决策变量uk为部件k上装的备用元件数，这里的决策变量是一维的。 这样，状态转移方程为：

xk1xkukckyk1ykukwk允许决策集合为

(1kn) (3)

Dk(xk,yk){uk:0ukmin([xk/ck],[yk/wk])} (4)

最优值函数fk(xk,yk)为状态xk和yk出发,从部件k到n的系统的最大可靠性。 因此，整个系统的动态规划基本方程为：

fk(xk,yk)max[pk(uk)fk1(xkckuk,ykwkuk)]ukDk(xk,yk) (5) kn,n1,2,1f(x,y)1n1n1n1边界条件为1，这是由于xn1,yn1均为零，转置根本不工作，故可靠性当然为1。最后计算得到的f1(c,w)即为所求系统的最大可靠性。 4 模型求解

由上面的数据可以知道这个具体实例的一些关于动态规划的基本概念以及参数。 （1）阶段数，这个案例可划分为3个决策阶段，第1阶段对配备部件A做出决策，第

2阶段对配备部件B做出决策，第3阶段对配备部件C做出决策，故n3。 （2）状态变量sk，表示第k阶段可用来购买部件的金额。

（3）决策变量uk，表示第k阶段配备部件数；ck表示阶段k部件的单价，c12,

c23,c31；pk为k阶段单个部件的故障率，p10.3,p20.2,p30.4。

因为目标是使得系统正常工作概率最大，所以直接指标取各阶段配备uk个部件时正常工作概率是d(pk,uk)1(pk)uk。 （4）状态转移方程，sk+1=skckuk。 （5）递推方程。设

- 3 -

fk(sk)maxVk(sk,uk) （6）

s1ukkckukZ式子中Vk(sk,uk)具有递推关系

Vk1(sk1,uk1)Vk(sk,uk)d(pk,uk) （7） V4(s4,u4)=1，s1=10于是利用逆序求法可知，当k=3时，由式子（6）、（7）可得

f(sk)max{d(p3,u3)}max{1(p3)u3}s1u33c3u3Z1u3s3u3Z （8）

331(p3)10.4,u3*s3ss即余下的资金全部用于购买部件C。

当k=2时，部件C至少各配备一个，也就是s31，由状态转移方程得到1s3s2c2u2，所以有

s211u2,u2Z （9）

c2于是由式子（6）、（7）、（9）可得

f2(s2)max{d(p2,u2)f3(s3)}max{d(p2,u2)f3(s2c2u2)}s11u22c2u2Zs11u22c2u2Zmax{(1(p2)u2)f3(s23u2)}s11u223u2Z（10）

因为部件B和部件C至少各配备一个，所以状态变量s2不得小于4，且部件A也至少配备一个，所以s2也不会大于8。于是对式子（10）分别用s2=4,5,6,7,8带入，计算f2(s2)的值。

f2(4)max{(1(p2)u2)f3(43u2)}(10.2)f3(1)411u23u2Z

*0.8(10.4)0.48,u2(4)1 - 4 -

f2(5)max{(1(p2)u2)f3(53u2)}(10.2)f3(2)511u23u2Z

*0.8(10.42)0.672,u2(5)1f2(6)max{(1(p2)u2)f3(63u2)}(10.2)f3(3)611u23u2Z*0.8(10.43)0.7488,u2(6)1f2(7)max{(1(p2)u2)f3(73u2)}=max{(10.2)f3(4),(10.22)f3(1)}711u23u2Z*max{0.8(10.44),(10.22)(10.4)}0.77952,u2(7)1f2(8)max{(1(p2)u2)f3(83u2)}=max{(10.2)f3(5),(10.22)f3(2)}811u23u2Z

*max{0.8(10.45),(10.22)(10.42)}0.8064,u2(8)2当k=1时，部件B和部件C至少各配备一个，即s24，所以4s2s1c1u1，所以

s41u11,u1Z （11）

c1于是由式子（6）、（7）、（11）可得到

f1(s1)max{d(p1,u1)f2(s2)}=max{d(p1,u1)f2(s1c1u1)}s41u11c1u1Zs41u11c1u1Z

max{(1(p1)u1)f2(s1c1u1)}s41u11c1u1Z （12）

因为用于购买部件的金额为10万元，即s110，所以

f1(10)max{d(p1,u1)f2(s2)}=max{(1(p1)u1)f2(102u1)}1041u12u1Z1u13u1Zmax{(10.3)f2(8),(10.32)f2(6),(10.33)f2(4)}max{(10.3)0.8064,(10.32)0.7488,(10.33)0.48}0.681408,u1*(10)25 结果分析

- 5 -

* 由上述的计算可以可得u12，即应该配备部件A为2个；由状态转移方程可得**s2s1c1u11022=6，从而可从f2(6)得出u21，即应该配备部件B为1个；再由***状态转移方程可得s3s2cu2所以u3即应该配备部件C为3个。631=3，s33，

故最佳决策p*(2,1,3)，整个系统的可靠性为f1(s1)0.681408，达到最大。 6 模型检验

由于上述的动态计算也是可以利用数学软件LINGO去求解,于是可以通过编程求解,求解的程序如下。

sets:

part/A,B,C/:c,p,x; endsets data: c=2 3 1; b=10;

p=0.3 0.2 0.4; enddata

max=@prod(part:1-p^x); @sum(part:c*x)<=b; @for(part:@gin(x));

求解结果为

Local optimal solution found.

Objective value: 0.6814080 Extended solver steps: 7 Total solver iterations: 338

Variable Value Reduced Cost B 10.00000 0.000000 C( A) 2.000000 0.000000 C( B) 3.000000 0.000000 C( C) 1.000000 0.000000 P( A) 0.3000000 0.000000 P( B) 0.2000000 0.000000 P( C) 0.4000000 0.000000 X( A) 2.000000 0.4245478E-02 X( B) 1.000000 -0.1460949 X( C) 3.000000 0.000000

Row Slack or Surplus Dual Price 1 0.6814080 1.000000

- 6 -

2 0.000000 0.4269187E-01

结果分析：由求解结果可得知部件A应并联配备2个元件，部件B应并联配备1个元件，部件C应并联配备3个元件，这样整个系统的串联的可靠性达到最大，为0.681408，所以通过这个检验可知，原模型的计算是可行的。 参考文献

[1] 谢金星．优化建模与LINDO/LINGO软件.北京:清华大学出版社,2005. [2] 张杰等．运筹学模型与实验．北京:中国电力出版社,2007.

[3] 《运筹学》教材编写组．运筹学.北京：清华大学出版社，2007

[4] 段东立，武小悦， 邓宏钟.基于时变故障率与服务恢复时间模型的配电系统可靠性评估．中国电机工程学报．2011，31（28），-57-64

- 7 -