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

Question

我正在研究一个动态规划问题，这个问题要求在T个时间段内销售产品，并使实际销售总额最大化。产品总数为N，我计划在不同时期(N,n1，⋯，nT−1，∑ni=N)销售一些产品。但实际销售金额Si和销售价格Pi是根据以下公式计算的。假设α=0.001， π=0.5

1. 初始化P = 0。则对于i=0,1，…，T−1
2. 计算新的Pi=<0.5∗(Pi+ni)
3. 时间i我们销售Si =(1−αP^π)*ni²产品

例如，假设我们已经知道所有期间的$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

你当前的方法复杂度为0 (N^T)。动态规划可以将其减少到O(tn ^3)，这对于T = 4或更高的值应该更有效。

注意这个问题有以下属性:

1. 价格越高，销量越少
2. 特定时间的高价格导致随后的高价格(如果对ni做出相同的后续选择)

这意味着你可以用动态规划来解决子问题:对于每个销售数量，最低价格是多少:

1. 正好有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增加了。这使我们无法应用动态规划。