Linear Programming Problem using the Simplex Method

In summary, the problem involves an electronics store trying to maximize their revenue by stocking VCRs, stereo systems, and television sets. They have limited storage space and must stock at least 30 TVs. The objective function is z=450x + 2000y + 750w and the constraints are x + y + w <= 210, w >= 30, and x-2y = 0. After using the Simplex Method Tool, it is determined that the optimal solution is x=120, y=60, and w=30, with a maximum revenue of $196500.
  • #1
pHlawless
7
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
  • #2
I think I would use $x=2y$ instead, so that your first constraint becomes:

$3y+w\le210$

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

$z=2900y+750w$

subject to the constraints:

$3y+w\le210$

$30\le w$
 
  • #5
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?
 
  • #6
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:
  • #7
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)
 
  • #8
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
 
  • #9
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$.
 

FAQ: Linear Programming Problem using the Simplex Method

What is the Simplex Method?

The Simplex Method is a mathematical technique used to solve linear programming problems. It involves creating a feasible solution and then iterating through a series of steps to improve the solution until an optimal solution is reached.

How is the Simplex Method used in linear programming problems?

The Simplex Method is used to solve linear programming problems by converting the problem into a standard form and then creating a feasible solution. The method then iteratively improves the solution by identifying the most optimal direction to move in until an optimal solution is reached.

What is the difference between the Simplex Method and other optimization techniques?

The Simplex Method is specifically designed for solving linear programming problems, while other optimization techniques may be used for a wider range of problems. Additionally, the Simplex Method is an iterative process, while other techniques may be more direct or use alternative approaches.

What are the steps involved in the Simplex Method?

The steps involved in the Simplex Method include converting the problem into standard form, creating a feasible solution, identifying the most optimal direction to move in, and then repeating this process until an optimal solution is reached. The method also involves checking for unboundedness and degeneracy at each iteration.

What are the limitations of the Simplex Method?

The Simplex Method may be computationally intensive for larger problems and may not always find the optimal solution. It also cannot handle problems with non-linear functions or constraints, and may struggle with problems that have a large number of variables and constraints.

Similar threads

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