1第四章动态规划

2§4-1多阶段决策问题§4-2动态规划的基本概念与模型构造

3§4-1多阶段决策问题通过以下几个典型实例进行分析来说明用动态规划解决的多阶段决策问题的些特点：例4-1(最短路线问题)由若干城市及其单向道路组成的交通图如图4-1所示,图中数字表示城市之间的距离,问:应如何选择行进路线,才能使A到G的路程最短?

4§4-1多阶段决策问题例4-2(负荷分配问题)已知机器在高、低两种负荷下的年度生产情况如表4-1所示其中,机器年完好率指年末完好机器台数与年初完好机器台数之比值。常数a、b、c、d满足0ab1,0dc,问:应如何在年初决定完好机器在两种负荷下工作的台数,才能使n年中总产量最多?负荷情况完好机器台数产品年产量机器年完好率高w1s1=cw1a低w2s2=dw2b表4-1

5§4-1多阶段决策问题例4-3(投资问题)现有资金7亿元，可在三个项目上投资：项目A的投资额不得超过3亿元；项目B与项目C的投资额合计不得低于2亿元,但不得超过4亿元,或者可以不投资。投资方式与预期收益如表4-2所示(其中,“-”表示不允许发生的情况,单位:亿元)。问:应如何分配在三个项目上的投资额，才能使总收益最大?表4-201234A05810-B0-3911C0-71113

6§4-2动态规划的基本概念与模型构造一、动态规划的基本概念（一）阶段阶段是指按问题的时间演变或空间特征对过程进行划分的结果,从第一个(初始)阶段到最后一个(终结)阶段,不断相连,就构成动态规划的全过程描写阶段序数的变量称为阶段变量,记作.k=1,2,…,n分别表示第1,第2,…，第n阶段

7§4-2动态规划的基本概念与模型构造全过程中从第k阶段到第n阶段的那部分称为后部k子过程,常简称为k子过程.当k=1时,k子过程就是全过程全过程中从第1阶段到第k阶段的那部分称为前部k子过程,当k=n时,前部k子过程就是全过程例4-1中共有6个阶段:k=1,2,…,6：例如,B1→C1、C2、C3及B2→C2、C3、C4，都处于k=2的阶段例4-2中共有n个阶段：k=1,2，…，n。例如，k=3就表示第3年度。

8§4-2动态规划的基本概念与模型构造（二）状态状态是指阶段开始的各种可能情况,一种情况就是一个状态,动态规划要求过程的发展只受当前阶段特定状态的影响(称为无后效性),所以在确定状态时,必须注意到这一点.描写状态特征的变量称为状态变量,反映第k阶段多种状态的状态变量记作sk,由于阶段开始时往往有多种状态,所以,sk相应有多个取值,其全体组成第k阶段的状态集合,记作Sk。Sk可以是有限集,也可以是无限集

9§4-2动态规划的基本概念与模型构造例4-1中,状态变量xk为第k阶段的行进起始城市,借用阶段数与字母代号下标,将表示城市的符号数量化,则各阶段的状态变量如表4-3所示.表4-3ksk1A112B1,B221,223C1,C2,C3,C431,32,33,344D1,D2,D341,42,435E1,E2,E351,52,536F1,F261,627G71

10§4-2动态规划的基本概念与模型构造例4-2中,状态变量s为第飞年初完好机器台数,按理,机器台数应取离散的非负整数值,但实际情形却不尽然例如,有两台在年初完好的机器,一台机器正常工作时间只有6个月,另一台全年正常工作,这两台机器在当年的生产情况显然大不一样,为能反映出这种区别,以尽量符合客观实际,自然认为只能工作半年的那台机器应该算作0.5台。因此，在构造模型时,把s取作连续的非负实数.

11§4-2动态规划的基本概念与模型构造（三)决策决策是指依据当前阶段的特定状态,为达到下阶段某一状态所作出的选择方案描写决策方案的变量称为决策变量,依据第k阶段已给状态s来作出决策的决策变量记作uk(sk),显见,决策变量依赖于状态变量依据状态变量sk所允许作出的决策方案的全体,也即决策变量uk(sk)取值的全体组成第k阶段的决策集合,记作Dk(sk)或{uk(sk)},分别将uk(sk)与Dk(sk)简记为uk与Dk

12§4-2动态规划的基本概念与模型构造例4-1中,决策变量uk为第k阶段的行进终结城市,各阶段的决策变量如表4-4所示由表4-4可得出任一Dk(sk),将表4-3右列各数对应代人表4-4中,就可得出Sk与uk数量化后的形式.表4-4k123xkAB1B2C1C2C3C4ukB1,B2C1,C2,C3C2,C3,C4D1,D2D1,D2D2,D3D2,D3456D1D2D3E1E2E3F1F2E1,E2E2,E3E2,E3F1,F2F1,F2F1,F2GG

13§4-