Ask Questions, Get Answers

Want to ask us a question? Click here
Browse Questions
Home  >>  CBSE XII  >>  Math  >>  Linear Programming
0 votes

Show that the minimum of Z occurs at more than two points. Maximise $Z = x + y$, subject to$\; x $– $y\leq –1, -x + y \leq 0, x, y \geq 0.$

$\begin{array}{1 1}8 \\ 19 \\ 10 \\ can\;not\;be\;determined \end{array} $

Can you answer this question?

1 Answer

0 votes
  • 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 maximize $Z =x+y \;\;(1)$, subject to the following constraints:
$(2) \quad x-y \leq -1$
$(3) \quad - x+y \leq -1$
$(4) \quad -x+y \leq 0$
$(5) \quad x \geq 0$
$(6) \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: $(7) x-y = -1$
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 = 1. Thus the point (0,1) must fall on this line.
Similarly, if y = 0, we can see from the equation that x = -1. Thus the point (-1,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): x - y = -1.
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 ≥0, y ≥0 and the values assumed by x and y cannot be negative.
The line connecting the points satisfies the equality x -y = -1. But recall that the first constraint in the problem is the inequality.
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.
$\textbf{Plotting the second constraint}$:
The boundary of the constraint is represented by the straight line defined by the equation: $(8)\; -x+y = 0$
This is the straight line y = x which passes through the origin.
$\textbf{Identifying the Feasible Region}$:
Since there are no other constraints, let us arrive at the feasible region.
While we see that the Feasible Region should lie in the first quadrant, from the graph it is clear that there is no common region as the lines don’t intersect.
From the graph it is clear that there is no common region. If there is no common region, we cannot determine the minimum of maximum value.
answered Apr 16, 2013 by balaji.thirumalai
edited Apr 27, 2016 by meena.p

Related questions

Ask Question
student study plans
JEE MAIN, CBSE, NEET Mobile and Tablet App
The ultimate mobile app to help you crack your examinations
Get the Android App