DP应用(建模)

1、 从某地出发，途径若干个中间点从某地出发，途径若干个中间点最后到达目的地，试求距离最短或最后到达目的地，试求距离最短或费用最省的路线。费用最省的路线。 具体有两种情况：具体有两种情况： 基基 本本 方方 程程 1 ,2, 1,0) !()(min)(11nnknfjfCifnkijjk 最最 短短 路路 问问 题题 最最 长长 路路 问问 题题 阶阶段段：nk,2, 1 状状态态变变量量：各各阶阶段段初初始始位位置置 )(kkkkXiXx或 决决策策变变量量：各各阶阶段段终终止止位位置置 )(kkkkUjUu或 状状态态转转移移方方程程：)()(11kkkkkkijixux或 阶阶段段效效益益

2、)(),(1的费用kkkijkkkxuxCuxr 目目标标函函数数：kkkknkijnkkjiuxCrR),(11 基基本本方方程程：1210)()().(min)(111，nnkjfjfjiCifnnkkkkkjkkk 1210)()().(max)(111，nnkjfjfjiCifnnkkkkkjkkk1210)()().(max)(111，nnkjfjfjiCifnnkkkkkjkkk 或或简简化化为为1 , 1,0)()(min)(111nnkifjfCifnnkijjk 或或1 , 1,0)()(max)(111nnkifjfCifnnkijjk 若是不定步数问题，则基本方若是不定步

3、数问题，则基本方程呈函数方程的形式：程呈函数方程的形式：)(min)(jfcifijj ： ？投放资金（万元）投放资金（万元）012345收收 益益 (万元万元)A022333B001247C01234531)(kkkugR 一一 般般 问问 题题 例例 4-2 大大前前提提 阶阶 段段 变变量量 k 把把每每一一种种活活动动作作为为一一个个阶阶段段，n 种种生生产产活活动动构构成成 n 个个阶阶段段。 由由于于每每个个阶阶段段都都要要确确定定对对该该项项活活动动的的资资源源投投放放量量，从从而而构构成成多多阶阶段段决决策策问问题题 把把资资金金分分配配给给一一个个企企业业的的过过程程看看作作

4、一一种种生生产产活活动动，向向三三个个企企业业的的投投资资过过程程看看作作三三个个阶阶段段 条条件件 1 状状态态与与状状态态变变量量 k 阶阶段段初初拥拥有有的的资资源源量量，即即对对第第 k 阶阶段段到到第第 n 阶阶段段这这 n-k 种种活活动动中中可可进进行行分分配配的的资资源源量量 0 x xk kM M，x x1 1= =M M 给给企企业业 K 投投资资时时所所拥拥有有的的资资金金数数 （即即初初始始的的资资源源拥拥有有量量）xk，0 x xk k5 5，x x1 1= =5 5 条条件件 2 决决策策与与决决策策变变量量 对对第第 k 种种生生产产活活动动的的资资源源投投放放量

5、量 0u uk kx xk k 给给企企业业 k 的的投投资资数数（阶阶段段投投放放量量） 0u uk kx xk k 条条件件 3 状状态态转转移移方方程程 xk+1=xk-uk xk+1=xk-uk 阶阶段段效效应应 对对活活动动投投放放资资源源 uk时时的的收收益益 rk（xk，uk）=gk（uk） gk（uk） ，k=1，2，3 条条件件 4 目目标标函函数数 R=nkkknkkkkuguxr11)(),( 31),(kkkkuxgR 一一个个方方程程 基基本本方方程程 1210)()()(max)(1111，nnkxfxfugxfnnkkkkukkk 12, 30)()()(max)

6、(4411，kxfxfugxfkkkkukkk 资资金金分分配配完完毕毕，不不再再分分配配，收收益益为为 0 0 今有今有1000台机床，要投放到台机床，要投放到A、B两个生产部门，计划连续使用两个生产部门，计划连续使用5年。年。已知对已知对A部门投入部门投入ua台机器时的年收益台机器时的年收益是是g(ua)=ua2元，机器完好率元，机器完好率a=0.8；相应；相应地，地，B部门为部门为h(ub)=2ub2，b=0.4。 试建立试建立5年间总收益最大的年度机年间总收益最大的年度机器分配方案。器分配方案。 一一 般般 问问 题题 例例 4-3 前前 提提 ： n 阶阶段段决决策策，每每个个阶阶段

7、段均均要要决决定定 A、B 两两个个部部门门的的资资源源投投放放量量 。 K=1,2, ,n 5 阶阶 段段 决决 策策 问问 题题 ， (机机 器器 连连 续续 使使 用用 五五 年年 ) 一一 个个 年年 度度 作作 为为 一一 个个 阶阶 段段 ；k=1， 2， 3， 4， 5。 状状 态态 与与 状状态态 变变 量量 k阶阶 段段 初初 拥拥 有有 的的 资资 源源 量量kx MxMxk1,0 k年年 初初 拥拥 有有 的的 完完 好好 机机 器器 数数kx 1000,100001xxk 决决 策策 与与 决决策策 变变 量量 k阶阶 段段 对对 A 部部 门门 的的 资资 源源 投投

8、 放放 量量Akuu 则则 有有 ：AkkkBuxuxu kkxu0 k年年 度度 投投 入入 A 部部 门门 的的 机机 器器 台台 数数Akuu （kkBuxu） kkxu0 状状 态态 转转 移移方方 程程 )(1kkkkuxbaux 阶阶 段段 末末 A 部部 门门 剩剩 余余 资资 源源 阶阶 段段 末末 B 部部 门门 剩剩 余余 资资 源源 )(4.08.01kkkkuxux 阶阶 段段 效效 益益与与 目目 标标 函函数数 )()(),(kkkkkkuxhuguxr nkkkknkkuxhugrR11)()( 22)(2)()(kkkkkkkuxuuxhugr nkkkknkk

9、uxurR1221)(2 基基 本本 方方 程程 1 , 1,0)()()()(max)(1111nnkxfxfuxhugxfnnkkkkkukkk 1 ,2,3 ,4,50)()()(2max)(661120kxfxfuxuxfkkkkkxukkkk 生产（或销售）部门生产（或销售）部门已知已知生产成生产成本、库存费用、各阶段的市场需求，本、库存费用、各阶段的市场需求，各阶段产量（或采购量），各阶段产量（或采购量），使计划期内的使计划期内的费用总和最小费用总和最小。：设有一生产部门，生产计划：设有一生产部门，生产计划周期分为周期分为n个阶段（即个阶段（即k=1n）已知最初库存量）已知最初库存

10、量为为x1，阶段产量需求为，阶段产量需求为dk，生产的固定成本，生产的固定成本为为 ，单位产品的消耗费用为，单位产品的消耗费用为L，单位产品的，单位产品的阶段库存费用为阶段库存费用为h，库存容量为，库存容量为M，阶段生产能，阶段生产能力为力为B，问应，问应如何安排各阶段的产量，使计划如何安排各阶段的产量，使计划期内的费用总和最小。期内的费用总和最小。k k 例例4-4 求解生产求解生产-库存问题：已知库存问题：已知n=3， =8，L=2，h=2，x1=1，M=4，x4=0（计划期末库存（计划期末库存为为0），），B=6，d1=3，d2=4，d3=3。 问问 题题 一一 般般 形形 式式 例例4

11、 - 4 阶阶 段段 （ k ） 计计 划划 期期 所所 划划 分分 的的 阶阶 段段 即即 为为 D P模模 型型 的的 阶阶 段段 nk,2,1 3,2,1,3kn 状状态态与与状状态态 变变 量量 第第k阶阶 段段 初初 的的 库库 存存 量量kx，1x已已 知知 。 若若1nx已已 知知 ，则则 为为 始始 、 终终 端端 固固 定定 的的 问问 题题 ， 若若1nx= 0 即即 计计 划划 期期 末末无无 库库 存存 。 这这 样样 ， nkkkdddMx1,min0 11x（ 初初 始始 库库 存存 ） 04x（ 计计 划划 期期 末末 库库 存存 为为0 ） 3,min0ddMx

12、kk 决决 策策 与与 决决策策 变变 量量 k阶阶 段段 的的 产产 量量ku knkkkkxddBuxd,min kkkkkxdduxd3,6min 状状 态态 转转 移移方方 程程 kkkkduxx 1 k = 1 ， ， n kkkkduxx 1 ， k = 1 ， 2 ， 3 阶阶 段段 效效 益益与与 目目 标标 函函数数 生生 产产 费费 用用 + 库库 存存 费费 用用 )(1kkkkkkkduxhLukhxLukr hkkrR1 )(2282281kkkkkkkduxuxur31)(228kkkkkduxuR 基 本 方 程 1 ,1,0)()()(min)(1111nnkx

13、fxfduxhLukxfnnkkkkkkukkk 1 ,2,30)()()(228min)(4411kxfxfduxuxfkkkkkkukkk ：已知：已知n为计算设备回为计算设备回收额的总期数，收额的总期数，t为某个阶段的设备役龄，为某个阶段的设备役龄，r(t)为从役龄为为从役龄为t的设备得到的阶段效益，的设备得到的阶段效益，u(t)为役龄为为役龄为t的设备的阶段使用费，的设备的阶段使用费，s(t)是是役龄为役龄为t的设备处理价格，的设备处理价格，p为新设备的购为新设备的购置价格。假定关于现值的折扣率为置价格。假定关于现值的折扣率为1，求求n期内使回收额最大的设备更新策略。期内使回收额最大的设备更新策略。 表4-6 例4-5有关信息表 (单位：万元) t期数 0 1 2 3 4 5 6 7 8 9 10 r（t） 27 26 26 25 24 23 23 22 21 21 20 u(t) 15 15 16 16 16 17 18 18 19 20 20 问题的一般提法问题的一般提法 例例 4 4- -5 5 阶阶 段段 设备使用年限设备使用年限 n=10 状态变量状态变量 设备的役龄设备的役龄 t 决策变量决策变量 K保留保留 P更新更新 k 或或 p 状态转移状态转移方程方程 )(1)(决策决策ktpt 阶段效应阶段效应与目标函与目标函数数 从役龄从役龄 t 为