网上找的一些运筹学动态

1、1.多阶段的决策问题动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法。所谓多阶段决策过程是指这样一类决策过程：它可以分为若干个互相联系的阶段，在每一阶段分别对应着一组可以选取的决策，在每一阶段都需要作出决策，从而使整个过程达到最好的效果。当各个阶段决策确定后，就了一个决策序列，称为一个策略。下面是几个多阶段决策过程的例子。【例 1】最短路线问题。设有一个旅行者从图中的 A 点出发，途中要经过B、C、D 等处，最后到达终点 E。从 A 到 E 有很多条路线可以选择，各点之间的距离如图中所示，问该旅行者应选择哪一条路线，使从A 到达E 的总的路程为最短。1【例 2】设有某种机

2、器设备，用于完成两类工作 A 和 B。若 k 年初完好机器的数量为 x k，若以数量 u k用于 A，余下的（x ku k）用于工作B，则该年的预期收入为 g（u k）+h（x ku k）。这里 g（u k）和 h（x ku k）是已知函数，且 g（0）=h（0）=0。又机器设备在使用中会有损坏，设机器用于工作 A 时，一年后能继续使用的完好机器数占年初投入量的 a%；若用于 B 项工作时，一年后能继续使用的完好机器数占年初投入量的 b%，即下一年初能继续用于完成这两项工作的设备数为 x k+1= a uk+b（x ku k）。设第一年初完好的机器总数为 x 0，问在连续五年内每年应如何分配用

3、于 A、B 两项工作的机器数，使五年的总收益为最大。【例 3】将一个数 c（c0）分成 n 个部分 c1，c2， cn 之和，且 ci0ncii1（i=1，n ），问如何分割使其乘积为最大。2.最优化原理与动态规划的数学模型2-1 动态规划问题的解题思路用动态规划方法解题的基本思路，是将一个 n 阶段的决策问题转化为依次求解 n 个具有递推关系的单阶段的决策问题，从而简化计算过程。在例 1 中，这种转化的实现是从终点 E 出发一步步进行反推，这种算法称为逆序算法。具体步骤如下：2（1）考虑一个阶段的最优选择。f（D1）=3表示某阶段初从 D1 出发到终点的最短距离f（D2）=4表示某阶段初从

4、D2 出发到终点的最短距离（2）联合考虑两个阶段的最优选择。从C1 出发到 E 的最短路程为：min d (C1 , D1 ) 1 3 ) f (D1 min 4d (C , D ) 4 4f (D2 )12即从C1 到 E 的最短路线为 C1D1E，并记 f（C1）=4。如果旅行者从 C2 出发，他的最优选择为：min d (C2 , D1 ) 6 3) f (D1 min 7d (C , D ) f ( D)3 4222 即从C2 到 E 的最短路线为 C2D2E，并记 f（C2）=7。如果旅行者从 C3 出发，他的最优选择为：min d (C3 , D1 ) ) 3 3f (D1 min

5、 6d (C , D ) f (D)3 4322 即从C3 到 E 的最短路线为 C3D1E，并记 f（C3）=6。3（3）再考虑三个阶段的最优选择。从 B1 出发，最优选择为：d (B1 , C1 ) f (C1 ) 7 4min d (B , C ) f (C ) min 5 7 11122d (B , C ) f (C) 6 6133即从 B1 到 E 的最短路线为 B1C1D1E，并记 f（B1）=11。如果旅行者从 B2 点出发，到 E 点的最优选择为：d (B2 ,C1 ) f (C1 ) 3 4min d (B ,Cf (C) min 2 7 7) 222d (B ,C ) f

6、(C ) 4 6233即从 B2 到 E 的最短路线为 B2C1D1E，并记 f（B2）=7。如果旅行者从 B3 点出发，到 E 点的最优选择为：d (B3 , C1 ) f (C1 ) 5 4min d (B , C ) f (C ) min 1 7 8322d (B , C ) f (C) 5 6333即从 B3 到 E 的最短路线为 B2C2D2E，并记 f（B3）=8。（4）四个阶段联合考虑时，从 A 点到 E 点的最优选择是d ( A, B1 ) f (B1 ) 2 11min d ( A, B ) f ( B ) min 5 7 1122d ( A, B ) f (B) 3 8 3

7、3即从 A 到 E 的最短路线为 AB3C2D2E，距离长度为 1l。4从上面解题的过程看出，将一个多阶段的决策问题转化为依次求解多个单阶段的决策问题时，一个重要特征是将前面的解传递并纳入下一个阶段一并考虑，即做到求解的各阶段间具有递推性。2-2 动态规划的基本概念1. 阶段（stage）是指一个问题需要作出决策的步数。通常用 k 来表示问题包含的阶段数，称为阶段变量。k 的方法有两种：（1）顺序为 1，以后随进程逐渐增大；法，即初始阶段（2）逆序法。令最后一个阶段为 1，往前推时逐渐增大。2.状态（se）各阶段的状态通常用状态变量 x 来描述，它既反映前面各阶段决策的结局，又是本阶段作出决策

8、的出发点和依据。第 k 阶段的状态变量 x k 应包含该阶段之前决策过程的全部信息，做到从该阶段后做出的决策同这之前的状态和决策相互独立。例 1 中对旅行者每个阶段所处位置只需用一个状态变量来描述，但有些问题中各阶段的状态则要用多个变量或向量的形式描述。向量中所含变量的个数称为动态规划问题的维数。3. 决策（deci）是指某阶段初从给定的状态出发，决策者在的若干种不同方案中做出的选择。决策变量 u k（x k）表示第 k 阶段状态为 x k 时对方案的选择。决策变量的取值要受到一定范围的限制，用 D k（xk）表示 k5阶段状态为 x k 时决策允许的取值范围，称允许决策集合：u k（x k）

9、D k（x k）例 1 中从 B1 点出发的允许决策集合 D（B1）=C1，C2，C3，如果选取下一个到达点为 C2，则决策变量 u2（B1）的取值为 C2，或直接写为 u2（B1）=C2。4. 策略（Policy）策略（subpolicy）动态规划问题各阶段决策组成的序列总体称作一个策略。含 n 个阶段的动态规划问题的策略可写为：p 1，n= u 1（x 1），u 2（x 2） ， ，un（xn）把从某一阶段开始到过程最终的决策序列称为问题的子过程策略或子策略。从 k 阶段起的子策略可写为p k，n= u k（x k），u k+1（x k+1）， ，un（xn）5. 状态转移律 从 x k

10、的某一状态值出发，当决策变量 u k（x k）的取值决定后，下一阶段状态变量 x的取值也就随之确定。这种从上阶段的某一状k+1态值到下阶段某一状态值的转移的规律称为状态转移律。下一阶段状态 x k+1 的取值是上阶段状态变量 x k 和上阶段决策变量 u k（x k）的函数，记为：x k+1 = T（x k ，u k（x k）或：x k+1 = T（x k ，u k）状态转移律也称状态转移方程。6顺序解法时：x k = T（x k+1，u k（x k）或：x k = T（x k+1，u k）6. 指标函数衡量实现过程优劣的一种数量指标，分为阶段指标函数和过程的指标函数。阶段的指标函数是对应某一

11、阶段状态和从该状态出发的一个阶段的决策的某种效益度量，用 v k（x k，u k）表示。过程的指标函数是指从状态 x k（k=1，n）出发至过程最终，当采取某策略时，所得到的效益值。这个值既与 x k 的状态值有关，又与x k 以后所选取的策略有关，它是两者的函数值，记作V kn（x k，u k，x k+1，u k+1， ，xn），对于要动态规划模型的指标函数，应具有可分离性，并满足递推关系，即 V kV k应可表示为 x k 、u k、V k+1的函数 ：n， n，n（x k，u k，x k+1，u k+1， ，x n），= k （x k，u k，V k+1 ， n（x k+1， ，x n）

12、常见的指标函数的形式是：（1）过程和它的任一子过程的指标是它所包含的各阶段的指标的和：n vi (xi ,ui )i kVk ,n则V k， n（x k，u k，x k+1， ，xn）= v k（x k，u k）+V k+1n（x k+1， ，x n），7（2）过程和它的任一子过程的指标是它所包含的各阶段的指标的乘积：n vi ( xi ,ui )i kVk , n则V k， n（x k，u k，x k+1，xn）= v k（x k，u k）V k+1n（x k+1，xn），当 x k 的值确定后，指标函数的值就只同 k 阶段起的子策略有关。过程指标函数的最优值，称为最优指标函数。它是指从第

13、k 阶段的状态 x k开始到第 n 阶段终止状态，采取最优策略所得到的指标函数值。对应于从状态x k 出发的最优子策略，过程指标函数值记作 f k（x k），于是有f k（x k）= opt V k，n式中 opt 代表最优化，根据效益值的具体含义可以是求最大（max）或求最小（min）。上述基本概念在多阶段决策过程中的关系可通过下图来表示。82-3 最优化原理与动态规划的数学模型从下述所有可能的组合中选取最优：将本阶段决策的指标效益值加上从下阶段开始采取最优策略时的指标效益值。50 年代，的利（ R.Bellman）等人根据研究一类多阶段决策问题，提出了最优性原理，作为动态规划的理论基础，该

14、原理内容如为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的诸决策必最优策略。根据这个原理可写出计算动态规划问题的递推关系式，称为动态规划的基本方程：n vi (xi ,ui ) 时，有 f k (xk ) i k（1）opt vk ( xk ,uk ) uk Dk ( xk )Vk ,nf k 1 ( xk 1 )n vi ( xi ,u i ) 时，有 f k (xk ) i kopt vk (xk , uk ) f k 1 ( xk 1 ) （2）u k Dk ( xk )Vk ,n边界条件f n+1（x n+1）的值动态规划的最优性定理：设

15、阶段数为 n 的多阶段决策过程，其阶段为k=1， n ，允许策略p* (u * , , u ) 是最优策略的充要条件是对任一个 k*（11,n1nkn）和 x 1 S 1 有(x , p) opt V(x , pV( x , p* ) opt V)1,k 111, k 11, n11, nk , nkk , np1,n ( p1,k 1 , pk ,n ) ， xk式中 Tk 1 ( xk 1 , uk 1) ，它是由给定的初始状态 x策略1p1,k 1 所确定的 k 阶段状态。9推论：若允许策略p (u * , , u ) 是最优策略，则对任意的 k*（1kn），1,n1n( x* , u*

16、 ) 为起点的 k 到 n 的子策略来它的子策略 p* (u* , , u* ) 对于以x* Tkk 1k 1k 1k ,nkn说，必是最优策略。（k 段状态x 是由 x和p*所确定的）*1k1,k 1为构造和求解动态规划的数学模型，需要明确模型中有关阶段的划分、状态变量、决策变量、允许决策集合和状态转移方程等，并注意下述各点。（1）状态变量状态变量首先应描述反映研究过程的演变特征，其次它应包含到达这个状态前的足够信息，并具有无后效性。即到达这个状态前的过程的决策将不影响到该状态以后的决策。状态变量还应具有可知性，即规定的状态变量的值可通过直接或间接的方法测知。状态变量可以是离散的，也可以是连

17、续的。（2）决策变量决策变量可以是的向量，它的取值可能离散，也可能连续。（3）状态转移律 x k+1=T（x k，u k）性的多阶段决策过程。确定性的多阶段决策过程和随机（4）指标函数指标函数必须具有递推性，即能写成如下的关系式： vk (xk , uk ) Vk 1,n或 vk (xk , uk ) Vk 1,nVk ,nVk ,n2-4 逆序解法与顺序解法动态规划问题的求解有两种基本方法：逆序解法与顺序解法。10顺序解法的思路和模型：u 1u 2u nx 1x 2x 3x nx n+112n例如在资源分配问题中，设阶段的k=1， n 同逆序解法决策变量 u k ： 表示分配到第 k 阶段的

18、资源数量状态变量 x k： 表示从第 1 到第（k1）阶段的可使用的资源数量则第（k1）阶段的状态 x k1 是第 k 阶段的状态 x k 和第（k1）阶段决策变量 u k1 的函数：x k1 = x ku k1故顺序解法中状态转移律可表为：x k1 = T（x k，u k1）第（k1）阶段的指标函数可表为：v k1（x k，u k1）用 f k1（x k）表示第 k 阶段初状态为 x k，从第 1 到第（k1）阶段采取最优子策略时，前（k1）个阶段的最优指标函数值，则由动态规划的最优化原理，采用顺序解法时，动态规划的数学模型可表示如下：（1） 当各阶段指标函数为求和关系时，有 f k (xk

19、 1 ) optvk ( xk 1 ,uk ) f k1 (xk )uk Dk (xk1 ) f0 ( x1) 011（2）当各阶段指标函数为求积关系时，有 f k (xk 1 ) optvk (xk 1 ,uk ) f k1 ( xk )uk Dk ( xk1 ) f0 ( x1 ) 12-5 动态规划模型的分类按过程演变的特征，动态规划模型划分为确定性的动态规划模型和随机性的动态规划模型两大类。根据状态变量的取值是离散还是连续，它们又可区分为连续和离散两类。离散确定性的动态规划模型连续确定性的动态规划模型离散随机性的动态规划模型连续随机性的动态规划模型3.离散确定性动态规划模型的求解【例

20、4】部门共有 12 支巡逻队，负责 4 个要害部位 A、B、C、某一D 的巡逻。对每个部位可分别派出 24 支巡逻队，并且由于派出巡逻队数的不同，各部位预期在一段时期内可能造成的损失有差别。问该部门应往各部位分别派多少支巡逻队，使总的预期损失为最小。12部位巡逻队数ABCD2352231410312125【解】把 12 支巡逻队往 4 个部位派遣看成依次分四个阶段（用 k 表示，k=1，2，3，4）。u 1u 2u 3u 4（1）逆序解法状态变量 x k 表示第 k 阶段初拥有的可派遣的巡逻队数，决策变量 u k 表示第 k 阶段派出的巡逻队数，第 k 阶段允许的决策集合为：（k = 1，2，

21、3，4）（k = 1，2，3，4）Dk (xk ) uk | 2 uk 4状态转移律为： xk 1 xk uk假设用p k（x k）表示 k 阶段派出的巡逻队数为 u k 时，该阶段的部位的预期损44失值，则指标函数可写为：Vk ,4 pi (ui ) pk (uk ) pi (ui ) pk (uk ) Vk 1,4i ki k 1假设用 f k (xk )表示从 k 阶段（状态为 x k ）开始，到过程结束，当采用最优子f k (xk ) min pk (uk ) fk 1 (xk 1 )策略时的预期损失值，则uk Dk ( xk ) 先考虑给 D 部位派巡逻队，即 k = 4，则：f 4

22、 ( x4 ) min p4 (u4 ) f5 (x5 )u4D4 ( x4 )因问题中只有 4 个要害部位，故第 5 阶段初拥有的未派出的巡逻队数对前 4 个部位的预期损失不再起影响，故边界条件 f 5 ( x5 ) =0 ，因此有 f 4 (x4 ) min p4 (u4 )u4D4 ( x4 )D 4（x 4）= 2，3，4，x 4 的可能值为 2x 46：13x 11x 22x 33x 44x 5 再联合考虑对 C、D 两个部位派巡逻队，即 k = 3 ，f3 ( x3 ) min p3 (u3 ) f 4 ( x4 )u3D3 ( x3 )D 3（x 3）= 2，3，4，x 3 的可

23、能值为 4x 38： 下面考虑对 B、C、D 三个部位派巡逻队，即 k = 2，f 2 (x2 ) min p2 (u2 ) f3 (x3 )u2D2 ( x2 )D 2（x 2）= 2，3，4，x 2 的可能值为 8x210：14 最后考虑对 A、B、C、D 四个部位派巡逻队，即 k = 1，f1 (x1) min p1 (u1 ) f2 (x2 )u1D1( x1 )D 1（x 1）= 2，3，4，x 1 = 12：u1* = 4，x 2 = 12 4 = 8 ，u2* = 2，x3 = 8 2 = 6 ，u3* = 2，x4 = 6 2 = 4 ，u4* = 4。部门的派巡逻队数的最优策

24、略为：A 部位 4 支，B 部位 2 支，C 部该位 2 支，D 部位 4 支，总预期损失为 97。（2）顺序解法u 1u 2u 3u 4同逆序解法，状态变量 xk 表示可用于前（k1）个部位的巡逻队阶段数，故有 x5=12 ；k 阶段决策变量 u k ，允许决策集Dk (xk 1 ) uk | 2 uk 4 。可用于前（k1）个部位的巡逻队数 x k 等于可用于前 k 个部位的数字 x k+1减于第 k 阶段派出的巡逻队数，故状态转移律为：15x 1x 2x 3x 4x 51234xk xk 1 uk（k = 1，2，3，4）8x410， 4x38，2x26假设用 p k（x k）表示 k

25、阶段派出的巡逻队数为 u k 时，该阶段的部位的预kk 1期损失值，则指标函数可写为：V1,k pi (ui ) pk (uk ) pi (ui ) pk (uk ) V1,k 1i 1i1假设用 f k (xk 1 ) 表示从第 1 阶段开始，到第 k 阶段结束（状态为 x k+1 ），当采用最优子策略时的预期损失值，则f k (xk 1 ) f0 (x1) 0minpk (uk ) fk 1 ( xk )uk Dk ( xk1 )f1 ( x2 ) min p1 (u1 ) f0 (x1 ) min p1 (u1) 0 min p1 (u1 )，u1D 1( x2 )u1D 1( x2 )

26、u1D 1( x2 )D 1（x 2）= 2，3，4，2x26：f 2 ( x3 ) min p2 (u2 ) f1 ( x2 )，u2D 2( x3 )D 2（x 3）= 2，3，4，4x38：16f3 ( x4 ) min p3 (u3 ) f 2 ( x3)，u3D 3( x4 )D 3（x 4）= 2，3，4，8x4 10：f4 ( x5 ) min p4 (u4 ) f3 ( x4 )，u4D 4( x5 )D 4（x 5）= 2，3，4，x5 = 12 ：x5 = 12，u4* = 4 ，x4 = 8，u3* = 2，x3 = 6，u2* = 2，x2 = 4，u1* = 4，预期

27、总损失 97。174.离散随机性动态规划模型的求解随机性动态规划是指状态的转移律是不确定的，即对给定的状态和决策，下一阶段的到达状态是具有确定概率分布的随量，这个概率分布由本阶段的状态和决策完全确定。随机性动态规划的基本结构：图中 N 表示第（k+1）阶段可能的状态数，p 1、p 2、p N 为给定状态 x k和决策 u k 的情况下，下一个可能到达的状态的概率，c i 为从 k 阶段状态 x k 转移到（k+1）阶段状态为 i 时的指标函数值。随机性的动态规划问题中，当指标函数值为各阶段效益和的情况下，基本方程应写为：f k (xk ) optEvk ( xk , uk ) u k Dk (

28、 xk )f k 1 ( xk 1 )【例 6】某公司承担一种新产品试制任务，合同要求三个月内交出一台合格的样品，否则将负担 1500 元的赔偿费。据有经验的技术估计，试制时每投产一台合格的概率为 1/3，投产一批的准备结束费用为 250 元，每台试制费用为 100 元。若投产一批后全部不合格，可再投一批试制，但每投一批的周期需一个月。要求确定每批投产多少台，使总的试制费用（包括可能发生的赔18偿损失）的期望值为最小。【解】（1）合同期为三个月，投产一批的周期为一个月，作为一个阶段。故可将整个合同期划分为三个阶段。状态变量 x k。假定尚没有一台合格品时 x k = 1，已得到一台以上合格品时

29、 x k = 0。则签订合同时有 x 1 = 1。决策变量 u k 为每个阶段的投产试制台数。允许决策集合D k（x k）= 1，2，N （当 x k = 1）D k（x k）= 0（当 x k = 0）（4）状态转移律为：（5）第 k 阶段的费用支出为 c（u k），有（6）设 f k（x k）为从状态 x k、决策 u k 出发的 k 阶段以后的最小期望费用。因有 f k（0）=0，故有当 k = 3 时，f 3（0）= 0 ，19f 4（1）的意义为第四个月初仍未得到一件合格产品，因按合同要求需赔偿 1500 元，故有 f 4（1）=1500。当k = 2时，f 2（0）= 0，k =

30、1当时，即该公司的最优决策为第一批投产3 台；如果无合格品，第二批再投产 3台；如果仍全部不合格，第 3 批投产 4 台。这样使总的期望研制费用（包括三批均不合格时的赔偿费）为最小，共计 796 元。205.动态规划应用举例1最短路径2资源分配问题所谓资源分配问题，就是将数量一定的一种或若干种资源（例如原材料、设备、劳力等）恰当地分配给若干个使用者，使目标函数为最优。例如：设有某种原料，总数量为 a，用于生产 n 种产品。若分配数量 x i 用于生产第 i 种产品，其收益为 g i（x i收入最大?）。问应如何分配，才能使生产 n 种产品的总此问题可写成静态规划问题：Max z g1 (x1

31、) gn (xn )x1 xn ai 1, , nx 0 i状态变量 s k决策变量 x k表示分配用于生产第 k 种产品至第 n 种产品的原料数量。表示分配生产第 k 种产品的原料数：s k+1 = s kx k状态转移方程允许决策集合：D k（s k）= x k |0 xs k k最优值函数 f k（s k） ： 表示以数量为s k的原料分配给第 k 种产品至第 n种产品所得的最大总收入，则动态规划的逆推关系式为：21 fk (sk ) max gk (xk ) xk )k n 1, ,1fk 1(sk0 xk skf (s ) max g (x )nnnnxn sn这种只将资源合理分配不

32、考虑回收，又称为资源平行分配问题。在资源分配问题中，还有一种要考虑资源回收利用，这里决策变量为连续值，称为资源连续分配问题。例如：设有数量为 s 1 的某种资源，可投入 A 和 B 两种生产。第一年若以数量 u 1投入生产 A，剩下的量s 1 u 1 就投入生产 B，则收入为 g（u 1）h（s 1u 1），其中 g（u 1）和 h（s 1u 1）为已知函数，且 g（0）h（0）0，这种资源在投入 A、B 生产后，年终还可回收再投入生产。设年回收率分别为 0a1 和 0b1，则在第一年生产后，回收的资源量合计为 s 2a u 1b（s 1u 1）。第二年再将资源数量 s 2 中的 u 2 和s

33、 2u 2 分别再投入 A、B 两种生产，到收入为 g（u 2）h（s 2u 2）。如此继续进行 n 年，应当如则第二年又何决定每年投入 A 生产的资源量 u 1、u 2、u n，才能使总的收入最大?此问题写成静态规划问题为：22【例】机器负荷分配问题某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为 g = 8 u 1，其中 u 1 为投入生产的机器数量，年完好率为 a = 0.7；在低负荷下生产的产量函数为 h = 5 y，其中 y 为投入生产的机器数量，年完好率为 b = 0.9 。假定开始生产时完好的机器数量 s 1= 1000 台，每年应如何安排机器在高、低负

34、荷下的生产，使在五年内生产的产品总产量最高？3背包问题有一个人带一个背包上山，其可携带物品重量的限度为 a 公斤。设有 N 种物品可供他选择装入背包中，这 N 重物品为 1、2、 N。已知第 i 种物品每件重量为 wi 公斤，在上山过程中的作用（价值）是携带数量 x i的函数 c i（x i ）。问此人应如何选择携带物品（各几件），使所起作用（总价值）最大？这就是著名的背包问题，类似有工厂里的下料问题，中的货物装载问题，人造内的物品装载问题等等。P168 【例 8】有一艘货船准备装载 N 种货物，已知第 k 种货物的重量为 w k，其价值为 v k。假如该货船的最大载重量为 W，要求确定每种货

35、物的装载件数，在不超过最大载重允许的条件下，使货船装运物资的总价值为最大。【解】若用 u k 表示第k 种货物的装载件数，则问题归结为求解下述整数规划问题Nmax z vkukk 123 N wkuk W k 1uk 0 , 且为整数为用动态规划方法求解，先将此问题转化成动态规划模型。将装载 N 种货物看作 N 个阶段，用 k（k=1，N ）来代表阶段。第 k 阶段的状态为可用于第 k、k+1、 N 阶段的装载重量，用 W k 表示。用 u k 表示第 k 阶段装载第 k 种物资的件数，则 u kW k /w j，W k /w j为 W k /w j 的最大整数部分。状态转移可表为 W k+1

36、 = W kw j u k。由此动态规划的递推方程可表为：f k (Wk ) maxvkuk fk 1(Wk1)0uk Wk / uk 例如：N=3 ，W = 5，w 1 = 2v 1 = 65，w 2 = 3，v 2 = 80，w 3 = 1，v 3 = 30u 1u 2u 3状态变量 W k：W 2 = W 1w 1 u 1，W 3 = W 2w 2 u 2，W 4 = W 3w 3 u 3W 2 = 52 u 1，W 3 = W 23 u 2，W 4 = W 3u 3当 k=3 时，u 3W 3 /w 35 / 1=524WWW3W123f 3(W3) max30u3 f4 (W4 )

37、max30u30u3 50u3 5当 k=2 时，u 2W 2 /w 25 / 3=1f 2 (W2 ) max80u2 f 3(W3 ) max80u2 f3(W2 3u2)0u2 10u2 1当 k=1 时，u 1W 1 /w 15 / 2=2f1 (W1 ) max65u1 f 2 (W2 ) max65u1 f 2 (W1 2u1 )0u120u1 2 max65u1 f 2(5 2u1 )0u1225u 1 * = 2 ，W 2 = 52 u 1= 1u 2 * = 0 ，W 3 = W 23 u 2 = 1 3 u 2=1u 3 * = 1总价值 = 265130 = 1604一般

38、数学规划问题一般数学规划模型包括线性规划、非线性规划、整数规划等，使用动态规划的方法来求解时，方法和步骤上大体相同。它把依次决定各个变量的取值看成是一个多阶段的决策过程，因而模型中含多少个变量，求解就分多少个阶段。约束条件的右端项表明可分配的资源数，用状态变量表示，而约束条件的个数则是状态变量的维数。P164【例 5】分别用动态规划的逆序和顺序解法求解下述非线性规划问题3max z ixii13 12 0 , i 1, 2, 3x i【解】将变量 x1、x2、x3 的取值人为地划分为 3 个阶段，k = 1，2，3 。x 1x 2x 326s 1s 2s 3s 4123（1）逆序解法状态变量 s k：s 1 = 12，s 2 = s 1 x 1，s 3 = s 2 3x 2，s 4 = s 3 2x 3。决策变量 x k0 x1 s 1，0 x2 s 2/3，0 x3 s 1