Terms of Linear Programming Problem (LPP)

1.0Introduction to Linear Programming Problem (LPP)

Linear Programming Problem (LPP) is an important chapter in the JEE Mathematics syllabus. It deals with optimizing (maximizing or minimizing) a linear objective function, subject to a set of linear inequalities or equations called constraints. LPP is widely used in various fields such as economics, business, engineering, and logistics to find the best possible solution to a problem within given limitations.

For JEE aspirants, understanding the basic terms of LPP is critical, as many questions require you to identify and utilize these terms to set up and solve the problem.

2.0Key Terms in Linear Programming

Let’s explore the essential terms in LPP, which form the foundation for solving any linear programming problem.

1. Objective Function: The objective function is the mathematical expression representing the quantity to be maximized or minimized. It is always linear in terms of the decision variables.

General Form: [ Z = ax + by ]

where ( Z ) is the objective function, ( x ) and ( y ) are the decision variables, and ( a ), ( b ) are constants.

• Maximization Example: Maximizing profit, output, or efficiency.
• Minimization Example: Minimizing cost, loss, or waste.

2. Decision Variables: Decision variables are the unknowns in the LPP whose values need to be determined. They represent the quantities to be optimized.

Example: If a factory produces two products ( x ) and ( y ), then ( x ) and ( y ) are the decision variables.

3. Constraints: Constraints are linear inequalities or equations that define the limitations or restrictions on the decision variables. These could be related to resources like time, labor, raw material, etc.

General Form:

$$\begin{gathered} [ax+by\le c] \\ [dx+ey\ge f] \\ [gx+hy=k] \end{gathered}$$

4. Non-negativity Restrictions: In most real-life problems, negative values for decision variables are not meaningful. Hence, we always have: $[x\ge 0,y\ge 0]$. These are called non-negativity restrictions.

5. Feasible Region: The feasible region is the set of all possible points (values of decision variables) that satisfy all the constraints and non-negativity conditions simultaneously. Graphically, it is the intersection of all half-planes defined by the constraints.

6. Feasible Solution: Any point within the feasible region is called a feasible solution. It satisfies all the constraints of the problem.

7. Optimal Solution: An optimal solution is a feasible solution that optimizes (maximizes or minimizes) the objective function. In two-variable problems, this is usually found at a vertex (corner point) of the feasible region.

8. Bounded and Unbounded Solutions

• Bounded Solution: If the feasible region is enclosed and the objective function has both a maximum and minimum value.
• Unbounded Solution: If the feasible region is open and the objective function can increase or decrease without limit.

9. Corner Point Theorem: The corner point theorem states that the optimal value of the objective function in a linear programming problem (if it exists) occurs at a vertex (corner point) of the feasible region.

3.0Solved Examples on Linear Programming

Example 1: Maximizing Profit

Problem: A company produces two products, A and B. Each unit of A requires 2 hours of labor and 3 units of raw material. Each unit of B requires 4 hours of labor and 2 units of raw material. The company has a maximum of 100 labor hours and 90 units of raw material available. The profit from each unit of A is ₹40 and from B is ₹50. Formulate the LPP and find the number of units of A and B to be produced to maximize profit.

Solution:

Let ( x ) = number of units of A, ( y ) = number of units of B.

Objective Function: Maximize ( Z = 40x + 50y )

Constraints:

• Labor: $(2x+4y\le 100)$
• Raw Material: $(3x+2y\le 90)$
• Non-negativity: $(x\ge 0,y\ge 0)$

Graphing these inequalities and finding the corner points (by solving equations pairwise):

1. $(2x+4y=100⟹x+2y=50)$
2. ( 3x + 2y = 90 )

Solving,

$$\begin{gathered} (x+2y=50) \\ (3x+2y=90) \end{gathered}$$

Subtract:

$(2x=40⟹x=20)$

Put ( x = 20 ) in (1): ( $20+2y=50⟹2y=30⟹y=15$ )

Corner Points:

• (0,0), (0,25), (30,0), (20,15)

Evaluating Z at each:

• (0,0): ( Z = 0 )
• (0,25): ( Z = 40·0 + 50·25 = 1250 )
• (30,0): ( 40·30 + 50·0 = 1200 )
• (20,15): ( 40·20 + 50·15 = 800 + 750 = 1550 )

Max Profit: ( Z = ₹1550 ) at ( x = 20, y = 15 ).

Example 2: Minimizing Transportation Cost

Problem: A company needs to transport goods from two warehouses to a market. Warehouse 1 can supply up to 70 tons, and warehouse 2 up to 50 tons. The market requires 90 tons. The cost per ton is ₹40 from warehouse 1 and ₹30 from warehouse 2. How much should be transported from each warehouse to minimize cost?

Solution:

Let ( x ) = tons from warehouse 1, ( y ) = tons from warehouse 2.

Objective Function:
Minimize ( Z = 40x + 30y )

Constraints:

• $(x\le 70)$
• $(y\le 50)$
• $(x+y\ge 90)$
• $(x\ge 0,y\ge 0)$

Graphing and finding intersection points:

1. ( x = 70 )
2. ( y = 50 )
3. ( x + y = 90 )

Possible points: (70,20), (40,50), (70,50)

Evaluate Z:

• (70,20): ( 40·70 + 30·20 = 2800 + 600 = 3400 )
• (40,50): ( 40·40 + 30·50 = 1600 + 1500 = 3100 )
• (70,50): ( 40·70 + 30·50 = 2800 + 1500 = 4300 )

Min Cost: ₹3100 (from 40 tons from warehouse 1, 50 tons from warehouse 2).

Example 3: Feasible Region and Bounded Solution

Problem: Solve the following LPP graphically and find the maximum value of ( Z = 5x + 3y ):

Subject to

$$\begin{gathered} (x+y\le 8) \\ (x\ge 2) \\ (y\ge 1) \\ (x,y\ge 0) \end{gathered}$$

Solution:

Plot the constraints:

• ( x + y = 8 ) (Region below the line)
• ( x = 2 ) (Region right of line)
• ( y = 1 ) (Region above the line)

Corner Points: (2,1), (2,6), (7,1), (8,0)

Evaluate Z:

• (2,1): ( 52 + 31 = 10 + 3 = 13 )
• (2,6): ( 52 + 36 = 10 + 18 = 28 )
• (7,1): ( 57 + 31 = 35 + 3 = 38 )
• (8,0): ( 5*8 = 40 )

Check which of these are within all constraints. (8,0) is not, since ( $y\ge 1$ ). So, maximum at (7,1): ( Z = 38 ).

Example 4: Unbounded Solution

Problem: Maximize ( Z = x + y )

Subject to

$$\begin{gathered} (x-y\ge 1) \\ (x+y\ge 2) \\ (x,y\ge 0) \end{gathered}$$

Solution:

Plot the constraints:

• ( x - y = 1 ) (Region above the line)
• ( x + y = 2 ) (Region right/above the line)

Feasible region is unbounded above, so as ( x ) and ( y ) increase, ( Z ) increases without bound.