LINEAR PROGRAMMINING PROBLEM (LPP)
MN531/1: Practical Optimization Techniques
A mathematical expression in the form
a1x1+ a2x2+ … + anxn is termed as linear.
Where,
a1, a2,…an are constants, and
x1, x2,… xn are variables.
In general form:
Programming refers to the process of determining a particular program or a
plan of action.
Linear Programming Problem (LPP) is the technique for optimizing
(maximizing or minimizing) a linear functions of variables called the
objective function subject to a set of linear equations and/or in-equations
called constraints or restrictions.
MN531/1: Practical Optimization Techniques
LP Model Formulation
Objective Function:
A linear relationship reflecting the objective of an operation. Most frequent
objective is to maximize profit or minimize the expenditure or cost.
Decision variables:
The unknown quantities representing a decision that needs to be made. It
is the quantities that a model needs to determine.
Constraints:
Linear relationships those representing the restrictions on decision
making.
MN531/1: Practical Optimization Techniques
Maximize or minimize (Objective Function)
Z = c1x1+c2x2+…+cnxn
Subject to (Constraints Functions)
a11x1+a12x2+…+a1nxn ≤ = ≥ b1
a21x1+a22x2+…+a2nxn ≤ = ≥ b2
…
am1x1+am2x2+…amnxn ≤ = ≥ bm
x1, x2,…xn ≥ 0
xjj= decision variables
cj = cost coefficients or objective function coefficients
aij = constraint coefficients
bi = constraint levels or requirements.
MN531/1: Practical Optimization Techniques
In matrix format
Maximize or minimize (Objective Function)
Z = cx
Subject to
Ax ≤ = ≥ b
x≥0
c = cost matrix [c1, c2,…cn]
x = decision variables [x1, x2,…xn]
A = coefficient matrix
b = requirement vectors [b1, b2,…bm]
MN531/1: Practical Optimization Techniques
Solution of LPP
1. Graphical method: When the number of decision variables are only two
the graphical method can be applied. There is no restriction variables it can
be more than two.
2. Simplex method: When the number of decision variables are more than
two the simplex method is applied.
1. Graphical solution:
A company is manufacturing two products, doors and windows. The profit
contribution for each door and window are Rs. 1500 and Rs. 1200
respectively. The carpentry and painting requirements for manufacturing of
each door is 15 hours & 3 hours and for each window is 12 hours & 2
hours respectively. The carpentry and the painting hours available are
6000 and 1200 respectively for the year. To maximize profit how much
each product are to be produced by the company for that particular year.
MN531/1: Practical Optimization Techniques
Formulation of Linear Programming:
Let the company is producing x1 numbers of doors and x2 numbers of
windows (x1 and x2 are decision variables)
Objective function:
Maximize Z = 1500 x1 + 1200 x2
Constraint functions:
15 x1 +12 x2 ≤ 6000
3 x1 + 2 x2 ≤ 1200
x1, x2 ≥ 0
It can be solved by graphical method when the number of variables is two
only. When the number of variables are more than two it is to be solved
by simplex method.
MN531/1: Practical Optimization Techniques
Definitions related to simplex method
Slack variables: If constraint equations in the form of
In order to form linear equations from inequalities we have to add
variables to left hand side of the equations these are termed as slack
variables .
Surplus variables: If constraint equations in the form of
In order to form linear equations from inequalities we have to subtract
variables to left hand side of the equations these are termed as surplus
variables .
MN531/1: Practical Optimization Techniques
Two particular type of LPP
Canonical form: Maximizing problem with constraint functions
Standard for: Maximize or minimize problem with constraints functions
Unknown variables = n and number of equations = m
Whenever we are adding slack variables or subtracting surplus variables
they should be included in the objective function. The cost coefficient of
these variables are always zero.
By introducing slack variables we are generating unit matrix (identity
matrix), we can be considered as basis solution.
MN531/1: Practical Optimization Techniques
The surplus variables do not generate unit matrix, since its coefficients are
negatives. Hence, we have to introduce another variables called artificial
variables for generation of unit matrix, so that we can consider these for
basis solution.
The cost coefficients of artificial variables are take as –M for maximizing
problem and +M for minimizing problem. Where M values are very large
(this is also known as Charnes M–method or Big–M method.
If all the basic variables are greater than zero, the solution is called non-
degenerate, if some of them are zero, the solution is called degenerate.
MN531/1: Practical Optimization Techniques
Simplex Table:
After reducing the linear programming problem into it standard form all the
information regarding the problem can be put into a tabular form. This
table is called simplex table.
Cj C1 C2 … Cj … Cn
CB B XB b a1 a2 … aj … an
CB1 β1 XB1 b1 y11 y12 … y1j … y1n
CB2 β2 XB2 b2 y21 y22 … y2j … y2n
… … … … … … … … … …
CBm βm XBm bm ym1 ym2 … ymj … ymn
Zj-Cj Z1-C1 Z2-C2 … Zj-Cj … Zn-Cn
MN531/1: Practical Optimization Techniques
Cj = Objective row
Zj-Cj = Each element is known as index number or net evaluation
B = the initial basis which is composed of the m-columns of A (β1, β2,
…βr,…,βm)
XB = Initial basic feasible solution
CB = Prices of the initial basic feasible solution of the objective function
b = Requirement vectors
m = is linearly independent column to form basis vector
Index row = Zj-Cj =
MN531/1: Practical Optimization Techniques
Simplex Algorithm
Definition: Simplex algorithm is an iterative procedure for solving n-
dimensional LPP in a finite number of steps for solution of the same. We
need certain steps to get the optimal solution which are as follows:
Step-1: Check whether the objective function of the given LPP is to be
maximized or minimized. If it is to be minimized then we convert it into a
maximization problem by using the result.
Minimize Z = Maximize (-Z)
Step-2: Check whether all bi’s (I = 1, 2, …,n) are non-negative. If any bi is
negative then multiply the corresponding equation of the constraint
function by (-1) so as to get all bi non-negative.
For example: a11x1+a12x2+…+a1nxn ≥ - b1
-a11x1-a12x2-…-a1nxn ≤ b1
MN531/1: Practical Optimization Techniques
Step-3: Convert all the inequalities of the constraints into equations by
introducing slack and/or surplus variables and also artificial variables if
necessary. Put the cost of the slack and surplus variables equal to zero and
that of artificial variables equal to –M for maximizing problem and +M for
minimizing problem. Where M is very large.
Step-4: Obtain an initial basic feasible solution to the problem in the form of
XB = B-1b
Step-5: Compute the index numbers. Zj-Cj (j = 1,2 …,n) by using the
relation
then examine the sign of Zj-Cj
i) If all Zj-Cj ≥0 then the initial basic feasible solution XB will be the optimal
basic feasible solution.
ii) If a tleast one Zj-Cj ≤0 then proceed to the next steps
MN531/1: Practical Optimization Techniques
Step-6: If there are more than one negative Zj-Cj then choose the most
negative of them, let it be Zk-Ck for j=k
i) If all yik≤0 then there is an unbounded solution of the LPP (I = 1,2,…,n)
ii) If at least one or more is yik≥0 then the corresponding vector (yk= Ck)
enters the basis. This kth column is known as key column
Step-7: Compute the ratio
and choose the minimum of them. Let the minimum of this ratio’s be
Then the vector βr will have leave the basis and this rth row will be called
the key row. Intersection of key row and key column will give the key
element yrk≤0 which is called the leading element or pivotal element. If this
minimum
occurs for more than one value of I then more than one
variable will vanish in the next solution generating degeneracy of the …
MN531/1: Practical Optimization Techniques
… basic feasible solution.
Step-8: Convert the leading diagonal element to unity by dividing its row by
the leading elements itself and all other elements in its column to zero’s by
making use of the following relations:
y´ij = yij - i=1, 2,…,m (i≠r)
y´rj = , j=1, 2, …n
Step-9: Go to Step-5 and repeat the computational procedure until either an
optimum solution is obtained or there is an indication of an unbound
solution.
MN531/1: Practical Optimization Techniques
Solve the following LPP by simplex method
Maximize Z = 60 x1 +50 x2
Subject to x1 +2 x2 ≤ 40
3 x1 +2 x2 ≤ 60
x1, x2 ≥ 0
Step-1: Z = 60 x1 +50 x2 +0. x3 +0. x4
x1 + 2 x2 + x3 + 0. x4 = 40
3 x1 + 2 x2 + 0. x3 +1. x4 = 60
x1, x2 , x3, x4 ≥ 0
MN531/1: Practical Optimization Techniques
Cj 60 50 0 0
CB B XB b a1 a2 a3 a4
0 a3 x3 40 1 2 1 0
0 a4 x4 60 3 2 0 1 Key row
Zj-Cj -60 -50 0 0
column
Key
It is available from 2nd row, it is called the key row. This implies that a4
will leave the basis and a1 is the entering vector. The pivotal element or
leading element = 3.
MN531/1: Practical Optimization Techniques
Cj 60 50 0 0
CB B XB b a1 a2 a3 a4
0 a3 x3 20 0 4/3 1 -1/3 Key row
60 a1 x1 20 1 2/3 0 1/3
Zj-Cj 0 -10 0 20
column
Key
It is available from 1st row, it is called the key row. This implies that a3
will leave the basis and a2 is the entering vector. The pivotal element or
leading element = 4/3.
MN531/1: Practical Optimization Techniques
Cj 60 50 0 0
CB B XB b a1 a2 a3 a4
50 a2 x2 15 0 1 3/4 -1/4
60 a1 x1 10 1 0 -1/2 1/2
Zj-Cj 0 0 15/2 35/2
Here all Zj-Cj are positive so optimal solution arrived.
x1 = 10 and x2 = 15
Zmax = 60×10+50×15=1350.
MN531/1: Practical Optimization Techniques
