Welcome to an introduction
to the simplex method.
In this lesson we'll solve a standard maximization problem
using the simplex method.
A standard maximization problem is a problem
where all of the variables are nonnegative
and all the constraints have this form here
where they're less or equal to N and N is nonnegative.
I outline nine steps to apply the simplex method
for standard maximization problems.
We'll go through each step looking at a basic example.
But before we do this, I do want to define
active and inactive variables.
Active or basic variables correspond to columns
that contain only one and nonzero entries.
Inactive or nonbasic variables correspond to columns
that don't contain only one and nonzero entries.
This is important because when applying the simplex method,
we can look at the completed tableau to determine
the value of the active variables,
all of the inactive variables will be equal to zero.
So to keep track of the active variables,
we label each row with the name of the corresponding
active or basic variable.
If we didn't do this, we could determine them at the end,
but I'm going to keep track of them as we go.
So here's our standard maximization problem.
We have the objective function we're trying to maximize,
and we have our constraints.
Notice how the last two just confirm
that x and y are nonnegative.
We won't be using these to perform the simplex method.
So step one, we want to convert these first two inequalities
to equations using slack variables.
So if two x plus y is less than or equal to five,
there must be some value which we'll call s,
so we can make the left side equal to five,
which means we can write an equation two x plus y
plus some value s would have to be equal to five.
Now leaving some space here horizontally,
because we'll have other variables,
we want the like terms to line up vertically.
For the second inequality, we have two x plus y
is less than or equal to four.
So on the left we could add another value, we'll call it t.
So that x plus two y plus t
would be equal to four,
not less than or equal to four.
Now for the third equation, we'll go to step two.
We're going to set the objective function equal to zero.
So looking at the objective function,
we want p to stay positive,
so we'll subtract the x and y terms on both sides
which will give us negative two x minus five y plus p
equals zero.
Now we're almost ready to set up
the simplex table or tableau,
before we do this, though, I am going to change the form
of these equations slightly.
Let's include every variable in every equation.
So we'll write the first equation as two x plus one y
plus one s plus zero t plus zero p equals five.
Second equation we'll write one x plus two y plus zero s
plus one t plus zero p equals four.
Third equation negative two x minus five y plus zero s
plus zero t plus one p equals zero.
We'll be using all of these constants in our tableau.
So to set up the tableau given here,
we first label the columns with the variables used,
x, y, s, t, and p.
Our first row, again will be the coefficients
from the first equation.
So notice how we have two, one, one, zero, zero, five,
two, one, one, zero, zero, five.
Next we have one, two, zero, one, zero, four.
And finally we have negative two, negative five,
zero, zero, one, zero.
So negative two, negative five, and so on.
The last thing we want to do is label the active variables
here on the left which would be the columns
that only contain one and zeroes.
So that would be s, t, and p.
So they are listed here.
Again, this is optional, but I do like to show this.
Now I should mention these tableau does represent
one possible solution to our problem.
This one would just not be the maximum p.
For example, we could read off the values
of the active variables from the table.
The way we do this, looking at this column for s,
notice how it's active, so one s equals five,
so s equals five.
Looking at the column t, one t equals four.
So t equals four.
And looking at the column p, one p equals zero,
so p equals zero.
So remember the inactive variables,
which would be x and y, would be equal to zero.
So when x and y are equal to zero, the constraints are met,
but notice how the profit would be zero.
So to find a better solution, we apply the simplex method.
So here's the same tableau.
Step four, we want to select the pivot column.
This is the column with the most negative number
on the left side of the bottom row.
If the number's the most negative, it would be the most left
on the number line.
So notice how this'd be the pivot column,
because negative five is the most negative number
along the left of the bottom row.
Step three, we want to select the pivot row.
To do this we divide each entry in the constant column
by the corresponding positive entry in the pivot column.
The smallest ratio indicates the pivot row.
So we're only concerned about the first and second row.
So five divided by one is equal to five
and four divided by two equals two.
The pivot row will never be this last row.
So the smallest ratio is two,
which means this is a pivot row.
Step six, we select the pivot which is the entry
in the pivot column and the pivot row.
However the pivot must be positive.
Notice in this case it would be positive two.
Now that we have the pivot,
we'll be pivoting around this entry.
So here's the same tableau, here's our pivot,
so now we're on step seven.
We perform row operations to make the pivot equal to one,
and the remaining elements
in the pivot column equal to zero.
So we want this to be a one,
we want this one and this a negative five to be zero.
I should mention that some textbooks
don't make the pivot equal to one,
which is okay, but then there's extra steps later.
So let's begin by making the pivot equal to one,
by performing a row operation.
So we'll replace row two with 1/2 times row two,
that's 1/2 times two equals one.
I've already done this here.
I've replaced row two with 1/2 times row two.
Notice 1/2 times one is 1/2, 1/2 times two is one,
still our pivot.
1/2 times zero is zero,
1/2 times one is 1/2,
1/2 times zero is zero,
1/2 times four equals two.
Next we want this entry and this entry to be zero.
Let's do this on the next slide.
So again, here's the tableau from the previous slide.
If we want this entry to be zero,
we could replace row one with row one minus row two.
Let's go ahead and do that.
We'll replace row one
with row one minus row two.
And to make this entry zero,
we could take row three and add five times row two.
Let's perform this row operation by hand.
We'll perform this row operation on the calculator.
So here we'd have two minus 1/2 that's 4/2 minus 1/2 or 3/2.
One minus one is zero.
One minus zero is one.
Zero minus 1/2, negative 1/2.
Zero minus zero, and five minus two is three.
Now again, we could do this by hand,
but I do want to show how we can do
this row operation on the calculator.
There's a couple ways to do this on the calculator.
I'm going to go ahead and do this from the home screen.
So to enter a row, we don't use the parentheses.
So I'm going to press 2ND, open parenthesis,
enter row three, so negative two, comma negative five,
comma zero,
comma zero, comma one,
comma zero, close it.
So there's row three.
And then plus five times row two.
So open squiggly bracket, 1/2,
comma one, comma zero,
comma 1/2,
comma zero,
comma two.
And close it.
Press ENTER, now it's giving us a decimal form,
we want the fraction form,
so we'll press MATH, ENTER, ENTER.
So we 1/2, zero, zero, 5/2, one, 10.
We could've just easily done that by hand,
but when there are a lot of fractions involved,
using a calculator is a nice way not to make a mistake.
Now in performing these row operations,
notice how t is no longer active,
this column no longer contains one and zeroes.
The new active variable would be y.
So we replace this t with y.
Another way to see this would be
to look at the row and column of our pivot.
Notice how it's in row t and column y,
so t is the exiting variable,
and y is the entering variable.
So we replace the t with the y.
Now to take this tableau onto the next slide,
step eight says to repeat by identifying
the most negative entry on the left in the last row.
But there aren't any, they're all positive,
which actually means we're done.
Step nine, once the left side of the last row
is all nonnegative, the solution can be found.
The value of each row variable or active variable
is equal to the right most entry in the row.
All inactive variables equal zero.
So looking at the tableau, notice how s is active
which means one s or s equals three,
and looking at the column y, y is active,
it's also labeled here, one y equals two.
So we know that s equals three,
y equals two,
and also p is active, p equals 10.
Which means the maximum of p under these constraints is 10.
Remember all inactive variables are equal to zero,
so t equals zero and x equals zero.
So to summarize we could say the maximum of p is 10 at
zero comma two.
Now this is a very straightforward example.
Many times we do have to repeat the process
because after pivoting once,
we still have negatives on the left in the bottom row.
Now if we compare this to how we solved a similar problem
using linear programming, we would've graphed
the feasible region on the coordinate plane
because our constraints are inequalities in two variables,
we would've found the vertices, one, two, three, four,
so divides into p, which I've shown here.
Notice how we get the same solution.
The max is 10 at zero comma two.
When we apply the simplex method,
the algorithm begins at a vertex, let's say here,
and moves along the edges of the polytope
until it reaches the vertex of the optimum solution.
I hope you found this helpful.