运筹学第九章动态规划应用举例课件.ppt

《运筹学第九章动态规划应用举例课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章动态规划应用举例(DualityTheory)一维资源分配问题生产与存贮问题背包问题设备更新问题货郎担问题第一节一维资源分配问题一、一维资源分配问题基本模型及求解方法1.模型设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为gi(xi)。问应如何分配，才能使生产n种产品的总收入最大？此问题可写成静态规划问题：在应用动态规划处理这类“静态规划”问题时，通常以把资源分配给一个或几个使用者的过程作为一个阶段，把问题中的变量xi作为决策变量，将累计的量或随递推过程变化的量选为状态变量。当gi(xi)都是

2、线性函数时，它是一个线性规划问题；当gi(xi)不是线性函数时，它是一个非线性规划问题。但当n较大时，具体求解是比较麻烦的。然而，由于这类问题的特殊结构，可以将它看成一个多阶段决策问题，并利用动态规划得递推关系来解。2.求解方法设状态变量sk表示分配用于生产第k种产品至第n产品的原料数量。则s1=a，可用逆推法求解。设决策变量uk表示分配给生产第k种产品的原料数量，即:uk=xk状态转移方程：允许决策集合：把该分配问题看成是对资源总量的消耗过程。令最优值函数fk(sk)表示以数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收入

3、。递推关系式为：利用这个递推关系式进行逐段计算，最后求得最大总收入为f1(a)例1某公司有9个推销员在全国三个不同市场推销货物，这三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案。解：设分配人员的顺序为市场1,2,3，已知s1=9，用逆推法。设sk为第k阶段尚未分配的人员数，xk为第k阶段分配的推销人员数。则状态转移方程为sk＋1=sk–xk目标函数为二、离散的一维资源分配问题第三阶段：给第三市场分配s3有0－9种可能，第三阶段最优决策表如下：第二阶段：给第二市场分配s2有0~9种可能，第二阶段最优决策表如下：状态转

4、移方程：s3=s2–x2第一阶段：给第一市场分配由边界条件s1=9，第一阶段最优决策表如下：得决策过程：x1*=2,x2*=0,x3*=7,f1*=218即市场1分配2人，市场2不分配，市场3分配7人，最大收益为218万元。状态转移方程：s2=s1–x1在资源分配问题中，还有一类要考虑资源回收利用问题，这里决策变量为连续值，故称为资源连续分配问题。这类问题一般描述如下：设有数量为s1的某种资源，可投入A和B两种生产。第一年若以数量u1投入生产A，剩下的量s1-u1就投入生产B，则可得收入为g(u1)+h(s1-u1)，其中g(u1)和h

5、(u1)为已知函数，且g(0)=h(0)=0。这种资源在投入生产A、B后，年终还可回收再投入生产。设年回收率分别为0

6、为可投入B生产的资源量。已知s1，可用逆推法求解。状态转移方程：令最优值函数fk(sk)表示以数量为sk的资源量分配给第k阶段至第n阶段所得到的最大总收入。递推关系式为：最后求得最大总收入为f1(s1)。例2机器负荷分配问题解：设状态变量sk表示第k年度初拥有的完好机器数量，同时表示第k－1年度末拥有的完好机器数量。设决策变量uk表示第k年度中分配高负荷下生产的机器数量，则sk－uk为该年度中分配低负荷下生产的机器数量。状态转移方程：允许决策集合：令最优值函数fk(sk)表示以资源量sk出发，从第k年开始至第5年结束时，生产的产品最大值

7、。递推关系式为：设vk(sk,uk)为第k年度的产量，则vk＝8uk＋5(sk－uk)故指标函数为：当k=5时，有求得最大解：相应的，有因，故最高产量为（台）第二节生产与存贮问题设某公司要制定一项n个阶段的生产计划。已知初始库存为零，每阶段该产品的生产量有上限的限制；每阶段社会对该产品的需求量是已知的，在n阶段末库存为零。问该公司如何制定每个阶段的生产计划，使产品总成本最低。一、生产计划问题1.问题的提出设dk为第k阶段对产品的需求量，xk为第k阶段该产品的生产量，sk＋1为k阶段末的产品库存量。则有sk＋1＝sk＋xk－dk由此可见，

8、过程演化方向由s1至sn＋1。2.基本模型设ck(xk)表示第k阶段生产量xk的成本费用，它包括生产准备成本K和产品成本a·xk(a是单位产品成本)两项费用，hk(sk)为第k阶段开始时有产品库存量sk所需