Math Notes For Class 12 Linear Programming Chapter 12 Download PDF

Chapter 12: Linear Programming

Chapter 12: Linear Programming

It is an important optimization (maximization or minimization) technique used in decision making is business and everyday life for obtaining the maximum or minimum values as required of a linear expression to satisfying certain number of given linear restrictions.

The linear programming problem in general calls for optimizing a linear function of variables called the objective function subject to a set of linear equations and/or linear inequations called the constraints or restrictions.

The function which is to be optimized (maximized/minimized) is called an objective function.

The system of linear inequations (or equations) under which the objective function is to be optimized is called constraints.

All the variables considered for making decisions assume non-negative values.

A general LPP can be stated as (Max/Min) z = c_{l}x_{l} + c_{2}x_{2} + â€¦ + c_{n}x_{n} (Objective function)
subject to constraints

and the non-negative restrictions x_{l}, x_{2},â€¦.., xn â‰¥ 0 where all a_{l}_{1}, a_{l}_{2},â€¦., amn; b_{l}, b_{2},â€¦., bm; c_{l}, c_{2},â€¦., cn are constants and x_{l},
x_{2},â€¦., xn are variables.

The positive variables which are added to left hand sides of the constraints to convert them into equalities are called the slack variables. The positive variables which are subtracted from the left hand sides of the constraints to convert them into equalities are called the surplus variables.

**(i) Solution of a LPP** A set of values of the variables x_{l}, x_{2},â€¦., x_{n} satisfying the constraints of
a LPP is called a solution of the LPP.

(ii) Feasible Solution of a LPP A set of values of the variables x_{l}, x_{2},â€¦., x_{n} satisfying the constraints and non-negative restrictions of a LPP is called a feasible solution of the LPP.

(iii) Optimal Solution of a LPP A feasible solution of a LPP is said to, be optimal (or optimum), if it also optimizes the objective function of the
problem.

(iv) Graphical Solution of a LPP The solution of a LPP obtained by graphical method i.e., by
drawing the graphs corresponding to the constraints and the non-negative restrictions is called the graphical solution of a LPP.

(v) Unbounded Solution If the value of the objective function can be increased or decreased
indefinitely, such solutions are called unbounded solutions.

(vi) Fundamental Extreme Point Theorem An optimum solution of a LPP, if it exists, occurs at one of the extreme points (i.e., corner points) of the convex
Polygon of the set of all feasible solutions.

The graph or the solution set of a system of simultaneous linear inequations is the region containing the points (x, y) which satisfy all the inequations of the given system
simultaneously.

To draw the graph of the simultaneous linear inequations, we find the region of the xy-plane, common to all the portions comprWng the solution sets of the given inequations. If there is no region common to all the solutions of the given inequations, we say that the solution set of the system of inequations is empty.

Note The solution set of simultaneous linear inequations may be an empty set or it may be the region bounded by the straight lines corresponding to given linear inequations or it may be an unbounded region with straight line boundaries.

There are two techniques of solving a LPP by graphical method

1. Corner point method and

2. Iso-profit or Iso-cost method

1. Corner Point Method

This method of solving a LPP graphically is based on the principle of extreme point theorem.

(i) Consider each constraint as an equation.

(ii) Plot each equation on graph, as each one will geometrically represent a straight line.

(iii) The common region, thus obtained satisfying all the constraints and the non-negative restrictions is called the feasible region. It is a convex polygon.

(iv) Determine the vertices (corner points) of the convex polygon. These vertices are known as
the extreme points of corners of the feasible region.

(v) Find the values of the objective function at each of the extreme points. The point at which the value of the objective function is optimum (maximum or minimum) is the optimal solution of the given LPP.

(i) Consider each constraint as an equation.

(ii) Plot each equation on graph as each one will geometrically represent a straight line.

(iii) The polygonal region so obtained, satisfying all the constraints and the non-negative
restrictions is the convex set of all feasible solutions of the given LPP, which is also known as
feasible region.

(iv) Determine the extreme points of the feasible region.

(v) Give some convenient value k to the objective function Z and draw the corresponding
straight line in the xy-plane.

(vi) If the problem is of maximization, then draw lines parallel to the line Z = k and obtain a
line which is farthest from the origin and has atleast one point common to the feasible region.

If the problem is of minimization, then draw lines parallel to the line Z = k and obtain a line,
which is nearest to the origin and has atleast one point common to the feasible region.

(vii) The common point so obtained is the optimal solution of the given LPP.

Consider the constraint ax + by â‰¤ c, where c > 0.

First draw the straight line ax + by = c by joining any two points on it. For this find two convenient points satisfying this equation.This straight line divides the xy-plane in two parts. The inequation ax + by c will represent that part of the xy-plane which lies to that side of the line ax + by = c in which the origin lies.

Again, consider the constraint ax + by â‰¥ c, where c > 0.

Draw the straight line ax + by = c by joining any two points on it.

This straight line divides the xy-plane in two parts. The inequation ax + by â‰¥ c will represent that part of the xy-plane, which lies to that side of the line ax + by = c in which the origin does not lie.

A BFS is a basic solution which also satisfies the non-negativity restrictions.

A BFS is said to be optimum, if it also optimizes (Max or min) the objective function.

**1. Point Sets** Point sets are sets whose elements are points or vectors in E^{n} or R^{n} (ndimensional
euclidean space).

**2. Hypersphere** A hypersphere in En with centre at â€˜aâ€™ and radius âˆˆ > 0 is defined to be the set
of points X = -{x:|x â€” a| = âˆˆ}

**3. An âˆˆ neighbourhood **An & neighbourhood about the point â€˜a is defined as the set of points
lying inside the hypersphere with centre at â€˜aâ€™ and radius âˆˆ > 0.

**4. An Interior Point** A point â€˜aâ€™ is an interior point of the set S, if there exists an
âˆˆ neighbourhood about â€˜aâ€™ which contains only points of the set S.

**5. Boundary Poin**t A point â€˜aâ€™ is a boundary point of the set S if every âˆˆ neighbourhood about
â€˜aâ€™ contains points which are in the set and the points which are not in the set.

**6. An Open. Set** A set S is said to be an open set, if it contain only the interior points.

**7. A Closed Se**t A set S is said to be a closed set, if it contains a its boundary points.

**8. Lines** In E^{n} the line through the two points x_{1} and x_{2}, x_{1} â‰ x_{2} is defined to be the set of points.

X = {x: x = Î» x_{1} + (1 â€” Î») x_{2}, for all real Î»}

**9. Line Segments** In En, the line segment joining two point x_{1} and x_{2} is defined to be the set of
points.

X = {x:x = Î» x_{1} + (1 â€” Î»)x_{2}, 0 â‰¤ Î» â‰¤ 1}

**10. Hyperplane** A hyperplane is defined as the set of points satisfying c_{1}x_{1}+ c_{2}x_{2} + â€¦+ cnxn = z (not all ci = 0) or cx = z for prescribed values of c_{1}, c_{2},â€¦, cn and z.

**11. Open and Closed Half Spaces**

A hyperplane divides the whole space En into three mutually disjoint sets given by

X_{1} = {x : cx >z}

X_{2} = {x : cx = z}

X_{3} = {x : cx < z}

The sets x_{1} and x_{2} are called â€˜open half spacesâ€™. The sets {x : cx â‰¤ z} and { x : cx â‰¥ z} are
called â€˜closed half spacesâ€™.

**12. Parallel Hyperplanes **Two hyperplanes c1x = z1 and c_{2}x = z_{2} are said to be parallel, if they have the same unit normals i.e., if c_{1} = Xc_{2} for Î», Î» being non-zero.

**13. Convex Combination** A convex combination of a finite number of points x_{1}, x_{2},â€¦., xn is defined as a point x = Î»_{1} x_{1} + Î»_{2}x_{2} + â€¦. + Î»nxn, where Î»i is real and â‰¥ 0, âˆ€ and

**14. Convex Set **A set of points is said to be convex, if for any two points in the set, the line segment joining these two points is also in the set.

or A set is convex, if the convex combination of any two points in the set, is also in the set.

**15 Extreme Point of a Convex Set** A point x in a convex set c is called an â€˜extreme pointâ€™, if x
cannot be expressed as a convex combination of any two distinct points x_{1} and x_{2} in c.

**16. Convex Hull** The convex hull c(X) of any given set of points X is the set of all convex combinations of sets of points from X.

**17. Convex Function **A function f(x) is said to be strictly convex at x, if for any two other distinct points x_{1} and x_{2}.

f{ Î»x_{1} + (1 â€” Î»)x_{2}} < Î»f(x_{1}) + (1â€” Î»)f(x_{2}), where 0 < Î» < 1.

And a function f(x) is strictly concave, if â€” f(x) is strictly convex.

**18. Convex Polyhedron** The set of all convex combinations of finite number of points is called
the convex polyhedron generated by these points.

(i) A hyperplane is a convex set.

(ii) The closed half spaces H_{1} = {x : cx â‰¥ z} and H2 = {x : cx â‰¤ z} are convex sets.

(iii) The open half spaces : {x : cx > z} and {x : cx < z} are convex sets.

(iv) Intersection of two convex sets is also a convex sets.

(v) Intersection of any finite number of convex sets is also a convex set.

(vi) Arbitrary intersection of convex sets is also a convex set.

(vii) The set of all convex combinations of a finite number of points X_{1}, X_{2},â€¦., X_{n} is convex
set.

(viii) A set C is convex, if and only if every convex linear combination of points in C, also
belongs to C.

(ix) The set of all feasible solutions (if not empty) of a LPP is a convex set.

(x) Every basic feasible solution of the system Ax = b,x â‰¥ 0 is an extreme point of the convex
set of feasible solutions and conversely.

(xi) If the convex set of the feasible solutions of Ax = b,x â‰¥ 0 is a convex polyhedron, then
atleast one of the extreme points gives an optimal solution.

(xii) If the objective function of a LPP assumes its optimal value at more than one extreme
point, then every convex combination of these extreme points gives the optimal value of the
objective function.

Please send your queries to ncerthelp@gmail.com you can aslo visit our facebook page to get quick help. Link of our facebook page is given in sidebar

- Chapter 5: Continuity and Differentiability
- Chapter 1: Relations and Functions
- Chapter 2: Inverse Trigonometric Functions
- Chapter 3: Matrices
- Chapter 4: Determinants
- Chapter 6: Application of Derivatives
- Chapter 7: Integrals
- Chapter 8: Application of Integrals
- Chapter 9. Differential Equations
- Chapter 10: Vector Algebra
- Chapter 12: Linear Programming
- Chapter 11: Three Dimensional Geometry

- NCERT Solutions for Class 9 Science Maths Hindi English Math
- NCERT Solutions for Class 10 Maths Science English Hindi SST
- Class 11 Maths Ncert Solutions Biology Chemistry English Physics
- Class 12 Maths Ncert Solutions Chemistry Biology Physics pdf

- Class 1 Model Test Papers Download in pdf
- Class 5 Model Test Papers Download in pdf
- Class 6 Model Test Papers Download in pdf
- Class 7 Model Test Papers Download in pdf
- Class 8 Model Test Papers Download in pdf
- Class 9 Model Test Papers Download in pdf
- Class 10 Model Test Papers Download in pdf
- Class 11 Model Test Papers Download in pdf
- Class 12 Model Test Papers Download in pdf

Copyright @ ncerthelp.com A free educational website for CBSE, ICSE and UP board.