Linear Programming
This chapter is a continuation of the concepts of linear inequalities and the system of linear equations in two variables studied in the previous class. This chapter helps to learn how these concepts can be applied to solve real-world problems and how to optimize the problems of linear programming so that one can maximize resource utilization, minimize profits, etc.
Linear Programming Problem: A linear programming problem is one that is concerned with finding the optimal value (maximum or minimum) of a linear function of several variables (called objective function) subject to the conditions that the variables are non-negative and satisfy a set of linear inequalities (called linear constraints). Variables are sometimes called decision variables and are non-negative.
Feasible Region: The common region determined by all the constraints including the non-negative constraints, x ≥ 0, y ≥ 0 of a linear programming problem is called the feasible region (or solution region) for the problem.
Infeasible Solution: Points within and on the boundary of the feasible region represent feasible solutions to the constraints. Any point outside the feasible region is an infeasible solution.
Optimal Solution: Any point in the feasible region that gives the optimal value (maximum or minimum) of the objective function is called an optimal solution.
The following Theorems are fundamental in solving linear programming problems:
- Let R be the feasible region (convex polygon) for a linear programming problem and let Z = ax + by, be the objective function. When Z has an optimal value (maximum or minimum), where the variables x and y are subject to constraints described by linear inequalities, this optimal value must occur at a corner point (vertex) of the feasible region.
- Let R be the feasible region for a linear programming problem, and let 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 the feasible region is unbounded. A maximum or a minimum may not exist. However, if it exists, it must occur at a corner point of R.
- Corner point method: For solving a linear programming problem. The method comprises the following steps:
- Find the feasible region of the linear programming problem and determine its corner points (vertices).
- Evaluate the objective function: Z = ax + by, at each corner point. Let M and m respectively be the largest and smallest values at these points.
- If the feasible region is bounded, M and m respectively are the maximum and minimum values of the objective function.
If the feasible region is unbounded, then,
- M is the maximum value of the objective function, if the open half-plane determined by ax + by > M, has no point in common with the feasible region. Otherwise, the objective function has no maximum value.
- m is the minimum value of the objective function if the open half-plane determined by ax + by < M, has no point in common with the feasible region. Otherwise, the objective function has no minimum value.
If two corner points of the feasible region are both optimal solutions of the same type, i.e., both produce the same maximum or minimum, then any point on the line segment joining these two points is also an optimal solution of the same type.
Learn more about, Graphical Solutions to Linear Programming Problems
Class 12 Maths Formulas
Class 12 maths formulas page is designed for the convenience of the learners so that one can understand all the important concepts of Class 12 Mathematics directly and easily. Math formulae for Class 12 are for the students who find mathematics to be a nightmare and difficult to grasp. They may become hesitant and lose interest in studies as a result of this. We have included all of the key formulae for the 12th standard Maths topic, which students may simply recall, to assist them in understanding Maths in a straightforward manner. For all courses such as Integration, Differentiation, Trignometry, Relation and Functions, and so on, the formulae are provided here according to the NCERT curriculum.
Table of Content
- Chapter 1: Relations and Functions
- Chapter 2: Inverse Trigonometric Functions
- Chapter 3: Matrices
- Chapter 4: Determinants
- Chapter 5: Continuity and Differentiability
- Chapter 6: Applications of Derivatives
- Chapter 7: Integrals
- Chapter 8: Applications of Integrals
- Chapter 9: Differential Equations
- Chapter 10: Vector Algebra
- Chapter 11: Three-Dimensional Geometry
- Chapter 12: Linear Programming
- Chapter 13: Probability
Contact Us