Linear Programming Problem (LPP)
The linear programming problem in general calls for optimizing a linear function of variables called
the objective function subject to a set of linear equations and/or linear inequations called the
constraints or restrictions.
Mathematical Description of a General Linear Programming Problem
• A general LPP can be stated as (Max/Min) 𝑧 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 (Objective function)
subject to constraints
and the non-negative restrictions 𝑥1 , 𝑥2 , … , 𝑥𝑛 ≥ 0.
where all 𝑎11 , 𝑎12 , … , 𝑎𝑚𝑛 ; 𝑏1 , 𝑏2 , … , 𝑏𝑚 are constants; 𝑐1 , 𝑐2 , . . , 𝑐𝑛 n are constants known as cost
coefficients and 𝑥1 , 𝑥2 , … , 𝑥𝑛 are known as decision variables.
Objective Function
The function which is to be optimized (maximized/minimized) is called an objective function.
𝑒. 𝑔. Maximum 𝑍 = 250 𝑥 + 120 𝑦
Constraints
The system of linear inequations (or equations) under which the objective function is to be
optimized is called constraints.
𝑒. 𝑔. −2𝑥 + 5𝑦 ≥ 10, 5𝑥 − 𝑦 ≥ 0
Non-negative Restrictions
All the variables considered for making decisions assume non-negative values.
Different Type of Linear Programming Problems
The various types of problems in linear programming problems are included.
They are
➢ Manufacturing problem- Here we maximize the profit with the help of minimum utilization of
the resource.
➢ Diet Problem- We determine the number of different nutrients in a diet to minimize the cost
of manufacture resource.
DR. SOURAV DEBASIS 1
➢ Transportation problem- Here we determine the schedule to find the cheapest way of
transporting a product at minimum time.
➢ Assignment Problem –It deals with the allocation of the various resources to the various
activities on one-to-one basis.
Important Definitions and Results
➢ The solution of an LPP: A set of values of the variables xl, x2,….,xn satisfying the constraints
of an LPP is called a solution of the LPP.
➢ Feasible Solution of an LPP: A set of values of the variables xl, x2,….,xn satisfying the
constraints and non-negative restrictions of an LPP is called a feasible solution of the LPP.
➢ Feasible Region: The common region determined by all the constraints of an LPP is called
the feasible region and every point in this region is a feasible solution of the given LPP.
➢ Infeasible Solution: A solution of an LPP is an infeasible solution if it does not satisfy the non-
negativity restrictions.
➢ Infeasible Region: The region other than the feasible region is called the infeasible region.
➢ Optimal Solution of an LPP: A feasible solution of an LPP is said to, be optimal (or
optimum) if it also optimizes the objective function of the problem.
➢ Convex set
A set S is convex if any point on the line segment connecting any two points in the set is also
in S.
DR. SOURAV DEBASIS 2
Remember:
The set of all feasible solutions of an LPP is a convex set.
➢ Bounded Feasible Region: A feasible region is said to be bounded if it can be enclosed within a
circle.
➢ Unbounded Feasible Region: A feasible region is said to be unbounded if it cannot be enclosed
within any circle 𝑖. 𝑒., if it extends indefinitely in any direction.
➢ Fundamental Extreme Point Theorem: An optimal solution of an LPP, if it exists, occurs at one of
the extreme (corner) points of the convex polygon of the set of all feasible solutions.
Graphical Method of solution for problems in two variables.
There are two techniques of solving an LPP by graphical method
1. Corner point method and
2. Iso-profit or Iso-cost method
CORNER - POINT METHOD
This method of solving an LPP graphically is based on the principle of extreme point theorem.
The following algorithm can be used to solve an LPP in two variables graphically by using the corner
– point method.
ALGORITHM
STEP I Formulate the given LPP in the mathematical form if it is not so.
STEP-II Convert all inequations into equations and draw their graphs. To draw
the graph of a linear equation, put 𝑦 = 0 in it and obtain a point on
𝑥 − 𝑎𝑥𝑖𝑠. Similarly, by putting 𝑥 = 0 obtain a point on 𝑦 − 𝑎𝑥𝑖𝑠. Join
these two points to obtain the graph representing the equation.
STEP III Determine the region represented by each inequation. To determine
the region represented by an inequation replace 𝑥 and 𝑦 both by zero,
if the inequation reduces to a valid statement, then the region
containing the origin is the region represented by the given
inequation.
STEP IV Obtain the region in 𝑥𝑦 − plane containing all points that
simultaneously satisfy all constraints including non-negativity
restrictions. The polygonal region so obtained is the feasible region
DR. SOURAV DEBASIS 3
and is known as the convex polygon of the set of all feasible solutions
of the LPP.
STEP V Determine the coordinates of the vertices (corner points) of the
convex polygon obtained in Step II. These vertices are known as the
extreme points of the set of all feasible solutions of the LPP.
STEP VI Obtain the values of the objective function at each of the vertices of
the convex polygon. The point where the objective function attains its
optimum (maximum or minimum) value is the optimal solution of the
given LPP.
REMARK: If the feasible region of an LPP is bounded 𝑖. 𝑒., it is a convex polygon. Then, the objective
function 𝑍 = 𝑎𝑥 + 𝑏𝑦 has both a maximum value 𝑀 and a minimum value 𝑚 and each of these
values occurs at a corner point of the convex polygon.
DR. SOURAV DEBASIS 4
