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
Asked
Active
Viewed 110 times
0
GNUSupporter 8964民主女神 地下教會
- 17,627
-
Is there a distinction between $X$ and $x$? If not then you obviously want $Y=3500000$ and then $f=3500000\cdot125$. – almagest Feb 06 '18 at 18:50
-
if i understand this right you can use the $AM-GM$ inequality here – Dr. Sonnhard Graubner Feb 06 '18 at 18:51
-
@Dr.SonnhardGraubner I would like to see such proof for fun. – GNUSupporter 8964民主女神 地下教會 Feb 06 '18 at 21:12
2 Answers
0
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.
-
1Practical side: OP probably doesn't have MATLAB due to its license fee. Why don't we recommend a free and libre version with compatible syntax so that he/she can run MATLAB code with Octave Online? To be more specific, run
glpk(GNU Linear Programming Kit) on that site to numerically solve LP problems. Theoretical side: A more basic way to solve this LP is to apply the Fundamental Theorem of Linear Programming to the reduced LP. – GNUSupporter 8964民主女神 地下教會 Feb 06 '18 at 21:49
0
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.
GNUSupporter 8964民主女神 地下教會
- 17,627