资源描述：
《动态规划1引例和基本概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4章动态规划(DynamicProgramming)动态规划的基本概念和思想最短路径问题背包问题投资分配问题例5.1.1管道设计最短路问题就是从某地出发，途经若干中间点最后到达目的地，要求找出路程或费用最小的路线。一般的最短路问题将在下一章讨论，这里只讨论分层的最短路问题。下面的管道设计问题(例5.1.1)就是其中之一。ED3D1D2C1C3C2AB3B2B1542634656122233234ED3D1D2C1C3C2AB3B2B1542634656122233234从A点到E点要铺设一条煤气管道，中间必须经过三个中间站
2、，第一站可在B1、B2、B3中选择，第二站可在C1、C2、C3中选择，第三站可在D1、D2、D3中选择，要求选择一条由A到E的铺管路线，使总长度最短。其中两点连线上的数字表示两点间管线的长度。从A点到E点铺设管道，可以按其地理特点自然地分成四个阶段：（如下图所示）从A到B是第一阶段，从B到C是第二阶段，从C到D是第三阶段，从D到E是第四阶段，ABCDE阶段1阶段2阶段3阶段4在阶段2，从B3点出发，只有C1、C3两种可选择的点，如选C1,则C1就是阶段2在B3点的决策结果；C1点既是阶段2铺设管道的终点，又是阶段3铺设管道的
3、起点；ED3D1D2C1C3C2AB3B2B1542634656122233234ABCDE阶段1阶段2阶段3阶段4同样的理由，可以递推得其余阶段的铺设路线，如阶段3在C1点的决策是D1，阶段4在D1点的决策只有E点；由于到E点是整个铺设管道的终点，至此，决策过程完成，铺设一条A点到E点的管道是由四个阶段的管道组成的，如A---B3---C1---D1---E，它也称为一个策略。ED3D1D2C1C3C2AB3B2B1542634656122233234可以看出，各个阶段的决策不同，铺设的管道也不同，并且当某个阶段的始点给定
4、后，它直接影响着后面各阶段的行进路线和管道的长短，而后面各阶段的路线的选取不受这点以前各阶段路线的影响。ED3D1D2C1C3C2AB3B2B1542634656122233234因此，最短路线问题可简化为四个阶段的决策问题，使由这四个阶段决策组成决策序列，也称为策略所决定的一条路线的总长度最短。递推关系式为:例5.1.2多阶段资源分配问题设有数量为x的某种资源，将它投入两种生产方式A和B中：以数量y投入生产方式A，剩下的量投入生产方式B，则可得到收入g(y)+h(x-y)，其中g(y)和h(y)是已知函数，并且g(0)=h
5、(0)=0；同时假设以y与x-y分别投入两种生产方式A，B后可以回收再生产，回收率分别为a与b。试求进行n个阶段后的最大总收入。若以y与x-y分别投入生产方式A与B，在第一阶段生产后回收的总资源为x1=ay+b(x-y)，再将x1投入生产方式A和B，则可得到收入g(y1)+h(x1-y1)，继续回收资源x2=ay1+b(x1-y1)，……若上面的过程进行n个阶段，我们希望选择n个变量y,y1,y2,…,yn-1，使这n个阶段的总收入最大。因此，问题就变成：求y,y1,y2,…,yn-1，以使g(y)+h(x-y)+g(y1)
6、+h(x1-y1)+…+g(yn-1)+h(xn-1-yn-1)达到最大，且满足条件x1=ay+b(x-y)x2=ay1+b(x1-y1)………xn-1=ayn-2+b(xn-2-yn-2)yi与xi均非负,i=1,2,…,n-1开始有资源x,再进行k阶段生产并采取最优分配策略后得到的最大总收入,当k=1时，有当k=2时，有xAByx-y第一阶段回收x1=ay+b(x-y)AB第二阶段y1x1-y1递推关系式为:例5.1.3生产和存储控制问题某工厂生产某种季节性商品，需要作下一年度的生产计划，假定这种商品的生产周期需要两个月
7、，全年共有6个生产周期，需要作出各个周期中的生产计划。设已知各周期对该商品的需要量如下表所示：周期123456需求量551030508假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品15个单位，每生产一个单位商品的成本为100元。当开足夜班时，每一生产周期能生产的商品也是15个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为120元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储费用的，假设每单位商品存储一周期需要
8、16元，问应该如何作生产和存储计划，才能使总的生产和存储费用最小？周期123456需求量551030508设第i个周期的生产量为xi，周期末的存储量为uj，那么这个问题用式子写出来就是：求x1,x2,…,x6，u1,u2,u3,u4,u5,（u0,u6已知）,满足条件：Sk是这个周期的商品
