Welcome to our community

Be a part of something great, join today!

Linear Programming Problem using the Simplex Method

pHlawless

New member
Feb 11, 2013
7
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
Feb 24, 2012
13,775
I think I would use $x=2y$ instead, so that your first constraint becomes:

$3y+w\le210$

Let us know if that works.(Smile)
 

pHlawless

New member
Feb 11, 2013
7
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 (Worried)

Thanks,
Kyle
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Did you try rewriting your objective function too?

$z=2900y+750w$

subject to the constraints:

$3y+w\le210$

$30\le w$
 

pHlawless

New member
Feb 11, 2013
7
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
Jan 26, 2012
995
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
Feb 24, 2012
13,775
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." (Smile)
 

Chris L T521

Well-known member
Staff member
Jan 26, 2012
995
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." (Smile)
It's been about 4 years since I last took linear programming, but yea...I kinda know that feeling. ;P
 

pHlawless

New member
Feb 11, 2013
7
(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
Jan 26, 2012
995
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
Feb 24, 2012
13,775
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
Feb 11, 2013
7
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
Feb 24, 2012
13,775
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. (Smile)
 

Fernando Revilla

Well-known member
MHB Math Helper
Jan 29, 2012
661
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$.