Module3 1

Topic1:

LPP in canonical form to get the initial BFS and method of improving current BFS:
Our next step is to learn and understand the algorithm called the Simplex Algorithm. The
algorithm is an iterative scheme and can be easily implemented on any LPP involving any type
of linear constraints. We shall learn how the algorithm works, its implementation success, and
of course the geometry behind it.

Recollect the knowledge from past few lecture. What we have learned is that if an LPP has an
optimal solution, then at least one extreme point of the convex polyhedron feasible set must
be optimal; the extreme point of the feasible set of a LPP involving equality constraint along
with non-negativity restriction corresponds to the BFS and conversely. This indicates that if
the constraints of the given LPP can be appropriately transformed to the equation them finding
out optimal solution (if exist) is equivalent to finding the BFS which yield the optimal value of
the objective function. We must appreciate that extreme point is a geometrical concept easy to
visualize but difficult to workout, on the other hand BFS is an algebraic notion mathematically
simple to workout. So our first task is to convert all inequalities unconstraint to equations.
Constraints of the type given by:
n
X
aij xj ≥ bi
j=1

are equivalent to
n
X
aij xj − xn+i = bi
j=1

The non-negative variable xn+i used to convert an inequality constraint involving ≥ to an

equality constraint is called the surplus variable.
Similarly the constraints of the type
n
X
arj xj ≤ br
j=1

are equivalent to
n
X
arj xj + xn+r = br , xn+r ≥ 0
j=1

The non-negativity variable xn+r used to convert an inequality constraint of type ≤ to an

equality constraint is called the slack variable.

c Copyright Reserved IIT Delhi

 2

In view of above discussion, the given LPP can equivalently be recasted as the following LPP:
n+q
X
max z = ct x = cj xj
j=1
n
X
subject to aij xj − xn+i = bi , i = 1, . . . , p
j=1
Xn
aij xj + xr+i = bi , i = p + 1, . . . , q
j=1
Xn
aij xj = bi , i = q + 1, . . . , m
j=1
xj ≥ 0 , j = 1, 2, . . . , n + q

where cj = 0 , j = n + 1, . . . , n + q, that is, the cost coefficient with the slack and the surplus
variables are taken to be [Link] format of LPP is called the Standard Format of LPP. In
the Standard Format all constraints are written as equality constraint with help of slack and
surplus variable and all variables are required to be non-negativity. Every LPP can be written
in the equivalent standard format.
Consider the following LPP

max 3x1 + 2x2 + x3

subject to 3x1 − x2 + 7x3 ≤ 0
5x1 + 2x2 − x3 = 0
2x1 + 4x2 + 5x3 ≥ 0
x1 , x2 , x3 ≥ 0

The equivalent standard form is:

max 3x1 + 2x2 + x3 + 0.x4 + 0.x5

subject to 3x1 − x2 + 7x3 + x4 = 2
5x1 + 2x2 − x3 = 15
2x1 + 4x2 + 5x3 − x5 = 10
x1 , x2 , x3 , x4 , x5 ≥ 0

x4 is a slack variable x5 is the surplus variable.

Besides converting inequalities into equation, observe that all the variable have to be non-
negative variable in the standard format. For instance consider the LPP:

min x1 − x2
subject to x1 + x2 ≤ 2
−x1 + x2 ≥ 1
x2 ≥ 0

c Copyright Reserved IIT Delhi

 3

Express x1 = x1 0 − x1 00 and use a slack variable x3 surplus variable x4 , we can write its standard
format as follow:
min x1 0 − x1 00 − x2 + 0.x3 + 0.x4
subject to x1 0 − x1 00 + x2 + x3 = 2
x1 0 − x1 00 + x2 − x4 = 1
x1 0 , x1 00 , x2 , x3 , x4 ≥ 0
Observe that the objective function can be recasted as

− max − x1 0 + x1 00 + x2 + 0.x3 + 0.x4

It is essential to convert all inequalities into equations, since the concept of basic feasible solution
(BFS) is defined for system of linear equation and secondly we shall see later that while moving
from one iteration of the simplex algorithm to the other iteration one need to apply row pivoting
and this can simply be not done with inequalities.
Though we shall be formally describing the steps of the simplex algorithmic in a later lecture but
here we briefly build its background. The simplex algorithm is basically an iterative algorithm
in which we start with an initial basic feasible solution of the LPP and moves from one iteration
to another by finding the BFS which improves the value of the objective function of the LPP till
we either reach the optimal solution of the LPP or we can conclude concretely about the nature
of LPP. By latter we mean that either the LPP is infeasible or unbounded. Fortunately in all
circumstances the simplex method applied on LPP will terminate in yielding the precise nature
(solution if exist) of the LPP. Thereby making the simplex algorithm (with some variation) a
powerful technique to solve all LPP’s.
The forgoing discussion clearly indicate to discuss the following:-

• How to find the initial BFS of LPP?

• How to decided when to stop the algorithm or move to the next iteration?

• How to get a new BFS from the current one so that if decided to more with iterations
then the objective function value improves?

We now concentrate to answer some of these issues. First note that at every iteration of the
simplex procedure a BFS of LPP is known. Since BFS ic characterized by the basic matrix
associated to it, a new BFS can be found by changing the basic matrix.

c Copyright Reserved IIT Delhi

 4

Suppose (xB , 0) is a BFS of LPP.

max z = ct x
subject to Ax = b
x≥0
where A is m × n matrix with rank m, b is m × 1 and c is n × 1 vector. Let B = [b1 , b2 , . . . , bm ]
be a basis matrix associated with (xB , 0).
Now suppose there exists a column aj in A which is not in B. Then there exist scalars
yij i = 1, . . . , m such that
m
X
aj = yij bi .
i=1

For a moment assume that there is some scalar yrj > 0. Then
m
X −yij 1
br = bi + aj .
yrj yrj
i=1,i6=r

m
X
Since (xB , 0) is a BFS. So, BxB = b or xBi bi = b implying
i=1
m m
X X −yij 1
xBi bi + xBr ( − bi + aj ) = b.
yrj yrj
i=1,i6=r i=1,i6=r

Simplifying the above , we obtain,

Xm
x̂Bi bi + x̂Br aj = b
i=1,i6=r
xBr yij
where x̂Br = yrj and x̂Bi = xBi − yrj xBr , i 6= r.

Writing B̂ = [b̂1 , . . . b̂r−1 , aj , b̂r+1 , . . . , b̂m ] , where b̂i = bi , i 6= r and b̂r = aj . Clearly (x̂B̂ , 0) is a
BFS of LPP if,
yij
x̂B̂i = xBi − xBr ≥ 0 , i = 1, . . . , m. (1)
yrj
Note x̂B̂r ≥ 0 So, we have to focus only on i 6= r. Now if yij ≤ 0 for i 6= r , then for all such
indices i , we have x̂B̂i ≥ 0. If yij > 0, i 6= r , then (1) holds if and only if
xBi xBr
yij ≥ yrj , for all such i 6= r , for which yij > 0 .
Choosing an index r such that
 
xBr xBi
= min | yij > 0 (2)
yrj yrj

will make sure that (1) holds.

c Copyright Reserved IIT Delhi

 5

By choosing r , according to (2) we make sure that the new matrix B̂ is a basis matrix with
corresponding BFS (x̂B̂ , 0). Now we compute the objective function function at the new BFS.
Let it be denoted by ẑ. Then

ẑ = ĉTB̂ x̂B̂
m
X
= cB̂i x̂B̂i
i=1
m
X yij xB
= cBi (xBi − xB ) + cj r
yrj r yrj
i=1,i6=r
m
X yij xB
= cBi (xBi − xBr ) + cj r
yrj yrj
i=1
m m
X X xBr
= cBi (xBi + (cj − cBi yij )
yrj
i=1 i=1
xB
ẑ = z + (cj − zj ) r
yrj

where z is the objective function value at the BFS (xB , 0). If xBr > 0 ,then ẑ > z provided
zj − cj < 0.
Thus, in absence of degeneracy, the objective function value ẑ at new BFS (x̂B̂ , 0) strictly im-
proves ( remember, the LPP is a max problem) over the current objective function value z at
(xB , 0) provided we can make sure that zj − cj < 0.
The above discussion can be summarized in the following theorem.

Theorem 3.1 : If some zj − cj < 0, for nonbasic index j and for that j some yij > 0 then there
exists a new BFS (x̂B , 0) such that z(x̂B ) ≥ z(xB ), where z(xB ) and z(x̂B ) are the objective
function values of LPP at current BFS (xB , 0) and new BFS (x̂B , 0) respectively.
Thus we have shown that a given BFS (xB , 0) can be improved upon provided:
(i) There exists a nonbasic variable xj such that zj − cj < 0.
(ii) yij > 0 for at least one value of i.

It may be noted that any value of j satisfying zj − cj < 0 can be selected for improvement
and there is no way to select the unique one out of many, yet it is a numerical convention
to choose the one for which zj − cj is the most negative in anticipation that it will yield large
improvement in the objective function value. The variable xj for which zj − cj is most negative
is thus selected to enter in the current basis matrix B and the variable xBr which is presently
a basic variable is selected to leave the basic matrix B by (2).

c Copyright Reserved IIT Delhi

 6

The method in (2) of determining the departing variable index r is called minimum ratio
rule. Subsequently we observe only one column change while moving from B to B̂. The column
br is replaced by aj . The variable xj is refereed to as entering variable while the variable xBr
leaving the basis is called the departing variable.

This iterative scheme of generating improved BFS can be continued till we reach one of the
following situations.
(i) zj − cj ≥ 0, ∀j
(ii) zj − cj < 0 , for at least one j with yij ≤ 0, ∀ i.

In case (i) holds then LPP reaches its optimal solution and the last iteration BFS yields the
optimal solution and optimal value of LPP. Case (ii) needs further discussion which we shall
postponed for coming lectures.

c Copyright Reserved IIT Delhi