MHB Solving Linear Programming Problems Graphically

AI Thread Summary
The discussion focuses on solving a linear programming problem graphically, specifically maximizing the function (x-y) under given constraints. Participants clarify the correct interpretation of the line equations, particularly distinguishing between 2x-y=2 and 2x+y=2. After correcting the graph, they identify the optimal solution at the point C(4,0). The conversation concludes with an acknowledgment of the graphical method's sufficiency and a mention of the formal simplex method for further analysis. Overall, the group successfully navigates the graphical solution process and confirms the optimal point.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
The following linear programming problem is given and I want to solve it graphically.

$$\max (x-y) \\ x+y \leq 4 \\ 2x-y \geq 2 \\ x,y \geq 0$$

I have drawed the lines :

$$(\ell_1) x+y=4 \\ (\ell_2) 2x-y=2 \\ (\ell_3) x=0 \\ (\ell_4) y=0$$

as follows:

View attachment 5092I have drawed the line $2x-y=0$ taking into consideration the following:

For $y=0 \Rightarrow x=1$ and for $y=2 \Rightarrow x=\frac{1}{2}$.But I found that this is the graph of $2x-y=2$ :View attachment 5093

So are the points that I have found above wrong? Or where is my mistake? (Thinking)
 

Attachments

  • gr22.png
    gr22.png
    3.6 KB · Views: 110
  • gr44.JPG
    gr44.JPG
    39.7 KB · Views: 114
Physics news on Phys.org
Hey evinda! (Smile)

In your drawing you have the line $2x+y=2$ instead of the line $2x-y=2$. :eek:
 
I like Serena said:
Hey evinda! (Smile)

In your drawing you have the line $2x+y=2$ instead of the line $2x-y=2$. :eek:

If we take pick $y=0$ we get $x=1$ and if we pick $y=2$ we get $x=2$.

Then we would get a line like this:
View attachment 5094

But picking $y=-2 \Rightarrow x=0$ and $y=1 \Rightarrow x=\frac{3}{2}$ we get a line as below:

View attachment 5095

Or am I wrong? (Thinking)
 

Attachments

  • l1.png
    l1.png
    328 bytes · Views: 92
  • l2.png
    l2.png
    311 bytes · Views: 108
Your first line is for $2x+y=2$ while the second is for $2x-y=2$.
It should be like the second.

Note that if we substitute $y=2$ in $2x-y=2$, we get $-2=2$.
 
I like Serena said:
Your first line is for $2x+y=2$ while the second is for $2x-y=2$.
It should be like the second.

Note that if we substitute $y=2$ in $2x-y=2$, we get $-2=2$.

Yes, I noticed it too now... I am sorry... Thank you! (Smile)

I will try to find now the optimal solution...
 
We also draw at the same graph the line $x-y=0$.
We consider the line $x-y=\lambda, \lambda>0$ where $\lambda$ is increasing.

View attachment 5096

Do we deduce from the graph that the optimal solution is $C(4,0)$ since it is the last line? (Thinking)
 

Attachments

  • fre.png
    fre.png
    8.4 KB · Views: 100
evinda said:
Do we deduce from the graph that the optimal solution is $C(4,0)$ since it is the last line? (Thinking)

Yep. (Nod)
 
I like Serena said:
Yep. (Nod)

Nice...And how could we explain it more formally? (Thinking)
 
evinda said:
Nice...And how could we explain it more formally? (Thinking)

Erm... I believe that for the graphical method this is pretty much it.
The formal method is with a simplex tableau. (Emo)
 
  • #10
I like Serena said:
Erm... I believe that for the graphical method this is pretty much it.
The formal method is with a simplex tableau. (Emo)

A ok... Thanks a lot! (Smirk)
 
Back
Top