Linear Programming Problem
Formulation and Solution by Graphical and Simplex Method
Case Studies –
1. [CS 1] Mr. Robert, owner of a small machine shop has some special purpose CNC machines. He received an
order to supply large number of units of two components A and B. Component A is made up of alloy steel of
grade I and component B is made up of alloy steel of grade II. Availability of alloy steel of grade I is 1500 kg
and that of grade II is 600 kg respectively per shift. One batch of component A needs 50 kg of alloy steel of
grade I and one batch of component B needs 24 kg of alloy steel of grade II. Availability of set of CNC machines
needed is for 1200 minutes per shift. One batch of component A takes 24 minutes for machining and that of
component B needs 30 minutes of machining. Profit earned by selling one batch of component A is six thousand
rupees and that for component B is seven thousand rupees. How many batches of components A and B should
Mr. Robert make so as to maximize the profit for the shift?
Answer: Zmax = 292, x = 30, y = 16
2. [CS 2] Manager of a company making health products wants to make certain energy drink containing
Vitamins A & B by adding ingredients X & Y to the processed milk. Each unit of ingredient X and ingredient
Y cost Rs.4 and Rs.6 respectively. Each unit of ingredient X provides one unit of vitamin A and one unit of
vitamin B. Each unit of ingredient Y provides one unit of vitamin A and two units of vitamin B. It is
recommended that each pack of energy drink must contain at least 8 units of vitamin A and at least 12 units of
vitamin B. How much of each ingredient should be used if company wants to minimize the cost?
Answer: Zmin = 40, x = 4, y = 4
3. A company wants to produce three products A, B and C. The profits obtained by selling these products
are Rs.30, Rs.40 and Rs.35 respectively. Three machines are needed to make these products. Each unit of
product A needs 3 hours on machine I, 2 hours on machine II and 1 hour on machine III. Each unit of
product B requires 4 hours on machine I, 1 hour on machine II and 3 hours on machine III. Each unit of
product C takes 2 hours on each of the three machines. Machining time available on machine I, machine
II, and machine III are 90, 54, and 93 hours respectively.
Formulate the L.P. model and determine the optimal product mix.
Theory –
Generalized LPP with n decision variables (j) and m constraints (i)
Optimize (Maximize or minimize)
Z = c1x1 + c2x2 +……. + cn xn
Subject to
a 11 x 1 + a 12 x 2 + …..…+ a1nxn (≤, =, ≥) b 1
a 21 x 1 + a 22 x 2 + ……..+ a 2nxn (≤, =, ≥) b 2 : :
:
: : :
am1 x 1 + a m2 x 2 + ….. + amn xn (≤, =, ≥) bm
x 1, x 2, …..…, xn ≥ 0
n – number of decision variables
m - number of constraints
xj - jth decision variable
cj - Cost/profits contribution per unit of decision variables
a ij - Consumption of resources per unit of decision variables
bi - Availability of resources
xj ≥ 0 is called as non-negativity constraint.
Feasible solution: Any set of values of decision variables that satisfy all the constraints including
non-negativity constraint.
Optimal Solution: Feasible solution for which value of objective function is optimal (maximum or
minimum).
Methods for finding Optimal solution
Given LPP may have infinite feasible solutions.
Methods suggested for finding optimal solution –
1. Graphical Method
2. Simplex Method
Graphical Method can be used when only two decision variables are involved.
Graphical Method
Graphical method solves LPP by plotting various constraints on a graph and then identifying the area
of feasible solution – set of all points that satisfy all the constraints including non-negativity
constraint.
Optimal solution exists if the area of feasible solution is convex. Area or region is called as convex if
line segment joining any two points in the area lines within that area. Optimal solution lies at the
vertex of convex AFS.
i. Plot a graph in which x and y axes represent the two-decision variable.
ii. Non-negativity constraints restrict solution area of feasible solution to first quadrant.
iii. Equality constraints are represented by straight lines while In-equality constraints are
represented by regions.
iv. To represent in-equality constraints on graph – Replace inequality with an equation and plot
straight line on the graph. It divides plane into two parts. One of these two is the region
containing all points that satisfy the inequality.
v. To choose the right half to mark as solution space – check whether origin (0,0) satisfies the
constraint. If it satisfies the in-equality, then the side in which it lies is the feasible solution
space otherwise the other side.
vi. Area of feasible solution AFS to given LPP is common feasible solution space for all
constraints.
vii. Optimal solution lies at the vertex of AFS.
viii. Obtain the co-ordinates of all the vertices of AFS and find value of Z for each vertex.
ix. Vertex with highest Z value is optimal solution for maximization problem and with least Z
value is for minimization problem.
Simplex Method
Example of LPP in Canonical form (3 variables and 3 constraints)
Maximize
Z = c1x1 + c2x2 + c3 x3
Subject to
a 11 x 1 + a 12 x 2 + a13x3 ≤ b 1
a 21 x 1 + a 22 x 2 + a 23x3 ≤ b 2
a31 x 1 + a 32 x 2 + a33x3 ≤ b3
x 1, x 2, x3 ≥ 0
LPP in Canonical form is converted into Standard form for solving it by Simplex Method
Expressing LPP in Standard form:
All the constraints are expressed as equations by adding slack variables. Slack variables represent un-
utilized resources.
Maximize
Z = c1x1 + c2x2 + c3 x3 + 0s1 + 0s2 + 0s3
Subject to
a 11 x 1 + a 12 x 2 + a13x3 + s1 = b 1
a 21 x 1 + a 22 x 2 + a 23x3 + s2 = b 2
a31 x 1 + a 32 x 2 + a33x3 + s3 = b3
x 1, x 2, x3, s1, s2, s3 ≥ 0
Basic solution: If n is no. of variables, m is no. of equations and n > m, then a solution to m equations
obtained by equating (n - m) variables to zero, is called as Basic solution. The m non-zero variables
in the solution are called as basic variables and variables equated to zero are non-basic variables.
Algorithm:
Various parameters of LPP are expressed in the form of a simplex tableau.
cj c1 c2 c3 0 0 0
ci Basis bi x1 x2 x3 s1 s2 s3
0 s1 b1 a 11 a 12 a13 1 0 0
0 s2 b2 a 21 a 22 a 23 0 1 0
0 s3 b3 a31 a 32 a33 0 0 1
zj
cj - zj
i) The iterative process begins with initial basic feasible solution obtained by equating all
decision variables to zero and slack variables taking respective bi values. It is usually
the worst solution. Basic variables are collectively called as Basis.
ii) The algorithm checks the optimality of current basic feasible solution.
iii) To check the optimality of current solution, first zj = ∑ ci x aij values and then Cj - Zj
values for all j are obtained. If all Cj - Zj values are zero or negative, current solution is
optimal.
iv) If it is not optimal, the solution is improved in next iteration.
v) Variable with highest positive (cj – zj) value is incoming variable.
vi) Corresponding column is called key column (k).
vii) To find outgoing variable, calculate θi = bi/aik
viii) Variable with least non-negative θi value is outgoing variable.
ix) Corresponding row is called key row (r).
x) New solution matrix is obtained using following steps -
xi) Elements of successive matrix corresponding to key row
arj* = arj/ark
xii) Elements of successive matrix corresponding to other rows other than key row
aij* (i≠r) = aij – aik x arj*
* represents element in new matrix
xiii) New solution which again is basic feasible is checked for optimality.
xiv) Iterations continue till optimal solution is reached.
