何为求解器？

图片

最近学习到的关于求解器的新知识总结。首先求解器是用在数学规划问题中的常见工具，那么问题来了，数学中用到的工具和供应链业务有什么相关呢？我们还要继续再往前走一步，看看数学规划问题能为我们解决些什么业务问题。带着这些疑惑请耐心往下看，文章较长。

图片

1. 什么是决策优化？

在解决实际问题前，先从理论出发，先让我们认识下决策优化。搞清楚决策优化的时候，我还要再塞入两个概念（后边不会再有套娃了）：可行解和最优解。

• 可行解 亦称可行点或允许解，数学规划的基本概念之一，指在数学规划问题中，满足所有约束条件的解（点）。
• 最优解 数学规划的基本概念之一，指在数学规划问题中，使目标函数取最小值（对极大化问题取最大值）的可行解。使目标函数取最小值的可行解称为极小解，使其取最大值的可行解称为极大解。极小解或极大解均称为最优解。
• 决策优化

从众多可行解中找到最优解的过程就是决策优化。决策优化可帮助业务部门在资源有限，满足业务规则的条件下，进行全面而综合（多个业务目标平衡）考虑，计算出给定场景下的更佳甚至最佳方案，从而节省成本，提高效益，提升服务水平。

举个例子，现在有这样一个需求，一辆车需要经过5个途径点，如果你是负责车辆调度的决策人员该如何做决策？很明显，途径5个地点，共有5！，也就是120种排列组合方式。这120种全部都是可行解，但很明显我们不会随机任选一种作为我们的决策结果，而是会根据限制条件和直观经验选择出一条相对高效、低成本的运行路线。而选出来的这最后的路线就是最优解。根据限制条件、直观经验，排除其他路径的过程就是决策优化。

2. 决策优化场景

适用决策优化的企业场景如下：制造业中的APS计划排产、MRP运行、人员排班、车辆调度等业务；运输业中的航班调度等业务；教育行业的排课等业务。

上面举得例子是比较直观且简单的，但是往往企业业务中需要决策的数据维度、数据量、约束限制上是更为庞大和复杂的，要想在这些业务中用人力去判断出最优解是不太现实的。人为判断结果在准确性和速度上都要大打折扣，更多的是基于人的经验得出的结果。而事实告诉我们单靠经验是十分不可靠的。

这时候就要引出我们今天要介绍的主角——求解器了。

3. 求解器

求解器是用来实现在可行解中找到最优解的信息化工具。它通常面对的是庞大数据量、诸多限制约束条件的复杂业务场景。目前市面上主要分商用求解器、开源求解器两类。商用求解器主要有IBM CPLEX、GUROBI；开源求解器主要有SCIP。商用求解器的效率一般是开源求解器的5-7倍。采用商用求解器计算下的生产计划排程在保证数据准确性的前提下可缩短至分钟级。

• 影响求解器运行效率的因素 在这里主要分享自己了解的两个因素：

1) 模型＞求解器版本＞硬件条件

首先是业务问题在抽象化为数学问题时的建模好坏，是直接影响求解器运行效率的最大因素。其次是求解器本身版本的差异，因为在每次版本更新时，其实主要的是求解器运行背后算法的提升模拟，做过开发的都知道一个算法对程序效率的影响程度。最后才是运行求解器的硬件本身的条件，这反而是对求解器效率影响程度最小的。但是如果采用求解器时，尽量部署在单独的设备上，因为在程序运行算法时，还是吃CPU比较大的，基本是满负荷运转。

2)Gap

我没找到官方定义解释，在我的理解中，gap是一组设定的函数目标值，gap=2*当前解/(最优解上限+最优解下限）*100%。当求解器模拟计算的值达到设定gap值后，就可以终止求解策略（收敛到gap的时间值也是作为衡量求解器好坏的重要依据。收敛越快效率越高，见图）。在设置求解器终止策略时，可以考虑：

    ①.设定一个固定时间值。不管结果如何，到点即停。

    ②.设置可容忍的gap。但是存在一直无法达到预期值的情况。

    ③.①和②组合。

图片

3. 利用求解器解决问题的实现过程

业务问题→约束明确→数学模型→程序实现

• 业务问题 以前段时间分享的MRP运行实例为例，即根据日程计划、BOM、物料采购期、MOQ、SPQ、安全库存、现有PO残等基础信息，自动计算得到物料需求计划。在确保正常的生产业务的同时，尽量降低库存，使库存资金占用最小化。
• 约束明确

①需求计划、到货计划要可以满足正常生产；

②不能存在缺口；

③库存不能超上限，也不能低于下限；

④要考虑LT、SPQ、MOQ；

⑤要考虑工作日；

⑥要考虑多社采购；

⑦要考虑替换料的情况；

• 数学模型 令T表示待计划时刻集合，∀t∈T；M表示所有物料集合，∀m∈M；P表示所有产品集合，∀p∈P；I_(t,m)表示第t时刻物料m的到货量；O_(t,p)表示第t时刻产品p的生产计划量，S_(t,p)表示第t时刻产品p的外销计划量；B_(p,m)表示产品与物料的BOM表信息。 令β_(t,m)表示t时刻物料m的库存水平，令▁V_(t,m)表示t时刻物料m的库存下限，令¯V_(t,m)表示t时刻物料m的库存上限，令S_(t,m)表示t时刻物料m的安全库存，令f_(t,m)表示t时刻物料m的安全库存单位欠缺量惩罚成本，令γ_(t,m)表示t时刻物料m的安全库存缺口。 则生产计划系统的主模型如下：

图片

（1）最小缺口成本；（2）预计库存；（3）安全库存缺口量；（4）（5）库存限制条件

• 程序语言 最终就是程序层面的逻辑实现。

最后，近期PMBOK第七版（英文版）官方已经发布，如果感兴趣，请在微信公众号“ActCrew”后台回复‘PMP’领取。