2012动态规划(2).ppt

1、动态规划,沈阳工业大学数学系,商人们怎样安全过河, 3名商人 3名随从,随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.,但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?,问题分析,多步决策过程,决策 每一步(此岸到彼岸或彼岸到此岸)船上的人员,要求在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河.,模型构成,xk第k次渡河前此岸的商人数,yk第k次渡河前此岸的随从数,xk, yk=0,1,2,3; k=1,2, ,sk=(xk , yk)过程的状态,S=(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2,S

2、 允许状态集合,uk第k次渡船上的商人数,vk第k次渡船上的随从数,dk=(uk , vk)决策,D=(u , v) u+v=1, 2 允许决策集合,uk, vk=0,1,2; k=1,2, ,sk+1=sk dk,+(-1)k,状态转移律,求dkD(k=1,2, n), 使skS, 并按转移律由 s1=(3,3)到达 sn+1=(0,0).,多步决策问题,模型求解,穷举法 编程上机,图解法,状态s=(x,y) 16个格点,允许决策 移动1或2格; k奇,左下移; k偶,右上移.,s1,sn+1,d1, ，d11给出安全渡河方案,评注和思考,规格化方法,易于推广,考虑4名商人各带一随从的情况,

3、允许状态,S=(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2,动态规划和静态规划的关系,用逆推解法求解下面问题,设,则有,解 : 按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。 设状态变量为s1, s2,s3,s4，并记s1=c；取问题中的变量x1,x2,x3为决策变量；各阶段指标函数按乘积方式结合。令最优值函数fk(sk)表示为第k阶段的初始状态为sk，从k阶段到3阶段所得到的最大值。,动态规划和静态规划的关系,用逆推解法，从后向前依次有,及最优解,由,得,和,(舍去),，而,，故,为极大值点。,最优解,由,所以,动态规划和静态规划的

4、关系,像前面一样利用微分法易知,故,由于已知,而按计算的顺序反推算，可得各阶段的最优决策和最优值。,动态规划和静态规划的关系,即,由,所以,所以,因此得到最优解为,最大值为,由,货郎担问题,货郎担问题在运筹学里是一个著名的命题。有一个串村走户卖货郎，他从某个村庄出发，通过若干个村庄一次且仅一次，最后仍回到原出发的村庄。问应如何选择行走路线，能使总的行程最短。类似的问题有旅行路线问题，应如何选择行走路线，使总路程最短或费用最少等。,现在把问题一般化。设有n个城市，以1，2，n表示之。dij表示从i城到j城的距离。一个推销员从城市1出发到其他每个城市去一次且仅仅是一次，然后回到城市1。问他如何选择

5、行走的路线，使总的路程最短。这个问题属于组合最优化问题，当n不太大时，利用动态规划方法求解是很方便的。,货郎担问题,由于规定推销员是从城市1开始的，设推销员走到i城，记,表示由1城到i城的中间城市集合。 S表示到达i城之前中途所经过的城市的集合，则有,因此，可选取(i,S)作为描述过程的状态变量，决策为由一个城市走到另一个城市，并定义最优值函数fk(i,S)为从1城开始经由k个中间城市的S集到i城的最短路线的距离，则可写出动态规划的递推关系为,边界条件为,为最优决策函数，它表示从1城开始经k个中间城市的S集到i城的最短路线上紧挨着i城前面的那个城市。,货郎担问题,例11 求解四个城市旅行推销员问题，其距离矩阵如表9-13所示。当推销员从1城出发，经过每个城市一次且仅一次，最后回到1城，问按怎样的路线走，使总的行程距离最短。,表9-13,货郎担问题,解: 由边界条件可知：,当k=1时，即从1城开始，中间经过一个城市到达i城的最短距离是：,货郎担问题,当k=2时，即从1城开始，中间经过二个城市(它们的顺序随便)到达i城的