图 7-3
递推关系式：
?fk(sk?1)?min?dk(sk?1,uk)?fk?1(sk)}k?1,2,3,4,5(7.5a)uk ?
(7.5b)?f0(s1)?0此与逆序法无本质的区别。一般来说，当初始状态给定时，用逆序解法，当终止状态给
定时，用顺序解法。若既给定了初始状态又给定了终止状态，则两种方法均可使用。如习题7.2/P237，终点有三个，用逆序解法较好。
7.2/P237 一艘货轮在A港装货后驶往F港，中途须靠港加油、淡水三次，从A港到F港全部可能的航行路线及两港之间距离如图7-7，F港有三个码头 ，，，实秋最合理的停靠的码头及航线，使总路程最短。
C1 20 50 60 30 F 1
B1 50 30 40 D 1 20 60
C2 F2 A 40 30 F 45 40 25 D 2 30
B2 F2 30 50
C3 图7-7 解：顺序解法
此法类似于逆序递推法。从起点A向终点F倒退。 （1）k=1时，f0(A)=0，此为初始条件。退向允许决策集S1=｛B1, B2 ｝，此时退向B1时看
起点A，最短距离为f1(B1)=50，此时路径（或最优决策）是唯一的：u1(B1)=A；记
??f1(B1)?50?f1(B2)?45，同理， ????u(B)?Au(B)?A?11?12（2）k=2时，直接用递推式：
?f2(C1)?d(B1,C1)?f1(B1)?20?50?70 ??u2(C1)?B1???f2(C2)???u?(C)?B1?22??f2(C3)???u?(C)?B2?23
?d(B1,C2)?f1(B1)??30?50?min??min????80
d(B,C)?f(B)40?45??2212???d(B1,C3)?f1(B1)??60?50?min??min????75 ?30?45??d(B2,C3)?f1(B2)?6
（3）k=3时。
??d(C1?D1)?f2(C1)??50?70??????min?d(C2,D1)?f2(C2)??min?40?80??100?f3(D1)? ??d(C,D)?f(C)??25?75?3123????????u3(D1)?C3,类似的
?f3(D2)?110。 ???u3(D2)?C2（4）k=4时
?f4(F1)?d(D1,F1)?f3(D1)?30?100?130 ??u(F)?D411???f4(F2)???u?(F)?D1?22?d(D1,F2)?f3(D1)??20?100?min??min????120
?40?110??d(D2,F2)?f3(D2)??f4(F3)?d(D2,F3)?f3(D2)?30?110?140 ??u(F)?D432?由此看来，A到F距离最短的是120，故最优路线为
A— B2 —C3 — D1—F2
§7.2 资源分配问题（离散型）
例：设有6万元资金用于4个工厂的扩建，已知每个工厂的利润增长额同投资额的大小有关，见下表。问应如何确定对这四个工厂的投资额，使总利润增长额最大？ 表内数据是利润额gi(xj) 投资额(j) 工厂(i) 1 2 3 4 0 100 200 300 400 500 600 0 20 42 60 75 85 90 0 25 45 57 65 70 73 0 18 39 61 78 90 95 0 28 47 65 74 80 85 解：把对四个工厂的投资依次看成4个阶段的决策过程，确定对第k个工厂的投资额看成第k个阶段的决策，k=1,2,3,4。图示如下：
投资x2(万元) 投资x3(万元) 投资x4(万元) S5 s1=600 投资x1(万元) 状态s2 状态s3 状态s4 s2= s1-x1 S3= s2-x2 S4= s3-x3 工厂4 工厂1 工厂2 工厂3 g3(x3) g1(x1) g2(x2) g4(x4)
7
状态变量sk：可用于第k, k+1,?n个工厂的投资额。 决策变量xk：第k阶段对第k个工厂的投资额。 允许决策集：Dk=｛0，100，?sk｝
状态转移方程：sk?1=sk-xk k=1,2,3,4 其中x1=600。 阶段指标函数gi(xj)：第i阶段投资xj元时所产生的利润。（见上表）
最优指标函数fk(sk)：第k阶段状态为sk且对第k个工厂投资为xk时，第k个工厂以及以后的总利润。
基本递推方程：
?fk(sk)? ??f5(s5)?00?xk?skmax?gk(xk)?fk(sk?1)?k?4,3,2,1
初始条件已知：s1=600，逆序法求解。 （1） k=4时，
考虑：若到最后一个，第4个工厂投资时，还有资金s4，若投资于第4个工厂的资金为x4，则最大利润为
f4(s4)?max{g4(x4)?f5(s5)} （注意到此时f5(s5)=0）
0?x4?s4 =max{g4(x4)} （1）
0?x4?s4自然问：现在还有多少钱？即s4=？s4=0，100，200，300，400，500，600都有可能。下分情况讨论：
1 s=0时，x只能=0。从表上看（4，1）位置是第4个工厂x=0时的利润其值为○444g4(x4)=0，由x4=0的唯一性知f4(s4)=0。
2s=100，此时x=0或100。产生的利润g(x)=0或28。 ○4444 max{g4(x4)}=｛0，28｝=28，
0?x4?s4?对应的x4=100，即此种情况的最优决策x4=100。
其他种情况类似讨论，我们把所有的结果汇总成一个表1。
（2）k=3时 到第三个工厂投资时，可利用的资金还有s3，若向第三个工厂投资x3（万
8
元），则自此即以后最大利润为：
f3(s3)?max{g3(x3)?f4(s4)}=max{g3(x3)?f4(s3?x3)}
0?x3?s30?x3?s3
表1 x4 g4(x4) 0 100 200 300 400 500 600 ?f4(s4) x4 s4 0 0 100 0 28 200 0 28 47 300 0 28 47 65 400 0 28 47 65 74 500 0 28 47 65 74 80 600 0 28 47 65 74 80 85 0 28 47 65 74 80 85 0 100 200 300 400 500 600 同样问：s3=？，即现在还有多少钱？分情况讨论汇总成下表：
x3 g3(x3)+f4(s3?x3) 0 100 200 300 400 500 600 ?f3(s3) x3 s3 0 0+0 0 100 0+28 18+0 28 200 0+47 18+28 39+0 47 300 0+65 18+47 39+28 61+0 67 400 0+74 18+65 39+47 61+28 78+0 89 500 0+80 18+74 39+65 61+74 78+28 90+0 108 600 0+85 18+80 39+74 61+65 78+47 90+28 95+0 126 0 0 0 200 300 300 300 我们举一个例子来说明。若s3=300，x3得所有可能取值为{0，100，200，300}，此为第三阶段允许决策集。在D3={0，100，200，300}中选取最优的x3，使g3(x3)?f4(300?x3)最大，即
f3(300)?max{g3(x3)?f4(300?x3)}
0?x3?300=max{g3(0)?f4(300?0),g3(100)?f4(300?100),g3(200)?f4(300?200),
g3(300)?f4(300?300)｝
?=max{0+65,18+47,39+28,61+0}=67, 此67对应的是x3=200时所得，即x3=200；
9
（3）k=2时 f2(s2)?max{g2(x2)?f3(s2?x2)}
0?x2?s2此时，s2的所有可能取值｛0，100，200，300，400，500，600｝，s2每个定一个值，x2在≤s2的范围内变动，由f2(s2)?max{g2(x2)?f3(s2?x2)}，求出f2(0)=？
0?x2?s2f2(100)=？?f2(600)=？下面举一个例子来说明。
f2(600)?max{g2(x2)?f3(600?x2)}
0?x2?600=max｛g2(0)?f3(600?0),g2(100)?f3(600?100),g2(200)?f3(600?200),
g2(300)?f3(600?300),g2(400)?f3(600?400),
g2(500)?f3(600?500),
g2(600)?f3(600?600)}=｛0+126，25+108，45+89，57+67，65+47，70+28，73+0｝
=max｛126，133，134，124，112，98，73｝=134。
?对应最大值的x2=200，所以x2=200。
关于s2的其他取值情况及相应的最有决策列于下表
x2 g2(x2)+f3(s2?x2) 0 100 200 300 400 500 600 ?f2(s2) x2 s2 0 0+0 0 100 0+28 25+0 28 200 0+47 25+28 45+0 53 300 0+67 25+47 45+28 57+0 73 400 0+89 25+67 45+47 57+28 65+0 92 500 0+108 25+89 45+67 57+47 65+28 70+0 114 600 0+126 25+108 45+89 57+67 65+47 70+28 73+0 134 （5）k=1时，此时s1=600。
0 0 100 200 100或200 100 200 f1(s1)?f1(600)?max{g1(x1)?f2(s1?x1)}=max{g1(x1)?f2(600?x1)}
0?x1?s10?x1?600=max｛g1(0)?f2(600?0),g1(100)?f2(600?100),g1(200)?f2(600?200),
g1(300)?f2(600?300),g1(400)?f2(600?400),g1(600)?f2(600?600)｝
=max｛0+134,20+114,42+92,60+73,75+53,85+28，90+0｝ =max｛134,134,134,133,128,113,90｝=134.
10