当k?4时：
由结点M31到达目的地有两条路线可以选择，即选择P1或P2；故：
?8?f4(S4?M31)?min???6 选择P2
?6?由结点M32到达目的地有三条路线可以选择，即选择P1、P2或P3；故：
?4???f4(S4?M32)?min?3??3 选择P2
?7???由结点M33到达目的地也有三条路线可以选择，即选择P1、P2或P3；故：
?7???f4(S4?M33)?min?6??5 选择P3
?5???由结点M34到达目的地有两条路线可以选择，即选择P2或P3；故：
?3?f4(S4?M34)?min???3 选择P2
?4?
当k?3时：
由结点M21到达下一阶段有三条路线可以选择，即选择M31、M32或M33；故：
?10?6???f3(S3?M21)?min?7?3??10 选择M32
?6?5???由结点M22到达下一阶段也有三条路线可以选择，即选择M31、M32或M33；故：
?9?6???f3(S3?M22)?min?7?3??10 选择M32或M33
?5?5???由结点M23到达下一阶段也有三条路线可以选择，即选择M32、M33或M34；故：
?11?3???f3(S3?M23)?min?4?5??9 选择M33或M34
?6?3???当k?2时：
由结点M11到达下一阶段有两条路线可以选择，即选择M21或M22；故：
?8?10?f2(S2?M11)?min???16 选择M22
?6?10?由结点M12到达下一阶段也有两条路线可以选择，即选择M22或M23；故：
?9?10?f2(S2?M12)?min???19 选择M22
11?9??当k?1时：
由结点C到达下一阶段有两条路线可以选择，即选择M11或M12；故：
?12?16?f1(S1?C)?min???28 选择M11
10?19??从而通过顺序（计算的反顺序）追踪（黑体标示）可以得到两条最佳的输运线路：C—
M11—M22—M32—P2；C—M11—M22—M33—P3。最短的输送距离是280千米。
2-2资源分配问题 所谓资源分配问题，就是将一定数量的一种或若干种资源（如原材料、机器设备、资金、劳动力等）恰当地分配给若干个使用者，以使资源得到最有效地利用。设有m种资源，总量分别为bi（i = 1,2,?,m），用于生产n种产品，若用xij代表用于生产第j种产品的第i种资源的数量（j = 1,2,?,n），则生产第j种产品的收益是其所获得的各种资源数量的函数，即gj = f（x1j,x2j,?, xmj）。由于总收益是n种产品收益的和，此问题可用如下静态模型加以描述：
maxz??gj
j?1n?xj?1nij?bi (i?1,2,?,m)
xij?0 (i?1,2,?,m;j?1,2,?,n)
若xij是连续变量，当gj = f（x1j,x2j,?, xmj）是线性函数时，该模型是线性规划模型；当gj = f（x1j,x2j,?, xmj）是非线性函数时，该模型是非线性规划模型。若xij是离散变量或（和）gj = f（x1j,x2j,?, xmj）是离散函数时，此模型用线性规划或非线性规划来求解都将是非常麻烦的。然而在此情况下，由于这类问题的特殊结构，可以将它看成为一个多阶段决策问题，并利用动态规划的递推关系来求解。
本教材只考虑一维资源的分配问题，设状态变量Sk表示分配于从第k个阶段至过程最终（第N个阶段）的资源数量，即第k个阶段初资源的拥有量；决策变量xk表示第k个阶段资源的分配量。于是有状态转移律：
Sk?1?Sk?xk
允许决策集合：
Dk(Sk)?{xk|0?xk?Sk}
最优指标函数（动态规划的逆序递推关系式）：
fk(Sk)?max{gk(xk)?fk?1(Sk?1)} (k?N,N?1,N?2,?,1)
0?xk?SkfN?1(SN?1)?0
利用这一递推关系式，最后求得的f1(S1)即为所求问题的最大总收益，下面来看一个具体的例子。
[例7-2] 某公司拟将500万元的资本投入所属的甲、乙、丙三个工厂进行技术改造，各工厂获得投资后年利润将有相应的增长，增长额如表7-1所示。试确定500万元资本的分配方案，以使公司总的年利润增长额最大。
表7-1 投资额 甲 乙 丙 100万元 200万元 300万元 400万元 500万元 30 50 40 70 100 60 90 110 110 120 110 120 130 110 120 解：将问题按工厂分为三个阶段k?1,2,3，设状态变量Sk（k?1,2,3）代表从第k个工厂到第3个工厂的投资额，决策变量xk代表第k个工厂的投资额。于是有状态转移率
Sk?1?Sk?xk、允许决策集合Dk(Sk)?{xk|0?xk?Sk}和递推关系式：
fk(Sk)?max{gk(xk)?fk?1(Sk?xk)} (k?3,2,1)
0?xk?Skf4(S4)?0
当k?3时：
f3(S3)?max{g3(x3)?0}?max{g3(x3)}
0?x3?S30?x3?S3?于是有表7-2，表中x3表示第三个阶段的最优决策。
表7-2 （单位：百万元） S3 ? x30 0 0 1 1 0.4 2 2 0.6 3 3 1.1 4 4 1.2 5 5 1.2 f3(S3) 当k?2时：
f2(S2)?max{g2(x2)?f3(S2?x2)}
0?x2?S2于是有表7-3。
表7-3 （单位：百万元） x2 g2（x2）+f3（s2 - x2） 0 0+0 0+0.4 0+0.6 0+1.1 0+1.2 0+1.2 1 0.5+0 0.5+0.4 2 1.0+0 3 1.1+0 4 1.1+0 5 S2 0 1 2 3 4 5 f2(S2) 0 0.5 1.0 1.4 1.6 2.1 ? x20 1 2 2 1，2 2 0.5+0.6 1.0+0.4 0.5+1.1 1.0+0.6 1.1+0.4 0.5+1.2 1.0+1.1 1.1+0.6 1.1+0.4 1.1+0 当k?1时：
f1(S1)?max{g1(x1)?f2(S1?x1)}
0?x1?S1于是有表7-4。
表7-4 x1 g1（x1）+f2（s1 – x1） 0 0+2.1 1 2 3 4 5 0.3+1.6 0.7+1.4 0.9+1.0 1.2+0.5 1.3+0 S1 5 f1(S1) 2.1 ? x10，2 然后按计算表格的顺序反推算，可知最优分配方案有两个：（1）甲工厂投资200万元，
乙工厂投资200万元，丙工厂投资100万元；（2）甲工厂没有投资，乙工厂投资200万元，丙工厂投资300万元。按最优分配方案分配投资（资源），年利润将增长210万元。
这个例于是决策变量取离散值的一类分配问题，在实际问题中，相类似的问题还有销售店的布局（分配）问题、设备或人力资源的分配问题等。在资源分配问题中，还有一种决策变量为连续变量的资源分配问题，请见例7-3。
[例7-3] 机器负荷分配问题。某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量（件）函数为g1?8x，其中x为投入高负荷生产的机器数量，年度完好率??0.7（年底的完好设备数等于年初完好设备数的70%）；在低负荷下生产的产量（件）函数为g2?5y，其中y为投入低负荷生产的机器数量，年度完好率??0.9。假定开始生产时完好的机器数量为1000台，试问每年应如何安排机器在高、低负荷下的生产，才能使5年生产的产品总量最多？
解：设阶段k表示年度（k?1,2,3,4,5）；状态变量Sk为第k年度初拥有的完好机器数量（同时也是第k?1年度末时的完好机器数量）。决策变量xk为第k年度分配高负荷下生产的机器数量，于是Sk?xk为该年度分配在低负荷下生产的机器数量。这里的Sk和xk均为连续变量，它们的非整数值可以这样理解：如Sk?0.6就表示一台机器在第k年度中正常工作时间只占全部时间的60%；xk?0.3就表示一台机器在第k年度中只有30%的工作时间在高负荷下运转。状态转移方程为：
Sk?1??xk??(Sk?xk)?0.7xk?0.9(Sk?xk)?0.9Sk?0.2xk
允许决策集合：
Dk(Sk)?{xk|0?xk?Sk}
设阶段指标Qk(Sk,xk)为第k年度的产量，则：
Qk(Sk,xk)?8xk?5(Sk?xk)?5Sk?3xk
过程指标是阶段指标的和，即：
Qk~5??Qj
j?k5令最优值函数fk(Sk)表示从资源量Sk出发，采取最优子策略所生产的产品总量，因而有逆推关系式：
fk(Sk)?max{5Sk?3xk?fk?1(0.9Sk?0.2xk)}
xk?Dk(Sk)边界条件f6(S6)?0。
当k?5时：
f5(S5)?max{5S5?3x5?f6(S6)}?max{5S5?3x5}
0?x5?S50?x5?S5?因f5(S5)是关于x5的单调递增函数，故取x5?S5，相应有f5(S5)?8S5。
当k?4时：
f4(S4)?max{5S4?3x4?f5(0.9S4?0.2x4)}
0?x4?S4?max{5S4?3x4?8(0.9S4?0.2x4)}
0?x4?S4?max{12.2S4?1.4x4}
0?x4?S4?因f4(S4)是关于x4的单调递增函数，故取x4?S4，相应有f4(S4)?13.6S4；依次类推，可求得：
?当k?3时：x3?S3，f3(S3)?17.5S3 ?当k?2时：x2?0，f2(S2)?20.8S2
?当k?1时：x1)?23.7S1?23700 ?0，f1(S1?1000?????计算结果表明最优策略为：x1?0，x2?0，x3?S4，x5?S3，x4?S5；即前两
年将全部设备都投入低负荷生产，后三年将全部设备都投入高负荷生产，这样可以使5年的总产量最大，最大产量是23700件。
有了上述最优策略，各阶段的状态也就随之确定了，即按阶段顺序计算出各年年初的完好设备数量。
S1?1000
S2?0.9S1?0.2x1?0.9?1000?0.2?0?900 S3?0.9S2?0.2x2?0.9?900?0.2?0?810 S4?0.9S3?0.2x3?0.9?810?0.2?810?567 S5?0.9S4?0.2x4?0.9?567?0.2?567?397 S6?0.9S5?0.2x5?0.9?397?0.2?397?278
上面所讨论的过程始端状态S1是固定的，而终端状态S6是自由的，实现的目标函数是
5年的总产量最高。如果在终端也附加上一定的约束条件，如规定在第5年结束时，完好的机器数量不低于350台（上面的例子只有278台），问应如何安排生产，才能在满足这一终端要求的情况下使产量最高呢？
解：阶段k表示年度（k?1,2,3,4,5）；状态变量Sk为第k年度初拥有的完好机器数量；决策变量xk为第k年度分配高负荷下生产的机器数量；状态转移方程为：