4-3动态规划应用() 建模练习
4-3 动 态 规 划 应用(一) 建 模 练 习
工程路线问题 (也称最短路或最长路问题) 工程路线问题的一般提法: 从某地出发,途径若干个中间点 最后到达目的地,试求距离最短或 费用最省的路线。 具体有两种情况:
一、工程路线问题 （也称最短路或最长路问题） 工程路线问题的一般提法： 从某地出发，途径若干个中间点 最后到达目的地，试求距离最短或 费用最省的路线。 具体有两种情况：
1.从出发点到目的地的每条路线均由n条 边(弧)组成,因此问题可以化为n个 阶段的多阶段决策过程。由于可以明确 地划分出固定的阶段数,所以称为定步 数问题,亦称定期的多阶段决策过程。 2.阶段数不固定则称为不定步数问题,或 不定期的多阶段决策过程。 建模过程如表4-1
1. 从出发点到目的地的每条路线均由n条 边（弧）组成，因此问题可以化为n个 阶段的多阶段决策过程。由于可以明确 地划分出固定的阶段数，所以称为定步 数问题，亦称定期的多阶段决策过程。 2. 阶段数不固定则称为不定步数问题，或 不定期的多阶段决策过程。 建模过程如表4-1
表4工程路线的建模过程 10=m 基本方 k=n,n-1,…,2,1 1(n+!)=0 最短路问题 最长路问题 阶段:k=1,2,…,n 「状态变量:各阶段初始位置x∈或(∈x)√ 决策变量:各阶段终止位置∈U或k∈UA)√ 状态转移方程:xk+1=uk(xk)或ik+1=jk(k) 阶段效益(x2)=C0(xk→4=x的费用)√ R=∑ Cu(xk,uk) 目标函数: KoK 基本方[(k)=mnA(kJ)++(k) ∫(4)=mxCA()+() fm+1(n+1)=0 k=n,n-1,……2,l fn+1(n+1)=0 k =n,n-1,…2,1 (4)=mxA()+() fn+1(n+1)=0 k= 1,…2,1 或简化为 f(=min Cu+&+o)) f2(=max Cu+k+Oj 或 fn+1(n+1)=0k=n,n-1,…,1 n. n
表4-1 工程路线的建模过程 基 本 方 程 , 1, ,2,1 ( !) 0 ( ) min ( ) 1 1 = − + = = + + + k n n f n f i C f j n i j k j k 最 短 路 问 题 最 长 路 问 题 阶段：k = 1,2,, n √ 状态变量：各阶段初始位置 ( ) k k k X k x X 或 i √ 决策变量：各阶段终止位置 ( ) k k k U k u U 或 j √ 状态转移方程： ( ) ( ) k 1 k k k 1 k k x = u x i = j i + 或 + √ 阶段效益 ( , ) ( ) rk xk uk = Ci j xk → uk = xk+1的费用 √ 目标函数： k k k k n k i j n k k i j R r C x u = = = = ( , ) 1 1 √ 基本方程： = = − = + + + + ( ) 0 1 2 1 ( ) min ( . ) ( ) 1 1 1 f j k n，n ， ， f i C i j f j n n k k k k k j k k k = = − = + + + + ( ) 0 1 2 1 ( ) max ( . ) ( ) 1 1 1 f j k n，n ， ， f i C i j f j n n k k k k k j k k k = = − = + + + + ( ) 0 1 2 1 ( ) max ( . ) ( ) 1 1 1 f j k n，n ， ， f i C i j f j n n k k k k k j k k k 或简化为 = = − = + + + + ( ) 0 , 1, ,1 ( ) min ( ) 1 1 1 f i k n n f i C f j n n i j k j k 或 = = − = + + + + ( ) 0 , 1, ,1 ( ) max ( ) 1 1 1 f i k n n f i C f j n n i j k j k
若是不定步数问题,则基本方 程呈函数方程的形式: f(i=min cu+fof
若是不定步数问题，则基本方 程呈函数方程的形式： f (i) min cij f ( j) j = +
资源分配问题: 1、资源的多元分配: 某种资源总量为M,用于进行n种 生产活动,已知用于活动k的资源量 为u时收益为g(u),(g(u)为u 的非递减函数),问如何分配资源, 才能使n种生产活动的总收益最大?
二、资源分配问题： 1. 资源的多元分配： 某种资源总量为M，用于进行n种 生产活动，已知用于活动k的资源量 为uk时收益为gk (uk )，（ gk (uk )为uk 的非递减函数），问如何分配资源， 才能使n种生产活动的总收益最大？
例42:某公司拟将5万元资金投放下属A、B C三个企业,各企业在获得资金后的收益如 下表所示,用动态规划方法求总收益最大的 投资分配方案(投资数取整数)。 表42例4-2已知信息表 投放资金(万元) 收益 2 53 (万元) ABC 0000 0 2212 3323 4344 7 5
例4-2：某公司拟将5万元资金投放下属A、B、 C三个企业，各企业在获得资金后的收益如 下表所示，用动态规划方法求总收益最大的 投资分配方案（投资数取整数）。 表4-2 例4-2已知信息表 投放资金（万元） 0 1 2 3 4 5 收 益 (万元) A 0 2 2 3 3 3 B 0 0 1 2 4 7 C 0 1 2 3 4 5
该问题可以作为三阶段决策过程。 对A、B、C三个企业资金分配过程分 别形成1、2、3三个阶段。 x表示给企业分配资金数时拥有的资金数。 u为给企业实际分配的资金数 数 状态转移方程是x+1=xk-k 表函 阶段效应r(xu)如表42所示,记为g(u)。 目标函数是: R=∑g4(uk) k=1
= = 3 1 ( ) k R gk uk 该问题可以作为三阶段决策过程。 对A、B、C三个企业资金分配过程分 别形成1、2、3三个阶段。 xk表示给企业分配资金数时拥有的资金数。 uk为给企业实际分配的资金数。 状态转移方程是xk+1=xk -uk。 阶段效应rk (xk ,uk )如表4-2所示,记为gk (uk )。 目标函数是：
般问题 例42 大|阶段 把每一种活动作为一个阶段,n种生产活把资金分配给一个企业的过程看作 前变量k动构成n个阶段,由于每个阶段都要确定|一种生产活动,向三个企业的投资过 提 对该项活动的资源投放量,从而构成多阶程看作三个阶段 段决策问题 条状态与状态k阶段初拥有的资源量,即对第k阶段到给企业K投资时所拥有的资金数(即 赚件1变量 第n阶段这nk种活动中可进行分配的资初始的资源拥有量)x,0≤x≤5, 源量0≤x≤M,x1=M 5 的多台配问题建模过 多|条|次策与决策对第种生产动的资源投放重给企业的投资数(阶投放量 件2变量 0≤u≤x1 0≤u≤xk 条|状态转移方|x:-xa 件3程 条阶段效应对活动投放资源u时的收益 gk(uk),k=1,2,3 件4 k(xk, uk) -gk (uk 目标函数 R∑n(xk,k)=∑gA(4) R=∑gk(xk2,uk) 基本方程 f k(xk)=max gk(uk)+fk+(xk+1)) fr(xx)=maxi(uk)+k+(xk+D) 个 f+1(x+)=0k=n,m-1…2,14(x4)=0 k=3.2,1 方 程 资金分配完毕,不再分配,收益为0
一 般 问 题 例 4-2 大前提 阶 段 变量 k 把每一种活动作为一个阶段，n 种生产活 动构成 n 个阶段。由于每个阶段都要确定 对该项活动的资源投放量，从而构成多阶 段决策问题 把资金分配给一个企业的过程看作 一种生产活动，向三个企业的投资过 程看作三个阶段 条件 1 状态与状态 变量 k 阶段初拥有的资源量，即对第 k 阶段到 第 n 阶段这 n-k种活动中可进行分配的资 源量 0 ≤xk ≤M，x1 = M 给企业 K 投资时所拥有的资金数（即 初始的资源拥有量）xk，0≤xk ≤5， x1 = 5 条件 2 决策与决策 变量 对第 k 种生产活动的资源投放量 0≤uk≤xk 给企业 k 的投资数（阶段投放量） 0≤uk≤xk 条件 3 状态转移方 程 xk+1=xk-uk xk+1=xk-uk 阶段效应 对活动投放资源 uk时的收益 rk（xk，uk）=gk（uk） 条 gk（uk） ，k=1，2，3 件 4 目标函数 R= = = = nk k k nk rk xk uk g u 1 1 ( , ) ( ) = = 31 ( , ) k k k uk R g x 一个方程 基本方程 = = − = + + + + + ( ) 0 1 2 1 ( ) max ( ) ( ) 1 1 1 1 f x k n，n ， ， f x g u f x n n k k k k u k k k = = = + + + ( ) 0 3,2 1 ( ) max ( ) ( ) 4 4 1 1 f x k ， f x g u f x k k k k u k k k 资金分配完毕，不再分配，收益为 0 表4- 3资源的多元分配问题建模过程
2.资源的多段分配—有消耗的资源 多阶段地在两种不同的生产活动中投放的问题 问题的提法:假定拥有某种资源,总量为 M,计划在A、B两种生产过程(部门)中连 续使用n个阶段,已知在两个部门中分别投入 资源u、u后可分别获得阶段效益g(u)、 h(ub),同时知道每生产一个阶段后资源的完 好率分别为a和b,(0<a<1,0<b<1),求n个 阶段间总收益最大的资源分配计划
2. 资源的多段分配——有消耗的资源 多阶段地在两种不同的生产活动中投放的问题 问题的提法：假定拥有某种资源，总量为 M，计划在A、B两种生产过程（部门）中连 续使用n个阶段，已知在两个部门中分别投入 资源ua、ub后可分别获得阶段效益g(ua ) 、 h(ub )，同时知道每生产一个阶段后资源的完 好率分别为a和b，（0<a<1,0<b<1），求n个 阶段间总收益最大的资源分配计划