Linear Programming
Problems (LPP)
Introduction
Linear Programming (LP) is a widely used mathematical
modeling technique to determine the optimum allocation of
limited resources.
As its name implies, the linear programming model consists of
linear objective and linear constraints.
LP is a method to achieve the best outcome such as maximum
profit or lowest cost.
Components of LP Model
An LP model consists of following basic components:
1. Decision Variables: Variables over which the decision maker has control; also known as a
controllable input variables. Usually designated by X1, X2, X3…
2. The objective function: A linear mathematical relationship describing the objective and
expressed in terms of decision variables to optimize(Maximize or Minimize) the criteria of
optimality, such as profit, cost, revenue etc.
3. The constraints: There are always certain limitations on the use of resources, such as labour,
machine, raw material, money that limit the degree to which objective can be achieved.
Constrains are expressed as linear inequalities or equalities in terms of decision variables.
4. Non-negativity restrictions: Each and every decision variable in LP model of a real life
problem is a non-negative variable, represented as X1, X2, X3…Xn ≥ 0.
Assumptions of an LP Model
Following are the assumptions of LP Model:
❖ Certainty: In LP models, it is assumed that the value of all the parameters are known with
certainty.
❖ Additivity: The value of the objective function and total amount of each resource used must be
equal to the sum of the respective individual contribution of the decision variables. For example,
total profit earned by selling two products A and B must be equal to the sum of profits earned
by selling products A and B separately.
❖ Linearity(or proportionality): The amount of resource required for any activity is directly
proportional to the level of the activity. For example, if one unit of product requires 2 hours
processing on a machine, the 5 units requires 2*5 = 10 hours of processing on that machine.
❖ Divisibility(or continuity): This means that the fractional values of the decision variables are
permitted.
Advantages of LPP
❑ LPP helps decision makers to use their resources effectively.
❑ It improves the quality of decisions.
❑ It takes into consideration all the limitations and helps to arrive at
optimal solution.
❑ LPP can be used to solve complex problems.
Limitations of LPP
o In real life situations, several problems are nonlinear in nature on which LPP can not be applied.
o Multi-objective problems can not be solved by using LPP.
o All parameters in any organization can not be known with certainty and many times values of
the coefficients are probabilistic and such problems cannot be solved using LPP.
o In LPP decision variables can take fractional values, whereas many real life problems should
have only integer valued solution, so in such cases LPP techniques cannot be used.
Development of LP Models
Problem formulation or modeling is the process of translating a verbal statement of a problem
into a mathematical statement. Following are the guidelines for model formulation:
✔ Understand the problem thoroughly.
✔ Describe the objective.
✔ Describe each constraint.
✔ Define the decision variables.
✔ Write the objective in terms of the decision variables.
✔ Write the constraints in terms of the decision variables.
General Format of an LP Model
Optimize(Maximize/Minimize) Objective Function
Subject to
Constraints
Non-negativity restriction on decision variables
General LP Model
Optimize(Maximize/Minimize) C1 X 1 + C 2 X 2 + … + CnX n
Subject to A 1,1X 1 + … + A 1,nX n (≤, =, ≥) b 1
A 2,1X 1 + … + A 2,nX n (≤, =, ≥) b 2
…
A m,1X 1 + … + A m,n X n (≤, =, ≥) b m
X 1, X 2, … X n ≥ 0
Where, Xj’s are decision variables, Cj’s are coefficients of per unit profit or cost of X j to objective
function.
Ai,j are technological coefficients, representing amount of resource i required for the activity j
and bi represents the total availability of the resource i.
LP Model formulation – An example
Production process of a furniture manufacturing plant manufacturing two products, tables and
chairs, which needs to be processed on three machines, A, B and C. Machine A cuts the wood in
required shapes, machine B join the pieces of wood to give furniture the desirable shape and
machine C finally polishes the product and yields finished product. Formulate the LPP.
Following table provides the information on structure of the production plant:
Machines
Product A (per unit B (per unit C (per unit Profit per unit
processing time in processing time in processing time in
hrs) hrs) hrs)
Chair 1 2 1 ₹ 50
Table 2 3 1 ₹ 100
Max available 50 72 30
weekly time in hrs
LPP Model Formulation Question - 1
LPP Model Formulation Question - 2
LPP Model Formulation Question - 3
LPP Model Formulation Question - 4
Solutions of LPP
Solution of an LPP: Set of values of decision variables which satisfies the
constraints of LPP is called solution of an LPP.
Feasible solution of an LPP: A solution of an LPP which also satisfies non-
negativity restrictions is called feasible solution of an LPP.
Optimal solution of an LPP: A feasible solution of an LPP which also
optimizes objective function is called optimal solution of an LPP.
Some Definitions
1. Feasible Region of an LPP: It refers to the area containing all possible feasible
solutions to the general LPP.
2. Convex Set: Convex set is a set of points such that if any two points are
selected from the set and joined by straight line segment, then that line
segment completely lies within the set.
3. Corner point: A corner point or extreme point in a convex set is any point in
the set that is the intersection of two boundary lines.
LPP solution techniques
1. Graphical Method: An LPP can be solved graphically, if it consists
only two decision variables.
2. Simplex Method: It is a general algebraic method to solve an LPP
having any number of decision variables.
Extreme Point Theorem for solution of
an LPP by Graphical Method
Optimal Solution of an LPP, if it exists, occurs at one of the
corner (extreme) points of the feasible region of an LPP.
Thank You