动态规划例

nullnull第三节 动态规划问题的一些例子§3.1 最短路径问题§3.2 投资分配问题§3.3 背包问题§3.4 排序问题§3.1 最短路径问题§3.1 最短路径问题例一、从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示距离，如图所示。问应该选择什么路线，使总距离最短？ AB1B2C1C2C3D24333321114null 解：整个计算过程分三个阶段，从最后一个阶段开始。 第一阶段（C →D）： C 有三条路线到终点D 。 AB1B2C1C2C3D24333321114DC1C2C3显然有 f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4 null d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 5第二阶段（B →C）： B 到C 有六条路线。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为B1→C1 →D)null d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为B2→C1 →D)null第三阶段（ A → B ）： A 到B 有二条路线。 f3(A)1 = d(A, B1 )＋ f2 ( B1 ) ＝2＋4＝6 f3 (A)2 = d(A, B2 )＋ f2 ( B2 ) ＝4＋3＝7∴ f3 (A) = min = min｛6,7｝=6d(A, B1 )＋ f2 ( B1 ) d(A, B2 )＋ f2 ( B2 )(最短路线为A→B1→C1 →D)AB1B2C1C2C3D24333321114DC1C2C3B1B2AnullAB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路线为 A→B1→C1 →D 路长为 6null练习1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最优路线为：A → B1 → C2 → D1 → E2 → F2 → G 路长＝18求从A到G的最短路径3nullk=5，出发点E1、E2、E3nullk=2, f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3null7 5 9 u5(E2)=F2u6(F2)=G最优策略AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643null求从A到E的最短路径路线为A→B2→C1 →D1 →E ，最短路径为19AB2B1B3C1C3D1D2EC25214112610104312111396581052练习2：1§3.2 投资分配问题§3.2 投资分配问题 现有数量为a（万元）的资金， 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 分配给n 个工厂,用于扩大再生产。 假设：xi 为分配给第i 个工厂的资金数量（万元） ；gi(xi)为第i 个工厂得到资金后提供的利润值（万元）。 问题是如何确定各工厂的资金数，使得总的利润为最大。 据此，有下式：null 令：fk(x) = 以数量为x 的资金分配给前k 个工厂，所得到的最大利润值。 用动态规划求解，就是求 fn(a) 的问题。 当 k=1 时， f1(x) = g1(x) （因为只给一个工厂） 当1＜k≤n 时，其递推关系如下： 设：y 为分给第k 个工厂的资金（其中 0≤y ≤ x ），此时还剩 x － y（万元）的资金需要分配给前 k-1 个工厂,如果采取最优策略，则得到的最大利润为fk－1(x－y) ,因此总的利润为： gk(y) ＋ fk－1(x－y) null 如果a 是以万元为资金分配单位，则式中的y 只取非负整数0，1，2，…，x。上式可变为：所以，根据动态规划的最优化原理，有下式：null 例题： 设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。解：依据题意，是要求 f4(60) 。null按顺序解法计算。 第一阶段：求 f1(x)。显然有 f1(x) ＝ g1(x)，得到下表第二阶段：求 f2(x)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。null最优策略为（40，20），此时最大利润为120万元。同理可求得其它 f2(x) 的值。null最优策略为（30，20），此时最大利润为105万元。null最优策略为（20，20），此时最大利润为90万元。最优策略为（20，10），此时最大利润为70万元。null最优策略为（10，0）或（ 0 ， 10 ） ，此时最大利润为20万元。 f2(0) ＝0。最优策略为（0，0），最大利润为0万元。 得到下表最优策略为（20，0），此时最大利润为50万元。null第三阶段：求 f3(x)。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。null最优策略为（20，10，30），最大利润为155万元。同理可求得其它 f3(x) 的值。得到下表null第四阶段：求 f4(60)。即问题的最优策略。null最优策略为（20，0，30，10），最大利润为160万元。null 练习： 求投资分配问题得最优策略，其中a＝50 万元，其余资料如表所示。null例：某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表所示。试问在各地区如何设置销售点可使每月总利润最大。 x1=2，x2=1，x3=1，f3(4)=47 §3.3 背包问题§3.3 背包问题 有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？ 这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。null设xj 为第j 种物品的装件数（非负整数）则问题的数学模型如下：用动态规划方法求解，令 fx(y) = 总重量不超过 y 公斤，包中只装有前k 种物品时的最大使用价值。 其中y ≥0， k ＝1,2, …, n 。所以问题就是求 fn(a) null其递推关系式为：当 k=1 时，有：null例题：求下面背包问题的最优解解：a＝5 ，问题是求 f3(5)nullnullnullnullnull所以，最优解为 X＝（1 . 1 . 0），最优值为 Z = 13。null 练习1：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过 6 吨，问如何安排运输，使总利润最大？最优 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ：X1 =（0.2.0）X2 =（1.0.1）Z=260null 练习2：求下列问题的最优解 X=(2. 1. 0) 最优值为 Z = 13§3.4 排序问题§3.4 排序问题 排序问题指n 种零件经过不同设备加工是的顺序问题。其目的是使加工周期为最短。 1、n × 1 排序问题 即n 种零件经过1 种设备进行加工，如何安排？例一、null （1）平均通过设备的时间最小 按零件加工时间非负次序排列顺序，其时间最小。（即将加工时间由小到大排列即可）零件加工顺序null延迟时间 = 13 – 6 = 7 （2）按时交货排列顺序零件加工顺序延迟时间 = 0null （3）既满足交货时间，又使平均通过时间最小零件加工顺序延迟时间 = 0null 2、n × 2 排序问题 即n 种零件经过2 种设备进行加工，如何安排？例二、null经变换为加工顺序图如下：ABT3756895432+2+2-5null 3、n × 3 排序问题 即n 种零件经过 3 种设备进行加工，如何安排？例三、nullABCT变换null排序复原null计算T = 6+10+8+7+6+4+3 = 44计算依据：null练习：