运筹学第10章2讲

设有数量为s1的某种资源，可投入A和B两种生产。第一年若以数量u1投入生产A，剩下的量s1−u1就投入生产B，则可得收入为其中g(u1)和h(u1)为已知函数，且g(0)=h(0)=0。这种资源在投入A、B生产后，年终还可回收再投入生产。设年回收率分别为0<a<1和0<b<1，则在第一年生产后，回收的资源量合计为第二年再将资源数量s2中的u2和s2−u2分别再投入A、B两种生产，则第二年又可得到收入为如此继续进行n年，试问：应当如何决定每年投入A生产的资源量才能使总的收入最大?资源连续分配问题此问题写成静态规划问题为状态转移方程为

最后求出f1(s1)即为所求问题的最大总收入。下面用动态规划方法来处理。设sk为状态变量，它表示在第k阶段(第k年)可投入A、B两种生产的资源量。uk为决策变量，它表示在第k阶段(第k年)用于A生产的资源量阶段指标函数为递推关系式为最优值函数fk(sk)表示有资源量sk

，从第k阶段至第n阶段采取最优分配方案进行生产后所得到的最大总收入。

例2

机器负荷分配问题某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为g=8u1

，其中u1为投入生产的机器数量，年完好率a=0.7；在低负荷下生产的产量函数为h=5y，其中y为投入生产的机器数量，年完好率为b=0.9。假定开始生产时完好的机器数量s1=1000台，试问每年如何安排机器在高、低负荷下的生产，使在五年内生产的产品总产量最高。

状态转移方程为

k段允许决策集合为设为第k年度的产量，即阶段指标函数构造这个问题的动态规划模型：设阶段序数k表示年度。

状态变量sk为第k年度初拥有的完好机器数量，同时也是第k−1年度末时的完好机器数量。决策变量uk为第k年度中分配高负荷下生产的机器数量，于是sk−uk为该年度中分配在低负荷下生产的机器数量。

因而有逆推关系式：当k=5时，因f5是u5的线性单调增函数，故得最大解u5*=s5，相应的有

当k=4时，有故得最大解，u4*=s4，相应的有依此类推，可求得 因s1=1000，故u5*=s5，最优策略为

已知s1=1000台，于是可得1.2二维资源分配问题

设有两种原料，数量各为a和b单位，需要分配用于生产n种产品。如果第一种原料以数量xi为单位，第二种原料以数量yi为单位，用于生产第i种产品，其收入为问应如何分配这两种原料于n种产品的生产使总收入最大?此问题可写成静态规划问题：设状态变量(x,y):x——分配用于生产第k种产品至第n种产品的第一种原料的单位数量。y——分配用于生产第k种产品至第n种产品的第二种原料的单位数量。决策变量xk——分配给第k种产品用的第一种原料的单位数量。yk——分配给第k种产品用的第二种原料的单位数量。状态转换关系： 式中和分别表示用来生产第k+1种产品至第n种产品的第一种和第二种原料的单位数量。用动态规划方法来解，状态变量和决策变量要取二维的。允许决策集合：

表示以第一种原料数量为x单位，第二种原料数量为y单位，分配用于生产第k种产品至第n种产品时所得到的最大收入。最后求得即为所求问题的最大收入。

可写出逆推关系为求解方法：1、拉格朗日乘数法2、逐次逼近法3、粗格子点法(疏密法)——降维——数值计算

表示以第一种原料数量为x单位，第二种原料数量为y单位，分配用于生产第k种产品至第n种产品时所得到的最大收入。1.3

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

若第1种资源的单位价格为a，第2种资源的单位价格为b，现有资金Z。此问题的数学模型：

(1)把资源分配利润表换算成资金分配利润表，即将换算成但必须注意，分配的资金应先使较贵的资源单位最大。知，在给定z的情况下，若购买第2种资源yk单位，则留下的资金只能购买第1种资源xk单位，于是得到资金利润函数Rk(z)为式中(z/b)指以资金z购买第2种资源的最大单位数，分配到第k个生产行业，则由设有资金资金z购买了第2种资源yk单位以后能购买第1种资源的最大单位数。指以(2)计算最优资金分配所获得最大利润。规定最优值函数fk(