Linear Programming — Questions and Answers
Welcome to HSLC Guru. This lesson gives complete, step-by-step answers to every question in ASSEB Class 12 Mathematics Chapter 12, Linear Programming (ৰৈখিক প্ৰগ্ৰেমিং). This chapter has a single set of problems, Exercise 12.1, and no miscellaneous exercise. Each Linear Programming Problem is solved graphically by the Corner Point Method, with a labelled diagram of the feasible region, so you can follow every step and prepare confidently for your examination.
Summary
A Linear Programming Problem (LPP) is concerned with finding the optimal value (maximum or minimum) of a linear function $Z = ax + by$, called the objective function, of the decision variables $x$ and $y$, subject to a set of linear inequalities called constraints and the non-negative restrictions $x \geq 0$, $y \geq 0$. The word linear means every relation in the problem is of the first degree, and programming refers to choosing a particular plan of action that gives the best value.
The common region determined by all the constraints (including $x \geq 0$, $y \geq 0$) is the feasible region; every point in or on it is a feasible solution, and any point outside it is infeasible. A feasible region is bounded if it can be enclosed within a circle and unbounded otherwise. The feasible region of a system of linear inequalities is always a convex region.
We solve each LPP by the Corner Point Method: graph the constraints, find the feasible region and its corner points (vertices) by inspection or by solving the intersecting lines, and evaluate $Z = ax + by$ at each corner point. If the region is bounded, the largest and smallest of these values are the maximum and minimum of $Z$ (Theorem 2). If the region is unbounded, a value $M$ is the maximum only when the open half-plane $ax + by > M$ has no point in common with the feasible region; similarly $m$ is the minimum only when $ax + by < m$ has no common point. When two corner points give the same optimum value, every point on the line segment joining them is also optimal, giving multiple optimal solutions; and if the constraints have no common point, the LPP has no feasible solution.
Summary: ASSEB Class 12 Mathematics Chapter 12 Linear Programming explains how to formulate and graphically solve a linear programming problem by the Corner Point Method, covering the objective function, constraints, feasible region, bounded and unbounded regions, multiple optimal solutions and infeasible problems, with fully worked, figure-supported answers to Exercise 12.1 for Assam Board (ASSEB) Class 12 students.
Textbook Questions and Answers
Exercise 12.1
Solve the following Linear Programming Problems graphically.
In every problem we use the Corner Point Method: draw the boundary lines of the constraints, shade the feasible region, find its corner points (vertices), and evaluate the objective function $Z$ at each corner. For a bounded region the largest and smallest of these values are the maximum and minimum; for an unbounded region we test the open half-plane to confirm the optimum.
1. Maximise $Z = 3x + 4y$ subject to the constraints: $x + y \leq 4$, $x \geq 0$, $y \geq 0$.
Answer: The boundary line $x + y = 4$ meets the axes at $(4, 0)$ and $(0, 4)$. Together with $x \geq 0$ and $y \geq 0$, the feasible region is the triangle $OAB$ with corner points $O(0, 0)$, $A(4, 0)$ and $B(0, 4)$, which is bounded. We evaluate $Z = 3x + 4y$ at each corner.
- $O(0, 0):\ Z = 3(0) + 4(0) = 0$
- $A(4, 0):\ Z = 3(4) + 4(0) = 12$
- $B(0, 4):\ Z = 3(0) + 4(4) = 16$
The maximum value is $Z = 16$, attained at the point $(0, 4)$.
2. Minimise $Z = -3x + 4y$ subject to $x + 2y \leq 8$, $3x + 2y \leq 12$, $x \geq 0$, $y \geq 0$.
Answer: The line $x + 2y = 8$ meets the axes at $(8, 0)$ and $(0, 4)$; the line $3x + 2y = 12$ meets them at $(4, 0)$ and $(0, 6)$. Subtracting $x + 2y = 8$ from $3x + 2y = 12$ gives $2x = 4$, so $x = 2$ and then $y = 3$; the two lines meet at $(2, 3)$. The feasible region is the bounded quadrilateral $OABC$ with corners $O(0, 0)$, $A(4, 0)$, $B(2, 3)$ and $C(0, 4)$. Evaluate $Z = -3x + 4y$.
- $O(0, 0):\ Z = -3(0) + 4(0) = 0$
- $A(4, 0):\ Z = -3(4) + 4(0) = -12$
- $B(2, 3):\ Z = -3(2) + 4(3) = 6$
- $C(0, 4):\ Z = -3(0) + 4(4) = 16$
The smallest value is $Z = -12$. Hence the minimum value of $Z$ is $-12$, attained at the point $(4, 0)$.
3. Maximise $Z = 5x + 3y$ subject to $3x + 5y \leq 15$, $5x + 2y \leq 10$, $x \geq 0$, $y \geq 0$.
Answer: The line $3x + 5y = 15$ meets the axes at $(5, 0)$ and $(0, 3)$; the line $5x + 2y = 10$ meets them at $(2, 0)$ and $(0, 5)$. To find where they cross, multiply the first by $2$ and the second by $5$: $6x + 10y = 30$ and $25x + 10y = 50$. Subtracting gives $19x = 20$, so $x = \frac{20}{19}$; then $5 \cdot \frac{20}{19} + 2y = 10$ gives $2y = \frac{90}{19}$, so $y = \frac{45}{19}$. The feasible region is the bounded quadrilateral $OABC$ with corners $O(0, 0)$, $A(2, 0)$, $B\left(\frac{20}{19}, \frac{45}{19}\right)$ and $C(0, 3)$.
- $O(0, 0):\ Z = 5(0) + 3(0) = 0$
- $A(2, 0):\ Z = 5(2) + 3(0) = 10$
- $B\left(\frac{20}{19}, \frac{45}{19}\right):\ Z = 5 \cdot \frac{20}{19} + 3 \cdot \frac{45}{19} = \frac{100 + 135}{19} = \frac{235}{19} \approx 12.37$
- $C(0, 3):\ Z = 5(0) + 3(3) = 9$
The greatest value is $\frac{235}{19}$. Hence the maximum value of $Z$ is $\frac{235}{19} \approx 12.37$, attained at $\left(\frac{20}{19}, \frac{45}{19}\right)$.
4. Minimise $Z = 3x + 5y$ such that $x + 3y \geq 3$, $x + y \geq 2$, $x \geq 0$, $y \geq 0$.
Answer: The line $x + 3y = 3$ meets the axes at $(3, 0)$ and $(0, 1)$; the line $x + y = 2$ meets them at $(2, 0)$ and $(0, 2)$. Subtracting the equations gives $2y = 1$, so $y = \frac{1}{2}$ and $x = \frac{3}{2}$; they cross at $\left(\frac{3}{2}, \frac{1}{2}\right)$. Because both inequalities are of the type $\geq$, the feasible region is unbounded, with corner points $A(0, 2)$, $B\left(\frac{3}{2}, \frac{1}{2}\right)$ and $C(3, 0)$.
- $A(0, 2):\ Z = 3(0) + 5(2) = 10$
- $B\left(\frac{3}{2}, \frac{1}{2}\right):\ Z = 3 \cdot \frac{3}{2} + 5 \cdot \frac{1}{2} = \frac{9 + 5}{2} = 7$
- $C(3, 0):\ Z = 3(3) + 5(0) = 9$
The smallest corner value is $7$ at $B$. As the region is unbounded, we test the open half-plane $3x + 5y < 7$. Since every point of the feasible region satisfies $x + 3y \geq 3$ and $x + y \geq 2$, one can check that $3x + 5y \geq 7$ throughout the region, so $3x + 5y < 7$ has no point in common with it. Hence the minimum value of $Z$ is $7$, attained at $\left(\frac{3}{2}, \frac{1}{2}\right)$.
5. Maximise $Z = 3x + 2y$ subject to $x + 2y \leq 10$, $3x + y \leq 15$, $x \geq 0$, $y \geq 0$.
Answer: The line $x + 2y = 10$ meets the axes at $(10, 0)$ and $(0, 5)$; the line $3x + y = 15$ meets them at $(5, 0)$ and $(0, 15)$. Solving the two together: from $3x + y = 15$ we get $y = 15 – 3x$, and substituting in $x + 2y = 10$ gives $x + 2(15 – 3x) = 10$, i.e. $-5x = -20$, so $x = 4$ and $y = 3$; they cross at $(4, 3)$. The feasible region is the bounded quadrilateral $OABC$ with corners $O(0, 0)$, $A(5, 0)$, $B(4, 3)$ and $C(0, 5)$.
- $O(0, 0):\ Z = 3(0) + 2(0) = 0$
- $A(5, 0):\ Z = 3(5) + 2(0) = 15$
- $B(4, 3):\ Z = 3(4) + 2(3) = 18$
- $C(0, 5):\ Z = 3(0) + 2(5) = 10$
The greatest value is $Z = 18$. Hence the maximum value of $Z$ is $18$, attained at the point $(4, 3)$.
6. Minimise $Z = x + 2y$ subject to $2x + y \geq 3$, $x + 2y \geq 6$, $x \geq 0$, $y \geq 0$. Show that the minimum of $Z$ occurs at more than two points.
Answer: The line $2x + y = 3$ meets the axes at $\left(\frac{3}{2}, 0\right)$ and $(0, 3)$; the line $x + 2y = 6$ meets them at $(6, 0)$ and $(0, 3)$. The two lines cross at $(0, 3)$. Both constraints are of the type $\geq$, so the feasible region is unbounded. Its corner points are $A(0, 3)$ and $B(6, 0)$, joined by the edge lying on $x + 2y = 6$ (shown in red).
- $A(0, 3):\ Z = 0 + 2(3) = 6$
- $B(6, 0):\ Z = 6 + 2(0) = 6$
Both corner points give $Z = 6$. As the region is unbounded, test $x + 2y < 6$: since the constraint $x + 2y \geq 6$ holds everywhere in the feasible region, the half-plane $x + 2y < 6$ has no point in common with it, so the minimum value of $Z$ is $6$. Because $Z = x + 2y$ equals $6$ at both $A$ and $B$, and the edge $AB$ lies on the line $x + 2y = 6$, every point of the segment $AB$ gives $Z = 6$. Thus the minimum of $Z$ occurs at infinitely many points, that is, at more than two points.
7. Minimise and Maximise $Z = 5x + 10y$ subject to $x + 2y \leq 120$, $x + y \geq 60$, $x – 2y \geq 0$, $x \geq 0$, $y \geq 0$.
Answer: The boundary lines are $x + 2y = 120$ (through $(120, 0)$ and $(0, 60)$), $x + y = 60$ (through $(60, 0)$ and $(0, 60)$) and $x – 2y = 0$, i.e. $x = 2y$ (through the origin and $(120, 60)$). Solving in pairs: $x + y = 60$ with $x = 2y$ gives $3y = 60$, so $y = 20$, $x = 40$, the point $D(40, 20)$; $x + 2y = 120$ with $x = 2y$ gives $4y = 120$, so $y = 30$, $x = 60$, the point $C(60, 30)$. The feasible region is the bounded quadrilateral with corners $A(60, 0)$, $B(120, 0)$, $C(60, 30)$ and $D(40, 20)$.
- $A(60, 0):\ Z = 5(60) + 10(0) = 300$
- $B(120, 0):\ Z = 5(120) + 10(0) = 600$
- $C(60, 30):\ Z = 5(60) + 10(30) = 600$
- $D(40, 20):\ Z = 5(40) + 10(20) = 400$
The smallest value is $300$ and the largest is $600$. Hence the minimum value of $Z$ is $300$ at $(60, 0)$, and the maximum value of $Z$ is $600$. Since $Z = 600$ at both $B(120, 0)$ and $C(60, 30)$, the maximum is attained at every point of the segment $BC$ (multiple optimal solutions).
8. Minimise and Maximise $Z = x + 2y$ subject to $x + 2y \geq 100$, $2x – y \leq 0$, $2x + y \leq 200$, $x \geq 0$, $y \geq 0$.
Answer: The boundary lines are $x + 2y = 100$ (through $(100, 0)$ and $(0, 50)$), $2x – y = 0$, i.e. $y = 2x$ (through the origin and $(50, 100)$) and $2x + y = 200$ (through $(100, 0)$ and $(0, 200)$). Solving in pairs: $x + 2y = 100$ with $y = 2x$ gives $5x = 100$, so $x = 20$, $y = 40$, the point $B(20, 40)$; $2x + y = 200$ with $y = 2x$ gives $4x = 200$, so $x = 50$, $y = 100$, the point $C(50, 100)$. The feasible region is the bounded quadrilateral with corners $A(0, 50)$, $B(20, 40)$, $C(50, 100)$ and $D(0, 200)$.
- $A(0, 50):\ Z = 0 + 2(50) = 100$
- $B(20, 40):\ Z = 20 + 2(40) = 100$
- $C(50, 100):\ Z = 50 + 2(100) = 250$
- $D(0, 200):\ Z = 0 + 2(200) = 400$
The largest value is $400$ and the smallest is $100$. Hence the maximum value of $Z$ is $400$ at $(0, 200)$, and the minimum value of $Z$ is $100$. Since $Z = 100$ at both $A(0, 50)$ and $B(20, 40)$, the minimum is attained at every point of the segment $AB$ (multiple optimal solutions).
9. Maximise $Z = -x + 2y$, subject to the constraints: $x \geq 3$, $x + y \geq 5$, $x + 2y \geq 6$, $y \geq 0$.
Answer: The boundary lines are $x = 3$ (vertical), $x + y = 5$ (through $(5, 0)$ and $(0, 5)$) and $x + 2y = 6$ (through $(6, 0)$ and $(0, 3)$). The corner points, found from the binding constraints, are: $x = 3$ with $x + y = 5$ gives $C(3, 2)$; $x + y = 5$ with $x + 2y = 6$ gives $B(4, 1)$; $x + 2y = 6$ with $y = 0$ gives $A(6, 0)$. All constraints are of the type $\geq$ (with no upper bound), so the feasible region is unbounded, extending upward along $x = 3$ and rightward along the $x$-axis.
- $A(6, 0):\ Z = -6 + 2(0) = -6$
- $B(4, 1):\ Z = -4 + 2(1) = -2$
- $C(3, 2):\ Z = -3 + 2(2) = 1$
The largest corner value is $1$ at $C(3, 2)$. Because the region is unbounded, we test the open half-plane $-x + 2y > 1$. The point $(3, 10)$ is feasible ($x = 3 \geq 3$, $x + y = 13 \geq 5$, $x + 2y = 23 \geq 6$, $y \geq 0$) and gives $-3 + 20 = 17 > 1$, so $-x + 2y > 1$ does have points in common with the feasible region. Moving up the line $x = 3$, the value $-3 + 2y$ grows without bound. Hence $Z$ has no maximum value subject to the given constraints.
10. Maximise $Z = x + y$, subject to $x – y \leq -1$, $-x + y \leq 0$, $x \geq 0$, $y \geq 0$.
Answer: Rewrite the constraints. From $x – y \leq -1$ we get $y \geq x + 1$, so the required points lie above the line $y = x + 1$. From $-x + y \leq 0$ we get $y \leq x$, so the required points lie below the line $y = x$. The lines $y = x + 1$ and $y = x$ are parallel, and $y = x + 1$ lies entirely above $y = x$. A point would need $x + 1 \leq y \leq x$, which forces $x + 1 \leq x$, i.e. $1 \leq 0$ — impossible.
Therefore no point satisfies all the constraints simultaneously; there is no feasible region. The problem has no feasible solution, and hence $Z = x + y$ has no maximum value.
Additional Questions and Answers
Multiple Choice Questions
1. In a linear programming problem, the optimal value of the objective function occurs at
(A) the centre of the feasible region (B) a corner point (vertex) of the feasible region (C) the origin always (D) any interior point
Answer: (B) a corner point (vertex) of the feasible region. By the fundamental theorem, if $Z = ax + by$ has an optimal value it occurs at a corner point of the feasible region.
2. The objective function $Z = ax + by$ of an LPP is always a
(A) quadratic function (B) linear function (C) constant (D) exponential function
Answer: (B) linear function. Every relation in an LPP is of the first degree.
3. A feasible region is said to be bounded if
(A) it extends indefinitely (B) it can be enclosed within a circle (C) it is empty (D) it is a single point
Answer: (B) it can be enclosed within a circle. Otherwise the region is called unbounded.
4. If the feasible region of an LPP is unbounded, then a maximum value of $Z = ax + by$ ($a, b > 0$)
(A) always exists (B) may not exist (C) is always $0$ (D) is always at the origin
Answer: (B) may not exist. For an unbounded region the objective function need not attain a maximum (or minimum); it exists only if the corresponding open half-plane has no point in common with the region.
5. The conditions $x \geq 0$, $y \geq 0$ in an LPP are called
(A) objective constraints (B) non-negative restrictions (C) optimal constraints (D) decision variables
Answer: (B) non-negative restrictions.
6. The feasible region determined by a system of linear inequalities is always
(A) a convex region (B) a concave region (C) a circle (D) unbounded
Answer: (A) a convex region.
7. The corner points of a feasible region are $(0, 0)$, $(0, 8)$, $(4, 10)$, $(6, 8)$ and $(6, 0)$. The maximum value of $Z = 3x + 2y$ is
(A) $16$ (B) $32$ (C) $34$ (D) $18$
Answer: (C) $34$. The values of $Z$ are $0, 16, 32, 34, 18$; the largest is $34$ at $(6, 8)$.
8. The corner points of a bounded feasible region are $(0, 3)$, $(1, 1)$ and $(3, 0)$. The minimum value of $Z = 2x + 5y$ is
(A) $15$ (B) $7$ (C) $6$ (D) $0$
Answer: (C) $6$. The values of $Z$ are $15, 7, 6$; the smallest is $6$ at $(3, 0)$.
Fill in the Blanks
1. A linear programming problem seeks the ________ value (maximum or minimum) of the objective function.
Answer: optimal
2. The common region determined by all the constraints, including $x \geq 0$ and $y \geq 0$, is called the ________ region.
Answer: feasible
3. The variables $x$ and $y$ whose values are to be found in an LPP are called ________ variables.
Answer: decision
4. If two corner points give the same maximum value of $Z$, then every point on the ________ joining them also gives that value.
Answer: line segment
5. A feasible region that cannot be enclosed within a circle is called ________.
Answer: unbounded
True or False
1. The optimal value of the objective function in an LPP always occurs at a corner point of the feasible region.
Answer: True. This is the corner-point principle used to solve every LPP graphically.
2. A linear programming problem always has a unique optimal solution.
Answer: False. It may have multiple optimal solutions (all points on an edge) or no feasible solution at all.
3. If the feasible region is empty, the LPP has no feasible solution.
Answer: True. When the constraints have no common point there is no feasible solution.
4. For a bounded feasible region, the objective function attains both a maximum and a minimum value.
Answer: True, and each of them occurs at a corner point of the region (Theorem 2).
5. The feasible region of an LPP can be a non-convex region.
Answer: False. The feasible region determined by linear inequalities is always convex.
Short Answer Questions
1. Define the objective function and the constraints of a linear programming problem.
Answer: The objective function is the linear function $Z = ax + by$ (with constants $a, b$) that has to be maximised or minimised. The constraints are the linear inequalities or equations that restrict the values of the decision variables $x$ and $y$; the special constraints $x \geq 0$, $y \geq 0$ are the non-negative restrictions.
2. State the steps of the Corner Point Method.
Answer: (i) Graph the constraints and identify the feasible region. (ii) Find the corner points (vertices) by inspection or by solving the intersecting lines. (iii) Evaluate $Z = ax + by$ at each corner point. (iv) If the region is bounded, the largest and smallest of these values are the maximum and minimum. If the region is unbounded, check whether the open half-plane $ax + by > M$ (for a maximum) or $ax + by < m$ (for a minimum) has any point in common with the feasible region; the optimum exists only if it does not.
3. The corner points of a feasible region are $O(0, 0)$, $A(5, 0)$, $B(3, 4)$ and $C(0, 5)$. Find the maximum and minimum values of $Z = 4x + 3y$.
Answer: $Z(O) = 0$, $Z(A) = 4(5) + 3(0) = 20$, $Z(B) = 4(3) + 3(4) = 24$, $Z(C) = 4(0) + 3(5) = 15$. The maximum value is $24$ at $(3, 4)$ and the minimum value is $0$ at $(0, 0)$.
4. Solve graphically: Minimise $Z = 2x + 3y$ subject to $x + y \geq 5$, $x \geq 0$, $y \geq 0$.
Answer: The line $x + y = 5$ meets the axes at $(5, 0)$ and $(0, 5)$, and the region $x + y \geq 5$ with $x, y \geq 0$ is unbounded with corner points $(5, 0)$ and $(0, 5)$. Here $Z(5, 0) = 10$ and $Z(0, 5) = 15$, so the smallest corner value is $10$. Testing $2x + 3y < 10$ shows it has no point in common with the region, so the minimum value of $Z$ is $10$, attained at $(5, 0)$.
Key Terms
| Term | Meaning |
|---|---|
| Linear Programming Problem (LPP) | A problem of finding the optimal (maximum or minimum) value of a linear objective function subject to linear constraints and non-negativity. |
| Objective function | The linear function $Z = ax + by$ ($a, b$ constants) that is to be maximised or minimised. |
| Decision variables | The variables $x$ and $y$ whose values are to be determined. |
| Constraints | The linear inequalities or equations that restrict the values of the decision variables. |
| Non-negative restrictions | The constraints $x \geq 0$ and $y \geq 0$. |
| Feasible region | The common region satisfying all the constraints (also called the solution region). |
| Feasible solution | Any point lying within or on the boundary of the feasible region. |
| Infeasible solution | Any point lying outside the feasible region. |
| Optimal (feasible) solution | A feasible point that gives the optimal (maximum or minimum) value of $Z$. |
| Corner point (vertex) | The point of intersection of two boundary lines of the feasible region; the optimum occurs here. |
| Bounded / Unbounded region | A feasible region is bounded if it can be enclosed within a circle; otherwise it is unbounded. |
| Corner Point Method | The graphical method of evaluating $Z$ at every corner point to locate the optimal value. |