动态规划稿.docVIP

第三节 背包装载问题及旅行推销员问题 背包装载问题 １．问题：有一人带一背包旅行，其可携带物品重量限度为。现有编号为1，2，…，的种物品供他选择。已知第种物品每件重量为，价值携带数量的函数。问此人应如何选择携带物品，以使装货的价值最大？ ２．动态规划求解方法 首先建立模型 设为第种物品的装入件数，则问题的数学模型为 这是整数规划问题，若，即变量取值仅为０，１，则称为“0－1”背包问题。 现在我们用动态规划方法来求解背包问题。 按物品的个种类分为个阶段； 状态变量：表示用于装第1种至第种物品的 总重量； 决策变量：表示装入第种物品的件数； 状态转移方程： 允许决策集合： 式中的表示不超过的最大整数； 6最优指标函数：表示总重量不超过时，背包中可装入第1种至第种物品的最大价值，即 7递推关系： 要求： 求解过程：逐步计算及，最后得到和相应的最优策略。 例１　用动态规划方法求解 解：，问题就是求，递推关系为： 因此，求，需先计算。 为计算，又需先计算： 对我们有： 对应的最优决策为，因此得到： 从而有 最后得到： 即最优方案为，最大价值为13。 ３．多维背包问题 “二维背包问题”的数学模型为： 最优指标函数：表示当总重量不超过，总体积不超过时，背包中装入第一种到第种物品的最大使用价值。则有： 递推关系为： 按上面递推关系求出，即为所求的最大价值，对应的策就是最佳携带方案。 二、旅行推销员问题 １．问题：设有个城市，以1，2，…，表示。表示从城到城的距离。一个推销员从城1出发到其它每个城市一次且仅去一次，然后回到城1。问应如何选择行走路线，才能使总的路程最短。 ２．动态规划解法 1设推销员从城1开始，最终走到城,记 表示由城1到城的中间城市集合， ：到达城之前中途所经过的城市集合，则有； 2状态变量：； 3决策：一个城市走到另一个城市； 4最优的指标函数：从城1出发经由个中间城市的集到城的最短距离； 5递推关系： 6最优决策函数：表示从城1开始经个中间城市的集到城的最短路线上紧挨着城前面的那个城市。 按上面递推关系可逐步求出最后求出，即为最短距离。同时，由即可确定最优路线。 例２：求解四个城市的旅行推销员问题，各城之间的距离同例１。设推销员从城1出发，经过每个城市一次且仅一次，最后回到城1。问应如何选择行走路线，才能使总的行程距离最短？ 各城之间的距离 城 1 2 3 4 城 1 2 3 4 0 ４ 2 5 4 0 1 1 2 1 0 4 5 1 4 0 解：显然 由递推关系知 当时，即从城1出发，中间经过一个城市到城的最短距离是： 当时，即从城1出,发，中间经过二个城市到达城的最短距离是： 所以 对应的走法为：1—3—4—2 同理 1—4—2—3 1—3—2—4 当时，即从城1出发，中间经过三个城市回到城1最短距离为： 相应地得： 由此可知，推销员的最短旅行路线为： 1—3—2—4—1 或 1—4—2—3—1 最短总距离为9。 还有哪些问题可以归结为旅行推销员问题？ 如运输路线中，怎样安排运输工具的行走路线才能使总行程距离最短； 城市里在这一些地方铺设管道时，管子应走怎样的路线才能使所用管子最少等。 第四节 动态规划在电力系统中的应用示例 一、设备更新问题 在实际问题中，经常会遇到设备陈旧或部分损坏后何时需要更新的问题。 现以一台机器为例，随着使用时间的增加，机器的故障率增加，收入减少，维修、运行费用增加。而且机器使用年限越长，它本身的剩余价值就越小，因而更新时所需的净支出费用就越多。 1：在第年、役龄为年的一台机器运行所得到的收入； 2：在第年、役龄为年的一台机器运行时所需要的运行费用； 3：在第年、役龄为年的一台机器更新时的净更新费用； 4：折扣因子表示一年以后的单位收入价值相当现年的单位； 5：在第一年开始时，正在使用的机器的役龄； 6：计划的年限数； 7：在年开始使用一个役龄为年的机器，从第年至第年末的最大收入； 8：决策变量，表示在第年开始时，对一台役龄为年的机器保留还是更新。 8寻找递推关系 若在第年开始时购买了新机器，则从第年至第年得到的总收入应等于在第年由新机器获得的收入，减去第年中的运行费用，减去在第年开始时役龄为年的机器的净更新费用，加上在第年开始使用役龄为1年的机器从第年至第年的最大收入；若在第年开始时继续使用役龄为年的机器，则从第年至第年的总收入应等于在第年由役龄为年的机器得到的收入，减去它的运行费用，加上在第年开始使用役龄为年的机器从第年至第年的最大收入。然后，比较它们的大小，选取大的，从而得出是更新还是保留的决策