Tip:
Highlight text to annotate it
X
So, let us continue with the sensitivity analysis for min-cost flow problems. I am considering
the min-cost flow and we are considering changes in U ij's; that means, in the capacities.
And let me, I will, through the examples I will try to explain and hopefully, it should
become clear. So, this was the example, which I have also looked at earlier and so the numbers,
we understand these are the Bi's, positive ones are the supplies, these are the demands,
so negative ones. And then, here, the 1st number refers to the cost and the 2nd number
to the capacity of the arc and then, yeah, so your sigma Bi's must add up to 0; this
is what our requirement is for the problem. And then, I had obtained the optimal solution,
which is shown here and crowded, but does not matter. So, these numbers refer to your
pi i's, so for example, pi 6 here is 19. So, these values are the pi i's, the dual variables
and the square numbers denote the flow on the arc, which are at their upper bound. So,
this is, these are non-basic arcs, the solid lines represent your tree optimal tree and
so here, the flows, the circle numbers give you the flow on the basic arcs. So, this is
what we have and you can please verify that this is an optimal solution, fine.
Now, suppose I want to consider the change on 1 3, that means... So, the idea is, that
I want to increase the capacity of, see for example, for, yes, I should have mentioned
that here, see, a change in the, in the capacity of a basic arc, for example consider 3 2,
the capacity is 35, but the flow on 3 2 is 15. So, increasing the capacity here will
not change my current optimal solution, because the current, because even if I increase the
capacity of 3 2 from, say 35 to 40, the current flow will remain feasible and since the optimality
conditions are satisfied, there, there will no change in the flow. This is the idea.
So, therefore, I do not have to consider changes in the capacities of basic arcs, which are
at there, which are not at their upper bounds because you already have surplus of capacity.
Similarly, for non-basic arcs, which are at 0 level, for example 2 5, there is no flow.
So, this arc is not being utilized in the optimal solution and increasing the capacity
of 2 5 also will not matter because my current flow will remain optimal and therefore, I
do not have to worry about it. So, we will only need to consider arcs, which
are at their upper bounds, because, for the non-basic arcs, which are at their upper bound,
the corresponding relative cost will be less than 0 and so increasing the capacity, if
I can also increase the flow on the arc and of course, conserve the flow in the network,
then my cost will go down. So, it is worth considering the possibility,
that if I increase the capacity of a non-basic arc, which is at its upper bound, will I will
be able to make use of that increased capacity and get, and reduce the cost? So, I will go
through the example and then, I will point out what is the main issue here.
So, for example, if U 1 3, the arc, for the arc 1 3, which is the non-basic arc at its
upper bound and its relative prize is minus 7, which is less than... because pi 0 is 0
and pi 3 is minus 9. So, you can compute and the cost of arc 1 3 is 2, so 2 minus 9 is
minus 7, which is less than 0 and so delta 3. So, therefore, let me consider increasing
the capacity of arc 1 3, say from 20 to 20 plus delta 1 3.
So, that means, I, I would like to flow delta 1 3 units on the arc 1 3, but if I do that,
then I should be able to, because you see, the demand here, the supply here has come
down because you have used delta 1 3 and then, here the number, now what is available is
plus delta 1 3. So, I should be able to send flow delta 1 3 from 3 to 1 to balance the,
to conserve the flows at each node; that is what we are doing. So, your conservation of
equation, so I mean, flow conservation equations have to be satisfied.
So, now, here of course, if you, when you, because you have a tree, you are adding this
non basic arc to the tree, then you will immediately have a cycle and consisting of the basic arcs.
So, therefore, I can consider sending slope from here to here, 3 to 1 and you see that,
and then, I will, first I will find out the path along which I can send the flow from
3 to 1 and then, we will try to find out the capacity. So, for example, here I can reduce
the flow by 20 units and here also, I can reduce the flow by 20 units.
So, that means, I can use this path and so, delta 1 3 units have to be send from 3 to
1 and delta 1 3 comes out to be 20. So, my new optimal solution, you see, I have
diverted this flow along here and here to on the arc 1 3 and this gives me, I should
have pointed out here, that the reduction in cost is equal to minus 7 into 20, you see.
So, because I have increased capacity available here, I could send 20 more units on the arc
1 3 and divert the flow on the arc 4 3 and 1 4 to the arc 1 3. So, this is the idea.
And now, if you want to look at the possibility of increasing delta 1 3 further, that means,
I have made the capacity of arc 1 3 to be D. Let us see if we can increase it further
and get a reduction. So, that is not possible with respect to the
current optimal solution because you see, that there is no path here now and of course,
talking in a very ad hoc manner, and later on I will point out the right way to go about
it. But any case, see here, from here you can check, that to send flow from 3 to 1,
you have no possible path consisting of the current arcs, current basic feasible solution
and if we look at the cost of the cycle, for example 1 3 2 1.
This is because, see here, now this is 0, 0. So, I cannot do anything, I cannot use
this particular path, because the flow from 4, 2, 3 is 0. So, I cannot go this way, I
cannot reduce the flow. So, therefore, I have this possibility of considering 1, 3, 2, 1;
1, 3, 2, 1 is... But then, the cost of this cycle, for this, if you add up is 2 plus 7,
9, minus 8 is 1. So, the cost of the cycle is 1 and therefore, the increase of 20 units
is possible, at the cost of rupees 20 additionally because the cost of the cycle is 1. So, when
I send 20 units along this path of a cycle, the cost will go out. So, it is possible.
And if, but the current solution, with, with the current solution, it is not possible with
the current solution. I got a reduction of 140 in the cost, this is one.
Then I will give you another example. So, now consider the arc 3 6, consider the, again
this is a non-basic arc at its upper bound here and you see, that C bar 3 6 is minus
5, so, which is less than 0. So, therefore, I can consider increasing in the capacity
of U 3 6, I mean, increasing U 3 6. So, path from, so the... Then, if I increase the flow
from 3 to 6, I have to divert that much flow from 6 to 3 and here, you see, this is the,
this is the path, that means, 6, 5, 7, 2, 3, this is the one along which you can send
additional flow and I mean, review the flow, that you have flow I have used for this r
3, 6. So, here you can immediately see, that the
capacity of this path is governed by this number because I can reduce the flow along
the arc 6 5 by 5 units. I mean, I will, can reduce the flow along 5 6, which means I can
flow 5 units from 6 to 5. So, 5, and then of course, here the capacity, you, will allow
you to have 5 more here because 5 7, the capacity is 30 and similarly, I can reduce the flow
by 5 units here, I can reduce the flow by 5 units here.
So, therefore, my delta 3 6 can be, path from 6 to 3 is this and the capacity I am saying
is 5. So, I can increase the flow on 3 6 by 5 units and the reduce, reduction in the cost
will be minus 5 into 5. So, a further increase in U T 3 6 possible again, just as we talked
about 1 3, but that cost will go up and the minimum, so we will have to, so essentially,
what is happening is, that when we want to increase the flow on 3 6, we also have to
send flow, the same amount of flow from 6 to 3 to conserve the flow at each node.
But then, see, you want to know and this is a small network. So, we could simply find
out what is the best route and so on. But, when you want to talk of optimally increasing
the flow on 3 6, that means, optimally utilizing the increased capacity on 3 6, then you have
to be able to divert, reroute the flow in an optimal way.
Now, there may be more than one path available from 6 to 3, not the current, of course, the
current tree, there will be only path, which we used for increasing the capacity from 3
to 6. But if you further want to increase the current capacity and you want to say what
will be the minimum increase in the cost by doing that, then you have to find the minimum
path; minimum rerouting path from 6 to 3 or from any, for any pair of nodes ij that you
consider. So, that will be require some work and one
would say, that you have to find the path of minimum cost augmenting, I am calling it
the augmenting path. So, you have to find the minimum cost path and then you use that,
so we will have to do that and later on, I will also, after this I will be discussing
max-flow algorithms with you to finding a maximum flow. So, but that will not consider
the cost. So, we will have to essentially find out the minimum costing augmenting path,
when we want to increase the capacity and so that will, of course we have algorithms
available for that, but right now in this course, we have not considered that.
So, what I am trying to say is, that by increasing the capacity of certain arcs, which are at
there at upper bounds, it is possible to reroute the flow and reduce the total cost of the
flow. So, this is what we have actually investigated
here, as to how we can increase the capacity of certain arcs and of course, we saw that,
that is possible only for arcs, which are at their upper bounds and then, we can increase
the flow on such arcs and reroute the current flow, so that we get a better, better solution.
That means the solution, which has lower cost. So, we go on doing the sensitivity analysis
and of course see, in the earlier lecture, I had talked about changing the values of
the Bi's and we said they are, that if a particular supply went up, then some other demand must
go down to balance the, that means, we were considering the sigma Bi to be 0, we have
to maintain that. And here, when we increase the capacity of a certain arc, then we, and
we want to increase the flow, then we have to be make sure, that flow is conserved at
each node and then doing that we can continue with the analysis as long as we want.
And as I told you that after a certain point when you want to change the optimal solution,
current optimal solution, then, you have possibilities of how you do it, but the cost will go up
and of course, the question would be, what is the best way to increase the flow, that
means, minimum increase you want to have in the total cost.
The max-flow problem and this is also part of your network flow problems. We have looked
at the shortest path, min-cost flow and so on, transportation problem I looked at with
you. So, all those were, you know, problems of allocation. So, this is another problem.
So, here what we are saying is, that you are given a network and you have a source node,
a sink node and these are your node set, this is your arc set and then, you have the capacities,
so low cost here. So, that means, you simply have a source node
and a sink node, then you have capacities on the arcs, you want to find out the maximum
amount you can transport from s to t. So, in this case for example, so let me formulate
the problem, this would be, for example maximize v. Suppose, I denote this as the amount of
flow in the network, so I want to maximize this and then subject to this is my node arc
incidence matrix, x is my flow vector. That means, the component of x are the x ij's and
x ij will tell me how much flow is there on the arc ij. So, ax, and I will explain this,
this is 0 and then we want to say, that x is less than or equal to u and x is greater
than or equal to 0. So, they can and here, when I write this, this means, the d is plus
1 and 0, so, sorry, so and this is minus 1, it should be the other way, minus 1 and plus
1. So, this is the sth row and this is the tth
row, so that means, here if I write the constraint for the, when I write the constraint for the
source node, then actually what I am saying is, that summation xsj, summation over j is
equal to v because you are sending the flow from node s.
So, the total flow, that you send from the node s is v, that will be the net flow in
the network because at every other node you are preserving conservation of flow, because
you see, all other components are 0 here. So, this is not there and then, you have just
wanting, that whatever flow reaches the particular node that should also leave it. So, therefore,
if you are sending nodes flow v from node s, then all other nodes in between are working
as transshipment nodes. So, no flow is remaining at any other, at
any of these transshipment nodes and then the final, this thing is summation x jt minus
this is equal to minus v. So, therefore, I am bringing this to this side. So, this becomes
minus v equal to 0 and this becomes plus v equal to 0.
So, the sth constraint and the tth constraint, you will have a minus 1 and a plus 1 and a
plus 1 follow the 0. So, this is, and therefore, you wanting to maximize. So, you can say,
that this is also your min-cost flow problem, where what will happen is, that all your these
Bi"s are 0; these are your upper bound constraints. So, essentially, your Bi's are 0, your c i's
are, C ij's are also 0 because I am not concerned with the cost, it is only the coefficient
of v, which is 1, otherwise this is the thing right.
Now, it depends on how I look at this problem, where I call it a primal problem or a dual
problem, but of course, so far our convention has been that maximization problem, we treat
as a dual problem. So, let us just look at this problem as a
dual problem and then let me show you what happens when I try to solve the problem by
the primal dual algorithm and it will, they will be very interesting interpretation for
the, so I write this and therefore, what I will do is I will write all the constraints
as less because this is maximization problem, dual problem. I am, I am looking up on this
as a dual problem, so just rewrite this as less than or equal to 0.
In that case, what would be your primal, primal problem? So, here you see, I can say, that
these are the node to, corresponding to the n nodes. So, let me denote the variables pi
i and then, with these it will be v ij's for x ij, v ij and for this w ij. So, right now
I am not treating these as, I am treating these as explicit constraints.
Remember, in the linear programming formulation, we were not worried about x non-negativity,
these constraints, but here, just to make the presentation simple I am doing this. So,
therefore, so essentially, this is minus x ij less than or equal to 0. So, this is ok.
And so, what would be, or this thing on the right hand side, you have only non-zeros here
and the corresponding variables are v ij, so this will actually become minimize summation.
You want to write U ij into v ij and subject to, yeah, if you want to make life a little
easy, I can rewrite here, say for example this thing, yeah, fine, yeah.
So, subject to the matrix here you see this is a I minus I and if you look at the constraints
your matrix has, what I was going to write here, this is a I minus I and then you have
d here, this is all 0, this is your, this thing and you have here x and v. So, this
is a single, then this is the n dimensional this thing, so this is what you have. And
this is less than or equal to, you have 0, u and 0 and I am writing minus I because I
am writing this as minus x less than or equal to 0; this is what you have.
So, in the dual or what will you have, the transpose of this, which will become A transpose
I minus I and then you will have d transpose 0 zero. And so this will be, remember with
this you have the variables pi and with this you have the variables v and then you have
minus, sorry, w. So, you are, because constraints are less
kind, so this will be, what will you have? Yes, now here I do not have any, any constraints
on the sign of the variables because I am not treat, I am treating these as explicit
constraints, so minus x less than or equal to 0. So, v and x both are the signs are not
specified. So, therefore, this will become 0, yes, now I will, why should I say 2, sorry
this will not be 2. But you had non-negativity here, so therefore,
your v and ws are, v and w is greater than or equal to 0, is it ok. Because these constraints
are fewer kinds, this is equality, so your pis are unrestricted, but your v and w are
restricted, fine. So, this can, that means, this actually becomes
minimize summation U ij, v ij, I should have said ij belonging to A, so this is also ij
belonging to A and this becomes A transpose I plus v minus w equal to 0. There should
have been for the d, you see, for the v 1 the thing is 1 because the coefficient here
is 1. So, we have that d transpose pi is equal to 1, this actually is, this constraint is
simply this; this is equivalent to because remember, this is minus 1 and plus 1, so this
is, minus y s or pi s plus pi t equal to 1. So, this is your primal problem and that is
my dual problem.
So, now, when you have this dual problem here, you will define your set I J. So, tight dual
constraints, constraints index set IJ, so I will define, so I J will be all i arcs IJ
for which either x ij is U ij or x ij is 0. So, these are the only possible because the
other set of constraints are all equality constraints, this was remember, flow conservation
equations. So, either x ij is U ij or x ij is 0.
So, then, when you define your restricted primal, yeah, I hope you enjoy this exercise
because I am trying to show you something here and this is restricted primal. See, you
have to add artificial variable here; you have to add an artificial variable here. And
you will only consider the, because here you are considering the column ij, which have
capital IJ, that means, the corresponding row constraint here would be considered.
So, you will write restricted primal would be minimized now, x ij i A summation ij belonging
to a plus let me write to v bar a corresponding to this constraint, yeah, the dual artificial
dual variable. So, v bar a, and therefore, and subject to, so this will be A transpose
pi plus v minus w plus we are writing x, ok, x a is equal to 0.
So, I am just calling this vector from comprising of all the ij's as this and then you have
this also, I can write in the simpler form, which is minus pi s plus pi t plus v bar a
is equal to 1, yes, and you have the non-negativity signs or what, x ij a greater than or equal
to 0 for all ij, remember, because we want to minimize this thing and v bar a is greater
than or equal to 0, fine. And this is for ij, remember these belonging to capital IJ.
So, the ones for which are, the ij's for which the constraints are tight dual constraints,
so that means, I have a starting flow, I have a starting flow in the network, feasible flow
because any x satisfying these constraints represents a feasible flow in the network.
So, then correspondingly, I then find out the tight constraints and corresponding to
that flow, then I am saying, that now you want to look at the restricted primal.
So, this would actually be, as I said, restricted, this will become restricted dual, ok, ok,
hold on where [f l] I call this as the primal, so that was the dual [f l], ok. So, now write
down the restricted dual problem.
So, yeah, earlier I have been simply writing DR, but I think it is better to say, that
the dual of the restricted primal, so the whole thing, DRP is the better nomination
for this thing, I have been writing DR. So, anyway, yeah, I meant it was dual of the restricted
primal. So, what would be the dual of the restricted
primal? Yeah, this is, this was, oh by the way, here I should not have written here.
So, this was x ij and I could have written something else here, but let us see. So, anyway,
I will try to write. So, this will be maximize, yeah, so let us write the restricted dual
now. So, that was the transpose of this. So, actually now what does this matrix become?
This is right now A transpose I minus I and I again because this is whole set of this
thing, this and then, you have D, D transpose and we have a 1 where it is a 0, this is 1
and this is all 0, 0, 0. So, this is what you have and this is and this was our pi,
v, w, x a and I was writing v bar a because 2, 4 and 5, so 3 and 2, 5, so that many you
should have, fine. And now, you want to write the dual, so therefore,
what will happen? This will become A, d then this will be I, minus I, I, 0 and this will
be 0, 0, 0, 1. And then, let me write you some other, this thing f, let me write f,
thus the vector corresponding to, so the flow to the corresponding to x, I could either
use y or f does not matter, f you will have here and we will have a corresponding, yeah,
I should not have used the single v bar a here, let me write something else here, fine,
or maybe we will do this thing here, something like w bar, this. And so, maximize your maximizing
w bar here, you want to write a, write in this way, that is the only one, which has
a one coefficient here corresponding w bar a, I am writing for this in the variable.
So, therefore, that will become max that and so coefficient is 1, and here your constraints
will be all less than or equal to, yes, because remember, we were writing all constraints
less than or equal to kind except for this one. So, maybe, you can say, that this is,
this is all 0 and then here, this is also, yes, and now what are the coefficients?
See, now the coefficients here, these are all 1s, so for these two it becomes 0, 0 because
your v, n, w are not present here in the objective function, it is only the artificial variables,
which are present. So, corresponding to those, this is my I here and so this will become
e right all 1 and this is 1. So, these are your dual constraints and you can correspondingly
have your...
So, therefore, and so here again, because this was all, yes, ok, what would be writing
here in the minimization problem? Remember, I had all equality constraints, so therefore,
this was your, no restrictions on f, n, w bar a, right now I want you to look at this
set of constraints, this problem very carefully. See, the first one says, that your A f plus
d w bar a is 0, which is your flow conservations, which we are anyway having here and this is
remember only for, yes, and then it will tell you f less than or equal to 0. So, f ij less
than or equal to 0 and remember, this corresponding to your v's and then the, we said, that here
for the tight constraints. And since we are in the restricted primal, we went back to,
we said, that here you can only have the corresponding constraints, which are tight for the dual.
So, the v ij, f ij is less than 0 when x ij is U ij; see, this is your IJ.
So, here, the columns for corresponding the, are you considering the columns for which
x ij is U ij or x ij is 0. So, in the dual thing it will become the row and so you are
considering only the those f ij's for which x ij is U i j. And the 2nd set is minus f
ij less than or equal to 0 when x ij is 0. Then, you are saying from here, that your
f ij's will be less than or equal to 1 for all ij belonging to ij, f ij less than or
equal to 1. And then, the final constraint is, that w bar a, is less than equal to 1.
See, what else suggest is that sit down, go through all this formulation very carefully.
So, finally, this is the dual of the restricted primal and sees what is happening here? You
are saying, maximize w bar a, w bar a is less than or equal to 1. Then it is saying, that
for arcs, which are saturated in the current flow x ij is equal to U ij, you can reduce
the flow and so you are trying to find out f ij less than or equal to1. And for arcs,
which are not saturated, which have no flow, which have 0 flow, I can increase the flow
on those arcs and so my f ij is greater than or equal to 0.
So, essentially, the restricted dual problem and my idea of spending so much time on this
is just to show you, that the, the primal dual algorithm has find applications because
you can, you can show, that how useful it is because here I am trying to give you another
interpretation of the primal dual algorithm and which is, it showing you, that the restricted
dual is actually nothing but a reachability problem because you are saying, that your
f ij's has to be less than or equal to 1, you have conservation of flow.
So, essentially, here if I, let me write it somewhere here, yeah, I do not need this anymore.
So, now, as I was showing you, that this is my DRP and the DRP actually now reduces to
reachability problem; DRP is a reachability problem from s to t. See, if I have an arc
here, say for example, if there is my node s is here, either I have an arc from s, actually
we are not having arcs like this. So, if there is an arc with no flow on it, that means,
they are, currently the x ij is 0, then I can increase the flow on it, but the idea
is, the flow has to be of 1 unit, that is why, I am calling it a reachability problem
because we just looking for a path. So, this is b, so there is an arc like this,
then I can use it because I am trying to solve this DRP and the solution would be, that is,
and then from there I will again try to see, if there is an arc here on which if you have
a flow in this direction, then I can reduce the flow or if it again knows flow on it,
then I can increase the flow and this way, you see, just using arcs, I will use the arcs
in the forward direction for which there is no flow currently on the, in the network and
arcs, which have saturated, I will them in a backward way and this way if I can continue
finding and the, I will maintain conservation of flow and then the maximum, if I reach t.
So, finally, if I manage to reach t by these arcs, then that means, my w bar a will be
1 because here you see, this is less than or equal to 1, you are trying to maximize
it and all these constraints will be satisfied here. Also, you see, that these constraints
will be satisfied when I choose w bar a less than or equal to 1. So, this will be my optimal
solution, so that means, the optimal solution for DRP is a finding a path. If this is finding
and augmenting path, see augmenting path, that means, you are augmenting, augmenting
path from s to t, so once I find an augmenting path from s to t, then you know, see, I have,
now I know, that I can increase the flow on the arc on this augmenting path. So, find
the capacity, capacity of this augmenting path, I had explained to you earlier, find
the capacity of this augmenting path. See, we discussed this while looking at the changes
in Bi's and I told you, that the capacity of a path is the minimum of the capacities
of the arc that make up the path. So, find the capacity of this augmenting path
and increase the flow, the flow on this path by that amount. So, by the capacity on this path, by the maximum possible, possible
amount, so I find the capacity I have. So, therefore, the restricted dual problem is
actually finding an augmenting path if one exists and then increase, I increase the flow.
So, we can see, that the structure of the algorithm, that we will use and this is again
simplification of the simplex algorithm and plus the primal dual, this things.
So, if we are basically using primal dual pivots to find augmenting paths, the, you
find out the capacity of the augmenting path, increase the flow, you update your dual solution
and then, you will have your new ij. And then, you will again define a restricted problem,
dual restrict problem and then, you will try to find an augmenting path. So, you will go
on doing this till, because your objective is to maximize the flow in the network. So,
you will go and doing this till you cannot find an augmenting path.
So, essentially, this is the basics algorithm, they are some refinement. So, we will later
on discuss the algorithm, how to actually, without actually doing all this we were simply
trying to find augmenting paths and augment the flow by as much as we can. So, that is
the basic, but the idea here is was to show you, that the origin of all these algorithms
are through the linear programming theory and that makes it very interesting and you
see how it is. So, versatile, the, yes, so now we can again
just try to look at some more theory. So, I need to develop because I have to show you,
that here even though we are using the primal dual pivots, I am not maintaining basic feasible
solutions and so on. So, we need to essentially, finally prove, that the algorithm will be
finite and that we will get an optimal solution here. So, all those things have to be done.
So, if I just simply yes, so let me reformulate the problem. Now, I will write the max problem
again as max v subject to a x plus d v equal to 0 and 0 less than or equal to x less than
or equal to u. I will simply look at this or you want to do this and then this we will
now not treat explicitly. So, I will come back to the usual thing, fine.
So, this is your best and therefore, dual or if, I mean you can keep calling this as
dual or the primal does not matter as, as I told you, that the dual of the, dual is
the primal, so it does not matter, so dual would be minimized. As we said, this is summation
U ij, v ij subject to, and remember, this I will now write in pi i minus pi j plus v
ij, yes, because column here will have two entries, plus 1, minus 1, and then U ij plus
v ij, v ij this will be because now I have taking non-negativity constraints. So, this
will be less than or equal to, sorry, greater than or equal to 0; greater than or equal
to 0. And then, you will have minus pi s plus pi t, so that is it. This is equal to, because
my v is unrestricted, so this is equal to 1, fine, and you have your v ij greater than
or equal to 0. So, I am keeping it, this, this is more simplified because I am not,
not treating these constraints as explicit constraints, fine. So, now, I want to show
you, that a dual feasible solution I can look up on the, this thing as representing cuts.
Now, I introduce to you the idea of cuts, which is the partition of the node set and
then s belongs to, therefore I said, that in this particular case, s bar is a cut such
that, such that s intersection s bar is empty and s union s bar is v and we are considering
particular cuts, where s belongs to, s and t belongs to s bar. So, now, because we are
trying to send flow from s to t, so this is what is it.
So, now, let me define a dual feasible solution, dual feasible solution where I say, that pi i 0, if i belongs to s is equal to 1, if
i belongs to s bar and v ij is 1; if i belongs to s and j belongs check to s bar 0 otherwise.
So, look at this dual and I can claim, that this is the dual feasible solution, why, because
these are your variables. And so, here quickly check, check, check for feasibility. What
are the possible situations? i j both belong to s. If you have i j both belonging to s,
then you have a constraint like this, pi i, pi j, both are 0, v ij is 0. So, this is satisfied
and here this is 0 this is 1. So, this is satisfied, you are done. And v, v ij's are
non-negative, then if i and j belong both belong to s bar, then also both are 1.
So, this is 0, this is 0, again this is satisfied, this will continue to be satisfied because
s is in small as and t is in capital, s bar and this is satisfied. Then, you have the
case, I belong to s and j, belongs to s bar, I belongs to s and j belong to s bar.
So, then, pi i is 0, pi j is 1, so minus 1, but p i j is 1. So, again, the sum is 0 and
so this constraint is satisfied, this will continue to be satisfied this is non-negative.
Then, the final case you can have, that when i belongs to s bar and j belongs to s and
also verified. So, therefore, what we are saying is, that the dual solution, the feasible
solutions are, they are, may be more other solutions I am not denying that, but essentially,
basically all, but basically all cuts are feasible solutions here and therefore, and
if you want to define and of course, I am going to talk about cuts some more later on
because we will spend more time.
But right now, you can just immediately see from the duality theory, from duality theory
we see, that because this is a minimization problem and that is a maximization problem.
So, if you say, that capacity, because if I take a feasible solution, a cut as a feasible
solution, then what is this? The objective function value is simply adding up because
my B ij's are 1 only when i is in s and j is in s bar. So, that means, what we are saying
is, that capacity of s s bar is summation U ij, i belonging to s and j belonging to
s bar, because you have, this is s, this is s bar, you have like this with U ij. So, we
are saying this. So, that will be the objective function value
for this dual feasible solution and by duality theory, by duality theory of LPP, you have,
that capacity of a cut is greater than or equal to the flow in the graph, in the network,
in the, flow in the network and we will further discuss and look at many interesting aspects
of this thing. But first of all, we have said, that the capacity of a cut will always exceed
the flow the network.
So, let me discuss assignment 7 with you, which was long overdue, but we had just finished
discussing the sensitivity analysis for min-cost flow problem.
So, I thought I will give you a few problems to work on, on the min-cost flow problem.
So, the 1st problem is simply, I have given you an incapacitated min-cost flow problem
and you can easily transform it to a transportation problem. Remember, it will be finding out
the shortest path between every pair of supply, and node, and demand point and then, you can
solve it as a transportation problem. So, that is your first problem.
Then, go to 2nd problem, which is now what am I asking you to do here, yes, this is the
min-cost flow problem given below with positive lower bounds, we had not discussed or I had
mentioned to you how to take care of lower bounds if you have, because we were all the
time taking lower bounds to be 0, but now here, you see for example, from 1 to 2 the
flow, that is a lower bound of unit 1, that means, you must in any feasible flow send
one unit of flow from 1 to 2. So, that means what? That means, so the idea
here is, and I have given you, explained to you through a note down below, below this
problem, I was, so I am suggesting to you, that the lower bounds, since you have to send
that much flow, you just send that flow on the arc. So, for example, x 1, I will slope,
flow 1 unit of, 1 unit of flow and 1 to 2 and then, I will, increase that, decrease
the supply at node 1 by 1. That means, the new supply will become 2 units and the demand
at node 2 will become minus 1. Similarly, you have this thing here, the lower
bound from 4 to 5 is 1 unit on the arc 4 5. So, here, I will reduce the supply, that means,
or in this case, of course it is the demand. So, the demand will become minus 2 and because
I am sending 1 unit to 5, so the supply at 5 will become 3. This is the idea.
So, once you do this, then a new problem you can solve as a min-cost, min-cost flow problem
with 0 lower bounds, that is the idea because our algorithm have, we have designed it for
lower bounds being 0 1 can do it, one can modify, but then becomes very cumbersome.
So, this, what I have explain to you here since I am sending a, so what I am saying
here is that I am sending 1 unit from, ok, so b 4 will actually become minus 4 and b
5 will become 3, that is right. So, that is ok because you must have conservation of flow
and since b 5 is going to increase by 1, b 4 must reduce by 4 otherwise the sum of the
b i's will not remain 0. So, right, I should not have said, so this is, b 4 will become
minus 4 and b 5 will become 3.
Problem 3 showing you this min-cost-flow problem, which I had worked out in the 29th lecture,
then the optimal solution I am showing you in the next network, fine. This is your this
and then, I am asking you, yes, so now, there is a few problems, that I am asking you to
look at and so this is sensitivity analysis or post optimality analysis.
So, I am saying, that by how much can c 1 2 and c 3 5 change one at a time, so that
the current solution, yeah, so with respect to this network you are going to now answer
these questions by how much can c 1 2 and c 3 5 change one at a time, so that the current
solution remains optimal.
Now, 1 2 according, so we will have to go back to the diagram here, 1 2 is a non-basic
arc at its upper bounds. So, currently, it is c 1 2 bar is, c 1 2 bar is less than 0
and so we are, I am asking you to by how much can it change so that the current solution
remains optimal, yes. And so, I am saying, that suppose it goes up by delta 1 2, then
you have the inequality c 1 2 plus delta 1 2 minus w 1 plus w 2 should be less than or
equal to 0. It should remain non-basic and the optimality criteria should not be violated.
Then, c 3 5, 3 5 is what? 3 5 is a basic arc. So, here, once it goes up by delta 3 5, then
remember, the other nodes, the other node potentials will also change and so you may
get an interval for delta 3 5 within which if your delta 3 5 varies, then your current
solution will not, will remain optimal. And then, you know how to...
So, then again in the problem 4 I am asking you for 2 5. 2 5 is also a basic arc and I
am saying, that here this goes to, this changes by delta 2 5 and again I am asking you to
find an interval. So, what is happening? 3 5 is also basic, yeah, so again, I am asking
you to do it for 2 5 also. 2 5 is a basic arc and I am asking you to find out the interval
for delta 2 5, so that the current solution remains optimal.
Then, path 3, path 3 I have changed b 1 to b 1 plus delta, that is the, and b 4 to minus
delta because b 4 was a transshipment widely since, so that, so sigma b i some remains
0. So, now, here find an interval for delta,
so that the current solution remains optimal. So, just what will be the feasible values
of delta, so that your current solution remains optimal? So, therefore, you have to send try
to send along the path from 1 to 4, you will have a path in this spanning tree, current
spanning tree and just see how much amount you can send on that path and that would be
your feasible interval for delta. In 4 I am saying, that b 1 hat has changed
to delta 25 plus delta and b 2 hat is minus delta and this call case also determine interval
for delta, so that the current solution remains optimal.
Then, I am asking you show one iteration of the dual simplex algorithm, where delta exceeds
either of its limits in 4. So, here, now I want you to consider changes in delta beyond
this feasible interval and then you will have to use the dual simplex pivot to find out
a new optimal solution. Then, the part 5 which I just discussed with
you relates to change in capacity, capacity values. So, u 1 2, u 1 2 is a non-basic arc
and the, I am saying, that the capacity goes up to 20. So, the current capacity may be,
check whatever it is and since c bar 1 2 is less than 0, I am reminding you again, that
the increase of flow on arc 1 2 will improve the cost. Thus, the current solution may long,
may no longer be optimal, obtain the new optimal solution. So, the new optimal solution, yeah,
we do not know by how much, I think the capacity for, let us just verify for c 1 2. For arc
1 2 the capacity is 50, so if I am raising it to 20, then we have to see, can we by sending
5 more units on the arc 1 2, can I send the 5 more units from 2 to 1, that is what I have
to find out. Then, that will be feasible if I can, that means, the capacity of the path
2 to 1 and which is in your current optimal solution, the path is from 2 to 1 is 2 5 3
1 and you see, that the blocking arc is 3 5 because there is no positive flow on 3 5.
Therefore, I cannot reduce the flow on, I cannot reduce the flow, and so that the capacity
of the path 2 to 1 0. So, therefore, the current solution will not remain optimal.
If you increase the capacity of the arc 1 2 and so, you will have to then drop the blocking
arc, then in the cut find the eligible arcs. And from among the eligible arcs choose the
one, which has a lowest relative cost and increase the flow and see, if you can increase
the flow, flow by 5 unit, if not and again you will find a blocking arc and again find
new eligible arc and so on. So, you will continue with that, so I want to give you to work out
the details what we discussed in the lecture. So, that takes care of your and then arc 2,
5 is a basic arc, yeah. So, whatever I have just finished in last part, arc 2, 5 is a
basic arc at its upper bound. Suppose, u 2 5 deceases to 10, this I have not discussed
in that lecture, but now you can surely, you have all the tools to handle this problem
also. So, now, u 2, 5 is decreased to 10. So, the current solution is no longer feasible
to obtain an optimal solution using the dual simplex pivot on the current optimal solution
because the current solution has becoming infeasible and so see, if you can handle this
part also. So, hope you will enjoy doing this assignment
sheet.