Chapter 12: Linear Programming

Linear programming is a mathematical modelling technique in which a linear function is maximized or minimized when subjected to various constraints. This technique has been useful for guiding quantitative decisions in business planning, in industrial engineering, and to a lesser extent, in the social and physical sciences.

Terminology

• Objective Function: A linear function $Z = ax + by$, where $a, b$ are constants, which has to be maximized or minimized is called a linear objective function. Variables $x$ and $y$ are called decision variables.
• Constraints: The linear inequalities or equations or restrictions on the variables of a linear programming problem are called constraints. The conditions $x \ge 0, y \ge 0$ are known as non-negative restrictions.
• Optimization Problem: A problem which seeks to maximize or minimize a linear function subject to certain constraints as determined by a set of linear inequalities is known as optimization problem. Linear programming problems (LPP) are a special type of optimization problem.

Graphical Method of Solving LPP

1. Formulate the problem in terms of decision variables and objective function.
2. Find the feasible region (common region determined by all constraints including non-negative constraints) and its corner points (vertices).
3. 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.
4. If feasible region is bounded, $M$ and $m$ are the maximum and minimum values of $Z$.
5. If feasible region is unbounded, $M$ is max if open half plane $ax + by > M$ has no point in common with the feasible region. Otherwise, $Z$ has no maximum value.

Competency-Based Questions

1. [CBSE 2022] Solve the following Linear Programming Problem graphically: Maximize $Z = 3x + 4y$ Subject to constraints: $x + y \le 4$ $x \ge 0, y \ge 0$

Solution:

The feasible region is bounded by $x = 0$ ($y$-axis), $y = 0$ ($x$-axis) and the line $x + y = 4$.

The corner points of the feasible region are:

$O(0, 0)$, $A(4, 0)$, and $B(0, 4)$.

Evaluate $Z = 3x + 4y$ at these corner points:

At $O(0, 0)$, $Z = 3(0) + 4(0) = 0$.

At $A(4, 0)$, $Z = 3(4) + 4(0) = 12$.

At $B(0, 4)$, $Z = 3(0) + 4(4) = 16$.

Since the region is bounded, the maximum value of $Z$ is 16, which occurs at $(0, 4)$.

2. [Sample Paper 2023] Solve the following LPP graphically: Minimize $Z = -3x + 4y$ Subject to: $x + 2y \le 8$ $3x + 2y \le 12$ $x \ge 0, y \ge 0$

Solution:

The feasible region is determined by the lines $x + 2y = 8$, $3x + 2y = 12$ and the axes.

Intersection of $x + 2y = 8$ and $3x + 2y = 12$:

Subtract first from second: $2x = 4 \implies x = 2$.

Substitute $x$ in first: $2 + 2y = 8 \implies 2y = 6 \implies y = 3$.

Intersection point is $B(2, 3)$.

The other corner points are $O(0,0)$, $A(4,0)$ (from $3x+2y=12$ intercept), $C(0,4)$ (from $x+2y=8$ intercept).

Evaluate $Z = -3x + 4y$ at corners:

$Z$ at $O(0,0) = 0$

$Z$ at $A(4,0) = -3(4) + 4(0) = -12$

$Z$ at $B(2,3) = -3(2) + 4(3) = -6 + 12 = 6$

$Z$ at $C(0,4) = -3(0) + 4(4) = 16$

The minimum value is $-12$ at the point $A(4, 0)$.

3. [CBSE 2019] Maximize $Z = x + 2y$ subject to the constraints $x \ge 3$, $x + y \ge 5$, $x + 2y \ge 6$, $y \ge 0$. Note that $x \ge 0$ since $x \ge 3$.

Solution:

Let’s find the feasible region. Note that all inequalities are $\ge$, meaning the region is likely unbounded.

Lines: $x = 3$, $x + y = 5$, $x + 2y = 6$.

Intersection $x = 3$ and $x + y = 5$: $y = 2 \implies P(3, 2)$.

Intersection $x + y = 5$ and $x + 2y = 6$: $(x+2y) - (x+y) = 6 - 5 \implies y = 1 \implies x = 4 \implies Q(4, 1)$.

Intersection $x + 2y = 6$ and $y = 0$: $x = 6 \implies R(6, 0)$.

The corner points of the unbounded feasible region are $P(3, 2)$, $Q(4, 1)$, $R(6, 0)$.

$Z = x + 2y$

$Z$ at $P(3, 2) = 3 + 2(2) = 7$

$Z$ at $Q(4, 1) = 4 + 2(1) = 6$

$Z$ at $R(6, 0) = 6 + 2(0) = 6$

The minimum value is 6. However, we are asked to maximize $Z$.

Since the feasible region is unbounded and the coefficients of objective function are positive ($1, 2$), the value of $x+2y$ can be made arbitrarily large by picking large bounded values in the region.

Therefore, the maximum value of $Z$ does not exist.