1. ## LP help

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

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

and

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

a) Demonstrate that the feasible region is unbounded.
b) If the objective is to maximize $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 $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 $Z=15x_{1}+20x_{2}$

subject to:

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

and $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?

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.

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

and

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

a) Demonstrate that the feasible region is unbounded.
b) If the objective is to maximize $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 $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 $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 $x_1$ and $x_2$ as large as you like and both inequalities will be satisfied. For example, if you want to make $x_2 = 1\,000\,000$, just take $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 $x_1 = 0 = x_2$ satisfy both inequalities. Therefore the origin is on the side to be shaded in each case.

(b) To maximise $Z = -x_1+x_2$, draw the line $-x_1+x_2 = 0$ (in other words, the line $x_1 = x_2$) and then try to find the line parallel to that whose intercept with the $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 $(0,25)$ giving a maximum value $Z = 25$.

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

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

subject to:

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

and $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?

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 ' $Z$ line' to make $Z$ a minimum. This is the line that passes through $(0,5)$, giving the minimum value of $Z = 100$.

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 ' $Z$ line' to make $Z$ a minimum. This is the line that passes through $(0,5)$, giving the minimum value of $Z = 100$.

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.

Hello DanneedshelpWe want the side of line (2) that contains the origin - which is the region above the line.

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:
$2x_1-3x_2\le6$
At the origin:
$2x_1-3x_2= 0$, and $0\le6$
So the origin lies on the side of the line where values of $x_1$ and $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.