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

第二期（2003年8月） 韶关学院学生数学建模论文集 No.2生产与存储的动态规划模型陈立云[摘要]：本文讨论了关于生产与存储的问题，这是一个多阶段决策的生产问题，就此可建立一个动态规划的数学模型．利用运筹学和计算机的数学软件等相关知识，应用动态规划方法解决了这一问题，达到生产、需求与库存之间的平衡，以及在资源限制条件下的最优化的生产方案．并建立混合整数规划模型用LINDON数学软件进行检验.关键词：数学模型；动态规划；状态变量；最优指标函数1 问题的提出设某工厂调查研究了解市场情况，估计在今后四个时期市场对产品的需求量，如表所示：时期1234需求量2324假定不论在任何时期，生产每批产品的固定成本费为3（千元），若不生产，则为0，每单位生产成本费为1（千元）.同时任何一个时期生产能力所允许的最大生产批量不超过6个单位.又设每时期的每个单位产品库存费为0.5（千元），同时规定在第一期期初及第四期期末均无产品库存.试问：该工厂如何安排各个时期的生产与库存，使所花的总成本费用最低？2 符号说明与问题重述生产过程划分为四个阶段，阶段变量 即：状态变量 表示第k阶段末的库存量，由已知得 决策变量 表示第k阶段的生产量， 表示第 k 阶段的需求量.状态转移方程： ， 阶段指标函数 表示第 k阶段的总成本，它由两部分构成，一部分是第 k阶段的生产成本 ，另一部分是第 k 阶段的存贮费 .最优指标函数已知时段k某产品的需求量为 (k=1,2,……K)，任一时段若生产该产品，需付出生产准备费 ，且生产每单位产品的生产成本为 n，若满足本时段需求后有剩余，每时段每单位产品需付出存贮费.设每时段最大生产能力为 ，最大存贮量为，且第1时段初有库存量 ，试制订产品的生产计划，即每时段的产量，使 K个时段的总费用最小.为了通过具体的计算说明解决这问题的方法，现设，千元，n=1千元/单位，千元/单位.时期.，单位，没有给出，视为存贮量不受限制.3 模型的建立3.1 建立模型Ⅰ在提出生产与存贮问题时，忽略生产准备费用，首先考虑到生产、需求与库存之间存在着的平衡关系，这是一个一般的线性规划问题，可假设生产量为，，，，由于存贮费用取决于库存量，则记第一、二、三时期末的库存量为，，，由此可以用生产成本与存贮费之和（记作Z）作为问题为目标函数，在已知的第一期期初及第四期期末均无产品库存，得到一个简单的线性规模型： 此模型可用单纯形法求解，或用数学软件Maple求解,也可将上模型输入LINDON求解，就可得到最优解（略）.注意：这是在忽略生产准备费用时的最优解.3.2 建立模型Ⅱ以上用混合整数规划求解过多阶段生产计划，实际上，这是一类典型的动态优化问题，与用变分法建立连续动态优化模型不同的是，多阶段生产计划属于离散动态优化问题，动态规划模型是解决这类问题的有效方法.本文先讨论确定需求下的最优生产计划，并将它转化为典型的动态优化模型——最短路问题，然后研究随机需求下如何求解最优生产计划.由上述数据、假设，可建立一个动态规划的数学模型.由题可知：所以：基本方程为： 4 模型Ⅱ的求解动态规划的寻优方向一般有用逆序算法（反向递归）或顺序算法（正向递归）进行求解.当问题的第一阶段初和第三阶段末的状态方程均已知时，即，可采用两种方法求解.下面用顺序算法求解：为了简化这个多阶段生产计划问题，可以将它从前向后地分解为一个个单时段问题.（1）首先看第一个时期，为使4个时期的总费用最小，对于第一时期期初的存贮量，则可由状态转移方程：，考虑到，在最大生产能力为 与第一时期的需求量出发，则可能存在的的5种情况：当时，有这时状态集合为：下面就各状态分别计算：， 所以 ， 所以 ， 所以，同理可得： ，所以，，所以（2）当时，由 其中由：，而状态集合是： 下面就各状态分别计算： 所以，所以，同理可得：，所以 ，所以注意：在计算和时，需要用到和，由于每个时期的最大生产批量为6单位，故和没有意义的，就取，其余类推.（3）当时，由：,其中，而状态集合为：下面就各状态分别计算：，所以；，所以或3；，所以，所以，所以（4）当时，因为要求第4时期期末的库存量为0，即为，故有：所以有.再回代求最优策略：由，得：，所以有，，所以有，，所以故最优生产策略为：，，，而相应的全个生产过程中的4个时期的最小总成本是：20.5千元.5 模型的检验这时我们可以建立一个混合整数规划模型来检验动态规划方法的结果正确性：建立模型Ⅲ：与模型Ⅰ比较，除了考虑随产品数量变化的费用（生产成本和存贮费用）外，还要考虑与生产数量无关的费用，即生产准备费用，只要某个时期开工生产时就需要有的这项费用，引入了变量，当时表示不生产，当生产.（） 这一模型也可将数据输入LINDON求解（代码附后），就可得到：最优目标函数为：20.5各变量值为：w1=1 w2=0 w3=1 w4=0 x1=5 x2=0 x3=6 x4=0s1=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.卡斯梯编（陈伟基等译）.动态规划原理.北京：清华大学出版社.1984Produce with saving of development programming modelCHEN Li-yun00Grade,Department of Mathematics,Shaoguan University,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 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.5s3int w1;int w2;int w3;int w4运行结果：OBJECTIVE FUNCTION VALUE 1) 20.50000 VARIABLE VALUE REDUCED COST W1 1.000000 3.000000 W2 0.000000 0.000000 W3 1.000000 3.000000 W4 0.000000 0.000000 X1 5.000000 0.000000 X2 0.000000 0.000000 X3 6.000000 0.000000 X4 0.000000 0.000000 S1 3.000000 0.000000 S2 0.000000 0.000000 S3 4.000000 0.000000s.t. x1-s1=2 x2+s1-s2=3 x3+s2-s3=2 x4+s3=4 x1-6w1<=0 x2-6w2<=0 x3-6w3<=0 x4-6w4<=0 x1>=0 x2>=0 x3>=0 x4>=0 s1>=0 s2>=0 s3>=0 end 26 。