Mathematics: Class 12 (Book 2) — Chapter 6: LINEAR PROGRAMMING

In day-to-day life, we often encounter situations where we need to make decisions to maximize profit or minimize cost under limited resources. These are called optimisation problems .

Consider a typical real-life scenario of a furniture dealer:

• The dealer invests in only two items: tables and chairs.
• Total investment capital available: Rs 50,000.
• Total storage capacity: at most 60 pieces.
• Cost of a table: Rs 2500; Cost of a chair: Rs 500.
• Estimated profit: Rs 250 per table; Rs 75 per chair.
• Objective: Determine the number of tables and chairs to buy to maximize total profit.

To formulate this problem mathematically, we define the decision variables :

• Let $x$ be the number of tables purchased.
• Let $y$ be the number of chairs purchased.

Since the number of items cannot be negative, we have the non-negative constraints :

The investment constraint is governed by the available capital of Rs 50,000:

The storage constraint is governed by the maximum capacity of 60 pieces:

The dealer's objective is to maximize the total profit, represented by the linear function $Z$:

• Objective Function : A linear function $Z = ax + by$, where $a, b$ are constants, which has to be maximized or minimized.
• Decision Variables : The variables $x$ and $y$ in the objective function.
• Constraints : The linear inequalities or equations or restrictions on the variables of a linear programming problem.
• Non-negative Restrictions : The conditions $x \ge 0, y \ge 0$ which ensure the physical viability of the decision variables.
• Linear Programming Problem (LPP) : A problem concerned with finding the optimal value (maximum or minimum) of a linear objective function of several variables, subject to linear constraints.

• Feasible Region : The common region determined by all the constraints, including non-negative constraints $x, y \ge 0$, of a linear programming problem. It is also called the solution region.
• Feasible Solutions : Points within and on the boundary of the feasible region. Every point in this region represents a feasible choice.
• Infeasible Region : The region other than the feasible region.
• Infeasible Solutions : Any point outside the feasible region.
• Optimal Solution : Any point in the feasible region that gives the optimal value (maximum or minimum) of the objective function.

The graphical solution of linear programming problems is based on two fundamental theorems:

• Theorem 1: Let $R$ be the feasible region (convex polygon) for a linear programming problem and let $Z = ax + by$ be the objective function. When $Z$ has an optimal value (maximum or minimum), where the variables $x$ and $y$ are subject to constraints described by linear inequalities, this optimal value must occur at a corner point (vertex) of the feasible region.
• Theorem 2: Let $R$ be the feasible region for a linear programming problem, and let $Z = ax + by$ be the objective function. If $R$ is bounded , then the objective function $Z$ has both a maximum and a minimum value on $R$ and each of these occurs at a corner point (vertex) of $R$.
• Remark on Unbounded Regions: If the feasible region $R$ is unbounded , then a maximum or a minimum value of the objective function may not exist. However, if it exists, it must occur at a corner point of $R$.

This method comprises the following systematic steps:

1. Find the feasible region of the linear programming problem and determine its corner points (vertices) either by inspection or by solving the two equations of the lines intersecting at that point.
2. Evaluate the objective function $Z = ax + by$ at each corner point. Let $M$ and $m$, respectively, denote the largest and smallest values of these points.
3. • When the feasible region is bounded , $M$ and $m$ are the maximum and minimum values of $Z$.
   • When the feasible region is unbounded :
     1. $M$ is the maximum value of $Z$, if the open half plane determined by $ax + by > M$ has no point in common with the feasible region. Otherwise, $Z$ has no maximum value.
     2. $m$ is the minimum value of $Z$, if the open half plane determined by $ax + by < m$ has no point in common with the feasible region. Otherwise, $Z$ has no minimum value.

Mathematical Problem Statement (Example 1):

Maximise $Z = 4x + y$ subject to the constraints:

$$x + y \le 50, \quad 3x + y \le 90, \quad x \ge 0, \quad y \ge 0$$

---

Step-by-Step Algorithmic Solution Trace:

1. Plot the boundary lines $x + y = 50$ and $3x + y = 90$.
2. Identify the bounded feasible region $OABC$ determined by the inequalities.
3. Find the coordinates of the corner points:
   • $O(0, 0)$
   • $A(30, 0)$ (intersection of $3x + y = 90$ with the x-axis)
   • $B(20, 30)$ (intersection of $x + y = 50$ and $3x + y = 90$)
   • $C(0, 50)$ (intersection of $x + y = 50$ with the y-axis)
4. Evaluate $Z = 4x + y$ at each corner point:

   Corner Point	Corresponding Value of $Z = 4x + y$
   $O(0, 0)$	$0$
   $A(30, 0)$	$120$ (Maximum)
   $B(20, 30)$	$110$
   $C(0, 50)$	$50$

Final Evaluation Output: The maximum value of $Z$ is $120$ at the point $(30, 0)$.

Mathematical Problem Statement (Example 2):

Minimise $Z = 200x + 500y$ subject to the constraints:

$$x + 2y \ge 10, \quad 3x + 4y \le 24, \quad x \ge 0, \quad y \ge 0$$

---

Step-by-Step Algorithmic Solution Trace:

1. Plot the boundary lines $x + 2y = 10$ and $3x + 4y = 24$.
2. Identify the bounded feasible region $ABC$ determined by the inequalities.
3. Find the coordinates of the corner points:
   • $A(0, 5)$
   • $B(4, 3)$ (intersection of $x + 2y = 10$ and $3x + 4y = 24$)
   • $C(0, 6)$
4. Evaluate $Z = 200x + 500y$ at each corner point:

   Corner Point	Corresponding Value of $Z = 200x + 500y$
   $A(0, 5)$	$2500$
   $B(4, 3)$	$2300$ (Minimum)
   $C(0, 6)$	$3000$

Final Evaluation Output: The minimum value of $Z$ is $2300$ at the point $(4, 3)$.

Mathematical Problem Statement (Example 3 - Multiple Optimal Solutions):

Minimise and Maximise $Z = 3x + 9y$ subject to the constraints:

$$x + 3y \le 60, \quad x + y \ge 10, \quad x \le y, \quad x \ge 0, \quad y \ge 0$$

---

Step-by-Step Algorithmic Solution Trace:

1. Plot the boundary lines $x + 3y = 60$, $x + y = 10$, and $x = y$.
2. Identify the bounded feasible region $ABCD$.
3. Find the coordinates of the corner points:
   • $A(0, 10)$
   • $B(5, 5)$
   • $C(15, 15)$
   • $D(0, 20)$
4. Evaluate $Z = 3x + 9y$ at each corner point:

   Corner Point	Corresponding Value of $Z = 3x + 9y$
   $A(0, 10)$	$90$
   $B(5, 5)$	$60$ (Minimum)
   $C(15, 15)$	$180$ (Maximum)
   $D(0, 20)$	$180$ (Maximum)

Final Evaluation Output: The minimum value of $Z$ is $60$ at $(5, 5)$. The maximum value of $Z$ is $180$, which occurs at two corner points $C(15, 15)$ and $D(0, 20)$, and therefore at every point on the line segment joining $C$ and $D$.

Mathematical Problem Statement (Example 4):

Determine graphically the minimum value of the objective function $Z = -50x + 20y$ subject to the constraints:

$$2x - y \ge -5, \quad 3x + y \ge 3, \quad 2x - 3y \le 12, \quad x \ge 0, \quad y \ge 0$$

---

Step-by-Step Algorithmic Solution Trace:

1. Plot the boundary lines $2x - y = -5$, $3x + y = 3$, and $2x - 3y = 12$.
2. Identify the feasible region, which is unbounded .
3. Find the coordinates of the corner points:
   • $(0, 5)$
   • $(0, 3)$
   • $(1, 0)$
   • $(6, 0)$
4. Evaluate $Z = -50x + 20y$ at each corner point:

   Corner Point	Corresponding Value of $Z = -50x + 20y$
   $(0, 5)$	$100$
   $(0, 3)$	$60$
   $(1, 0)$	$-50$
   $(6, 0)$	$-300$ (Smallest)

5. Since the feasible region is unbounded, we must check if the minimum value is indeed $-300$. We graph the inequality: $$-50x + 20y < -300 \implies -5x + 2y < -30$$
6. Check if the resulting open half plane has points in common with the feasible region. Since it has common points, the minimum value of $-300$ is not attained.

Final Evaluation Output: $Z = -50x + 20y$ has no minimum value subject to the given constraints.

Mathematical Problem Statement (Example 5):

Minimise $Z = 3x + 2y$ subject to the constraints:

$$x + y \ge 8, \quad 3x + 5y \le 15, \quad x \ge 0, \quad y \ge 0$$

---

Step-by-Step Algorithmic Solution Trace:

1. Plot the boundary lines $x + y = 8$ and $3x + 5y = 15$.
2. Observe that the half-plane $x + y \ge 8$ lies above the line, while $3x + 5y \le 15$ lies below the line.
3. There is no common region satisfying all constraints simultaneously.

Final Evaluation Output: The problem has no feasible region and hence no feasible solution.

• An LPP seeks to find the optimal value of a linear objective function subject to linear constraints .
• The feasible region is always a convex region.
• The optimal solution always occurs at one of the corner points (vertices) of the feasible region.
• If two corner points produce the same optimal value, then every point on the line segment joining them also produces the same optimal value.