运筹学第10章动态规划

第十章动态规划§1动态规划的基本概念与基本思路§2多阶段决策过程最优化问题举例§3动态规划的应用(1)§4动态规划的应用(2)1动态规划是一种研究多阶段决策问题的理论和方法，在决策中将问题分成若干阶段，对不同阶段采取不同的决策，使全过程达到整体最优。所谓多阶段决策问题是指这样一类决策过程，当每个阶段的决策选定以后，过程也就随之确定。把各个阶段的决策综合起来，构成一个决策序列，称为一个策略。显然由于各个阶段选取的决策不同，对应整个过程就可以有一系列不同的策略。当对过程采取某一策略时，可以得到一个确定的（或期望的）效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中间选取一个最优的策略，使在预定的标准下得到最好的效果。2与线性规划相比，动态规划问题没有一个标准的数学模型。然而，动态规划是一类很普遍的问题解决方法，需要建立特定的方程以适应各种情况。在多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前的状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义。因此,把处理它的方法称为动态规划方法。但是,一些与时间没有关系的静态规划(如线性规划、非线性规划等)问题,只要人为地引进“时间”因素,也可把它视为多阶段决策问题,用动态规划方法去处理。动态规划问题的复杂性在于各阶段决策之间的相互联系。根据实际问题构造动态规划模型往往需要掌握更多的技巧。34最短路径问题：引例。如图

,给定一个线路网络,两点之间连线上的数字表示两点间的距离(或费用),试求一条由A到G的铺管线路,使总距离为最短(或总费用最小)。§1动态规划的基本概念5由图可知,从A点到G点可以分为6个阶段。从A到B为第一阶段,从B到C为第二阶段⋯从F到G为第六阶段。在第一阶段,A为起点,终点有B1、B2两个,因而这时走的路线有两个选择,一是走到B1;一是走到B2,若选择走到B2的决策,则B2就是第一阶段在我们决策之下的结果。它既是第一阶段路线的终点,又是第二阶段路线的始点。在第二阶段,再从B2点出发,对应于B2点就有一个可供选择的终点集合{C2,C3,C4};若选择由B2走至C2为第二阶段的决策,则C2就是第二阶段的终点,同时又是第三阶段的始点。同理递推下去,可看到:各个阶段的决策不同,铺管路线就不同。很明显,当某阶段的始点给定时,它直接影响着后面各阶段的行进路线和整个路线的长短,而后面各阶段的路线的发展不受这点以前各阶段路线的影响。故此问题的要求是:在各个阶段选取一个恰当的决策,使由这些决策组成的一个决策序列所决定的一条路线,其总路程最短。61、动态规划的基本概念1.阶段把所给问题的过程,恰当地分为若干个相互联系的阶段,以便能按一定的次序去求解。描述阶段的变量称为阶段变量,常用k表示。阶段的划分,一般是根据时间和空间的自然特征来划分,但要便于把问题的过程能转化为多阶段决策的过程。如引例可分为6个阶段来求解,k分别等于1、2、3、4、5、6。72.状态状态表示每个阶段开始所处的自然状况或客观条件,它描述了研究问题过程的状况,又称不可控因素。在引例中,状态就是某阶段的出发位置。它既是该阶段某支路的起点,又是前一阶段某支路的终点。通常一个阶段有若干个状态,第一阶段有一个状态就是点A,第二阶段有两个状态,即点集合{B1,B2},一般第k阶段的状态就是第k阶段所有始点的集合。8描述过程状态的变量称为状态变量。常用sk

表示第k阶段的状态变量。如在引例中第三阶段有四个状态,则状态变量sk

可取四个值,即C1、C2、C3、C4。点集合{C1,C2,C3,C4}就称为第三阶段的可达状态集合。记为S3={C1,C2,C3,C4}。有时为了方便起见,将该阶段的状态编上号码1,2⋯这时也可记S3={1,2,3,4}。第k阶段的可达状态集合就记为Sk

。9这里所说的状态应具有下面的性质:如果某阶段状态给定后,则在这阶段以后过程的发展不受这阶段以前各段状态的影响。换句话说,过程的过去历史只能通过当前的状态去影响它未来的发展,当前的状态是以往历史的一个总结。这个性质称为无后效性(即马尔科夫性)。如果状态仅仅描述过程的具体特征,则并不是任何实际过程都能满足无后效性的要求。所以,在构造决策过程的动态规划模型时,不能仅由描述过程的具体特征这点着眼去规定状态变量,而要充分注意是否满足无后效性的要求。103.决策决策表示当过程处于某一阶段的某个状态时,可以作出不同的决定(或选择),从而确定下一阶段的状态,这种决定称为决策。描述决策的变量,称为决策变量。常用xk

(sk

)或uk

(sk

)表示第k阶段当状态处于sk

时的决策变量。它是状态变量的函数。在实际问题中,决策变量的取值往往限制在某一范围之内,此范围称为允许决策集合。常用Dk

(sk

)表示第k阶段从状态sk

出发的允许决策集合,显然有xk

(sk

)∈Dk

(sk

)。11如在引例

第二阶段中,若从状态B1出发,就可作出三种不同的决策,其允许决策集合D2(B1)={C1,C2,C3},若选取的点为C2,则C2是状态B1在决策x2(B1)作用下的一个新的状态,记作x2(B1)=C2。124.策略策略是一个按顺序排列的决策组成的集合。由过程的第k阶段开始到终止状态为止的过程,称为问题的后部子过程(或称为k子过程)。由每段的决策按顺序排列组成的决策函数序列{xk

(sk

),⋯,xn

(sn

)}称为k子过程策略,简称子策略,记为pk,

n

(sk

)。即13145.状态转移方程状态转移方程用来表示过程由一个状态到另一个状态的演变。若给定第k阶段状态变量sk

的值,如果该段的决策变量uk

一经确定,第k+1阶段的状态变量sk

+1

的值也就完全确定。即sk

+1

的值随sk

和uk

的值变化而变化。这种确定的对应关系,记为上式描述了由k阶段到k+1阶段的状态转移规律,称为状态转移方程。Tk

称为状态转移函数。156.指标函数和最优值函数指标函数是衡量所选策略优劣的数量指标，具体可以是收益、成本、距离等指标。分为k阶段指标函数、k子过程指标函数及最优指标函数。

k阶段指标函数从k阶段状态sk出发，选择决策xk所产生的第k阶段指标，称为k阶段指标函数,记为rk(sk,xk)。16从k阶段状态sk出发，选择决策xk,xk+1,…,xn所产生的过程指标，称为k子过程指标函数或简称过程指标函数，记为Vk(sk,xk,xk+1,…,xn)或Vk，n为阶段数。过程指标函数最优指标函数从k阶段状态sk出发，对所有的子策略，最优的过程指标函数称为最优指标函数，记为fk(sk)，通常取Vk的最大值或最小值。17动态规划要求过程指标满足递推关系

，即连和形式：最优指标函数是18动态规划数学模型、边界条件及状态转移方程构成。如连和形式的数学模型连乘形式(vj≠0)：最优指标函数是19对于可加性指标函数，上式可以写为上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以写为上式称为动态规划最优指标的递推方程，是动态规划的基本方程。终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，即确定最后一个初始状态n+1下最优指标fn+1(sn+1)的值。nksfxsvsfkkkkksDxkkoptkkk,,2,1)}(},({)(11)(L=+=++Î20动态规划方法的基本思想结合解决最短路线问题来介绍动态规划方法的基本思想。生活中的常识告诉我们,最短路线有一个重要特性:如果由起点A经过P点和H点而到达终点G是一条最短路线,则由点P出发经过H点到达终点G的这条子路线,对于从点P出发到达终点的所有可能选择的不同路线来说,必定也是最短路线。此特性用反证法易证。因为如果不是这样,则从点P到G点有另一条距离更短的路线存在,把它和原来最短路线由A点到达P点的那部分连接起来,就会得到一条由A点到G点的新路线,它比原来那条最短路线的距离还要短些。这与假设矛盾,是不可能的。21例如,在最短路线问题中,若找到了A→B4→C3→D1→E是由A到E的最短路线,则B4→C3→D1→E应该是由B4出发到E点的所有可能选择的不同路线中的最短路线。最优化原理作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。22根据最短路线这一特性,寻找最短路线的方法,就是从最后一段开始,用由后向前逐步递推的方法,求出各点到E点的最短路线,最后求得由A点到E点的最短路线。所以,动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。23动态规划求解思路（1）将多阶段决策问题按照空间或时间顺序划分成相互联系的阶段，从而把问题化成一族同类型的子问题，恰当地选取状态变量和决策变量，写出状态转移方程，定义最优指标函数，写出递推关系式和边界条件。（2）求解从边界条件开始，由后向前逐段递推寻找最优。在每一个阶段的计算中都要用到前一阶段的子问题的最优结果，最后一个子问题的最优解就是整个问题的最优解。（3）在多阶段决策过程中，确定阶段k的最优决策时，不仅要考虑本阶段最优，而且要考虑本阶段及其所有后部子过程的整体最优。

24§2多阶段决策过程最优化问题举例例1最短路径问题

下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。BACBDBCDEC41231231232216472483867561106375125§2多阶段决策过程最优化问题举例如何解决这个问题呢?可以采取穷举法。即把由A到E所有可能的每一条路线的距离都算出来，然后互相比较找出最短者，相应地得出了最短路线。这样，由A到E的4个阶段中,一共有4×3×2×1=24条不同的路线，比较24条不同的路线的距离值,才找出最短路线为A→B4→C3→D1→E

，相应最短距离为14。显然,这样作计算是相当繁杂的。如果当段数很多,各段的不同选择也很多时,这种解法的计算将变得极其繁杂,甚至在电子计算机上计算都是不现实的。因此,为了减少计算工作量,需要寻求更好的算法,这就是要介绍的动态规划的方法。26第一步建模阶段k：划分为四个阶段，k=1,2,3,4决策变量xk：第k阶段要到达的位置状态变量sk：第k阶段出发的位置Sk：第k阶段状态集合，即状态变量的取值范围Dk（sk）：第k阶段从状态sk出发允许的决策集合sk+1=Tk(sk,xk)：状态转移方程rk(sk,xk)：第k阶段从状态sk出发，采取决策xk到达第k+1阶段的状态sk+1时两点间的距离fk(sk)表示从第k阶段的状态sk出发，到终点的最短距离，f1(s1)即为所求。27基本方程：fk(sk)=min{rk(sk,xk)+fk+1(sk+1)},k=4,3,2,1终点条件：fn+1(sn+1)=0即f5(E)=0由于E是终点，所以不再移动了。一般情况下，终点（边界）条件或者取0（递推方程连加的形式下）或者取1（递推方程连乘的形式下）28第二步逆推求解求解要做的是在给定状态下做决策。本题中是站在始点选终点。第四阶段，状态s4可取两个值D1和D2，根据到最终终点E的距离最短来决策。最优值函数计算的也就是各状态点到E的最短距离。在状态D1下，到E的路径只有一条，故只能选择这一条，这也是最优的，f4(D1)=min{r4(D1,E)+f5(E)}=10在状态D2下，同理f4(D2)=min{r4(D2,E)+f5(E)}=6第三阶段，状态s3可取三个值C1、C2和C3在状态C1下，D3(C1)={D1,D2}。有两个地点可选择，根据到E距离最短来选择。f3(C1)=min{r3(C1,D1)+f4(D1);r3(C1,D2)+f4(D2)}=min{8+10;6+6}=12。选择C1经D2到E29第二步逆推求解-表格形式

1、以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di

、Ci、Bi、A到E的最短路径问题。第四阶段：两个始点（初始状态变量）D1和D2，终点（决策变量）只有一个；

表10-1分析得知：从D1和D2到E的最短路径唯一。阶段4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)

ED1D2

106

106

EE30第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2

的最短路径问题：

表10-2分析得知：如果经过C1，则最短路为C1-D2-E；如果经过C2，则最短路为C2-D2-E；如果经过C3，则最短路为C3-D1-E。

§2多阶段决策过程最优化问题举例阶段3本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12

121111

D2D2D131第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3

的最短路径问题：

表10-3

分析得知：如果经过B1，则走B1-C2-D2-E；如果经过B2，则走B2-C3-D1-E；如果经过B3，则走B3-C3-D1-E；如果经过B4，则走B4-C3-D1-E。

§2多阶段决策过程最优化问题举例阶段2本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=12

12131412

C2C3C3C332第一阶段：只有1个始点A，终点有B1,B2,B3,B4

。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：

表10-4最后，可以得到：从A到E的最短路径为AB4C3D1E§2多阶段决策过程最优化问题举例阶段1本阶段始点(状态)本阶段各终点（决策）到E的最短距离本阶段最优终点(最优决策)B1B2B3B4A4+12=163+13=163+14=172+12=14

12

C233

以上计算过程及结果，可用图2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。

以上过程，仅用了22次加法，计算效率远高于穷举法。BACBDBCDEC41231231233216472483867516106010612111112131414127512§1多阶段决策过程最优化问题举例34动态规划小结问题可以被分解为几个阶段，每个阶段要求进行决策。每个阶段都有大量与其相关的状态。任意阶段所选定的决策描述了当前阶段的状态如何转移为下一阶段的状态。已知当前状态，其他各个阶段的决策不能依赖于先前到达的状态或先前选定的决策。存在递推表达式，将阶段t，t+1，…，T期间的成本和收益与阶段t+1，…，T期间的成本和收益联系起来。要使用动态规划解决问题，需要确定合适的状态、阶段和决策。35决策目标是在各个阶段的每一种状态下，选择合适的决策变量来最优化成本或收益的累积表达式。可通过罗列来找出（在离散决策变量时），也可通过决策变量的给定区间，求解出最优值及取最优值时决策变量的取值。要正确表达递推公式，需要确定３个重要方面：对于给定状态和阶段而言，容许或可行的决策集（决策变量的取值范围）；必须指出阶段k的值、当前状态和在阶段k所选择的决策如何影响当前阶段的费用；必须指出阶段k的值、当前状态和在阶段k所选择的决策如何影响阶段k+1的状态。36动态规划的步骤第一划分阶段。第二设定决策变量。第三设定状态变量。根据决策变量，寻找能够影响决策变量的因素作为状态，状态不是只有一个确定的状态，而是有多个状态，在每个状态下需进行最优决策。第四，确定每一状态下决策变量的取值范围。第五，写出状态转移方程。第六，写出阶段指标表达式。第七，写出终端条件。第八，写出递推方程。37状态变量的设定：当前还有多少可用库存，还有多少可用分配的资源，还有多少可供利用的空间。当前产品存储量是多少。3839一、资源分配问题

例2.某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表10-5所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？

表10-5盈利工厂设备台数甲厂乙厂丙厂0

0

0

0

1

3

5

4

2

7

10

6

3

9

11

11

4

12

11

12

5

13

11

12§3动态规划的应用(1)40解：阶段k：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设状态变量：sk=可分配给第k个厂至第3个厂的设备台数（k=1、2、3）。用于分配给剩余工厂的可得到的设备台数。决策变量：xk=分配给第k个工厂的设备台数。状态转移方程：sk

+1=sk

-xk

为可分配给第k+1个工厂至第3

个工厂的设备台数。阶段指标函数：rk

(sk,xk

)表示为xk

台设备分配到第k个工厂所得的盈利值。具体如上表。最优指标函数：fk

(sk

)表示为sk

台设备分配给第k个工厂至第3个工厂时所得到的最大盈利值。因而可写出递推关系式为§3动态规划的应用(1)下面从最后一个阶段开始向前逆推计算。fk

(sk

)=max[rk(sk,xk)+fk+1(sk-xk)],k=1,2,3

0≤xk≤skf4(s4)=041

第三阶段:

由于第3阶段是最后的阶段，故有其中可取值为0,1,2,3,4,5。其数值计算见表10－6。

§3动态规划的应用(1)42表10－6

0

1

2

3

4

5

0

0－－－－－001－4－－－－412－－6－－－623－－－11－－1134－－－－12－1245－－－－12

12124或5§3动态规划的应用(1)43其中表示取3子过程上最优指标值时的决策，例如在表10-6中可知当=4时，有有此时，即当时，此时取（把4台设备分配给第3厂）是最优决策，此时阶段指标值（盈利）为12，最优3子过程最优指标值也为12。第二阶段：

当把台设备分配给第2工厂和第3工厂时，则对每个值，有一种最优分配方案，使最大盈利即最优2子过程最优指标函数值为

§3动态规划的应用(1)44因为上式也可写成其数值计算如表10－7所示。

表10－7

0

1

2

3

4

5

0－－－－－0010＋4

－－－－5120＋6

5＋4－－－10230＋11

5＋6

11＋0－－14240＋12

11＋4

11＋0－161,250＋12

5＋12

11＋6

11＋4

11＋0

212§3动态规划的应用(1)45其中在的这一行里，当时，这里从表10－5中可知，把1台设备交给乙厂所得盈利数即可，知，这里从表10－6查即可知=11。同样可知当时，可知

;当时，；当时，；当时，

；由于，不可能分2厂5台设备，故时，栏空着不填。从这些数值中取得最大即得，即有=16。在此行中我们在取最大值的上面加一横以示区别，也可知这时的最优决策为1或2。§3动态规划的应用(1)46

第一阶段：把台设备分配给第1，第2，第3厂时，最大盈利为其中可取值0,1,2,3,4,5.数值计算见表10－8

表10-8

然后按计算表格的顺序推算，可知最优分配方案有两个：

1.由于，根据，查表10－7可知，再由，求得。即分配给甲厂0台，乙厂2台，丙厂3台。

2.由于，根据，查表10－7可

0

1

2

3

4

55

3＋169+1012+513+0210,2§3动态规划的应用(1)47知，再由,求得，即分配给甲厂2台，乙厂2台，丙厂1台。这两种分配方案都能得到最高的总盈利21万元。

§3动态规划的应用(1)小结：第一步，建立动态规划模型划分阶段，设决策变量，设状态变量，确定决策变量的取值范围，写状态转移方程，写阶段指标函数，写递推（基本）方程。第二步，求解动态规划模型从后往前逐段累计求解48现有资金4万元，拟分给A、B、C三个项目，每项目获得不同的资金后可能创造的利润如下表所示，问应如何分配这4万元资金，使三个项目创造的总利润最大？资金（万元）ABC0123403810120581111046111449现有某种设备4台，拟分给甲、乙、丙三个工厂，个工厂获得此设备后可能创造的利润如下表所示，问应如何分配这4台设备，使所创造的总利润最大？设备台数甲乙丙0123403791205101111046111250二、背包问题设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设xi为第i种物品装入背包的件数（i=1,2,…,n），背包中物品的总价值为z，则

Maxz=c1x1+c2x2+…+cnxns.t.w1x1+w2x2+…+wnxn≤Wx1,x2,…,xn0

且为整数。§3动态规划的应用(1)51下面用动态规划逆序解法求解它。设阶段变量k：第k次装载第k种物品（k=1,2,…,n）状态变量sk：第k次装载时背包还可以装载的重量；决策变量uk

=xk：第k次装载第k种物品的件数；决策允许集合：Dk(sk)={xk

|0

xksk/wk，xk为整数}；状态转移方程：sk+1=sk

wkxk；阶段指标：vk

=ckxk；最优过程指标函数fk(sk)：第k到n阶段容许装入物品的最大使用价值；递推方程： fk(sk)=max{ckxk+fk+1(sk+1)}=max{ckxk+fk+1(sk

wkxk)}；

xDk(sk)终端条件：fn+1(sn+1)=0。§3动态规划的应用(1)52

例3.某咨询公司有10个工作日可以去处理四种类型的咨询项目，每种类型的咨询项目中待处理的客户数量、处理每个客户所需工作日数以及所获得的利润如表10－9所示。显然该公司在10天内不能处理完所有的客户，它可以自己挑选一些客户，其余的请其他咨询公司去做，应如何选择客户使得在这10个工作日中获利最大？表10－9

咨询项目类型待处理客户数处理每个客户所需工作日数处理每个客户所获利润1234

4

3

2

2

1

3

4

7

2

8

11

20§3动态规划的应用(1)53

解：用动态规划来求解此题。我们把此问题分成四个阶段，第一阶段我们决策将处理多少个第一种咨询项目类型中的客户，第二阶段决策将处理多少个第二种咨询项目类型中的客户，第三阶段、第四阶段我们也将作出类似的决策。我们设＝分配给第k种咨询项目到第四种咨询项目的所有客户的总工作日（第k阶段的状态变量）。

=在第k种咨询项目中处理客户的数量（第k阶段的决策变量）。已知＝10并有

§3动态规划的应用(1)54

并从与的定义可知从第四阶段开始计算：显然将个工作日尽可能分配给第四类咨询项目，即时，第四阶段的指标值为最大，其中，表示取不大于的最大整数，符号为取整符号，故有由于第四阶段是最后的阶段，故有§3动态规划的应用(1)55

因为至多为10，其数值计算见表10－10。

表10－10

0

1

0

－

0

0

1－

0

0

2－

0

0

3－

0

0

4－

0

0

5

－

0

0

6－

0

0

7

0

20

1

8

0

20

1

9

0

20

1

10

0

1

1§3动态规划的应用(1)56

第三阶段：当把个工作日分配给第四类和第三类咨询项目时，则对每个值，都有一种最优分配方案，使其最大盈利即最优3子过程最优指标函数值为

因为因为至多为10，所以的取值可为0,1,2。其数值计算见表10－11。§3动态规划的应用(1)57

表10－11

0120－－

0

0

1－－

0

0

2－－

0

0

3－－

0

0

4

0＋0－

11

1

5

0＋0－

11

1

6

0＋0－

11

1

7

11+0－

20

0

8

0＋20

11+0

22

2

9

0＋20

11+0

22

2

10

0＋20

11+0

22

2§3动态规划的应用(1)58

第二阶段：同样以每个值都有一种最优分配方案，使其最大盈利即最优2子过程最优指标函数值为：因为，故有因为至多为10，所以的取值为0,1,2,3。其数值计算见表10－12。§3动态规划的应用(1)59§3动态规划的应用(1)

表10-1260

第一阶段：我们已知，又因为，同样有

因为,故可取值为0,1,2,…,10。其数值计算见表10－13。表10－13§3动态规划的应用(1)

61从表10－13可知，从而得＝10－0＝10，在表10－12的的这一行可知，由，查表10－11的的这一行可知，最后由，查表10-10的的这一行得，综上所述得最优解为：此时最大盈利为28。现在我们不妨假设该咨询公司的工作计划有所改变，只有8个工作日来处理这四类咨询项目，那么该咨询公司如何选择客户使得获利最大呢？我们不必从头开始重做这个问题，而只要在第一阶段上把改成8，重新计算就可得到结果，如表10－14所示，这是动态规划的一个好处。

§3动态规划的应用(1)

62

表10－14

如上一样可从表10－14,10－12,10－11,10－10得到两组最优解如下：

它们的最优解（即最大盈利）都为22。一旦咨询的工作日不是减少而是增加，那么我们不仅要重新计算第一阶段，而且要在第二、第三、第四阶段的计算表上补上增加的工作日的新的信息，也可得到新的结果。§3动态规划的应用(1)

63

实际上，背包问题我们也可以用整数规划来求解，如果背包携带物品重量的限制为W公斤，这N种物品中第i种物品的重量为，价值为，第i种物品的总数量的，我们可以设表示携带第i种物品的数量，则其数学模型为：

S.T.

且为整数。

我们不妨用此模型去求解例3，也一定得出同样的结果。§3动态规划的应用(1)

64三、生产与存贮问题例4.某公司为主要电力公司生产大型变压器，由于电力采取预订方式购买，所以该公司可以预测未来几个月的需求量。为确保需求，该公司为新的一年前四个月制定一项生产计划，这四个月的需求如表10－15所示。生产成本随着生产数量而变化。调试费为4，除了调度费用外，每月生产的头两台各花费为2，后两台花费为1。最大生产能力每月为4台，生产成本如表10－16所示。

表10－15

§3动态规划的应用(1)

65

表10－16

每台变压器在仓库中由这个月存到下个月的储存费为1，仓库的最大储存能力为3台，另外，知道在1月1日时仓库里存有一台变压器，要求在4月30日仓库的库存量为零。试问该公司应如何制定生产计划，使得四个月的生产成本和储存总费用最少？解：我们按月份来划分阶段，第i个月为第i阶段：（i=1,2,3,4).

设为第k阶段期初库存量；k=1,2,3,4

§3动态规划的应用(1)

66

为第k阶段生产量；k=1,2,3,4为第k阶段需求量；k=1,2,3,4，这已在表10-15中告诉我们。因为下个月的库存量等于上个月的库存量加上上个月的产量减去上个月的需求量，我们就得到了如下状态转移方程：因为，故有

因为，故有

§3动态规划的应用(1)

67

由于必须要满足需求，则有

通过移项得到

另一方面，第k阶段的生产量必不大于同期的生产能力（4台），也不大于第k阶段至第四阶段的需求之和与第k阶段期初库存量之差，否则第k阶段的生产量就要超过从第k阶段至第四阶段的总需求，故有

以下我们从第四阶段开始计算：从以上的状态转移方程可知这样就有

§3动态规划的应用(1)

68

这里的阶段指标可以分成两部分，即生产成本与储存费，即为由于第四阶段末要求库存为零，即有，这样可得对于每个的可行值，的值列于表10－17。

表10－17§3动态规划的应用(1)

69

表中当时，可知第四阶段要生产台，从表10－16可知总成本为9，同样可以算出当为1,2,3时的情况，结果已列于表10－17中。第三阶段：此时有：因为

以及

所以有例如，当第三阶段初库存量时，生产量为2时，则所以生产成本为8，第三阶段末库存为2时，储存费为，而§3动态规划的应用(1)

70查10－17表可知，这样可知，填入表10－18中的栏内，其他结果如表10－18所示：表10－18

第二阶段：因为所以有§3动态规划的应用(1)

71计算结果如表10－19所示。

表10－19

§3动态规划的应用(1)

72

第一阶段：因为故有

计算结果见表10－20。

表10－20§3动态规划的应用(1)

73

利用递推关系可以从表10－20，表10－19，表10－18和表10－17得到两组最优解：这时有最低总成本29。§3动态规划的应用(1)

74§3动态规划的应用(1)

四、系统可靠性问题

例5.某科研项目组由三个小组用不同的手段分别研究，它们失败的概率各为0.40，0.60，0.80。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表：问如何分派科学家才能使三个小组都失败的概率（即科研项目最终失败的概率）最小？高级科学家小组12300.400.600.8010.200.400.5020.150.200.3075§3动态规划的应用(1)

解：用逆序算法。设阶段：每个研究小组为一个阶段，且阶段123小组12376§3动态规划的应用(1)

计算当n=3时，当n=2时，s3f3*(s3)x3*00．80010．50120．302

x2s2f2(s2,x2)=P2(x2)·f3*(s2-x2)f2*(s2)x2*01200．480．48010．300．320．30020．180．200．160．16277§3动态规划的应用(1)

当n=1时，最优解为x1*=1，x2*=0，x3*=1；科研项目最终失败的概率为0.060。x1s1f1(s1,x1)=P1(x1)·f2*(s1-x1)f2*(s2)x2*01220．0640．0600．0720．060178§4动态规划的应用(2)*一、连续确定性动态规划

对于状态变量和决策变量只取连续值，过程的演变方式为确定性时，这种动态规划问题就称为连续确定性动态规划问题。79§4动态规划的应用(2)*机器负荷分配问题例1一种机器能在高低两种不同的负荷状态下工作。设机器在高负荷下生产时，产量函数为P1=8u1，其中u1为在高负荷状态下生产的机器数目，年完好率为a=0.7，即到年底有70％的机器保持完好。在低负荷下生产时，产量函数为P2=5u2，其中u2为在低负荷状态下生产的机器数目，年完好率为b=0.9。设开始生产时共有1000台完好的机器，请问每年应该如何把完好机器分配给高、低两种负荷下生产，才能使得5年内生产的产品总产量最高。80§4动态规划的应用(2)*解建立动态规划模型：分为5个阶段，每个阶段为1年。设状态变量sk表示在第k阶段初拥有的完好机器数目；k=1,2,3,4,5。决策变量xk表示第k阶段中分配给高负荷状态下生产的机器数目；k=1,2,3,4,5。显然sk-xk为分配给低负荷状态下生产的机器数目。状态转移方程为sk+1=0.7xk+0.9(sk-xk)

阶段指标rk(sk,xk)=8xk+5(sk-xk)

最优指标函数，其中k=1,2,3,4,5。

f6(s6)=0。81§4动态规划的应用(2)*第5阶段：因为f5(s5)是x5的线性单调增函数，故有x5*=s5，于是有f5(s5)=8s5。第4阶段：

82§4动态规划的应用(2)*

同样的，f4(s4)是x4的线性单调增函数，有x4*=s4，f4(s4)=13.6s4。对前几个阶段依次类推，可得

f3(s3)=17.5s3，

f2(s2)=20.75s2，

f1(s1)=23.72s1。因为期初共有完好机器1000台，故s1=1000。有f1(s1)=23.72s1＝23720，即5年最大的产量为23720台。得最优解为，，，。这意味着前两年应把年初完好机器完全投入低负荷生产，后三年应把年初完好机器完全投入高负荷生产。83§4动态规划的应用(2)*

下一步工作是确定每年初的状态，按照从前向后的顺序依次计算出每年年初完好的机器数目。已知s1=1000,根据状态转移方程，有:84§4动态规划的应用(2)*上面所讨论的最优策略过程，初始端状态s1=1000台是固定的，终点状态s6没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优策略。如果终点附加一定的条件，则问题就称为“终端固定问题”。例如，规定在第5年度结束时仍要保持500台机器完好（而不是278台），应如何安排生产才能使得总产量最大？下面来分析：根据终点条件有

可得85§4动态规划的应用(2)*显然，由于固定了终点的状态，x5的取值受到了约束。因此有类似的，

容易解得，f4(s4)=21.7s4-7500。

86§4动态规划的应用(2)*

依次类推，得

f3(s3)=24.5s3-7500f2(s2)=27.1s2-7500f1(s1)=29.4s1-7500

再采用顺序方法递推计算各年的状态，有

s1=1000，

87§4动态规划的应用(2)*

可见，为了使终点完好的机器数量增加到500台，需要安排前四年中全部完好机器都要投入低负荷生产，且在第5年，也只能全部投入高负荷。相应的最优指标为

f1(s1)=29.4s1-7500＝21900。

可以看到，因为增加了附加条件，总产量f1(s1)要比终点自由情况下的产量要低。88二、离散随机性动态规划随机型的动态规划是指状态的转移律是不确定的，即对给定的状态和决策，下一阶段的到达状态是具有确定概率分布的随机变量，这个概率分布由本阶段的状态和决策完全确定。随机型动态规划的基本结构如下图：

§4动态规划的应用(2)*

sk状态

xk决策概率k阶段的收益p1p2pN….k+1阶段的状态sk+1c1c2cN

1

2N89§4动态规划的应用(2)*图中N表示第k+1阶段可能的状态数，p1、p2、…pN为给定状态sk和决策xk的前提下，可能达到下一个状态的概率。ci为从k阶段状态sk转移到k+1阶段状态为i时的指标函数值。在随机性的动态规划问题中，由于下一阶段到达的状态和阶段的效益值不确定，只能根据各阶段的期望效益值进行优化。90离散随机性动态规划例2