生产与存储的动态规划模型

生产与存储的动态规划模型

陈立云

[摘要]：本文讨论了关于生产与存储的问题，这是一个多阶段决策的生产问题，就此可建立一个动态规划的数学模型．利用运筹学和计算机的数学软件等相关知识，应用动态规划方法解决了这一问题，达到生产、需求与库存之间的平衡，以及在资源限制条件下的最优化的生产方案．并建立混合整数规划模型用LINDON数学软件进行检验.

关键词：数学模型；动态规划；状态变量；最优指标函数

1 问题的提出

如表所示：

0，每单位生产成本费为1（千元）.同时任何一个时期生产能力所允许的最大生产批量不超过6个单位.又设每时期的每个单位产品库存费为0.5（千元），同时规定在第一期期初及第四期期末均无产品库存.试问：该工厂如何安排各个时期的生产与库存，使所花的总成本费用最低？

2 符号说明与问题重述

生产过程划分为四个阶段，阶段变量k1,2,3,4. 即：

状态变量 sk 表示第k阶段末的库存量，由已知得 s0s40

决策变量 xk 表示第k阶段的生产量，dk 表示第 k 阶段的需求量.

状态转移方程：sk1skxkdk ，

阶段指标函数 vk(sk,xk) 表示第 k阶段的总成本，它由两部分构成，一部分是第 k阶段的生产成本 ck(xk)，另一部分是第 k 阶段的存贮费 hk(sk) .最优指标函数fk(sk)

已知时段k某产品的需求量为 dk(k=1,2,……K)，任一时段若生产该产品，需付出生产准备费 c0 ，且生产每单位产品的生产成本为 n，若满足本时段需求后有剩余，每时段每单位产品需付出存贮费h0.设每时段最大生产能力为 Xm ，最大存贮量为Im，且第1时段初有库存量 s0 ，试制订产品的生产计划，即每时段的产量，使 K个时段的总费用最小.

为了通过具体的计算说明解决这问题的方法，现设k4，d12,d23,d32,d34,c03千元，n=1千元/单位，h00.5千元/单位.时期.s10，Xm6单位，Im没有给出，视为存贮量不受限制.

3 模型的建立

3.1 建立模型Ⅰ

在提出生产与存贮问题时，忽略生产准备费用，首先考虑到生产、需求与库存之间存在着的平衡关系，这是一个一般的线性规划问题，可假设生产量为x1，x2，x3，x4，由于存贮费用取决于库存量，则记第一、二、三时期末的库存量为s1，s2，s3，由此可以用生产成本与存贮费之和（记作Z）作为问题为目标函数，在已知的第一期期初及第四期期末均无产品库存s0s40，得到一个简单的线性规模型：

Minzxk0.5sk

k1k144

x1s12

x2s1s23

x3s2s32

x4s34

x1.....x46

x1.....x4,s1...s30

此模型可用单纯形法求解，或用数学软件Maple求解,也可将上模型输入LINDON求解，就可得到最优解（略）.注意：这是在忽略生产准备费用时的最优解.

3.2 建立模型Ⅱ

以上用混合整数规划求解过多阶段生产计划，实际上，这是一类典型的动态优化问题，与用变分法建立连续动态优化模型不同的是，多阶段生产计划属于离散动态优化问题，动态规划模型是解决这类问题的有效方法.本文先讨论确定需求下的最优生产计划，并将它转化为典型的动态优化模型——最短路问题，然后研究随机需求下如何求解最优生产计划.由上述数据、假设，可建立一个动态规划的数学模型. s.t.

......xk00,.........xk1,2,3,....6 由题可知：ck(xk)3xk,........

................xk6

hk(sk)0.5sk

所以：vk(sk,xk)ck(xk)hk(sk)

minvk(sk,xk)fk1(sk1),..(k1,2,3,4)fk(sk)0xkk基本方程为：  f0(s0)0,而kminskdk,6

4 模型Ⅱ的求解

动态规划的寻优方向一般有用逆序算法（反向递归）或顺序算法（正向递归）进行求解.当问题的第一阶段初和第三阶段末的状态方程均已知时，即s0s40，可采用两种方法求解.下面用顺序算法求解：

为了简化这个多阶段生产计划问题，可以将它从前向后地分解为一个个单时段问题.

（1）首先看第一个时期，为使4个时期的总费用最小，对于第一时期期初的存贮量s00，则可由状态转移方程：sk1skxkdk，考虑到s1，在最大生产能力为 Xm6与第一时期的需求量d12出发，则可能存在的s1的5种情况：

当k1时，有f(s1)minxc1(x1)h1(s1).

11

这时状态集合为：

ss0s4为整数

11|1mindk;6d1,且s1

k2



s1|0s1min9,62,且s1为整数

0,1,2,3,4.

下面就各状态分别计算：

f1(0)minxc1(2)h1(0)3120.505， 所以x12

12

f1(1)minxc1(3)h1(1)3130.516.5， 所以x

1313

f1(2)minx4c1(4)h1(2)3140.528 ， 所以x14，

1

同理可得： f1(3)9.5，所以x15，

f1(4)11，所以x16

（2）当k2时，由

f2(s2)minc2(x2)h2(s2)f1(s1)

0x22

0minxc2(x2)h2(s2)f1(s2d2x

2)

22

其中由：2mins2d2,6，

s4

s

22|0s2mindk;6d2,且s2为整数

k3

而状态集合是： s2|0s2min6,63,且s2为整数

0,1,2,3.

下面就各状态分别计算：

f2(0)0minxc2(x2)h2(0)f1(3x2)

23

c2(0)h2(0)f1(3)09.5

minc(1)h(0)f(2)

21

c2(2)h2(0)f1(1)min482

9.5

56.5

c2(3)h2(0)f1(0)

65

所以x20，

f2(1)minc2(x2)h2(1)f1(4x2)0x24

c2(0)h2(1)f1(4)0.511c(1)h(1)f(3)4.59.5221 minc2(2)h2(1)f1(2)min5.5811.5

c(3)h(1)f(1)6.56.52217.55c2(4)h2(0)f1(0)

所以x20，同理可得：

f2(2)minc2(x2)h2(2)f1(5x2)14，所以x25 0x25

f2(3)minc2(x2)h2(3)f1(6x2)15.5 ，所以x26 0x26

注意：在计算f2(2)和f2(3)时，需要用到f1(5)和f1(6)，由于每个时期的最大生产批量为6单位，故f1(5)和f1(6)没有意义的，就取f1(5)f1(6)，其余类推.

（3）当k3时，由：

f3(s3)minc3(x3)h3(s3)f2(s3d3x3, 0x33

其中3mins32,6，而状态集合为：

s3s3|0s3mind4,6d3,且s3为整数

0,1,2,3,4

下面就各状态分别计算：

f3(0)minc3(x3)h3(0)f2(2x3)14，所以x30； 0x32

f3(1)minc3(x3)h3(1)f2(3x3)16，所以x30或3； 0x33

f3(2)minc3(x3)h3(2)f2(4x3)17.5，所以x34 0x34

f3(3)minc3(x3)h3(3)f2(5x3)19，所以x35 0x35

f3(4)minc3(x3)h3(4)f2(6x3)20.5，所以x36 0x36

（4）当k4时，因为要求第4时期期末的库存量为0，即为s40，故有：

f4(0)minc4(x4)h4(0)f3(4x4)0x44

c4(0)f3(4)020.5c(1)f(3)41943 minc4(2)f3(2)min517.520.5

c(3)f(1)61643714c4(4)f3(0)

所以有x40.

再回代求最优策略：由x40，s40得：

s3s4d4x44，所以有x36，

s2s3d3x34260，所以有x20，

s1s2d2x23，所以x15

故最优生产策略为：

x15，x20，x30 6，x4

而相应的全个生产过程中的4个时期的最小总成本是：20.5千元.

5 模型的检验

这时我们可以建立一个混合整数规划模型来检验动态规划方法的结果正确性：

建立模型Ⅲ：与模型Ⅰ比较，除了考虑随产品数量变化的费用（生产成本和存贮费用）外，还要考虑与生产数量无关的费用，即生产准备费用Tk，只要某个时期开工生产时就需要有的这项费用，引入了01变量wk，当wk0时表示不生产，当wk1生产.

Minz(Tkwkckxkhk(sh))（Tkc03,hk0.5）

k14

k1,2,3,4) s.t. sk1xkskdk,......(

1,.....xk0wk0,....xk0

xkXm,..........(在此Xm6)

s0s40

xk,sk0,..(k1,2,3,4)

这一模型也可将数据输入LINDON求解（代码附后），就可得到：

最优目标函数为：20.5

各变量值为：

w1=1 w2=0 w3=1 w4=0 x1=5 x2=0 x3=6 x4=0

s1=3 s2=0 s3=4

由此可验证动态规划方法的正确性.

参考文献：

[1]叶其孝.大学生数学建模竞赛辅导教材.长沙：湖北教育出版社.1993

[2]刘来福、曾文艺.数学模型与数学建模.北京：北京师范大学出版社.1997

[3]姜启源等编.数学模型（第三版）.北京：高等教育出版社.2003

[4]胡知能.徐玖平编著.运筹学线性系统优化.北京：科学出版社.2003

[5]卢开澄.编著.单目标、多目标与整数规划.北京：清华大学出版社.1999

[6]黄桐城、鲍祥霖编.数学规划与对策论.上海：上海交通大学出版社.2002

[7]刘满凤、傅波、聂高辉编.运筹学模型与方法教程例题分析与题解.北京：清华大学出版社.2000

[8]魏权龄、王日爽、徐兵等编.数学规划与优化设计.北京：国防工业出版社.1984

[9]张有为编.动态规划.长沙：湖南科学技术出版社.1991

[10]罗伯特.E.拉森、约翰.L.卡斯梯编（陈伟基等译）.动态规划原理.北京：清华大学出版社.1984

Produce with saving of development programming model

CHEN Li-yun

00Grade,Department of Mathematics,Shaoguan University,Shaoguan 512005,Guangdong ,China Abstract： This text discussed concerning produce with the saving problem, this is mathematics model that a many production problems that the stage make policy, can establish now a development programming. make use of the strategy learn with the related knowledge in etc. in software in mathematics of the calculator, applying the development programming method resolved this problem, attaining the production, need and equilibrium of the stock, and limit the superior the production project that turn that term descend in the resources. Establishing the integral of admixture programs, examining this model use LINDON mathematics software .

Key words：Mathematics model; The development programs； the appearance changes the deal；superior index sign function

用LINDON计算混合整数规划模型Ⅲ，代码：

min 3w1+3w2+3w3+3w4+x1+x2+x3+x4+0.5s1+0.5s2+0.5s3

s.t.

x1-s1=2

x2+s1-s2=3

x3+s2-s3=2

x4+s3=4

x1-6w1

x2-6w2

x3-6w3

x4-6w4

x1>=0

x2>=0

x3>=0

x4>=0

s1>=0

s2>=0

s3>=0

end