更有效的产品销售动态规划

Question

我正在处理一个动态规划问题，这个问题需要在T期内销售一个产品，并使实际销售总量最大化。产品总数为N，I计划在不同时期( n0、n1、⋯、nT−1和∑ni=N )销售部分产品，但实际销售金额Si和销售价格Pi则是基于以下公式。假设α=0.001和π=0.5

1. 初始化P=0。那么对于i=0,1，…计算新Pi=⌈0.5∗(Pi+ni)⌉
2. At时间i我们出售Si =⌈(1−αP^π)*ni⌉products

例如，假设我们已经知道所有时期的$n_i$，则交易将低于

    P = 0
    T = 4
    N = 10000
    alpha = 1e-3
    pi = 0.5
    S = np.zeros(T,dtype='i')
    n  = np.array([5000,1000,2000,2000])
    print(n)
    total = 0
    for i in range(T):
        P = math.ceil(0.5*(P + n[i]))
        S[i] = math.ceil((1 - alpha*P**pi)*n[i])
        total += S[i]
        print('at time %d, M = %d and we trade %d shares' %(i,M,S[i]))
    print('total sold =', total)

我的想法是这个问题处理的是数量而不是价格。因此，我们应该关注与数量有关的东西，比如数量的移动平均值。我还在考虑怎么给它编程。有人能提供关于动态规划的想法吗？非常感谢。下面是我的一些粗略代码。

def DPcrude(N,T,alpha,pi,S):
    for k in range(1, T):
        t = T - k - 1
        for n in range(0,N+1):
            best = -1

            for sell in range(0,n):
                newprice = 
                salenow = 
                salelater = 
                candidate = salenow + salelater
                if candidate > best:
                    best = candidate
            S[t,a,n] = best

N = 1000
T = 10
pi = .5
alpha = 1e-2

Answer 1

当前方法的复杂性为O(N^T)。动态规划可用于将其降为O(T.N^3)，而对于T值为4或更高的值，则更有效。

请注意，该问题具有以下属性：

1. 价格上涨导致销售减少
2. 某一特定时间的较高价格会导致更高的价格(如果随后对ni作出相同的选择)

这意味着您可以通过动态规划来解决子问题，即每个销售数量的最低价格是多少：

具有精确t个时间周期的

2. ，t时间周期的ni求和为n

要计算这个子问题，需要在最后一段时间内循环对数字的选择，并结合以前子问题中的选择。

请注意，解决子问题会给出最多N个结果的数组，其中，数组中的输入k给出了获得精确的k销售的最低价格。

存在O(T.N)子问题，每一个子问题都需要O(N^2)来求解，复杂度为O(T.N^3)。

Answer 2

除非您能够应用一些数学魔法来限制价格P的影响，否则您将无法将动态规划应用到这个问题上。

动态规划依赖于具有最优子结构性质的问题。维基百科：

在计算机科学中，如果一个问题的最优解可以由其子问题的最优解构造，那么它就被称为具有最优子结构。

但是，您的问题没有显示此属性--如果我们计算T间隔和N项的最优解，则不能对T+1间隔和N+K项使用该解决方案，因为T+1问题中的价格取决于T区间价格。价格较高的P (对于最后一个区间)但总体上不太理想的利润的子解仍然可以用来构造T+1的最优利润，因为价格P增加了。这使我们无法应用动态编程。