设为首页收藏本站|繁體中文

Excel 技巧网

QQ登录

只需一步,快速开始

手机号码,快捷登录

查看: 21496|bwin官网地址: 40

[综合应用] 用Excel解决先进先出问题详解

  [复制链接]
发表于 2012-11-13 00:54:20 | 显示全部楼层 |阅读模式
  • 署名作者: amulee
  • 版权声明: 版权归本站与作者共有 除本站官方外非作者本人转载须经许可并注明出处
  • 本文来自:
  • 引用作品:
  • 适用版本: 2013 2010 2007 2003以前版本 
  • 语言环境: 简体中文
  • 学习方法: 掌握Excel技巧的关键是动手操作 | 下载 ≠ 知识


  • 免费注册成为本站会员,享用更多功能,结识更多Office办公高手!

    您需要 登录 才可以下载或查看,没有帐号?注册

    x
    本帖最后由 amulee 于 2012-11-11 21:53 编辑

    本题源自我出的一个测验题,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.png

         上图完整展示了分配的关系,可见分配的数量实质就是每个订单向库存处引线,交接处即为分割点。是否够分呢是由库存向订单引线,有交点说明不够分,交界处可体现剩余未分配的部分。上图分配的结果为:
    2.png

    请读懂上述部分再进入以下讲解。

    1.4 多批次货物的先进先出分配

          我们再将问题稍微复杂一点,我们增加一个批次数量为10的库存,两个批次分别用1号库和2号库分开。我们仍然按照1.3的方法由库存和订单互相向对方引线,交界处即为分割点。其分配关系如下图所示
    3.png

    OK,上图我们看到了什么?实质上,在1号库分配结果的基础上,2号库继续分配1号库未分配的部分。实质上,我们将1.3的过程分成了两组,分别就是两次1.3中的货物分配。

    多批次货物分配的实质就是每个批次按照顺序分别分配,在前一个分配结果的基础上,下一个批次去分配前一个批次未分完的订单。
    5.png


    说到这里,大家应该明白怎么回事了。其实分配过程很简单,如果能做图,可以立即得到结果。多批次的分配,其实原理都是一样,实质就是每个批次的商品分别对应每一段订单的分配,如下图所示:
    6.png



    如果以上都看明白了,那么可以继续看下一篇。






    评分

    参与人数 5魅力值 +20 收起 理由
    + 3
    使用意义很大
    + 5
    感谢帮助:)
    + 2
    思路巧妙:)
    + 5
    精品!
    + 5
    优秀作品!

    查看全部评分

     楼主| 发表于 2012-11-13 00:54:21 | 显示全部楼层
    本帖最后由 amulee 于 2012-11-11 22:15 编辑

    2、先进先出算法篇

          看了原理篇之后,其算法就不难实现了。此处,我们将继续深入话题。

          如果能够绘制柱形图,那么我们可以很快得到最终分配结果。但是在Excel语言描述中,似乎这一个方法很难实现,因而我们需要用一点数学的方法来将这个绘图的过程转换为数字计算的过程。

    2.1 单一批次对应单一订单的分配

          别犹豫,我们要做的正是一对一的情形。在计算机语言描述中,其实是将所有的情形进行细分,直到分到能够直接用计算机语言描述。以下我们来看最简单的一种情形,即库存中只有一个批次的商品,现在有一个订单需要该商品,会发生什么情况呢?那么只可能出现三种情况:

           7.png

          当出现这种情况时,库存中的商品数量能够满足该订单,于是该订单分到了Q2的数量,库存中还剩余Q1-Q2,订单1未分配的部分为0。

           8.png

          当出现这种情况时,库存中的商品数量无法满足订单,则只能将库存中的商品全部分配,即订单1分配到了Q1的数量,库存中剩余库存为0,订单1未分配部分为Q2-Q1。

           9.png

          这个情形正好是上述两种的一个特例,也是上述两种情形的一个交集,此时库存全部分配给订单,订单分配到的数量=Q1=Q2,库存剩余未0,订单未分配部分为0

    2.2 多批次对应多订单的分配

          多对多的情形其实是上述情形的一种延伸。在多对多的系统中,实质上是进行多次的1对1分配。在1对1分配的结果上继续分配。

          如果出现上述情形1,那么第一次分配后的剩余库存Q1-Q2可以视为一个单独的批次,让其与接下去的订单2继续分配。

          如果出现上述情形2,那么第一次分配后的订单1剩余部分Q2-Q1可以视为一个单独的订单,让其与接下去的2#库存继续分配。

          如果出现上述情形3,那么订单2和2#库存是一次全新的1对1分配。

          上述过程如图所示:

           10.png

          接下去,你只需不断延续上述过程,直到没有新的订单,或者没有剩余的库存为止。


    如果你能看完上述部分,那么我们就可以进入实质的解题了。


    评分

    参与人数 1魅力值 +5 收起 理由
    + 5
    感谢帮助:)

    查看全部评分

     楼主| 发表于 2012-11-13 00:54:22 | 显示全部楼层
    本帖最后由 amulee 于 2012-11-11 22:47 编辑

    3、先进先出VBA解决方案

    根据第2部分的算法解答,我们很容易就能够得到VBA的解决方案。

    只要按照第2部分的步骤,将其翻译成VBA语言即可。

    为了便于理解,我将第2部分的步骤逐一转换成VBA代码,大家可以自己去优化。
    1. Sub FIFO()
    2.     Dim Arr1    '库存
    3.     Dim Arr2    '订单
    4.     Dim Arr      '结果
    5.     Dim C1&, C2& '记录当前分配的库存或订单序号
    6.     Dim K&      '结果数组计数
    7.     Dim Q1&, Q2&    '记录库存和订单数量
    8.    
    9.     '获取订单和库存数组
    10.     Arr1 = Sheet1.Range("B2:C7").Value
    11.     Arr2 = Sheet2.Range("B2:C6").Value
    12.    
    13.     '定义结果数组
    14.     ReDim Arr(1 To 3, 1 To 1)
    15.    
    16.     '结果计数
    17.     K = 0
    18.    
    19.     '设定分配从序号1开始
    20.     C1 = 1
    21.     C2 = 1
    22.    
    23.     '获取Q1 Q2
    24.     Q1 = Arr1(1, 2)
    25.     Q2 = Arr2(1, 2)
    26.    
    27.     '当序号在库存和订单序号范围内,持续分配
    28.     Do
    29.         '分三种情形讨论
    30.         '情形1,Q1>Q2
    31.         If Q1 > Q2 Then
    32.             '新增结果数组的记录数
    33.             K = K + 1
    34.             ReDim Preserve Arr(1 To 3, 1 To K)
    35.             '订单分配数量为Q2
    36.             Arr(3, K) = Q2
    37.             '写入分配结果的库存和订单来源
    38.             Arr(1, K) = Arr1(C1, 1)
    39.             Arr(2, K) = Arr2(C2, 1)
    40.             '剩余库存Q1-Q2作为独立库存继续分配
    41.             Q1 = Q1 - Q2
    42.             '取下一个订单
    43.             C2 = C2 + 1
    44.             '若订单已经取完,则结束分配
    45.             If C2 > UBound(Arr2) Then Exit Do
    46.             '取订单数量
    47.             Q2 = Arr2(C2, 2)
    48.         
    49.         '情形2,Q1<Q2
    50.         ElseIf Q1 < Q2 Then
    51.             '新增结果数组的记录数
    52.             K = K + 1
    53.             ReDim Preserve Arr(1 To 3, 1 To K)
    54.             '订单分配数量为Q2
    55.             Arr(3, K) = Q1
    56.             '写入分配结果的库存和订单来源
    57.             Arr(1, K) = Arr1(C1, 1)
    58.             Arr(2, K) = Arr2(C2, 1)
    59.             '剩余订单Q2-Q1作为独立订单继续分配
    60.             Q2 = Q2 - Q1
    61.             '取下一个批次的库存
    62.             C1 = C1 + 1
    63.             '若库存已经取完,则结束分配
    64.             If C1 > UBound(Arr1) Then Exit Do
    65.             '取库存数量
    66.             Q1 = Arr1(C1, 2)
    67.             
    68.         '情形3,Q1=Q2
    69.         ElseIf Q1 = Q2 Then
    70.             '新增结果数组的记录数
    71.             K = K + 1
    72.             ReDim Preserve Arr(1 To 3, 1 To K)
    73.             '订单分配数量为Q2
    74.             Arr(3, K) = Q1
    75.             '写入分配结果的库存和订单来源
    76.             Arr(1, K) = Arr1(C1, 1)
    77.             Arr(2, K) = Arr2(C2, 1)
    78.             '取下一个批次的库存
    79.             C1 = C1 + 1
    80.             '若库存已经取完,则结束分配
    81.             If C1 > UBound(Arr1) Then Exit Do
    82.             '取下一个订单
    83.             C2 = C2 + 1
    84.             '若订单已经取完,则结束分配
    85.             If C2 > UBound(Arr2) Then Exit Do
    86.             '取库存数量
    87.             Q1 = Arr1(C1, 2)
    88.             '取订单数量
    89.             Q2 = Arr2(C2, 2)
    90.         End If
    91.     Loop
    92.    
    93.     '结果输出:
    94.     With Sheet3
    95.         .Cells.Clear
    96.         .Range("A2").Resize(UBound(Arr, 2), 3) = WorksheetFunction.Transpose(Arr)
    97.         .Range("A1") = "仓库"
    98.         .Range("B1") = "客户"
    99.         .Range("C1") = "分配数量"
    100.         .UsedRange.Columns.AutoFit
    101.         .UsedRange.Borders.Color = 1
    102.     End With
    103. End Sub
    复制代码
    参考附件: 先进先出VBA.rar (20.34 KB, 下载次数: 450)

    评分

    参与人数 3魅力值 +15 消费券 +100 收起 理由
    + 5
    + 50
    技法娴熟:)
    + 5
    感谢帮助:)
    + 5
    + 50
    受益良多,感谢分享!

    查看全部评分

     楼主| 发表于 2012-11-13 00:54:23 | 显示全部楼层
    本帖最后由 amulee 于 2012-11-13 00:14 编辑

    4、先进先出算法SQL解答篇--原理解释

    4.1 原理解析
    SQL的解法就不如VBA的那么直接,因为单纯的SQL语句中没有循环。我们举个简单一点的例子,如下图:

    11.png

    如何求出以上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、该区间的终点数量大于该红线所表示的数量。


    如图所示:
    12.png
    13.png

    由上图我们可以看见,起点数量就是当前订单或库存所对应的上一个累计数量,而终点数量就是当前订单或库存的累计数量,而红线对应的数量就是对方某个终点数量。

    而在实际计算中,这是个相互作用的过程,即终点数量、红线数量、起点数量随着对应计算区间的不同,一直在进行着角色变换。以下我们会进一步说明。在此之前,请读懂以上内容

    4.3 订单向库存引线的分割点计算

    为方便理解,我们将这个例子转换为数字,如下表:
    14.png


    4.3.1 我们先取2个仓库,计算一下订单向库存引红线的情况。
    15.png


    可以发现,红线落在起点和终点范围内的情况就是最右两列计算结果都大于0的情况,也就是1号仓库被订单分割成了两部分。与图示一致。

    4.3.2 我们再取2个仓库,计算一下订单向库存引红线的情况。

    16.png

    如图所示,1号和2号仓库被订单分割了3下。依次类推,最终结果如下:

    18.png

    4.4 库存向订单引线的分割点计算

    此处大家自己去计算了,我把结果直接给大家。
    17.png

    4.5 最终结果

    可以看见,最终双向各有3条引线,因而结果为6个。那么这么多数字当中取那些数字呢?再来观察一下这个图


    最终,我们得到的六个结果中有好多列的数字,这些数字正好包括了4.1中所述的全部4种情况。但是取哪些呢?很显然,在这些数字中其实包含了几个区间的相减结果,而通过图中的观察,我们所需要的结果正好是这些区间的最小值,也就是所有被红色线分割的所有最小单位区间。

    因而最终结果:
    19.png

    这一段我知道很难理解,大家都动手做一下才能体会。看懂了就接下去看。

    4.6 简化

    事实上,我们并不是从24个结果中去取结果,我们只需要从12个结果中取(库存批次3*订单批次4,笛卡尔积)。

    我们将上述24个结果排序后放在一起。

    20.png

    事实上,我们只要判定库存红线是否大于对方起点:
    1、若大于对方,则表示当前的数量能够满足对方对应区间的全部或部分需求。
    2、若能够满足全部需求时,则分配数量为是取对方每个最小区间的数量。
    3、若能够满足部分需求时,则当前数量为为分配数量
    4、在能够满足对方需求的前提下,对方所对应的区间应能够涵盖当前区域,即对方的红线必须落在当前库存区域。否则表示对方在前一个库存中已经分配完毕。
    5、取上图四列中全部为正数的记录,并保留最小值,即为分配结果。

    逻辑大致如此。此处不必考虑对方红线是否超过当前区域,因为之间正好有相排斥的部分,当超过当前区域时,实质是进入后一个库存批次分配,而此时库存的红线不能够满足该订单,表现为负数。

    这个逻辑有点难理解。不知道有没有跟大家说清楚。我的建议是,大家最好拿一些具体的数字自己动手按照上述逻辑比较一下

    如果都能够看懂,那么恭喜你,你已经掌握了核心思想了,可以开始进行正式计算了。




    评分

    参与人数 1魅力值 +2 收起 理由
    + 2
    技法娴熟:)

    查看全部评分

     楼主| 发表于 2012-11-13 00:54:24 | 显示全部楼层
    5、SQL解法

    如果你能够进行到这里,那么恭喜你,你已经完全理解我所要表达的意思了。

    我的数学不好,我也不知道有什么数学方法能够证明我的思想,我仅是凭借那个分配图一步步分析而来的。也希望数学系的朋友们看了别**。

    OK,不管怎么说,我的理论是正确的(有兴趣可以反驳一下)。那么我们现在就按照第四部分的理论来解题了。

    5.1 得到累计数量

    累计库存:
    1. Select A.仓库,A.数量 As 库存,(Select Sum(数量) from [库存$] B Where B.序号<=A.序号) As 累计库存 from [库存$] A
    复制代码
    累计订单:
    1. Select C.客户,C.数量,(Select Sum(数量) from [订单$] D Where D.序号<=C.序号) As 累计数量 from [订单$] C
    复制代码
    5.2 计算红线-起点

    由于SQL中没有行函数MIN,所以只能用IIF比较大小,我们这里就先比较库存和订单数量,取最小值Q3,剩余的Q1和Q2分别表示仓库向订单引线以及订单向仓库引线。
    1. Select 客户,仓库,IIF(数量>库存,库存,数量) As Q3,累计库存-累计数量+数量 As Q1,累计数量-累计库存+库存 As Q2
    2. from
    3. (Select C.客户,C.数量,(Select Sum(数量) from [订单$] D Where D.序号<=C.序号) As 累计数量 from [订单$] C) As E
    4. ,(Select A.仓库,A.数量 As 库存,(Select Sum(数量) from [库存$] B Where B.序号<=A.序号) As 累计库存 from [库存$] A) As F
    复制代码
    5.3 取大于0的记录

    此处可以比较Q1和Q2,得到Q4
    1. Select 客户,仓库,Q3,IIF(Q1>Q2,Q2,Q1) As Q4 From
    2. (Select 客户,仓库,IIF(数量>库存,库存,数量) As Q3,累计库存-累计数量+数量 As Q1,累计数量-累计库存+库存 As Q2
    3. from
    4. (Select C.客户,C.数量,(Select Sum(数量) from [订单$] D Where D.序号<=C.序号) As 累计数量 from [订单$] C) As E
    5. ,(Select A.仓库,A.数量 As 库存,(Select Sum(数量) from [库存$] B Where B.序号<=A.序号) As 累计库存 from [库存$] A) As F)
    6. Where Q1>0 And Q2>0
    复制代码
    5.4 最终结果

    继续比较Q3和Q4,得到最终结果
    1. Select 客户,仓库,IIF(Q3>Q4,Q4,Q3) As 分配数量 From
    2. (Select 客户,仓库,Q3,IIF(Q1>Q2,Q2,Q1) As Q4 From
    3. (Select 客户,仓库,IIF(数量>库存,库存,数量) As Q3,累计库存-累计数量+数量 As Q1,累计数量-累计库存+库存 As Q2
    4. from
    5. (Select C.客户,C.数量,(Select Sum(数量) from [订单$] D Where D.序号<=C.序号) As 累计数量 from [订单$] C) As E
    6. ,(Select A.仓库,A.数量 As 库存,(Select Sum(数量) from [库存$] B Where B.序号<=A.序号) As 累计库存 from [库存$] A) As F)
    7. Where Q1>0 And Q2>0)
    复制代码
    参考附件下载:
    先进先出.rar (19.44 KB, 下载次数: 265)

    评分

    参与人数 1魅力值 +5 收起 理由
    + 5
    谢谢补充:)

    查看全部评分

     楼主| 发表于 2012-11-13 00:54:25 | 显示全部楼层
    本帖最后由 amulee 于 2012-11-13 01:15 编辑

    6、函数公式解法

    利用上述原理,用函数公式也可以得到结果。
    在函数解法中,由于没有笛卡尔积,只能运用二维数组运算获得。

    具体算法不在这里阐述了,和SQL步骤一样。

    懒得简化和合并了,因而用了辅助区域,大家感兴趣做一下。


    参考附件: 先进先出函数解法.rar (12.39 KB, 下载次数: 328)

    评分

    参与人数 3魅力值 +15 消费券 +50 收起 理由
    + 5
    + 50
    献上膝盖
    + 5
    思路巧妙:)
    + 5
    真心强大。

    查看全部评分

    发表于 2012-12-5 18:04:23 | 显示全部楼层
    精彩!
    发表于 2012-12-6 15:11:03 | 显示全部楼层
    非常感谢,拜读**!
    发表于 2012-12-6 16:07:47 | 显示全部楼层
    高手 高手 高高手
    发表于 2012-12-10 13:05:26 | 显示全部楼层
    强,我平时都用IF函数将相关资料进行分析
    您需要登录后才可以回帖 登录 | 注册

    本版积分规则

    关闭

    站长推荐上一条 /1 下一条

    Excel技巧网的会员探讨问题仅代表其个人意见,与网站的立场无关。任何违反国家和地方相关法律法规的言论,本站有义务协助政府相关部门追究发言者的责任!
    本站中非注明转载文章与案例的版权为作者与Excel技巧网共有。若非原文作者,本站之外任何单位或个人未经允许,不得将其用于商业用途。
    若非原文作者,任何形式的非商业性转载必须获得Excel技巧网或作者允许,并注明作者和出处。
    会员发表的帖子如涉及版权纠纷,须自行负责。详情请参考注册时的网站服务条款。
    本站特聘法律顾问:沈学律师