It is assumed that you are familiar with the "conventional" Simplex Method --- also known as the Primal Method. If this is not so, consult your OR/MS textbook.
So recall that the Primal Simplex Method conducts a sequence of pivot operations on the Simplex Tableau where we first determine the pivot column using the Greedy Rule, and then the pivot row using the Ratio Test.
The initial tableau of the Primal method has the property that all the right hand side values are non-negativeand this propery remains in tact thoughout the solution process. Indeed, the Ratio Test makes sure that this is so.
The Dual Simplex Method requires the reduced costs of the initial Simplex Tableau to satisfy the optimality criterion, but allows the right hand side values to be negative.
It reverses the process of determining the pivot cell: the Greedy Rule is used to determine the pivot row and the Ratio Test is used to determine the pivot column.
The process terminates when either the Greedy Rule cannot select a new row, in which case an optimal solution has been constructed, or the Test Ratio fails, in which case we conclude that the problem is not feasible.
So all we have to do now is explain how the Greedy Rule and Ratio Test work in the framework of the Dual Simplex Method.
- Greedy Rule:
Select a row whose right hand side (RHS) value is the most negative. Call it i. If all the right hand side values are non-negative, then stop: the current basic solution is feasible and optimal.
- Ratio Test:
Select a column k such that |rc(k)/a(i,k)| = min {|rc(j)/a(i,j)|: a(i,j) < 0, j=1,...,n}, where rc(j) denotes the reduced cost of x(j) and a(i,j) denotes the coefficient of x(j) in row i of the Simplex Tableau and i denotes the row selected by the Greedy Rule. If a(i,j) >= 0 for all j, then stop: the problem is infeasible.To illustrate how the method works, consider the following LP problem:
min 2x + 5y + 6zSince the Dual Simplex Method allows the right hand side values to be negative, we multiply each of the functional constraints by -1 and obtain the following equivalent LP problem:
s.t.
x + 2y + z >= 3
x + 3y + 4z >= 4
x,y,z >= 0min 2x + 5y + 6zThus, the first simplex tableau is as follows:
s.t.
- x - 2y - z <= -3
- x - 3y - 4z <= - 4
x,y,z >= 0
BV x y z s1 s2 RHS s1 -1 -2 -1 1 0 -3 s2 -1 -3 -4 0 1 -4 rc -2 -5 -6 0 0 0 Note that the reduced costs satisfy the optimality conditions for opt=min, hence we can use the Dual Simplex Method.
So we apply the Greedy Rule and identify -4 as the most negative right hand side value. We therefore select the second row of the tableau, i=2, as the pivot row, meaning that S2 will now leave the basis.
We now apply the Ratio Test to decide what variable should enter the basis. So we conduct the Ratio Test on the second row of the tableau:
j 1 2 3 4 5 a(2,j) -1 -3 -4 0 1 rc(j) -2 -5 -6 0 0 R(j) 2 5/3 3/2 * * Since the minimum ratio is attained at column j=3, we let z become the new basic variable.
So we conduct a pivot operation on cell (2,3) of the tableau. This generates the following new tableau:
BV x y z s1 s2 RHS s1 -3/4 -5/4 0 1 -1/4 -2 z 1/4 3/4 1 0 -1/4 1 rc -1/2 -1/2 0 0 -3/2 6 We now repeat the procedure: We apply the Greedy rule and select i=1 as the row with the most negative RHS value.
Next we conduct the Ratio Test on row i=1:
j 1 2 3 4 5 a(1,j) -3/4 -5/4 0 1 -1/4 rc(j) -1/2 -1/2 0 0 -3/2 R(j) 2/3 2/5 * * 6 The smallest ratio is at column j=2, so we now pivit on cell (1,2). This generates the fommowing tableau:
BV x y z s1 s2 RHS y 3/5 1 0 -4/5 1/5 8/5 z -1/5 0 1 3/5 -2/5 -1/5 rc -1/5 0 0 -2/5 -7/5 34/5 We now apply the Greedy Rule select i=2 as the pivot row and conduct the Ratio Test on this row:
j 1 2 3 4 5 a(2,j) -1/5 0 1 3/5 -2/5 rc(j) -1/5 0 0 -2/5 -7/5 R(j) 1 * * * 3 The smallest ratio is at j=1, so we pivot on cell (2,1). The new tableau is:
BV x y z s1 s2 RHS y 0 1 3 1 -1 1 x 1 0 -5 -3 2 1 rc 0 0 1 1 1 7 All the right hand side values are now non-negative so we stop. Thge optimal solution is (x,y,z)=(1,1,0) and the optimal value of the objective function is equal to 7.