基于网格自适应直接搜索的随机库存决策模型

昆明理工大学管理与经济学院 薛瀚 黄琼

作为一类典型的库存系统，随机库存系统由于存在随机变量以及变量之间的复杂线性关系，不容易通过解析方法对其进行求解[1]。仿真技术擅长于构建随机性和动态条件下的复杂系统模型，并进行相关分析。利用仿真技术能够尽可能准确地描述各个变量之间的关系，还原现实世界的复杂随机性，能够有效地求解随机库存问题[2,3]。

本文优化问题属于基于仿真的优化问题(Simulationbased optimization)，其特征有：由于仿真的复杂性，目标函数(1)易受到噪声不同程度的影响；(2)不一定可导和；(3)评价过程耗时长[4]。本文将采用网格自适应直接搜索进行求解。网格自适应直接搜索，作为一类直接搜索算法，与随机搜索算法相比，具有较强的鲁棒性、优良的分布式计算机制、全局收敛性等优点[5]。

本文针对随机需求、随机订货提前期的随机库存系统，构建了随机库存决策模型，并提出了一种基于网格自适应直接搜索的求解方法。研究实例表明，模型仿真求解结果具有稳健性且能够提高系统绩效，从而验证了模型的有效性。

1 问题描述及假设

本文考虑一个无限时间范围内，随机需求以及随机提前期情形下求解随机库存系统的最优库存策略，使系统的平均总成本最小的问题。本文中，库存系统采用连续盘点库存策略(Q, r)，即当系统库存位置(库存位置=库存水平+未到达的订货量)下降到再订货点r时，发出补货订单将库存位置补充到Q[6]。同时，只有当系统的库存水平大于或等于订单的需求数量时，才满足订单需求，否则记入缺货数量。综上，本文的随机库存决策问题可以表述为通过确定最优库存策略参数使得库存系统在满足最小顾客满意度约束下最小化平均总成本。

本文库存系统满足以下假设：

(1)单期只出现一个需求(订单)；

(2)需求和订货提前期是随机的，且相互独立；

(3)货物订单(需求)期初达到，库存满足则马上发货，若不满足该订单量则记入缺货数量；

(4)单个订货周期内不允许再次订货。

2 随机库存决策模型

如前文所述，本文考虑的随机库存决策问题是通过求解最优的库存策略来最小化系统的平均总成本。按照本文假设，同时考虑实际情况，平均总成本由平均订货成本、平均持有成本和平均缺货成本组成。模型中用到两个绩效指标：平均总成本和顾客满意度，平均总成本是主要指标，而顾客满意度是用作约束的指标。基于上述讨论，随机库存决策模型(SID)表示如下：

由于本文考虑到随机提前期的情况，模型更加现实并且变得复杂，难以写出中间变量的解析式，造成模型解析求解困难。对此，本文将进行仿真建模并采用网格自适应直接搜索对模型进行求解。

3 基于网格自适应直接搜索的模型求解

网格自适应直接搜索(Mesh Adaptive Direct Search,MADS)[5]是模式搜索(Pattern Search)方法的一类，通过允许变量空间中方向的渐近紧致集的局部搜索，它扩展了广义模式搜索(GPS)。其具有以下优势：(1)容易拓展与应用；(2)求导困难和有限差分不可靠的情况下仍然有效；(3)具有比得上线搜索算法和信赖域算法的全局收敛性质[7]。选择最大代数和网格阀值作为网格自适应直接搜索的停止条件，当算法的运行代数超过最大代数或者网格尺寸低于网格阀值时，算法结束并输出最优结果。

本文采用美国MathWorks公司开发的商业数学软件MATLAB®实现MADS对控制策略优化模型的优化求解，其拥有强大的数值计算性能，并且能够通过各种工具箱扩展功能。

4 实例仿真及结果分析

本文以某企业作为实证对象。该企业的产品在100周内的需求量如表1所示，100次订货提前期统计数据如表2所示，而该产品每周的单位订货成本为单位库存持有成本为单位缺货成本为最小顾客满意度。MADS的最大代数为60，网格阀值为1e-06。

表1 产品每周需求量统计表

表2 产品每周订货提前期统计表

MADS的优化求解过程如图1和图2所示。从图1可以看到目标函数值随着算法迭代过程不断地减小，而从图2可以看到当目标函数值得到提高时网格尺寸在扩大，否则虽小，且可以知道算法停止是由于网格尺寸低于网格阀值(1e-06)。SID的优化求解结果见表3。利用MADS对SID进行优化求解，目标函数值 取得了一个满意的优化值，而指标 也满足了大于85%的约束。

图1 目标函数值变化过程

图2 网格尺寸变化过程

表3 优化求解结果

5 结语

本文基于网格自适应直接搜索，研究了不确定市场需求和订货提前期条件下的库存决策问题。首先建立随机库存决策模型；然后提出一种基于网格自适应直接搜索的求解方法；最后进行仿真求解并验证了模型解的收敛性。本文的贡献在于，一方面丰富了随机库存决策问题的研究，另一方面提出了一种基于网格自适应直接搜索算法的求解方法，对存在随机因素的复杂系统管理决策具有较好的借鉴意义。

[1] 胡运权,郭耀煌.运筹学教程[M].北京:清华大学出版社,2007.

[2] 胡幼华,潘荫荣,孙强.FIFO存贮队列管理的随机库存系统的仿真模型[J].华东师范大学学报(自然科学版),2003(03).

[3] 姜昌华,胡幼华.基于遗传算法的随机(s，S)库存系统仿真优化[J].华东师范大学学报(自然科学版),2006(03).

[4] Deng G.Simulation-based optimization[D].UNIVERSITY OF WISCONSIN MADISON,2007.

[5] Audet C,Dennis Jr J E.Mesh adaptive direct search algorithms for constrained optimization[J].SIAM Journal on optimization,2006,17(1).

[6] 冯颖,张炎治.随机需求下考虑订货提前期的易变质产品(r,Q)库存策略研究[J].中国管理科学,2012(S2).

[7] Lewis R M,Torczon V,Trosset M W.Why pattern search works[R].Institute for computer applications in Science and engineering hampton va,1998.