Linear Programming Class XII Chapter 12

 Class XII  Chapter 12 

Linear Programming Problems

Basic concepts based on Linear Programming Problems (LPP) Class XII chapter 12 strictly according to the CBSE syllabus.

Optimisation problem

A problem which seeks to maximise or minimise a linear function (say of two variables x and y) subject to certain constraints as determined by a set of linear inequalities is called an optimisation problem.

Linear programming problems are special type of optimisation problems.

Linear Programming

Linear Programming (LP) is a mathematical technique used to optimize a linear objective function, subject to a set of linear inequality or equality constraints. It’s widely applied in various fields, such as economics, business, engineering, and military operations.

Key Components of Linear Programming:

Linear Objective Function:

Linear function Z = ax + by, where a, b are constants, that needs to be maximized or minimized is called linear objective function. For example, profit function is maximized or cost function is minimized are the Linear Objective Functions

Decision Variables:

The variables that decision-makers will decide the values, within the constraints are called Decision Variables. x and y are the decision variables.

Non-Negativity Restriction:

The decision variables x & y are often restricted to be non-negative.

The conditions x ≥ 0, y ≥ 0 are called non-negative restrictions.

Constraints

The linear inequalities or equations or restrictions or limitations on the decision variables which define the feasible region of a linear programming problem are called constraints.

Feasible region:

The common region determined by all the constraints including non-negative constraints x ≥ 0, y ≥ 0 of a linear programming problem is called the feasible region (or solution region) for the problem.

The region other than feasible region is called an infeasible region.

Feasible solutions:

Points within and on the boundary of the feasible region represent feasible solutions of the constraints.

Any point outside the feasible region is called an infeasible solution.

Optimal (feasible) solution:

Any point in the feasible region that gives the optimal value (maximum or minimum) of the objective function is called an optimal solution. Optimal solution of the objective function always occurs at the corner point of the feasible region.

Corner Point

A corner point of a feasible region is a point in the region which is the intersection of two boundary lines.

Convex Region:

The feasible region in a Linear Programming Problem is always a convex region, meaning that a line segment connecting any two points within the regionlies entirely within the region.

Graphical method of solving Linear Programming Problems or 

This method is a visual approach  to solve linear programming problems. It involves the plotting the constraints as lines on the graph  and identifying the feasible region, which represents the set of all possible solutions that satisfy the constraints. This method is also called Corner Point Method of solving the Linear Programming Problems.

Working rule for making feasible region.

To determine the feasible region, consider each constraint as an inequality. Plot the corresponding line and shade the region that satisfies the inequality.

If the origion (0, 0) satisfy the inequality, shade the region containing the origin. If the region does not satisfy the inequality then shade the region opposite to the origin.

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.

If R is unbounded, then a maximum or a minimum value of the objective function may or may not exist. However, if it exists, it must occur at a corner point of R.

A feasible region of a system of linear inequalities is said to be bounded if it can be enclosed within a circle. Otherwise, it is called unbounded.

Unbounded means that the feasible region can be extended indefinitely in any direction.

Algorithm for corner method

This method comprises of the following steps:

1. Find the feasible region of the linear programming problem and determine its corner points (vertices) 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.

4. In case, the feasible region is unbounded, we have:

(a) 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.

(b) Similarly, 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.

5. Multiple optimal solutions: If two corner points A and B produce same maximum value for optimal function (Z) then Z is maximum at every point on the line segment AB. Same is also true in the case if the two points produce same minimum value.

THANKS FOR YOUR VISIT

PLEASE COMMENT BELOW