Linear Programming Problem
LINEAR PROGRAMMING PROBLEM
INTRODUCTION:
Linear Programming is a technique for determining an
optimum schedule of interdependent activities in view of the
available resources. Programming is just another word of
“planning” and refers to the process of determining a particular
plan of action from amongst several alternatives. The word linear
stands for indicating that all relationships involved in a particular
problem are linear.
Linear Programming is a special and versatile
technique which can be applied to a variety of
management problems viz. Advertising, Distribution
etc., The linear programming is useful not only in
industry and business but also in non-profit sectors
such as Education, Government, Hospital, and
Libraries.
The objective function and the constraints can be
expressed as linear functions of the decision
variables. An objective function represents some
principal objective criterion or goal that measures the
effectiveness of the system such as maximizing profits
or productivity, or minimizing cost or consumption.
There is always some practical limitation on the
availability of resources viz. man, material, machine,
or time for the system. These constraints are expressed
as linear equations involving the decision variables.
Solving a linear programming problem means
determining actual values of the decision variables that
optimize the objective function subject to the limitation
imposed by the constraints.
For use with a common management problem
the allocation of resources in an optimum manner
Mathematical or graphical technique - used to
determine best use of scarce resources to
accomplish a defined objective
Used when problems have these characteristics:
Mix
Needs an optimum solution
Constraints
Linear relationship
Definition of linear programming Problem
LP is a mathematical technique for choosing
the best alternatives from a set of feasible
alternatives, in situations where the objective
function as well as the restrictions or constraints
can be expressed as a linear mathematical
functions.
Definition of linear programming Problem
Mathematical programming is used to find the
best or optimal solution to a problem that requires a
decision or set of decisions about how best to use a
set of limited resources to achieve a state goal of
objectives.
It is a mathematical model or technique for
efficient and effective utilization of limited
recourses to achieve organizational objectives
(Maximize profits or Minimize cost).
Requirements of LPP
There must be well defined objective function.
There must be a constraint on the amount.
There must be alternative course of action.
The decision variables should be interrelated and
non negative.
The resource must be limited in supply.
Basic Assumptions of LPP
The linear programming problems are formulated on the basis
of the following assumptions.
Proportionality: The contribution of each variable in the
objective function or its usage of the resources is directly
proportional to the value of the variable. i.e., if resource
availability increases by some percentage, then the output shall also
increase by the same percentage.
Additivity: Sum of the resources used by different activities
must be equal to the total quantity of resources used by each
activity for all the resources individually or collectively.
Divisibility: The variables are not restricted to integer value.
Certainty or Deterministic: Co-efficients in the objective
function and constraints are completely known and do not
change during the period under study in all problems considered.
Finiteness: Variables and constraints are finite in number
Optimality: In a linear programming problem we determine the
decision variables so a s to extremise (optimize)the objective
function of the LPP.
The problem involves only one objective namely profit
maximization and cost minimization.
LPP can be divided into two types:
Maximization problem which has the maximize the profit ≤.
Minimization problem which has the minimize the cost ≥
LINEAR – All variables occurring in objective functions.
PROGRAMMING – process of determining particular course
of action.
OBJECTIVE FUNCTION: LPP deals with optimization
(maximization or minimize) of function of decision variables
known as objective function.
Subject to a set of simultaneous linear equation is known as
constraints.
Advantages and Disadvantage of LPP
Advantages of LPP
It helps in attaining optimum use of productive factors.
It improves the quality of the decisions.
It provides better tools for meeting the changing conditions.
It highlights the bottleneck in the production process.
Disadvantage of LPP
For large problems the computational difficulties are
enormous.
It may yield fractional value answers to decision variables.
It is applicable to only static situation.
LPP deals with the problems with single objective.
Important Definitions in LPP
Solution: A set of variables [X1,X2,...,Xn+m] is called a solution
to L.P. Problem if it satisfies its constraints.
Feasible Solution: A set of variables [X1,X2,...,Xn+m] is called a
feasible solution to L.P. Problem if it satisfies its constraints as
well as non-negativity restrictions.
Optimal Feasible Solution: The basic feasible solution that
optimizes the objective function.
Unbounded Solution: If the value of the objective function can
be increased or decreased indefinitely, the solution is called an
unbounded solution.
