Linear Programming: Chapter 12 Links
Current page: Linear Programming 12.1 NCERT Solutions. Go to other content from this chapter :
Linear Programming 12.1 NCERT Solutions covers the graphical method of solving Linear Programming Problems. This exercise brings together important concepts such as linear constraints, the feasible region, feasible solutions, corner points, and the objective function to find maximum or minimum values.
\displaystyle Z=ax+by;\qquad ax+by\leq c,\; ax+by\geq c;\qquad x\geq0,\;y\geq0
While solving these questions, you will learn how to graph linear inequalities, identify the feasible region, find its corner points, and evaluate the objective function at these points. You will also encounter important cases such as multiple optimal solutions, an unbounded feasible region, and a problem with no feasible region.
The exercise is based on the Corner Point Method, which provides a systematic way to find the optimum value of the objective function. These questions are important for CBSE board examinations and are also useful for strengthening your graphical and problem-solving skills in Linear Programming 12.1.
Key Concepts
1. Linear Programming Problem
A Linear Programming Problem (LPP) is an optimisation problem in which we find the maximum or minimum value of a linear function, subject to a set of linear constraints and non-negative restrictions on the variables.
The function that we want to maximise or minimise is called the objective function.
\displaystyle Z=ax+by
Here, x and y are called decision variables.
The conditions or restrictions imposed on the decision variables are called constraints. In a Linear Programming Problem, these are generally linear inequalities such as
\displaystyle a_1x+b_1y\leq c_1,\qquad a_2x+b_2y\geq c_2
The conditions x ≥ 0 and y ≥ 0 are called non-negative constraints.
2. Linear Inequalities and Their Graphs
To graph a linear inequality, first draw the corresponding boundary line by replacing the inequality sign with an equality.
For example, the boundary line of \displaystyle x+y\leq4 is \displaystyle x+y=4
For ≤ or ≥, the boundary line is included, so we draw a solid line. And, for < or >, the boundary line is not included, so we draw a dotted line.
After drawing the boundary line, we identify the required half-plane using a checking point, usually the origin (0, 0) when it does not lie on the boundary line.
3. Feasible Region and Feasible Solution
The feasible region is the common region satisfying all the constraints simultaneously, including the non-negative constraints.
Every point inside or on the boundary of the feasible region is called a feasible solution.
A point outside the feasible region is an infeasible solution.
Remember: The feasible region contains infinitely many feasible solutions in general. Our aim is to find the feasible solution that gives the required maximum or minimum value of the objective function.
4. Corner Points and Optimal Solution
A corner point (or vertex) of the feasible region is a point where two boundary lines meet.
For the objective function
\displaystyle Z=ax+by
we calculate the value of Z at each corner point. The point that gives the required maximum or minimum value is called the optimal solution, and the corresponding value of Z is the optimal value.
5. Bounded and Unbounded Feasible Region
A feasible region is bounded if it does not extend indefinitely in any direction. Otherwise, it is called unbounded.
For a bounded feasible region, both the maximum and minimum values of the objective function exist, and they occur at corner points.
For an unbounded feasible region, a maximum or minimum value may or may not exist. If an optimal value exists, it must occur at a corner point.
6. Multiple Optimal Solutions
Sometimes two corner points give the same maximum or minimum value of the objective function. In that case, every point on the line segment joining those two corner points also gives the same optimal value.
7. Corner Point Method
To solve an LPP graphically using the Corner Point Method:
- Draw the boundary lines of all the constraints.
- Identify and shade the common feasible region.
- Find all the corner points of the feasible region.
- Calculate the value of the objective function at each corner point.
- For a bounded feasible region, the largest and smallest values give the maximum and minimum values.
- For an unbounded feasible region, check separately whether the required optimum actually exists.
- Convex feasible region: The feasible region of an LPP is convex, meaning that the line segment joining any two points in the feasible region lies completely within the feasible region.
Quick Reference Table
| Concept | Details |
|---|---|
| Decision Variables |
The variables whose values are to be determined in the LPP, usually represented by x and y. |
| Objective Function |
The linear function that is to be maximised or minimised. \displaystyle Z=ax+by |
| Constraints |
The linear inequalities or equations that represent the restrictions or conditions imposed on the decision variables. For example, \displaystyle a_1x+b_1y\leq c_1 |
| Non-negative Constraints |
The conditions that the decision variables cannot be negative. \displaystyle x\geq0,\qquad y\geq0 |
| Feasible Region |
The common region satisfying all the constraints, including the non-negative constraints. |
| Feasible Solution |
Any point inside or on the boundary of the feasible region. It satisfies all the constraints simultaneously. |
| Infeasible Solution |
Any point outside the feasible region. It does not satisfy all the constraints simultaneously. |
| Corner Point (Vertex) |
A point of the feasible region where two boundary lines intersect. |
| Optimal Solution |
A feasible solution that gives the required maximum or minimum value of the objective function. |
| Optimal Value |
The maximum or minimum value of the objective function corresponding to the optimal solution. |
| Bounded Feasible Region |
A feasible region that does not extend indefinitely in any direction. For a bounded region, both the maximum and minimum values of the objective function exist. |
| Unbounded Feasible Region |
A feasible region that extends indefinitely in some direction. A maximum or minimum value may or may not exist. |
Bounded Region
|
Working Rule — Bounded Feasible Region
|
Unbounded Region
|
Working Rule — Unbounded Feasible Region
|
Maths Better Tip! Bounded region → compare corner points. Unbounded region → compare corner points, then perform the extra \displaystyle Z<k or \displaystyle Z>k check.
Let us now solve all the NCERT questions of Linear Programming 12.1 step by step.
Question 1: Linear Programming 12.1
1. Maximise \displaystyle Z=3x+4y subject to the constraints: \displaystyle x+y\leq4;\; x\geq0;\; y\geq0
Solution
Think First… To solve an LPP graphically, first identify the feasible region and its corner points. Then evaluate the objective function at each corner point.
We have to maximise \displaystyle Z=3x+4y, subject to the given constraints
\displaystyle x+y\leq4\qquad ...(1)
\displaystyle x\geq0\qquad ...(2)
and \displaystyle y\geq0\qquad ...(3)
Consider the corresponding equation of (1),
\displaystyle x+y=4
Rewriting it in intercept form, we get
\displaystyle \frac{x}{4}+\frac{y}{4}=1
This represents the line AB with x-intercept \displaystyle4 and y-intercept \displaystyle4, as shown in the diagram.
The corresponding equations of (2) and (3) represent the y-axis and x-axis, respectively.
Solution sets:
To identify the solution set of (1), we use the checking point \displaystyle(0,0). Substituting it in (1),
\displaystyle 0+0\leq4
which is true. Therefore, the solution set of (1) is the region containing the origin.
The constraints (2) and (3) collectively restrict the region to the first quadrant.
Hence, the common feasible region is the shaded region OAB, as shown in the diagram. Its vertices or corner points are
\displaystyle O(0,0),\; A(4,0),\; B(0,4)
Now, the corresponding values of the objective function \displaystyle Z=3x+4y at these corner points are as shown in the table below.
| Corner Point | Value of \displaystyle Z=3x+4y |
|---|---|
| \displaystyle O(0,0) | \displaystyle Z=3(0)+4(0)=0 |
| \displaystyle A(4,0) | \displaystyle Z=3(4)+4(0)=12 |
| \displaystyle B(0,4) | \displaystyle Z=3(0)+4(4)=16 |
Therefore, the maximum value of \displaystyle Z is \displaystyle16, attained at the corner point \displaystyle B(0,4).
Hence,
\boxed{\displaystyle Z_{\max}=16\text{ at }(x,y)=(0,4)}
Question 2: Linear Programming 12.1
2. Minimise \displaystyle Z=-3x+4y subject to the constraints: \displaystyle x+2y\leq8;\; 3x+2y\leq12;\; x\geq0;\; y\geq0.
Solution
Think First… Draw the boundary lines, identify the common feasible region and find all its corner points. Since the feasible region is bounded, the smallest value of the objective function will give the minimum.
We have to minimise \displaystyle Z=-3x+4y, subject to the given constraints
\displaystyle x+2y\leq8\qquad ...(1)
\displaystyle 3x+2y\leq12\qquad ...(2)
and
\displaystyle x\geq0\qquad ...(3)
\displaystyle y\geq0\qquad ...(4)
Consider the corresponding equation of (1),
\displaystyle x+2y=8
Rewriting it in intercept form, we get
\displaystyle \frac{x}{8}+\frac{y}{4}=1
This represents the line CD with x-intercept \displaystyle8 and y-intercept \displaystyle4, as shown in the diagram.
Similarly, the corresponding equation of (2) is
\displaystyle 3x+2y=12
Rewriting it in intercept form, we get
\displaystyle \frac{x}{4}+\frac{y}{6}=1
This represents the line AE with x-intercept \displaystyle4 and y-intercept \displaystyle6, as shown in the diagram.
The corresponding equations of (3) and (4) represent the y-axis and x-axis, respectively.
Solution sets:
To identify the solution set of (1), we use the checking point \displaystyle(0,0). Substituting it in (1),
\displaystyle 0+2(0)\leq8
which is true. Therefore, the solution set of (1) is the region containing the origin.
Similarly, substituting \displaystyle(0,0) in (2),
\displaystyle 3(0)+2(0)\leq12
which is also true. Therefore, the solution set of (2) is again the region containing the origin.
The constraints (3) and (4) collectively restrict the region to the first quadrant.
Hence, the common feasible region is the shaded region OABC, as shown in the diagram.
The corner points \displaystyle O,\;A,\;C can be read directly from the graph. The remaining corner point \displaystyle B is the point of intersection of the two boundary lines:
\displaystyle x+2y=8\qquad ...(5)
and
\displaystyle 3x+2y=12\qquad ...(6)
Subtracting (5) from (6),
\displaystyle 2x=4\Rightarrow x=2
Substituting \displaystyle x=2 in (5),
\displaystyle 2+2y=8\Rightarrow y=3
Therefore, the corner points of the feasible region are
\displaystyle O(0,0),\; A(4,0),\; B(2,3),\; C(0,4)
Now, the corresponding values of the objective function \displaystyle Z=-3x+4y at these corner points are as shown in the table below.
| Corner Point | Value of \displaystyle Z=-3x+4y |
|---|---|
| \displaystyle O(0,0) | \displaystyle Z=-3(0)+4(0)=0 |
| \displaystyle A(4,0) | \displaystyle Z=-3(4)+4(0)=-12 |
| \displaystyle B(2,3) | \displaystyle Z=-3(2)+4(3)=6 |
| \displaystyle C(0,4) | \displaystyle Z=-3(0)+4(4)=16 |
Therefore, the minimum value of \displaystyle Z is \displaystyle-12, attained at the corner point \displaystyle A(4,0).
Hence,
\boxed{\displaystyle Z_{\min}=-12\text{ at }(x,y)=(4,0)}
You may already be following Maths Better for the NCERT Solutions of the earlier Class 12 Maths chapters. If not, do check them out after completing this exercise.
- NCERT Maths Class 12
- Integrals
- Application of Integrals
- Differential Equations
- Vector Algebra
- 3–D Geometry
Likewise, Linear Programming 12.1 builds on your understanding of linear inequalities and introduces graphical methods to find the best possible solution. In this chapter, you will learn how to identify the feasible region, find its corner points, and determine the maximum or minimum value of an objective function. You will also come across important cases such as unbounded feasible regions, multiple optimal solutions, and no feasible region. Keep practising these questions to build speed and accuracy for the CBSE Board Examination as well as CUET. Now, let’s proceed to the next question of Linear Programming 12.1
Question 3: Linear Programming 12.1
3. Maximise \displaystyle Z=5x+3y subject to the constraints:
\displaystyle 3x+5y\leq15\qquad ...(1)
\displaystyle 5x+2y\leq10\qquad ...(2)
and
\displaystyle x\geq0\qquad ...(3)
\displaystyle y\geq0\qquad ...(4)
Solution
Think First… Convert each boundary equation into intercept form to plot the lines quickly. Then identify the common feasible region and find the corner points.
We have to maximise \displaystyle Z=5x+3y, subject to the given constraints.
Consider the corresponding equation of (1),
\displaystyle 3x+5y=15
Rewriting it in intercept form, we get
\displaystyle \frac{x}{5}+\frac{y}{3}=1
This represents the line CD with x-intercept \displaystyle5 and y-intercept \displaystyle3, as shown in the diagram.
Similarly, the corresponding equation of (2) is
\displaystyle 5x+2y=10
Rewriting it in intercept form, we get
\displaystyle \frac{x}{2}+\frac{y}{5}=1
This represents the line AE with x-intercept \displaystyle2 and y-intercept \displaystyle5, as shown in the diagram.
The corresponding equations of (3) and (4) represent the y-axis and x-axis, respectively.
Solution sets:
To identify the solution set of (1), we use the checking point \displaystyle(0,0). Substituting it in (1),
\displaystyle 3(0)+5(0)\leq15
which is true. Therefore, the solution set of (1) is the region containing the origin.
Similarly, substituting \displaystyle(0,0) in (2),
\displaystyle 5(0)+2(0)\leq10
which is also true. Therefore, the solution set of (2) is the region containing the origin.
The constraints (3) and (4) collectively restrict the region to the first quadrant.
Hence, the common feasible region is the shaded region OABC, as shown in the diagram.
The corner points \displaystyle O,\;A,\;C can be read directly from the graph. The remaining corner point \displaystyle B is the point of intersection of the two boundary lines:
\displaystyle 3x+5y=15\qquad ...(5)
and
\displaystyle 5x+2y=10.\qquad ...(6)
Multiplying (5) by 2 and (6) by 5, we get
\displaystyle 6x+10y=30\qquad ...(7)
\displaystyle 25x+10y=50.\qquad ...(8)
Subtracting (7) from (8),
\displaystyle 19x=20\Rightarrow x=\frac{20}{19}.
Substituting \displaystyle x=\frac{20}{19} in (5),
\displaystyle 3\left(\frac{20}{19}\right)+5y=15
\displaystyle \frac{60}{19}+5y=\frac{285}{19}
or \displaystyle 5y=\frac{225}{19}\Rightarrow y=\frac{45}{19}.
Therefore, the corner points of the feasible region are
\displaystyle O(0,0),\; A(2,0),\; B\left(\frac{20}{19},\frac{45}{19}\right),\; C(0,3)
Now, the corresponding values of the objective function \displaystyle Z=5x+3y at these corner points are as shown in the table below.
| Corner Point | Value of \displaystyle Z=5x+3y |
|---|---|
| \displaystyle O(0,0) | \displaystyle Z=5(0)+3(0)=0 |
| \displaystyle A(2,0) | \displaystyle Z=5(2)+3(0)=10 |
| \displaystyle B\left(\frac{20}{19},\frac{45}{19}\right) | \displaystyle Z=5\left(\frac{20}{19}\right)+3\left(\frac{45}{19}\right)=\frac{235}{19} |
| \displaystyle C(0,3) | \displaystyle Z=5(0)+3(3)=9 |
Therefore, the maximum value of \displaystyle Z is \displaystyle\frac{235}{19}, attained at the corner point \displaystyle B\left(\frac{20}{19},\frac{45}{19}\right).
Hence,
\boxed{\displaystyle Z_{\max}=\frac{235}{19}\text{ at }\left(x,y\right)=\left(\frac{20}{19},\frac{45}{19}\right)}
Question 4: Linear Programming 12.1
4. Minimise \displaystyle Z=3x+5y subject to the constraints:
\displaystyle x+3y\geq3\qquad ...(1)
\displaystyle x+y\geq2\qquad ...(2)
and
\displaystyle x\geq0\qquad ...(3)
\displaystyle y\geq0\qquad ...(4)
Solution
Think First… Here the inequalities have signs “≥”, so the required regions lie on the sides of the boundary lines away from the origin. The common feasible region is unbounded, so the smallest corner value is not automatically the minimum.
We have to minimise \displaystyle Z=3x+5y, subject to the given constraints.
Consider the corresponding equation of (1),
\displaystyle x+3y=3
Rewriting it in intercept form, we get
\displaystyle \frac{x}{3}+\frac{y}{1}=1
This represents the line CD with x-intercept \displaystyle3 and y-intercept \displaystyle1, as shown in the diagram.
Similarly, the corresponding equation of (2) is
\displaystyle x+y=2
Rewriting it in intercept form, we get
\displaystyle \frac{x}{2}+\frac{y}{2}=1
This represents the line AE with x-intercept \displaystyle2 and y-intercept \displaystyle2, as shown in the diagram.
The corresponding equations of (3) and (4) represent the y-axis and x-axis, respectively.
Solution sets:
To identify the solution set of (1), we use the checking point \displaystyle(0,0). Substituting it in (1),
\displaystyle 0+3(0)\geq3
which is false. Therefore, the solution set of (1) is the region away from the origin.
Similarly, substituting \displaystyle(0,0) in (2),
\displaystyle 0+0\geq2
which is false. Therefore, the solution set of (2) is also the region away from the origin.
The constraints (3) and (4) collectively restrict the region to the first quadrant.
Hence, the common feasible region is the shaded unbounded region XDBEY, as shown in the diagram.
The corner points of the feasible region are \displaystyle D,\;B and \displaystyle E. The points \displaystyle X and \displaystyle Y lie on the unbounded portions of the feasible region and are not corner points.
The coordinates of \displaystyle D and \displaystyle E can be read directly from the graph:
\displaystyle D(3,0),\; E(0,2)
The remaining corner point \displaystyle B is the point of intersection of the two boundary lines:
\displaystyle x+3y=3
and
\displaystyle x+y=2.
Subtracting the second equation from the first,
\displaystyle 2y=1\Rightarrow y=\frac12.
Substituting \displaystyle y=\frac12 in \displaystyle x+y=2,
\displaystyle x+\frac12=2\Rightarrow x=\frac32.
Therefore, we get
\displaystyle B\left(\frac32,\frac12\right)
Thus, the corner points of the feasible region are
\displaystyle D(3,0),\; B\left(\frac32,\frac12\right),\; E(0,2)
Now, the corresponding values of the objective function \displaystyle Z=3x+5y at these corner points are as shown in the table below.
| Corner Point | Value of \displaystyle Z=3x+5y |
|---|---|
| \displaystyle D(3,0) | \displaystyle Z=3(3)+5(0)=9 |
| \displaystyle B\left(\frac32,\frac12\right) | \displaystyle Z=3\left(\frac32\right)+5\left(\frac12\right)=7 |
| \displaystyle E(0,2) | \displaystyle Z=3(0)+5(2)=10 |
The smallest value obtained at a corner point is \displaystyle7 at \displaystyle B\left(\frac32,\frac12\right). However, since the feasible region is unbounded, this smallest value may or may not be the actual minimum value. We therefore need to check it graphically.
To check whether \displaystyle7 is the minimum value, consider the corresponding objective-function line
\displaystyle Z=7\quad\Rightarrow\quad3x+5y=7.
Now consider the inequality
\displaystyle 3x+5y\text{ is less than }7
This represents the open half-plane on the side of the line \displaystyle 3x+5y=7 where the values of \displaystyle Z are less than \displaystyle 7.
From the graph, we observe that this open half-plane has no point in common with the feasible region. The line \displaystyle 3x+5y=7 touches the feasible region at the corner point \displaystyle B\left(\frac{3}{2},\frac{1}{2}\right). The region corresponding to \displaystyle 3x+5y\text{ is less than }7 lies outside the feasible region.
Therefore, there is no feasible point for which \displaystyle Z\text{ is less than }7. Hence, \displaystyle 7 is indeed the minimum value of the objective function.
Hence,
\boxed{Z_{\min}=7}
at \displaystyle (x,y)=\left(\frac{3}{2},\frac{1}{2}\right).
By now, you have already completed the NCERT Solutions for Matrices, Determinants, Relations and Functions, Inverse Trigonometric Functions, Continuity and Differentiability, Application of Derivatives, Integrals, Application of Integrals, Differential Equations, Vector Algebra and Three Dimensional Geometry.
Now, we are working through Linear Programming 12.1 with detailed, step-by-step solutions. In this chapter, you will learn how to represent constraints graphically, identify the feasible region, find its corner points, and determine the maximum or minimum value of the objective function. The questions also cover important cases such as unbounded feasible regions and multiple optimal solutions.
Many of these questions are also available in video format on my YouTube Channel, @MathsBetter, where each solution is explained in a simple and student-friendly manner. Now, let’s proceed to the next question of Linear Programming 12.1.
Question 5: LPP Exercise 12.1
5. Maximise \displaystyle Z=3x+2y subject to the constraints:
\displaystyle x+2y\leq10\qquad ...(1)
\displaystyle 3x+y\leq15\qquad ...(2)
and
\displaystyle x\geq0\qquad ...(3)
\displaystyle y\geq0\qquad ...(4)
Solution
Think First… Convert the boundary equations into intercept form to plot the lines quickly. Then identify the common feasible region, find its corner points and evaluate the objective function at each corner point.
We have to maximise \displaystyle Z=3x+2y, subject to the given constraints.
Consider the corresponding equation of (1),
\displaystyle x+2y=10
Rewriting it in intercept form, we get
\displaystyle \frac{x}{10}+\frac{y}{5}=1
This represents the line CD with x-intercept \displaystyle10 and y-intercept \displaystyle5, as shown in the diagram.
Similarly, the corresponding equation of (2) is
\displaystyle 3x+y=15
Rewriting it in intercept form, we get
\displaystyle \frac{x}{5}+\frac{y}{15}=1
This represents the line AE with x-intercept \displaystyle5 and y-intercept \displaystyle15, as shown in the diagram.
The corresponding equations of (3) and (4) represent the y-axis and x-axis, respectively.
Solution sets:
To identify the solution set of (1), we use the checking point \displaystyle(0,0). Substituting it in (1),
\displaystyle 0+2(0)\leq10
which is true. Therefore, the solution set of (1) is the region containing the origin.
Similarly, substituting \displaystyle(0,0) in (2),
\displaystyle 3(0)+0\leq15
which is also true. Therefore, the solution set of (2) is the region containing the origin.
The constraints (3) and (4) collectively restrict the region to the first quadrant.
Hence, the common feasible region is the shaded region OABC, as shown in the diagram.
The corner points \displaystyle O,\;A,\;C can be read directly from the graph. The remaining corner point \displaystyle B is the point of intersection of the two boundary lines:
\displaystyle x+2y=10
and
\displaystyle 3x+y=15.
From the second equation,
\displaystyle y=15-3x
Substituting this in the first equation,
\displaystyle x+2(15-3x)=10
\displaystyle x+30-6x=10
or \displaystyle -5x=-20\Rightarrow x=4
Therefore,
\displaystyle y=15-3(4)=3.
Hence,
\displaystyle B(4,3).
Therefore, the corner points of the feasible region are
\displaystyle O(0,0),\; A(5,0),\; B(4,3),\; C(0,5).
Now, the corresponding values of the objective function \displaystyle Z=3x+2y at these corner points are as shown in the table below.
| Corner Point | Value of \displaystyle Z=3x+2y |
|---|---|
| \displaystyle O(0,0) | \displaystyle Z=3(0)+2(0)=0 |
| \displaystyle A(5,0) | \displaystyle Z=3(5)+2(0)=15 |
| \displaystyle B(4,3) | \displaystyle Z=3(4)+2(3)=18 |
| \displaystyle C(0,5) | \displaystyle Z=3(0)+2(5)=10 |
Therefore, the maximum value of \displaystyle Z is \displaystyle18, attained at the corner point \displaystyle B(4,3).
Hence,
\boxed{\displaystyle Z_{\max}=18\text{ at }(x,y)=(4,3)}
The next question of Linear Programming 12.1 is about having multiple optimal solutions.
Question 6: Linear Programming 12.1
6. Minimise \displaystyle Z=x+2y subject to the constraints:
\displaystyle 2x+y\geq3\qquad ...(1)
\displaystyle x+2y\geq6\qquad ...(2)
and
\displaystyle x\geq0\qquad ...(3)
\displaystyle y\geq0\qquad ...(4)
Solution
Think First… Here the feasible region is unbounded. More importantly, the objective function is the same as the left-hand side of one of the constraints. This can lead to the same optimal value at infinitely many points.
We have to minimise \displaystyle Z=x+2y, subject to the given constraints.
Consider the corresponding equation of (1),
\displaystyle 2x+y=3
Rewriting it in intercept form, we get
\displaystyle \frac{x}{3/2}+\frac{y}{3}=1
This represents the line AC with x-intercept \displaystyle\frac32 and y-intercept \displaystyle3, as shown in the diagram.
Similarly, the corresponding equation of (2) is
\displaystyle x+2y=6
Rewriting it in intercept form, we get
\displaystyle \frac{x}{6}+\frac{y}{3}=1
This represents the line CB with x-intercept \displaystyle6 and y-intercept \displaystyle3, as shown in the diagram.
The corresponding equations of (3) and (4) represent the y-axis and x-axis, respectively.
Solution sets:
To identify the solution set of (1), we use the checking point \displaystyle(0,0). Substituting it in (1),
\displaystyle 2(0)+0\geq3
which is false. Therefore, the solution set of (1) is the region away from the origin.
Similarly, substituting \displaystyle(0,0) in (2),
\displaystyle 0+2(0)\geq6
which is false. Therefore, the solution set of (2) is also the region away from the origin.
The constraints (3) and (4) collectively restrict the region to the first quadrant.
Hence, the common feasible region is the shaded unbounded region XBCY, as shown in the diagram.
The corner points of the feasible region are \displaystyle B and \displaystyle C. Their coordinates can be read directly from the graph:
\displaystyle B(6,0),\qquad C(0,3).
Now, the corresponding values of the objective function \displaystyle Z=x+2y at these corner points are as follows.
| Corner Point | Value of \displaystyle Z=x+2y |
|---|---|
| \displaystyle B(6,0) | \displaystyle Z=6+2(0)=6 |
| \displaystyle C(0,3) | \displaystyle Z=0+2(3)=6 |
Both corner points give the same value \displaystyle Z=6. However, since the feasible region is unbounded, we first need to check graphically whether \displaystyle6 is actually the minimum value.
To check this, consider the corresponding objective-function line
\displaystyle Z=6\quad\Rightarrow\quad x+2y=6.
Now consider the inequality
\displaystyle x+2y\text{ is less than }6
This represents the open half-plane on the side of the line \displaystyle x+2y=6 where the values of \displaystyle Z are less than \displaystyle 6.
From the graph, we observe that this open half-plane has no point in common with the feasible region. Therefore, there is no feasible point for which \displaystyle Z\text{ is less than }6.
Hence, \displaystyle 6 is indeed the minimum value of the objective function.
Now, notice that the objective-function line \displaystyle x+2y=6 itself forms a part of the boundary of the feasible region. It joins the two corner points \displaystyle C(0,3) and \displaystyle B(6,0).
Therefore, every point on the line segment joining \displaystyle C(0,3) and \displaystyle B(6,0) gives the same minimum value.
For example, the points \displaystyle (0,3),\;(2,2),\;(4,1),\;(6,0) all lie on this line segment and give
\displaystyle Z=x+2y=6
Since there are infinitely many points on the line segment, the problem has infinitely many optimal solutions.
Hence,
\boxed{Z_{\min}=6}
at every point on the line segment joining \displaystyle (6,0) and \displaystyle (0,3).
Infinite Optimal Solutions
Sometimes, the maximum or minimum value of the objective function is attained at more than one point. If two corner points give the same optimal value, then every point on the line segment joining those two corner points also gives the same optimal value. Therefore, the problem has infinitely many optimal solutions.
For example, if the minimum value is attained at \displaystyle A and \displaystyle B, then every point on the line segment \displaystyle AB gives the same minimum value. Thus, the complete set of optimal solutions consists of all the points on that segment.
Maths Better Tip for Linear Programming 12.1: Two corner points having the same optimal value is a strong indication of infinitely many optimal solutions. Always check the line segment joining them.
And now in the next two questions of Linear Programming 12.1, we will find both, the maximum and minimum values in each of them.
Question 7: Linear Programming 12.1
7. Minimise and Maximise \displaystyle Z=5x+10y subject to the constraints:
\displaystyle x+2y\leq120\qquad ...(1)
\displaystyle x+y\geq60\qquad ...(2)
and
\displaystyle x-2y\geq0\qquad ...(3)
\displaystyle x\geq0,\qquad y\geq0.
Solution
Think First… We will use the Corner Point Method: first find the feasible region, then find its corner points and evaluate the objective function at each corner point.
We first draw the graphs of the boundary lines corresponding to the given inequalities.
For inequality (1), the corresponding equation is
\displaystyle x+2y=120
Re-writing it in intercept form, we get
\displaystyle \frac{x}{120}+\frac{y}{60}=1
It represents the line \displaystyle CD with x-intercept \displaystyle120 and y-intercept \displaystyle60.
For inequality (2), the corresponding equation is
\displaystyle x+y=60
Re-writing it in intercept form, we get
\displaystyle \frac{x}{60}+\frac{y}{60}=1
It represents the line \displaystyle AB with x-intercept \displaystyle60 and y-intercept \displaystyle60.
For inequality (3), the corresponding equation is
\displaystyle x-2y=0
or
\displaystyle x=2y
It represents the line passing through the origin and the points where it intersects the other two boundary lines.
Now, we determine the required solution regions.
For inequality (1), the checking point \displaystyle(0,0) gives
\displaystyle 0+2(0)\leq120
which is true. Hence, its solution set is the region containing the origin.
For inequality (2), the checking point \displaystyle(0,0) gives
\displaystyle 0+0\geq60
which is false. Hence, its solution set is the region on the side of the line \displaystyle x+y=60 not containing the origin.
For inequality (3),
\displaystyle x-2y\geq0\Rightarrow x\geq2y
so its solution set is the region on the side of the line \displaystyle x=2y containing the positive x-axis.
Also, \displaystyle x\geq0 and \displaystyle y\geq0 restrict the region to the first quadrant.
Therefore, the common feasible region is the bounded region \displaystyle ABCD, as shown in the diagram.
The corner points are
\displaystyle A(60,0),\; B(40,20),\; C(60,30),\; D(120,0).
Now, evaluate the objective function \displaystyle Z=5x+10y at each corner point.
| Corner Point | Value of \displaystyle Z=5x+10y |
|---|---|
| \displaystyle A(60,0) | \displaystyle Z=5(60)+10(0)=300 |
| \displaystyle B(40,20) | \displaystyle Z=5(40)+10(20)=400 |
| \displaystyle C(60,30) | \displaystyle Z=5(60)+10(30)=600 |
| \displaystyle D(120,0) | \displaystyle Z=5(120)+10(0)=600 |
The smallest value of \displaystyle Z is \displaystyle300, attained at \displaystyle A(60,0).
Therefore, the minimum value of \displaystyle Z is \displaystyle300 at \displaystyle(x,y)=(60,0).
For the maximum, observe that
\displaystyle Z=5x+10y=5(x+2y)
From constraint (1),
\displaystyle x+2y\leq120
Therefore,
\displaystyle Z=5(x+2y)\leq5(120)=600
Equality holds when
\displaystyle x+2y=120.
The feasible part of this line is the line segment joining \displaystyle C(60,30) and \displaystyle D(120,0). Hence, the maximum value is attained at every point on the line segment \displaystyle CD.
Thus, the maximum value of \displaystyle Z is \displaystyle600 at all points on the line segment joining \displaystyle C(60,30) and \displaystyle D(120,0).
Hence,
\boxed{\displaystyle Z_{\min}=300\text{ at }(60,0)}
and
\boxed{\displaystyle Z_{\max}=600\text{ at\ all\ points\ on\ }CD}
Question 8: Linear Programming 12.1
8. Minimise and Maximise \displaystyle Z=x+2y subject to the constraints:
\displaystyle x+2y\geq100\qquad ...(1)
\displaystyle 2x-y\leq0\qquad ...(2)
and
\displaystyle 2x+y\leq200\qquad ...(3)
\displaystyle x\geq0,\qquad y\geq0.
Solution
Think First… We will first find the feasible region using the boundary lines and checking points. Then we will evaluate the objective function at the corner points. Since the objective function is the same as the left-hand side of constraint (1), we should also look carefully at that boundary for the minimum.
We have to minimise and maximise \displaystyle Z=x+2y, subject to the given constraints.
Consider the corresponding equation of (1),
\displaystyle x+2y=100
Re-writing it in intercept form, we get
\displaystyle \frac{x}{100}+\frac{y}{50}=1
This represents the line \displaystyle AB with x-intercept \displaystyle100 and y-intercept \displaystyle50, as shown in the diagram.
For inequality (2), the corresponding equation is
\displaystyle 2x-y=0
or
\displaystyle y=2x.
This represents the line passing through the origin and the points \displaystyle A and \displaystyle D, as shown in the diagram.
For inequality (3), the corresponding equation is
\displaystyle 2x+y=200
Re-writing it in intercept form, we get
\displaystyle \frac{x}{100}+\frac{y}{200}=1
This represents the line \displaystyle CD with x-intercept \displaystyle100 and y-intercept \displaystyle200.
The constraints \displaystyle x\geq0 and \displaystyle y\geq0 restrict the region to the first quadrant.
Solution sets:
For inequality (1), using the checking point \displaystyle(0,0), we get
\displaystyle 0+2(0)\geq100
which is false. Therefore, its solution set is the region on the side of the line \displaystyle x+2y=100 away from the origin.
For inequality (2), take the checking point \displaystyle(0,1). We get
\displaystyle 2(0)-1\leq0
which is true. Therefore, its solution set is the region above the line \displaystyle y=2x.
For inequality (3), using the checking point \displaystyle(0,0), we get
\displaystyle 2(0)+0\leq200
which is true. Therefore, its solution set is the region containing the origin.
Combining all the solution sets with the first-quadrant restrictions, the common feasible region is the bounded region ABCD, as shown in the diagram.
We now find the corner points of the feasible region.
From the graph,
\displaystyle B(0,50),\qquad C(0,200).
Point \displaystyle A is the intersection of
\displaystyle x+2y=100
and
\displaystyle y=2x.
Substituting \displaystyle y=2x in \displaystyle x+2y=100, we get
\displaystyle x+2(2x)=100
\displaystyle 5x=100\Rightarrow x=20
Therefore,
\displaystyle y=2(20)=40.
Hence,
\displaystyle A(20,40).
Similarly, point \displaystyle D is the intersection of
\displaystyle y=2x
and
\displaystyle 2x+y=200.
Substituting \displaystyle y=2x, we get
\displaystyle 2x+2x=200
\displaystyle 4x=200\Rightarrow x=50
Therefore,
\displaystyle y=2(50)=100.
Hence,
\displaystyle D(50,100).
Thus, the corner points are
\displaystyle A(20,40),\; B(0,50),\; C(0,200),\; D(50,100).
Now, evaluate the objective function \displaystyle Z=x+2y at each corner point.
| Corner Point | Value of \displaystyle Z=x+2y |
|---|---|
| \displaystyle A(20,40) | \displaystyle Z=20+2(40)=100 |
| \displaystyle B(0,50) | \displaystyle Z=0+2(50)=100 |
| \displaystyle C(0,200) | \displaystyle Z=0+2(200)=400 |
| \displaystyle D(50,100) | \displaystyle Z=50+2(100)=250 |
The smallest value of \displaystyle Z is \displaystyle100, obtained at both \displaystyle A(20,40) and \displaystyle B(0,50).
But we can say from constraint (1),
\displaystyle x+2y\geq100.
Since \displaystyle Z=x+2y, every feasible point satisfies
\displaystyle Z\geq100.
Equality occurs when
\displaystyle x+2y=100.
The feasible part of this line is the line segment joining \displaystyle A(20,40) and \displaystyle B(0,50). Therefore, every point on the line segment AB gives the same minimum value.
Thus, there are infinitely many optimal solutions for the minimum value.
For the maximum, the largest value in the table is \displaystyle400, attained at \displaystyle C(0,200).
Hence, the maximum value of \displaystyle Z is \displaystyle400 at \displaystyle(x,y)=(0,200).
Hence,
\boxed{\displaystyle Z_{\min}=100\text{ at all points on the line segment }AB}
and
\boxed{\displaystyle Z_{\max}=400\text{ at }(0,200)}
Let’s solve this question of Linear Programming 12.1 which has no maximum value.
Question 9: Linear Programming 12.1
9. Maximise \displaystyle Z=-x+2y subject to the constraints:
\displaystyle x\geq3\qquad ...(1)
\displaystyle x+y\geq5\qquad ...(2)
and
\displaystyle x+2y\geq6\qquad ...(3)
\displaystyle y\geq0.
Solution
Think First… The feasible region may be unbounded. In such a case, simply comparing the values of the objective function at the corner points is not enough to conclude that a maximum exists.
We have to maximise \displaystyle Z=-x+2y, subject to the given constraints.
Consider the corresponding equation of (1),
\displaystyle x=3.
This represents the vertical line passing through \displaystyle(3,0) and parallel to the y-axis.
For inequality (2), the corresponding equation is
\displaystyle x+y=5
Re-writing it in intercept form, we get
\displaystyle \frac{x}{5}+\frac{y}{5}=1
This represents the line passing through the intercepts \displaystyle(5,0) and \displaystyle(0,5).
For inequality (3), the corresponding equation is
\displaystyle x+2y=6
Re-writing it in intercept form, we get
\displaystyle \frac{x}{6}+\frac{y}{3}=1
This represents the line passing through the intercepts \displaystyle(6,0) and \displaystyle(0,3).
The constraint \displaystyle y\geq0 restricts the region to the region on or above the x-axis.
Solution sets:
For inequality (1), the solution set is the region to the right of the line \displaystyle x=3.
For inequality (2), using the checking point \displaystyle(0,0), we get
\displaystyle 0+0\geq5
which is false. Therefore, its solution set is the region away from the origin.
Similarly, for inequality (3), using the checking point \displaystyle(0,0), we get
\displaystyle 0+2(0)\geq6
which is false. Therefore, its solution set is also the region away from the origin.
Combining all the solution sets, the common feasible region is the unbounded region XABCY, as shown in the diagram.
The finite corner points of the feasible region are
\displaystyle A(6,0),\qquad B(4,1),\qquad C(3,2).
Note: The points \displaystyle X(n,0) and \displaystyle Y(3,n) are marked on the graph only to show that the feasible region extends indefinitely. They are not corner points.
Now, evaluate the objective function \displaystyle Z=-x+2y at the finite corner points.
| Corner Point | Value of \displaystyle Z=-x+2y |
|---|---|
| \displaystyle A(6,0) | \displaystyle Z=-6+2(0)=-6 |
| \displaystyle B(4,1) | \displaystyle Z=-4+2(1)=-2 |
| \displaystyle C(3,2) | \displaystyle Z=-3+2(2)=1 |
The largest value among the corner points is \displaystyle1, attained at \displaystyle C(3,2).
However, the feasible region is unbounded. Therefore, we cannot conclude that \displaystyle1 is the maximum value. We need to check whether any feasible point can give a value greater than \displaystyle1.
To check this, consider the corresponding objective-function line
\displaystyle Z=1\quad\Rightarrow\quad-x+2y=1.
Now consider the inequality
\displaystyle-x+2y>1.
This represents the open half-plane on the side of the line \displaystyle-x+2y=1 where the values of \displaystyle Z are greater than \displaystyle1.
From the graph, we observe that this open half-plane has points in common with the feasible region. Therefore, there are feasible points for which
\displaystyle Z>1.
Hence, \displaystyle1 is not the maximum value. Moreover, since the feasible region extends indefinitely in the direction in which the values of \displaystyle Z increase, the objective function can take values greater than \displaystyle1 without bound.
Therefore, the objective function has no maximum value.
Hence,
\boxed{\displaystyle Z\text{ has no maximum value}}
And the last question of Linear Programming 12.1 which has no common feasible region.
Question 10: No Common Solution
10. Maximise \displaystyle Z=x+y subject to the constraints:
\displaystyle x-y\leq-1\qquad ...(1)
\displaystyle -x+y\leq0\qquad ...(2)
and
\displaystyle x\geq0,\qquad y\geq0.
Solution
Think First… Before finding corner points or evaluating the objective function, first check whether the constraints have any common solution. If there is no feasible region, there can be no maximum or minimum value.
We have to maximise \displaystyle Z=x+y, subject to the given constraints.
Consider the corresponding equation of (1),
\displaystyle x-y=-1
or
\displaystyle y=x+1.
This represents the line passing through the points \displaystyle(-1,0) and \displaystyle(0,1), as shown in the diagram.
For inequality (2), the corresponding equation is
\displaystyle -x+y=0
or
\displaystyle y=x.
This represents the line passing through the origin, as shown in the diagram.
Now, let us determine the solution sets of the two inequalities.
For (1),
\displaystyle x-y\leq-1
or
\displaystyle y\geq x+1.
Therefore, its solution set is the region above the line \displaystyle y=x+1.
For (2),
\displaystyle -x+y\leq0
or
\displaystyle y\leq x.
Therefore, its solution set is the region below the line \displaystyle y=x.
But the two lines are parallel, and the required solution regions are on opposite sides. In fact, the two inequalities require simultaneously
\displaystyle y\geq x+1\qquad\text{and}\qquad y\leq x.
This is impossible, because \displaystyle x+1>x for every real value of \displaystyle x.
Hence, there is no point satisfying both (1) and (2). Therefore, after also considering \displaystyle x\geq0 and \displaystyle y\geq0, there is still no common region.
Thus, the problem has no feasible region and hence no feasible solution.
Since there is no feasible solution, the objective function \displaystyle Z=x+y cannot attain a maximum value.
Hence,
\boxed{\displaystyle\text{No feasible region, so no maximum value of }Z}
Common Mistakes to Avoid
- Forgetting to convert the inequality into its corresponding equation: To draw the boundary line, first replace the inequality by an equality. For example, \displaystyle x+y\leq4 gives the boundary line \displaystyle x+y=4.
- Making the graph unnecessarily difficult: For a boundary line, use the intercept form whenever possible. For example, \displaystyle 5x+2y=10 can be written as \displaystyle\frac{x}{2}+\frac{y}{5}=1, giving the intercepts directly.
- Shading the wrong side of an inequality: After drawing the boundary line, use a checking point such as \displaystyle(0,0) to determine the required half-plane. Do not assume the shaded side without checking.
- Forgetting the non-negative constraints: The conditions \displaystyle x\geq0,\;y\geq0 restrict the feasible region to the first quadrant. Always include these constraints while finding the common feasible region.
- Taking points outside the feasible region: Only points satisfying all the constraints simultaneously belong to the feasible region. A point may lie on one boundary line but still not be a feasible point.
- Missing a corner point: Carefully identify every vertex of the feasible region, including the points where a boundary line meets the coordinate axes and where two boundary lines intersect.
- Assuming the corner-point method always gives the maximum or minimum: For a bounded feasible region, the maximum and minimum values occur at corner points. For an unbounded region, the largest or smallest corner-point value may not be the actual optimum; the required open half-plane must be checked.
- Missing multiple optimal solutions: If two corner points give the same maximum or minimum value of the objective function, every point on the line segment joining those two points also gives the same optimal value.
- Confusing an unbounded region with no feasible region: An unbounded feasible region contains infinitely many feasible points and extends indefinitely. A problem has no feasible solution only when there is no common region satisfying all the constraints.
- Stopping after finding the smallest or largest corner-point value in an unbounded region: In an unbounded region, a corner-point value alone does not prove that the required maximum or minimum exists. The relevant open half-plane must have no point in common with the feasible region.
- Not checking the objective function at every corner point: Once all corner points are identified, calculate the value of the objective function at each one before deciding the maximum or minimum.
- Giving only the optimal value: Always state both the optimal value of \displaystyle Z and the point or points at which it is attained. If infinitely many optimal solutions exist, mention the complete line segment.
Continue Learning
In the Linear Programming chapter, you learned how to formulate a linear programming problem using decision variables, an objective function, and linear constraints. You also learned how to solve such problems graphically using the feasible region and the Corner Point Method. These concepts are important for understanding how mathematical conditions can be used to find optimal solutions and are frequently tested in CBSE board examinations as well as CUET.
Next, continue with Probability. This chapter takes you into the world of conditional probability, independent events, Bayes’ theorem, and random variables. Before starting the chapter, make sure you are comfortable with the following concepts from Linear Programming:
- How to identify the decision variables and formulate a linear programming problem.
- How to identify the objective function and determine whether it has to be maximised or minimised.
- How to represent the given conditions as linear inequalities and non-negative constraints.
- How to convert a linear inequality into its corresponding boundary line and determine the required half-plane.
- How to find the feasible region by taking the common region satisfying all the constraints.
- How to identify the corner points of a feasible region and evaluate the objective function at each point.
- How to distinguish between bounded and unbounded feasible regions and understand their effect on the optimal value.
- How to recognise multiple optimal solutions, no maximum or minimum value, and cases where there is no feasible region.
Explore More
A good understanding of the concepts covered in Linear Programming is essential for solving problems involving linear inequalities, feasible regions, corner points, and objective functions. Always begin by identifying the decision variables and the objective function, write the given conditions as inequalities, and carefully determine the common feasible region using the corresponding boundary lines.
While solving graphical LPP questions, first identify whether the feasible region is bounded or unbounded, find all its corner points, and evaluate the objective function at these points. Be especially careful in cases involving multiple optimal solutions, an unbounded feasible region, or no feasible region. With regular practice, you will be able to interpret graphs correctly and solve Linear Programming problems accurately and confidently.
All the best and keep learning 👍
