算法只计算当年支出利息时的最大可能支出金额？

Question

我的头衔可能有点模糊，但我尽量把它弄清楚。我会在下面解释我的意思：

我想要创建一个动态规划算法，它可以计算出你可以花费的最大金额，当你每年能花的唯一的钱，就是你从银行得到的利息。也就是说，如果一个人的起始资本是35,000美元，这个人只能在10%的利率下最多花费3500美元。

我想到了以下几点：

兴趣i(t)或基本上是您可以花费的金额，在上面的示例中，这是3500。

支出e(t)，所以你当年花的钱，所以这可能是任何低于3500，作为一个例子，我将使用1000。

利率r，这本身就说明了问题。

公式：i(t + 1) = i(t) + r * (i(t) - e(t))，意思是你下一年可以花多少钱，就是你今年得到的利息加上你支出后剩下的利率乘以什么。

例如，我想计算的是，在10年期间，开支的最高金额，即某一年的开支总是低于所收取的利息。我不知道该怎么做，也不知道从哪里开始。

Answer 1

那么，让我们改革你的问题。有一个向量E=(e_1，e_2，.，e_n)。您希望在两个条件下使点积<(1,1，...,1);(E)>最大化。

(1) e_t >= 0/ t。

(2) e_t <= i_t。

由于右部pf (2)中的每个条件都可以扩展为e_t、i_0和r的线性组合(您给出了一个递归公式)，所以所有条件都可以写成

(2') e_t <= sumj=0..n A_tj e_j，或

(2'') c_t <= sumj=0..n B_tj e_j，其中B_tj和c_t是一些固定的比率，因此是一个n*n大小的矩阵和n个大小的向量。

所以，现在有一个经典的线性规划问题。我不会描述解决这些问题的所有技术，因为这里有很多这样的技术，而你的情况就是典型的。

UPD通过公式i(t+1) = (1 + r)i(t) - e(t)显式展开约束。

e(0) <= i(0)

e (1 ) <= i(1) = i(0) (1+ r) - e(0)

e(2) <= i(2) = i (1 ) (1 + r) - e (1 ) = (i(0) (1+ r) - e(0)) (1+ r) - e(1) =

i(0) (1 + r) ^2-e(0) (1 +r)- e(1)

它可以通过归纳来证明，但也可以看到

e(t) <= i(0) (1 + r) ^(0) (1 +r)^(t-1)-e (1 +r)^(t-2)-.-e(t-2) (1 +r)-e(t-1)-e(t-1)

对此进行改革

e(t) +和J=t-1.0^(t-1-j) e(j) <= i(0) (1 + r)^t

所以，我们有一个方阵：

• B_tj = (1 +r)^(t-1-j)表示j=0.t-1，
• B_tt =1
• J>t的B_tj =0

现在您的约束形式为sumj=0..n B_tj e(j) <= c_t

(显然，c_t = i(0) (1 + r)^t)

它是LP约束的规范形式。