数学建模
nMaxZ??pk(uk)k?1
（1）
s.t.?cukk?1nk?C,uk为非负整数
（2）
这个非线性规划转化为动态规划求解比较方便。
按照对n个部件装置备用件的次序划分阶段，决策变量仍为部件
k的备用件数量uk，而状态变量选取装配部件k之前所容许使用的费
用，记作xk，于是状态转移方程为
xk?1?xk?ckuk
（3）
最优值函数fk(xk)定义为状态xk下，由部件k到部件n组成的子系统的最大正常工作概率，它满足
fk(xk)?Max[pk(uk)?fk?1(xk?1)]uk?Uk(xk)
（4）
Uk(xk)?{ukuk?[0,xk/ck ],0?xk?C,k?n，?，2，1
fn?1(xn?1)?1且为正整数},
（5）
注意，这个动态规划模型的最优方程（4）中，阶段指标pk(uk)与最优值函数fk?1(xk?1)之间的关系是相乘，而不是例13~15中的相加，这是由“两事件之交的概率等于两事件概率之积”这一性质决定的。与此相应，最优值函数的初始条件fn?1(xn?1)?1等于1。
例16 任务均衡问题。一批任务由若干设备完成，问题是如何均衡地向每个设备分配各项任务，使这批任务尽早地完成。例如一高层
【最新整理，下载后即可编辑】
数学建模
（设N层）办公大楼有n部性能相同的电梯，为了在早高峰期间尽快地将乘客送到各层的办公室，决定各部电梯分段运行，即每部电梯服务一定的层段。假定根据统计资料，已知一部电梯从第i层次开始服务j层所需要的时间为tij，问如何安排这些电梯服务的层段，使送完全部乘客的时间最短。
按照由下而上安排电梯服务层次的序号划分阶段k?1,2,?,n。第k部电梯（即第k阶段）开始服务的层次为状态xk，它服务的层数为决策uk，满足 当xk
xk?1?xk?uk
（1）
?i，uk?j时，已知第k部电梯服务的时间为vk(xk,uk)?tij。因为对
于第k,l两部电梯而言，总的服务时间为Max[vk(xk,uk),vl(xl,ul)]，所以最优值函数fk(xk)（即从第k部到第n部电梯总的最短服务时间）满足
fk(xk)?min{max[vk(xk,uk),fk?1(xk?1)]}
uk?Uk(xk)Uk(xk)?{uk|uk?1,2,?,N?xk?(n?k)?1}
xk?2,3,?,Nk?n,?,2,1
（2）
fn?1(n?1)?0
（3）
这里我们假定每部电梯至少服务1层，且从第2层起开始服务。 应用动态规划方法求解多阶段决策问题分为两个步骤。第一是应用动态规划基本方程，逆序地求出条件最优目标函数值集合和条件最优决策集合。第二是顺序地求出最优决策序列。下面以一个例子加以说明。
例17 机器负荷分配问题。某种机器可以在高低两种不同的负荷下进行生产。在高负荷下生产时，每台机器生产产品的年产量为7吨，
【最新整理，下载后即可编辑】
数学建模
年折损率a?0.7（即若年初完好的机器有u台，则年终完好的机器数为au台），在低负荷下生产时，每台机器生产产品的年产量为5吨，年折损率b?0.9。若开始时完好的机器数有x1?1000台，要求制定一个三年计划，在每年开始时，决定如何重新分配在两种不同的负荷下生产的完好机器数，使在三年内产品的总产量达到最大。
设第k年初完好的机器数为xk，分配给高负荷下生产的机器数为
uk，即在低负荷下生产的机器数为xk-uk。这里uk、xk可取非负实数，
如xk?0.7表示第k年度一台机器正常工作时间只占0.7。于是第k?1年
初完好的机器数
xk?1?0.7uk?0.9(xk?uk)?0.9xk?0.2uk
第k年度的产量
vk(xk,uk)?7uk?5(xk?uk)?5xk?2uk
设三年总产量为V，则问题即求解下面的线性规划问题：
MaxV??(5xk?2uk)
k?13
s.t.x1?1000
xk?1?0.9xk?0.2uk,0?uk?xk,k?1,2,3
现用动态规划来解。本题要求的是已知第一年度初拥有的完好机器数x1?1000台，用最优方案到第三年度末这段期间的产品产量，将它记为f1(x1)。为此先求：已知第j年度初拥有的完好机器数xj，用最优方案到第三年末这段期间的产品产量，将它记为fj(xj),动态规划的基本方程
?fk(xk)?Max[vk(xk,uk)?fk?1(xk?1)]0?uk?xk?xk?1?0.9xk?0.2uk,k?1,2,3??f(x)?0?44j?2,3，列出
求解过程如下：
【最新整理，下载后即可编辑】
数学建模
（1）
f3(x3)?Max[v3(x3,u3)?f4(x4)]
0?u3?x3
*即f3(x3)?0Max(2u3?5x3)，得最优解u3?u?x33?x3，从而f3(x3)?7x3。
[v2(x2,u2)?f3(x3)] f2(x2)?0Max?u?x22（2）
即f2(x2)?0Max[2u2?5x2?7(0.9x2?0.2u2)]?Max(0.6u2?11.3x2)， ?u?x0?u?x2222*得最优解u2?x2，从而f2(x2)?11.9x2。
f1(x1)?Max[v1(x1,u1)?f2(x2)]0?u1?x1
（3）
即f1(x1)?0Max[2u1?5x1?11.9(0.9x1?0.2u1)]?Max(?0.38u1?15.71x1)， ?u?x0?u?x1111得最优解u1*?0，从而f1(x1)?15.71x1。
已知x1?1000，则原问题的最优值为f1(x1)?15710。 顺序求出原问题的最优解为
***?x3?0.9x2?0.2u2?630 ?x2?0.9x1?0.2u1?900，u3u1?0，u2即第一年度应把年初全部完好机器投入低负荷生产，后两年每年应把年初全部完好机器投入高负荷生产，这样所得的三年总产量最高，为15710吨。
【最新整理，下载后即可编辑】
数学建模案例分析--最优化方法建模6动态规划模型举例(完整资料).doc
