动态规划法求解生产与存储问题 下载本文

条件下,决定各个生产阶段的产量,使得计划期内的费用之和最小。

现设有一个生产部门,生产计划周期为n个阶段,已知最初库存量为x1,阶段需求量为dk,单位产品的消耗费用是lk,单位产品的阶段库存费用为hk,仓库容量为mk,阶段

生产能力为bk,生产固定成本为问如何安排

现阶段的产量,使计划期内的费用综合为最小?

该问题本身就是一个多阶段决策问题,设状态变量为xk为k阶段初的库存量,由于计划期初的库存量x1已知,计划期末的库存量通常也是给定的,为简单起见,假定x(n+1)=0,于是状态变量

xk

的约束条件是:

决策变量uk选为阶段k的产量,它满足的约束条件是:

状态转移方程为的要求。

阶段效用由两阶段组成,一部分为生产费用,另一部分为存贮费用,即:

,它满足无后效性

动态规划基本方程为:

七.设计题目: 某机床厂

根据合同,在一至四月份为客户生产某种机床。工厂每月的生产能力为10台,机床可以库存,存储费用为每台每月0.2万元,每月需要的数量及每台机床的生产成本如下表。试确定每月的生产量,要求既能满足每月的需求,又能使生产成本和存储费用之和达到最小。

表 需求量及生产成本

月份 需求(台) 生产成本(万元/台) 1. 构造动态规划模型

1阶段变量k ○

1 6 7 2 7 7.2 3 12 8 4 6 7.6 把每个月作为一个阶段,k=1,2,3,4

2状态变量○

,可满足无后效性,

选择每个阶段的库存量为状态变量

由已知条件可知:x1=x5=0,单位为台

3决策变量○

,由已知条件得0≤

设每个阶段的生产量为决策变量10台,

4状态转移方程 ○

状态转移方程为:需求量)

5阶段指标○

=+-(是第k阶段的市场

第k阶段的指标费用: (或

,,)=0.2)=0.2

+y(i)

>0)i=1,2,3,4. =0)

+0 (

其中y1=7,y2=7.2,y3=8,y4=7.6,单位为万元 2. 建立基本方程 设最优值函数

是从第k阶段的

状态出发到过程终

结的最小费用,按动态规划方法的逆序解基本方程又:

[

F5(x5)=0 3. 逆序逆推计算

1k=4时 ○

(,)+] (k=4,3,2,1)

按照问题的各种约束条件,确定状态变量x4的取值范围。按穷举法的思路,在量化的精度内,确定状态变量x4的全部可能取值。状态转移方程 x5=x4+u4-d4

又x5=0,d4=6 所以有x4+u4=6

又因为每个月的最大生产能力为10台。第1,2,3月的需求量为6,7,12台,故x4=0,1,2,3,4,4台

2对x4的的确定取值,分别求出决策变量u4的取值范围 ○

当x4=0,u4=6;x4=3,u4=3 x4=1, u4=5; x4=4, u4=2 x4=2, u4=4; x4=5, u4=1

由此可知x4与u4是一一对应的,即对于每个确定的状态,只有一种决策,故这唯一决策的结果是最优的。 利用第四阶段的基本方程进行计算: F4(x4)=min[v4(x4,u4)+f5(x5)] =min[v4(x4,u4)] =v4(x4,u4)

=0.2x4+7.6u4 (u4>0)或=0.2x4 (u4=0)计算结果列表1 表1 k=4时 0 1 2 3 4 5 6 5 4 3 2 1 0 0 0 0 0 0 45.6 38.2 30.8 23.4 16 8.6 0 0 0 0 0 0 +45.6 38.2 30.8 23.4 16 8.6 2k=3时 ○

因为d3=12,d4=6,x1=x5=0,d1=7.每月的最大生产能力为10台,故2≦x3≦7 当x3=2,u3=10 x3=3,u3=10,9 x3=4,u3=10,9,8 x3=5,u3=10,9,8,7 x3=6,u3=10,9,8,7,6 x3=7,u3=10,9,8,7,6,5

状态变量x3的一个取值,对应决策变量u3的六个可能取值,要求分别计算出各个u3取值相应的指标函数值,再挑选其中的最小值为这个状态的最优指标函数值,f3(0). 下面利用第三阶段的基本方程进行计算。 F3(x3)=min【v3(x3,u3)+f4(x4)】

其中v3(x3,u3)=0.2x3+8u3 (u3>0)或v3(x3,u3)=0.2x3 (u3=0)

状态转移方程x4=x3+u3-12 计算结果位于表2 表2表2 k=3时

2 3 10 10 9 0 1 0 80.4 80.6 72.6 45.6 38.2 45.6 +126 118.8 118.2