多阶段决策问题的案例分析

多阶段决策过程是指对于特殊的活动过程,可以按时间或空间顺序分解成若干相互联系的阶段,在每个阶段都要做出决策,全部过程的决策是一个决策序列,所以多阶段决策问题也称为序贯决策问题。在多阶段决策过程的每一阶段,都有多种可供选择的方案,从中选取一种方案,一旦各个阶段的决策选定之后,就构成了解决这一问题的一个决策序列。

(1)最短路径问题。

动态规划问题中的最短路径问题与网络分析中的提法相同,即从一个地方到另一个地方有很多条路径,从中找到一条距离最短的路径。

【例8-1】供应商A要运输一批货物到F公司,两公司中间有一个运输网络,路线中间的结点表示要经过的港口或城市,如图8-1所示,路线上的数字表示两地间的距离,试求一条运输路径,使所走距离最短。

图8-1

(2)资源分配问题。

只有一种资源有待于分配到若干个活动,其目标是如何最有效地在各个活动中分配这种资源。一般来说,阶段对应于活动,每个阶段的决策对应于分配到该活动的资源数量;任何状态的当前状态总是等于当前阶段和以后阶段分配的资源数量,即总资源量减去前面各阶段已分配的资源量。本章导入案例属于资源分配问题。

【例8-2】某公司有5台设备,分配给所属甲、乙、丙三个工厂。各工厂获得不同的设备台数所能产生的效益(万元)情况如表8-1所示。求最优分配方案,使总效益最大。

表8-1

(3)投资决策问题。

某公司现有一定的资金,考虑给若干个项目投资,这些项目的投资期限、回报率均不相同,因此需要确定这些项目的投资额,以获得最大的总利润。

【例8-3】某投资者有40万元,面临三种不同的投资机会,投资额为x1,x2,x3。经预测,三项投资可获得的效益分别为问如何分配投资额,才能获得最大收益?

(4)生产与存储问题。

某工厂每月需供应市场一定数量的产品,剩余产品应存入仓库。一般地说,某月适当增加产量可降低生产成本,但超产部分存入仓库会增加库存费用,因此要确定一个每月的生产计划,在满足需求的条件下,使一年的生产与存储费用之和最小。(www.xing528.com)

【例8-4】某企业拟与客户签订未来4个月的交货合同,如表8-2所示。该企业的生产能力为每月4千件,其仓库的最大存货能力为3千件。据以往数据统计,单位生产成本cv＝5 000元/千件,生产的固定运营费用F＝4 000元,每月仓库保管费用H＝300元/千件。

表8-2

假设企业现有存货3千件,未来第4个月月底计划存货2千件,问应在每月各生产多少产品,才能既满足交货合同,又使总费用最小?

(5)背包问题(装载问题)。

背包问题的一般提法是,一个徒步者携包旅行,共有n种物品供他选择后装入背包中,n种物品的编号为1,2,…,n。已知每单位第j种物品的重量为aj,单位j物品使用价值为cj,且该旅行者所能承受的总重量不超过a,为此旅行者需要考虑选择携带这n种物品的数量,以便获得最大的使用价值。

【例8-5】已知某背包问题的数据如表8-3所示,最大限制重量为5,问如何携带,才能使总价值最大?

表8-3

背包问题在实际生产经营过程中,经常用于解决装载问题。

【例8-6】有一辆货车载重量为10吨,用来装载货物A,B时成本分别为5元/吨和4元/吨。现在已知每吨货物的运价与该货物的重量有如下线性关系:A:P1＝15－x1;B:P2＝18－2x2,其中x1,x2分别为货物A,B的重量。如果要求满载,问货物A和B各装载多少,才能使总利润最大?

(6)机器完好率问题。

某种机器设备若干台,用于完成不同的工作。若第k年年初完好机器的数量为sk,其中xk用于完成一种工作,余下的sk－xk用于完成另一种工作,则该年的预期收入为g(xk)＋h(sk－xk)。假设机器在使用过程会发生损坏,若机器用于完成一种工作时,一年后能继续使用的完好机器数占年投入量的某个比例;用于完成另一种工作时,为另一个比例。已知g(x)和h(x),问在接下来的几年内如何分配每年用于完成不同工作的机器数,才能获得最大总收益?

【例8-7】某种机器设备s0＝100台,用于完成工作A和B。若第k年年初完好机器的数量为sk,其中xk用于完成工作A,余下的sk－xk用于完成工作B,则该年的预期收入为g(xk)＋h(sk－xk)。机器在使用过程会发生损坏,经测算,该机器用于完成工作A时,一年后能继续使用的完好机器数占年投入量的三分之二;用于完成工作B时,该比例为十分之九。又知g(x)＝10x(万元),h(x)＝7x(万元),问在三年内如何分配每年用于完成工作A和B的机器数,才能使总收益最大?

如上所述,动态规划可以用于解决最短路径问题、资源分配问题、生产存储问题、投资问题、装载问题、设备完备率问题等,由于动态规划模型结构不一、解法不一,因此需要根据模型结构灵活处理;与此同时,涉及的变量不能太多,否则计算量太大。