代码之家  ›  专栏  ›  技术社区  ›  HMD

考虑运输约束和存储水平的CLSP优化算法

  •  0
  • HMD  · 技术社区  · 6 年前

    银行有自动取款机。对于特定的一周,现金的使用情况如下所示。

    • 5-星期一
    • 4-星期二
    • 1-星期三
    • 15-周四
    • 6-周五
    • 2-周六
    • 4-周日

    银行雇佣一家存款公司,每周存款5、3或1轮。

    存款公司向银行收取存款费用时提供以下套餐:,

    • 每月4轮存款的成本-21135

    • 每月12轮存款的成本-32000

    • 每月20轮存款的成本-41975

    订单保留为周一、周二、周三、周四、周五、周六、周日。在对值进行分类时,不应违反此顺序。

    实例

    • 5轮

    [(5+4),1, 15, 6, (2+4)]

    [(5+4), 1, (15+6)=20+1, 2, 4]

    可以有许多其他组合,不会破坏秩序。

    • 3轮

    [(5+4+1), 15, (6+2+4)]

    [(5+4), (1+15), (6+2+4)]

    可以有许多其他组合,不会破坏秩序。

    • 1轮

    [(5+4+1+15+6+2+4)]

    此外,银行必须在一天结束时承担剩余金额0.019%的持有成本。

    实例

    考虑第一周现金的使用情况如下。(以百万计)

    星期一至十三

    星期二-5

    星期三-4

    星期四至四

    星期五-2

    Sat-11

    太阳-1

    5轮

    第一周现金存款单-13,(5+4),4,(2+11),1

    假设一个月的4周内共有5轮存款, (5*4 = 20)

    总存款成本=41975

    1-13交存, 13人撤回, 剩下0个, 0持有成本

    2-(5+4)沉积, 5.撤回, 剩下4个, 4*0.00019持有成本

    3-0分, 4.撤回, 剩下0个, 0持有成本

    4-4交存, 4.撤回, 剩下0个, 0持有成本

    5-(2+11)沉积, 2.撤回, 剩下11个, 11*0.00019持有成本

    6-0交存, 11人撤回, 剩下0个, 0持有成本

    7-1交存, 1.撤回, 剩下0个, 0持有成本

    第一周的总持有成本=4*0.00019+11*0.00019=0.00285百万=2850

    同样,考虑到每个特定的星期,我需要找到当月的总持有成本。

    3轮

    第一周现金存款单-13,(5+4+4),(2+11+1)=(1+1+12)

    编辑-假设选择每月12轮套餐,因此每周3轮(3*4=12)

    总存款成本=32000

    1-13交存, 13人撤回, 0剩余,0持有成本

    2-(5+4+4)存入,5提取,(4+4)剩余,(4+4)*0.00019持有成本

    3-0存款、4提取、4剩余、4*0.00019持有成本

    4-0存款、4提取、0剩余、0持有成本

    5-(2+11+1)存入,2提取,(11+1)剩余,(11+1)*0.00019持有成本

    6-0存款,11提取,1剩余,1*0.00019持有成本

    7-0存款、1提取、0剩余、0持有成本

    第一周的总持有成本=(4+4)*0.00019+4*0.00019+(11+1)*0.00019+1*0.00019=0.00475百万=4750

    同样地,我需要找到每月的总持有成本。

    编辑-假设选择了41975包。那就意味着每月存入20轮的现金。这意味着每周5轮。如果选择32000包,则每月12轮。这意味着每周3轮。如果选择21135套餐,则意味着每月4轮,即每周1轮。在特定月份的四周内,不存在5,3,1的混合组合。只有所有的四周是在1、3或5轮中完成的。考虑到持有成本和包装成本,我们必须选择最好的包装。

    5轮不违反顺序的组合,可以比所有3轮和1轮的解决方案更好。同样适用于3轮解决方案。否则,一轮解决方案可能比所有5轮和3轮解决方案都好。

    当存款轮数增加时,持有成本降低,但存款成本增加。当轮次减少时,存款成本降低,但持有成本增加。因此,我需要找到每月每周的存款顺序和每月的存款方案,它可以在总持有成本和总存款成本之间进行很好的折衷,消耗最少的时间。

    对该方法的任何见解都将非常有用。

    1 回复  |  直到 6 年前
        1
  •  0
  •   ichantz    6 年前

    在你的情况下,你有一个 每月固定成本 (FMC) 还有 可变月成本 (VMC) 每种选择的包装。 FMC 在{x,x+10000,x+20000}中,而 VMC 是总的 每周可变成本 VWC 这四个星期。 VWC 通过将D=(M,T,W,T,F,S,S)的区间划分为k个不相交的子区间,其中k在{1,3,5}中。

    因此你必须选择min{ FMC1 + VMC1* , FMC3 + VMC3* , FMC5 + VMC5* },在哪里 VMCk* 表示将D划分为k个区间的最小可变月成本(注意,对于k=1的情况,答案很简单,因为每周都有一个分区)。因为每周的可变成本是 VWC = 0.7*( r1+r2+r3+r4+r5+r6+r7 ), 是一天的剩余时间 这一切归根结底都是为了尽量减少每周的剩余量。在计算 VMCk* 可以使用中描述的DP算法 this 纸张,目的是尽量减少每周的剩余量。

    所以在高层:

    1. 获得最低可变周成本->每包存款{1,3,5}每周使用DP的最低剩余金额。然后将每月的可变成本作为4周的总和。
    2. 从考虑每个包的固定成本和1时获得的可变成本中选择最小总成本。