Ruby 中的利润优化

Question

我正在使用 Ruby，但对于这个问题来说，这并不重要。

假设我有两种不同类型的资源，其数量用 a 和 b 表示。我可以分配 d 新资源，并且由于 a 和 b 的生产成本和价值相同，我可以选择以最有利可图的方式分配资源。

最好这样解释：(a + j) * (b + k) = c，其中 j + k = d。我想通过最佳资源分配来最大化 c，同时理解这两种不同类型资源的成本及其生产价值是相同的。所有变量都是正整数，a 和 b 都大于 0。这是我天真的暴力破解方法：

def max_alloc(a, b, d)
  max_j = 0
  max_k = 0
  max_c = 0
  (0..d).each do |j|
    k = d - j
    c = (a + j) * (b + k)
    if c > max_c
      max_c = c
      max_j = j
      max_k = k
    end
  end
  [max_j, max_k]
end

我希望有某种数学或算法 "trick" 我想念它可以让我不必诉诸蛮力。

Answer 1

你真的需要算法来做到这一点吗？这是一个简单的 maximum/minimum 优化问题。

现在考虑等式

它是j的一个函数，所以我们称它为f(j):

你想找到 j 使得 c = f(j) 最大...所以你想研究它的导数符号

现在可以画table个符号了

给你！

的最大值

这意味着您正在寻找的j, k对是

对于这样的值，您将获得最大值 c:

在Ruby

def max_alloc(a, b, d)
    j = (-a + b + d) / 2.0
    j = j.round # round to prevent Float, explained at the end of this answer
    if j < 0
        j = 0 # prevent from negative values
    elsif j > d
        j = d # prevent from values greater than d
    end
    [j, d - j]
end

甚至更短

def max_alloc(a, b, d)
    j = ((-a + b + d) / 2.0).round
    j = [0, [j, d].min].max # make sure j is in range 0..d
    [j, d - j]
end

如果你喜欢也可以单行

def max_alloc(a, b, d)
    [[0, [((-a + b + d) / 2.0).round, d].min].max, d - [0, [((-a + b + d) / 2.0).round, d].min].max]
end

深入了解案例 `j < 0` 和 `j > d`

让我们从j必须满足的边界开始：

所以j*是：

现在，由于f(j)总是一条向下开口的抛物线，绝对最大值将是它的顶点，所以，如前所述：

但是如果这个点超出了j的给定范围怎么办？您必须决定选择 j* = 0, k* = d 还是 j* = d, k* = 0。

由于 f(j) 对 j < j* 严格递增，对 j > j* 严格递减，因此越接近 j*，f(j) 就越大值。

因此，如果j* > d选择j* = d，如果j* < 0选择j = 0。

这里我展示了一些图表，只是为了看看实际效果：

为什么 `j.round`？

正如你刚刚了解到的，f(j)是一条抛物线，抛物线有一条对称轴。如果 j* 是一个整数，你就完成了，否则 f(j) 最大的整数值是多少？好吧...对于最接近顶点的整数值；即 j.round.

注意：如果a, b和d是整数，那么j*只能是整数或xxx.5。所以 f(j) 对于 j.ceil 和 j.floor 是一样的...你选择。

Answer 2

对于给定的常量 a 和 b，设

f(j,k) = (a + j) * (b + k)

我们希望最大化 f(j,k) 满足三个要求：

j + k = d，对于给定常数 d
j >= 0
k >= 0

我们可以用

替换k来替换k（或j）

k = d - j

这会将 f 更改为：

f(j) = (a + j) * (b + d - j)
     = a*(b + d) + (b + d - a)*j -j**2

现在的问题是最大化 f 受制于：

0 <= j <= d

此不等式的第二部分来自 k = d - j >= 0。如果 d = 0，j = k = 0 是唯一满足变量非负要求的解。如果d < 0无可行解。应该检查这两种情况，但我会假设 d > 0.

我们首先将f的导数设为零并求解j以确定f的斜率为零的位置：

f'(j) = b + d - a - 2*j = 0

所以

j* = (b + d - a)/2

因为f的二阶导数是

f''(j) = -2 < 0

我们知道 f 是凹的，所以 j* 是最大值（而不是凸的最小值）。此处显示凸函数和凹函数¹:

考虑凹函数的图形。 j 的值在水平轴上。由于 j* 必须在 0 和 d 之间才可行（两个变量都有非负值），让点 a、c 和 [=图表上的 21=] 分别等于 0、j* 和 d。

三种可能：

0 <= j* <= d，在这种情况下，这是一个可行的解决方案（因为 k = d - j* >= 0）。
j* < 0，在这种情况下，f 的最大可行值是 j = 0.
j* > d，在这种情况下，f 的最大可行值是 j = d.

确定j的最佳值后，k = d - j

这里有一些例子。

例如。 1: a = 2, b = 3, d = 5

j* = (b + d - a)/2 = (3 + 5 - 2)/2 = 3

因为0 <= 3 <= 5、j = 3、k = 5 - 3 = 2是j的最优值，而k和f(3) = 25是最优值。

例如。 2: a = 6, b = 1, d = 3

j* = (b + d - a)/2 = (1 + 3 - 6)/2 = -1

因为-1 < 0、j = 0、k = 3 - 0 = 3是j的最优值，而k和f(0) = 24是最优值。

例如。 3: a = 2, b = 7, d = 3

j* = (b + d - a)/2 = (7 + 3 - 2)/2 = 4

由于4 < 3、j = 3、k = 3 - 3 = 0是j的最佳值，f(3) = 35是最佳值。

如果j和k必须是最大值f的整数值，我们可以假设a、b和d 是整数值。（如果 a 和 b 不是，则 a 可以向上舍入， b 向下舍入。）现在让 j* 成为 [=28= 的值] 满足 0 <= j <= d 其中 f(j) 是最大值（但 j* 不一定是整数）。因为f是凹的，如果j*不是整数，如果f(j*.floor) >= f(j*.ceil)，j的最优值是J*.floor，否则j*.ceil。

^{1 如果对于所有 a 和 b、a < b 以及所有 x，函数 f 是凹的， a <= x <= b、f(x) >= g(x)，其中 g 是具有属性且 g(a) = f(a) 和 g(b) = f(b) 的线性函数。}

Ruby 中的利润优化

Optimization of profit in Ruby

ruby

algorithm

mathematical-optimization

在Ruby

深入了解案例 `j < 0` 和 `j > d`

为什么 `j.round`？

Ruby 中的利润优化

Optimization of profit in Ruby

ruby

algorithm

mathematical-optimization

在Ruby

深入了解案例 j < 0 和 j > d

为什么 j.round？

深入了解案例 `j < 0` 和 `j > d`

为什么 `j.round`？