(Dynamic programming) 动 态 规 划 (Dynamic programming) 背包问题 资源分配问题 生产计划问题 复合系统工作可靠性问题
背包问题 有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？ 物品 1 2 … j … n 重量（公斤/件） a1 a2 … aj … an 每件使用价值 c1 c2 … cj … cn 这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。
设xj 为第j 种物品的装件数（非负整数）则问题的数学模型如下： 用动态规划方法求解，令 fk(y) = 总重量不超过 y 公斤，包中只装有前k 种物品时的最大使用价值。 其中y ≥0， k ＝1,2, …, n 。所以问题就是求 fn(a)
其递推关系式为： 当 k=1 时，有：
例题：求下面背包问题的最优解 物品 1 2 3 重量（公斤） 3 2 5 使用价值 8 5 12 解：a＝5 ，问题是求 f3(5)
所以，最优解为 X＝（1 . 1 . 0），最优值为 Z = 13。
练习2：求下列问题的最优解
机器负荷问题 某工厂有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为：
阶段指标函数：vk（sk，xk）=10xk+7（sk－xk）表示第k阶段所获得的利润； 最优指标函数fk（sk）表示从第k阶段初完好机器数为sk至第四阶段的最大利润，动态规划基本方程为： k=4时， x4*=s4 k=3时， ∴ x3*=s3
k=2时， ∴ x2*=0 k=1时， ∴ x1*=0
因为s1=100，所以f1（100）=2680，逆向追踪得： s1=100， x1*=0 x2*=0 x3*=s3=81 x4*=s4=54 即，第1，2期把全部完好机器投入低负荷下生产，第3，4期把全部完好机器投入高负荷下生产所得利润最大。
三、非线性规划问题 【例7-4】 用动态规划方法解下列非线性规划问题
作业1：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过 6 吨，问如何安排运输，使总利润最大？ 种类 1 2 3 重量（吨/公斤） 2 3 4 单件利润（元） 80 130 180