1、21 生产与存储的动态规划模型摘要：本文讨论了关于生产与存储的问题，这是一个多阶段决策的生产问题，就此可建立一个动态规划的数学模型利用运筹学和计算机的数学软件等相关知识，应用动态规划方法解决了这一问题，达到生产、需求与库存之间的平衡，以及在资源限制条件下的最优化的生产方案并建立混合整数规划模型用LINDON 数学软件进行检验.关键词：数学模型；动态规划；状态变量；最优指标函数1 问题的提出设某工厂调查研究了解市场情况，估计在今后四个时期市场对产品的需求量，如表所示：时期 1 2 3 4需求量 2 3 2 4假定不论在任何时期，生产每批产品的固定成本费为 3（千元） ，若不生产，则为 0，每单位
2、生产成本费为 1（千元）.同时任何一个时期生产能力所允许的最大生产批量不超过6 个单位.又设每时期的每个单位产品库存费为 0.5（千元） ，同时规定在第一期期初及第四期期末均无产品库存.试问：该工厂如何安排各个时期的生产与库存，使所花的总成本费用最低？2 符号说明与问题重述生产过程划分为四个阶段，阶段变量 即：.4,321k状态变量 表示第 k 阶段末的库存量，由已知得 ks 040s决策变量 表示第 k 阶段的生产量， 表示第 k 阶段的需求量.xd状态转移方程： ， kkxs1阶段指标函数 表示第 k 阶段的总成本，它由两部分构成，一部分是第 k),(v阶段的生产成本 ，另一部分是第 k
3、阶段的存贮费 .最优指标函数xc )(ksh)(ksf已知时段 k 某产品的需求量为 (k=1,2,K)，任一时段若生产该产品，需付出生kd产准备费 ，且生产每单位产品的生产成本为 n，若满足本时段需求后有剩余，每时段0c每单位产品需付出存贮费 .设每时段最大生产能力为 ，最大存贮量为 ，且第 10hmXmI时段初有库存量 ，试制订产品的生产计划，即每时段的产量，使 K 个时段的总费用最s小.为了通过具体的计算说明解决这问题的方法，现设 ，4k,21d,3,2d千元，n=1 千元/单位， 千元/单位 .时期. ， 单位，,43d0c 5.0h0s6mX22 没有给出，视为存贮量不受限制.mI3
4、 模型的建立3.1 建立模型在提出生产与存贮问题时，忽略生产准备费用，首先考虑到生产、需求与库存之间存在着的平衡关系，这是一个一般的线性规划问题，可假设生产量为 ， ， ， ，由1x234x于存贮费用取决于库存量，则记第一、二、三时期末的库存量为 ， ， ，由此可以用s生产成本与存贮费之和（记作 Z）作为问题为目标函数，在已知的第一期期初及第四期期末均无产品库存 ，得到一个简单的线性规模型：040s41415.0kksxzMin.ts0.,.64233141231sxs此模型可用单纯形法求解，或用数学软件 Maple 求解,也可将上模型输入 LINDON 求解，就可得到最优解（略）.注意：这是
5、在忽略生产准备费用时的最优解.3.2 建立模型以上用混合整数规划求解过多阶段生产计划，实际上，这是一类典型的动态优化问题，与用变分法建立连续动态优化模型不同的是，多阶段生产计划属于离散动态优化问题，动态规划模型是解决这类问题的有效方法.本文先讨论确定需求下的最优生产计划，并将它转化为典型的动态优化模型最短路问题，然后研究随机需求下如何求解最优生产计划.由上述数据、假设，可建立一个动态规划的数学模型.由题可知： 6.,.321,30.0)(kkkkxxcksh50)(所以： )(,kkhxcsv基本方程为： 6,min,0)( )4,321,.),(i 1kkxk dssf f而4 模型的求解动
6、态规划的寻优方向一般有用逆序算法（反向递归）或顺序算法（正向递归）进行求解.当问题的第一阶段初和第三阶段末的状态方程均已知时，即 ，可采用两种040s23 方法求解.下面用顺序算法求解：为了简化这个多阶段生产计划问题，可以将它从前向后地分解为一个个单时段问题.（1）首先看第一个时期，为使 4 个时期的总费用最小，对于第一时期期初的存贮量，则可由状态转移方程： ，考虑到 ，在最大生产能力为 0s kkdxs1 1s与第一时期的需求量 出发，则可能存在的 的 5 种情况：6mX2d当 时，有1k.)()(min)(1111shxcsfx这时状态集合为： .4,3210,269in| ,;| 141
7、1为 整 数且 为 整 数且ssdsk下面就各状态分别计算：， 所以 50.)(min)(1211 hcfx 21x， 所以.61331 3， 所以 ，82.4)(4i)(11 cfx 41x同理可得： ，所以 ，5.93x，所以)4(1f61（2）当 时，由 k)()(min) 22122022 xdsfhxcsfx 其中由： ，6,in22ds而状态集合是： .3,210,36in| ,;| 242为 整 数且 为 整 数且ssdk下面就各状态分别计算：5.96.84.0min)(0)3(1221)3()(mini)0( 212232 fhcfxfhxcfx24 所以 ，02x5.15.7
8、.68.945.0min)0()()4(1322)3()()1(40min)()()(i)1(2212224 fhcffhcxxfx所以 ，同理可得：02x，所以14)()()(in)( 212250 xfxcfx 52x，所以.563m3622 h 6注意：在计算 和 时，需要用到 和 ，由于每个时期的最大生产批量)(ff )5(1f1f为 6 单位，故 和 没有意义的，就取 ，其余类推.511 )6(（3）当 时，由：k,3323303 ()(min)(3 xdsfhxcsfx 其中 ，而状态集合为：6,2min33s4,310,6,in| 34为 整 数且 sds下面就各状态分别计算：，
9、所以 ；14)2()()(in)0( 33323 xfhxcfx 03x，所以 或 3；61m103 ，所以5.7)4()()(i)( 323433 xfcfx 4x，所以195n503 h3，所以.20)6()()(i)( 323633 xfcfx 6x（4）当 时，因为要求第 4 时期期末的库存量为 0，即为 ，故有：k 4s25 5.201476.59.0min)0()4(132)()(40min)()()(i)0(4343444 fcffcxfhxfx所以有 .04x再回代求最优策略：由 ， 得：4x4s，所以有 ，3ds63x，所以有 ，0232x02，所以21s51x故最优生产策略
10、为：， ， ，51x026304而相应的全个生产过程中的 4 个时期的最小总成本是：20.5 千元.5 模型的检验这时我们可以建立一个混合整数规划模型来检验动态规划方法的结果正确性：建立模型：与模型比较，除了考虑随产品数量变化的费用（生产成本和存贮费用）外，还要考虑与生产数量无关的费用，即生产准备费用 ，只要某个时期开工生产时就需要有kT的这项费用，引入了 变量 ，当 时表示不生产，当 生产.10kw0k 1kw（ ）)(41hkkksxcTzMin5.0,30kkhc.ts 4,21,.dsxk)4,321,.(0, 6.,0,.4ksxXwkmmkk在 此这一模型也可将数据输入 LINDO
11、N 求解（代码附后） ，就可得到：最优目标函数为：20.5各变量值为：w1=1 w2=0 w3=1 w4=0 x1=5 x2=0 x3=6 x4=026 int w1;int w2;int w3;int w4运行结果：OBJECTIVE FUNCTION VALUE1) 20.50000VARIABLE VALUE REDUCED COSTW1 1.000000 3.000000W2 0.000000 0.000000W3 1.000000 3.000000W4 0.000000 0.000000X1 5.000000 0.000000X2 0.000000 0.000000X3 6.0000
12、00 0.000000X4 0.000000 0.000000S1 3.000000 0.000000S2 0.000000 0.000000S3 4.000000 0.000000s1=3 s2=0 s3=4由此可验证动态规划方法的正确性.参考文献：1叶其孝.大学生数学建模竞赛辅导教材.长沙：湖北教育出版社.19932刘来福、曾文艺.数学模型与数学建模.北京：北京师范大学出版社.19973姜启源等编.数学模型（第三版）.北京：高等教育出版社.20034胡知能.徐玖平编著.运筹学线性系统优化.北京：科学出版社.20035卢开澄.编著.单目标、多目标与整数规划.北京：清华大学出版社.19996黄
13、桐城、鲍祥霖编.数学规划与对策论.上海：上海交通大学出版社.20027刘满凤、傅波、聂高辉编.运筹学模型与方法教程例题分析与题解.北京：清华大学出版社.20008魏权龄、王日爽、徐兵等编.数学规划与优化设计.北京：国防工业出版社.19849张有为编.动态规划.长沙：湖南科学技术出版社.199110罗伯特.E.拉森、约翰 .L.卡斯梯编（陈伟基等译） .动态规划原理.北京：清华大学出版社.1984Produce with saving of development programming model00Grade,Department of Mathematics,Shaoguan Univer
14、sity,Shaoguan 512005,Guangdong ,ChinaAbstract： 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
15、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
16、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.5s3s.t. x1-s1=2x2+s1-s2=3x3+s2-s3=2x4+s3=4x1-6w1=0x2=0x3=0x4=0s1=0s2=0s3=0 end
