《【数学与应用数学】论文——生产与存储的动态规划模型》由会员分享,可在线阅读,更多相关《【数学与应用数学】论文——生产与存储的动态规划模型(6页珍藏版)》请在金锄头文库上搜索。
1、21 生产与存储的动态规划模型生产与存储的动态规划模型 摘要摘要 :本文讨论了关于生产与存储的问题,这是一个多阶段决策的生产问题,就此可建立一个动态规划的数学模型利用运筹学和计算机的数学软件等相关知识,应用动态规划方法解决了这一问题,达到生产、需求与库存之间的平衡,以及在资源限制条件下的最优化的生产方案并建立混合整数规划模型用LINDON 数学软件进行检验.关键词关键词:数学模型;动态规划;状态变量;最优指标函数1 1 问题的提出问题的提出 设某工厂调查研究了解市场情况,估计在今后四个时期市场对产品的需求量,如表所 示:时期1234 需求量2324 假定不论在任何时期,生产每批产品的固定成本费
2、为 3(千元) ,若不生产,则为 0, 每单位生产成本费为 1(千元).同时任何一个时期生产能力所允许的最大生产批量不超过 6 个单位.又设每时期的每个单位产品库存费为 0.5(千元) ,同时规定在第一期期初及第四 期期末均无产品库存.试问:该工厂如何安排各个时期的生产与库存,使所花的总成本费用 最低? 2 2 符号说明与问题重述符号说明与问题重述生产过程划分为四个阶段,阶段变量 即:. 4 , 3 , 2 , 1k状态变量 表示第 k 阶段末的库存量,由已知得 ks040 ss决策变量 表示第 k 阶段的生产量, 表示第 k 阶段的需求量.kxkd状态转移方程: , kkkkdxss1阶段指
3、标函数 表示第 k 阶段的总成本,它由两部分构成,一部分是第 k),(kkkxsv阶段的生产成本 ,另一部分是第 k 阶段的存贮费 .最优指标函数)(kkxc)(kksh)(kksf已知时段 k 某产品的需求量为 (k=1,2,K),任一时段若生产该产品,需付出生kd产准备费 ,且生产每单位产品的生产成本为 n,若满足本时段需求后有剩余,每时段0c每单位产品需付出存贮费.设每时段最大生产能力为 ,最大存贮量为,且第 10hmXmI时段初有库存量 ,试制订产品的生产计划,即每时段的产量,使 K 个时段的总费用最0s小.为了通过具体的计算说明解决这问题的方法,现设,4k, 21d, 32d, 23
4、d千元,n=1 千元/单位,千元/单位.时期.,单位,, 43d30c5 . 00h01s6mX22 没有给出,视为存贮量不受限制.mI3 3 模型的建立模型的建立 3.13.1 建立模型建立模型 在提出生产与存贮问题时,忽略生产准备费用,首先考虑到生产、需求与库存之间存在着的平衡关系,这是一个一般的线性规划问题,可假设生产量为,由1x2x3x4x于存贮费用取决于库存量,则记第一、二、三时期末的库存量为,由此可以用1s2s3s生产成本与存贮费之和(记作 Z)作为问题为目标函数,在已知的第一期期初及第四期期末均无产品库存,得到一个简单的线性规模型:040 ss 41415 . 0kk kksxz
5、Min. .ts0.,.6.42323141413432321211ssxxxxsxssxssxsx此模型可用单纯形法求解,或用数学软件 Maple 求解,也可将上模型输入 LINDON 求解, 就可得到最优解(略).注意:这是在忽略生产准备费用时的最优解. 3.23.2 建立模型建立模型 以上用混合整数规划求解过多阶段生产计划,实际上,这是一类典型的动态优化问题, 与用变分法建立连续动态优化模型不同的是,多阶段生产计划属于离散动态优化问题,动 态规划模型是解决这类问题的有效方法.本文先讨论确定需求下的最优生产计划,并将它转 化为典型的动态优化模型最短路问题,然后研究随机需求下如何求解最优生产
6、计划.由 上述数据、假设,可建立一个动态规划的数学模型.由题可知: 66,3 , 2 , 1,30,.0)(kkkkkk xxxxxckkkssh5 . 0)(所以:)()(),(kkkkkkkshxcxsv基本方程为: 6 ,min, 0)()4 , 3 , 2 , 1,()(),(min)(00110kkkkkkkkxkkdssfksfxsvsfkk 而4 4 模型模型的求解的求解 动态规划的寻优方向一般有用逆序算法(反向递归)或顺序算法(正向递归)进行求解.当问题的第一阶段初和第三阶段末的状态方程均已知时,即,可采用两种040 ss23 方法求解.下面用顺序算法求解: 为了简化这个多阶段
7、生产计划问题,可以将它从前向后地分解为一个个单时段问题. (1)首先看第一个时期,为使 4 个时期的总费用最小,对于第一时期期初的存贮量,则可由状态转移方程:,考虑到,在最大生产能力为 00skkkkdxss11s与第一时期的需求量出发,则可能存在的的 5 种情况:6mX21d1s当时,有1k.)()(min)(11111 11shxcsf x 这时状态集合为: .4 , 3 , 2 , 1 , 0,26 , 9min0|,6 ;min0|1111142111 为整数且为整数且ssssddssskk下面就各状态分别计算:, 所以 505 . 0213)0()2(min)0(1121 1 hcf
8、 x21x, 所以5 . 615 . 0313) 1 ()3(min) 1 (1131 1 hcf x31x, 所以,825 . 0413)2()4(min)2(1141 1 hcf x41x同理可得: ,所以,5 . 9)3(1f51x,所以11)4(1f61x(2)当时,由 2k)()()(min)()()(min)(2221222201122220222222 xdsfshxcsfshxcsfxx 其中由:,6 ,min222ds 而状态集合是: .3 , 2 , 1 , 0,36 , 6min0|,6 ;min0|2222243222 为整数且为整数且ssssddssskk下面就各状态
9、分别计算:5 . 9565 . 65845 . 90min)0()0()3() 1 ()0()2()2()0() 1 ()3()0()0(min)3()0()(min)0(12212212212221222302 2 fhcfhcfhcfhcxfhxcf x24 所以,02x5.1155.75.65.685.55.95.4115.0min)0()0()4()1()1()3()2()1()2()3()1()1()4()1()0(min)4()1()(min)1(12212212212212221222402 2fhcfhcfhcfhcfhcxfhxcfx所以,同理可得:02x,所以14)5()2
10、()(min)2(21222502 2xfhxcfx52x,所以5.15)6()3()(min)3(21222602 2xfhxcfx62x注意:在计算和时,需要用到和,由于每个时期的最大生产批量)2(2f)3(2f)5(1f)6(1f为 6 单位,故和没有意义的,就取,其余类推.)5(1f)6(1f)6()5(11ff(3)当时,由:3k,33323333033()()(min)(33xdsfshxcsf x 其中,而状态集合为:6 , 2min33s 4 , 3 , 2 , 1 , 0,6 ,min0|334333 为整数且sddsss下面就各状态分别计算:,所以;14)2()0()(mi
11、n)0(32333203 3xfhxcfx03x,所以或 3;16)3()1()(min)1(32333303 3xfhxcfx03x,所以5.17)4()2()(min)2(32333403 3xfhxcfx43x,所以19)5()3()(min)3(32333503 3xfhxcfx53x,所以5.20)6()4()(min)4(32333603 3xfhxcfx63x(4)当时,因为要求第 4 时期期末的库存量为 0,即为,故有:4k04s25 5.201471665.1751945.200min)0()4()1()3()2()2()3()1()4()0(min)4()0()(min)0
12、(343434343443444404 4fcfcfcfcfcxfhxcfx所以有.04x再回代求最优策略:由,得:04x04s,所以有,44443xdss63x,所以有,06243332xdss02x,所以32221xdss51x故最优生产策略为:,51x02x63x04x而相应的全个生产过程中的 4 个时期的最小总成本是:20.5 千元. 5 5 模型的检验模型的检验 这时我们可以建立一个混合整数规划模型来检验动态规划方法的结果正确性: 建立模型建立模型:与模型比较,除了考虑随产品数量变化的费用(生产成本和存贮费用)外,还要考虑与生产数量无关的费用,即生产准备费用,只要某个时期开工生产时就
13、需要有kT的这项费用,引入了变量,当时表示不生产,当生产.10kw0kw1kw())(41hkk kkkkshxcwTzMin5 . 0, 30kkhcT. .ts)4 , 3 , 2 , 1,(1kdsxskkkk)4 , 3 , 2 , 1,(0,0)6.(,.0,00,.140 ksxssXXxxxwkkmmkkk k在此这一模型也可将数据输入 LINDON 求解(代码附后) ,就可得到: 最优目标函数为: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.000000 0.000000X4 0.000000 0.000000S1 3.000000 0.000000S2 0.000000 0.000000S3