动态规划应用举例 - 图文(8)

有两个约束条件，它的静态规划模型为：

max P??pi(ui)i?1n ?ncu?c;wu?w??ii?iii?1?i?1?u?0且为整数，i?1,2,?,n?in这是一个非线性整数规划问题，因ui要求为整数，且目标函数是非线性的。此问题用动态规划方法来解，比较容易。

为构造动态规划模型，根据两个约束条件，取二维状态变量，采用两个状态变量：

xk——由第k个到第n个部件所容许使用的总费用。 yk——由第k个到第n个部件所容许具有的总重量。

决策变量uk为部件k上装的备用元件数，这里决策变量是一维的。 这样，状态转移方程为：xk?1?xk-ukck;yk?1?yk?ukwk (1?k?n)

m??inxk?允许决策集合为 Dk(xk,yk)?uk:0?uk??/c?k,yk/w ???k最优值函数fk(xk,yk)为由状态xk和yk出发，从部件k到部件n的系统的最大可靠性。 因此，整机可靠性的动态规划基本方程为：

?fk(xk,yk)?max?pk(uk)fk?1(xk?ckuk,yk?wkuk)?uk?Dk(xk,yk)?? ? k?n,n?1,?,1?f(x,y)?1n?1n?1n?1??边界条件为1，这是因为xn?1、yn?1均为零，装置根本不工作，故可靠性当然为1。最后计算得f1(c,w)，即为所求问题的最大可靠性。

例8 某厂设计一种电子设备，由三种元件D1,D2,D3组成。已知这三种元件的价格和可靠性如表9-9所示，要求在设计中所使用元件的费用不超过105元。试问应如何设计使设备的可靠性达到最大(不考虑重

量的限制)。

表9-9

元件 D1 D2 D3 单位/元 30 15 20 可靠性 0。9 0。8 0。5 解 按元件种类划分为三个阶段，设状态变量sk表示能容许用在Dk元件至D3元件的总费用；决策

变量xk表示在Dk元件上的并联个数；pk表示一个Dk元件正常工作的概率，则(1?pk)k为xk个Dk元件不正常工作的概率。令最优值函数fk(sk)表示由状态sk开始从Dk元件至D3元件组成的系统的最大可靠性。因而有

xf3(s3)?f2(s2)?x3?max?1?(0.5)?1?x3??s3/20??1?x2??s2/15maxf1(s1)?max1?x1??s1/30??1?(0.2)??f(s?15x)? ????1?(0.1)??f(s?30x)???x2322x1211由于s1=105，故此问题为求出f1(105)即可。

而 f1(105)?max?1?(0.1)x1?f(105 ?30x)1?max?0.9f(75),0.99f(45),0.999f(15)2222?1?x1?3??但f2(75)?max?1?(0.2)x2?f3(75-15x2)?max?0.8f3(60),0.96f3(45),0.992f3(30),0.9984f3(15)?

1?x2?4??可是 f3(60)?max1?(0.5)x3max?0.5,0.75,0.875??0.875

1?x3?3f3(45)?max?0.5,0.75??0.75 f3(30)?0.5

f3(15)?0所以f2(75)?max?0.8?0.875,0.96?0.75,0.992?0.5,0.9984?0??max?0.7,0.72,0.496??0.72 同理 f2(45)?max?0.8f3(30),0.96f3(15)??max?0.4,0??0.4

f2(15)?0

故 f1(105)?max?0.9?0.72,0.99?0.4,0.999?0??max?0.648,0.396??0.648。 从而求得x1?1,x2?2,x3?2为最优方案，即D1元件用1个， D2元件用2个，D3元件用2个。其总费用为100元，可靠性为0。648。

五、排序问题

设有n个工件需要在机床A、B上加工，每个

工件都必须经过先A而后B的两道加工工序(见图9-1)。以ai、bi分别表示工件i(1?i?n)在A、B上的加工时间。问应如何在两机床上图9-1安排各工件加工的顺序，使在机床A上加工第一个工件开始到在机床B上将最后一个工件加工完为止，所用的加工总时间最少?

图9-1

下面用动态规划方法来研究同顺序两台机床加工n个工件的排序问题。

当加工顺序取定之后，工件在A上加工时没有等待时间，而在B上则常常等待。因此，寻求最优排序方案只有尽量减少在B上等待加工的时间，才能使总加工时间最短。设第i个工件在机床A上加工完毕以后，在B上要经过若干时间才能加工完，故对同一个工件来说，在A、B上总是出现加工完毕的时间差， 我们以它来描述加工状态。 …… 此处隐藏：52字，全部文档内容请下载后查看。喜欢就下载吧 ……