Tip:
Highlight text to annotate it
X
So, I had point out in the last lecture that there was a little error in the computing
this number, so I have just done the last 2 tableaus again, this is the inverse
tableau presentation of the LPP algorithm for the parametric cost problem.
So, the problem we were discussing in the last lecture, that one continuous here; so
the correction was somewhere here, so just make sure with the tables in the last
lecture you compare and make the corrections wherever necessary. So, I think we had almost
completed the problem. So, here in this case, you see for the positive
once the ratios are 6, 6 and the eighth number is missing somewhere, this part we had done
already in it was for x 6,
so this tableau shows you when x 6 has been brought into the basis, so this number was 48 and
minus 6; so when you take the ratio it will be minus 48 by 6 which
would be 8. So, this tableau shows you the computation for the after x 6 has been brought
into the basis, so this you are pivoting on 2.
So this is for your basic columns, so any way for x 6 the upper ratio would be 8 and
the lower ratios are 6 for the mu and you pivoting on this, so after this when
you do the pivoting on 2, so you will be dividing by 2. So, this tableau shows you after you
are pivoted on this element; so here in this case the interval was 6 and
8, so the characteristic interval for the corresponding basis x 5, x 4and x 3 when these
are the basic variables the corresponding characteristic interval for mu is 6
comma 8. And then, x 6 has to come into the basis,
this is the pivoting element, you do the pivoting, you come back here, and let us see what are
the ratios, I have computed
them for you minus 66 upon 8; so that become 66 upon 8 which is equal to 8.25. And for
the positive ones the ratios are 30 by 4 which will be 7.5 and 24 by 3
which is 8; so you see this is your lower because you take the max of this, and there
is only one entry here; so that is only one other wise you would have more
than one you would have taken the minimum of the 2, whatever the entries here.
So, therefore the next characteristic interval is for you 8 and 8.25 as you would expect,
this lower and this upper should match. Now, after 8.25 you see we can
now make you of this fact that, you started with your basis, your starting basis was x
1, x 2, x 3; this was your starting basis. So, therefore what figures here is your this
corresponds to x 1 now, this whole column corresponds to x 1, because you started with
your columns for x 1 here and
after all the iterations, so actually this shows you the column for x 1, this shows you
the column for x 2 and this shows you the column for x 3.
And, so from here you can see that for lambda for mu greater than 8.25, this will be a candidate
for coming into the basis, your column a one will be a candidate
for coming into the basis, but corresponding entries here are all less than 0. So, therefore
this mu greater than 8.25, x 1 is to become a basic variable, but y 1 is all
less than or equal to 0. In fact it is all less than 0, so this implies problem is unbounded for mu greater than to 8.25, because it has to
be an open interval. For 8.25 you have already have a basis which
is optimal, which is your x 5, x 4 and x 6 are the basic variables, and the starting
tableau is not there, but you could
have checked that we started with, I think we started with the six.
So far, the characteristic intervals that you have obtained are this 8 and 8.25, and
then you have the open interval 8.25 to infinity. And for mu less than 6, if you in
the original tableau your A 4 was less than or equal to 0, whatever it is; so this would
imply original tableau A 4 and C 4 minus Z 4 also less than 0. So, this implies
the problem is unbounded again for mu
less than 6. So, therefore you have the complete partition
of the real line is as follows, so this is minus infinity to 6 open interval, and 6 to
8 is a closed interval 8 to 8.25 is
again a characteristic interval which is closed, and then you have the open interval 8.25 to
infinity.
See, while showing you the break up for the real line we had computed all the intervals,
but while writing out the final break up for the real line, I should have
written minus infinity 6 and then we had also computed this, which I did not mention in
the lecture; so this was a single turn. And then of course we recorded all
the other intervals, which is 8, 8.25 and finally 8.25 infinity. So, the real breakup
that means when you add up all these intervals you would get the breakup for the
real line for minus infinity to infinity. So, the single turn the interval containing
the single element 6 got left out, so kindly read this as the real breakup of the real
life. As occasion arises we will also see
that we may need such situations after we have solved a particular problem, so we will
be coming back to it sometimes again.
So, now I want to start a new topic and that is you know min-cost flow problem, the min
is short for minimize; and you will be surprised how vast the area is where
the problems arise, which can be formulated modeled as min-cost flow problem.
And then, we will look at the special cases, I already look at one of them, it is up to
formulate the general min-cost flow problem, the shortest path problem that we
discussed is also a special case and I will show you later on how it is, so just a few
terminologies and then we can start defining and formulating the min-cost flow
problem. So, the idea is you have G is V and A, so
here again for short path problem I also I took the directed arcs, directed edges, which
we call as arcs; so G is V A where
V is the node set. So, I will just redefine and A is the arc
set that is A is the pair, ordered pair is i j, ordered pairs for i and j belonging to
v. So, that means you have a node i and you
have a node j the idea is, you have a directed arc that means you can go from i to j, this
is the idea and this is the ordered pair i comma j.
So, we also have concept of undirected edges which are called edges, so edges were simply
i and j that means you can go from i to j or j to i no direction is
specified, and we can have a situation where you have some edges are directed and some
edges are not directed, so it will be called a mixed graph.
So, any way usually when you have the direction set between all pairs of nodes, then you say
that g is a directed graph, when the edges are all directed; so edges
implied no direction in the edges are directed, all the edges are directed.
You can read it as directed, G is a directed and another word for a directed graph is network,
so it is a network. So, network implies that there is direction from a
node to another node, because networks are basically considered in connection of flows,
and so you always have directed edges in a network; so I will be using
directed graphs and networks synonymously, sometimes I may refer to it as this and so
on.
So, let me first define the problem, so a min-cost flow problem can be formulated as, and I will define the terms as we go along, so
minimize z equal to summation
c i j, x i j; where i j is your edge in the directed graph, subject to summation x i j,
summation over j minus summation x k i, summation over k is equal to b i. I will
define all these terms, and then we have a capacity constraint also, let me write this
as less than or equal to u i j and here let me say that this is called each node, so
i belonging to v. So, let me specify the thing; so b i can be
a positive or a negative number and b i greater than 0 indicates the amount of certain of
commodity of an item available,
it could be the capacity. See, you may have a telephone exchanges and b i may denote the
capacity of the phone calls at particular time the exchange can handle.
As I said, in this course probably one cannot adjust give you all possible situations where
these problems can occur or where the problems can be formulated as
min-cost problem, but hopefully you will get a good idea by the time we finish the various
special cases and so on of this class of problems, and of course I will tell
you why we are discussing it in the linear programming course, because as it is you see
first of all that the formulation is a linear programming problem, and then
there will be many good other reasons for doing it here.
So, let see b i positive indicates the amount of an item of available at node I, and b i
less than 0 would indicate the demand for the item at node i. So, obviously
what concept is that positive quantity is available for supply and a negative number
indicates that things are being demanded or required at that particular node.
Then, we refer to, as you can guess that your x i j is the decision variable, and it tells
you decision variable regarding the amount to the sent along arc i j. So, you
are using arc i j, if you are using arc i j then x i j tells you, that means x i j positive
value will tell you the amount that has to be sent on the arc i j.
Then, u i j is the positive number and denotes of capacity of arc i j, and you can immediately
related to, see for example if your sending same things by trucks and
the capacity of the truck that there is certain amount beyond which you cannot sent the items
through the truck or the railroad you hire a carriage that capacity or
telephone exchange as I told you for a particular arc, again the telephones lines are built
for certain capacity. They cannot handle unlimited amount of volume
of traffic, so railroads and so on. All these situations you can figure out, so it is a
very natural constraint on the
system in the variable. Then c i j of course is the cost, so c i j is the cost of sending
a unit of item on along arc i j, finally these are the arc flow conservation
constraints, which for shortest path problem we wanted, see the b i's were only 1 and minus
1. For the b i was 1 for the node from which you wanted to begin your
shortest path, it was minus 1 for the node which was to wish the shortest path to be
found, and at all other nodes were intermediate nodes in the sense that they
were only being used for the constructing the shortest path from the starting node to
the ending node, so they were all zeros. So, we have already looked at these flow conservation
concept and so here all it is saying is that from a particular node i, if b i is positive,
then b i is the amount
available at that node. So, certainly you do not want to be sending
more than the item available at a node and similarly, at a demand node you would want
to required amount to be a set
to that point. While formulating this min-cost maximum problem, in the beginning not mentioned
that sigma b i should be equal to 0, later on I did say that of
course, this is a necessary condition that all the b i's must add up to 0. Now, I am
just inserting it in the beginning of the formulation of the problem.
And as I told you, that when arc leaving, if an arc leaves a node it has a positive
sign, if an arc enters the node it has a negative sign. So, it is possible that node I
may be receiving some amount and then it is sending some amount but the net amount, so
whatever it receives that is the amount beyond b i is positive.
What we are saying is that you may have some amount coming to node i, that means the amount
will become more than b i, but then you will be sending amount to
other nodes. So finally, the flow conservation equation says, that the net amount that node
i handles should not be more than b i, whether b i is positive or
negative, even if b i is negative then that means, it will be receiving amount and it
will be sending out, so this tells you the total amount which is being sent from
node i, and this tells you the amount which is coming from nodes like k to node i and
that is the minus thing. So, then the net amount that node i handles
should be equal to b i, whether b i is positive or negative. So, these are the flow conservation
equations which we
always maintain and therefore we maintain a feasible solution. So, now we need to know
have a few more definitions, for example I did define a path for you, but
let us do it again in this course.
So, first let us define a path, a path from node i to node j and this is a sequence of
arcs i, k 1, k 1, k 2 see a constitutive arcs or we can say adjacent arcs i to k 1 and
k 1 to k 2, because that is a concept of a path and similarly, from here it will be k
l to j. Some people like to define arcs and nodes,
but I want to keep it simple; so you understand that from i to k 1 then k 1 to k 2; so the
node part is quite clear fine
sequence of arcs. Then we say that path is simple if no node is repeated, so path is
simple and that is important for us, because some time that means you are not
coming back to a node and then going out, so let me give you an example.
So, let us just consider a directed graph, so you have a directed graph here; so for
example a simple path would be something like 1, 3, 3, 2. I should have set
something more, now that I am giving the example I realized that I have said things, so 1,
3, 3, 2 then you can have 3, 4 and then 4, 6; so simple path from 1 to 6.
I should have said here sequence of arcs, let me add here where either k i plus 1 or
k i plus 1 k i is belongs to A, so it will crowded, but I think you can read it; so
what I am saying is that it not necessary when I am giving you a sequence of arc, it
is not necessary that each of the arcs is in A it can be either way.
So, the concept of path is it will general here, because what we are saying here is whereas
for the shortest path when we were looking at a path it was directed
path, because you wanted to actually go from 1to 6, and so for example it was 1 to 2, 4,
4, 6 So, we were trying to find out paths which
had the same direction, all arcs at the same direction, but here path will more general,
and so for example 1, 3 then I am
taking 3 2, 3 4 that would not be correct, so this would not be correct 2 3; so this
would not be 1 3, 2 3 3 4. I would have to make it 2 3.
So, writing an example helps, so it will be 1 3, 2 3 then 3 4 that is also not correct,
so let me take it to be 1 2; so simple path would be 1 2, 2 3 then 3 4 I can take
and 4 6; so this is a simple path from 1 to 6, not simple path, but if you take the path
that means 1 3 and then 3 4, 4 2 and then if I add 2 3.
So, you see 1 3 3 4 4 2 2 3, now the node is being repeated node 3 is repeated, and
then I can go from 3 to 5 and 5 to 6. So, the path is not simple, because you are
repeating a node, you are visiting a node again whereas here I am not visiting a node
again, 1 2, 2 3 then 3 4 and 4 6; so no node is being repeated that is very
important simple paths. So, path is simple. Now, if I want to define a cycle or some people
call it a circuit, so cycle is a simple path in which the first node and the last nodes
are the same, so cycle or a
circuit is simple path, for example here it is very simple 1 2, 2 3, 3 1 this is a cycle;
so they are so many obtain 12, 2 4, 4 5, 5 3, 3 1 any of them.
So, the last node and the first node are the same in a simple path, it becomes a cycle.
Then we also are interested another configuration and they are many more
other things which we will not need right away, so whenever we need them I will try
to define, but right now i just want to begin with the basic definitions, so that
we can start with the algorithm, so this is a tree.
So, now you have a cycle and you want to look at, you can also have a definition called
subnetwork or a subgraph. So, a subgraph which we mean that it is a
subgraph, so you want to call it G prime, this will be V and A prime, that means it
is has a same node set as G but, the arc set may be subset of this, where A prime
is A subset of A this is important, so it becomes a sub network.
So, this is good enough for us, sub network or a subgraph. Now, we want to say that tree
or a spanning tree is a subgraph, so everything is being define with respect
to the original graph G which is V A. So, a spanning tree is a sub graph with no cycles.
So, for example here, remember a sub graph has to has the same node set, so we are wanting
a subgraph, but with no cycles; so that means here if you remove the
edges which are arcs which are making cycles, then so for example I would remove this, this
can be of course were not unique; so they can be so many spanning
graphs. So, if I remove this, then what happens, you
have a cycle; so if you remove this, this is a subgraph with no cycles. No one more
thing we should have defined there
is still a cycle here, so this is not, because this would have been a cycle but 2 4 and 5.
This would be a spanning tree, but then another concept which i should have
defined and that is connectedness. So, let me talk about connectedness, I will keep that
as it is right now. Connectedness, so right after a path, I should have
defined this thing after a path. A graph is connected, if there is a path and
remembers when I say a path I mean a simple path, if there is a path between every pair
of nodes of G; so
connectedness, that means I should be able to connect two nodes any two nodes of the
graph via a path. So, what I drew for you was a connected graph,
but for example if I have something like this, and I have a single term here, you may have
this does not matter, but
still this graph is not connected, because I cannot in any way reach from 1 to 5 or from
any node here 2 to 5.
So, this is not a connected graph, so we want connectedness; so therefore what I have to
say here is the definition is not complete, definition has to be a connected
subgraph with no cycles. So, that is very important here, one has to add is a connected subgraph with no cycles is a spanning
tree.
Because, see here we had this edge, does not matter which direction it is, suppose you
consider this, then if I had not written the word connected, I could have had
something like this. I could have had a subgraph, so there I had to be no cycles; so I will
have this, then I could have 4, 6 and 5, no cycles; so this is the subgraph,
because all the nodes are there, the 6 nodes are there and no cycles are present; so that
definition was not complete, I have to say that it is a connected subgraph
with no cycles. So, what I drew for you here, finally this was it.
So, here you can see how many edges, arcs 2, 4 and 5, 6 edges; so this is the important
result which we will not prove, because one requires a little bit of more
rigour, so we will simply take it as it is and we will use this thoroughly.
So, what is the claim, claim is if cardinality of these n, then any spanning tree of G will
have exactly n minus 1 arcs, by the way what I am defining is all also valid
for a non directed graph, so this is a spanning tree will have exactly n minus 1 arcs, if
the cardinality of the nodes that is n and using this then we can do lot of
interesting things. So, now let me just put a few words; see of course as I told you many
situations can be modeled as min-cost flow problems, that is one important
reason why we look at them and secondly, why I am looking at these problems in the linear
programming course is that I want to demonstrate that if your problems
have special structures, then simplex algorithm exploits them beautifully and we will see
how it simplifies the algorithm, because the problems have special
structure and why do i c s problems have special structures, because you see the constraints
are this kind, and while discussing the shortest path problem, I showed
you that when you write a node arc incidence matrix which will be the coefficient matrix
here, when on this side you have nodes and you have arcs here.
Then, every column will have only 2 nonzero entries and they will be 1 and minus 1, so
this I had shown you when we were discussing the shortest path problem
and I talked about the node arc incidence matrix. So, this special structure really
simplifies the simplex algorithm, and in fact you can the way I will solve problems
for you. I will actually without bothering to show you give you the tableau and I do
not need to, I will actually show the progress of this simplex algorithm on the
graph itself, and you can see how things are happening.
So, therefore that is why we said that linear programming is the simplex algorithm, so versatile
that you do not need to with keep on adding, talking about its
property and as the thing there is the course is unfolding, you see that you can really
do many things with the simplex algorithm. And so we will define the concept
of base and what a feasible solution here would mean and so on, so I will continue defining.
By the way, I should have sets also, that here very important condition is that sigma
b i is 0. This is very important that it is a balance, because when I am saying
flow conservation and I am saying that whatever is available should be also, since we have
the quality constraints it is very important and we will show you why,
because if you some up this thing respect to i, then you see that this sum and this
sum will be exactly the same, so sigma b i must be 0. So this is the necessary
condition for feasibility of this problem, therefore a feasibility will also not be a
concern here.
We will discuss assignment 5 now with you, which is based on the portion of sensitivity
analysis and parametric programming that we discussed in the last few
lectures. So, the first problem is a product mixed problem, that means have given some
raw materials and the manufacturer has to manufacture certain products
and he has to maximize his profit, so because we want to formulate the problem as a minimizing
problem, so I have taken minus of the objective function, and so it
is a minimization problem with minus cost coefficients, and then the raw materials available
are; there are three different raw materials and the availability is given
to you of these raw materials.
And, now x 5, x 6 and x 7 are the slack variables and corresponding to the 3 inequalities, then
B is a optimal basis and i have given you the corresponding; so I
have told you that the variables x 1, x 3 and x 2 are the basic variables, that means
your basis will consist of columns A 1, A 3 and A 2 and then I have given you
the B inverse.
Now, you have to answer these following questions which are concerned with post optimality analysis,
and I would like you to support your answers with good
proper reasons. So, for example, in the first part, in the part a I am asking you to, if
you know that you can increase the availability of one of the raw materials,
then which one will you choose and you know that the person is trying to maximize his
profit the manufacturer and the dual variables give you the prices of the
raw materials. So, therefore you can now figure out how to
answer this question, what I am asking you is, you have a choice of increasing the availability
of only one of the
materials by 1 unit, which one will you choose. So, the rate of increase of the objective
function value is given by the dual variables. Part b says, what is an optimum feasible solution,
what is an optimum solution if availability of b 2 is increased by 31 units, because optimal
solution implies
feasibility. If available of b 2 is increased, so right hand side the value of b 2 has increased
by 31 units. I want you to find out the optimal solution, either the
current solution is optimal or if not then you have to apply dual simplex algorithm.
Part c, ask you to find out if total of ten units of third raw material can be made available
that is four units more, already 6 are available; so 4 more are available.
What is the maximum amount you can afford to pay for it? So, kindly think about it,
again the answer will come through the dual variables, so what is the
maximum amount you can afford to pay for it. Part d says, that obtain the interval for
c 1 such that the current solution remains optimal for all values of c 1 in that interval
and do the same for c 2, c 1and c 2
both turn out to be optimal intervals, may be you can also on your own do it for some
non-basic variables also the price ranging.
Part e says, that if x 8 denotes the number of new product that the company has the option
to produce at rupees 10 per unit, it should have been minus, because
the objective function I am writing as minimization, so therefore this should be actually minus
10 per unit. So, I have taken care of that in the problem.
So, actual cost is 10, but the profit is 10 rupees per unit, but in the objective function
it will appear as minus 10 x 8. Since, we are minimizing the objective
function, so then let A 8 transpose I am giving you the column this is parameterized, it has
a parameter lambda appearing in it, that means here we are considering
changes in the technology coefficients, and what input output coefficients you can call
at what value of lambda will it become profitable to manufacture the new
product. So, this remember when you add new product
that means you adding a new column you add a new constraint to the dual problem, so again
you can try to answer
what the value of lambda would be for which or what it can be more than one value of lambda
for which the current solution will remain optimal, that means you
have to actually check for dual optimal dual feasibility. In f you have to find out the
range of values of theta for which the current solution will remain optimal, if
the input output coefficient A 2 2 is changed to A 2 2 plus theta again here I am trying
to A 2 2 corresponds to basic column and therefore you will have to do a
little bit of work to find out the range for theta, so that the current solution remains
optimal.
Problem 2; now, here you have a parametric right hand side problem and this I have already
discussed in my lecture what I would like you to sit down and write it
down properly, so you have to say that you have to answer the question that if the problem
is infeasible for a particular value of lambda, which is lambda naught,
then you have to show that the problem will either be infeasible for all lambda less than
or equal to lambda naught or for all values of lambda greater than or equal
to lambda naught.
I have been emphasizing for you that either infeasibility or unboundedness will always
be valid for an open interval, and so I want you to prove it here. Question 3;
I have design specifically, I mean I took some time to come out with the numbers of
course the calculations may still prove to be a little cumbersome, but anyway
in the third problem I have given you, it is a parametric cost problem.
So, the c row is the top one c star is the row below it and its 2 constraint problem,
so objective function is to be minimized. Solve the problem for all values of the
parameter mu starting with the basic feasible solution consisting of the basic variables
x 1, x 5; that means your starting basis will consist of the columns A 1 and A
5. So, I wanted to actually design a problem
in which gives you a basis which is not optimal for any value of mu it was the idea, and so
finally I could do it. And in
this you will see that when you come out with the basis, and when you compute the lower
value for mu and upper value for mu, the lower value will be higher than
the upper value. So, the characteristic interval is empty corresponding to this basis.
So, now you have to proceed from here and what will be the idea here, that the lower
interval is bigger than the upper interval, so where will you begin, you will
begin with the upper interval, because the corresponding when the value is less than
the upper interval value say mu upper bar. So, when value of mu is less than mu upper
bar, your corresponding variable this relative cost will become negative and you can proceed
with the values of mu less
than mu upper bar ,from there you will begin and then you will be able to, because it will
not help you to choose the lower thing, since the mu lower bar is higher
than the mu upper bar; so you should proceed with the mu upper bar, so start with mu less
than mu upper bar, and you should be able to continue and then get a
full partition for the real line. So, of course this is not the end of problems
that you can work out on sensitivity analysis and parametric analysis, these are only representative
problems and I
hope that you will try out many more on your own from many other text books and I have
already the reference books, I have already mention to you in the
beginning, and all these books have lot of problems for you to work out and get a good
feeling for the post optimality analysis that we have discussed so far.