The Dual Simplex Method (Revised Version) - University of …

1 The dual Simplex Method (Revised Version). Again we are only considering Phase II of the dual Simplex Method . So the assumption is that we begin with a basis where the basic solution of the dual problem is feasible. This fact will continue to be true in all subsequent pivots. If we get to a basis where the basic solution of the primal problem is feasible, it will be optimal. I will also assume (for the sake of simplicity) that all sign-free variables are basic and all artificial variables are nonbasic. Then the only consideration we have to give to these is that sign-free variables are ignored when we look for candidates to leave the basis, and artificial variables are ignored when we look for candidates to enter the basis. Just as in the ordinary Revised Simplex Method , we will keep B 1 and from one iteration to the next.

2 Here is the procedure. 1. Find a basic variable (not sign-free) whose entry in is negative. This will be the leaving variable. Usually we take the one with the most negative value (corresponding to the largest- coefficient rule). If there is no leaving variable, stop: the current basic solution is optimal. 2. Calculate yT = cTB B 1 and tTN = yT AN cTN as in the ordinary Revised Simplex Method . 3. If the leaving variable is the i'th in the basis, let w T be the i'th row of B 1 , and vN. T. = w T AN . Calculate the ratios yi /wi and tj /vj corresponding to non-artificial nonbasic variables with negative entries in w or v. The entering variable is one with the minimum ratio. If there are no ratios to calculate, because there are no such negative entries, then the problem is infeasible. 4. Pivot, with the entering variable entering and the leaving variable leaving the basis.

3 To update B 1 and , we first calculate d = B 1 Ae , where Ae is the column of A or I corresponding to the entering variable. Then we can do the updating of and B 1 as in the ordinary Revised Simplex Method . Worked Example: maximize x1 2x2 x3. subject to 3x1 x2 x3 3. x1 4x4 2. 3x1 + 2x2 + x3 + 2x4 6. all variables 0. This is the same example I used in the on-line notes on the dictionary version of the dual Simplex Method . You might find it helpful to compare the progress of the Revised Method here with what happened in the dictionary Method .. s1 3. The initial basis is s1 , s2 , s3 , with B 1 = I, = b = s2 2 . yT = [0, 0, 0] and s3 6. x1 x2 x3 x4. tTN cTN.. = = 1 2 1 0 . Note that we do have a feasible basic solution for the dual problem, but not for the primal. We choose s 1 as the leaving variable since it has the most negative entry in.

4 X x2 x3 x4. 1 . 3 1 1 0. wT = [1, 0, 0] is the first row of B 1 . vN. T. = wT AN = [1, 0, 0] 1 0 0 4 =. 3 2 1 2. x1 x2 x3 x4.. 3 1 1 0 . The ratios are 2/1 for x2 and 1/1 for x3 . Having the minimum ratio, x3. enters. x3.. 1 1. d = B 1 0 = 0 . 1 1.. 1 1 0 0 3 1 1 0 0 3 1 0 0 x3 3. 0 0 1 0 2 0 0 1 0 2 so B 1 = 0 1 0 , = s2 2 . 1 0 0 1 6 0 1 0 1 3 1 0 1 s3 3. Having the only negative entry in , s2 will leave. x x2 x4. 1. x1 x2 x4.. 3 1 0. yT = [ 1, 0, 0]B 1 = [1, 0, 0] and tTN = yT 1.. 0 4 [ 1, 2, 0] = 4 1 0 . 3 2 2. x1 x2 x4. T T T.. We have w = [0, 1, 0], the second row of B , and v = w AN =. 1. 1 0 4 . The only ratio to calculate is 0/4 = 0 for x 4 , so x4 enters. x 4 . 0 0. d = B 1 4 = 4 . 2 2 . 0 1 0 0 3 0 1 0 0 3 1 0 0. 4 0 1 0 2 1 0 1/4 0 1/2 so B 1 = 0 1/4 0 , =. 2 1 0 1 3 0 1 1/2 1 2 1 1/2 1.. x3 3. x4 1/2 . s3 2.

5 Since no variable needs to leave the basis, we now have an optimal solution: x 1 = x2 = 0, x3 = 3, x4 = 1/2, s1 = s2 = 0, s3 = 2, z = cTB = 3.