深圳大学管理学院：《运筹学》课程教学资源（案例PPT）动态规划-应用

运筹学课件 主讲:郭家雄 课件制作:郭家雄 小组成员: 李干彪(学号:2002044002) 彭丹(学号:2002044008) 张玲玲(学号:2002044010) 莫斌(学号:2002044037) 郭家雄(学号:2002044038) 刘东平(学号:2002044046) 范万里(学号:2002044047) 陈晓川(学号:2002044053) 2021112/24

2021/12/24 1 运筹学课件 主 讲：郭家雄 课件制作：郭家雄 ◼ 小组成员： ◼ 李干彪（学号：2002044002） ◼ 彭 丹（学号：2002044008） ◼ 张玲玲（学号：2002044010） ◼ 莫 斌（学号：2002044037） ◼ 郭家雄（学号：2002044038） ◼ 刘东平（学号：2002044046） ◼ 范万里（学号：2002044047） ◼ 陈晓川（学号：2002044053）

今天,我们来上背包问题 首先让我们来看一个小偷背包問題:有個 偷,光顧一家超級市場,他帶了一個背 包來裝所偷的東西,假設他的背包最多只 能裝三十公斤,而超市內的每樣東西有 的重量及價 偷背包問題是要找出最 佳的偷法,使得背包內所裝的贓物總價值 最高 重 樣 的一個問題居然也是難題!如果小偷用數 位計算機來替他決定最好的偷法,在他得 到答案前,可能早就被繩之以法了。所以 这节课就让我们来了解和熟悉背包问题 2021/12/24

2021/12/24 2 今天，我们来上背包问题 首先让我们来看一个小偷背包問題：有個 小偷，光顧一家超級市場，他帶了一個背 包來裝所偷的東西，假設他的背包最多只 能裝三十公斤，而超市內的每樣東西有它 的重量及價值，小偷背包問題是要找出最 佳的偷法，使得背包內所裝的贓物總價值 最高，且總重量又不超過三十公斤。這樣 的一個問題居然也是難題！如果小偷用數 位計算機來替他決定最好的偷法，在他得 到答案前，可能早就被繩之以法了。所以 这节课就让我们来了解和熟悉背包问题

态规划在经济管理中的应 背包问题 2021/12/24 独上高楼

2021/12/24 3 动态规划在经济管理中的应 用： 背包问题

背包问题的介绍 位旅行者携带背包去登山,已知 他所能承受的背包重量限度为a千克, 现有n种物品可供他选择装入背包, 第种物品的单件重量为千克,其 价值(可以是表明本物品对登山的 重要性的数量指标)是携带数量 的函数(ie(,)2,…,n),问 旅行者应如何选择携带各种物品的 件数,以使总价值最大? 2021/12/24

2021/12/24 4 背包问题的介绍: 一位旅行者携带背包去登山，已知 他所能承受的背包重量限度为a千克， 现有n种物品可供他选择装入背包， 第i种物品的单件重量为 千克，其 价值（可以是表明本物品对登山的 重要性的数量指标）是携带数量 的函数 （i＝1，2，…，n），问 旅行者应如何选择携带各种物品的 件数，以使总价值最大？

进一步了解 如何结合“背包问题”的 整数规划模型理解目标函 数及约束条件的含义 2021/12/24 5

2021/12/24 5 进一步了解 ◼ 如何结合“背包问题”的 整数规划模型理解目标函 数及约束条件的含义

如何建模求解 注意“背包问题”是整数规划问 题 1k∑(S+Ob 如何利用动态规划顺序解法来建 模求解 2021112/24 6

2021/12/24 6 如何建模求解 ◼ 注意“背包问题”是整数规划问 题 ◼ 如何利用动态规划顺序解法来建 模求解

基本方程为 fA(S+)=0p1{V(S+1,U)+-1(S)…k=1,2;…,n f(S)=0 2021/12/24

2021/12/24 7 ·基本方程为

小结 正确写出最优目标 函数,即正确写出 每一步的 f K(Sk+1) 正确应用约束条件 写出每一段状态变 量的取值范围和表 达式 2021/12/24 8

2021/12/24 8 小结◼ 正确写出最优目标 函数，即正确写出 每一步的 ◼ 正确应用约束条件 写出每一段状态变 量的取值范围和表 达式

考虑多维的情况 当约束条件不止一个时,就是多维 背包问题,其状态变量时多维的, 但解法于一维背包问题类似意义 2021/12/24 9

2021/12/24 9 考虑多维的情况 ◼ 当约束条件不止一个时，就是多维 背包问题，其状态变量时多维的， 但解法于一维背包问题类似意义