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.
Graphical method of solving Linear Programming Problems or
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.
Comments
Post a Comment