Optimization of profit in Ruby

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.

For given constants a and b, let

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

We wish to maximize f(j,k) subject to three requirements:

• j + k = d, for a given constant d
• j >= 0
• k >= 0

We can substitute out k (or j) to by replacing k with

k = d - j

This changes f to:

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

The problem is now to maximize f subject to:

0 <= j <= d

The second part of this inequality follows from k = d - j >= 0. If d = 0, j = k = 0 is the only solution that satisfies the requirement that the variables are non-negative. If d < 0 there is no feasible solution. These two cases should be checked for but I will assume d > 0.

We first set the derivative of f to zero and solve for j to determine where f's slope is zero:

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

so

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

As the second derivative of f is

f''(j) = -2 < 0

we know f is concave, so j* is a maximum (rather than a minimum were it convex). Convex and concave functions are shown here¹:

Consider the graph of the concave function. Values of j are on the horizontal axis. Since j* must be between 0 and d to be feasible (both variables have non-negative values), let the points a, c and b on the graph equal 0, j* and d, respectively.

There are three possibilities:

• 0 <= j* <= d, in which case that is a feasible solution (since k = d - j* >= 0).
• j* < 0, in which case the largest feasible value of f is where j = 0.
• j* > d, in which case the largest feasible value of f is where j = d.

Once the optimum value of j has been determined, k = d - j

Here are some examples.

Ex. 1: a = 2, b = 3, d = 5

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

Since 0 <= 3 <= 5, j = 3, k = 5 - 3 = 2 are the optimum values of j and k and f(3) = 25 is the optimum value.

Ex. 2: a = 6, b = 1, d = 3

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

Since -1 < 0, j = 0, k = 3 - 0 = 3 are the optimum values of j and k and f(0) = 24 is the optimum value.

Ex. 3: a = 2, b = 7, d = 3

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

Since 4 < 3, j = 3, k = 3 - 3 = 0 is the optimum value of j and f(3) = 35 is the optimum value.

If j and k must be integer-valued at the maximum value of f, we can assume a, b and d are integer-valued. (If a and b are not, a can be rounded up and b rounded down.) Let j* now be the value of j satisfying 0 <= j <= d for which is f(j) is a maximum (but j* is not necessarily an integer). Because f is concave, if j* is not integer, the optimal value of j is J*.floor if f(j*.floor) >= f(j*.ceil) and j*.ceil otherwise.

^{1 A function f is concave if, for all a and b, a < b, and all x, a <= x <= b, f(x) >= g(x), where g is the linear function having the property that g(a) = f(a) and g(b) = f(b).}