Browse Questions

Solve the following Linear Programming Problems graphically: Maximise $Z = 5x + 3y$ subject to $3x + 5y \leq 15, 5x + 2y \leq 10, x \geq 0, y \geq 0.$

Toolbox:
• One we graphically plot the area bounded by the constraints, it’s easy to see which points satisfy all constraints. This common region determined by all the constraints including non-negative constraints of a linear programming problem is called the $\textbf{Feasible Region (or solution region).}$
• Now, any point in the feasible region that gives the optimal value (maximum or minimum) of the objective function is called an $\textbf{Optimal Solution}$. We see that every point in the feasible region satisfies all the constraints, and there are infinitely many points.
• Since we know from theory that the optimal value must occur at a corner point (vertex) of the feasible region, calculate the objective function values associated with the coordinates of all the extreme points. This method is called the $\textbf{Corner Point Method}$.
We are asked to minimize $Z = 3x + 4y \;\;(1)$, subject to the following constraints:
$(2) \quad 3x + 5y \leq 15$
$(3) \quad 5x+2y \leq 10$
$(4) \quad x \geq 0$
$(5) \quad y \geq 0$
To solve a Linear Programming problem graphically, first plot the constraints for the problem. This is done by plotting the boundary lines of the constraints and identifying the points that will satisfy all the constraints.
$\textbf{Plotting the first constraint}$:
The boundary of the first constraint is represented by the straight line defined by the equation:
$(6) \quad 3x+5y = 15$
If we can find any two points on this line, the entire line can be plotted by drawing a straight line through these points.
If x = 0, we can see from the equation that y = 3. Thus the point C (0,3) must fall on this line. Similarly, if y = 0, we can see from the equation that x = 5. Thus the point D (5,0) must fall on this line.
Plot these two points on the graph, and connect them to form the straight line representing the equation $(6):\;3 x + 5y = 15.$
Note that the graph actually extends beyond the x and y axes as shown in the figure. However, we can disregard the points beyond the axes because we have the constraints $x \geq 0, y \geq 0$ and the values assumed by x and y cannot be negative.
The line connecting the points C (0,3) and D (8,0) satisfies the equality $3 x + 5y = 15$. But recall that the first constraint in the problem is the inequality $3x+5y \leq 15$
Thus, after plotting the boundary line of a constraint we must determine which area on the graph corresponds to the feasible solutions for original constraint. This can be done very easily by picking an arbitrary point on either side of the boundary and checking where it satisfies the original constraint.
For example, if we test the point (0, 0), we see that it satisfies the constraint, i.e., 0 + 0 = 0 ≤ 15. Therefore, the area of the graph must be on the same side of the boundary line as the point (0,0).
As shown in the figure, this is the region bounded by OCD (0,0), (0,3) and (5,0).
$\textbf{Plotting the second constraint}$:
The boundary of the constraint is represented by the straight line defined by the equation: $(7)\; 5x + 2y = 10$
If we can find any two points on this line, the entire line can be plotted by drawing a straight line through these points.
If x = 0, we can see from the equation that 2y = 10 and therefore y = 5. Thus the point (0,5) must fall on this line. Similarly, if y = 0, we can see from the equation that 5x = 10 and therefore x = 2. Thus the point (2,0) must fall on this line.
Plot these two points on the graph, and connect them to form the straight line representing the equation $(7):\; 5x + 2y = 10.$
As we did with the first constraint, we can disregard the points beyond the axes because we have the constraints x ≥0, y ≥0 and the values assumed by x and y cannot be negative, and we can similarly see that the area bounded by this constraint also lies in the first quadrant, i.e., the area of the graph must be on the same side of the boundary line as the point (0,0).
As shown in the figure, this is the region bounded by OAB (0,0), (0,5) and (2,0).
$\textbf{Identifying the Feasible Region}$:
Since there are no other constraints, let us arrive at the feasible region.
Some of the feasible solutions to one constraint in a LP model will usually not satisfy one or more of the other constraints. For example the point (0,3) satisfies the first constraint, but not the second constraint. Similarly, the point (0,5) satisfies the second constraint but not the first.
Once we draw the graph, it is easy to see which points satisfy all constraints in the model.Notice that when we add the second constraint, some of the feasible solutions associated with the first constraint were eliminated.
We see that the graphs intersect at point E. We need to solve the equations (6) and (7) to get the point of intersection (E):
$(6) \quad 3x + 5y = 15$
$(7) \quad 5x + 2y =10$
Substituting for $y$ in the first equation, $\Rightarrow y = (10-5x)/2 = 5 – 5/2x$
$\Rightarrow 3x + 5(5 – 5x/2) = 15.$ Resolving, $3x + 25 – 25x/2 = 15.$
$\Rightarrow 25-15 = 25x/2 – 3x \rightarrow 10 = x(25/2-3) = 19x/2.$
$\Rightarrow x = 10 \times 2/19 = 20/19.$
Substituting for $x$, we get $5 \times 20/19 + 2y = 10 \rightarrow y =\frac{1}{2}\times(10-100/19)$, which resolves to 45/19.
Point E $(\large\frac{20}{19}, \frac{45}{19}$) is the point of intersection.
• Therefore the feasible region is given by $OCEBO$ i.e., area bounded by $(0,0), (0,3), (\large\frac{20}{19}, \frac{45}{19}$)$(2,0).$
$\textbf{Solving the objective function using the Corner Point Method:}$
Recall that any point in the feasible region that gives the optimal value (maximum or minimum) of the objective function is called an optimal solution. We see that every point in the feasible region satisfies all the constraints, and there are infinitely many points.
We know that the solution will always occur at a point in the feasible region where two or more boundary lines intersect (corner points or vertex).
Since we are asked to maximize the objective function, all we need to do is solve the objective function at the corner points and choose the corner or vertex that gives us the maximum value.
This can be easily summarized in a table as follows:
Corner Point Z = 5x + 3y
O (0,0) Z = 0
C (0,3) Z = 9
E (20/19,45/19) Z = 235/19 (Max Value)
B (2,0) Z = 10

$\textbf{The Maximum value of Z is 235/19 which occurs at point E (20/19, 45/19)}$