Welcome to a lesson on how to use
the simplex method to solve a standard minimization problem.
A standard minimization problem has nonnegative variables,
and all the constraints are in this form here,
where they are greater than or equal to N,
and N is nonnegative.
Before we look at our example though,
let's review the transpose of a matrix.
A matrix formed by making the rows of a given matrix
the columns of a new matrix is transposing a matrix.
The new matrix, using this notation here,
is called the transpose of matrix A, or the given matrix.
As an example, if this is matrix A,
this would be the transpose of matrix A.
Notice how row one becomes column one,
and row two becomes column two.
To solve the standard minimization problem,
we reconstruct the standard minimization problem
into a standard maximization problem
by converting it to what's called a Dual Problem.
Then we solve the dual problem using the Simplex Method.
The original minimum problem is called the primal problem,
and the corresponding maximum problem
as mentioned before, is called the dual problem.
The maximum of the dual problem
is also the minimum of the primal problem,
however, the point at which they occur will be different.
The solution to the maximum problem
is found in the last column, as we already know,
but the solution to the minimum problem
is found in the last row of the same tableau.
Let's look at an example, and take this step by step.
Here's our given standard minimization problem.
Step one, we want to build a matrix out of the constraints
and the objective function without slack variables.
So we'll be using these first two inequalities,
and our objective function
to create a three by three matrix.
And the entries will be the coefficients
from our inequalities and equation.
So we'll only be using these first two constraints,
so looking at the coefficients,
we would have one, two, four,
which make up the first row of our matrix.
Looking at the second inequality,
we have seven, six, 20, which make up the second row,
and then for our third row, we use our objective function,
but we do want to change the order here,
this is equivalent to 14 s plus 20 t equals C,
so the coefficients are 14, 20, and one,
which we see here in our third row.
Step two, we want to find the transpose of this matrix,
so if this is matrix A,
this would be the transpose of matrix A.
Again, notice how row one becomes column one,
row two becomes column two,
and row three becomes column three.
This is the matrix that we'll use
to set up the corresponding maximum problem,
or the dual problem.
Step three, rewrite the constraints and objective function
using this new matrix, which will give us our dual problem.
So these first two rows will give us our constraints,
the third row will give us the objective function.
So our first row will give us the constraint
one x plus seven y less than or equal to 14,
which we see here, notice how
because it's a maximum problem,
the inequalities are less than or equal to.
The second row gives us the inequality
two x plus six y less than or equal to 20,
and our last row gives us the objective function
four x plus 20 y equals, let's say one P,
or we can just say P equals four x plus 20 y.
And now from here we solve this
using the simplex method as we normally do,
so the next step, we write the constraints as equations,
and set the objective function equal to zero,
to form the initial tableau.
Looking at our first constraint, we have the equation
x plus seven y plus s equals 14,
where s is our slack variable.
Second equation would be two x plus six y plus t equal 20,
where t is our slack variable,
and then setting our objective function
equal to zero, we'd have the equation
negative four x minus 20 y plus P equal zero.
To set up the initial tableau,
we label the columns with the variables used,
x, y, s, t, and P, and now we find the coefficients
from the first, second, and third equations
to complete the tableau.
We have one x plus seven y plus one s equals 14,
so the coefficients for t and P are both zero.
The second equation we have two x plus six y,
there's no s term, coefficient of t is one,
there's no P term, and it equals 20.
For the third row we have negative four,
negative 20, there are no s and t terms,
so zero, zero, one, and zero.
So this is our initial tableau,
and we have these variables on the far left,
which indicate the basic or active variables,
which are the columns that contain
only a one and zeros, which are s, t, and P.
And we'll change these
as the active or basic variables change.
So here's our same tableau,
to solve this using the simplex method,
we want to identify the pivot column,
which is the column with the most negative entry
on the left of the bottom row,
which would be this column here.
So this is the pivot column,
to find the pivot row, and identify the pivot,
we form ratios using the constants on the far right,
and divide by the corresponding
nonnegative entries from the pivot column.
So we have 14 divided by seven, that's two,
and 20 divided by six, which is 10/3,
the smallest ratio indicates the pivot row.
10/3 is about three point three, so two is smaller,
so this would be the pivot row,
making seven our pivot.
So now we want to make the pivot equal to one,
and the remaining entries in this column equal to zero.
So if we wanted this entry to be one,
we have to replace row one with 1/7 times row one,
which I've already done to save some time.
This row one came from finding the product of
1/7 and the original row one.
So here's our pivot and now we want
six and negative 20 to be zero.
So if we want six to be zero,
we'll perform a row operation using row one,
we can replace row two with
negative 1/6 times row one plus row two,
and to make negative 20 equal to zero,
we could replace row three with,
20 times row one plus row three.
Notice once we perform these row operations,
y will be active and s will become inactive or non basic,
so we'll label row one with y.
I'm going to go ahead and show how to perform
these two row operations on the calculators,
of course we could do them by hand,
but then after this, I'll assume we can perform
the needed row operations.
So we first have negative six times row one plus row two,
so we enter negative six, second open parenthesis,
we enter the entries in row one separated by commas,
so we have 1/7 comma one comma 1/7
comma zero comma zero comma two
second closed parenthesis and then plus row two,
so plus second open parenthesis two comma six
comma zero comma one comma zero comma 20
second closed parenthesis Enter.
We want fractions not decimals
so we press Math Enter Enter,
we record our new entries.
And now we're going to replace row three with
20 times row one plus row three,
so 20 times row one again,
so 1/7 comma and so on,
so there's 20 times row one plus row three
so we have negative four comma negative 20
comma zero comma zero comma one comma zero
and Enter, and Math Enter Enter.
These are the new entries for row three.
Notice how this is not the final tableau
because we still have this negative value
here in the third row on the left side.
So now we'll take this tableau, find the pivot,
and perform another pivot operation,
so the first column is the pivot column,
and now we'll find our ratios to determine the pivot row,
so first row we have two divided by 1/7,
which is two times seven or 14,
the second row we have eight divided by 8/7,
which equals eight times 7/8, which is seven,
the smallest ratio is seven,
and therefore the pivot row is row two,
so now our pivot is 8/7, so we want 8/7 to be one,
the remaining entries in this column to be zero.
So to make 8/7 equal to one, we multiply row two
by the reciprocal of 8/7, which is 7/8,
so we replace row two with 7/8 times row two,
and again, to same some time I've already done this.
Of course I encourage you to verify this,
but I have one, zero, negative 3/4,
7/8, zero, and seven.
Now that our pivot is equal to one,
we want the remaining entries in this column to be zero,
we want 1/7 to be zero, and negative 8/7 to be zero.
Notice once we do this, x will be active,
and t will no longer be active.
So to make this 1/7 equal to zero, we can replace row one
with negative 1/7 times row two plus row one,
so we'll replace row one with
negative 1/7 times row two plus row one,
and then to make negative 8/7 equal to zero,
we could replace row three with
8/7 times row two
plus row three,
and again, to save some time I've already done this,
which I would encourage you to verify,
for row one I have zero, one, 1/4,
negative 1/8, zero, one,
for the new row three I have zero, zero, two, one, one, 48.
Notice how I relabeled row two with x,
our new active or basic variable.
So here's our final tableau which we know
because looking at the last row,
there are no negatives on the left side.
So from this tableau, the solution to the minimum
will appear in the last row
of the slack variables, here and here,
the minimized objective function value
will appear in the last row, last column
of this tableau, which is 48.
This will be the same maximum of the dual problem.
So let's summarize this on the next slide.
Again, here was the original
primal problem or minimization problem,
and looking at the final tableau from the dual problem,
we can find the solutions to both
the dual problem and the primal problem.
For the primal problem, the minimum of C is 48,
and that occurs when s equals two and t equals one,
let's go ahead and record that,
the minimum is C equals 48
at the point s comma t or two comma one,
and for the dual problem,
or the maximization problem for review,
the maximum is also 48, but looking at the active variables,
this occurs when one y, or y equals one,
and one x, or x, equals seven,
so here we have the max of P equals 48
at x comma y, or seven comma one.
Now before we go, I do want to take a look
at solving divisional minimization problem graphically.
If we graph the constraints,
this would be the feasible region,
and then we would test the corner points or vertices
of this region to determine the minimum
of the objective function.
Notice how the vertices are zero comma 10/3,
two comma one, and four comma zero.
I've already performed the substitution here below,
and notice how this does verify our results
that we found using the simplex method.
The minimum of C is 48, and it occurs at the point
two comma one, or when s equals two, and t equals one.
I hope you found this helpful.