运筹学--第七章 动态规划

１８９

习题七7.1计算如图所示的从A 到E 的最短路线及其长度（单位：km ）：

（1） 用逆推解法；2用标号法。

7.2 用动态规划方法求解下列问题

（1） max z ＝x 12x 2 x 33

x 1＋x 2＋x 3 ≤6

x j ≥0 （j ＝1,2,3）

（2）min z ＝ 3x 12＋4x 22 ＋x 32

x 1x 2 x 3 ≥ 9

x j ≥0 （j ＝1,2,3）

7.3 利用动态规划方法证明平均值不等式：

n n n x x x n

x x x 12121)()( ≥+++ 设x i ≥0，i ＝1，2，…，n 。 7.4 考虑一个有m 个产地和n 个销地的运输问题。设a i （i ＝1，2，…，m ）为产地i 可发运的物资数，b j （j ＝1，2，…，n ）为销地j 所需要的物资数。又从产地i 到销地j 发运x ij 单位物资所需的费用为h ij （x ij ），试将此问题建立动态规划的模型。

7.5 某公司在今后三年的每一年的开头将资金投入A 或B 项工程，年末的回收及其概率如下表所示。每年至多做一项投资，每次只能投入1000万元。求出三年后所拥有的期望金额达到最大的投资方案。

投 资 回 收 概 率

A 0 0.4

2000 0.6

B 1000 0.9

2000 0.1

7.6 某公司有三个工厂，它们都可以考虑改造扩建。每个工厂都有若干种方案可供选择，各种方案的投资及所能取得的收益如下表所示(单位：千万元)。现公司有资金5千万元，问应如何分配投资使公司的总收益最大?

7.7 某厂准备连续3个月生产A种产品，每月初开始生产。A的生产成本费用为x2，其中x是A产品当月的生产数量。仓库存货成本费是每月每单位为1元。估计3个月的需求量分别为d1＝100，d2＝110，d3＝120。现设开始时第一个月月初存货s0＝0，第三个月的月末存货s3＝0。试问：每月的生产数量应是多少才使总的生产和存货费用为最小。

7.8 设有一辆载重卡车，现有4种货物均可用此车运输。已知这4种货物的重量、容积及价值关系如下表所示。

货物代号重量（吨）容积（立方米）价值（千元）

1 2 2 3

2 3 2 4

3 4 2 5

4 5 3 6

若该卡车的最大载重为15吨，最大允许装载容积为10立方米，在许可的条件下，每车装载每一种货物的件数不限。问应如何搭配这四种货物，才能使每车装载货物的价值最大。

7.9 某警卫部门有12支巡逻队负责4个仓库的巡逻。按规定对每个仓库可分别派2－4支队伍巡逻。由于所派队伍数量上的差别，各仓库一年内预期发生事故的次数如下表所示。试应用动态规划的方法确定派往各仓库的巡逻队数，使预期事故的总次数为最少。

巡逻队数预期事故次数仓库 1 2 3 4

2 18 38 14 34

3 16 36 12 31

4 12 30 11 25

7.10 （生产计划问题）根据合同，某厂明年每个季度末应向销售公司提供产品，有关信息见下表。若产品过多，季末有积压，则一个季度每积压一吨产品需支付存贮费0.2万元。现需找出明年的最优生产方案，使该厂能在完成合同的情况下使全年的生产费用最低。

季度j生产能力a j（吨）生产成本d j（万元/吨）需求量b j（吨）

1 30 15.6 20

2 40 14.0 25

3 25 15.3 30

4 10 14.8 15

（1）请建立此问题的线性规划模型。（提示：设第j季度工厂生产产品x j吨，第j季度初存贮的产品为y j吨，显然y1＝0）（2）请建立此问题的动态规划模型。（均不用求解）

１９０

胡运权运筹学第七章习题解

7.3某厂每月生产某种产品最多600件，当月生产的产品若未销出，就需贮存（刚入库的产品下月不付存储费）月初就已存储的产品需支付存储费，每100件每月1000元。已知每100件产品的生产费为5千元，在进行生产的月份工厂支出经营费4千元，市场需求如表7-19所示，假定1月初及4月底库存量为零，试问每月应生产多少产品，才能在满足需求条件下， 解： 设阶段变量：k=1,2,3 状态变量：k x 第k 个月初的库存量 决策变量：k d 第k 个月的生产量 状态转移方程：1k k k k x x r d 阶段指标：(,)k k k k v x d c d 由于在4月末，仓库存量为0，所以对于k=4阶段来说有两种决策： 5+4=9 40x 4()f x = 1 41x 对K=3 334()54()f x x f x K=2

解得：第一个月生产500份，第二个月生产600份，第三个月生产0份，第四个月生产0份。 7.4某公司有资金4万元，可向A ，B ，C 三个项目投资，已知各项目不同投资额的相应效益值如表7-20所示，问如何分配资金可使总效益最大。 表 7-20 解： 设阶段变量k ，{ }4,3,2,1∈k ，每一个项目表示一个阶段;

状态变量S k，表示可用于第k阶段及其以后阶段的投资金额； 决策变量Ｕk，表示在第k阶段状态为S k下决定投资的投资额； 决策允许集合：0≤Ｕk≤S k 状态转移方程：S k+1=S k-Ｕk; 阶段指标函数：V k(S kＵk)； 最优指标函数：f k(S k)=max{ V k(S kＵk)+ f k+1(S k+1)} 终端条件：f4(x4)=0； K=4, f4(x4)=0 k=3, 0≤Ｕ3≤S3 k=2, 0≤Ｕ2≤S2 k=1, 0≤Ｕ1≤S1 所以根据以上计算，可以得到获得总效益最大的资金分配方案为（1，2，1）.

运筹学第七章动态规划

习题七7.1计算如图所示的从A 到E 的最短路线及其长度（单位：km ）： （1） 用逆推解法；2用标号法。 7.2 用动态规划方法求解下列问题 （1） max z ＝x 12x 2 x 33 x 1＋x 2＋x 3 ≤6 x j ≥0 （j ＝1,2,3） （2）min z ＝ 3x 12＋4x 22 ＋x 32 x 1x 2 x 3 ≥ 9 x j ≥0 （j ＝1,2,3） 7.3 利用动态规划方法证明平均值不等式： n n n x x x n x x x 12121)()( ≥+++ 设x i ≥0，i ＝1，2，…，n 。 7.4 考虑一个有m 个产地和n 个销地的运输问题。设a i （i ＝1，2，…，m ）为产地i 可发运的物资数，b j （j ＝1，2，…，n ）为销地j 所需要的物资数。又从产地i 到销地j 发运x ij 单位物资所需的费用为h ij （x ij ），试将此问题建立动态规划的模型。 7.5 某公司在今后三年的每一年的开头将资金投入A 或B 项工程，年末的回收及其概率如下表所示。每年至多做一项投资，每次只能投入1000万元。求出三年后所拥有的期望金额达到最大的投资方案。 投 资 回 收 概 率 A 0 0.4 2000 0.6 B 1000 0.9 2000 0.1 7.6 某公司有三个工厂，它们都可以考虑改造扩建。每个工厂都有若干种方案可供选择，各种方案的投资及所能取得的收益如下表所示(单位：千万元)。现公司有资金5千万元，问应如何分配投资使公司的总收益最大?

7.7 某厂准备连续3个月生产A种产品，每月初开始生产。A的生产成本费用为x2，其中x是A产品当月的生产数量。仓库存货成本费是每月每单位为1元。估计3个月的需求量分别为d1＝100，d2＝110，d3＝120。现设开始时第一个月月初存货s0＝0，第三个月的月末存货s3＝0。试问：每月的生产数量应是多少才使总的生产和存货费用为最小。 7.8 设有一辆载重卡车，现有4种货物均可用此车运输。已知这4种货物的重量、容积及价值关系如下表所示。 货物代号重量（吨）容积（立方米）价值（千元） 1 2 2 3 2 3 2 4 3 4 2 5 4 5 3 6 若该卡车的最大载重为15吨，最大允许装载容积为10立方米，在许可的条件下，每车装载每一种货物的件数不限。问应如何搭配这四种货物，才能使每车装载货物的价值最大。 7.9 某警卫部门有12支巡逻队负责4个仓库的巡逻。按规定对每个仓库可分别派2－4支队伍巡逻。由于所派队伍数量上的差别，各仓库一年内预期发生事故的次数如下表所示。试应用动态规划的方法确定派往各仓库的巡逻队数，使预期事故的总次数为最少。 巡逻队数预期事故次数仓库 1 2 3 4 2 18 38 14 34 3 16 36 12 31 4 12 30 11 25 7.10 （生产计划问题）根据合同，某厂明年每个季度末应向销售公司提供产品，有关信息见下表。若产品过多，季末有积压，则一个季度每积压一吨产品需支付存贮费0.2万元。现需找出明年的最优生产方案，使该厂能在完成合同的情况下使全年的生产费用最低。 季度j生产能力a j（吨）生产成本d j（万元/吨）需求量b j（吨） 1 30 15.6 20 2 40 14.0 25 3 25 15.3 30 4 10 14.8 15 （1）请建立此问题的线性规划模型。（提示：设第j季度工厂生产产品x j吨，第j季度初存贮的产品为y j吨，显然y1＝0）（2）请建立此问题的动态规划模型。（均不用求解）

胡运权运筹学第七章习题解

某厂每月生产某种产品最多600件，当月生产的产品若未销出，就需贮存（刚入库的产品下月不付存储费）月初就已存储的产品需支付存储费，每100件每月1000元。已知每100件产品的生产费为5千元，在进行生产的月份工厂支出经营费4千元，市场需求如表7-19所示，假定1月初及4月底库存量为零，试问每月应生产多少产品，才能在满足需求条件下， 解： 设阶段变量：k=1,2,3 状态变量：k x 第k 个月初的库存量 决策变量：k d 第k 个月的生产量 状态转移方程：1 k k k k x x r d 阶段指标：(,)k k k k v x d c d 由于在4月末，仓库存量为0，所以对于k=4阶段来说有两种决策： 5+4=9 40x 4()f x = 1 41x 对K=3 334()54()f x x f x K=2

K=1时 d 5 解得：第一个月生产500份，第二个月生产600份，第三个月生产0份，第四个月生产0份。 某公司有资金4万元，可向A ，B ，C 三个项目投资，已知各项目不同投资额的相应效益值如表7-20所示，问如何分配资金可使总效益最大。 表 7-20

解： 设阶段变量k ，{ }4,3,2,1∈k ，每一个项目表示一个阶段; 状态变量S k ，表示可用于第k 阶段及其以后阶段的投资金额； 决策变量Ｕk ，表示在第k 阶段状态为S k 下决定投资的投资额； 决策允许集合：0≤Ｕk ≤S k 状态转移方程：S k+1=S k -Ｕk ; 阶段指标函数：V k (S k Ｕk )； 最优指标函数：f k (S k )=max{ V k (S k Ｕk )+ f k+1(S k+1)} 终端条件：f 4(x 4)=0； K=4, f 4(x 4)=0 k=3, 0≤Ｕ3≤S 3 k=2, 0≤Ｕ2≤S 2 k=1, 0≤Ｕ1≤S 1

运筹学实验_动态规划

实验二用MATLAB解决动态规划问题 问题：有一部货车每天沿着公路给四个售货店卸下6箱货物，如果各零售店出售该货物所得利润如下表所示，试求在各零售店卸下几箱货物，能使获得总利润最大其值为多少 解： 1)将问题按售货店分为四个阶段 2)设s k表示为分配给第k个售货店到第n个工厂的货物数， x k设为决策变量，表示为分配给第k个售货店的货物数， 状态转移方程为s k＋1＝s k－x k。 P k(x k)表示为x k箱货物分到第k个售货店所得的盈利值。 f k(s k)表示为s k箱货物分配给第k个售货店到第n个售货店的最大盈利值。 3)递推关系式： f k(s k)＝max[ P k(x k)+ f k+1(s k－x k) ] k=4,3,2,1 边界条件：f5(s5)＝0 4)从最后一个阶段开始向前逆推计算。 第四阶段： 设将s4箱货物（s4＝0,1,2,3,4,5,6）全部分配给4售货店时，最大盈利值为：f4(s4)＝ *表示使得f

第三阶段： 设将s3箱货物（s3＝0,1,2,3,4,5,6）分配给3售货店和4售货店时，对每一个s3值，都有一种最优分配方案，使得最大盈利值为：f3(s3)＝max[ P3(x3)+ f4(s3－x3) ] ，x3＝ 设将s2箱货物（s2＝0,1,2,3,4,5,6）分配给2售货店、3售货店和4售货店时，则最大盈利值为：f2(s2)＝max[ P2(x2)+ f3(s2－x2) ] 其中，x 第一阶段： 设将s2箱货物（s1＝0,1,2,3,4,5,6）分配给1售货店、2售货店、3售货店和4售货店时，则最大盈利值为：f1(s1)＝max[ P1(x1)+ f2(s1－x1) ]

《运筹学》第五章习题及答案

《运筹学》第五章习题及答案 《运筹学》第五章习题 1．思考题 （1）试述动态规划的“最优化原理”及它同动态规划基本方程之间的关系。（2）动态规划的阶段如何划分？ （3）试述用动态规划求解最短路问题的方法和步骤。 （4）试解释状态、决策、策略、最优策略、状态转移方程、指标函数、最优值函数、边界函数等概念。 （5）试述建立动态规划模型的基本方法。 （6）试述动态规划方法的基本思想、动态规划的基本方程的结构及正确写出动态规划基本方程的关键步骤。 2．判断下列说法是否正确 （1）动态规划分为线性动态规划和非线性动态规划。 （2）动态规划只是用来解决和时间有关的问题。 （3）对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解。 （4）在用动态规划的解题时，定义状态时应保证各个阶段中所做的决策的相互独立性。 （5）在动态规划模型中，问题的阶段等于问题的子问题的数目。（6）动态规划计算中的“维数障碍”，主要是由于问题中阶段数的急剧增加

而引起的。 3．计算下图所示的从A到E的最短路问题 4．计算下图所示的从A到E的最短路问题 5．计算从A到B、C、D的最短路线。已知各线段的长度如下图所示。 6．设某油田要向一炼油厂用管道供应油料，管道铺设途中要经过八个城镇，各 城镇间的路程如下图所示，选择怎样的路线铺设，才使总路程最短？

7．用动态规划求解下列各题 （1）．2 22211295m a x x x x x z-+-=； ?? ?≥≤+0,52 121x x x x； （2）． 3 3 221m a x x x x z= ?? ?≥≤++0,,6321 321x x x x x x； 8．某人外出旅游，需将3种物品装入背包，但背包重量有限制，总重量不超过 10千克。物品重量及其价值等数据见下表。试问每种物品装多少件，使整个背包的价值最大？ 913千克。物品重量及其价值的关系如表所示。试问如何装这些物品，使整个背包价值最大？

运筹学--第七章 动态规划

１８９ 习题七7.1计算如图所示的从A 到E 的最短路线及其长度（单位：km ）： （1） 用逆推解法；2用标号法。 7.2 用动态规划方法求解下列问题 （1） max z ＝x 12x 2 x 33 x 1＋x 2＋x 3 ≤6 x j ≥0 （j ＝1,2,3） （2）min z ＝ 3x 12＋4x 22 ＋x 32 x 1x 2 x 3 ≥ 9 x j ≥0 （j ＝1,2,3） 7.3 利用动态规划方法证明平均值不等式： n n n x x x n x x x 12121)()( ≥+++ 设x i ≥0，i ＝1，2，…，n 。 7.4 考虑一个有m 个产地和n 个销地的运输问题。设a i （i ＝1，2，…，m ）为产地i 可发运的物资数，b j （j ＝1，2，…，n ）为销地j 所需要的物资数。又从产地i 到销地j 发运x ij 单位物资所需的费用为h ij （x ij ），试将此问题建立动态规划的模型。 7.5 某公司在今后三年的每一年的开头将资金投入A 或B 项工程，年末的回收及其概率如下表所示。每年至多做一项投资，每次只能投入1000万元。求出三年后所拥有的期望金额达到最大的投资方案。 投 资 回 收 概 率 A 0 0.4 2000 0.6 B 1000 0.9 2000 0.1 7.6 某公司有三个工厂，它们都可以考虑改造扩建。每个工厂都有若干种方案可供选择，各种方案的投资及所能取得的收益如下表所示(单位：千万元)。现公司有资金5千万元，问应如何分配投资使公司的总收益最大?

7.7 某厂准备连续3个月生产A种产品，每月初开始生产。A的生产成本费用为x2，其中x是A产品当月的生产数量。仓库存货成本费是每月每单位为1元。估计3个月的需求量分别为d1＝100，d2＝110，d3＝120。现设开始时第一个月月初存货s0＝0，第三个月的月末存货s3＝0。试问：每月的生产数量应是多少才使总的生产和存货费用为最小。 7.8 设有一辆载重卡车，现有4种货物均可用此车运输。已知这4种货物的重量、容积及价值关系如下表所示。 货物代号重量（吨）容积（立方米）价值（千元） 1 2 2 3 2 3 2 4 3 4 2 5 4 5 3 6 若该卡车的最大载重为15吨，最大允许装载容积为10立方米，在许可的条件下，每车装载每一种货物的件数不限。问应如何搭配这四种货物，才能使每车装载货物的价值最大。 7.9 某警卫部门有12支巡逻队负责4个仓库的巡逻。按规定对每个仓库可分别派2－4支队伍巡逻。由于所派队伍数量上的差别，各仓库一年内预期发生事故的次数如下表所示。试应用动态规划的方法确定派往各仓库的巡逻队数，使预期事故的总次数为最少。 巡逻队数预期事故次数仓库 1 2 3 4 2 18 38 14 34 3 16 36 12 31 4 12 30 11 25 7.10 （生产计划问题）根据合同，某厂明年每个季度末应向销售公司提供产品，有关信息见下表。若产品过多，季末有积压，则一个季度每积压一吨产品需支付存贮费0.2万元。现需找出明年的最优生产方案，使该厂能在完成合同的情况下使全年的生产费用最低。 季度j生产能力a j（吨）生产成本d j（万元/吨）需求量b j（吨） 1 30 15.6 20 2 40 14.0 25 3 25 15.3 30 4 10 14.8 15 （1）请建立此问题的线性规划模型。（提示：设第j季度工厂生产产品x j吨，第j季度初存贮的产品为y j吨，显然y1＝0）（2）请建立此问题的动态规划模型。（均不用求解） １９０

运筹学各章的题

《运筹学》各章的作业 ----复习思考题及作业题 第一章绪论 复习思考题 1、从运筹学产生的背景认识本学科研究的内容和意义。 2、了解运筹学的内容和特点，结合自己的理解思考学习的方法和途径。 3、体会运筹学的学习特征和应用领域。 第二章线性规划建模及单纯形法 复习思考题 1、线性规划问题的一般形式有何特征？ 2、建立一个实际问题的数学模型一般要几步？ 3、两个变量的线性规划问题的图解法的一般步骤是什么？ 4、求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 5、什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 6、试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 7、试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 8、在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 9、大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？ 10、什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 作业题: 1、把以下线性规划问题化为标准形式： (1) max z= x1-2x2+x3 s.t. x1+x2+x3≤12 2x1+x2-x3≥ 6 -x1+3x2＝9 x1, x2, x3≥0 (2) min z= -2x1-x2+3x3-5x4 s.t x1+2x2+4x3-x4≥ 6 2x1+3x2-x3+x4＝12 x1+x3+x4≤ 4 x1, x2, x4≥0