第九章动态规划应用举例(Du貅町Theory)U东人日心一绍质源分配问题生产与存贮问题背包问题设备更新问题货郎担问题 第一节一维资源分配问题云、一维资源分配问题基本模型及求解方法1.模型设有树种原料,总数量为g,用于生产n种产品若分配数坤x,用于生产第i种产品,其收益为gir)问应如何分配,才能催生产n种产品的总收入最大?此问题可写成静态规划问题:MUarZ二81(x1)十8o(X2)十…十B,(X,)8命靥干城十1年诊下硫亚么0二二二2凤 当gi(r)都是线性函数时,它是一个线性规划问题;当gi(ri)不是线性函数时,它是一个非线性规划问题但当m较大时,具体求解是比较麻烦的然而,由于这类问题的特殊结构,可以拳它看戍一个多阶段决策问题,并利用动态规划得递推关系来解在应用动态规划处理这类“静态规刘“问题时,通常以把资源分配给一个或几个使用者的过程作为一个阶殴,把问题中的变量ri作为决策变量,将累计的量或随递推过程变化的量选为状态变量 把该分配问题看成是对资源总量的消耗过程设状态变量g表示分配用于生产第k种产品至第n产品的料数量则sl=g,可用逆推法求解设决策变量x表示分配给生产第种产品的原料数量,P:k一状态转移方程:st=8一史=8一x允许决策集合:D.(st)={z10三z=二三st} |令最优值出数ft(st)表示以数量为st的原料分配给第k种产品R种产品所得到的最大总收入。
递推关系式为:丁(S=max{gx(Xx)十异l(Sx一川无二友不一二.儿口zn丁a(sm)0利用这个递推关系式进行逐殴计算,最后求得最大总收入为fi(a) 二、离散的一维资源分配问题例1“栋公司有9个推销员在全国三个不同市场推销货4物,这三个市场里推销人员数与收盐的关系如下表,试作出使总收益最大的分配方案E市场E12E寸E05EEE77沥UE河浩一1091201311401S0解:设分配人员的顺序为市场l2,3,已知sl=9,用逗推法设sx为第阶殴尚未分配的人员数,xk为第K阶段分配的推销人员数则状态转移方程为st,i=8Sx一吉目标函数为巾(-max艺粼唰 白有0一9种可能,第三阶殴最优决策表如下:0蓼h瓷hutouCO6]噱EE]0g1200971091201310971091201311400E振尿人朋口育a育化ao疆[沥沥沥=东-东-二沥=林技c0E2E4EE2EE 给第二市场分配一2E寸E2Y0E2E寸C:208E沥洁[河育a河肖4u河育一1洁ud1E/状态转移方程:sazso-口l有0-9种可能,第二阶段最优决策表如下:E】'技东Bballnsl怀-怀-尿-吴-技怀-技国PC河河许述育东 第一阶段:给第一市场分配l霍_0__1_23_4_5__61_E魍LLEEELLEEELLEELILEEELILEEELIEEELEPIKi90_101112124137149160171181191状态转移方程:gzzsl一出由边界条件s=9,第一阶段最优决策表如下:得决策过程:xl#=2,xo*=0,xa#=7,月=218即市场1分配2人,市场2不分配,市场3分配7人,最大收益为218万元。
三、逊续的一维资源分配问题F在资源分配问题中,还有一类要考虑资源回收利用问题,这责术责支量为违续值故称为资源连续分配问题这类问题_帐笠拮如下:设有数量为s的树种资源,可投入4和B两种生产第一年若以数量i投入生产A,剩下的量si-wi就投入生产B,则可得收入为gfrtlj+fh(si-iilj,关中g(nl)和ftai)为己卯函数,丁g(0)=(0)=0这种资源在投入生产A,B后,年终还可回收再投入生产设年回收率分别为0