# Thread: LP help

1. ## LP help

Q1: Suppose that the following constraints have been provided for a linear programming model.

$\displaystyle -x_{1}+2x_{2}\leq\\50$ (1)
$\displaystyle -2x_{1}+x_{2}\leq\\50$ (2)

and

$\displaystyle x_{1}\geq\\0, x_{2}\geq\\0$.

a) Demonstrate that the feasible region is unbounded.
b) If the objective is to maximize $\displaystyle Z=-x_{1}+x_{2}$, does that model have an optimal soultion? If so, find it. If now, explain why not.
c) Repeat part (b) when the objective is to maximize $\displaystyle Z=x_{1}-x_{2}$.

Does "unbounded" mean something specific when dealing with LP problems? When, I graph the above lines, I am not sure where the feasible region is, since the inequality tells me to shade below both lines in the first quadrant. Furthermore, since line (2) is above line (1) I have to shade over line (1) down to the horizontal axis, which doesn't seem right, as that would mean the constraints are not being satisfied. Does this mean the the feasible region is unbouned? Also,

Moreover, if the feasible region is unbouned and the gradiants of both objective functions from parts (b) and (c) are in directions away from the first quadrant, how can there be optimal solutions?

Q2: Minimize $\displaystyle Z=15x_{1}+20x_{2}$

subject to:

$\displaystyle x_{1}+2x_{2}\geq\\10$ (1)
$\displaystyle 2x_{1}-3x_{2}\leq\\6$ (2)
$\displaystyle x_{1}+x_{2}\leq\\6$ (3)

and $\displaystyle x_{1}\geq\\0,x_{2}\geq\\0$.

For this question, I am also not sure where my feasible region is (or if one even exists). I have graphed all the lines and drawn arrows in the direction of the inequality signs, but I am not sure where to shade. I am assuming this means there is no feasible region.

Should I be checking to makie sure the inequalities hold or do I just assume they do and and shade above or below the lines accordingly?

Thanks in advanced for your time

disclaimer: My entire second week of class has been cancled due to snow days, so I only have one example of how to solve an LP in my notes and have yet to recieve my text book. Thats my excuse for these elementary questions....

2. ## Linear Programming

Hello Danneedshelp
Originally Posted by Danneedshelp
Q1: Suppose that the following constraints have been provided for a linear programming model.

$\displaystyle -x_{1}+2x_{2}\leq\\50$ (1)
$\displaystyle -2x_{1}+x_{2}\leq\\50$ (2)

and

$\displaystyle x_{1}\geq\\0, x_{2}\geq\\0$.

a) Demonstrate that the feasible region is unbounded.
b) If the objective is to maximize $\displaystyle Z=-x_{1}+x_{2}$, does that model have an optimal soultion? If so, find it. If now, explain why not.
c) Repeat part (b) when the objective is to maximize $\displaystyle Z=x_{1}-x_{2}$.

Does "unbounded" mean something specific when dealing with LP problems? When, I graph the above lines, I am not sure where the feasible region is, since the inequality tells me to shade below both lines in the first quadrant. Furthermore, since line (2) is above line (1) I have to shade over line (1) down to the horizontal axis, which doesn't seem right, as that would mean the constraints are not being satisfied. Does this mean the the feasible region is unbouned? Also,

Moreover, if the feasible region is unbouned and the gradiants of both objective functions from parts (b) and (c) are in directions away from the first quadrant, how can there be optimal solutions?
(a) You're right in saying that the shading for line (2) goes over all the shading for line (1), leaving the feasible region just the same as that obtained by line (1) together with $\displaystyle x_1\ge0, x_2\ge0$.

This region extends infinitely far to the right and upwards, and so is unbounded. In other words, you can find values of $\displaystyle x_1$ and $\displaystyle x_2$ as large as you like and both inequalities will be satisfied. For example, if you want to make $\displaystyle x_2 = 1\,000\,000$, just take $\displaystyle x_1 = 2\,000\,000$, and both inequalities are satisfied.

It's very easy to decide which side of the line to shade. Choose a point not on the line (if the line doesn't pass through the origin, then choose the origin), and check to see whether the condition is satisfied at this point. If it is, shade that side; if not, shade the other side.

So for both (1) and (2), the values $\displaystyle x_1 = 0 = x_2$ satisfy both inequalities. Therefore the origin is on the side to be shaded in each case.

(b) To maximise $\displaystyle Z = -x_1+x_2$, draw the line $\displaystyle -x_1+x_2 = 0$ (in other words, the line $\displaystyle x_1 = x_2$) and then try to find the line parallel to that whose intercept with the $\displaystyle x_2$ axis is as large as possible, subject to at least one point on the line lying within the shaded region. This intercept is at $\displaystyle (0,25)$ giving a maximum value $\displaystyle Z = 25$.

(c) We draw the same line again ($\displaystyle x_1=x_2$), but this time, since $\displaystyle x_2 = x_1-Z$, we need to make the intercept as far down as possible, to make $\displaystyle Z$ a maximum. Since the region is unbounded to the right, there is no limit to the lowest intercept possible. Hence $\displaystyle Z$ can be made as large as you like. (In the example that I gave above, $\displaystyle Z = 2\,000\,000-1\,000\,000 = 1\,000\,000$, for instance.)

Q2: Minimize $\displaystyle Z=15x_{1}+20x_{2}$

subject to:

$\displaystyle x_{1}+2x_{2}\geq\\10$ (1)
$\displaystyle 2x_{1}-3x_{2}\leq\\6$ (2)
$\displaystyle x_{1}+x_{2}\leq\\6$ (3)

and $\displaystyle x_{1}\geq\\0,x_{2}\geq\\0$.

For this question, I am also not sure where my feasible region is (or if one even exists). I have graphed all the lines and drawn arrows in the direction of the inequality signs, but I am not sure where to shade. I am assuming this means there is no feasible region.

Should I be checking to makie sure the inequalities hold or do I just assume they do and and shade above or below the lines accordingly?

Thanks in advanced for your time

disclaimer: My entire second week of class has been cancled due to snow days, so I only have one example of how to solve an LP in my notes and have yet to recieve my text book. Thats my excuse for these elementary questions....
Look at the diagram I've attached.

Using the technique I outlined above, choosing the origin as my test point, I found the origin is on the 'wrong' side of line (1), but it's on the 'right' side of lines (2) and (3). Hence the only feasible area is the triangle I've shaded.

I've drawn in the optimum '$\displaystyle Z$ line' to make $\displaystyle Z$ a minimum. This is the line that passes through $\displaystyle (0,5)$, giving the minimum value of $\displaystyle Z = 100$.

Grandad

3. Originally Posted by Grandad

Look at the diagram I've attached.

Using the technique I outlined above, choosing the origin as my test point, I found the origin is on the 'wrong' side of line (1), but it's on the 'right' side of lines (2) and (3). Hence the only feasible area is the triangle I've shaded.

I've drawn in the optimum '$\displaystyle Z$ line' to make $\displaystyle Z$ a minimum. This is the line that passes through $\displaystyle (0,5)$, giving the minimum value of $\displaystyle Z = 100$.

Grandad
Thank you very much for all your help and time.

I do have one last question though. I am not seeing how you got the feasible region illustrated in the above attachment, since we are concerend with the region below line (2). In you illustration, the afore mentioned constraint isn't accounted for, correct?

Nevertheless, I used the solver tool in excel to do this problem and got the same solution you posted. So, I am clearly seeing this problem incorrectly. Some clarification would be much appreciated.

4. Hello Danneedshelp
Originally Posted by Danneedshelp
Thank you very much for all your help and time.

I do have one last question though. I am not seeing how you got the feasible region illustrated in the above attachment, since we are concerend with the region below line (2). In you illustration, the afore mentioned constraint isn't accounted for, correct?

Nevertheless, I used the solver tool in excel to do this problem and got the same solution you posted. So, I am clearly seeing this problem incorrectly. Some clarification would be much appreciated.
We want the side of line (2) that contains the origin - which is the region above the line.

Grandad

5. Originally Posted by Grandad
Hello DanneedshelpWe want the side of line (2) that contains the origin - which is the region above the line.

Grandad
Due to the non-negativity constraint?

6. Hello Danneedshelp
Originally Posted by Danneedshelp
Due to the non-negativity constraint?
No - it has nothing to do with that. Condition (2) is:
$\displaystyle 2x_1-3x_2\le6$
At the origin:
$\displaystyle 2x_1-3x_2= 0$, and $\displaystyle 0\le6$
So the origin lies on the side of the line where values of $\displaystyle x_1$ and $\displaystyle x_2$ satisfy condition (2); i.e. the region 'above' the line.

The points representing the possible solutions to the problem lie in the region that is the intersection of the five regions that satisfy each individual inequality (including the non-negativity ones). If you study these five regions, you'll see that it's only the triangle I have shaded light blue that satisfies them all.

Grandad