Linear Programming Problem
A linear programming problem (LPP) deals 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).
Objective Function
The linear function Z = ax + by,
where a and b are constants, which has to be maximised or minimised
is called the objective function.
Decision Variables
In the objective function, Z = ax
+ by, variables x and y are called decision variables.
Constraints
The linear inequalities or conditions on the
variables of a linear programming problem are called constraints. The
conditions x
are called non-negative constraints.
Feasible and Infeasible Regions
The common region
determined by all the constraints including non-negative constraints x, y
of a linear programming
problem is called the feasible region. The region other than feasible region is
called an infeasible region.
Feasible and Infeasible Solutions
Every point inside the feasible region and on the boundary of the feasible region represents feasible solution to the problem. Any point outside the feasible region is called 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 the optimal solution.
Important Theorems
Theorem 1: 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.
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 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.
Corner Point Method for Solving LPP
This method comprises
of the following steps:
Step 1: Find the feasible region of the
linear programming problem and determine its
corner points
(vertices) either by inspection or by solving the two equations of the lines
intersecting at that point.
Step 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.
Step 3: When the feasible region is bounded, M
and m are the maximum and
minimum values of
Z.
Step 4: When the feasible region is unbounded,
then
(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) 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.