运筹学教材编写组《运筹学》章节题库(第10章 动态规划应用举例——第12章 网络计划)【圣才出品】
- 格式：pdf
- 大小：2.53 MB
- 文档页数：72
下载文档原格式
合集下载
(完整版)运筹学》习题答案运筹学答案
《运筹学》习题答案一、单选题1.用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（）BA.任意网络B.无回路有向网络C.混合网络D.容量网络2.通过什么方法或者技巧可以把工程线路问题转化为动态规划问题？（）BA.非线性问题的线性化技巧B.静态问题的动态处理C.引入虚拟产地或者销地D.引入人工变量3.静态问题的动态处理最常用的方法是？BA.非线性问题的线性化技巧B.人为的引入时段C.引入虚拟产地或者销地D.网络建模4.串联系统可靠性问题动态规划模型的特点是（）DA.状态变量的选取B.决策变量的选取C.有虚拟产地或者销地D.目标函数取乘积形式5.在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是( )。
CA.降低的B.不增不减的C.增加的D.难以估计的6.最小枝权树算法是从已接接点出发，把( )的接点连接上CA.最远B.较远C.最近D.较近7.在箭线式网络固中，( )的说法是错误的。
DA.结点不占用时间也不消耗资源B.结点表示前接活动的完成和后续活动的开始C.箭线代表活动D.结点的最早出现时间和最迟出现时间是同一个时间8.如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是( )。
CA.1200B.1400C.1300D.17009.在求最短路线问题中，已知起点到A，B，C三相邻结点的距离分别为15km，20km,25km，则（）。
DA.最短路线—定通过A点B.最短路线一定通过B点C.最短路线一定通过C点D.不能判断最短路线通过哪一点10.在一棵树中，如果在某两点间加上条边，则图一定( )AA.存在一个圈B.存在两个圈C.存在三个圈D.不含圈11.网络图关键线路的长度( )工程完工期。
CA.大于B.小于C.等于D.不一定等于12.在计算最大流量时，我们选中的每一条路线( )。
CA.一定是一条最短的路线B.一定不是一条最短的路线C.是使某一条支线流量饱和的路线D.是任一条支路流量都不饱和的路线13.从甲市到乙市之间有—公路网络，为了尽快从甲市驱车赶到乙市，应借用（）CA.树的逐步生成法B.求最小技校树法C.求最短路线法D.求最大流量法14.为了在各住宅之间安装一个供水管道．若要求用材料最省，则应使用( )。
运筹学教材编写组《运筹学》课后习题(第10章 动态规划应用举例——第12章 网络计划)【圣才出品】
6 / 87
圣才电子书 十万种考研考证电子书、题库视频学习平台
10.3 某公司打算向承包的三个营业区增设六个销售店，每个营业地区至少增设一个， 从各区赚取的利润与增设的销售店个数有关，其数据如表 10-11 所示。试求各区应分配几 个增设的销售店，才能使总利润最大?其值是多少?
25
28
0
2
47
53
45
53
1
3
67
72
73
57
73
2
4
89
92
92
85
65
92
1,2
5
108 114 112 104
93
70
114
1
6
126 133 134 124 112
98
73
134
2
当 k =1 时
分别取 x1为0,1,…, 6 时。其数值计算如表 10-10 所示：
表 10-10
所以，总的最大增产量为 134，最优分配方案有如下四种：
当 k =2 时， 由题意，可取 x2 1,2,3, 4, s2 2,3, 4,5 ，其数值计算如表 10-13 所示：
表 10-13
当 k =l 时， 由题意，可取 x1 1,2,3, 4 ， s1 6 ，其数值计算如表 10-14 所示：
表 10-14 所以，总利润最大值为 710 万元，最优增设方案有三种：
表 10-11
解：按营业区数将此问题划分三个阶段；状态变量 sk 表示第 k 个区至第 3 个区增设的 店数； xk 表示第 k 个区增设的店数， xk 1；状态转移方程为： sk1 sk xk ；阶段指标
pk xk 表示为第 k 区内增设店数为 xk 时所取得的利润；最优值函数 fk sk 表示第 k 个区
运筹学智慧树知到答案章节测试2023年华东交通大学
第一章测试1.用运筹学解决问题时，要对问题进行（）。
A:分析与考察B:分析和定义C:分析和实验D:分析和判断答案:B2.运筹学是一门（）。
A:定性分析的学科B:定量分析的学科C:定量与定性相结合的学科D:定量与定性相结合的学科，其中分析与应用属于定性分析，建立模型与求解属于定量分析答案:C3.规划论内容不包括（）。
A:非线性规划B:动态规划C:网络分析D:线性规划答案:C4.运筹学主要研究对象是各种有组织系统的管理问题及生产经营活动。
（）A:对B:错答案:A5.研究大量随机现象，从中揭示出事物基本规律的科学方法是指线性规划法。
（）A:对B:错答案:B6.统筹学是用教学方法研究各种系统最优化问题的学科。
（）A:对B:错答案:B7.若用图解法求解线性规划问题，则该问题所含决策变量的数目一般为（）。
A:无限制B:五个以下C:二个D:三个以上答案:C8.图解法求解极小化线性规划问题，一般目标函数直线放在可行域内，并（）移动。
A:垂直梯度方向移动。
B:沿着梯度反方向移动。
C:沿着梯度方向移动。
D:任意方向移动答案:B9.在二元线性规划问题中，如果问题有可行解，则一定有最优解。
（）A:错B:对答案:A10.任何线性规划问题一定有最优解。
（）A:对B:错答案:B11.下面哪些不是线性规划问题的标准形式所具备的（）？A:所有的变量必须是非负的B:添加新变量时，可以不考虑变量的正负性C:所有的约束条件（变量的非负约束除外）必须是等式D:求目标函数的最小值答案:B12.线性规划标准型中，决策变量（）是非负的。
A:不一定B:一定不C:一定D:无法判断答案:C13.下列哪种解法必须化标准型（）？A:MATLAB软件B:单纯形表格法C:WinQSB软件D:图解法答案:B14.线性规划的标准型主要特征为：(1)目标函数为极大化类型；(2)所有的约束条件都是等式；(3)所数学规划有约束方程右端的常数都是非负的；(4)所有决策变量都是非负的。
管理运筹学：第10章 动态规划
5－
r3(s3, x3)
1
2
3
4
5 f3(s3) x*3
－－ －－－ 0 0
4 － －－－ 4 1
－ 6－ －－ 6 2
－ － 11 － － 11 3
－ － － 12 － 12 4
－ － － － 12 12 5
管理运筹学
15
§3 动态规划的应用(1)
其中
x
* 3
表示取3子过程上最优指标值f3(s3)时的 x3
区别，也可知这时 x2的最优决策为1或2。
管理运筹学
18
§3 动态规划的应用(1)
第一阶段：
把 s1(s1 5) 台设备分配给第1，第2，第3厂时，最大
盈数利值为计算f1(见5) 表m1xa10x－[r1(85, x1) f1(5 x1)],其中 x1可取值0,1,2,3,4,5.
s1 x1 0
管理运筹学
5
§1 多阶段决策过程最优化问题举例
第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分 析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题：
表10-3
本阶段始点 （状态）
B1 B2 B3 B4
阶段2 本阶段各终点（决策）
C1 2+12=14 4+12=16 4+12=16 7+12=19
为最大，即
max x3
r3
(s3
,
x3
)
r3
(s3
,
s3
)
由于第3阶段是最后的阶段，故有
f3
(s3
)
max x3
r3
(s3
运筹学试题及答案
运筹学试题及答案一、线性规划试题一某工厂生产A、B两种产品，A产品每件利润为20元，B 产品每件利润为30元。
已知生产一个A产品需10小时，生产一个B产品需15小时。
某次生产过程中，工厂共有50个小时可用于生产，且设定A产品的最少需求量为20件，B产品的最少需求量为15件。
问应该生产多少件A产品和多少件B产品，才能使得工厂的利润最大化？答案一为了使工厂的利润最大化，我们需要建立一个数学模型来描述这个问题。
设工厂生产的A产品数量为x，B产品数量为x。
根据题目中的要求，可得以下条件：1.$10x+15y\\leq50$ （生产时间的限制）2.$x\\geq20$ （A产品的最少需求量）3.$y\\geq15$ （B产品的最少需求量）另外，我们还需要定义目标函数，即使工厂利润最大化：$max\\ Z = 20x+30y$根据以上条件和目标函数，可以得到如下线性规划模型：$max\\ Z = 20x+30y$$\\begin{cases} 10x+15y\\leq50\\\\ x\\geq20\\\\y\\geq15\\\\ x,y\\geq0 \\end{cases}$以上模型可以通过线性规划求解软件进行求解，得到最优解。
试题二某公司有甲、乙、丙三个工厂，每个工厂都可以制造产品A和产品B。
甲工厂每天制造产品A的数量最多为80件，产品B的数量最多为100件；乙工厂每天制造产品A的数量最多为60件，产品B的数量最多为40件；丙工厂每天制造产品A的数量最多为50件，产品B的数量最多为70件。
公司有订单，要求每天至少制造产品A的30件，产品B的50件。
甲工厂生产产品A的成本为5元，产品B的成本为4元；乙工厂生产产品A的成本为4元，产品B的成本为3元；丙工厂生产产品A的成本为3元，产品B的成本为2元。
问如何安排存货以使公司在利润最大化的前提下能够满足订单需求？答案二为了使公司在利润最大化的前提下满足订单需求，我们需要建立一个数学模型来描述这个问题。
运筹学第10章动态规划
从k阶段状态sk出发，对所有的子策略，最优的过程指标函数称为最 优指标函数，记为fk(sk)，通常取Vk的最大值或最小值。
管 理 运 精品资料 筹 学
17
动态(dòngtài)规划要求过程指标满足递推关系 ，即
Vk (sk , xk , xk1, , xn ) Vk [v(sk , xk ),Vk1(sk1, xk1, , xn )]
管 理 运 精品资料 筹 学
20
动态(dòngtài)规划方法的基本思想
• 结合解决最短路线问题来介绍动态规划方法(fāngfǎ) 的基本思想。生活中的常识告诉我们, 最短路线有一 个重要特性: 如果由起点A 经过P 点和H 点而到达终 点G 是一条最短路线, 则由点P 出发经过H 点到达终 点G 的这条子路线, 对于从点P 出发到达终点的所有 可能选择的不同路线来说, 必定也是最短路线。
连和形式 (xíngshì)：
VK VK (sk , xk , xk1, , xn ) vk (sk , xk）＋VK (sk＋1, xk1, , xn )
n1
v j (s j , x j）Vn jk
最优指标函数是
f k (sk ) Opt {vk (sk , xk } f k1 (sk1 )}, k 1,2,, n
xk Dk ( sk )
管 理 运 精品资料 筹 学
18
连乘形式(xíngshì)(VvjK≠0)V：K (sk , xk , xk1, , xn )
vk (sk , xk ) VK (sk＋1, xk1, , xn )
n1
j =k
vj
(s j
,
xj
) Vn
最优指标函数是
fk (sk ) Opt {vk (sk , xk } fk1(sk1)}, k 1, 2, , n
管 理 运 精品资料 筹 学
17
动态(dòngtài)规划要求过程指标满足递推关系 ，即
Vk (sk , xk , xk1, , xn ) Vk [v(sk , xk ),Vk1(sk1, xk1, , xn )]
管 理 运 精品资料 筹 学
20
动态(dòngtài)规划方法的基本思想
• 结合解决最短路线问题来介绍动态规划方法(fāngfǎ) 的基本思想。生活中的常识告诉我们, 最短路线有一 个重要特性: 如果由起点A 经过P 点和H 点而到达终 点G 是一条最短路线, 则由点P 出发经过H 点到达终 点G 的这条子路线, 对于从点P 出发到达终点的所有 可能选择的不同路线来说, 必定也是最短路线。
连和形式 (xíngshì)：
VK VK (sk , xk , xk1, , xn ) vk (sk , xk）＋VK (sk＋1, xk1, , xn )
n1
v j (s j , x j）Vn jk
最优指标函数是
f k (sk ) Opt {vk (sk , xk } f k1 (sk1 )}, k 1,2,, n
xk Dk ( sk )
管 理 运 精品资料 筹 学
18
连乘形式(xíngshì)(VvjK≠0)V：K (sk , xk , xk1, , xn )
vk (sk , xk ) VK (sk＋1, xk1, , xn )
n1
j =k
vj
(s j
,
xj
) Vn
最优指标函数是
fk (sk ) Opt {vk (sk , xk } fk1(sk1)}, k 1, 2, , n
运筹学教材编写组《运筹学》课后习题-动态规划的基本方法(圣才出品)
由此，可得出三条最优的运输路线：
（1） A → B2 →C1 → D1 → E ；（2） A → B3 →C1 → D1 → E ； （3） A → B3 →C2 → D2 → E 。
8.3 计算从 A 到 B、C 和 D 的最短路线。已知各段路线的长度如图 8-2 所示。
图 8-2
解：设阶段变量 k = 1, 2,3, 4 ,依次表示 4 个阶段选择路线的过程；状态变量 sk 表示第 k 阶段初所处的位置；决策变量 xk 表示第 k 阶段初可能选择的路线；最优值函数 fk (sk ) 表示 从起点 A 到第 k 阶段状态 sk 的最短距离，则有
xn =sn
n
xn
，或 fn+1(sn+1) = 0
n
（2）设状态变量为 sk = ai xi (k = 1, 2, n) ，状态转移方程为 sk+1 = sk − ak xk ，最 i=k
n
优值函数 fk (sk ) 表示在 sk 状态下从第 k 阶段到第 n 阶段使 z = ci xi2 最小的值，则动态规 i=k
划的基本方程为：
3 / 11
圣才电子书 十万种考研考证电子书、题库视频学习平台
fk (sk )
=
min
0xk sk ak
{ck
xk2
+
f k +1 (sk
− ak xk )}
fn+1(sn − anxn ) = 0(k = n, n −1, 2,1)
8.5 用递推方法求解下列问题。
=
max {2
0x3 10
x32
+
f2 (s2 )} =
max {2
0x3 10
（1） A → B2 →C1 → D1 → E ；（2） A → B3 →C1 → D1 → E ； （3） A → B3 →C2 → D2 → E 。
8.3 计算从 A 到 B、C 和 D 的最短路线。已知各段路线的长度如图 8-2 所示。
图 8-2
解：设阶段变量 k = 1, 2,3, 4 ,依次表示 4 个阶段选择路线的过程；状态变量 sk 表示第 k 阶段初所处的位置；决策变量 xk 表示第 k 阶段初可能选择的路线；最优值函数 fk (sk ) 表示 从起点 A 到第 k 阶段状态 sk 的最短距离，则有
xn =sn
n
xn
，或 fn+1(sn+1) = 0
n
（2）设状态变量为 sk = ai xi (k = 1, 2, n) ，状态转移方程为 sk+1 = sk − ak xk ，最 i=k
n
优值函数 fk (sk ) 表示在 sk 状态下从第 k 阶段到第 n 阶段使 z = ci xi2 最小的值，则动态规 i=k
划的基本方程为：
3 / 11
圣才电子书 十万种考研考证电子书、题库视频学习平台
fk (sk )
=
min
0xk sk ak
{ck
xk2
+
f k +1 (sk
− ak xk )}
fn+1(sn − anxn ) = 0(k = n, n −1, 2,1)
8.5 用递推方法求解下列问题。
=
max {2
0x3 10
x32
+
f2 (s2 )} =
max {2
0x3 10
第10章 动态规划
②某些情况下，用动态规划处理不仅能定性描 述分析，且可利用计算机给出求其数值解的 方法。
管理运筹学
7
缺点
①没有统一的处理方法，求解时要根据问题的 性质，结合多种数学技巧。因此实践经验及 创造性思维将起重要的引导作用；
②“维数障碍”，当变量个数太多时，由于计 算机内存和速度的限制导致问题无法解决。 有些问题由于涉及的函数没有理想的性质使 问题只能用动态规划描述，而不能用动态规 划方法求解。
盈利 工厂 设备台数
0 1 2
3 4 5
甲厂
0 3 7 9 12 13
乙厂
0 5 10 11 11 11
管理运筹学
29
第一阶段：只有1个始点A，终点有B1,B2,B3,B4 。对始点和终 点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：
表10-4
本阶段始 点(状态)
A
阶段1 本阶段各终点（决策）
B1
B2
B3
B4
4+12=16 3+13=16 3+14=17 2+12=14
到E的最 本阶段最优终 短距离 点(最优决策)
第四阶段：两个始点D1和D2，终点只有一个；
表10-1
阶段4
本阶段始点 本阶段各终点（决策） 到E的最短距离
（状态）
E
D1
10
10
D2
6
6
分析得知：从D1和D2到E的最短路径唯一。
本阶段最优终点 （最优决策)
E E
管理运筹学
27
第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点
和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路
管理运筹学
7
缺点
①没有统一的处理方法，求解时要根据问题的 性质，结合多种数学技巧。因此实践经验及 创造性思维将起重要的引导作用；
②“维数障碍”，当变量个数太多时，由于计 算机内存和速度的限制导致问题无法解决。 有些问题由于涉及的函数没有理想的性质使 问题只能用动态规划描述，而不能用动态规 划方法求解。
盈利 工厂 设备台数
0 1 2
3 4 5
甲厂
0 3 7 9 12 13
乙厂
0 5 10 11 11 11
管理运筹学
29
第一阶段：只有1个始点A，终点有B1,B2,B3,B4 。对始点和终 点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：
表10-4
本阶段始 点(状态)
A
阶段1 本阶段各终点（决策）
B1
B2
B3
B4
4+12=16 3+13=16 3+14=17 2+12=14
到E的最 本阶段最优终 短距离 点(最优决策)
第四阶段：两个始点D1和D2，终点只有一个；
表10-1
阶段4
本阶段始点 本阶段各终点（决策） 到E的最短距离
（状态）
E
D1
10
10
D2
6
6
分析得知：从D1和D2到E的最短路径唯一。
本阶段最优终点 （最优决策)
E E
管理运筹学
27
第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点
和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路
运筹学教材习题答案
教材习题答案部分有图形的答案附在各章PPT文档的后面，请留意。
第1章线性规划第2章线性规划的对偶理论第3章整数规划第4章目标规划第5章运输与指派问题第6章网络模型第7章网络计划第8章动态规划第9章排队论第10章存储论第11章决策论第12章对策论习题一1.1 讨论下列问题：（1）在例1.1中，假定企业一周内工作5天，每天8小时，企业设备A有5台，利用率为0.8,设备B有7台，利用率为0.85,其它条件不变，数学模型怎样变化．（2）在例1.2中，如果设x j(j=1，2，…，7)为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化．（3）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路．（4）在例1.4中，若允许含有少量杂质，但杂质含量不超过1％，模型如何变化．（5）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化．1.2 工厂每月生产A、B、C三种产品,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－22所示．310和130.试建立该问题的数学模型,使每月利润最大．【解】设x1、x2、x3分别为产品A、B、C的产量，则数学模型为123123123123123max 1014121.5 1.2425003 1.6 1.21400150250260310120130,,0Z x x x x x x x x x x x x x x x =++++≤⎧⎪++≤⎪⎪≤≤⎪⎨≤≤⎪⎪≤≤⎪≥⎪⎩ 1.3 建筑公司需要用6m 长的塑钢材料制作A 、B 两种型号的窗架．两种窗架所需材料规格及数量如表1－23所示：【解】设x j （j =1,2,…，14）为第j 种方案使用原材料的根数，则 （1）用料最少数学模型为14112342567891036891112132347910121314min 2300322450232400232346000,1,2,,14jj j Z x x x x x x x x x x x x x x x x x x x x x x x x x x x x x j ==⎧+++≥⎪++++++≥⎪⎪++++++≥⎨⎪++++++++≥⎪⎪≥=⎩∑ 用单纯形法求解得到两个基本最优解X (1)=( 50 ,200 ,0 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=534 X (2)=( 0 ,200 ,100 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,150 ,0 ,0 );Z=534 （2）余料最少数学模型为134131412342567891036891112132347910121314min 0.60.30.70.40.82300322450232400232346000,1,2,,14j Z x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x j =+++++⎧+++≥⎪++++++≥⎪⎪++++++≥⎨⎪++++++++≥⎪⎪≥=⎩ 用单纯形法求解得到两个基本最优解X (1)=( 0 ,300 ,0 ,0,50 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料550根 X (2)=( 0 ,450 ,0 ,0,0 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料650根 显然用料最少的方案最优。
《运筹学》课程考试试卷试题(含答案)
《运筹学》课程考试试卷试题(含答案)一、选择题（每题5分，共25分）1. 运筹学的核心思想是（）A. 最优化B. 系统分析C. 预测D. 决策答案：A2. 在线性规划中，约束条件可以用（）表示。
A. 等式B. 不等式C. 方程组D. 矩阵答案：B3. 以下哪个不是运筹学的基本模型？（）A. 线性规划B. 整数规划C. 非线性规划D. 随机规划答案：D4. 在目标规划中，以下哪个术语描述的是决策变量的偏离程度？（）A. 目标函数B. 约束条件C. 偏差变量D. 权重系数答案：C5. 在动态规划中，以下哪个概念描述的是在决策过程中，某一阶段的最优决策对后续阶段的影响？（）A. 最优子结构B. 无后效性C. 最优性原理D. 阶段性答案：B二、填空题（每题5分，共25分）1. 运筹学是一门研究在复杂系统中的______、______和______的科学。
答案：决策、优化、实施2. 在线性规划中，若目标函数为最大化，则其标准形式为______。
答案：max z = c^T x3. 在非线性规划中，若目标函数和约束条件均为凸函数，则该规划问题为______。
答案：凸规划4. 在目标规划中，若决策变量x_i的权重系数为w_i，则目标函数可以表示为______。
答案：min Σ(w_i d_i^+ + w_i d_i^-)5. 在动态规划中，若状态变量为s_n，决策变量为u_n，则状态转移方程可以表示为______。
答案：s_{n+1} = f(s_n, u_n)三、判断题（每题5分，共25分）1. 线性规划问题的最优解一定在可行域的顶点处取得。
（）答案：正确2. 在整数规划中，若决策变量为整数，则目标函数和约束条件也必须为整数。
（）答案：错误3. 目标规划中的偏差变量可以是负数。
（）答案：正确4. 在动态规划中，最优策略具有最优子结构。
（）答案：正确5. 在非线性规划中，若目标函数为凸函数，则约束条件也必须为凸函数。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
求为零。求最优生产计划。[北京交通大学 2009 研]
表 10-1
时期（月） 需求量（dk）
12Leabharlann 2332
4
4
解：采用动态规划方法求解。设第 k 个月生产 xk 件产品， xk 6 ； sk 为每个月开始的
存货量，则 s1=0,s5 =0 ，
fk (sk )
min( xk
gk
(
xk
)
ck
(
xk
)
f k 1 (sk 1 ))
4
s4
k =3 时，
f3 (s3 )
min
2s3 x3 6
s3
(
g3
(
x3
)
c3
(
x3
)
f4 (s4 ))
min
2s3 x3 6
s3[（3 3
x3） 0.5(x3
s3
3)
f4 (s4 )]
3
(6
s3
)
0.5(s3 2)
0.5*4 11 3 (6 s3)
s3, s3 [0, 2），x3* 6 s3 8 0.5s3, s3 [2, 6)时，x3*
分配给第二种生产的机器数量。
状态转移方程为 sk1 auk b(sk uk ) 0.7uk 0.9(sk uk ) ； 设 vk 为第 k 阶段的收益，则 vk 9uk 6(sk uk ) ； 令最优值函数 fk (sk ) 表示由机器数量 sk 出发，从第 k 阶段开始到第 4 阶段结束时所获
（3
-
s2）+11
0.5(s2 3) 11
17 s2, (s2 3)
s2 [0,3), x2* 3 12.5 0.5s2, s2
s2 [3,
4],
x2*
0
2
10,,xx22
0 0
k =1 时，
f1 ( s1 )
min (
2 x1 6
g1
(
x1
)
c1
(
x1
)
f2 (s2 ))
min[3
2 x1 6
x1
0.5(x1
2)
f2 (s2 )]
min[3
2 x1 6
x1
0.5(x1
2)
f2 (x1
2)]
min
2 x1 6
2 2
1.5x1 1.5x1
17 12.5
(x1 2) 21 0.5(x1 2)
0.5x1, x1 [2,5) 15.5 x1, x1 [5,
ck
(
xk
)
0, sk 0.（5 sk
xk
xk
dk 0时 dk），否则
k =4 时，
1 / 72
圣才电子书 十万种考研考证电子书、题库视频学习平台
f4 (s4 )
min (
4s4 x4 4
g4
(
x4
)
c4 (x4 ))
3 x4, 0, s4
s4 [0, 4)时，x4* 4时，x4* 0
因 f4 是 u4 的线性单调增函数，故得最优解 u4 s4 ，相应的 f4 (s4 ) 9s4 。 （2） k=3 时，
f3(s3) max9u3 6(s3 u3) f4 [0.7u3 0.9(s3 u3)] max3u3 6s3 9(0.9s3 0.2u3) max14.1
f1(s1) max9u1 6(s1 u1) f2 [0.7u1 0.9(s1 u1)] max3u1 6s1 19.77(0.9s1 0.2u1) max23.793s` 0
3 / 72
圣才电子书 十万种考研考证电子书、题库视频学习平台
当 u1 0 ，相应的有 f1(s1) 23.793s1 。 因 s1=1000 ，所以 f1(s1)=23793 （千元）。
，
f5 (s5 )
0
表示在 k
月初存货量是 sk 时从第 k 个月开始至第 4 个月的最优指标函数。 gk (xk ) 表示第 k 个月生产
xk 个产品时所需要的生产费用，
g
k
(
xk
)
30， xxkk
0 , xk =1,2,3,4,5,6
ck (xk ) 表示第 k 个月生产 xk 个产品时，剩余产品所需要的存储费用，
,x4* =0 0
0.5* 4 2, s3 6时，x3* 0,x4* 0
3
1, x3 0 0, x3 0
k =2 时，
f2 (s2 )
min (
3s2 x2 6
g
2
(
x2
)
c2
(
x2
)
f3 (s3 ))
3ms2ixn26[（2 3
x2） 0.5(x2
s2
3)
f3 (s3 )]
3
6]
20.5, x1* 5
所以 x1* 5, x2* 0, x3* 6, x4* 0 为最优生产计划。
2．某工厂有 1000 台机器，拟分四个阶段使用。已知在每个阶段有两种生产任务，进 行第一种生产时每台机器可收益 9 千元，其机器报废率为 0.3，而进行第二种生产时每台机 器可收益 6 千元，其机器报废率为 0.1。问怎样分配机器，使收益最大？（要求写出动态规
2 / 72
圣才电子书 十万种考研考证电子书、题库视频学习平台
划模型的基本要素并求解）[北京交通大学 2008 研]
解：将此题看成一个 4 个阶段决策问题。令 sk 为状态变量，它表示第 k 阶段初拥有的 完好机器数量，决策变量 uk 为第 k 阶段分配给第一种生产的机器数量，于是 sk -uk 为该阶段
得的收益最大值，故有递推关系式：
fk (sk ) max9uk 6(sk uk ) fk1[0.7uk 0.9(sk uk )]
f5 (s5 ) 0 （1） k=4 时，
s4 0.9s3 0.2u3
f4 (s4 ) max 9u4 6(s4 u4) max3u4 6s4
圣才电子书 十万种考研考证电子书、题库视频学习平台
第 10 章 动态规划应用举例
一、计算题
1．某公司生产并销售某产品。根据市场预测，今后四个月的市场需求量如表 10-1 所
示。已知生产一件产品的成本是 1 千元，每批产品的生产准备成本是 3 千元，每月仅能生
产一批，每批 6 件。每件存储成本为 0.5 千元，且第一个月初无存货，第四个月末的存货要
故得最优解 u3 s3 ，相应的有 f3(s3) 15.3s3 。 （3） k=2 时，
f2(s2) max9u2 6(s2 u2) f3 [0.7u2 0.9(s2 u2)] max3u2 6s2 15.3(0.9s2 0.2u2) max19.77s2
当 u2 0 ，相应的有 f2 (s2 ) 19.77s2 。 （4） k =1时，