动态规划应用举例 - 图文(4)

n种产品时所得到的最大收入。故可写出逆推关系为

??fn(x,y)?gn(x,y)??gk(xk,yk)?fk?1(x?xk,y?yk)? ?fk(x,y)?0max?xk?x?0?yk?y?? k?n?1,?,1最后求得f1(a,b)即为所求问题的最大收入。 1。 拉格朗日乘数法

引入拉格朗日乘数λ，将二维分配问题化为

max?g1(x1,y1)?g2(x2,y2)???gn(xn,yn)??(y1?y2???yn)?

满足条件x1?x2???xn?a；xi?0,yi?0, i?1,2,?,n 且为整数，其中λ作为一个固定的参数。 令 hi(xi)?hi(xi,?)?max?gi(xi,yi)－?yi?

yi?0于是问题变为max?h1(x1)?h2(x2)???hn(xn)?，满足x1?x2???xn?a, xi?0且为整数

这是一个一维分配问题，可用对一维的方法去求解。这里，由于λ是参数，因此，最优解xi是参数λ的函数，相应的yi也是λ的函数。即xi?xi(?)，yi?yi(?)为其解。如果?yi(?)?b，则可证明xi,yii?1nnn??为原问题的最优解。如果?yi(?)?b，将调整λ的值(利用插值法逐渐确定λ )，直到?yi(λ)?b满足为

i?1i?1止。

这样的降维方法在理论上有保证，在计算上是可行的，故对高维问题，可用上述拉格朗日乘数法的思想来降低维数。

2。 逐次逼近法

这是另一种降维方法，先保持一个变量不变，对另一个变量实现最优化。然后交替地固定，以迭代的形式反复进行，直到获得某种要求为止。

先设x(0)??x(0)1,x(0)2,?,x(0)n?为满足?xi?1n(0)i?a的一个可行解，固定x在x(0)，先对y求解，则二维

分配问题变为一维问题：

(0)(0)(0)?g(x,y)?g(x,y)???g(x,yn)??max?111222nn?? ???y1?y2???yn?b,yi?0 且为整数可用对一维的方法来求解。设这解为y(0)(0)(0)??y1(0),y2,?,yn?，然后再固定y为y(0)，对x求解，即

n?(0)maxg(x,y)?iii??i?1 ?n?x?a,x?0 且为整数?ii??i?1设其解为x(k)(1)??x1(1),x2(1),?,xn(1)?，再固定x为x(1)，对y求解，这样依次轮换下去得到一系列的解

?x?，?y?(k?0,1,?)。

(k)因为

?gi(x,yi)??gi(x,y(0)i(0)ii?1i?1nn(0)i)??gi(xi(1),yi(0))，

i?1n?n(k)(k)?故函数值序列??gi(xi,yi)?是单调上升的，但不一定收敛到绝对的最优解，一般只收敛到某一局部?i?1?最优解。因此，在实际计算时，可选择几个初始点x一个最好的。

3．粗格子点法(疏密法)

在采用离散化的方法计算时，先将矩形定义域：0≤x≤a，0≤y≤b分成网格，然后在这些格子点上进行计算。如将a、b各分为m1和m2等份，则总共有(m1+1)·(m2+1)个格点，故对每个k值需要计算的fk(x,y)共有(m1+1)·(m2+1)个。因此，这里的计算量是相当大的。随着分点加多，格子点数也增多，那时的计算量将大得惊人。为了使计算可行，往往根据问题要求的精确度，采用粗格子点法逐步缩小区域来减少计算

量。

粗格子点法是先用少数的格子点进行粗糙的计算，在求出相应的最优解后，再在最优解附近的小范围内进一步细分，并求在细分格子点上的最优解，如此继续细分下去直到满足要求为止。这种方法可能会出现最优解“漏网”的情况，因此，应用此法时要结合对指标函数的特性进行分析。

1。3 固定资金分配问题

设有n个生产行业，都需要某两种资源。对于第k个生产行业，如果用第1种资源xk和第2种资源yk进行生产，可获得利润为rk(xk,yk)。若第1种资源的单位价格为a ，第2种资源的单位价格为b，现有资金Z。问应购买第1种资源多少单位(设为X)，第2种资源多少单位(设为Y)，分配到n个生产行业，使总利润最大?

此问题的数学模型可写为

(0)进行计算，然后从所得到的几个局部最优解中选出

nmax?rk(xk,yk)k?1?n??xk?X xk为非负整数?k?1 ?n ??yk?Y yk为非负整数?k?1?aX?bY?Z??(1) 把资源分配利润表换算成资金分配利润表，即将rk(xk,yk)换算成Rk(z), z?0,1,?,Z。但必须注意，分配的资金应先使较贵的资源单位最大。

设有资金z(0?z?Z)分配到第k个生产行业，则由Z?aX?bY知，在给定z的情况下，若购买第

2种资源yk单位，则留下的资金只能购买第1种资源xk单位，xk???z?byk?a??。于是得到资金利润函数?Rk(z)为

Rk(z)????z?byk?rk??yk?0,1,?,(z/b)???amax???,y?k?? ???式中(z/b)指以资金z购买第2种资源的最大单位数，购买第1种资源的最大单位数。

z?byka指以资金z购买了第2种资源yk单位以后能

(2) 计算最优资金分配所获得最大利润。规定最优值函数fk(z)表示以总的资金z分配到k至n个生产行业可能获得的最大利润。则有逆推关系式：

??Rk(zk)?fk?1(z?zk)??fk(z)?zkmax?0,1,?,z ???fn(z)?Rn(z)(3) 求出f1(z)，即为问题的解。这样，就把一个原含有两个状态变量的问题转化为只含有一个状态变量的问题。

二、生产与存储问题

在生产和经营管理中，经常遇到要合理地安排生产(或购买)与库存的问题，达到既要满足社会的需要，

又要尽量降低成本费用。因此，正确制定生产(或采购)策略，确定不同时期的生产量(或采购量)和库存量，以使总的生产成本费用和库存费用之和最小，这就是生产与存储问题的最优化目标。

2。1 生产计划问题

设某公司对某种产品要制定一项n个阶段的生产(或购买)计划。已知它的初始库存量为零，每阶段生产(或购买)该产品的数量有上限的限制；每阶段社会对该产品的需求量是已知的，公司保证供应；在n阶段末的终结库存量为零。问该公司如何制定每个阶段的生产(或采购)计划，从而使总成本最小。

设dk为第k阶段对产品的需求量，xk为第k阶段该产品的生产量(或采购量)，vk为第k阶段结束时的产品库存量。则有vk?vk?1?xk?dk

ck(xk)表示第k阶段生产产品xk时的成本费用，它包括生产准备成本K和产品成本axk (其中a是单

位产品成本)两项费用。即

?0 当xk?0?ck(xk)??K?axk 当xk?1,2,?,m

?? 当x?mk?hk(vk)表示在第k阶段结束时有库存量vk所需的存储费用。

故k阶段的成本费用为ck(xk)?hk(vk) m表示每阶段最多能生产该产品的上限数。

上述问题的数学模型为

min g???ck(xk)?hk(vk)?k?1n?v0?0,vn?0?k?v??(x?d)?0 k?2,?,n?1

jj?k ?j?1?0?x?m k?1,2,?,nk???xk为整数 k?1,2,?,n用动态规划方法来求解，可看作一个n阶段决策问题。令vk?1为状态变量，它表示第k阶段开始时的库存量。xk为决策变量，它表示第k阶段的生产量。

状态转移方程为 vk?vk?1?xk?dk k?1,2,?,n

最优值函数fk(vk)表示从第1阶段初始库存量为0到第k阶段末库存量为vk时的最小总费用。 顺序递推关系式为：

fk(vk)?min?ck(xk)?hk(vk)?fk?1(vk?1)? k?1,?,n

0?xk??k其中?k?min(vk?dk,m)。这是因为一方面每阶段生产的上限为m；另一方面由于保证供应，故第k-1阶段末的库存量vk?1必须非负，即vk?dk?xk?0，所以xk?vk?dk。

边界条件为f0(v0)?0或f1(v1)?min?c1(x1)?h1(v1)?从边界条件出发，利用上面的递推关系式，对

x1??1

k?n?每个k ，计算出fk(vk)中的vk在0至min??dj,?(m?dj)?之间的值，最后求得的fn(0)即为所求的

j?1?j?k?1?最小总费用。

例3 某工厂要对一种产品制订今后四个时 …… 此处隐藏：2577字，全部文档内容请下载后查看。喜欢就下载吧 ……