《运筹学动态规划应用讲义》由会员分享，可在线阅读，更多相关《运筹学动态规划应用讲义（35页珍藏版）》请在金锄头文库上搜索。
1、1,第十章 动态规划应用举例,2,第一节 一维资源分配问题,一、一维资源分配问题基本模型及求解方法,1. 模型,设有某种原料，总数量为a，用于生产n中产品。若分配数量xi用于生产第i 种产品，其收益为gi(xi)。问应如何分配，才能使生产n种产品的总收入最大？,此问题可写成静态规划问题：,3,在应用动态规划处理这类“静态规划”问题时，通常以把资源分配给一个或几个使用者的过程作为一个阶段，把问题中的变量xi作为决策变量，将累计的量或随递推过程变化的量选为状态变量。,当gi(xi)都是线性函数时，它是一个线性规划问题；当gi(xi)不是线性函数时，它是一个非线性规划问题。但当n较大时，具体求解是比
2、较麻烦的。然而，由于这类问题的特殊结构，可以将它看成一个多阶段决策问题，并利用动态规划的递推关系来解。,4,2. 求解方法,设状态变量sk表示分配用于生产第k种产品至第n产品的原料数量。则s1 =a，可用逆推法求解。,设决策变量uk表示分配给生产第k种产品的原料数量，即: uk = xk,状态转移方程：,允许决策集合：,把该分配问题看成是对资源总量的消耗过程。,5,令最优值函数fk(sk)表示以数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收入。递推关系式为：,利用这个递推关系式进行逐段计算，最后求得最大总收入为f1(a),6,例1 某公司有9个推销员在全国三个不同市场推销货物，这
3、三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案。,解：设分配人员的顺序为市场1, 2, 3，已知 s1=9，用逆推法。 设 sk 为第k阶段尚未分配的人员数， xk 为第k阶段分配的推销人员数。则状态转移方程为 sk1=sk xk 目标函数为,二、离散的一维资源分配问题,7,第三阶段：给第三市场分配,s3 有09种可能，第三阶段最优决策表如下：,8,第二阶段：给第二市场分配,s2 有09种可能，第二阶段最优决策表如下：,状态转移方程： s3=s2 x2,9,第一阶段：给第一市场分配,由边界条件 s1=9，第一阶段最优决策表如下：,得决策过程：x1*=2, x2*=0, x
4、3*=7, f1*=218 即 市场1 分配 2人，市场2 不分配 ，市场3 分配 7人， 最大收益为218万元。,状态转移方程： s2=s1 x1,10,三、连续的一维资源分配问题,1. 问题的提出,在资源分配问题中，还有一类要考虑资源回收利用问题，这里决策变量为连续值，故称为资源连续分配问题。这类问题一般描述如下： 设有数量为s1的某种资源，可投入A和B两种生产。 第一年若以数量u1投入生产A，剩下的量s1-u1就投入生产B，则可得收入为g(u1)+h(s1-u1)，其中g(u1)和h(u1)为已知函数，且g(0)= h(0)=0 。 这种资源在投入生产A、B后，年终还可回收再投入生产。设
5、年回收率分别为0a1和0b1，则在第一年生产后，回收的资源量合计为s2=au1+b(s1-u1)。 第二年再将资源数量s2按u2和s2-u2分别投入A、B两种生产，如此继续n年，试问：应当如何决定每年投入A生产的资源量u1，u2，un，才能使总收入最大？,11,2. 基本模型,3. 求解方法,设状态变量sk表示第k阶段可投入A和B两种生产的资源量；决策变量uk表示第k阶段可投入A生产的资源量，则sk uk为可投入B生产的资源量。,已知 s1，可用逆推法求解。,12,状态转移方程：,令最优值函数fk(sk)表示以数量为sk的资源量分配给第k阶段至第n阶段所得到的最大总收入。 递推关系式为：,最后
6、求得最大总收入为f1(s1)。,13,例2 机器负荷分配问题(书P253),解：,设状态变量sk表示第k年度初拥有的完好机器数量，同时表示第k1年度末拥有的完好机器数量。,设决策变量uk表示第k年度中分配高负荷下生产的机器数量，则sk uk为该年度中分配低负荷下生产的机器数量。,状态转移方程：,允许决策集合：,14,令最优值函数fk(sk)表示以资源量sk出发，从第k年开始至第5年结束时，生产的产品最大值。递推关系式为：,设vk(sk , uk)为第k年度的产量，则vk 8 uk 5(sk uk) 故指标函数为：,15,当k=5时，有,求得最大解：,相应的，有,因,，故最高产量为,（台）,补充
7、作业14,若计划期结束时完好的机器台数为500台，应如何安排生产使产量最大？,16,第二节 生产与存贮问题,一、生产计划问题,1. 问题的提出,设某公司要制定一项n个阶段的生产计划。已知初始库存为零，每阶段该产品的生产量有上限的限制；每阶段社会对该产品的需求量是已知的，在n阶段末库存为零。问该公司如何制定每个阶段的生产计划，使产品总成本最低。,设dk为第k阶段对产品的需求量，xk为第k阶段该产品的 生产量，sk1为k阶段末的产品库存量。则有 sk1 sk xk dk 由此可见，过程演化方向由s1至 sn1 。,2. 基本模型,17,设ck(xk)表示第k阶段生产量xk的成本费用，它包括生产准备
8、成本K和产品成本axk(a是单位产品成本)两项费用 ，hk(sk )为第k阶段开始时有产品库存量sk 所需的存贮费用。故k阶段的成本费用为ck(xk) hk(sk)。m表示每阶段最多能生产该产品的上限数量。,因而，上述问题的模型为,18,根据动态规划求解规则，采用逆推法，递推关系式：,边界条件为：,用动态规划方法求解如下：,由于过程演化方向由s1至 sn1 ，则其状态转移方程：,问题的关键是确定 sk 和 xk 的取值范围。,从边界条件出发，利用这个递推关系式进行计算，对每个k计算fk(sk) 的值，最后求得f1(0)即为所求最小总费用。,19,xk 的取值范围：,sk 的取值范围：下限为0；
9、上限为,mdk 1 表示k1阶段生产时的最大库存量，如果不生产则库存量更小。这是由生产与存贮问题的特性决定的，即k1阶段进行生产的条件是该阶段初的库存一定为零，而一旦进行生产则尽可能按最大生产能力生产。,20,21,例3 某工厂生产某种产品的月生产能力为6件，已知今后四个月的每批产品的固定成本和单位产品成本分别为3千元、1千元。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为0.5千元，试安排月生产计划并做到： 1、保证满足每月的销售量，并规定计划期初和期末库存为零； 2、在生产能力允许范围内，安排每月生产量计划使产品总成本(即生产费用加存储费)最低。,3. 实例(P
10、263 例3),22,设xk为第k阶段生产量，则有k阶段生产成本：,k阶段存贮成本：,则k阶段总成本：,状态转移方程：,采用逆推法，递推关系式：,边界条件为：,23,k=4,s4的上限：,所以， s4 0,4。,x4的取值范围：,24,25,k=3,s3的上限：,所以， s3 0,3。,x3的取值范围：,26,27,k=2,s2的上限：,所以， s2 0,4。,x2的取值范围：,28,29,k=1,s10,x1的取值范围：,逆计算过程反推得：x1* =5, x2* =0 , x3* =6, x4* =0,这类库存问题的特征：si xi =0,30,二、不确定性采购问题,例4 (P269 例6)
11、 某工厂生产上需要在近五周内采购一批原料，而估计在未来五周内价格有波动，其浮动价格和概率已测得如下表。试求在哪一周以什么价格购入，使其价格的数学期望值最小，并求出期望值。,解: 这里价格是一个随机变量，是按某种已知的概率分布取值的。按采购期限5周分为5个阶段，将每周的价格看作该阶段的状态。,31,yk为状态变量，表示第k周的实际价格。 xk为决策变量，当xk1表示第k周采购，当xk0，不采购。 ykE表示第k周决定等待，而在以后采取最优决策时采购价格的 期望值。 fk(yk)表示第k周实际价格为yk时，从第k周到第5周最优决策的期望值。 逆序递推关系为：,(1),32,从最后一周，向前递推： k=5时，因,即在第五周，若所需的原料尚未买入，无论价格多少，都必须采购。,k=4时，由（1）式可知,第4周的最优决策为,33,k=3时，由（1）式可知,34,k=2时，由（1）式可知,35,由上可知，最优策略为：在第一、二、三周时，若价格为500就采购，否则等待；在第四周时，若价格为500或600就采购，否则等待；在第五周，无论价格多少，都必须采购。 按照该最优策略，价格的数学期望为：,k=1时，由（1）式可知,
