Module 9
Basic Feasible Solution of Balanced Transportation Problem:
Recall that the coefficient matrix A in(TP) is of order (m + n) mn. So, it has mn columns
which we have denoted by aij , with a11 as first column, a12 as second column and so on.
Remember aij = ei + em+j . Now, symbolically we create another matrix as.
a11
a21
..
.
a12
a22
a13
a23
am1 am2 am3
a1n
a2n
.
amn
Note each cell in above matrix is a column vector. In this Lecture, we shall first see that because
of unimodularity of matrix A, the non-basic columns in a simplex tableau for (TP) (if (TP) is
solved by the simplex method) can be expressed as linear combination of m+n-1 basic columns
with coefficients 0, +1 or -1 only. This is advantageous and we shall explore how these special
numerical values of scalars help us to get the new BFS of (TP) with much more ease without
working with inverse of basis matrix in each tableau. The latter makes computational efforts so
simple that one need not necessarily work with the simplex method for (TP) rather exploiting
this advantage one can design a new algorithm for such a class of problems. So, lets begin this
journey first before we actually start discussing the n
ew algorithm for (TP).
Let me just refresh that in the simplex method, when we move form one BFS to another what
principally we were doing is identifying a non-basic variable to become basic (entering vector/variable). In this process we try to write the current entering variable xj column aj in A
(the coefficient matrix in LPP) in terms of basic variable columns. Recall that for basis matrix B,
aj = B yj or yj = B 1 aj .
To determine scalars yj ( which virtually form the column in simplex tableau), we required to
invert the basis matrix B. This was precisely what was done by pivoting in simplex tableau.
Now, with the above background in mind, let us see what these yj s values be if (TP) is solved
by the simplex method. Because of double subscript used for denoted each column of coefficient
matrix A in (TP), let us assume that current basis of (TP) is B=[a ]. Since rank(A) =m+n-1,
So order of B is (m + n 1) (m + n 1). Let us assume that there is an non-basic column
aij of A which is a candidate to enter in the basis. Then there exist scalars yij
s such that
aij =
yij
a .
We claim that yij
can take value in the set 0,1,-1 only , (, ). We may not prove it but
definitely make an effort to convince you. For sake of illustration assume that m=2, n=4. Then
c
Copyright
Reserved IIT Delhi
A is of the order 6 8 and the corresponding symbolic matrix is
"
a11 a12 a13 a14
a21 a22 a23 a24
#
.
Suppose the 5 (=m+n-1) basic columns in B are a11 , a12 , a14 , a22 , a23 . In other words, the basic
variables are x11 , x12 , x14 , x22 , x23 and the BFS network is as follows
Let these basic columns be encircled in symbolic matrix for clarity.
Now convince yourself that the three nonbasic columns can be expressed as follows
a21 = a11 a12 + a22
because
a21
0
1
1
0
0
0
61
1
0
1
0
0
0
1
0
0
1
0
0
0
1
0
1
0
0
Similarly
a13 = a12 a22 + a23
a24 = a22 a12 + a14 .
c
Copyright
Reserved IIT Delhi
= a11 a12 + a22 .
3
See, how to depict these ideas in basic feasible network. We illustrate it for a21 .
Now suppose a21 enters into basis. Draw the edge in above network (red) for it. Identify that
this introduction leads to a cycle in this network and the cycle is O2 D1 O1 D2 O2 ; starting
with O2 and ending at O2 traversing edges from the current network. In this cycle certain edges
are traversed in the direction as apparent in network while some are in opposite orientation.
Like O2 D1 is compatible with its orientation while D1 O1 is opposite, then O1 D2 is in same
orientation but D2 O2 is opposite. So we express it as if
(O2 D1 ) + (D1 O1 ) + (O1 D2 ) + (D2 O2 ) = 0
or in other words
a21 + (a11 ) + (a12 ) + (a22 ) = 0
a21 = a11 a12 + a22 .
Appreciate it is same as what we had discussed above.
Similarly, instead of O2 D1 suppose the edge O1 D3 is introduced in current BFS network(i.e.
a13 is entering column). Then it again leads to a cycle O1 D3 O2 D2 O1 . By same argument of
edge orientation, we can express it as
(O1 D3 ) + (D3 O2 ) + (O2 D2 ) + (D2 O1 ) = 0
or we get
a13 + (a23 ) + (a22 ) + (a12 ) = 0
a13 = a23 a22 + a12 .
Two important things to note here. One that each time we introduce a nonbasic variable column in a current basic feasible solution we form a cycle in a corresponding network and each
c
Copyright
Reserved IIT Delhi
time this cycle is unique. In fact latter is a property of basis that every non basic variable can
4
be expressed as a unique linear combination of basic variables. Second, due to formation of
cycle we can always expressed the entering edge (or column aij ) as a linear combination of the
existing basic edges in the network and the scalars in this linear combination are the orientation
of the edges (if included in cycle), i.e. +1 or -1. For edges not a part of the formed cycle, the
corresponding scalars are zero. Thus
aij =
yij
a
has yij
= +1, for edges in opposite orientation and yij
= 1, for edges in same orientation
of existing one in the current basic network. For remaining edges (not in cycle but in network)
yij
= 0. Thus, yij s are either 0 or 1 or -1. This phenomena is not restricted to above example
only but in general, in any (TP) network. Basically those of you who are familiar with concepts
from Graph Theory (do not worry if you are not !), can easily relate it to the notion of Tree.
The current basic feasible solution network is a tree (m+n vertices and m+n-1 edges and also
connected). The moment an edge enters in this tree it leads to a formation of a unique cycle.
Precisely this is what is happening above. Moreover, we can explain all this in symbolic matrix
of (TP) too. For instance,
let a21 enters into the basis. What we do is that we try and make a loop, comprising of
horizontal and vertical lines only, starting from cell (2,1) and it must contains minimum one
basic cell and not more than two consecutive basic cells from same row or column. For example
if a21 is entering, the only possible loop is
a21 a11 a12 a22 a21 .
The same is depicted in figure above. Verify that this is the only loop with a21 (as expected too
a unique combination). Take alternate + and - sign (starting with +) in this loop to write
a21 = +a11 a12 + a22 .
We encourage you to see that the same concept can be applied to the other two non-basic cells
too. Whichever the way may be but get convinced that the yij s are in the set {0,1,-1} only.
c
Copyright
Reserved IIT Delhi
Due to this characteristic to ys, we realize that the minimum ratio rule in simplex method, i.e,
5
min
xBi
yij
| yij 0
is applicable to only those yij
= 1. And thus if xrs is the outgoing variable in (TP) (or corresponding column is ars in A), then the new BFS for (TP) is easily available as
x
bB
xB + xBrs
=
xB xBrs
xB
yrs = 1
yrs = +1
yrs = 0
for 6= rs and
x
bBrs = xBrs
.
All this is happening because of unimodularity of matrix A. We can hence avoid any kind of
basis matrix inversion in the algorithm we intend to develop specifically for (TP) . And this is
precisely what motivates us to explore a new algorithm for solving (TP) rather than restoring
to the simplex method.
In between somewhere we have talked and explained what a loop is in context of (TP). Let us
formly define it.
Definition (Loop): An ordered sequence of four or more different cells in a symbolic matrix
of the given balanced (TP) is called a loop if (i) any two consecutive cells in it lies in the same
row or same column and (ii) no three consecutive cells in it lie in the same row or in the same
column.
Note every loop must have even number of cells as the first cell is considered to follow the last
cell (means loop is a closed structure).
example of loop
(1, 2), (2, 2), (2, 3), (3, 3), (3, 4), (1, 4), (1, 2)
c
Copyright
Reserved IIT Delhi
example of loop
6
(1, 2), (2, 2), (2, 5), (3, 5), (3, 3), (1, 3), (1, 2)
Another fact and seriously important is that the set of columns of A are linearly dependent if
and only if the corresponding cells in the symbolic matrix contains a loop.
So, how we are going to use the notion of loop? See, suppose somehow by some technique we are
able to obtain a BFS of (TP) and somehow we also check that this BFS is not the optimal one.
So, next what we do is to first identify that which variable has to enter in the basis and that
of course we will decide by calculating the opportunity cost of each cell (we will come to this
point shortly). After that we shall form a loop starting with this entering cell. This loop (exists
uniquely) will enable us to figure out what is the value of each yij in the linear combination
of entering column in terms of the current basic columns only. Thus the loop to be formed
comprises of only current basic cells except the one cell which is entering cell. This loop will
also help us to identify the vector to leave the basis. In this way we shall be getting a new BFS.
Thus, loop is a pivotal structure in the algorithm that we shall be discussing in the next lecture
to solve a balanced (TP).
So, by now we get into the mood of designing something new to solve (TP) than to apply the
simplex. One important question to answer here is that how we will choose our initial BFS in
(TP).
Initial BFS of (TP): There are quite a few good method to get the IBFS. But we shall be
describing only two here for brievety.
1. North-west corner rule.
2. Vogels approximation method (VAM).
We shall be understanding both the methods by simple illustrations.
Example 9.2.1: Consider the following (TP)
P
P
Observe
ai =
bj = 50. So, it is a balanced (TP). Now, start from the north-west corner
cell; in our case it is cell (1,1). Fill x11 = min{a1 , b1 }. For example, here x11 = min{15, 5} = 5.
Write this value in top with box around it. Once this is done we observe that requirement of
D1 is fully met, so we virtually cross-off D1 column as D1 will now not accept any product from
any where. Now since O1 has supplied 5 units to D1 , its availability a1 has reduced to 10.
The next north-west cell is then (1,2). Fill this with x12 =min{availability left, requirement left}.
c
Copyright
Reserved IIT Delhi
For our example it is x12 =min{10,15}=10. Now, availability of O1 is completely exhausted. So7
assume to cross off O1 as this origin can no longer supply anything. The next north-west cell
is (2,2). We take x22 = min{25, 5} where 5 is the left requirement of D2 . And proceed till we
reach the last cell. The final solution that we so obtains in our example is shown below.
In case of a tie situation while selecting and assigning xij =min{availability left at Oi , requirement left out at Dj }. we will get a degenerate BFS, as here in such a situation, we will virtually
be deleting both row and column corresponding to a common minimum value. The number of
basic cells will be less than m+n-1. To complete it, we shall be assigning zero to any cell (not
included in basic cells in the table).
Example 9.2.2: Consider the following (TP) with three origins and three destinations
P
P
Note that it is a balanced (TP) as
ai =
bj = 20. Suppose we start allocation from cell
(1,1). Then x11 = min{a1 , b1 } = min{10, 5} = 5. Since D1 requirements is fulfilled we move
to next cell (north-west) which is (1,2). Allocate x12 = min{5, 5} = 5. Since both availability
at O1 gets exhausted and requirement of D2 are completely met, we go to the next north west
corner in reduced matrix which is cell (2,3) and allocate x23 and proceed to get a solution
as shown in above matrix. Note that the feasible solution so obtained has one 4 basic cells
(1,1),(1,2),(2,3),(3,3). having positive values. This is the case of degenerate BFS in (TP) as the
fifth basic variable (any cell which is currently not allocated positive value) takes the value zero
only. In the lecture to follow, we shall be explaining you another important and perhaps most
popular method called Vogels approximation method (VAM) to find an IBFS for (TP).
Feasible se
x
X
x2*isX not integer
x x
!
x2* +1
x
x
x2*
x
Can be removed
~
y
Wow! We are ready to begin
c
Copyright
Reserved IIT Delhi
c
Copyright
Reserved IIT Delhi
