论文部分内容阅读
经济批量问题（Economic Lot Size Problem或Dynamic Lot Size Problem），简写为ELS或DLS问题，来源于生产和库存管理领域。最简单的ELS模型是假设需求率和生产费用是固定的，通常被称为EOQ模型。而在现实生产和库存管理中，经常采用的是需求和成本随时间变化而变化的ELS模型。在我们的论文中，我们着重研究两类ELS问题。论文分三章来叙述。第一章引言，主要介绍了库存管理的发展、经济批量问题的定义和研究概况，及算法复杂性中的相关定义。第二章研究了一类单一产品满足多断点折扣费用函数且不允许缺货的ELS问题。所谓的多断点折扣费用函数是指当进货量在不同的区间时，其相应的单位进货费用的折扣率也不同。我们把每个区间的端点值称为断点。本章是由一类单一产品具有单断点折扣费用函数的ELS问题，推广到具有多个断点的折扣费用函数的情形。对此问题我们分析了其最优解的性质，并给出一个复杂性不超过O（n3+mn2）的最优算法，其中n表示需要考虑的时期的个数，m表示断点的个数且为常数。第三章讨论了易腐产品允许缺货的ELS问题，其中定购费用函数、存储费用函数和缺货惩罚费用函数均满足规模经济（economics of scale）函数。所谓的易腐产品是指产品在存贮过程中易损耗，而损耗程度与存储的时间长短有关。而规模经济函数是指满足下面两个条件的函数f（x）：（1）f（x）在定义域[0，+∞)上为非降函数，且f（0）=0。（2）平均函数（?）（x）=f（x）／x在（0，+∞）上是非增函数。费用函数为规模经济的易腐产品的ELS问题是NP-难的问题，对于不允许缺货情形，Chu等（2005．Naval Research Logistics）给出了一个寻找近似解的算法，并证明了该算法的最差性能比为(421／2+5)／7。本章我们将这一结果推广到允许缺货的情形，在所有费用函数均满足规模经济函数时，对此问题给出一个近似算法，这个算法可以在多项式时间内得到原问题的近似解，其最差性能比为(421／2+5)／7且该界是紧的。