用Excel解决先进先出问题详解

楼主 amulee	本题源自我出的一个测验题，VBA与SQL先进先出算法 http://www.exceltip.net/thread-40775-1-1.html 可惜参与的人不多，搜索了一下百度，发现关于这个问题的算法阐述不多。以下我就从原理入手，分享我对此题的一些看法，希望能够帮到各位。 1、先进先出原理篇 1.1 先进先出概念解释先进先出，顾名思义就是先进去的得先出来。这个思想在物流系统中比较常见。为了避免时间造成的损失，在商品出库的时候，先入库的商品先出库。其实在计算机数据结构算法中，也有先进先出的概念，如队列：所有数据排成一列，增加的数据排在队尾，取出数据时从队首取出。与先进先出相对应的一个概念是先进后出，如堆栈：堆栈好比一个瓶子，先进去的数据放在瓶底，后进去的数据靠近瓶口，取数据时只能从靠近瓶口的数据依次取。 1.2 先进先出的应用当然，先进先出不仅适用于商品出库，其实相同思想概念的就是根据优先级分配资源。如本题中，其实是变换了一种说法，但细想之下，实质就是先进先出。在先进先出的系统中，实质上是对分批进库的商品进行重新分组。因而，牵涉按一定顺序重新分组的问题，我们都可以将其转化为先进先出问题。如本例，实质就是对商品进行重新分组。 1.3 单批次货物的先进先出分配我们先从简单的开始，假设仓库中只有一个批次的商品，数量为60，现要求按照优先级分配给数量为20、10、15、30的订单中。可见60个商品不足以分配给所有订单，但是可以分配给多个订单，只要将订单排列好后，画如下的图就可以一目了然此次分配的结果。上图完整展示了分配的关系，可见分配的数量实质就是每个订单向库存处引线，交接处即为分割点。是否够分呢是由库存向订单引线，有交点说明不够分，交界处可体现剩余未分配的部分。上图分配的结果为：请读懂上述部分再进入以下讲解。 1.4 多批次货物的先进先出分配我们再将问题稍微复杂一点，我们增加一个批次数量为10的库存，两个批次分别用1号库和2号库分开。我们仍然按照1.3的方法由库存和订单互相向对方引线，交界处即为分割点。其分配关系如下图所示 OK，上图我们看到了什么？实质上，在1号库分配结果的基础上，2号库继续分配1号库未分配的部分。实质上，我们将1.3的过程分成了两组，分别就是两次1.3中的货物分配。多批次货物分配的实质就是每个批次按照顺序分别分配，在前一个分配结果的基础上，下一个批次去分配前一个批次未分完的订单。说到这里，大家应该明白怎么回事了。其实分配过程很简单，如果能做图，可以立即得到结果。多批次的分配，其实原理都是一样，实质就是每个批次的商品分别对应每一段订单的分配，如下图所示：如果以上都看明白了，那么可以继续看下一篇。
2楼 amulee	2、先进先出算法篇看了原理篇之后，其算法就不难实现了。此处，我们将继续深入话题。如果能够绘制柱形图，那么我们可以很快得到最终分配结果。但是在Excel语言描述中，似乎这一个方法很难实现，因而我们需要用一点数学的方法来将这个绘图的过程转换为数字计算的过程。 2.1 单一批次对应单一订单的分配别犹豫，我们要做的正是一对一的情形。在计算机语言描述中，其实是将所有的情形进行细分，直到分到能够直接用计算机语言描述。以下我们来看最简单的一种情形，即库存中只有一个批次的商品，现在有一个订单需要该商品，会发生什么情况呢？那么只可能出现三种情况：当出现这种情况时，库存中的商品数量能够满足该订单，于是该订单分到了Q2的数量，库存中还剩余Q1-Q2，订单1未分配的部分为0。当出现这种情况时，库存中的商品数量无法满足订单，则只能将库存中的商品全部分配，即订单1分配到了Q1的数量，库存中剩余库存为0，订单1未分配部分为Q2-Q1。这个情形正好是上述两种的一个特例，也是上述两种情形的一个交集，此时库存全部分配给订单，订单分配到的数量=Q1=Q2，库存剩余未0，订单未分配部分为0 2.2 多批次对应多订单的分配多对多的情形其实是上述情形的一种延伸。在多对多的系统中，实质上是进行多次的1对1分配。在1对1分配的结果上继续分配。如果出现上述情形1，那么第一次分配后的剩余库存Q1-Q2可以视为一个单独的批次，让其与接下去的订单2继续分配。如果出现上述情形2，那么第一次分配后的订单1剩余部分Q2-Q1可以视为一个单独的订单，让其与接下去的2#库存继续分配。如果出现上述情形3，那么订单2和2#库存是一次全新的1对1分配。上述过程如图所示：接下去，你只需不断延续上述过程，直到没有新的订单，或者没有剩余的库存为止。如果你能看完上述部分，那么我们就可以进入实质的解题了。
3楼 amulee	3、先进先出VBA解决方案根据第2部分的算法解答，我们很容易就能够得到VBA的解决方案。只要按照第2部分的步骤，将其翻译成VBA语言即可。为了便于理解，我将第2部分的步骤逐一转换成VBA代码，大家可以自己去优化。 Sub FIFO() Dim Arr1 '库存 Dim Arr2 '订单 Dim Arr '结果 Dim C1&, C2& '记录当前分配的库存或订单序号 Dim K& '结果数组计数 Dim Q1&, Q2& '记录库存和订单数量 '获取订单和库存数组 Arr1 = Sheet1.Range("B2:C7").Value Arr2 = Sheet2.Range("B2:C6").Value '定义结果数组 ReDim Arr(1 To 3, 1 To 1) '结果计数 K = 0 '设定分配从序号1开始 C1 = 1 C2 = 1 '获取Q1 Q2 Q1 = Arr1(1, 2) Q2 = Arr2(1, 2) '当序号在库存和订单序号范围内，持续分配 Do '分三种情形讨论 '情形1，Q1>Q2 If Q1 > Q2 Then '新增结果数组的记录数 K = K + 1 ReDim Preserve Arr(1 To 3, 1 To K) '订单分配数量为Q2 Arr(3, K) = Q2 '写入分配结果的库存和订单来源 Arr(1, K) = Arr1(C1, 1) Arr(2, K) = Arr2(C2, 1) '剩余库存Q1-Q2作为独立库存继续分配 Q1 = Q1 - Q2 '取下一个订单 C2 = C2 + 1 '若订单已经取完，则结束分配 If C2 > UBound(Arr2) Then Exit Do '取订单数量 Q2 = Arr2(C2, 2) '情形2，Q1<Q2 ElseIf Q1 < Q2 Then '新增结果数组的记录数 K = K + 1 ReDim Preserve Arr(1 To 3, 1 To K) '订单分配数量为Q2 Arr(3, K) = Q1 '写入分配结果的库存和订单来源 Arr(1, K) = Arr1(C1, 1) Arr(2, K) = Arr2(C2, 1) '剩余订单Q2-Q1作为独立订单继续分配 Q2 = Q2 - Q1 '取下一个批次的库存 C1 = C1 + 1 '若库存已经取完，则结束分配 If C1 > UBound(Arr1) Then Exit Do '取库存数量 Q1 = Arr1(C1, 2) '情形3，Q1=Q2 ElseIf Q1 = Q2 Then '新增结果数组的记录数 K = K + 1 ReDim Preserve Arr(1 To 3, 1 To K) '订单分配数量为Q2 Arr(3, K) = Q1 '写入分配结果的库存和订单来源 Arr(1, K) = Arr1(C1, 1) Arr(2, K) = Arr2(C2, 1) '取下一个批次的库存 C1 = C1 + 1 '若库存已经取完，则结束分配 If C1 > UBound(Arr1) Then Exit Do '取下一个订单 C2 = C2 + 1 '若订单已经取完，则结束分配 If C2 > UBound(Arr2) Then Exit Do '取库存数量 Q1 = Arr1(C1, 2) '取订单数量 Q2 = Arr2(C2, 2) End If Loop '结果输出： With Sheet3 .Cells.Clear .Range("A2").Resize(UBound(Arr, 2), 3) = WorksheetFunction.Transpose(Arr) .Range("A1") = "仓库" .Range("B1") = "客户" .Range("C1") = "分配数量" .UsedRange.Columns.AutoFit .UsedRange.Borders.Color = 1 End With End Sub 参考附件：先进先出VBA.rar
4楼 amulee	4、先进先出算法SQL解答篇--原理解释 4.1 原理解析 SQL的解法就不如VBA的那么直接，因为单纯的SQL语句中没有循环。我们举个简单一点的例子，如下图：如何求出以上AQ1--AQ6呢？其实我们可以发现，这几个结果其实是由库存与订单相互引线后的所围成的区域。进一步可以发现，这些结果其实是库存和订单数量或者累计数量相减后得到的结果。我们来计算一下AQ1--AQ6 AQ1=qA AQ2=qB AQ3=Q1-(qA+qB) AQ4=(qA+qB+qC)-Q1 AQ5=(Q1+Q2)-(qA+qB+qC) AQ6=Q3 乍看之下，这些结果似乎没有什么特别的规律。但其实这些结果只存在4种情况： 1、等于单个订单数量（如：AQ1，AQ2） 2、等于单个库存数量（如：AQ6） 3、等于多个订单的累计数量-多个库存的累计数量（如：AQ3） 4、等于多个库存的累计数量-多个订单的累计数量（如：AQ3，AQ5）那么这些结果如何获取呢？我们来看一下上述那张图，实质上我们计算的就是库存和订单引出的红线在对方区间内的分割点。 4.2 分割点结论那么这些分割点是如何产生的呢？其实是当红色虚线落到对方的某一个区间内就会产生分割。而判断红线落到区间内的数学表达就是： 1、这根红线所代表的数量大于该区间的起点数量。 2、该区间的终点数量大于该红线所表示的数量。如图所示：由上图我们可以看见，起点数量就是当前订单或库存所对应的上一个累计数量，而终点数量就是当前订单或库存的累计数量，而红线对应的数量就是对方某个终点数量。而在实际计算中，这是个相互作用的过程，即终点数量、红线数量、起点数量随着对应计算区间的不同，一直在进行着角色变换。以下我们会进一步说明。在此之前，请读懂以上内容。 4.3 订单向库存引线的分割点计算为方便理解，我们将这个例子转换为数字，如下表： 4.3.1 我们先取2个仓库，计算一下订单向库存引红线的情况。可以发现，红线落在起点和终点范围内的情况就是最右两列计算结果都大于0的情况，也就是1号仓库被订单分割成了两部分。与图示一致。 4.3.2 我们再取2个仓库，计算一下订单向库存引红线的情况。如图所示，1号和2号仓库被订单分割了3下。依次类推，最终结果如下： 4.4 库存向订单引线的分割点计算此处大家自己去计算了，我把结果直接给大家。 4.5 最终结果可以看见，最终双向各有3条引线，因而结果为6个。那么这么多数字当中取那些数字呢？再来观察一下这个图最终，我们得到的六个结果中有好多列的数字，这些数字正好包括了4.1中所述的全部4种情况。但是取哪些呢？很显然，在这些数字中其实包含了几个区间的相减结果，而通过图中的观察，我们所需要的结果正好是这些区间的最小值，也就是所有被红色线分割的所有最小单位区间。因而最终结果：这一段我知道很难理解，大家都动手做一下才能体会。看懂了就接下去看。 4.6 简化事实上，我们并不是从24个结果中去取结果，我们只需要从12个结果中取（库存批次3订单批次4，笛卡尔积）。我们将上述24个结果排序后放在一起。事实上，我们只要判定库存红线是否大于对方起点： 1、若大于对方，则表示当前的数量能够满足对方对应区间的全部或部分需求。 2、若能够满足全部需求时，则分配数量为是取对方每个最小区间的数量。 3、若能够满足部分需求时，则当前数量为为分配数量 4、在能够满足对方需求的前提下，对方所对应的区间应能够涵盖当前区域，即对方的红线必须落在当前库存区域。否则表示对方在前一个库存中已经分配完毕。 5、取上图四列中全部为正数的记录，并保留最小值，即为分配结果。逻辑大致如此。此处不必考虑对方红线是否超过当前区域，因为之间正好有相排斥的部分，当超过当前区域时，实质是进入后一个库存批次分配，而此时库存的红线不能够满足该订单，表现为负数。这个逻辑有点难理解。不知道有没有跟大家说清楚。我的建议是，大家最好拿一些具体的数字自己动手按照上述逻辑比较一下*。如果都能够看懂，那么恭喜你，你已经掌握了核心思想了，可以开始进行正式计算了。
5楼 amulee	5、SQL解法如果你能够进行到这里，那么恭喜你，你已经完全理解我所要表达的意思了。我的数学不好，我也不知道有什么数学方法能够证明我的思想，我仅是凭借那个分配图一步步分析而来的。也希望数学系的朋友们看了别。 OK，不管怎么说，我的理论是正确的（有兴趣可以反驳一下）。那么我们现在就按照第四部分的理论来解题了。 5.1 得到累计数量累计库存： Select A.仓库,A.数量 As 库存,(Select Sum(数量) from [库存$] B Where B.序号<=A.序号) As 累计库存 from [库存$] A 累计订单： Select C.客户,C.数量,(Select Sum(数量) from [订单$] D Where D.序号<=C.序号) As 累计数量 from [订单$] C 5.2 计算红线-起点由于SQL中没有行函数MIN，所以只能用IIF比较大小，我们这里就先比较库存和订单数量，取最小值Q3，剩余的Q1和Q2分别表示仓库向订单引线以及订单向仓库引线。 Select 客户,仓库,IIF(数量>库存,库存,数量) As Q3,累计库存-累计数量+数量 As Q1,累计数量-累计库存+库存 As Q2 from (Select C.客户,C.数量,(Select Sum(数量) from [订单$] D Where D.序号<=C.序号) As 累计数量 from [订单$] C) As E ,(Select A.仓库,A.数量 As 库存,(Select Sum(数量) from [库存$] B Where B.序号<=A.序号) As 累计库存 from [库存$] A) As F 5.3 取大于0的记录此处可以比较Q1和Q2，得到Q4 Select 客户,仓库,Q3,IIF(Q1>Q2,Q2,Q1) As Q4 From (Select 客户,仓库,IIF(数量>库存,库存,数量) As Q3,累计库存-累计数量+数量 As Q1,累计数量-累计库存+库存 As Q2 from (Select C.客户,C.数量,(Select Sum(数量) from [订单$] D Where D.序号<=C.序号) As 累计数量 from [订单$] C) As E ,(Select A.仓库,A.数量 As 库存,(Select Sum(数量) from [库存$] B Where B.序号<=A.序号) As 累计库存 from [库存$] A) As F) Where Q1>0 And Q2>0 5.4 最终结果** 继续比较Q3和Q4，得到最终结果 Select 客户,仓库,IIF(Q3>Q4,Q4,Q3) As 分配数量 From (Select 客户,仓库,Q3,IIF(Q1>Q2,Q2,Q1) As Q4 From (Select 客户,仓库,IIF(数量>库存,库存,数量) As Q3,累计库存-累计数量+数量 As Q1,累计数量-累计库存+库存 As Q2 from (Select C.客户,C.数量,(Select Sum(数量) from [订单$] D Where D.序号<=C.序号) As 累计数量 from [订单$] C) As E ,(Select A.仓库,A.数量 As 库存,(Select Sum(数量) from [库存$] B Where B.序号<=A.序号) As 累计库存 from [库存$] A) As F) Where Q1>0 And Q2>0) 参考附件下载：先进先出.rar
6楼 amulee	6、函数公式解法利用上述原理，用函数公式也可以得到结果。在函数解法中，由于没有笛卡尔积，只能运用二维数组运算获得。具体算法不在这里阐述了，和SQL步骤一样。懒得简化和合并了，因而用了辅助区域，大家感兴趣做一下。参考附件：先进先出函数解法.rar 以上个人看法希望能够抛砖引玉，得到社区众高手的指正和提点。如有更好的解法，希望不要吝啬，能够共享出来。如果没有看明白，欢迎提问。不知不觉1点了，睡了
7楼 lrlxxqxa	精彩！
8楼 lqin119	非常感谢，拜读**！
9楼 webuse123	高手高手高高手
10楼 zhuangdi198243	强,我平时都用IF函数将相关资料进行分析
11楼 deutscher123	受用**
12楼 bensonlei	真精彩！研究中
13楼 maukiu	这个东东找了很久了
14楼翼天龙	虽然现在还看不懂，但是正在学习中。感谢分享！
15楼 roykonev	正受困于这个，太感谢了
16楼夏之梦	谢谢，好厉害啊
17楼 amylee	驻足学习，谢谢分享！
18楼 wise	厉害啊！阿木
19楼 10night	非常不错，很有用~
20楼 Kingem_Chan	太有用了，学习中
21楼 hustclm	看了阿木的文章，真心给跪了，感觉在看一篇数学论文
22楼 raalyf	强,我平时都用IF函数将相关资料进行分析
23楼水星钓鱼	这才是ｅ文精选啊。木哥，给跪了！
24楼 lrlxxqxa
25楼 rfshi	学习了，谢谢分享！
26楼 dgxsdr	很强大
27楼小同学大衣柜	能帮我把我这个填一下公式吗空白库存模板41（鞋、服装）.rar
28楼小同学大衣柜	能帮我把我这个填一下公式吗空白库存模板41（鞋、服装）.rar
29楼 gcl-1	好好吸收一下.楼主辛苦了..
30楼 windimi007	阿木老师的这篇大作必须花时间好好研读，慢慢消化一番才行哈！
31楼 HWL	非常难得的好帖子绝对值得花时间研究
32楼 HWL	楼主幸苦...
33楼 Back_34	谢谢！精彩，我要好好研究