《运筹学ch09》由会员分享，可在线阅读，更多相关《运筹学ch09（121页珍藏版）》请在金锄头文库上搜索。
1、清华大学出版社,1,五、动态规划,第8章 动态规划的基本方法 第9章 动态规划应用举例,清华大学出版社,2,第9章 动态规划应用举例,第1节 资源分配问题 第2节 生产与存储问题 第3节* 背包问题 第4节* 复合系统工作可靠性问题 第5节 排序问题 第6节 设备更新问题 第7节* 货郎担问题,清华大学出版社,3,第1节 资源分配问题,所谓分配问题，就是将数量一定的一种或若干种资源(例如原材料、资金、机器设备、劳力、食品等等)，恰当地分配给若干个使用者，而使目标函数为最优。,清华大学出版社,4,1.1资源分配问题,设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其
2、收益为,问应如何分配，才能使生产n产品的总收入最大? 此问题可写成静态规划问题：,当,都是线性函数时，它是一个线性规划问题；当,是非线性函数时，它是一个非线性规划问题。但当n比较大时，具体求解是比较麻烦的。由于这类问题的特殊结构，可以将它看成一个多阶段决策问题，并利用动态规划的递推关系来求解。,清华大学出版社,5,1.1资源分配问题,在应用动态规划方法处理这类“静态规划”问题时，通常以把资源分配给一个或几个使用者的过程作为一个阶段，把问题中的变量xi为决策变量，将累计的量或随递推过程变化的量选为状态变量。,清华大学出版社,6,1.1资源分配问题,设状态变量sk表示分配用于生产第k种产品至第n种
3、产品的原料数量。 决策变量uk表示分配给生产第k种产品的原料数，即uk=xk 状态转移方程：,允许决策集合：,令最优值函数,表示以数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收入。因而可写出动态规划的逆推关系式为：,利用这个递推关系式进行逐段计算，最后求得 即为所求问题的最大总收入。,清华大学出版社,7,1.1资源分配问题,例1 某工业部门根据国家计划的安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如表9-1所示。,问：这五台设备如何分配给各工厂，才能使国家得到的盈利最大。,清华大学出版社,8,1.1资源分配问题,解
4、: 将问题按工厂分为三个阶段，甲、乙、丙三个工厂分别编号为1、2、3 设sk表示为分配给第k个工厂至第n个工厂的设备台数。xk表示为分配给第 k个工厂的设备台数。则,为分配给第k+1个工厂至第n个工厂的设备台数。,表示为sk台设备分配到第k个工厂所得的盈利值。,表示为sk台设备分配给第k个工厂至第n个工厂时所得到的最大盈利值。,因而可写出逆推关系式为,清华大学出版社,9,1.1资源分配问题,下面从最后一个阶段开始向前逆推计算。 第三阶段： 设将s3台设备(s3=0,1,2,3,4,5)全部分配给工厂丙时，则最大盈利值为,其中x3=s3=0,1,2,3,4,5,因为此时只有一个工厂，有多少台设备
5、就全部分配给工厂丙，故它的盈利值就是该段的最大盈利值，如下表。,表中x3*表示使f3(s3)为最大值时的最优决策。,清华大学出版社,10,1.1资源分配问题,第二阶段： 设把s2台设备(s2=0,1,2,3,4,5)分配给工厂乙和工厂丙时，则对每个s2值，有一种最优分配方案，使最大盈利值为,其中,因为给乙工厂x2台，其盈利为p2(x2) ，余下的s2x2台就给丙工厂，则它的盈利最大值为f3(s2 x2) 。现要选择x2的值，使,取最大值。其数值计算如表9-3所示。,清华大学出版社,11,1.1资源分配问题,表9-3,清华大学出版社,12,1.1资源分配问题,第一阶段： 设把s1台(这里只有s1
6、=5的情况)设备分配给甲、乙、丙三个工厂时，则最大盈利值为,其中,因为给甲工厂x1台，其盈利为p1(x1) ，剩下的5x1台就分给乙和丙两个工厂，则它的盈利最大值为f2(5x1) 。现要选择x1值，使,取最大值，它就是所求的总盈利最大值，其数值计算如表9-4所示。,表9-4,清华大学出版社,13,1.1资源分配问题,然后按计算表格的顺序反推算，可知最优分配方案有两个： (1) 由于x1*=0 ，根据,查表9-3知x2*=2，由,故,即得甲工厂分配0台，乙工厂分配2台，丙工厂分配3台。 (2) 由于x1*=2，根据,查表9-3知x2*=2，由,故,即得甲工厂分配2台，乙工厂分配2台，丙工厂分配1
7、台。 以上两个分配方案所得到的总盈利均为21万元。,清华大学出版社,14,1.1资源分配问题,资源连续分配问题 设有数量为s1的某种资源，可投入A和B两种生产。第一年若以数量u1投入生产A，剩下的量s1u1就投入生产B，则可得收入为,其中g(u1)和h(u1)为已知函数，且g(0)=h(0)=0。这种资源在投入A、B生产后，年终还可回收再投入生产。设年回收率分别为0a1和0b0,cd。年回收率分别为a和b,0ab1。试求出最优策略的一般关系式。显然，这时状态转移方程为,k段的指标函数为,令fk(sk)表示由状态sk出发，从第k年至第n年末时所生产的产品的总产量最大值。,清华大学出版社,25,1
8、.1资源分配问题,可写出逆推关系式为：,我们知道，在低负荷下生产的时间愈长，机器完好率愈高，但生产产量少。而在高负荷下生产产量会增加，但机器损坏大。这样，即使每台产量高，总起来看产量也不高。,清华大学出版社,26,1.1资源分配问题,从前面的数字计算可以看出，前几年一般是全部用于低负荷生产，后几年则全部用于高负荷生产，这样才产量最高。如果总共为n年，从低负荷转为高负荷生产的是第t年，1tn。即是说，从1至t1年在低负荷下生产，t至n年在高负荷下生产。现在要分析t与系数a、b、c、d是什么关系。 从回收率看，(b a)值愈大，表示在高负荷下生产时，机车损坏情况比在低负荷时严重得多，因此t值应选大
9、些。从产量看，(c d)值愈大，表示在高负荷下生产较有利，故t应选小些。下面我们从(9-2)式这一基本方程出发来求出t与(b a)、(c d)的关系。,清华大学出版社,27,1.1资源分配问题,令,。则在低负荷生产时有,，高负荷生产时有,对第n段，有,由于cd，所以,应选1才能使,最大。也就是说，最后一年应全部投入高负荷生产。故,清华大学出版社,28,1.1资源分配问题,对n-1段，根据(9-2)式有,因此，欲要满足上式极值关系的条件是当,时，应取,即n 1年仍应全部在高负荷下生产。否则，当(9-4)式不满足时，应取,即n 1年应全部投入低负荷生产。,清华大学出版社,29,1.1资源分配问题,
10、由前面知道，只要在第k年投入低负荷生产，那么递推计算结果必 然是从第1年到第k年均为低负荷生产，即有,可见，算出后 ，前几年就没有必要再计算了。故只需研究哪一年由低负荷转入高负荷生产，即从 那一年开始变为1就行。根据这点，现只分析满足(9-4)式的情况。由于,故(9-3)式变为,又由于,将它代入上式得,清华大学出版社,30,1.1资源分配问题,对n-2段，由(9-2)式有,由此可知，只要满足极值条件式,就应选,否则为0，即应继续在高负荷下生产。,清华大学出版社,31,1.1资源分配问题,依次类推，如果转入高负荷下生产的是第t年，则由,可以推出，应满足极值关系的条件必然是：,相应的有最优策略,它
11、就是例2在始端固定终端自由情况下最优策略的一般结果。,从本例可看出，应用动态规划，可以在不求出数值解的情况下，确定最优策略的结构。,清华大学出版社,32,1.1资源分配问题,例如，只要知道了a,b,c,d四个值，就总可找到一个t值，满足(9-5)式，且,例如题中给定的,代入(9-5)式，应有,可见,所以t=3，即从第三年开始将全部机器投入高负荷生产，五年内总产量最高。,清华大学出版社,33,1.1资源分配问题,上面的讨论表明： 当x在0，s1上离散地变化时，利用递推关系式逐步计算或表格法而求出数值解。 当x在0，s1上连续地变化时， 若g(x)和h(x)是线性函数或凸函数时，根据递推关系式运用解析法不难求出fk(x)和最优解； 若g(x)和h(x)不是线性函数或凸函数时，一般来说，解析法不能奏效，那只好利用递推关系式(91)求其数值解。首先要把问题离散化，即把区间0，s1进行分割，令x=0，2，m=s1。其的大小，应根据计算精度和计算机容量等来确定。然后规定所有的fk(x)和决策变量只在这些分割点上取值。这样，递推关系式(9-1)便可写为,清华大学出版社,34,1.1资源分配问题,对,依次计算，可逐步求出,及相应的最优决策，最后求得,就是所求的最大总收入。 这种离散化算法可以编成程序在计算机中计算。,
