MHB Linear Programming Problem using the Simplex Method

AI Thread Summary
The discussion revolves around solving a linear programming problem for an electronics store using the Simplex Method. The objective is to maximize revenue from VCRs, stereo systems, and television sets while adhering to constraints on storage and product ratios. The key constraints include a total stock limit of 210 units, a requirement for at least 30 television sets, and a ratio of two VCRs for every stereo system. Participants suggest various formulations of the constraints and objective function, ultimately confirming that the optimal solution is to stock 120 VCRs, 60 stereo systems, and 30 television sets, yielding maximum revenue of $196,500. The conversation highlights the importance of correctly formulating the problem for successful application of the Simplex Method.
pHlawless
Messages
7
Reaction score
0
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 >= 30The 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
 
Mathematics news on Phys.org
I think I would use $x=2y$ instead, so that your first constraint becomes:

$3y+w\le210$

Let us know if that works.(Smile)
 
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
 
Did you try rewriting your objective function too?

$z=2900y+750w$

subject to the constraints:

$3y+w\le210$

$30\le w$
 
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?
 
pHlawless said:
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:
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)
 
MarkFL said:
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
 
Chris L T521 said:
(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
 
  • #10
pHlawless said:
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
 
  • #11
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.
 
  • #12
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!
 
  • #13
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)
 
  • #14
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$.
 

Similar threads

Replies
6
Views
3K
Replies
3
Views
2K
Replies
44
Views
5K
Replies
1
Views
5K
Replies
4
Views
3K
Replies
1
Views
2K
Replies
8
Views
4K
Back
Top