Linear
Programming Problem:
A linear programming problem is one in which we have to find
optimal value (maximum or minimum) of a linear function of several variables
(called objective function) subject to certain conditions that the variables
are non-negative and satisfying by a set of linear inequalities with variables,
are sometimes called division variables.
Terms
related to Linear Programming
Objective Function:
A linear function z = px
+ qy (p and q are constants) which has to be
maximised or minimised, is called an objective function.
Constraints:
The linear inequalities or equations or restrictions on the
variables of the linear programming problem are called constraints. The
conditions x ≥ 0, y ≥ 0 are called non-negative restrictions.
Optimal
Value:
The maximum or minimum value of an objective function is known
as its optimal value.
Optimisation
Problem:
A problem, which seeks to maximise or minimise a linear function
subject to certain constraints as determined by a set of linear inequalities, is
called an optimisation problem.
Feasible
Region:
The common region determined by all the constraints including
non-negative constraints x,y>0
of a linear programming problem is called the feasible region for the problem.
The region other than the feasible region is called an infeasible region. The
feasible region is always a convex polygon.
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 of
the objective function is called the optimal feasible solution.
Bounded
and Unbounded Region:
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.
Fundamental
Theorems for Solving Linear Programming
Theorem 1: Let R be
the feasible region 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.
Note: A corner point of a feasible region is a point in the region which is the
intersection of two boundary lines.
Theorem 2: 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 z has both a maximum and a minimum
value on R and each of these recurs at a corner point of JR.
Note: Maximum or a minimum may not exist,- if the feasible region is unbounded.
Corner
Point Method:
The corner point method says that, if a maximum or minimum value
exists, then it will occur at a corner point of the feasible region.
Steps
for Applying Corner Point Method
Find the feasible region of the linear programming problem and
determine its corner points either by inspection or by solving the two
equations of the lines intersecting at that point.
Evaluate the objective function z = ax
+ by at each corner point. Let M and m be, respectively denote the largest and
the smallest values of these points.
If the feasible region is bounded, then M and m respectively are
the maximum and minimum values of the objective function at corner points.
If the feasible region is unbounded, then
(a) M is the maximum value of objective function 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) 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.
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.