How to maximize objective function $z=xy$ where $x$ and $y$ can take only integer values

Question

I want to maximize the value of product of $x$ and $y$ where $x$ and $y$ can take only integer values as well as there are some constraints as mentioned below :

$$x+\alpha y \le N \textrm{ and } x>0,\ y>0$$

where $\alpha$ and $N$ are known constants and could be very large. How to solve such a problem ?

Answer 1

The function $$f(y):=y(N-\alpha y)={N^2\over 4\alpha}-\alpha\left(y-{N\over2\alpha}\right)^2$$ is unimodal and takes its maximum at $y_*:={N\over2\alpha}$. The optimal integer value of $y$ therefore is one of $\lfloor y_*\rfloor$ and $\lceil y_*\rceil$.

(Unimodal means: increasing till the max, then decreasing.)

Answer 2

Let $f=xy$ when $x>0,y>0$ $f$ is a increment function and symmetric to the plain $x-y=0$. The condition $x+\alpha y \leq N$ implies that the range of points (x,y) are below the line $x+\alpha y = N$. So now, the range is a triangular. Now it is only have to consider the edge of triangular. It obvious that the two sides x=0 and y=0 is not a maximum value,so we need to take third edge. Replacing x in $f=xy$ by $x+\alpha y=N$ we have

$f=y(N-\alpha y)$.

so it is easy to find the max value of this parabola.