SOLUTION: 1. For the following LP problem, graph the region of feasible solution and solve by the corner-point method. Maximize z = 5x1 + 8x2

Click here to see ALL problems on Graphs

Question 1157366: 1. For the following LP problem, graph the region of feasible solution and solve by the corner-point method.
Maximize z = 5x1 + 8x2
Subject to x1 + x2 ≥ 6
3x1 + 2x2 ≤ 30
2x1 + x2 ≤ 5
x1 , x2 ≥ 0
2. For the following LP problem, graph the region of feasible solution and solve by the corner-point method.
Minimize z = 3x1 + 2x2
Subject to x1 + 2x2 ≥ 6
9x1 + 6x2 ≤ 108
x1 ≥ 8
x2 ≥ 4
x1 , x2 ≥ 0

Found 3 solutions by KMST, ikleyn, greenestamps:
Answer by KMST(5434)   (Show Source):
You can put this solution on YOUR website!
I assume the variables for optimization are and .
For graphing purposes, and to make it easier to write and keep track of them,
will replace and will replace .

1. Maximize . Subject to
, , ,

The borders (edges) of the feasible region would be determined by the lines represented by
, , and the x- and y-axes.
Points that satisfy are only found in the first quadrant, including the positive x- and y-axes.
The graphs below show the first quadrant and the lines in question.
and
The inequalities related to those lines can be graphed as
and
There is no point on the x-y plane that satisfies all those inequalities, because no point in the first quadrant satisfies .
Either there is a typo or the problem required you try to find corner points and be puzzled to find out there are none, without necessarily understand why.

The corner-point method requires you to look for corner-points that could be part of the feasible region.
That method ccan be used to find corner points for this problem because all inequalities include an "or equal" sign.
It would not work if the "or equal" was not present in all inequalities.
The algebra approach is to find solutions to all systems of 2 equations in two variables
that you could make from the equations included in the inequalities, and then check each solution to see if it satisfies all inequalities.
Our equations are , , , .
Every one of the equations above represents a different line, and no two of them represent a pair of parallel lines.
So, every set of 2 of the equations forms a system with one solution representing the intersection point of the corresponding lines.
From the 5 equations we can make 10 pairs, so we are to solve 10 systems of equations.
1 , the intersection point does not satisfy
2 --> , the intersection point does not satisfy
3 -->--> , the intersection point does not satisfy
4 --> , the intersection point does not satisfy
5 --> , the intersection point does not satisfy
6 -->--> , the intersection point does not satisfy
7 -->--> , the intersection point does not satisfy
8 -->-->--> , the intersection point does not satisfy
9 -->-->--> , the intersection point does not satisfy
10 -->-->-->--> , the intersection point does not satisfy
We found 10 intersection points, but none of them satisfied all inequalities.
There are no corner points and no feasible region.

2. Minimize , subject to
, , , ,
, .

Graphing looks easier, and I know means first quadrant,
so I will graph not including much of the other quadrants.
Also, lines and are the coordinate axes, so I do not need to draw them.
Drawing vertical line and horizontal line was no problem.
Now I just have to draw the slanted lines and <--> .
I can use the x- and y-intercepts, or two points, or a point and the slope.
I will find my points:
-->-->
-->
-->-->-->
-->-->
With the two points found above for each slanted line, I can draw those lines and get:
means to the right of the red line,
and means above the purple line, so I can forget the axes,
and the blue line ,
because they never comply with within the first quadrant.
Line was the boundary for <--> .
That inequality represents obviously the side of the green line that contains point because .
The feasibility region is that little triangle bounded by lines
, and
<--> represents an infinite set of parallel lines, including line , and ,
which goes through .
The lines get closer to the origin as decreases, and to decrease we need to move to another line parallel to closer to .
To minimize we need to be on one of those parallel lines,
as close to as possible and within our little triangle .
That will happen at , where .

We can use the corner-point method because we have an "or equal" sign in all 6 inequalities,
but it seems like cruel and usual punishment from a math teacher.
First, we write the 6 corresponding equations of the lines
, <--> , , , , and .
We write and solve all 15 systems made from combinations of those equations
to find the intersection points.
Then, we check each intersection point found and discard it it does not satisfy all inequalities
-->-->-->-->--> ,
intersection point does not satisfy
-->-->--> ,
intersection point does not satisfy
, intersection point will not satisfy
, intersection point will not satisfy
, intersection point will not satisfy
-->-->-->
-->-->-->
, intersection point will not satisfy
, intersection point will not satisfy

--> no solution
, intersection point will not satisfy
, intersection point will not satisfy
, intersection point will not satisfy
, intersection point will not satisfy
We found the three corner-points , , and
To find the minimum value for in polygonal (triangular) feasible region ,
we calculate for all three corner-points:
For , for , for .
The minimum value for in the feasible region is .

Answer by ikleyn(54018)   (Show Source):
You can put this solution on YOUR website!
.
2. For the following LP problem, graph the region of feasible solutions and solve by the corner-point method.
Minimize z = 3x1 + 2x2
Subject to x1 + 2x2 ≥ 6
9x1 + 6x2 ≤ 108
x1 ≥ 8
x2 ≥ 4
x1 , x2 ≥ 0
~~~~~~~~~~~~~~~~~~~~~~

In this post, I will provide the solution to problem 2.

My solution will be a compact standard solution in readable form to this LP problem
by the geometric "corner point method".

Minimize z = 3x1 + 2x2 Subject to x1 + 2x2 ≥ 6 9x1 + 6x2 ≤ 108 x1 ≥ 8 x2 ≥ 4 x1 , yx2 ≥ 0. First of all, I will reformulate the problem EQUIVALENTLY in terms (x,y) instead of (x1,x2) using standard designations (x,y) for the method instead of (x1,x2). Minimize z = 3x + 2y Subject to x + 2y ≥ 6, 9x + 6y ≤ 108, x ≥ 8, y ≥ 4, x >= 0, y ≥ 0. To get the feasibility domain, draw the lines (see the plot below) x + 2y = 6 (red line), 9x + 6y = 108 (purple line), x = 8 (green line overlying vertical coordinate line), y = 4 (blue line overlying horizontal coordinate line). Obviously, the feasibility domain is the set of points in the plane on the right of the vertical green line x=8, above the horizontal blue line y=4, and below the purple sloped line 9x+6y=108. In other words, the feasibility domain is triangle ABC in the plot including all its boundary points. The vertices of this triangle are A(8,4), B(,) and C(8,6). The coordinates are easily found as the intersections of the corresponding lines. Finding these coordinates is traditionally considered as elementary operations for LP problems, so I will not bore the reader with these details. Next, according to the "corner points method", we should evaluate the objective function z = 3x+2y at the corner points of the feasibility domain and select that vertex where the objective function is minimal. You can do it manually on your own, but it will be much better if, looking at the objective function, you will guess mentally in your mind that the minimum of the objective function is at point A(8,4). To get this conclusion, you should simply notice that the objective function rises as the coordinates x and/or y increase. So, x = 8, y = 4 is the solution to the problem, giving the minimum z = 3x + 2y = 3*8 + 2*4 = 32 for the objective function. ANSWER. x1 = 8, x2 = 4 is the solution, giving the minimum z = 32 for the objective function.

At this point, the solution is complete.

Answer by greenestamps(13382)   (Show Source):
You can put this solution on YOUR website!

For most of my response, I will borrow the following from the excellent response from tutor @ikleyn:

Minimize z = 3x1 + 2x2 Subject to x1 + 2x2 >= 6 9x1 + 6x2 <= 108 x1 >= 8 x2 >= 4 First of all, I will reformulate the problem EQUIVALENTLY in terms (x,y) instead of (x1,x2) using standard designations (x,y) for the method instead of (x1,x2). Minimize z = 3x + 2y Subject to x + 2y >=6, 9x + 6y <= 108, x >= 8, y >= 4, To get the feasibility domain, draw the lines (see the plot below) x + 2y = 6 (red line), 9x + 6y = 108 (purple line), x = 8 (green line overlying vertical coordinate line), y = 4 (blue line overlying horizontal coordinate line). Obviously, the feasibility domain is the set of points in the plane on the right of the vertical green line x=8, above the horizontal blue line y=4, and below the purple sloped line 9x+6y=108. In other words, the feasibility domain is triangle ABC in the plot including all its boundary points. The vertices of this triangle are A(8,4), B(,) and C(8,6). The coordinates are easily found as the intersections of the corresponding lines. Finding these coordinates is traditionally considered as elementary operations for LP problems, so I will not bore the reader with these details. Next, according to the "corner points method", we should evaluate the objective function z = 3x+2y at the corner points of the feasibility domain and select that vertex where the objective function is minimal. You can do it manually on your own, but it will be much better if, looking at the objective function, you will guess mentally in your mind that the minimum of the objective function is at point A(8,4). To get this conclusion, you should simply notice that the objective function rises as the coordinates x and/or y increase. So, x = 8, y = 4 is the solution to the problem, giving the minimum z = 3x + 2y = 3*8 + 2*4 = 32 for the objective function. ANSWER. x1 = 8, x2 = 4 is the solution, giving the minimum z = 32 for the objective function.

So in that response, she mentions the corner points method but points out that it is not needed because logical reasoning tells us where the objective function is minimized.

While in this example logical reasoning gives us the answer to the problem, there is another method related to the corner points method that can be used to find the answer.

With this alternative to the standard corner points method, you can find the answer by comparing the slopes of the constraint lines to the slope of the objective function. That eliminates the need to evaluate the objective function at every corner of the feasibility region.

The slopes of the constraint lines are -1/2 and -2/3; the slope of the objective function is -2/3. So the minimum and maximum values of the objective function are obtained where lines with slope -2/3 just touch the feasibility region.

So the minimum value of the objective function is at A(8,4).

Note that in this example, since the slope of the objective function is the same as the slope of one of the constraint lines, the maximum value of the objective function is obtained at any point on segment BC.