Tip:
Highlight text to annotate it
X
So, let us continue with our miss minimum cost flow problem; I will quickly revise the
whole thing. So, we said that we will have starting solution as a structured (T, L, U),
where T is the, a spanning tree; yes, spanning tree consisting of basic arcs.
Now, these arcs, the flow may be, some of the flows may at their upper bounds, but we
will call these the basic arcs. So, the spanning tree is the spanning tree consisting of basic
arcs. Then L is the set of non-basic arcs at their lower bound, which is zero in our
case right now. So you can see, the, you can guess that they
can be situations, where the lower bounds are not necessarily zeros, we will just mention
them in at the end of the... And that this thing over, then U is the set of non-basic arcs at their upper bounds.
So, we have the structure given to us starting thing and we also need to discuss later on
how to get a starting spanning tree structure like this; we will do that, so anyway then
given this, the compute the dual solution, so I was mentioning the last time also compute
the dual solutions. So, this we do by select to or put w 1 as 0; so, we are always do that
and so, we call this the, we also call this the root node.
And therefore, the spanning tree is also called a rooted tree and the significance of this comes in later on but anyway right
now we had saying that w 1 is 0; so, then you can compute the remaining w I n minus
1, w i is uniquely. So, you can do that, because you will have
for the basic tree, you have n minus 1 arcs and once you fix one of the w i's, you have
n minus 1 w variables to decide given n minus 1 equations and so, because the relative prices
for the basic arcs must be zeros, so we get the remaining this thing.
And the process is not difficult, because you see it is a spanning tree, so it is a
connected tree with n minus 1 arcs; so, once you have your arc 1 and here you have put
the dual variable as 0, then there will be at least 1 arc incident on it correspondingly
for this let say it is j1, then you will fix, you say that w 1 minus w j 1is equal to c
1 j 1, so that is
tell you that w j 1 is minus c 1 j 1, similarly, because it is a connected thing they will
may an arc like this or like this. So, you just move on because the tree structure
is given to you, so you can and given as we mention that the basis is triangular; so,
backward substitution you are essentially doing and the backward substitution, you are
starting from node 1 onwards. So, you can accordingly fix as you go along the tree,
you can fix all the dual variables also, so we do that and then...
So, after that, compute c i j bars right and we said that if c i j bar is greater than
0 or x i j 0 right for non-basic variable which is at its lower bound, then you cannot,
because increasing the value here would also increase the objective function value; so,
this is the so, this is optimality criteria for x i j 0 and if c i j bar is less than
0, for a basic non-basic variables at its upper bound, then also we cannot improve the
value of the objective function, because if you want to reduce this value then c i j bar
negative, the product will become again positive and it will be a positive increase in the
value of the objective function right. If this, then the current solution is optimal.
So, therefore, we will look for, we will always at the end of, once we have obtained a basic
feasible solution; we will very check for optimality, if we find some arcs violating
the optimality condition, then we will consider them for entering into the basis. So, now,
here as I said, right now I will follow Danzig's pivot rule which says that you select the
arc which violates optimality criterion the most, that means, it may either be c i j bar negative
which is the most negative or it may be a c i j bar positive which will is post positive.
So, that means, you will have to compute all the c i j bars for the non-basic arcs and
then select the one which violets the optimality condition the most. So, then it is rule and
I as, I told you that the other pivot rule could be that, you the moment, you find one
arc which is violating the optimality condition, you enter it.
And of course, there can be , so these are the two extremes, you first compute all c
i j bars and then find the best one to induct, best one in Danzig cells or you just the moment,
you find one arc which is violating the optimality condition you try to enter it. So, there are
also in between rules and you know one can, I will give you some more references later
on, see you can go through them, so that is it. So, once we, then therefore, we use Danzig's
pivot rule, so we decide on an arc to enter the basis and now what happens when an arc
enters the basis.
So, that means, you will add. So, suppose, consider now let us say that c i j bar is
less than 0 and currently x i j is 0; so, that means, this is a non-basic variable at
its lower bound and the corresponding c i j bar is less than 0. So, improve increasing
the value of x i j will improve the objective function value. So, in that case, if you consider
T union i j has a cycle, see I went through all this in detail for the transportation
problem, where I demonstrated to you, how a theta loop could be available and the same
kind of thing happens here. So, we will not spend time on rigorously establishing that
this will have a cycle but, anyway because this will be now n arcs and so they must be
linearly dependent, because the rank of the matrix is n minus 1.
So, this will have a cycle, we showed you is a minimal in his concept minimal dependent
set; so, that means, it will be the set of columns which have a two entries, each column
of the set consisting of the cycle will have two entries one plus 1 minus 1 and so, when
you add up, you can add up, all the rows will be 0, anyway so this has a cycle.
So, now let us consider a configuration; suppose this is i and this is j and then you may have
j 1 and then you may j 2 and this may be j 3 and then this. So, this is your cycle and
now what we talk about I have already mentioned all these things, so I am just going through
them; so that, you have a, you can recall all these things, so the thing is that, we
want to increase the flow along this direction right, on the arc i j because the c i j bar
is less than 0. So, then we give an orientation to the cycle
which is the same as the orientation of the arc, because you want to increase the flow
in this direction; so, that means, a, now the ideas to determine by what level you can
raise up this value; so, suppose I want to increase the flow by delta here, then this
arc also has the same orientation as the cycle or as the arc I j; therefore, also here also
the flow will increase. But now, this arc has an orientation which
is opposite to the orientation of the cycle therefore, this will the flow here will decrease
and so we indicate that by minus delta, because see the arc is in this direction; see, if
I try to flow something which means I am actually reducing the flow on this arc right, then
here this also has the same orientation, so this will be plus delta and this will be delta.
So, all these arcs will have, now what are the considerations as usual again the same,
see the, it is a same simplex algorithm, I first showed it to you, how it can be implemented
on a transportation array, you saw the simplifications tremendously its tremendous simplification.
Now, I am just trying to show you how to implement the simplex algorithm on the on a graph on
a network; this is the difference, otherwise the theory and everything remains the same.
So, in any case you want to just quickly recall, so here you see you will have three values;
delta 1 will be the smallest value for which a basic arc; so, that means, I am considering,
see here you have this kind of thing and you may already have a flow here j j 1; so, then
you do not want and here this would be the flow, now, will go up to plus delta. So, then
we do not want the flow on this arc to go beyond its upper bound, so we saying smallest
value for which a basic arc reaches its upper bound. So, that means, you are going to say
that this is u j j 1, so which implies the delta isless than or equal to u
j j 1 minus x j j 1 delta is this. So, then among all such deltas, that means, among all
the positive deltas, so here for example, this would be your delta would be less than
or equal to u j 3 i minus at whatever the flow here x j 3 i and so on, so far, all positive
deltas you will compute the smallest one, because none of these constraint should get
violated; so, delta 1 is the smallest value for which a basic arc delta 1 is smallest
value of delta for which basic arc reaches its upper bound.
Similarly, delta 2 would be, now here you see that for they once for which is negative,
see here the new value is x j 2 j 1 minus delta, I am trying to flow delta units among
this, which means that, the you actually reducing the flow on this arc by delta; so, this is,
this now this should remain greater than 0, which implies that delta has to be less than
or equal to x j 2 j 1. So, whatever the flow on the arc j 2 j 1,
your delta cannot exceed that for all the minus 1. So, delta 2 is the smallest value
for which no basic variable, no basic arc has negative flow, so you want to make sure
that. When you increase the flow on a basic non-basic arc none of the basic arcs has become,
has a flow less than 0 and what is your delta 3, I am increasing the flow here.
So, delta 3 is actually your, here it will be u i j or in other words, delta 3 is the
upper bound constraint for the incoming arc you would increasing the flow here. So, in
a, I can say that this is going to enter the basis, it is going to become basic depends
on how what the choice is right. And now let us quickly write down, so how and similarly,
you can write down these values, when so I have considered the case or maybe I will draw
it again for you here.
And will quickly revise the considerations; so, now you can also have a situation when
the arc has a flow like this, then may be let us consider the same situation j 2 has
this one and now in this case when c i j bar is greater than 0 and the flow x i j is u
i j; so, that means, this is saturated on. And if part, if the c i j bar is greater than
0, producing this value will give a decrease in the value of the objective function.
So, therefore, now your orientation will be reversed, I will do it this way and so, this
will be minus delta, here again this will be minus delta and this is also opposite,
but this will become plus now and this will be minus delta. So, I want to decrease the
flow on or arc i j, then I will use this device; so that, I, so that, the orientation or becomes
opposite to the direction of i j because I want to give flow into a cycle in this direction
anyways and you can you self-observe just like theta loop that, because I am changing
the flow along a cycleat a every node conservation is there and so your constraints will not
be violated the constraints will remain entire. So, here also what we are doing is, we are
saying that this has to be like this and which means that the flow here will go down by delta.
And so, again when you want to determined you will have the three numbers, again see
here, delta cannot, so here delta cannot be greater than u i j, because otherwise the
flow here will become negative and then for all these minus arcs, see here the flow.
So, therefore, here the delta will be governed by the amount of flow that you have in this
direction, because the same consideration as you had for the arc j 2, j 1 see here we
said that delta has to be less than or equal to x j to is, so wherever there is a minus
sign, the delta will be governed by the amount of flow, that is there already in the arc.
So, in our case, this one, the flow is here u i is equal to u i j and on this just x j
3 i and so on so for, minus 1, the value of the delta has to be governed by the amount
of flow, that is already there in network; for plus 1, here your consideration will be
that, this arc should notagain exceed its upper bound. So, here you will have the that
delta must be less than or equal to u j 2 j 1; in other words, your whatever the flow
j 2 j 1, this is the flow plus delta should be less than or equal to u j 1 j 2 and so,
once you understand because the theta loop part was very welldone with you.
So, you understand that this everything, so once, that means, depending on what kind of
a arc we are entering into the basis, we will compute these things and decide. And so, now
once you have decided the value of delta, so then you update, that means, update the
flow in the network; so, you, this is the next step update the flow in the network.
Now, you have to recompute the dual solution, so just has in the case of the transportation
problem. I showed you a, show shortcut, so here also there is a shortcut we do not need
to compute the dual solution from scratch, we can take advantage of the our earlier calculation;
so, for example, what we are saying is that, if suppose you have something like this, suppose
this is a tree solution and suppose this arc is a candidate for entering the basis.
So, then and I should have told you that wherever, the say for example, out of these three, I
should have mention this also, see the of example, if delta is equal to delta 1, that
means, the minimum of the three, so I should have written that down. So, final choice of
delta is minimum of delta 1, delta 2, I hope you can read it, this is delta 3, so out of
these, when once you compute these three numbers, then choose its smallest one of the three
and that will be the a value of delta, at which this variable will enter, the this arc
will become a basic arc and the flow will get determined.
So, here for example, if delta is delta 1, then what is happening if delta is delta 1,
that means, one of the arcs is reaching its upper bound, before any of these two things
is happening, so what will be do, once this happens so again I will not right it down,
because the same steps for the as we did for the transportation.
So, once an arc reaches its upper bound, we will rename it as a non-basic variable and
drop it from the basis; so that means, suppose it is this arc which is reaching its upper
which for this minimum is attained; so, then this will reach its upper bound, when I update
the flow so this will become a basic arc and this would become non-basic. So, again I will
have to recomputed my, so that means, this is my incoming variable, this is my exiting
arc from the basis; if the minima occurs for delta 2 out of these 3, delta 2 is a smallest
number, that means, some arc is going to become 0 when I have the flow at level delta in the
cycle. So, that means, one arc will become and so
you can say that for example, here smallest variable for which the basic arc has negative
flow will become negative; so, that means, before that happens, so here that means this
arc therefore, becomes non-basic and this arc becomes basic the usual pivot, because
this will become 0 and this has become positive and if delta is minimum for delta 3, then
this has reached its upper bound, before anything else has happens.
So, that means, I do not have to change the status of i j, the arc i j remains non-basic,
but now it reaches its upper bound, so it is there is a positive flow on the arc which
is equal to its upper bound, but I do not change the status of the arc it remains non-basic.
So, these are the three things, that to so you have this is, this describes your pivot
rule completely and accordingly you can also manage the pivot rule here.
So, now you have to recomputed; so, how do you recomputed the dual solution; so, idea
is that, I will give you the simple rule here, try to write it in this much space. So, this
is suppose, arc i j is entering the basis and arc p q is leaving the basis and I have,
you have seen that it can be in two different ways, either the flow is becoming 0 or it
is reaching its upper bound two things can happen.
So, its leaving the basis, now what you do is, before you do this, actually arc i j is
entering and this arc p q is, so drop p q from the current tree, which I mean is that,
before you have done the pivot, before the pivoting, drop p q form the tree before the
privet; so, you are dropping this in that and then this, this will decompose the tree
into two trees T1 and T2, where one node, one belongs to T1, so your root node
Node 1 belongs to so we will call that sub tree T1, in which T1 lies so and the other
one is T2; so, that will always happen, you see because it is a minimally connected tree
sub graph; so, let say example, if I drop this arc from the tree, then I will have this
portion and I will have this portion, look at I drop this arc I drop this arc, then I
will have T 2 will be just simply this node and T1 will be this because one belongs to
T1; so, you will always have 2 sub trees, a moment you drop the exiting arc from the
basis.
So, then and now you have two cases, q belongs to T 2, see so therefore, before I say that
so wi's for I belonging to T1 do not change why because this remains 0. So, since T1 all
these arcs are connected to node 1; so, therefore, your dual equations remain intact and so these
dual variables will not change.
So, wi's for i belonging to T1 do not change, because my value here of the dual variable
corresponding to the root node does not change. Now, if q belongs to T 2 for the two possibilities,
if the arc is like this, so for example, and let me say that this is the exiting arc, so
let us say 35 is the exiting arc and this is coming in, in this one; so, what we are
saying is that, here either so what is it, if this is leaving the if you are dropping
this, then what is your T 1, see I have drop this, see your T1 is this these three arcs
and your T 2 will be simply this one T 2consists of the arc 56.
So, now, you if the arc is in this direction, then your node 6 belongs to T 2 and if the
arc will be in this direction, then what we will say is that, see if I call it p q, then
p will be in T 2, so that depends on the notation, if q belongs to T 2, then what is happening,
so then you see, because p is not in T 2; so, the value of the p has not change, then
you have the equation . So, then let me write it this way, then c p q minus w p plus w q
is c p q bar and which is less than 0, because that is why we decided that p q will enter
the basis that was at 0 level; so, then this is this, and if w q prime is the new value w q, then what is the equation that
needs to be satisfied, then we want that w p minus w q prime should be equal to c p q
now because p q is going to become a basic arc this is it; so, which implies that your
w q prime is equal to q w p minus c p q and from here w p if you take it to this side
is equal to w q minus c p q bar. So, that means, that the new value of w q prime is
w q minus c p q bar. So, the value of w q changes by you subtract c p q bar from it.
And so, this is the new value that we have and we have already discuss; this again in
the transportation problem, that now in this T 2, if for example, this value has change,
then this value will also change because they are connected by the same amount; so, that
means, what is our rule, now for all nodes in T 2 the dual solution.
So, when we are re computing the a dual solution, so what comes out is that, wi's for i belonging
T 1 do not change; so, you do not have to spend time computing them and for and w i
goes to w i minus c p q bar for i belonging to T 2, where we know the p q is the exiting,
sorry, what did I say here, yes it has been clear is i j is entering, so I should have
and the basic we drop pq and I should have, I should have said, if I say that, it is i
j which is entering, then if j belongs to T 2, then I have to recomputed.
So, maybe it will be easier to I will keep it has q T 2 I have read this; so, here we
will say that i j is the, is the exiting is leaving the basis n r p q is entering; so, make it the other way, so then drop i
j from the tree before the pivot; this will decompose the tree into two trees and we will
call T1, that tree for in which one lies and the other sub tree would be T2 and then we
are discussing like this. So, if q is T2, so therefore, we have to,
so then the these values will change by c bar p q, so we said that you see when the
arc p q is entering the basis and i j is leaving the basis, then why by dropping arc i j from
the tree; you see it will get disconnected into two parts, we said. And then, so T1 and
T2 will be the two parts of the tree and note we call T1 that subset of the tree in which
node 1 the root node lies; so, therefore, T1 will be that particular tree and T2 is
the other one. Now, the wi's, so recomputed the dual solution I am giving you a simple
formula; so, this is wi's and T1 will not change, it is only the wi's for the nodes
in T2 which will change.
And so here I am saying that see for i in T 2, the calculation I have already shown
you the w i will change will reduce by c p q bar; so, that means, the new w i would be
w i minus c p q bar and then of course, we will continue with the algorithm, but in case
p belongs to T 2, that means, the arc p q that is coming into the basis, so, either
the node p belongs to T2 or the node q.
So, in case, node q belongs to T 2, then we update the corresponding dual value by w i
minus c p q bar and in case, p belongs to T2, then w prime p minus w q, you see well
the calculation is simple, the new w p prime the value of this w p prime minus w q is c
p q because the arc is coming into the basis, so, the new dual values should satisfy this
particular dual constraint as equality. So, therefore, it follow the w prime is w
q plus c p q, now when you substitute for c p q bar, then the w q will cancel and you
will have w p plus c p q bar; so, that means, w p has gone up by c bar p q. So, if p belongs
to T2 then the dual variable will, the value will go up by c bar p q and since the, your
T2 is connected, that means, that all nodes in T2 the, the dual variables will go up by
c p q bar.
So, this is how if you can remember the simple formula, then you do not have to re compute
the dual variables for all the nodes; you only have to re compute them by for the nodes
in T 2 and that also the formula is simple, that if p belongs to T 2, then the values
go up by c bar p q and i f q belongs to T 2, then they reduce by c bar p q or i belonging
to T 2. So, once therefore, a real shortcut to re computing your dual solution, here again
we are taking advantage of the structure of the problem; so, we are exploiting the structure
and simplifying our computations.
So, now this happens, so then we continue, so then continue with the, I have already
said that you update your flow in the network to re compute the dual solutions and then
continue with the algorithm. Now, there are two issues that we need to look at and so
I will first work out an example for you quickly, I will show you one or two iterations of the
algorithm and then we need to look at how to compute the starting dual feasible solution;
that means, I must get a starting structure T, L, U and given a problem to solve and secondly,
we have to tackle degeneracy.
And again is nothing different adjust, that here again people take advantage of the structure
and try to come up with the simpler rule, for you know , so they take up this example,
now here the numbers are c i j u i j; so, the first number is the cost, the second number
indicates the upper bound on the flow, that can take place on that arc, then these numbers
are the di's; so, here for node 1, it is 25 units, that is only source the other, so these
3 do not have anything available, then 5 and 6 are in our sense markets or the demand points.
So, then they add up so sigma b i is 0 and you are told that, this is the initial solution;
so T is this and U contains these three arcs which the flow is are at their upper bounds
and this is the arc which has 0 flow; 3, 4 so I have try to draw the thing here and let
us see so 1, 2 and what we will do is, we will indicate the, I find it convenient to
represent this as a broken line and so there 1, 2, for example, so you had 20 units this
upper bound; so, that means, the flow here is 15.
So, then this flow is 10 and so the round circles indicate your basic arcs and the square
ones indicate the non-basic arc at their upper bounds, the flow is at their upper bound,
then you have 2, 4, the flow is at its upper bound which is again 15. So, I can fill up
this and then you have 4, 6, the flow is 10, which is so we will again denote this by broken
line and this is also a broken line. So, then you have a 10, so 10 go up this way
because this only thing; so, 10 going this way, then 2, 5 you have how much, now this
is 15, this is going 15, so this much have 10 units of flow remember conservation; so,
if 25 units are coming in here then 25 units have to go out. So, this just becoming familiar
with the, you know when you trying to do the algorithm on a on a network. Now, here 5 units
for required and so you have 25 then, you have 4, 5 and 5, 6; so, 45you have 10 units
coming here, then you need 10 more here; so, this will be 10.
And so 10 going out, so you must have 5 units coming here, because 5 units are demanded
here; so, 10 are coming, so this way you have 5 more units, so 15 are coming, then 5 get
absorbed here and 10, go on this way. So, this is your starting feasible solution and
3, 4 is 0 and in fact 3, 4 and 3, 5 both I have not, may I should have included 35 also,
both these arcs are at their lower bounds which is 0. Now, and we to compute the dual
solution, we will quickly do this and then you see that here, I will just write it out;
so, the cost is 3, so that means, 3 minus 0 plus w 3 is 0, the basic arc which says
that w 3is minus 3. So, it is minus, so for these arcs, it is
so, I will write this is minus 3; so, same thing we were doing that on transportation
array, now we have to do it on the network. So, here again this were this cost is how
much 3 into 2, 6, so you want that the c i j value, that means, the c i j value 6 is
equal to essentially u i minus 3 plus w 2; so, w 2 becomes 9, but then it should be minus 9; I think according to
me, this is 6, so we want the relative price to be so 6 plus 3 plus w, sorry this is minus.
So, therefore, so your w 2 is minus 9 and I will tell you, why I could realize that,
this is not correct, the plus 9 was not correct, I will get back to you in it; similarly, let
us quickly do this, so this is a because for the transportation problem, it all sub plus
we had got rid of the negative sign, but here the negative sign is intact, therefore, so
for 25 what is the calculation, so 2 should be equal to minus 9 minus w 5 so minus w 5
is or w 5 is 11 minus 11. And for this one, again you will have to right out 7 is equal
to minus 11 minus w 4, so that gives you w 4 as something wrong, because so w 4 is minus
18 let us see that; let me right it again, see what we are saying c 4 5 minus w 4, again
I was not writing it correctly. So, this is because arc is 4, 5, so minus
w 4 plus w 5 is 0; so, therefore, this implies that w 4 is equal to c 4 5 which is 7 and
this is minus 11, so this is minus 4, w 4 is minus 4 we will check this in a minute.
Now, the values, fine, so then this for 5,6 what is the, what is happening the cost is
1; so, one should be equal to minus 11 minus w 6; therefore, w 6 is equal to minus 12.
So, given this basic feasible solution, I compute the relative prices and you see that
from here for 3, 4 that is positive, so that will not be candidate c 35 bar is minus 3,
so this can be a candidate for entering the basis and c bar 24 or is 9 and since this
is at is upper bound; the positive number here implies that, when I reduce the flow,
the cost will also come down; so, these are the, where 4,6 is as its upper bound and minus
5 does not help.
So, therefore, the arcs that are candidate for coming into the basis, that means, arcs
3, 5 and 2, 4 are candidates for entering the basis and so we will choose arc 2, 4,
that means, I will reduce the flow but, before I continue with the algorithm I just want
to make a note here that you that is a nice interpretation for the dual variables for
the network flow problem; so, here you see minus w i will be the distance of node i from
node 1.
That means, suppose I take the numbers which are the cos I can treat them as distances,
so whether I call this as a distance of node i from node 1 or the cost of reaching node
i from node 1, whichever way you want to interpret the numbers here the c i j's, then you see
for any basic feasible solution with respect to the given tree minus w i should measure
up to the distance of node i from node 1 with respect to the tree.
So, for example, in the, in the solution here you see 1, 3, so here this is and we start
with w 1 as 0, so then this is minus of this is 3, which is the distance of node 3 from
node 1. Then you can go up so to reach to node 2 from node 1, this is the path, you
will take so you add up the cos which is three plus 6, 9.
So, minus 9 is here w 2. Then similarly, when you come to node 5, this is the path; so,
here this would be 3 plus 6, 9 plus 2, 11, so minus 11 is your w 5. Now, when you go
to node 4, you see this arc, you travel from the opposite direction; so, that means, here,
I will, when I want to compute w 4, the distance or w 4 is minus 4; so maybe I should write
here minus 4, now this is or whichever way you want to do it fine, whichever way you
want to do it fine. This will be minus 3 or minus 11, I have already come up to here minus
11, then this is travels in the opposite direction; so, I will have to write plus 7 here and so,
this will be minus 4 or you want to do it, this way that 3 plus 5, so this is 11, so
if 11 and then minus 7, so that is 4, so minus 4, so the distance or the cost of reaching
node 4 from node 1 is a 4 in our term. And similarly, this is 12, that means, the currently
so every time, when you re compute your dual solution, this will be a very good check,
because you have small networks you can do it by hand.
So, therefore, you will know immediately, that given the tree solution with respect
to the tree, we find out the path for each node from node 1 and then add up the cos of
the arcs that make up that path and it should measure up to so minus of that some should
measure up to the dual value, the current dual value; so, this was just I wanted to
show you that the dual solution has a very meaningful interpretation here.
So, now, we continue with the algorithm, so I decide to choose 2, 4 because now I am using
the Danzig rule, which says that you bring the most profitable arc; remembered it is
common you would bring in the most profitable arc into the basis. So, since c bar 2 4 is
9, so here the rate of reduction in the cost would be at 9 units this thing and c bar 35,
c bar 35 is minus 3.
So, therefore, we will choose c bar 24 has to be reduced and so the cycle formed here
would be this and I consider this and the orientation has to be this, because I am reducing
the flow one 2, 4; so, then an arc 2, 4 the flow will go up and an arc 4, 5 again the
flow will go down and delta here comes out to be 5, because remember we have to make
show that the flow here should not become negative, the flow here should not exceed
its upper bound and similarly, here also the flow should not become negative.
So, the numbers are 5, 5 is 10 and you take the minimum of the three numbers, then 25,
so when your delta is 5, 25 will reach its upper bound, because the currently, the flow
is 10 and if I add 5 more units 15, the upper bound will be reached. Now, I have three
choices here and 24 becomes basic because flow here has now come down from its upper
bound and 4,5 what is happening for 4,5, what is the current flow the current flow is 5;
so, if I reduce the flow, then this become 0. So, you see, you have, either you have
a choice of allowing making 25 and a non-basic variable ordropping 45 which is a non-basic
variable at 0 level.
So, we decide to, and this is where you see the problem in the simplex algorithm can come,
because your choice of exiting variable is not unique. So, here drop arc 4, 5 and similarly,
for the incoming variable also, we decide to drop arc 4, 5, is it and I have shown you
the updated solution here, now this is 15, I am keeping it as basic 4,5 has been dropped
this arc the flow has come down by 5 units.
So, this is it, now remember the shortcut that we have used; so, what is happening is
that, when you see the drop in the arc, which is being dropped is 4, 5, so when you drop
this from this tree, see you are dropping arc 4, 5 from here, then in the current tree,
this remains intact it is only node 4; so, node 4 now becomes your T 2 and this is your
T 1, because 1 belongs to this part of the tree; so, T 2 simply contains node 4 and since
you are the incoming arc is 2, 4, remember it was non-basic; now, we are making it basic,
so the incoming arc is 2, 4, so that means, q belongs to T 2.
And so, that means that the corresponding value for w 4 prime will go down by c 2 4
bar and this is c 2 4 bar is 9, so minus 4 minus 9 is minus 13 and this is your updated
dual solution nothing else changes, because all the other nodes are in T 1, so there the
w i is remain intact and this is the only one which changes and now you can again just
do it exercise, that the distance from here to here should measure up to 13 and other
distances remain the same, because that the only change you have made, we have made 4,5
has been dropped. So, now, that means, we, I, you re compute
my dual see relative prices and here you see that 3, 4 is a non-basic variable, the value
is minus 7 c bar 3, 4; therefore, this is a candidate for coming into the basis and
again we are using the most negative here, I am I mean absolute value in the largest
value; so this minus 7. So, therefore, arc 3,4 enters the basis fine and now when you
compute the delta, so I will let you do the computations yourself, but I have giving you
the number; so, delta is minimum, so all the three numbers are the same and here again
you have you see lot of choices, your choice of deciding on the exiting variable is not
unique; we let arc 3,4 remain and of course, because see here what is happening is that,
when you allow 3,4 to enter at level 10, then 3,4 it reaches, its upper bound and all others
also either become flow becomes 0 or attends its upper bound, whatever you can check out,
what are the choices here. So, in any case, see we will have to do least
work, when we decide not to make not to change the status of 3, 4, it is just that the flow
on 3, 4 becomes equal to 10, that means, it is equal to its upper bound. And so, we will
not have to change anything, we will not have to change our dual solution, because no arc
is leaving the basis; the basis remains intact. So, and then, but then what will happen is
will remember if you allow 3, 4 to enter, maybe I can just show you here, see this your
allowing to enter. So, your orientation will be this way; so, this becomes this and this
comes down like this and so what is happening, that both of them or a 10 so since you are
increasing the flow on this arc by 10 units, this flow become 0, this flow becomes 0.
So, you will have to, then decide on one of the variables, because you have to maintain
5 arcs in the basis; so, that you have connectivity; therefore, I will increase the flow by 10
here, so 3, 4. And so, this will remain non-basic at its upper bound, but here the flow will
become, will not disturb this one; next table, I, the next diagram I will make, but I will
keep 3, 4 and 3, 2 at 0 level but in the basis; so, this is what we are doing. So, therefore,
we do not have to do any calculations it just that this number; now, the flow an arc 3,4
is also equal to 10 and both these flows come down to 10.
So, now, I have updated the solution here, remember these two became non-basic but at
0 level. So, this is the solution, now without because my dual solution did not change; so,
I have from earlier calculation, your c bar 46 is equal to 4; 4, 6 is at its upper bound,
so this would help in reducing the cost. And now, you see when you want to reduce the cost,
your orientation of the cycle would be this; so, this would be minus delta, minus delta,
this would be plus delta and plus delta, but you see that here delta would be 0, because
this is already at its upper bound here, that is node flow on arc 2,4; so, I cannot reduce
by the flow by any amount, therefore, delta by here is also 0; therefore, this is the
d j, so that means, delta is actually minimum of 0,0,0.
I hope this point is clear, because the orientation has to be this, I want to reduce the flow
on 4, 6. So, here also it will be minus delta, there is no flow on 2, 4, then when you want
to come down this way, the delta has to be positive, so plus delta, but the flow is already
at its upper bound. So, therefore, the, a value of delta is 0,
0, 0, the minimum value which is equal to 0. Therefore, this is the degenerate pivot,
but we, it will help us to change the status of certain arcs, so that, we get a new basic
feasible solution; in the new, the sense we get a new tree, so let arc 2, 4 exist, we
are saying that because at its upper bound, so I can make it non-basic and arc 4, 6 enter
the basis. So, there not changing the flow, it all, it is just that now I am calling this
arc as non-basic and this arc 46 as basic, because trying out a new basis and this so
I wanted to show you the step also. Now, here when arc 4, 6 enters and you are dropping
arc 2, 5, so just see from here arc 2, 5 is being dropped, then you see your tree T1 remains
1, 3, 2, 4 and only 5, 6 are the this is the arc which make your T 2, I mean the, T 2 is
your 5 and then arc 5, 6 and node 6, so these are the and what is your entering arc 4, 6.
So, again q belongs to T 2 and therefore, as I am saying here that incoming arc is 46
and 6 belongs to T2therefore, w 5 and w 6 will decrease by c bar 46 which is 4 so I
have done that earlier value was minus 11 it has become minus 15 and this was minus
12 so this is minus 16 now.
So, I think I have shown you enough iterations, how to update your dual solution, how to update
the flow and so on and so, try to demonstrate to you the shortcut in computing your dual
values, then I just, I would like you to may be 1 or 2 more iterations, I think 2 more
iterations from here to reach the optimal solution and I have given an optimal solution
here, but of course, it need not be unique, because remember the choice of exiting and
entering variables has not been unique and all the iterations, but you can try out and
see. So, anyway, this is one of the optimal solutions
and if you should try to complete the, this thing; so, basically, I have try to just translate
the simplex algorithm to the network flow problem, in-cost flow problem and try to show
you that because of the simple structure, you can take advantage of the calculations
just as we exploited the structure of the transportation problem, because there the
under laying graph or the network goes simply bipartite here, of course, it is not bipartite,
but still we could explode the structure and make shortcuts in your computations.
So, I think the algorithm should be quite here, how we go about it; so, as I said that
two considerations degeneracy has to be tackled and also a starting feasible solution and
we will use here phase 1 just as I showed you for the transportation problem we can
use phase 1 and that is not difficult I, but later on, I will give you as I said for the
bounded variable transportation problem also. I will give you this max flow method of computing
the starting feasible solution, which will hold for this one also.
Because the only difference between a bounded variable transportation problem and min-cost
problem, means, that for the transportation problem, it is bipartite graph just the computations
become little different, otherwise this almost the something. So, that the idea of including
this, in the prose was I could have simple said that, you just apply the algorithm as
a quite a bounded, as for the transportation problem to this one also, but I wanted to
show you how you can work on networks directly and see the implementation of the algorithm.