Okay guys, so this is discrete optimization, linear programming.
Okay. And this is part four.
Okay? So this is going to be a transition
lecture. Okay?
Between the basic you know, simplex algorithm and duality theory, which is
this beautiful marvelous thing that you need absolutely to know baout, okay.
This is essentially introducing a bunch of notations, okay, of what we have seen
already. Re-proving, proving some of the results
we saw, we've all proved before, using that notation so you don't have to get
familiar with yourself, and then introducing this tableau.
Okay? Which is really a very useful tool when
you actually implement the simplex algorithm, or you do things by hand to
actually understand them better. Okay?
So, this is a lot of notations today, I'm trying to make it easy for you, but this
is also very useful is you start reading papers, if you start reading books You
need to understand, you need to understand some of these notations.
Okay? It's all trivial, but it's kind of
boring, right? and it's kind of confusing.
So, this is essentially a system of linear equations.
Okay? And one of the things that we need to do
when we talk about matrix notation, or the table, is to basically view this as a
big matrix. Okay?
So, our Yeah. So essentially what you see here, you
have all the coefficients of all these variables.
You can view them as a matrix, right? So first column, second column, third
column and so on. So there are as many columns as there are
variables. There are as many rows as there are
constraints. And these guys are going to be the right
hand side, so we're going to see that you know, as well, inside the tableau at some
point. Okay, so typically what we do when we are
doing the simplex algorithm is that we have the basis, you know these are going
to be the basic variables. The other ones are going to be the
non-basic variables. All of this you have seen, mastered, you
love this thing, hopefully, so the basis here is variable three, four, and five.
Sometimes we've gotta call this guy, the matrix there, the basis as well.
You know this is kind of abusing notational language.
Okay, so remember in most of the other lecture work we were doing is basically
taking the basic variable, isolating them, they become part of the left side.
Okay. They are expressed in terms of the
constant and then the rest of the non-basic variables.
Okay, and so that's what we did. Okay, so once again, you can view this
thing here as a matrix. It's part of the big matrix here okay,
once we do some operation on it. And this is kind of also a part of the
matrix, but which is very nice like, it's like, you know, a diagonal matrix.
Okay? So I'm going to show you that in detail.
Okay? So essentially you can re-express the
whole thing here in terms of basically two matrices.
Okay? And then some you know, vectors, call
them vectors, okay? For the variables, for the basic
variables and the non-basic variables. Okay.
So the basis is always going to be, you know, in general, well yeah.
So, so let's forget, so this basis here is a very nice form, but it's not always
going to be the cases. But let's say this is the part of the
matrix associated with the basic variables.
You see the basic variables over there. This is essentially the part of the
matrix which is associated with that. Okay.
In this particular case is 1, 0, 0, 0, 1, 0, 0, 0, 1.
Okay. And then the rest here is the part of the
matrix when you see this big thing over there.
Right. Associated with the non-basic variable.
Okay, which is x, x1, x2 and then x6 over there.
Okay? So you see the first vol, the first basic
variables there, you know, Well the first non-basic variable there,
x1. It has, it has a column which is 3 to 1
and that's the column that you see here. Right?
So 3 to 1. Then you see the next variable there, x
2, okay so the column is 1 0 0. Okay, this is the column that you see
there, 1 0 0. Okay?
And then finally you have the column for x 6, which is basically 0 1 1, okay?
And you see 0 1 1 there. I mean, you see it, I don't see it, I
can't tell you the screen that I'm looking there, is so tiny and is
reversed, there is no way I can see anything.
And so, but this is very interesting and exciting, right?
And then you see the right column there which is basically the coefficients that
you see there. Okay?
So, this is basically the, the matrix notation, and then we're going to use
some, you know, nice algebraic notation for you know, representing this.
This is A Substraited by B because this is associated with the basic variable Xb
the basic variable this is An that's a part of the big matrix which is
associated with the non basic variable these are the basic variables and this B.
Okay so once again the formula that I'm always going to tell is we have what.
Ab times Xb plus An times Xn okay. is equal to b.
Okay. So this is basically reformulating this
entire system of equation, as a formula about, you know with matrix notation.
Okay? So in a sense, everything that I told you
last time can be summarized in this particular form, okay.
So we have a system of equations A x is equal to b, okay.
Now I have to find a basic feasible solution, how do I do that?
I take a set of linearly independent columns in, in the matrix A, okay?
These columns are called A-B. These are columns, the columns of the
basic variables. And then I start re-expressing these
basic variables in terms of the non-basic variables.
So I have these first constraints that I've just described on the previous
slide, right? A b times x b plus A n times x n is equal
to b. Okay?
Now I want to isolate the, the basic variables, okay?
So I have A x. You know, ABXB on the left hand side.
And on the right hand side what do I get? I get B minus ANXN, Okay?
So once again, basic variable, non-basic variable.
I still have a matrix there, Okay? So, if it's not you know, the nice
diagonal matrix, unit diagonal matrix, I have to basically get rid of it.
So I basically compute its inverse, you know, multiply you know, the inverse by
the matrix itself, which is basically the diagonal matrix that I wanted.
But then on the right hand side, you see basically the inverse of the basis.
A b minus one times b this time, and then you see A B minus one times A N times x
N. Okay.
And these, and these basically give you the expression of the basic variable in
terms of non-basic variables. Okay.
Now when we do these operations you know, in the equation before, what we get is we
get a new set of right hand side b prime, which is equal to this Ab minus 1 times
b, okay? That was you have there and then you get
new coefficient for the non-basic variables, which you know, I'm courting
you here is. And prime, which is basically that's a
type of the matrix which is associated with the non basic variable.
Okay? So, so this is essentially a basic
solution, right? And it's going to be feasible if all the
b primes are greater than 0. So, this is how I compute A basic
feasible solution, right? So, I'll select this, you know m linearly
independent column. I'm re-expressing the basic variables in
terms of the other one, and I'm testing feasibility here, right?
So, same thing as we have seen in the previous lecture, but just in matrix
notation, okay? Now, the matrix AB is also called a
basis. As I told you, you know, we call basis a
lot of things, okay. So, in a sense, linear programming, okay.
So, this is the, the statement of the problem.
You minimize cx, you know, we've the constraints Ax equals b, okay.
And then you get this basic feasible solution here which express xB in terms
of the non basic variable using this matrix notation.
Inverse of the basis times b minus, you know, inverse of the basis.
Inverse of the basis times ANxN, okay. And now one of the things you may ask is,
oh, what is the cost, because I haven't covered the cost yet.
But the cost we can express in exactly the same fashion, all right.
So we can see set at cx equal to what, cB times, you know, xB.
So these are the basic variables. And then cN times xN which shall, done on
basic variable. Of course once you have that well we know
value of the xb the the basic variable so we can reexpress them in this in some
sort of this equation and that's what I'm going to do in the next equation okay so
take a deep breath because that's going to be.
Ugly formula, okay, but very simple. So what we know is that we want to
compute CX, okay? So you have CX times B plus CN times XN,
okay? Now we know the value of XB, this is this
ugly, you know, inverse of the basis time B minus inverse of the basis time AN time
you know, X, XN okay, and that's what we just did here, okay?
So we just substituted inside the val, for the value of XB, okay?
So you see this is the second equation, okay?
Now I invite you to look at the third equation which is basically a simple
distribution. A simple algebraic manipulation there.
So that I can isolate, you know, the constant term and then the term which is
only associated with the variable the non-basic variables.
Now the next line, actually the next two lines, so what we do here is interesting,
alright? So when you look at the, when you look at
what we have done so far, you see this expression which is multiplying,
multiplying the non-basic variables. So, so, so essentially this expression is
in terms of the nonbasic variable, using also you know, the notation cN and AN
which is part of the matrix which are used in, for, only for the nonbasic
variables. What I would like is to have this
expression, but to re-express in terms of the whole overall matrix.
And that's what I'm going to do in the next two lines.
Okay? The first thing that I do is that I say,
okay, so this is about cN And A N, I want to have the same kind of relationship,
but for the cBs and the ABs okay? Because if I do that then I can merge the
cB and the cN, the AN and the AB, and I have the global matrix and the global
cost. And that's what I'm doing here, I'm
adding a term for the cBs. Okay?
And this term is essentially zero. Why?
Because I have cB over here, okay? And then I have cB times the inverse of
the basis Times AB. Okay?
Now, the inverse of the basis, you know, time, times the basis.
That's going to be the diagonal matrix. So, what I get here is basically cB minus
cB, which is 0. Okay?
So this is why this term is 0. But now when I basically re-express these
two terms together, I get this beautiful, really beautiful, truly beautiful
expression, which is what? Which we see, you know, no basic
variables, no non-basic variables is the entire coefficient, that row of
coefficients, Okay? And then I get one CB here, you know,
times AB minus 1, Okay? And then I have the real matrix, A.
Right? So in a sense the only thing here which
depends on the basis are basically this expression in the middle.
And this is actually very important and you'll see why.
But the c here is a real, you know, doesn't depends on the basic or nonbasic
variable, and you have the real matrix A, okay?
So this is essentially all you can re-express cx, cx is equal this
expression. Where you have the value of the constant
there, you know, and then you have basically the non-basic variables over
there. You know, we try expressing sums of C and
then A, and then these things. And this thing, we're going to denote
them pi. And this pi, so very important.
Okay, you'll see them all, you know, all over in the next two lectures They are
called simplex multipers. So pie is equal to Cb times inverse of
the bases. Okay.
Now sometimes I'm going to say P because Pie in Greek is P and I'm going to be
confused. But you know i'm trying to pie all the
time but in Greek is P so I'm confused alright.
so, but this complex multiplier, I have this value which is very important, it's
cb times the inverse of the bases. Okay?
Now so this cost here, cx, I can reexpress in terms of these simplest
multipliers, as simply Pi B minus C, minus Pi A times X, okay?
So, this is, this, this equality is very nice, because no, it's only expressed in
terms of this simplex multipliers, and it becomes this beautiful thing, you know.
C minus...so, C minus Pie A over there. And this is very important.
Why is it very important because at optimality we know that we have a
property of these guys. Right?
What is the property, do you remember that beautiful property?
These guys have to be greater or equal to zero, okay.
So the relation here C minus PA has to be non-negative.
Okay, so this is what I'm basically trying to do.
So this thing here is the same as that, expressing the, the simplex multiplier, I
know that c is to be greater or equal to pi A.
Okay? So, which is essentially equivalent to
this because pi is equal to cB times the inverse of the basis.
okay? Now once you have that, this is very
interesting. Okay, so I know that the basis is optimal
if these costs are non-negative. And I have this relationship between C
and PiA, okay? And once I have done, I can very easily
prove now that optimality, you know these these these you know, these concepts to
be greater than zero, okay? So let's see, let's denote C star, okay?
You see C star, okay? C star is equal to C minus PiA, okay?
And I also have c 0 star which is the value of pi b which is like c b times the
inverse of the bases times b. And so this is the value of the function
atop finality, right? And so what I need to prove is that these
guys So that, the, the solution where c is greater than pi A is an optimal
solution. I need to prove that.
Okay. So what am I going to do.
I know that I have detected, I believe I have detected optimality, which is the
property that c is greater than pi A, okay?
And that's what you see there. and now what i'm going to do is that I'm
going to take another arbitrary feasible solution y, and i'm going to show you
that the cost of y, the objective function for that basic feasible
solution, is going to be greater than c zero star.
If I show you that it means basically when I get To a particular basic feasible
solution where c is greater than pi a, then I know that I am at the optimal
solution. And how do I do that?
It's very simple, this one. Okay, so what do I know about y?
I know that it has to be a feasible solution, right.
So what I know is that it has to satisfy this constraint, which is Ay is equal to
b, okay And I just have to this the following manipulation okay.
So I have the cost Cy so that's the cost of the feasible solution Y.
Now I know I know because you know I'm basically detecting these property that C
great than. Pi a.
So I can replace this c by pi a, and so c y is going to be greater than pi a times
y. Okay?
Now, you look at this expression here. It's nice, right?
So it's pi a y. But what do I know about y?
I know that y is to satisfy this condition, so Pi y is to be equal to b,
okay? So I get essentially the value pi b and
pi b is the value of the solution at that base when this condition is satisfied.
So I end, so this is the optimal solution because essentially any of the feasible
solution is going to be greater than that.
So what I'm basically going to be showing you here, with matrix notation, is that
every time I detect that this property is, you know, satisfied, the constantly
objective functions are all positive now, I'm basically optimum.
Okay, so that's why, you know, this matrix notation is some, is used for some
of these properties are easier to state. Okay, now the other things that I need to
tell you, and this is really important, is the tableau.
Okay, so a lot of the papers, a lot of the books that you're going to read, I'm
going to work with this tableau. And essentially this tableau is going to
put everything together in, you know, the right hand side, the left hand side.
All this the basis, everything in one big matrix, okay.
One big array. Okay?
So, so we're going to put all these coefficients, we're going to put all, all
these coefficients of the objective function.
All the coefficients of the matrix here. The right hand sides, you know.
All these things are going to be in one big tableau.
And then you can do pivoting, or simple naive implementation of the the, the
simplex algorithm very easily with one big matrix.
Of course, you know, practical implementatoin, don't do that.
There are much, you know, th-, th-, th-, th-, th-, they are, they are much more
efficient representation, because most of the time this matrix is sparse and you
want to, you know, exploit that sparsity. But this is the tableau.
Okay? And this is all you can actually compute
these things, you know by hand or simple implementation.
Okay? So this is essentially the system of
equations that I've shown you, and this is the first basic feasible solution that
I'm showing you for that particular system, okay?
And so what I want to show you is that we have the basis, we gotta have the right
end side, we gotta have the you know, we gotta have the objective function
represented there, okay? There are some convention and some of
them may not be natural but these are the convention most people are using.
Okay? So what you see there, the first row here
is going to be the negation of the objective volume.
Okay? So the way to think about this, in terms
of what we have done before, it's like exactly, you know, when we were looking
at the objective function, that's what was on the right-hand side.
Except the value here, which is going to be negated.
Okay? The va, the, the constant is going to be
negated but, all these guys think of that.
They were on the right hand side of this, this, of, of the formulation that we
have, that we were using when we were doing you know the representation where
the, the, the basic variables were isolated from the non-basic variable.
What you there you see the basic variable.
The basis okay. And the basic variable is always going to
be a nice matrix you know 1 0 0 0 0 0 1 0 0 0 the 0 1 0 0 0 1.
That matrix can be anywhere it's going to move right.
And it doesn't have to be that order but somewhere they will be basic variables
with 1 0 0. 010 and 001 and of course you can
generalize that, okay? And then you see the right inside over
there, these are the b values that you see over there, okay?
So basically, this is a particular, this is the basic feasible representation
expressed by the tableau. So you see the basic variables there,
okay? So they are one, you know, the, the, the,
they are there. The other ones are like what we have seen
before but we brought them in a sense you have to think about them, we brought them
to the left side. Okay, and so the coefficient that they
have are the negation of the coefficient. When we were represented that as a set of
equation, okay? So instead of leaving a 2, you have a
minus 2, instead of leaving a minus 3, you get a 3, okay?
So this is basically the tubler representation, okay?
So we look again at this tubler representation and see that we are doing
the simplex algorithm on top of this one, okay?
So what we're going to do is going to, we're going to look at basically the
objective function, and once again. If all the values there are strictly
positive okay well greater or or not negative okay, we will be at optimality.
In this particular case it's not the case.
Okay, so you can see that we have a minus 3 and minus 3 over there and so that
basically means that these two variables want to enter the basis, okay.
They say, ooh, I want to go into the basis, okay.
And so we can actually, you know and, you know, select a variable to enter the
basis. And now we left to select a variable to
lift the basis. And once again remember you know we flip
the size of this non basic variable. So before we were looking at variables
with a negative coefficient. since we flipped them, you know, from one
side to the other. In this box, in this case, we have to
look with values that are, that are positive.
So, for these particular guys, we going to look at the first equation.
We going to look at the last one. These are the two equations that we can
select. We are going to compute the ratio between
that co-efficient and the value B. In the first case, it's going to be 1/2,
in the second case it's going to be 1. So the variable, the, the constraints
that we are going to use to pivot is going to be the first constraint.
We're going to do the pivoting operation, and this is the resulting tableau, okay?
So once again, what you're going to see is the objective function in the top row,
okay? And know, the nice thing is that you see
these guys, they are strictly positive which basic they are, which basically
means that we are a toptemality, okay? And these are the values of the non-basic
variables, okay? So now, once again, you see the tableau
there you see the variable x2 there? One, zero, zero, that's part of the
basis. You see zero, one, zero and then you see
zero, zero, one. Okay?
This is the basis. You see that, you know some of the column
of this basis, basis are not interleafed with some of the column of the non basic
variables. Okay?
And obviously you see the value of the non basic variables.
Okay? x2 now is equal to three and a half.
You know x4, somewhere here, is equal to seven and a half and so on, okay.
And the value of the objective function at this point can be found in this column
and it's can be found in this column. And its value here is minus nine and a
half which means that. The real, the, but this is minus the
effective function, so this is going to be four and a half.
Okay? So, this is what the tableau does, okay?
Basically the same information that we have seen before, but it's kind of put in
one big matrix, with the, with various convention, okay?
So, this is essentially this transition lecture, so I'm done, so I've shown you
how actually we can use this matrix notation, it's very convenient in
general, okay, once you get used to it. And the tableau is also something that is
very nice, and we'll be able to express some beautiful property, just reasoning
about this tableau later on. Okay?
So thank you very much.