Optimization of profit in Ruby

Question

I'm using Ruby, but for the purposes of this problem it doesn't really matter.

Let's say I have two different kinds of resources, the quantities of which are denoted by a and b. I can allocate d new resources, and since a and b are of equal cost and equal value to production, I can choose to allocate resources in whatever way is most profitable.

This might best be explained like so: (a + j) * (b + k) = c, where j + k = d. I want to maximize c by the best allocation of resources, with the understanding that the cost of the two different types of resources and their value to production are the same. All variables are positive integers, with a and b being greater than 0. Here's my naive brute force method:

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

I'm hoping that there's some sort of mathematical or algorithmic "trick" I'm missing that will keep me from having to resort to brute force.

Answer 1

Do you really need an algorithm to do that? This is a simple maximum/minimum optimization problem.

Now consider the equation

It is a function of j, so let's call it f(j):

You want to find j such that c = f(j) is maximum... so you want to study the sign of it's derivative

Now you can draw the table of signs

There you have it! A maximum for

this means the j, k pair you are looking for is

and for such values you'll have the maximum value of c:

---

In 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

Or even shorter

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

A one-liner too if you like

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

---

An in-depth look at the cases j < 0 and j > d

Let's start from the bounds that j must satisfy:

So j* is:

Now, since f(j) is always a parabola opened downward, the absolute maximum will be it's vertex, so, as discovered before:

But what if this point is outside the given range for j? You'll have to decide wheter to chose j* = 0, k* = d or j* = d, k* = 0.

Since f(j) is strictly increasing for j < j* and strictly descreasing for j > j*, the closer you get to j*, the greater would be f(j) value.

Therefore, if j* > d the choose j* = d, if j* < 0 then choose j = 0.

Here I show some plots just to see this in action:

---

Why j.round?

As you just learned f(j) is a parabola, and parabolas have an axis of symmetry. If j* is an integer, you are done, otherwise for what integer value is f(j) maximized? Well... for the integer value closest to the vertex; i.e., j.round.

Note: If a, b and d are integers, then j* can only be an integer or xxx.5. So f(j) would be the same for j.ceil and j.floor... You choose.