Solving for maximum value

Question

I have $x\ge983614$, $y\ge268877$ and $z\ge514175$.
Also I am told that the sum of $x+y+z$ can not be greater than $3500000$.
I am requested to find the values of $x,y,z$ such that $\max f(x,y,z) = 117x+125y+97z$.
In other words, I need to find the values of $x,y$ and $z$ such that I get the maximum solution of the above constraints.
Your assistance will be highly appreciated

Answer 1

This is a linear programming problem which can be easily solved.

If you have Matlab, just use the linear programming tool to solve it.

If you want to solve it by hand, use simplex method which you can find from the book. https://www.math.ucla.edu/~tom/LP.pdf.

Answer 2

Hint: Use the transformation $a = x - 983614$, $b = y - 268877$ and $c = z - 514175$ so that the decision variables $a,b,c$ becomes nonnegative (i.e. $a,b,c\ge0$), and the constraint becomes $a + b + c \le 1733334$.

The feasible region of $a+b+c\le K$ with $K$ fixed and $a,b,c\ge0$ is simply the pyramid with base $(0,0,0)$, $(K,0,0)$ and $(0,K,0)$ and vertex $(0,0,K)$. One of these four vertices of the feasible region will be an optimal solution.

Maximizing $f(x,y,z) = 117x+125y+97z$ is equivalent to maximizing $g(a,b,c) = 117a+125b+97c$. Since the coefficient of $b$ is largest, clearly $(a,b,c) = (0,1733334,0)$ is the unique optimal solution for this LP.

Hence $(x,y,z) = (983614, 2002211, 514175)$ is the unique optimal solution with optimum value $$f(x,y,z) = 117(983614)+125(2002211)+97(514175) = 415234188.$$

---

Remarks: We don't even need a computer program to find an optimal solution. Knowing the shape of the feasible region will do.