§7货郎担问题 货郎担问题也称旅行员问题，是运筹学里一个著名问题。设有 n个城市，以1,2，，n表示，d表示从i城到j城的距离。一个推销 员从城市1出发到其它每个城市去一次且仅仅一次，然后回到城市1， 问他应如何选择行走路线，使总的路程最短。这个问题属于组合最 优化问题，目前尚无有效解法。如果用穷举法，计算次数为n!,当n 很大时，例如=20，计算次数20！=2.432902×1018，实际上这是无 法计算的。但当不太大时，利用动态规划方法求解却是很方便的。 规定推销员是从城市1出发，设推销员走到城，s表示到达城之 前中途所经过的城市集合。选取(，s)作为描述过程的状态变量， 定义f(,s)为从1城出发经由k个中间城市的s集到i城的最短路线的距 离，则 f(i,S)=min{f-1G,sj)+di}j∈s(k=1,2,,n-1;i-2,3,“…,n) 边界条件为fi,p)=d1.记最优决策函数为pk(,S),它表示从1城出 发经k个中间城市的s集到城的最短路线上紧挨着城前面的城市。 这样，我们可以从k=O出发，依次求出(i,S),直至求出-(I,N), 其中N,表示从1城出发回到1城的所有中间城市集合
§7 货郎担问题 ❖ 货郎担问题也称旅行员问题，是运筹学里一个著名问题。设有 n个城市，以1，2，…，n表示，dij表示从i城到j城的距离。一个推销 员从城市1出发到其它每个城市去一次且仅仅一次，然后回到城市1， 问他应如何选择行走路线，使总的路程最短。这个问题属于组合最 优化问题，目前尚无有效解法。如果用穷举法，计算次数为n！,当n 很大时，例如n=20，计算次数20！=2.432902×1018，实际上这是无 法计算的。但当n不太大时，利用动态规划方法求解却是很方便的。 ❖ 规定推销员是从城市1出发，设推销员走到i城，s表示到达i城之 前中途所经过的城市集合。选取（i,s）作为描述过程的状态变量， 定义fk (i,s)为从1城出发经由k个中间城市的s集到i城的最短路线的距 离，则 ❖ fk (i,s)=min｛fk-1(j,s/j)+ dji ｝,j∈s (k=1,2, …,n-1;i=2,3, …,n) ❖边界条件为f0 (i,φ)=d1i. 记最优决策函数为pk (i,s)，它表示从1城出 发经k个中间城市的s集到i城的最短路线上紧挨着i城前面的城市。 这样，我们可以从k=0出发，依次求出fk (i,s)，直至求出 fn-1 (1,N1 )， 其中N1表示从1城出发回到1城的所有中间城市集合
例9求解四个城市的推销员问题，其距离矩阵如下表所示： 23 4 1 085 6 2 6 08 5 7 9 0 5 4 9 7 8 0 解：k=0 f6(2,p)=8,f6(3,p)=5,f6(4,p)=6 k=1 f(2,{3})尸f6(3,p)+d325+9=14f(2,{4})尸f6(4,p)+d426+7=13 f(3,{2))尸6(2，p)+d23=8+8=16;f(3,{4)尸f6(4,p)+d43=6+8=14 f(4,{2)=f6(2,0)+d24=8+5=13;f43}=f6(3,φ)+d34=5+5=10
例9 求解四个城市的推销员问题，其距离矩阵如下表所示： i j 1 2 3 4 1 2 3 4 0 8 5 6 6 0 8 5 7 9 0 5 9 7 8 0 解：k=0 f0 (2,φ)=8, f0 (3,φ)=5, f0 (4,φ)=6 k=1 f1 (2,｛3｝)= f0 (3,φ)+d32=5+9=14; f1 (2,｛4｝)= f0 (4,φ)+d42=6+7=13 f1 (3,｛2｝)= f0 (2,φ)+d23=8+8=16; f1 (3,｛4｝)= f0 (4,φ)+d43=6+8=14 f1 (4,｛2｝)= f0 (2,φ)+d24=8+5=13; f1 (4,｛3｝)= f0 (3,φ)+d34=5+5=10
k-2 f62,3,4))ㄕmin{f(4,{3}+d42,f(3,{4)+d32} min{10+7,14+9}=17 p2(2.{3.4}）=4 f(3,{2,4)片min{f(4,{2}+d43,f(2,{4))+d23 min[13+8,13+8}=21 p2(3,{2,4))=2或4 (4,{2,3}min{f2,{3)+d24,f(3,{2}+d34} =min{14+5,16+5)=19 p2(4,{2,3})=2 k=3 f3(1,{2,3,4)) =min{f6(2,(3,4}+d21(3,{2,4))+d31,f(4,{2,3}+d4) =min(17+6,21+7,19+9}=23 p31.{2.3.4}=2 由此可知，推销员最短路线为1→3→4→2→1，最短距离为23。 实际中很多问题都可以归结为货郎担问题，如物资运输中汽车 应走怎样的路线使路程最短；工厂中机床应如何布置，可使零件所 经过的路线最短等等
k=2 f2 (2,｛3,4｝)=min{ f1 (4,｛3｝)+ d42, f1 (3,｛4｝)+d32} =min｛10+7,14+9｝=17 p2 (2,｛3,4｝)=4 f2 (3,｛2,4｝)=min{ f1 (4,｛2｝)+ d43, f1 (2,｛4｝)+d23} =min｛13+8,13+8｝=21 p2 (3,｛2,4｝)=2或4 f2 (4,｛2,3｝)=min{ f1 (2,｛3｝)+ d24, f1 (3,｛2｝)+d34} =min｛14+5,16+5｝=19 p2 (4,｛2,3｝)=2 k=3 f 3 (1,｛2,3,4｝) =min{f2 (2,｛3,4｝)+d21, f2 (3,｛2,4｝)+d31, f2 (4,｛2,3}+d41) =min｛17+6,21+7,19+9｝=23 p3 (1,｛2,3,4｝)=2 由此可知，推销员最短路线为 1→3→4→2→1 ，最短距离为23。 实际中很多问题都可以归结为货郎担问题，如物资运输中汽车 应走怎样的路线使路程最短；工厂中机床应如何布置，可使零件所 经过的路线最短等等
§8其它应用问题 有些求最优解的问题，初看起来似乎不是多阶段决策问题，但 经过适当变换后仍能变为多阶段决策问题，从而可用动态规划方法 求解。 例10求解下面的规划问题： maXZ=+√x2+√83 JX1+X2+X3=9 LX1,X2,X3≥0 这是一个单约束条件的非线性规划问题，可以用非线性规划方 法求解。现在把它转换成动态规划模型。就问题的模型来看，类似 资源分配问题，约束条件右端常数相当于资源总量，三个变量可以 看成是分三个阶段分配已有资源，Z是分配后的总效果。 令k代表阶段，k=1,2,3;Sk为状态变量，代表k阶段初尚未 分配的资源总数；X为决策变量，代表分配给第k阶段的资源量； 区k代表第k阶段决策确定后的直接效果
§8 其它应用问题 ❖ 有些求有些求最优解的问题，初看起来似乎不是多阶段决策问题，但 经过适当变换后仍能变为多阶段决策问题，从而可用动态规划方法 求解。 例10 求解下面的规划问题： maxZ= x1+x2+x3=9 x1 ,x2 ,x3≥0 这是一个单约束条件的非线性规划问题，可以用非线性规划方 法求解。现在把它转换成动态规划模型。就问题的模型来看，类似 资源分配问题，约束条件右端常数相当于资源总量，三个变量可以 看成是分三个阶段分配已有资源，Z是分配后的总效果。 令 k代表阶段， k=1，2，3；sk为状态变量，代表k阶段初尚未 分配的资源总数； xk为决策变量，代表分配给第k阶段的资源量； 代表第k阶段决策确定后的直接效果。 x1 + x2 + x3 xk
于是，状态转移方程为：Sk+1S 记(S)为k阶段到第3阶段按最优分配方案获得的最大效果， 则动态规划基本方程是： 东(sk)=max{V区+f+1(sk+i)} 0≤X≤Sk 4(s4)=0 k=3,2,1 k=3 (s;)=max {v3 )=3 X3=S3 0≤X3≤S3 k=2 (s2)max{(s3))max +- 0≤X2≤S2 0≤X≤S 用微分法可求得上式当x2=0.5s2时，有最大值：五(s2)=√2s, kf(s)0方(s)}0+2s-x) 用微分法可求得上式当x=s/3=3时，有最大值：f(s)=35 因此，原问题的最优解为：x=X2=X=3,最优值为：33
于是，状态转移方程为：sk+1= sk-xk 记 fk（sk）为k阶段到第3阶段按最优分配方案获得的最大效果， 则动态规划基本方程是： fk（sk）= max｛ +fk+1（sk+1）｝ 0≤xk≤sk f4（s4）=0 k=3,2,1 xk k=3 f3（s3）=max｛ ｝= x3= s3 0≤x3≤s3 k=2 f2（s2）=max｛ x2 +f3（s3）｝= max｛ + ｝ 0≤x2≤s2 0≤x2≤s2 用微分法可求得上式当x2=0.5s2时，有最大值：f2（s2）= x3 s3 s2 x2 x2 − 2s2 k=1 f1（s1）=max｛ +f2（s2）｝= max｛ + ｝ 0≤x1≤s1 0≤x1≤s1 用微分法可求得上式当x1=s1 /3=3时，有最大值：f1（s1）= x1 ( ) 2s1−x1 x1 3 3 因此，原问题的最优解为： x1= x2= x3= 3，最优值为：3 3
第六章作业 P112:3 P112:4 P113:6 P114:10
第 六 章 作 业 ❖ P112: 3 ❖ P112: 4 ❖ P113: 6 ❖ P114: 10