Chapter 12 Linear Programming

Notes

Linear Programming – Complete Notes

1. Linear Programming Problem (LPP)

A Linear Programming Problem (LPP) is a mathematical problem in which a linear objective function is maximised or minimised subject to given linear constraints.

In linear programming, the variables and the conditions are related linearly.

1.1 Objective Function

The given linear function that is to be maximised or minimised is called the Objective Function.

It is generally represented by:

Z = ax + by

Here, x and y are variables, while a and b are constants.

The objective is to find the maximum or minimum value of Z.

1.2 Constraints

The given conditions expressed in the form of linear inequalities are called Constraints.

Examples:

• x + y ≤ 4
• x + 2y ≤ 8
• 2x + y ≥ 3

The values of x and y must satisfy all the given constraints.

1.3 Non-Negativity Conditions

The conditions:

x ≥ 0 and y ≥ 0

are called Non-Negativity Conditions.

These conditions restrict the feasible region to the first quadrant, including its boundary axes.

1.4 Feasible Region

The common region that satisfies all the given constraints, including the non-negativity conditions, is called the Feasible Region.

It is represented by the common shaded region in the graph.

1.5 Graphical Method

The graphical method is used to solve a Linear Programming Problem involving two variables.

Steps:

1. Write the objective function and all the constraints.
2. Convert each linear inequality into an equality to draw its boundary line.
3. Find two suitable points on each line, generally its intercepts.
4. Plot the lines on the coordinate plane.
5. Check a test point, such as (0, 0), wherever applicable, to identify the required half-plane.
6. Find the common feasible region satisfying all constraints.
7. Identify the corner points of the feasible region.
8. Substitute each corner point into the objective function Z.
9. Compare the values to obtain the required maximum or minimum.

2. Solved Example 1 – Maximisation

Question: Maximise the objective function:

Z = 3x + 4y

Subject to the constraints:

x + y ≤ 4

x ≥ 0, y ≥ 0

Solution

The given objective function is:

Z = 3x + 4y

The constraint is:

x + y ≤ 4 ...(A)

Changing the inequality into an equality:

x + y = 4 ...(1)

From equation (1), we obtain: