In this video, I’ll be solving this minimization LP Problem
using this simplex tableau structure.
One of the solution approaches in solving the minimization problem
is to choose the largest negative value on the cj – zj row to enter the basis (rather
than the largest positive as done in maximization problems).
Another way is to change this cj – zj to zj – cj.
And another way is to convert the minimization problem to a maximization problem by multiplying
the objective function by -1.
And that’s what we’ll do in this video.
So we will be working with this maximization objective
and the constraints will remain the same.
The idea is that making cost as small as possible is equivalent to making profit as large as
possible.
To put this in tableau form, we need the right side of all the constraints to be positive.
Therefore, we multiply the second constraint by -1 to make its right hand positive.
And that also changes the direction of the inequality from a less than to a greater than.
The original minimization problem is now equivalent to this maximization one.
Writing it in standard form, we introduce a slack variable to the first
constraint because it’s a less or equal constraint,
we introduce a surplus variable to the second since it’s a greater or equal constraint,
and the third does not need slack or surplus because it already has equality.
Based on this model, suppose we make x1, x2, and x3 non basic by setting them to zeros,
we will have s1 = 18 and s2 =-14 which poses two problems:
first, s2 violates nonnegativity and second, there is no variable representing the equality
constraint.
These issues prevent us from setting up the initial simplex tableau.
To circumvent them, we introduce what we call artificial variables,
sometimes denoted by lower-case a_i, and sometimes by the upper-case A_i.
In other words, we introduce artificial variables whenever we have a greater or equal constraint,
or whenever we have an equality constraint.
Artificial variables are indeed artificial because they have no real meaning in the problem.
They are essentially used to set up the initial simplex tableau
with a basic feasible solution and they must be eliminated before we reach an optimal solution.
So, the equation of the first constraint stays as is.
No artificial variable required there.
We introduce an artificial variable a2 to constraint 2 equation because it’s a greater
than or equal constraint.
And we introduce another artificial variable a3 to constraint 3 since it’s an equality
constraint.
We denote them a2 and a3 here to match the constraint number.
You may prefer them to be a1 and a2 to indicate the first and second artificial variables
introduced …but it doesn’t matter.
Xxx
Since we don’t want the model to keep the artificial variables in the solution, we include
them in the objective function with a very large negative coefficient or large cost,
which we denoted -M. Note that M is a large positive number.
You can hold a large number in mind like one billion.
And all variables are non-negative.
The problem is now in tableau form.
We begin setting up the tableau with the objective coefficients,
followed by the coefficients in the constraints then their right-hand sides,
that we call the b column.
The basic variables will be the ones with unit columns
-the ones that have a coefficient of 1 in one of their rows while the coefficients of
the other basic variables are zeros on that row.
So s1, a2, and a3 will be our initial basic variables.
And we list their objective coefficients in the cB column here.
The zj values are calculated by taking the sumproducts of the column and each of the
other columns.
For the x1 column, we have 0(2) + (-M)(-1) + (-M)(3) which gives
M - 3M or -2M.
For the rest of the columns, because of the 0 here, we can ignore the first row,
and because these two coefficients are the same,
we can simply add the bottom 2 coefficients and then multiply the sum by -M.
So 1 + 2 = 3 times -M gives negative 3M, then negative 4M
zero positive M
negative M and negative M
For the b column, -14M -26M gives -40M For the cj minus zj row, or what we call the
net evaluation row, we take the objective coefficient row and minus the zj row.
So 6 – (-2M) gives 6+2M Negative 7 –(-3M) gives -7+3M
-4 + 4M 0
-M 0
and 0.
We reach the optimal solution when there are no more positive values on this row.
This setup is called the initial simplex tableau.
The largest positive entry on this net evaluation row determines the new variable entering the
basis.
Since M is a very large positive number, 4M is larger than 3M or 2M, therefore -4+4M is
the largest positive value on this row, this x3 column is the key or pivot column,
and x3 is the new variable entering the basis.
To determine the pivot row, we compute ratios of the b column values to the positive pivot
column values.
The smallest of these ratios determines the pivot row.
If the pivot column has values that are either negative or zero, we will ignore them as we
are only interested in nonnegative ratios.
The first ratio here is 18/-1 which we will ignore since it produces a negative value.
The second ratio is 14/2 which gives 7.
The third ratio is 26/2 which is 13.
The minimum of 7 and 13 is 7; therefore, the key pivot row is the second row and the variable
leaving the basis is a2.
The value at the intersection of the pivot row and pivot column, which is 2 in this case,
is called the key or pivot element.
Moving forward, a2 will be leaving the basis, and because it is an artificial variable which
has no real meaning in the solution, it can be removed from the columns altogether.
So in the tableau setup for the first iteration, a2 has been replaced by the pivot column element
x3 with the objective function coefficient -4.
We begin this first iteration by dividing the pivot row by the pivot element which is
2.
So -1 divided by 2 gives -0.5 1/ 2 gives 0.5
2/ 2 gives 1 0/2 gives 0
-1/2 gives -0.5 0/2 gives 0
And 14/2 gives 7.
Next, we make the initial pivot column a unit column by making all other entries in that
column zeros.
This is done simply by adding or subtracting a multiple of the pivot row.
To make this -1 a zero in the new tableau, we can easily add it to the 1 here…and do
the same for the other elements on that row.
So 2 + (-0.5) is 1.5 5 + 0.5 = 5.5
-1 + 1 = 0 1 + 0 = 1
0 + (-0.5) = -0.5 0 + 0 = 0
and 18 + 7 = 25.
To make this pivot column entry on the third row zero (it is currently 2) we can multiply
this new Row 2 by 2 and subtract the result from the old row 3.
We can also obtain the same result by simply subtracting 2 minus 2 here.
In that case, the operation is old Row 3 minus old Row 2.
For the x1 column, 3 – (-1) = 4 2 – 1 = 1
2 – 2 = 0 0
1 and 1
And for the b column, 26 minus 14 gives 12 Next, we compute the entries of the zj row
using the sumproduct of c_B column and other columns.
Since we have 0 in the top c_B row, multiplying the top row values by 0 will result in zeros.
So we can ignore the first row in calculating the zj values.
For the x1 column, we have (-4)(-0.5) +(-M)(4) which gives 2 – 4M.
Next, -4(0.5) + (-M*1) gives -2-M Next we have -4,
Then 0 2 - M
and -M For the b column we have -28 – 12M.
For the net evaluation row, 6 – (2 - 4M) gives 4 + 4M
-7 – (-2 – M) gives -5+M Then we have 0
0 again -2 + M
and 0 And that completes the first iteration.
Remember that M is a large positive number.
Thus, the largest positive value on the net evaluation row is 4+4M, indicating that the
pivot column is the x1 column and the entering variable is x1.
To determine the pivot row, we calculate ratios by dividing the b column entries by the pivot
column entries.
25/1.5 = 16.7 We skip the second row since its pivot column
entry is negative (we don’t want negative ratios).
For the third row we have 12/4 which gives 3.
The minimum nonnegative ratio is 3, indicating that the pivot row is third row,
the variable leaving the basis is a3, and the pivot element is 4.
For the next iteration, x1 will replace a3 in the basis so we can remove a3 from the
columns because it is an artificial variable that has served its purpose and is no longer
needed in the tableau.
Note that we do this only for artificial variables.
If a non-artificial variable leaves the basis, it is not removed from the tableau.
For the second iteration, we have x1 replacing a3 here with an objective function coefficient
of 6.
The primary goal again is to make the previous pivot column a unit column.
We first make the previous pivot element a 1 by dividing the third row by the pivot element
4.
4/4 = 1 1/4 = 0.25
0 0
0.25 and 3.
To make this 1.5 position zero in the new tableau, we subtract 1.5 times the new Row
3.
So 1.5 – 1.5(1) = 0 5.5 – 1.5(0.25) = 5.125
0 – 1.5(0) = 0 1 – 1.5(0) = 1
-0.5 – 1.5(0.25) = -0.875 and 25 – 1.5(3) = 20.5
And to make this -0.5 zero in the new tableau, we multiply the new Row 3 by -0.5 and subtract
it from the old Row 2.
That is, we take the old Row 2, add 0.5 times the new Row 3, and assign the result to the
new Row 2.
So -0.5 + 0.5(1) = 0 0.5 + 0.5(0.25) = 0.625
1 + 0.5(0) = 1 We have zero here
-0.5 + 0.5(0.25) = -0.375 And for the b column 7 + 0.5(3) = 8.5
For the zj row, we can again ignore the first row since its c_B value is 0.
Hence for the x1 column, -4(0) + 6(1) = 6 -4(0.625) + 6(0.25) = -1
Then we have -4 0
-4(-0.375) + 6(0.25) = 3 -4(8.5) + 6(3) = -16
For the net evaluation row, 6 – 6 = 0
-7 - (-1) = -6 -4 – (-4) = 0
0 – 0 = 0 And -3.
Since there is no positive value in the in the net evaluation row,
the objective function cannot be improved further.
So we have an optimal solution given by x1 = 3
x2 = 0 as it is non-basic, x3 = 8.5,
s1 = 20.5, and s2 = 0 because it is non-basic as well.
The objective function value for the maximization problem
here appears as -16.
But since this is a minimization problem, we multiply it by -1
and that will give an optimal objective function value of +16.
And here are some highlighted events in solving this problem.
1.
Because the problem was a minimization problem, we multiplied the objective function by -1
to convert it to a maximization problem.
2.
Because a constraint has a negative right-hand-side, we multiplied the constraint by -1 to its
the right side positive to be suitable for the initial simplex tableau.
3.
We added artificial variables to “≥” constraint and to “=” constraint again to make them
suitable for the initial simplex tableau.
4.
We set the coefficient of artificial variables to -M in the objective function where M is
a large positive number.
5.
We evaluated the resulting simplex tableau in typical fashion and multiplied the optimal
objective function value in the tableau by -1 to convert it to a minimization objective
value.
And that’s it.
Thanks for watching.