# Linear Programming Problem using the Simplex Method

#### pHlawless

##### New member
Here is my story problem:

An electronics store stocks VCRs, stereo systems, and television sets. They have limited storage space and can stock a total of at most 210 of these three machines. They know from past experience that they should stock twice as many VCRs as stereo systems and at least 30 television sets. If each VCR sells for $450, each stereo system sells for$2000, and each television set sells for $750, how many of each should be stocked and sold for maximum revenues? My professor has us using this site to solve these problems: Simplex Method Tool Here is what I have so far: My objective function is z= 450x + 2000y + 750w My constraints are: x + y + w <= 210 w >= 30 The problem I am having is I am unsure as to how to incorporate the condition of there being twice as many VCRs as stereo systems. Obviously y = 1/2x. I tried to change my first inequality to 3/2x + w <= 210 (Since y = 1/2x and x = 2/2x then x + y = 3/2x) but this website calculator didn't seem to like that. Any idea where I'm going wrong here? Thanks for the help, Kyle #### MarkFL ##### Administrator Staff member I think I would use$x=2y$instead, so that your first constraint becomes:$3y+w\le210$Let us know if that works. #### pHlawless ##### New member Hey Mark, Thanks for the response. I tried that as well on the website and it keeps returning "No optimal solution exists for this problem." Common sense and ability to do the problem in my head tells me the answer is more than likely x=120, y=60 and w=30. I just need to know how to put that into inequalities somehow for full credit on this problem Thanks, Kyle #### MarkFL ##### Administrator Staff member Did you try rewriting your objective function too?$z=2900y+750w$subject to the constraints:$3y+w\le21030\le w$#### pHlawless ##### New member Thanks Mark, that did give me the correct answer. However, I feel like this is a workaround of some sorts. Is there another inequality or something I could add so I wouldn't have to get rid of my x variable? #### Chris L T521 ##### Well-known member Staff member Thanks Mark, that did give me the correct answer. However, I feel like this is a workaround of some sorts. Is there another inequality or something I could add so I wouldn't have to get rid of my x variable? (Don't mean to steal your thunder Mark) If you leave all three variables in, the LP problem that you want to solve is: Maximize:$z=450x+2000y+750w$subject to$\begin{cases}x+y+w\leq 210\\ x-2y = 0\\ w\geq 30\\ x,y,w\geq 0\end{cases}$Last edited: #### MarkFL ##### Administrator Staff member Hey Chris, glad to have your input to see the problem properly stated, as it has been 20 years since I have done any linear programming, and like the OP I felt I was "cheating." #### Chris L T521 ##### Well-known member Staff member Hey Chris, glad to have your input to see the problem properly stated, as it has been 20 years since I have done any linear programming, and like the OP I felt I was "cheating." It's been about 4 years since I last took linear programming, but yea...I kinda know that feeling. ;P #### pHlawless ##### New member (Don't mean to steal your thunder Mark) If you leave all three variables in, the LP problem that you want to solve is: Maximize:$z=450x+2000y+750w$subject to$\begin{cases}x+y+w\leq 210\\ x-2y = 0\\ w\geq 30\end{cases}$While that third condition you added makes perfect sense to me, this website just doesn't want to accept it. I'm assuming because it doesn't have a greater/less than sign? Sorry to be a pain here... Simplex Method Tool Here is what I am inputting for my linear programming: maximize z = 450x 2000y + 750w subject to x + y + w <= 210, w >= 30, x - 2y = 0 I've used this website (Professor has showed us and told us to use) on many different problems and never had an issue, however I've never had to use an "=" with no ">,<". Thanks again, Kyle #### Chris L T521 ##### Well-known member Staff member While that third condition you added makes perfect sense to me, this website just doesn't want to accept it. I'm assuming because it doesn't have a greater/less than sign? Sorry to be a pain here... Simplex Method Tool Here is what I am inputting for my linear programming: maximize z = 450x 2000y + 750w subject to x + y + w <= 210, w >= 30, x - 2y = 0 I've used this website (Professor has showed us and told us to use) on many different problems and never had an issue, however I've never had to use an "=" with no ">,<". Thanks again, Kyle Interesting, because I had no problem with this. Copy the following and it should work: Code: Maximize p = 450x + 2000y + 750z subject to x + y + z <= 210 x-2y = 0 z >= 30 It gives me the following: Code: Optimal Solution: p = 196500; x = 120, y = 60, z = 30 #### MarkFL ##### Administrator Staff member I ran the app you linked to and used: maximize z = 450x + 2000y + 750w subject to x + y + w <= 210, w >= 30, x - 2y = 0 (notice the "+" between 450x and 2000y you left out) and it gave me a solution. #### pHlawless ##### New member Wow, through all of that editing of my objective function I was missing a plus sign. That's depressing. Thanks for all of the help gentlemen, it was greatly appreciated! #### MarkFL ##### Administrator Staff member Glad to help, Kyle, and please don't ever feel you are being a pain by asking questions...we are more than happy to help. #### Fernando Revilla ##### Well-known member MHB Math Helper Although the problem has been solved, I write a version of the simplex method. The problem is equivalent to maximize$z=2900y+750w$with the constraints:$\left \{ \begin{matrix} 3y+w\leq 210\\w\leq 30 \\y\geq 0,\;w\geq 0\end{matrix}\right.$We write the problem in standard form:$\left \{ \begin{matrix} 3y+w+x_1= 210\\w-x_2= 30 \\y\geq 0,\;w\geq 0,x_1\geq 0,x_2\geq 0\end{matrix}\right.$And now, the simplex algorithm:$\left[\begin{array}{ccccc|c}
3 & 1 & 1 &0 & 0 & 210\\
30& 1 & 0 &-1 & 0 & 30\\
-2900 & -750 & 0 &0 & 1 & 0
\end{array}\right]\left[\begin{array}{ccccc|c}
\boxed{1} & 1/3 & 1/3 &0 & 0 & 70\\
0& 1 & 0 &-1 & 0 & 30\\
-2900 & -750 & 0 &0 & 1 & 0
\end{array}\right]\left[\begin{array}{ccccc|c}
\boxed{1} & 1/3 & 1/3 &0 & 0 & 70\\
0& 1 & 0 &-1 & 0 & 30\\
0 & 650/3 & 2900/3 &0 & 1 & 203000
\end{array}\right]\left[\begin{array}{ccccc|c}
\boxed{1} & 0 & 1/3 &1/3 & 0 & 60\\
0& \boxed{1} & 0 &-1 & 0 & 30\\
0 & 0 & 8050/3 &650/3 & 1 & 19650
\end{array}\right]$An optimal basic feasible solution is$(y,w,x_1,x_2)^t=(60,30,0,0)^t$and$z_{\max}[(60,30,0,0)^t]=19650$. Equivalently, we get the maximum at$x=120,y=60,w=30$and the maximun is$19650\$.