(Dynamic programming)

Presentation on theme: "(Dynamic programming)"— Presentation transcript:

1 (Dynamic programming)
动 态 规 划 (Dynamic programming) 背包问题 资源分配问题 生产计划问题 复合系统工作可靠性问题

2 背包问题 有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？ 物品 … j … n 重量（公斤/件） a a … aj … an 每件使用价值 c c … cj … cn 这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。

3 设xj 为第j 种物品的装件数（非负整数）则问题的数学模型如下：
用动态规划方法求解，令 fk(y) = 总重量不超过 y 公斤，包中只装有前k 种物品时的最大使用价值。 其中y ≥0， k ＝1,2, …, n 。所以问题就是求 fn(a)

4 其递推关系式为： 当 k=1 时，有：

5 例题：求下面背包问题的最优解 物品 重量（公斤） 使用价值 解：a＝5 ，问题是求 f3(5)

6

7

8

9

10 所以，最优解为 X＝（ ），最优值为 Z = 13。

11 练习2：求下列问题的最优解

12 机器负荷问题 　　　某工厂有100台机器，拟分四期使用，每一期都可在高、低两种不同负荷下进行生产。若把x台机器投入高负荷下进行生产，则在本期结束时将有(1/3)*x台机器损坏报废；余下的机器全部投入低负荷下进行生产，则在期末有1/10的机器报废。如果高负荷下生产时每台机器可获利润为10，低负荷下生产时每台机器可获利润为7，问怎样分配机器使四期的总利润最大？ 解 将问题按周期分为4个阶段，k=1，2，3，4； 状态变量sk表示第k阶段初完好的机器数，s1=100，0≤sk≤100； 决策变量xk表示第k阶段投入高负荷下生产的机器数， 则sk－xk表示第k阶段投入低负荷下生产的机器数； 允许决策集合：Dk（sk）=｛xk|0≤xk≤sk｝ 状态转移方程：sk+1=Tk（sk，xk），即第k+1阶段初拥有的完好机器数sk+1为：

13 　　　阶段指标函数：vk（sk，xk）=10xk+7（sk－xk）表示第k阶段所获得的利润；
　　　最优指标函数fk（sk）表示从第k阶段初完好机器数为sk至第四阶段的最大利润，动态规划基本方程为： 　k=4时， 　　　　　　　　　x4*=s4 　k=3时， 　　　　　　　 ∴ x3*=s3

14 k=2时， 　　　　　　　 ∴ x2*=0 k=1时， 　　　　　　　　　 ∴ x1*=0

15 因为s1=100，所以f1（100）=2680，逆向追踪得： 　s1=100， x1*=0 　　　　　　　　　　　　　　　　x2*=0 　　　　　　　　　　　　　　　　x3*=s3=81 　　　　　　　　　　　　　　　　x4*=s4=54 　　即，第1，2期把全部完好机器投入低负荷下生产，第3，4期把全部完好机器投入高负荷下生产所得利润最大。

16 三、非线性规划问题 【例7-4】 用动态规划方法解下列非线性规划问题

17 作业1：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过 6 吨，问如何安排运输，使总利润最大？
种类 重量（吨/公斤） 单件利润（元）