第三节动态规划题的一些例子.ppt

§3.1 最短路径问题 §3.2 投资分配问题 §3.3 背包问题 §3.4 排序问题 所以，最优解为 X＝（1 . 1 . 0），最优值为 Z = 13。 练习1：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过 6 吨，问如何安排运输，使总利润最大？ 80 130 180 单件利润（元） 2 3 4 重量（吨/公斤） 1 2 3 种类 最优方案：X1 =（0.2.0）X2 =（1.0.1）Z=260 练习2：求下列问题的最优解 X=(2. 1. 0) 最优值为 Z = 13 排序问题指n 种零件经过不同设备加工是的顺序问题。其目的是使加工周期为最短。 1、n × 1 排序问题 即n 种零件经过1 种设备进行加工，如何安排？ 14 6 8 20 23 交货日期（d） 4 5 1 7 3 加工时间（t） 零件代号 例一、 * 第三节 动态规划问题的一些例子 §3.1 最短路径问题 §3.2 投资分配问题 §3.3 背包问题 §3.4 排序问题 例一、从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？ A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 解：整个计算过程分三个阶段，从最后一个阶段开始。 第一阶段（C →D）： C 有三条路线到终点D 。 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 显然有 f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4 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 有六条路线。 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 B1 B2 (最短路线为B1→C1 →D) 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 5 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 B1 B2 (最短路线为B2→C1 →D) 第三阶段（ 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｝=6 d(A, B1 )＋ f2 ( B1 ) d(A, B2 )＋ f2 ( B2 )