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.