00:00:01
okay welcome to another video today
00:00:04
we're getting into the heart of the
00:00:06
Simplex method so uh reviewing what we
00:00:10
covered in the previous videos we found
00:00:13
uh that if we have a linear program and
00:00:15
augmented form uh we can find all the
00:00:18
basic feasible Solutions um and that's
00:00:21
what we did in the last video but um
00:00:25
although there are only finitely many of
00:00:27
those uh basic feasible Solutions it
00:00:30
wouldn't be a good strategy to just try
00:00:31
to list them all it works for small
00:00:34
problems it's essentially what we did
00:00:36
when we did the graphical method um but
00:00:38
it's not how we want to work in practice
00:00:41
uh when we're solving a linear program
00:00:44
instead uh the whole idea behind uh the
00:00:48
Simplex method is instead of checking
00:00:50
all basic feasible Solutions um we start
00:00:53
at a basic feasible solution and then we
00:00:58
move to another basic feasible solution
00:01:01
sort of moving around the boundary of
00:01:03
the feasible region from kind of corner
00:01:05
to
00:01:06
corner and we always move in a direction
00:01:09
that improves our in objective value or
00:01:12
at least doesn't make it worse there's
00:01:14
sometimes where you sort of have to move
00:01:15
sideways and you see no improvement um
00:01:17
for that move but then you're able to
00:01:19
see some more Improvement in a later
00:01:21
move and we won't we won't worry about
00:01:23
that too much to begin with um but
00:01:26
there's this idea that we're going to
00:01:28
move from corner point to Corner point
00:01:30
or or basic feasible solution to basic
00:01:32
feasible solution in a way that moves us
00:01:35
around the boundary of our feasible
00:01:37
region until we find the best
00:01:41
solution okay so some questions that we
00:01:44
need to answer if we're going to do that
00:01:45
is uh how do we know where to start um
00:01:49
how do we know where to move next and
00:01:51
how do we know when we're done um we're
00:01:53
going to focus on two and three in this
00:01:55
video we're going to save uh one for
00:01:57
later we'll give a pretty simple answer
00:01:59
answer for number one uh for this video
00:02:02
um but we'll have to dive into that in
00:02:04
more deep deeply when our Simple
00:02:07
Solution doesn't work out so uh let's
00:02:09
look again at uh jepetto's problem in
00:02:12
augmented form um but let's also
00:02:16
introduce a a a variable z uh that
00:02:21
tracks our objective okay so uh we said
00:02:24
we want to maximize three times the
00:02:26
number of soldiers plus two times the
00:02:28
number of trains and we're going to say
00:02:29
that uh that value Z so Z is going to be
00:02:32
our objective value and our goal in this
00:02:34
case is to maximize uh
00:02:37
Z and we're going to do a little trick
00:02:39
in that we want all our variables on the
00:02:41
left side of the equation and so we'll
00:02:43
subtract 3xs and and 2xt over the other
00:02:47
side um so that we have this equation
00:02:49
here and we're going to treat this
00:02:51
equation just like we treat our
00:02:54
constraints um it's a little bit special
00:02:56
as a constraint because it's really our
00:02:58
objective uh we're going to put in the
00:03:00
top row of our system um but essentially
00:03:03
we're going to take that augmented
00:03:04
system now and add this to it so um if I
00:03:08
think of my variables now that I've
00:03:11
introduced uh Z is in my new variable
00:03:14
I'll always put it the left side just
00:03:15
kind of out of practice U my original
00:03:18
variables of Xs and XT and then I've got
00:03:22
three slack variables SF S C and S
00:03:28
D and then uh right hand
00:03:32
side okay so first I'll take uh this
00:03:35
objective and I'll actually put that in
00:03:38
the top row so I've got a coefficient of
00:03:40
one for
00:03:42
Z -3 for
00:03:44
XS -2 for XT none of my slack variables
00:03:49
show up and so they're all zeros and
00:03:51
then my right hand side uh because I
00:03:53
moved everything to the left side uh my
00:03:56
right hand side ends up being zero okay
00:03:58
and just to show that this uh top row is
00:04:02
actually the objective I sort of draw a
00:04:04
line to separate it out from the
00:04:07
rest I also like to uh draw a vertical
00:04:10
line to separate out my right hand side
00:04:13
and maybe also out of habit I like to
00:04:15
draw another line to separate out z z is
00:04:19
uh kind of a little bit of a different
00:04:20
variable um it's tracking our objective
00:04:24
now underneath that I put all my
00:04:26
constraints uh and so we had our
00:04:29
constraints from last time let me S pull
00:04:32
those up
00:04:33
here uh so and notice my Z doesn't show
00:04:37
up in any of my constraints and so
00:04:39
actually I'm going to get
00:04:41
zero uh in there for each of my um for
00:04:46
the coefficient of Z because it's not in
00:04:48
any of the constraints um but my first
00:04:50
constraint was 2x1 or 2xs 1xt uh one for
00:04:55
my first slack variable zero for my
00:04:57
other slack variables equals 100
00:05:01
one one 0 one 0 and 80 for my second
00:05:06
constraint and uh one 0 0 0 1 and 40 for
00:05:13
my third constraint and this uh this
00:05:17
constraint was the uh finishing
00:05:19
constraint the carpentry constraint and
00:05:21
the demand
00:05:23
constraint okay so I've got uh my
00:05:27
objective row I've got my three
00:05:28
constraint rows along with this new
00:05:31
variable z uh that's going to track um
00:05:35
essentially my objective so um and this
00:05:38
is actually we give this a name this is
00:05:39
this will uh be what we call the Tableau
00:05:43
um and we're using sort of the Tableau
00:05:45
method it's just a fancy way of of
00:05:46
talking about this a special augmented
00:05:50
uh Matrix here it really is um just a
00:05:53
matrix an augmented Matrix where we've
00:05:55
now added an extra row um for
00:06:00
for the objective okay so similar to
00:06:03
what we did in the last uh video now
00:06:05
we're going to choose a basis okay and
00:06:08
this is really the where do we start
00:06:10
question of where should we start
00:06:12
because we know that each choice of a
00:06:14
basis corresponds to a basic feasible
00:06:18
solution or a corner point so uh to
00:06:21
begin with and for all the examples or
00:06:23
the first several examples that we see
00:06:25
this week our choice for a basis um will
00:06:29
be pretty easy and that our initial
00:06:36
basis uh we'll choose we'll always
00:06:40
choose Z to be in our basis um some
00:06:42
books actually kind of implicitly choose
00:06:44
Z in in to be in the basis and don't
00:06:47
explicitly say that it's in the basis
00:06:49
but I I like thinking of Z is always in
00:06:51
our basis and then we're going to choose
00:06:54
each of the slack variables to be in our
00:06:57
basis to begin with so s f s c and SD so
00:07:04
these are going to be all of our basic
00:07:05
variables and all the other variables so
00:07:08
maybe I'll make a note note of it
00:07:13
nonbasic then uh would
00:07:16
be uh my two original variables Xs and
00:07:21
XT so uh the non-basic variables we're
00:07:24
going to set each of these to
00:07:26
zero and then uh we're g to essentially
00:07:30
read off the values of these ones here
00:07:32
now kind of the first step would be
00:07:36
forming the B Matrix here and sort of
00:07:39
solving to get that into the identity it
00:07:42
turns out we've already got an identity
00:07:45
Matrix or our standard basis vectors
00:07:47
underneath SF SC and SD okay so if we
00:07:52
set these two to be equal zero it's
00:07:54
essentially the same as Crossing off
00:07:57
these two columns and ignoring them
00:07:59
because
00:07:59
the value of those variables is zero and
00:08:02
then uh this first row well actually our
00:08:04
objective row if we cross if we set XS
00:08:07
to zero and XT to zero uh then we get
00:08:11
one we get Z equals that's zero that's
00:08:14
zero these are all zeros for their
00:08:16
coefficient and then our right hand side
00:08:18
says equals zero and so our initial
00:08:27
solution has Z equal Z that we can know
00:08:32
from this first line and actually I'll
00:08:34
kind of denote this row as the Z it's
00:08:36
our objective row and so I'll write that
00:08:39
there um this next row if I set uh Xs
00:08:42
and XT to be zero um and so essentially
00:08:45
hide those I can read off that
00:08:47
SF is uh is the only other thing that
00:08:50
has a has a coefficient in that row and
00:08:53
it has a coefficient one so 1 * SF equal
00:08:56
100 and so we'll actually call this the
00:08:59
f SF row and that one tells us that SF
00:09:03
equals
00:09:05
100 SC similarly we can read off from
00:09:09
this row these these get zeroed out and
00:09:11
we get SC equals 80 and SD equal 40 okay
00:09:19
and this is actually one of our um basic
00:09:21
feasible solutions from last time and
00:09:24
then we can tack on that XS equals 0 and
00:09:27
XT equal 0 cuz they are the non-basic
00:09:31
variables so that is our initial
00:09:35
solution first qu uh next question is is
00:09:38
it an optimal solution um we know
00:09:40
because we've solved this problem uh
00:09:43
graphically that it's not um this this
00:09:47
corresponds to the origin in the
00:09:48
original units or in the original
00:09:50
variables it's not optimal but how do we
00:09:53
know that well let's look at our
00:09:55
objective
00:09:57
so is it
00:10:02
optimal and then so uh we can say no but
00:10:06
why is that well Z if we if we read off
00:10:10
this first row Z minus
00:10:13
3xs minus
00:10:16
2xt = Z or actually moving these back
00:10:19
over to the other side Z = 3 XS +
00:10:26
2xt now Xs and XT are currently
00:10:30
non-basic variables meaning that they're
00:10:32
currently set to zero but the question
00:10:35
is if we brought one of those variables
00:10:38
into the basis and made them not zero
00:10:42
would we improve our objective and and
00:10:44
in this case both of them once we move
00:10:46
them over to the right side have
00:10:48
positive coefficients they're negative
00:10:50
coefficients when they're on the left
00:10:51
side but they're positive coefficients
00:10:53
once we move them over the right side
00:10:54
and so increasing either XS or XT from
00:10:58
zero would increase Z as well okay this
00:11:01
is the key idea of um Xs and XT are
00:11:05
currently zero but if we increase them
00:11:07
from zero brought them into the basis
00:11:09
made them non zero um would that improve
00:11:13
uh and the answer is yes um so I'll
00:11:17
maybe write that out we
00:11:19
can
00:11:22
increase
00:11:24
Z
00:11:27
by increasing
00:11:30
XS or
00:11:34
XT okay so that that's going to be the
00:11:38
next step we're going to change our
00:11:39
basis uh we're going to choose one uh
00:11:42
either XS or XT um of our variables to
00:11:45
come into our basis we'll choose another
00:11:48
variable then we'll have to leave the
00:11:49
basis um because if we remember uh when
00:11:53
choosing our basis we want essentially
00:11:55
uh the basis to match the number of um
00:11:58
constraints now we sort of add added an
00:12:01
extra row added Z in there so we're
00:12:03
going to we're going to always look for
00:12:04
having four variables in our basis and
00:12:07
so and you can actually think of each of
00:12:09
these uh four variables as corresponding
00:12:13
to one of the rows okay so there's one
00:12:15
variable to per row and you'll notice
00:12:18
that if I look at the columns for these
00:12:20
variables the standard basis vectors
00:12:23
show up in the columns for Z SF s c and
00:12:26
SD and that's going to be the
00:12:28
characteristic
00:12:30
um feature of our basis is that the
00:12:33
standard basis vectors are going to show
00:12:35
up underneath our basis variables okay
00:12:38
and so when we bring a new variable into
00:12:41
the basis we're going to do elementary
00:12:43
row operations in order to change
00:12:46
whatever the current column is into uh
00:12:50
the standard basis
00:12:51
Vector okay
00:12:54
so let's uh choose XS or XT to our our
00:13:00
basis um now either of them should
00:13:03
improve our objective there's a couple
00:13:05
of rules of thumb uh that your book
00:13:08
talks about um of how to choose they're
00:13:11
mostly just heris and as long as you
00:13:13
choose one that one variable that
00:13:15
improves it um and as long as you're
00:13:18
kind of careful not to get stuck in a
00:13:20
loop uh where you're sort of uh
00:13:23
switching back and forth between between
00:13:24
variables um it really doesn't matter
00:13:27
which variable you choose as as long as
00:13:29
you choose one that improves um your
00:13:31
objective so um I tend to follow the
00:13:35
simple
00:13:36
heuristic of choosing whichever has the
00:13:39
larger coefficient meaning that the
00:13:41
smallest change in either XS or XT
00:13:44
results into a larger change in Z no
00:13:47
guarantee that that's going to get you
00:13:48
there in the fewest number of steps
00:13:50
actually in this case uh we'll find that
00:13:52
it will take us more steps using this
00:13:54
heuristic which is fine more more
00:13:56
example more um more uh kind
00:13:59
uh yeah more video to show you so um
00:14:02
looking at this uh the three coefficient
00:14:04
is bigger than the two coefficient so
00:14:06
we're going to choose XS to enter our
00:14:09
basis okay uh you're going to want a
00:14:12
couple extra sheets of paper for this
00:14:14
and so here I'm going to jump onto a new
00:14:17
sheet of
00:14:19
paper so we're going to
00:14:23
choose
00:14:25
XS to enter the basis
00:14:31
okay which means that our new
00:14:34
basis
00:14:35
um is going to have XS in it but we've
00:14:38
got to get rid of something else and so
00:14:41
uh let's look at our
00:14:44
constraints uh that are up here and
00:14:47
think about okay if XS which is
00:14:49
currently zero starts increasing from
00:14:51
zero uh when does one of the other
00:14:56
variables uh the other variables SF f s
00:14:59
c and SD are going to have to uh kind of
00:15:02
compensate for that um in order to
00:15:05
maintain the inequalities here might
00:15:07
remember we don't have inequalities
00:15:08
anymore we got equalities so if uh XS
00:15:12
increases uh SFS C and SD are going to
00:15:15
have to compensate and the question is
00:15:17
um as they're compensating uh which one
00:15:20
of those gets driven to zero first okay
00:15:24
so let's actually write out uh what each
00:15:27
of these constraints are um maybe not in
00:15:30
augmented form but actually in as
00:15:32
formulas and let's look at those so our
00:15:35
first constraint uh up here is
00:15:38
essentially saying
00:15:40
2xs + 1
00:15:44
XT plus
00:15:47
SF uh equals
00:15:51
100 okay sorry let me bring that up and
00:15:54
I'll kind of just hide some of the work
00:15:56
we had below um my our next constru
00:15:59
straint is uh XS +
00:16:04
xt+ S
00:16:08
C equals 80 and then we've got uh
00:16:13
XS plus SD equal
00:16:17
40 okay let's uh look at this first
00:16:20
constraint the first thing we can do is
00:16:23
we know that we're going to increase XS
00:16:25
but XT is going to stay nonbasic
00:16:29
okay and so we're going to cross out
00:16:31
these
00:16:33
XTS and we're going to put zero there
00:16:36
and that's because
00:16:39
XT is
00:16:41
non Basic and it's going to stay
00:16:44
non-basic so we can essentially ignore
00:16:47
that okay now I want to essentially
00:16:51
figure out what value of XS would make
00:16:55
SF go to zero okay and so if I want to
00:16:59
find out when does SF go to zero well
00:17:01
let's just actually set SF to zero and
00:17:04
if SF goes to zero uh then um I'll
00:17:09
essentially hide that and then I'd be
00:17:11
left with 2xs equals 100 uh and so this
00:17:15
is essentially saying or uh if SF equals
00:17:22
z then XS equals if SS equals zero then
00:17:28
X has to be equal to
00:17:32
50
00:17:33
okay let's do the same thing here uh
00:17:37
let's figure out if SC equals zero so if
00:17:41
I plug in zero for SC then
00:17:47
XS equals 80 and then finally
00:17:52
if SD equals
00:17:55
z then um X s equal
00:18:02
40 okay so I've sort of figured out what
00:18:06
value of XS would correspond to each of
00:18:09
those slack variables going to
00:18:12
zero uh and the thing is I'm sort of
00:18:15
slowly raising XS from zero and I need
00:18:19
to stop as soon as one of these gets
00:18:22
driven all the way down to zero because
00:18:23
if I go any more that variable would
00:18:26
then go negative okay and remember if we
00:18:28
want to stay in our feasible region all
00:18:31
of our variables need to need to remain
00:18:34
non negative so we can't go negative we
00:18:36
can go to zero but we can't go past zero
00:18:38
okay and so looking at these the first
00:18:41
one that gets driven to
00:18:43
zero is this
00:18:45
one so this is
00:18:50
the first
00:18:56
variable that goes to zero
00:19:03
okay and so
00:19:06
SD is going to be what we'll call our
00:19:08
exiting variable okay XS is entering SD
00:19:12
is going to exit then it's the first one
00:19:14
that gets driven to
00:19:16
zero okay and
00:19:19
so we'll say
00:19:22
[Music]
00:19:24
SD uh is
00:19:26
our exiting
00:19:33
variable and that X SD leaves the basis
00:19:38
okay um so uh that will tell us that
00:19:42
then our new
00:19:46
basis will be Z is still going to be
00:19:49
there and let's see let's look at what
00:19:52
our our old
00:19:54
basis uh was that we're going to
00:19:57
essentially take s D Spot in that basis
00:20:00
and and put XS in that spot I'm going to
00:20:03
actually give pretend like this basis
00:20:06
has an ordering because it sort of does
00:20:07
it has the ordering of our columns and
00:20:10
so our basis is going to be
00:20:13
zsf S C and now
00:20:18
XS okay that's going to be our new basis
00:20:21
and now the trick is we need to do um
00:20:24
Elementary row operations so that we get
00:20:27
our standard basis vector below each of
00:20:29
these in our Tableau or our augmented
00:20:33
Matrix so I'm going to go ahead and set
00:20:36
this up again so uh Z
00:20:39
XS XT
00:20:42
SF S C
00:20:45
SD right hand
00:20:50
side objective
00:20:52
row draw some lines in there
00:20:56
okay so what we want uh for this to
00:21:01
happen
00:21:02
is uh let's see we want XS to enter our
00:21:08
basis okay and so what we want to get is
00:21:11
we want to get it so that and it's
00:21:13
entering in the place of X SD SD had the
00:21:17
fourth standard basis Vector so back
00:21:21
here maybe I'll flip it up like this
00:21:24
hold my page a little bit so that we can
00:21:26
see this of where we were and where we
00:21:29
are okay this is going to help yep so SD
00:21:33
had the
00:21:35
00001 standard basis Vector in it and so
00:21:38
that's the standard basis Vector that
00:21:40
we're going to eventually want in the XS
00:21:43
column okay and so uh Xs and let's
00:21:48
actually label the rows that will help
00:21:50
us maybe a little bit s c SF those ones
00:21:54
stay in there and Z is always the
00:21:57
objective row
00:21:59
okay so this is what we want here okay
00:22:03
looking at what we have if we look at uh
00:22:07
the bottom row it's got a one here we
00:22:09
want a one here and so actually our
00:22:12
bottom row in this case is good to go if
00:22:14
there wasn't a one here we'd want to
00:22:17
multiply or divide this row by whatever
00:22:20
made uh this turn into a one okay and
00:22:23
we'll see that an example of that in a
00:22:24
bit um but this is a one and so we don't
00:22:29
actually have to do anything to the
00:22:30
bottom row and so let's copy the bottom
00:22:32
row up to here and so this bottom row is
00:22:34
then zero
00:22:37
zero I'm trying to make this line up a
00:22:40
little bit z z one um 40 okay so I just
00:22:46
copied my bottom row
00:22:48
down okay now I look at uh this entry
00:22:52
here and it's a one I want it to be a
00:22:55
zero so if I want to zero this out then
00:22:58
I'm going to use a multiple of this row
00:23:00
add it up to zero that out okay uh this
00:23:03
value is one this value is one if I I
00:23:06
take uh this row minus this row that
00:23:09
should zero this out okay uh and so I'm
00:23:12
going to do uh this this row minus this
00:23:15
row and so uh 0 - 0 is 0o uh 1 - 0 is 1
00:23:22
0 - 0 is 0 1 - 0 is 1 0 - 1 is -1 and 80
00:23:30
- 40 is 40 so I did uh sort of this row
00:23:36
minus this row okay uh now looking up at
00:23:40
the top row or not well not the top row
00:23:43
the second row I've got a two here I
00:23:46
want to turn that two into a zero and so
00:23:49
I'm going to take -2 times the bottom
00:23:51
row add it up to the top row okay and so
00:23:55
-2 * 0 add it up and I'll still have
00:23:59
zero up here uh -2 * 0 add it up and
00:24:04
that leaves this as a one -2 * 0 we'll
00:24:07
leave this as a one -2 * 0 we'll leave
00:24:10
this as a Zer -2 * 1 uh we'll change
00:24:15
this into a -2 and -2 * 40 plus 100 will
00:24:21
give us 20
00:24:23
here okay so doing row
00:24:26
operations um
00:24:29
essentially maybe I'll kind of here's
00:24:31
maybe the way that I keep track of my
00:24:33
row operations of I took negative one
00:24:36
times this row and added up there I took
00:24:40
negative two times that row and added it
00:24:43
up there and then I need to cancel this
00:24:47
three out now to turn that into the zero
00:24:49
that I want there and so I'm going to
00:24:51
take uh
00:24:54
three times the bottom row add it up to
00:24:57
the top row
00:24:59
okay so this is going to remain a
00:25:02
one uh 3 * 1 + -3 that's going to get me
00:25:07
the zero that I want uh 3 * 0o uh we'll
00:25:11
leave this as a -2 3 * 0 will leave this
00:25:15
as a zero 3 * 0 + 0 will leave this 0 3
00:25:21
* 1 + 0 will turn this into a three and
00:25:24
3 * 40 + 0 is 120
00:25:30
okay so this is
00:25:33
our uh augmented Matrix or Tableau after
00:25:38
this process that we just did is called
00:25:40
pivoting so in pivoting uh you
00:25:42
essentially um change one of your
00:25:45
columns into a standard basis Vector in
00:25:47
this case we chose to change our XS
00:25:50
column into the standard basis Vector
00:25:54
00001 okay that brought XS into our
00:25:57
basis
00:25:59
I'll maybe show you yeah that brought
00:26:01
excess into our basis
00:26:05
okay so this is now our updated uh
00:26:09
Matrix uh it's row equivalent to what we
00:26:12
had before so has the same Solutions and
00:26:15
everything but we've sort of uh changed
00:26:19
uh where our nice uh kind of standard
00:26:22
basis vectors are in here okay so here's
00:26:26
our new basis I will say that non-basic
00:26:33
variables are XT and
00:26:39
SD uh SD because it left and XT because
00:26:42
it's still
00:26:43
non-basic okay and so those are both
00:26:45
going to be uh zero in our solution and
00:26:48
so reading off our new
00:26:52
solution um each basis each choice of
00:26:55
basis corresponds to a corner Point uh
00:26:57
BF best basic feasible solution and so
00:27:00
that new
00:27:03
solution uh we read it off um so
00:27:06
essentially the right hand side encodes
00:27:10
the values of Z SF s c and Xs okay and
00:27:15
that's because I'm essentially putting
00:27:17
in zeros for XT and SD and then if I put
00:27:22
zeros in for those then the only things
00:27:24
that have uh a coefficient in this first
00:27:27
row is the Z in the second row is SF and
00:27:30
in the third row SC and then in the last
00:27:33
row
00:27:34
Xs and so the new solution is z our
00:27:37
objective value has now increased to 120
00:27:40
okay that's going in the right direction
00:27:42
we went from zero objective to now
00:27:45
120 um
00:27:47
SF we can read off this value is now 20
00:27:51
we've got 20 units of finishing
00:27:53
slack we've got 40 units of carpent tree
00:27:58
slack and we are making now um 40
00:28:05
soldiers okay 40 soldiers
00:28:09
and zero trains and we've got
00:28:13
no slack for demand we are making all
00:28:16
the soldiers that demand tells us will
00:28:19
sell okay so this is essentially one
00:28:23
step of the Simplex algorithm okay to
00:28:25
kind of review uh
00:28:29
what happened in this one step is we
00:28:32
checked is it optimal we said no uh we
00:28:35
can improve it by bringing in XS or XT
00:28:39
into our basis we chose XS to enter our
00:28:43
basis we found which of the current
00:28:47
basis variables gets driven to zero
00:28:49
first and in this case it was SD so SD
00:28:52
exited our basis and then we had a new
00:28:56
basis and we pivoted on that new
00:28:59
basis okay uh pivoted on excess to get
00:29:03
to that uh Tableau that represents that
00:29:05
new basis and with that we got a new
00:29:08
solution okay now we now we repeat the
00:29:11
process um so let's ask uh the same
00:29:14
question again uh which is is it
00:29:24
optimal okay uh and so let's look at
00:29:27
this top row this top row Says
00:29:30
Z -
00:29:34
2xt + 3 SD equals
00:29:39
120 okay I'm going to go ahead and move
00:29:42
uh everything but Z to the other side
00:29:44
and so my formula for Z is I'll add 2xt
00:29:48
to the other side and minus 3 SD to the
00:29:52
other side uh plus
00:29:56
120 and so these two variables are
00:29:59
currently zero there are non-basic
00:30:02
variables and so if I look at them if I
00:30:04
were to increase SD from zero it's got a
00:30:07
negative coefficient so it would
00:30:09
decrease our objective not good
00:30:13
okay we might have had a hint that this
00:30:15
was going to happen because SD just left
00:30:17
our basis and we improved when it left
00:30:19
so we wouldn't want to immediately bring
00:30:21
it back in it wouldn't it wouldn't
00:30:22
provide any Improvement right now on the
00:30:25
other hand XT has a positive coefficient
00:30:28
okay uh so bringing XT into our basis
00:30:32
increasing it from zero should increase
00:30:35
our
00:30:37
objective okay so
00:30:40
uh yeah we want to
00:30:43
[Music]
00:30:44
choose so is it
00:30:47
optimal not
00:30:52
optimal XT can improve
00:30:59
uh the
00:31:03
objective okay so here's here's actually
00:31:07
the way I do it uh and so we've sort of
00:31:09
done it the long way but what you want
00:31:11
to do is scan this top row here and for
00:31:14
a maximization problem you want to look
00:31:16
for negative coefficients okay uh for
00:31:19
these variables here looks like XT has a
00:31:21
negative coefficient which means that
00:31:23
once we move it over the other side it
00:31:24
would be a positive coefficient and
00:31:26
would increase our OB object
00:31:30
objective then what I do is I go ahead
00:31:32
and circle that column okay XT is going
00:31:35
to be our entering
00:31:37
variable and now we need to do this
00:31:40
process again okay here's the thing to
00:31:43
get these numbers over here uh you'll
00:31:47
notice that these numbers over here are
00:31:48
exactly the right hand side numbers
00:31:51
divided by the coefficients of
00:31:54
XS okay and so that's all it is and then
00:31:57
we just chose the smallest positive one
00:32:00
so let's actually do that uh kind of as
00:32:02
a shortcut here so what we're going to
00:32:03
do is we're going to take our right hand
00:32:05
side and we're going to divide it by
00:32:07
whatever coefficient is in uh this XT
00:32:11
column and so we're going to do 20 over
00:32:15
one uh we'll do 40
00:32:19
over one and we'll do 40 over
00:32:23
z uh yeah if we got a zero or a negative
00:32:26
value here we ignore those rows okay um
00:32:30
it's not going to uh that uh that uh
00:32:35
that variable is not going to be driven
00:32:37
to zero okay
00:32:39
so so we're going to ignore that one and
00:32:42
now we choose the smaller of the two
00:32:43
okay so uh either SF or SC is going to
00:32:48
leave leave it turns out that uh By the
00:32:51
time
00:32:53
uh XT uh
00:32:58
yeah as we raise XT uh SF goes to zero
00:33:01
when XT is 20 and SC goes to zero when
00:33:05
XT is 40 and so we got to do the one
00:33:07
that goes drives it to zero first and so
00:33:10
SF is going to be
00:33:12
[Music]
00:33:13
our exiting
00:33:20
variable okay
00:33:24
so I'll move this up here XT
00:33:28
is
00:33:32
entering
00:33:33
SF is
00:33:37
exiting which gives us a new
00:33:45
basis uh let's see uh
00:33:50
Z XT is going to replace SF
00:33:58
uh SC is going to stay in and Xs is
00:34:01
going to stay
00:34:02
in and then our non-basic
00:34:06
variables are going to be
00:34:10
um well we just had SF leave and
00:34:14
SD um left in the previous
00:34:17
iteration
00:34:19
okay let's do another pivot uh this time
00:34:24
uh so looking up at this we sort of
00:34:25
circled a row as our sort of exiting
00:34:28
variable we circled a column as our
00:34:30
entering variable this point here is
00:34:33
going to see be uh kind of what I'd say
00:34:36
we pivot on this point okay meaning that
00:34:39
we want to turn this into a one
00:34:41
thankfully it's already already a one
00:34:42
and we're going to want to turn
00:34:44
everything else in this column into
00:34:46
zeros so that's the
00:34:50
goal I'm get myself a new sheet of paper
00:34:53
here and Slide the
00:34:57
okay actually
00:35:00
yeah so let's go ahead and set this up
00:35:04
and line it up right below here so
00:35:08
Z XS
00:35:10
XT
00:35:12
SF S C
00:35:16
SD right hand side normally once I get
00:35:20
kind of uh the pattern down I'll sort of
00:35:23
line these up so I don't have to write
00:35:25
my variables out again and I'll just
00:35:27
kind of have one Tableau directly below
00:35:29
the next
00:35:30
Tableau and so if you have like a nice
00:35:32
grid paper or something like that um
00:35:35
that can be kind of nice here okay so
00:35:39
I'm going to want to turn this value
00:35:41
into one turns out it's already a one
00:35:43
and so I can leave this row alone and so
00:35:46
let me draw this line here and then so
00:35:49
this uh second row is going to stay as Z
00:35:52
0 1 1 0 -2 20
00:35:58
okay now I like to think as little as
00:36:02
possible when I'm doing uh these row
00:36:04
operations because it's easy to kind of
00:36:06
get messed up and so I I like to fill in
00:36:10
right from the beginning as many entries
00:36:11
as I I can just because I know what my
00:36:16
next Tableau is going to look like okay
00:36:18
and as long as you're sort of following
00:36:20
the right rules um these these values
00:36:22
are going to kind of fill in the right
00:36:24
way um one is I know that I want this C
00:36:27
to become 0 1 0 0 okay that's what I
00:36:33
want it to come become I also know that
00:36:37
my other basic variables which let me
00:36:39
write that basis along the side here
00:36:42
zero uh x t s c and
00:36:46
Xs those other basic variables are going
00:36:49
to have the other standard basis vectors
00:36:52
uh beneath them and so my Z column
00:36:56
actually never changes throughout this
00:36:57
whole process um the Z column never
00:37:00
changes if you wanted to sort of omit
00:37:02
that Z column you could um but it's just
00:37:05
really There To Remind us that we've
00:37:08
introduced this Z variable it will
00:37:10
always say one z0
00:37:12
Z okay uh this SC column is going to
00:37:15
have the 0 0 one0 it's going to only
00:37:20
have a one in the row that it
00:37:22
corresponds to the SC row and then XS is
00:37:25
g to have a one right here but zeros
00:37:29
everywhere else okay and then from there
00:37:33
now I just see that I only have one two
00:37:35
three four five six seven eight nine
00:37:38
things that are gonna actually have to
00:37:39
think about okay so that's sort of a
00:37:42
nice shortcut is put my standard basis
00:37:45
vectors exactly where they need to be
00:37:47
okay uh so this row already had a one
00:37:50
there it didn't need to be multiplied it
00:37:52
was able to stay the same okay now I
00:37:54
need to take multiples of this row add
00:37:57
up and down in order to cancel out uh
00:38:00
the different values and so let's go up
00:38:04
first uh and so I've got a one here I
00:38:07
got a negative -2 here so I'm going to
00:38:10
take
00:38:11
uh two times that row added up in order
00:38:15
to
00:38:16
cancel so uh 2 * 1 added to the -2 will
00:38:22
give me zero that's what I want that's
00:38:24
why I chose two uh 2 * 1 plus the zero
00:38:28
is going to make this into a two uh 2 *
00:38:32
-2 is -4 plus the three uh becomes - 1 2
00:38:37
* 20 is 40 plus the 120 is
00:38:44
160 okay now I want to zero this value
00:38:48
out here and so I'm going to actually
00:38:52
take this row times Nega 1 add it down
00:38:55
and so take1 1 times that row add it
00:38:59
down um so -1 * 1 + 1 is z that gave me
00:39:04
what I wanted uh -1 * 1 + 0 is 1 uh 1
00:39:11
* that's going to give me my 1 -1 * 2 is
00:39:16
pos2 plus the - 1 is postive 1
00:39:20
and uh 1 * 20 + 40 is positive 20
00:39:28
okay looking at my last row I want a
00:39:30
zero here I've got a zero there so I
00:39:33
actually can leave this last row alone
00:39:35
nothing changes in this last row zero
00:39:38
one
00:39:40
40 okay the last row didn't
00:39:43
change okay um so there I go I pivoted
00:39:47
this was a little bit quicker now this
00:39:49
time and as you get the practice it it
00:39:51
it'll move a little bit faster you're
00:39:53
just doing Elementary row operations of
00:39:55
taking multiples of a row and adding it
00:39:58
or subtracting it to the other rows and
00:40:00
it's you're always going to essentially
00:40:02
use your pivot row as your I like to
00:40:05
think of it as a tool okay it's going to
00:40:08
be what you're going to be adding and
00:40:09
subtracting to your other rows to make
00:40:11
things
00:40:12
happen Okay uh new solution we've got a
00:40:15
new basis now let's go ahead and read
00:40:17
off our new
00:40:23
solution our objective value Z increased
00:40:27
to 160 that's good we should always see
00:40:30
this uh our objective value
00:40:33
improving XT we can read it off this row
00:40:37
XT =
00:40:39
20
00:40:42
SC equal 20 and
00:40:47
Xs equal 40 I'm reading those off the
00:40:50
right hand side um because the other
00:40:55
variables uh
00:40:57
SF and SD are both
00:41:03
zero okay that's so that's my new
00:41:05
solution my new basic feasible solution
00:41:07
it is feasible uh because I should
00:41:09
verify all my entries are positive okay
00:41:13
um all the variable values are positive
00:41:15
so I'm at a feasible
00:41:18
Point okay am I optimal Let's uh do what
00:41:22
we did last time so I said we want to
00:41:24
scan the top row for negatives
00:41:28
okay uh so it was this sort of -2 that
00:41:30
tipped us off that we should choose XT
00:41:32
as our entering variable now as I scan
00:41:35
the top row I see a negative one here
00:41:38
okay so we're not yet
00:41:49
optimal no um essentially that top row
00:41:53
says that Z equal -2 SF plus
00:41:59
SD plus 160 and so if I increase SD now
00:42:06
um kind of one pivot into the future it
00:42:08
will actually improve it and so although
00:42:10
in our first iteration we sort of moved
00:42:13
SD out of the basis um now we're going
00:42:16
to move it back into the basis okay and
00:42:19
as long as it's sort of one pivot later
00:42:21
on down the road that's sort of fine um
00:42:24
and and it's actually going to lead to
00:42:26
an improvement
00:42:29
okay um so we're going to have
00:42:34
SD as our entring
00:42:38
variable we'll Circle this column here
00:42:41
we can see that it's got a negative one
00:42:43
in the top row negative coefficient in
00:42:45
the top row it indicates Improvement for
00:42:48
a maximization
00:42:50
problem now let's go ahead and compute
00:42:52
our ratios we take this number divided
00:42:54
by the value in our pivot column
00:42:58
if we have a negative in our PIV pivot
00:43:00
column ignore that one we can't pivot on
00:43:02
a negative okay um so then we get 20
00:43:07
over one and 40 over one and so choose
00:43:11
the smaller of the two and so we're
00:43:14
going to
00:43:15
choose this
00:43:19
one
00:43:21
okay so which variable is that that's SC
00:43:24
so SC is going to be exiting
00:43:31
okay now let's go ahead I want to pause
00:43:34
the video a little bit and rearrange my
00:43:37
paper okay I folded my paper over to
00:43:40
kind of hide the stuff that we just
00:43:41
wrote in the middle there so that I can
00:43:43
have my two tablos right next to each
00:43:45
other I also went ahead and kind of uh
00:43:48
set up the uh the edges the labels on my
00:43:51
taows um but so this is our pivot uh
00:43:55
column uh this is our pivot row we want
00:43:59
a one here and Zer everywhere else in
00:44:01
that column so we want to turn this SD
00:44:03
column into zero 0 one
00:44:08
0 okay uh turns out we got a one here uh
00:44:12
so we don't need to do anything to this
00:44:14
row if it were a two we'd divide by two
00:44:17
if it were a half we'd multiply by two
00:44:19
essentially we'd multiply or divide this
00:44:21
row by whatever we needed to in order to
00:44:24
turn this into a one got a little lucky
00:44:27
it's already one again and so we're
00:44:29
going to have uh we're going to leave it
00:44:31
alone and we're going to get zero uh 0 0
00:44:35
neg1 1 and
00:44:40
20 um and now let's go ahead and fill in
00:44:42
the columns that we know are going to be
00:44:44
what they're going to be so our basis
00:44:46
columns are going to still be one zer0
00:44:49
for um Z my second basis column is going
00:44:52
to be
00:44:54
XT my third basis column is this SD and
00:44:57
my last basis column is
00:45:01
XS that's going to give me those okay
00:45:04
and you can verify that actually because
00:45:06
you'll notice that um this row has zeros
00:45:10
in both in all three of these places
00:45:12
then as we add or subtract multiples of
00:45:15
this this row here this SD row it's
00:45:17
actually not going to change any of the
00:45:19
entries in these three columns because
00:45:22
it's got zeros here so that's why I can
00:45:24
kind of quickly fill those values in
00:45:29
okay now let's kind of go ahead and
00:45:31
think about what we need to do uh to
00:45:35
cancel out various values let's go up to
00:45:37
the top row we've got a one here a
00:45:39
negative one here if I add this row up
00:45:42
um that will cancel out the one here and
00:45:44
so I'm going to
00:45:46
do one times this row add it up to that
00:45:51
row and so that's going to be 1 * - 1
00:45:54
plus the 2 is going to give positive 1 1
00:45:59
* 1 + 0 is going to be 1 1 * 1 +
00:46:06
negative 1 is going to give me the zero
00:46:07
that's there 1 * 20 + 160 is going to
00:46:12
make it
00:46:14
180 okay next we'll go ahead and zero
00:46:17
out this entry here uh I need to add two
00:46:20
times this row up to that Row in order
00:46:23
to cancel it and so I'll go remind
00:46:27
myself that I'm going to take two times
00:46:28
that add it up to there um so 2
00:46:32
* -1 + one is going to be uh negative
00:46:41
1 2 * 1 + 0 will be 2 2 * 1 + -2 is
00:46:47
going to give us the zero that we want 2
00:46:50
* 20 uh plus 20 is going to give us 60
00:46:55
and that's good for that row now if we
00:46:57
think about what we need to do uh to
00:46:59
cancel out this one here we're going to
00:47:02
take this row times neg1 and add it down
00:47:07
to
00:47:09
here okay and so uh neg 1 * uhga - 1 + 0
00:47:16
is going to be positive 1 -1 * 1 + 0 is
00:47:23
going to
00:47:23
be 1 -1 * 1 + 1 is going to give us our
00:47:28
zero that we want and -1 * 20 + 40 is
00:47:33
going to give us
00:47:35
20 okay so we F finished pivoting there
00:47:38
we now have our standard basis vectors
00:47:41
here here here and here okay um and now
00:47:46
we can read off our new
00:47:49
solution so our new
00:47:55
solution uh reading it off sort of for
00:47:58
our first row corresponds is our
00:48:00
z um z r uh equals
00:48:05
180 second row tells us that XT equal 60
00:48:10
third row tells us that SD equal 20
00:48:15
fourth row tells us that XS = 20 and
00:48:20
then because they're non-basic we know
00:48:22
that um
00:48:24
SF and S are both
00:48:29
zero okay that's our new solution ask
00:48:32
the same question again is it optimal
00:48:34
okay and we're going to scan this top
00:48:36
row there's no negatives so the question
00:48:40
to is it
00:48:43
optimal the answer is
00:48:46
now
00:48:48
yes okay and that's because if we look
00:48:50
at the top row and sort of move things
00:48:52
over to the other side Z is going to be
00:48:55
netive s F minus S C + 180 and so if I
00:49:02
were to increase either SF or SC from
00:49:05
zero both of those would have a negative
00:49:08
effect on Z okay z uh yeah the best we
00:49:12
can do for Z is actually 180 increasing
00:49:15
either of these would uh decrease our
00:49:18
objective
00:49:19
value and so that is our optimal
00:49:22
solution here uh and sort of the end of
00:49:25
the Simplex algorithm okay to wrap this
00:49:28
up I want to kind of pictorially show
00:49:30
you what sort of happened uh in our
00:49:33
feasible region so I'm going to kind of
00:49:35
sketch a quick uh sketch of our feasible
00:49:40
region um let's
00:49:49
see okay not going to be perfectly uh
00:49:53
accurate with this this sketch here um
00:49:55
but we started off uh if we think of our
00:49:58
variables as
00:50:00
Xs and XT and we just sort of plotted in
00:50:04
the original variables we started off
00:50:06
with both Xs and XT at zero and so we
00:50:09
started at0 0 in the original
00:50:12
coordinates um then after one step we
00:50:16
moved to the point where we were at
00:50:21
40 okay and then in another step we
00:50:24
moved up here to where we were at 40 20
00:50:29
and then in the final step we moved up
00:50:31
to here where we are now at
00:50:36
uh no no no
00:50:39
no oh
00:50:42
2060 y so XS is 20 XT is 60 yep yep so
00:50:49
we went from 40 20 to 2060 there yeah
00:50:52
and so uh what the Simplex method does
00:50:55
is it is mov moves us around the
00:50:57
boundary um sort of uh if we had made
00:51:01
the opposite Choice uh in the first step
00:51:04
we actually could have gone from here to
00:51:05
here to here and gotten there in two
00:51:07
steps instead of three steps um but
00:51:09
really you don't know that um from the
00:51:11
beginning and in practice we're dealing
00:51:14
with higher dimensional spaces and it's
00:51:15
more like uh kind of branching uh
00:51:18
through um kind of a bunch of edges on a
00:51:22
hypergraph or something like that but um
00:51:25
visually you kind of want to think about
00:51:26
is that we're moving from here to here
00:51:28
to here each time um because our
00:51:31
objective vector or kind of the director
00:51:34
direction of improvement um was sort of
00:51:36
in the three two was sort of in this
00:51:39
direction here um we were always moving
00:51:42
in a direction that offered us some
00:51:45
improvement
00:51:47
okay uh so that'll wrap up this video uh
00:51:51
the next video we'll sort of talk about
00:51:53
the Simplex method from a bird's eye
00:51:54
view and do some more practice
