运筹学8

假设有某种资源的总数量为a(例如原材料、能源、机器设备、劳动力、食品等)，可用于生产n种产品，若生产第j种产品所使用的资源数为xj时，可获得利润为gj(xj)，问如何分配该种资源，使所获得的总利润达到最大。一、资源分配问题该问题的数学模型可表示为：11221212max()()(),,0nnnnzgxgxgxxxxaxxx第四节动态规划应用举例当gj(xj)都是线性函数时，它是一个线性规划问题；当gj(xj)是非线性函数时,它是一个非线性规划问题。但当n比较大时，求解起来是非常麻烦的。由于该问题的特殊性，可以将它看成一个多阶段决策问题，并利用动态规划的方法来求解。决策变量xk表示生产第k个产品所使用的资源数量，则:我们将n个产品看作是n个阶段，设状态变量sk表示生产第k个产品至第n个产品所使用的资源数量。0kkxs显然状态转移方程为：1kkkssx第k阶段的阶段指标为：则由动态规划最优化原理，可得动态规划的基本方程为：最优值函数fk(sk)表示生产第k个产品至第n个产品所使用的资源数量为sk时获得的最大总利润。(,)()kkkkkvsxgx1111()max()()()0kkkkkkkxnnfsgxfsfs例1:(投资分配问题)某公司拟将5百万元资金投放到A、B、C三个项目，各项目在获得资金后的收益如下表所示，用动态规划方法求总收益最大的投资分配方案。151184C121050B1210630A收益(百万)4321投放资金(百万)0解：该问题可以作为三阶段决策过程。对A、B、C三个项目分配资金分别形成1，2，3三个阶段。sk表示给项目k分配资金时拥有的资金数。uk表示给项目k分配的资金数（单位：百万元）。状态转移方程是sk+1=sk-uk。则递归方程为：311()max{()}max{()()},3,2,1kkkjjjkkkkkufSgugufSk44()0fS阶段指标gk(uk)表示分配给第k个项目的资金为uk时所获得的收益，最优值函数fk(sk)表示分配给第k个至第3个项目的资金为sk时所获得的最大总收益。（1）K=3时(第3阶段)注意到C的投资额不超过4百万元，允许状态集合{1,2,3,4},即用剩余额S3＝1，2，3，4投资项目C，得到的收益为：3333(1)4,(2)8,(3)11,(4)15ffff（2）K=2时(第2阶段)注意到C的投资额至少是1百万元，允许决策集合D2(S2)＝{0,1,…,S2-1},下面是各种可能方案的列表：允许状态集合{1,2,3,4，5},S2＝1S2＝2S2＝3S2＝4S2＝5BCBCBCBCBC01020304141112132321223231故：223(1)(0)(1)4fgf23223(0)(2)08(2)maxmax9(1)(1)54gffgf2322323(0)(3)011(3)max(1)(2)max5814104(2)(1)gffgfgf232322323(0)(4)015(1)(3)511(4)maxmax18(2)(2)108124(3)(1)gfgffgfgf2322323(1)(4)515(5)max(2)(3)max101121128(3)(2)gffgfgf（3）K=1时（第1阶段）S1＝5允许决策集合D1(S1)＝{0,1,2,3,4},12121121212(0)(5)021(1)(4)318(5)max(2)(3)max61421109(3)(2)124(4)(1)gfgffgfgfgf应用顺序追踪可知，最优方案有两个：方案1：***1230,2,3uuu方案2：***1231,2,2uuu最大收益都为21百万元。二、可回收利用的资源分配问题设有某种资源，初始的拥有量是s1。计划在A、B两个生产车间连续使用n个阶段。巳知在A车间投入资源x时的阶段收益是g(x)，在B车间投入资源y时的阶段收益是h(y)。投入的资源在生产过程中有部分消耗,已知，每生产一个阶段后，车间A、B的资源回收率分别为a和b，0＜a，b＜1。回收的资源下一阶段可继续使用，求使用n个阶段后总收益最大的资源分配方案。设sj为第j阶段投入A、B两个车间使用的资源数，j=1、2、…、n。该模型可用动态规划的方法来处理。设xj为第j阶段投入A车间使用的资源数，投入B车间使用的资源数为yj=sj-xj，j=1、2、…、n。此问题的静态规划模型为：11122221113222111max()()()()()()()().()0,1,2,,nnnnnnnjjzgxhsxgxhsxgxhsxsaxbsxsaxbsxstsaxbsxxsjn最优值函数fk(sk)表示第k阶段拥有资源数为sk时，从第k阶段至第n阶段采取最优分配方案进行生产时所获得的最大总收益。令sk为状态变量，表示在第k阶段投入A、B两个车间使用的资源数，k=1、2、…、n。xk为决策变量，表示在第k阶段投入A车间使用的资源数，则yk=sk-xk表示第k阶段投入B车间使用的资源数，k=1、2、…、n。状态转移方程为：sk+1=axk+b(sk-xk)下面我们对一个具体问题，用此方法求解。则动态规划的递推公式：1111()max()()()()0kkkkkkkkxnnfsgxhsxfsfs例2：(机器负荷分配问题)某公司新购进1000台机床，每台机床都可在高、低两种不同的负荷下进行生产，设在高负荷下生产的产量函数为g(x)=10x(单位：百件)，其中x为投入生产的机床数量，年完好率为a=0.7；在低负荷下生产的产量函数为h(y)=6y(单位：百件)，其中y为投人生产的机床数量，年完好率为b=0.9。计划连续使用5年，试问每年如何安排机床在高、低负荷下的生产计划，使在五年内生产的产品总产量达到最高。解：该问题可看作一个5阶段决策问题，一个年度就是一个阶段。决策变量xk为在第k阶段投入高负荷下生产的机床数。状态转移方方程为：sk+1=axk+b(sk-xk)=0.7xk+0.9(sk-xk)第k年度的产量为：vk(sk,xk)=10xk+6(sk-xk)则动态规划的基本方程为：最优值函数fk(sk)表示拥有机床数为sk时，从第k年度至第五年度采取最优分配方案进行生产时所获得的最大总产量。1111()max()()()()0kkkkkkkkxnnfsgxhsxfsfs状态变量sk取为第k年度初拥有的完好机床台数。下面第5年度开始，用逆推归纳法进行计算。5555555660()max()()()xsfsgxhsxfs因为是x5的单调增加函数，故最大解为：55()fs55*xs1）k=5时，有相应有555()10fss55555555500max106()0max46xsxsxsxxs2)k=4时，有44444444455044450()max()()()max106()10xsxsfsgxhsxfsxsxs因为是x4的单调增加函数，故最大解为：44()fs444()17fss44*xs相应有44444444440440max106()10(0.70.9())max215xsxsxsxxsxxs3)k=3时，有因为是x3的单调增加函数，故最大解为：33()fs333()21.9fss33*xs33333333344033340()max()()()max106()17xsxsfsgxhsxfsxsxs相应有33333333330330max106()17(0.70.9())max0.621.3xsxsxsxxsxxs4）k=2时，有22222222233022230()max()()()max106()21.9xsxsfsgxhsxfsxsxs因为是x2的单调减少函数，故最大解为：22()fs2*0x222()25.71fss相应有22222222220220max106()21.9(0.70.9())max0.3825.71xsxsxsxxsxxs5）k=1时，有11111111122011120()max()()()max106()25.71xsxsfsgxhsxfsxsxs因为是x1的单调减少函数，故的最大解为：11()fs1*0x111()29.139fss相应有11111111110110max106()25.71(0.70.9())max1.14229.139xsxsxsxxsxxs即前两年应把年初全部完好机床投入低负荷生产，后三年应把年初全部完好机床投入高负荷生产。这样所得的产量最高，其最高产量为29139百件产品。同时，从求解过程还可反过来确定每年年初的状态，即每年年初所拥有的完好机器台数。已知s1=1000，于是可得：由于第l阶段的初始状态s1是给定的，即s1=1000，因此最优目标函数值为=29139（百件）。11()fs12334455*0,*0,*,*,*xxxsxsxs计算结果表明，最优策略为：21111322224333354444655550.70.9()0.9900(0.70.9()0.9810(0.70.9()0.7567(0.70.9()0.7397(0.70.9()0.7278(sxsxssxsxssxsxssxsxssxsxs台)台)台)台)台)假设有一个企业，要制定某种产品n个时期(例如年、月、周)的生产(或购买)计划，已知初始的存贮量为零，第k个时期市场需求量为dk，每个时期企业的最大产量为M，单位产品的生产成本为a，每次生产的生产准备成本为K。设xk为第k个时期(阶段)该产品的生产量。sk为第k个时期(阶段)末该产品的库存量，则有sk=sk-1+xk-dk。三、生产与存贮问题ck(xk)表示第k个时期(阶段)该产品产量为xk时的生产成本，它包括生产准备成本K和产品成本axk两项费用，即：0,0(),1,2,,,kkkkkkxcxKaxxMxMhk(xk)表示在第k个时期(阶段)结束时库存量为sk时所需的存贮费用。故第k个阶段的总成本费用为：()()kkkkcxhs问如何安排生产(或购买)计划使得n个时期总成本费用最低？上述问题的数学模型为：101min[()()]0,0()0,1,2,,0,1,2,,,1,2,,nkkkkknkkjjjkkzcxhssssxdknxMknxkn为整数现在我们用动态规划的顺推归纳法来讨论，把它看作一个n阶段决策问题。令:1110()min{[()()]}min{()()()}1,2,,jkkkkkjjjjxjkkkkkkxfscxhscxhsfskn最优值函数fk(sk)表示从第1阶段初始库存量为0到第k阶段末库存量为sk时的最小总成本费用。sk为状态变量，表示第k个阶段末该产品的库存量。xk为决策变量，它表示第k阶段的生产量。则状态转移方程为：sk-1=sk-xk+dk。则其顺序递推关系式：其中σk=min{dk+sk,