REVISED SIMPLEX METHOD We have implemented the simplex algorithm by using the Tableau to update the information we proceed along the various steps. For problems with only a few variables the simplex method is efficient. However, problems of practical interest often have several hundred variables. The tableau method is hopeless for problems containing more than a few variables. We are in fact calculating AB-1aj for all j as well as calculating all components of the relative cost coefficient r, albeit in an fairly automatic manner. However, we really need to know only one component rj of r, one row AB-1aj of the Tableau †(B), and the column constant AB-1b of the Tableau in order to pass to the next basic index set B. The goal of the revised simplex method is the ordering of all calculations so that no unnecessary calculations are performed. No new theory will be need. The simplex algorithm exactly as written in an earlier chapter will be implemented. The implementation will avoid all unnecessary calculations and will try whenever possible to update any available information. The Simpex Algorithm (Theoretical Foundation) 1. 2. Start with some basic index set B1 = {i(1), i(2), … ,i(m)}. Compute a coefficient of the relative cost coefficient rj = cj - cBAB-1aj for B1 until some index j with rj > 0 is found. (i).If all rj ≤ 0, termination phase has been reached. (ii).Only those j M N1 are candidates 3. Find AB-1aj = aj and AB-1b = b and compute the allowable ratios of the jth column , viz., bi/aij for those i with aij > 0. (i). If there are no allowable ratios, then a termination phase has been reached. 4. 5. 6. Find an index k where the minimum ratio is attained. Add j to the basic index set and delete i(k) to get a new basic index set B2. Go back to step 2). Minimal Needed Information to Implement the Simplex Algorithm 1. B (Basic Index Set) (The Simplex Multiplier) (jth column of the Tableau) (constant column of the Tableau)

2. cBAB-1 3. AB-1aj 4. AB-1b 5. Ratios of 3) and 4)

Revised Simplex Method page 1

Computation Aids (Basic Index Heading) It is easier to insert the entering basic index at the end of the basic index set and to remove the exiting basic index from the place it is found. In order to keep track of the basic indices as they appear in the matrices we introduce the notion of a basic index heading. Definition. Let B be a basic index set with m indices; a basic index heading is an m-tuple H = (h(1),h(2),.....,h(m)) such that B = { h(1), h(2), … , h(m) }. Here note that we are no longer assuming that h(1) < h(2) < … < h(m). We still continue to use the notation {i(1), … , i(m)} for a basic index set with the assumptions i(1) < … < i(m) (i.e., the i-index set is ordered according to its natural ordering while the h-index set is ordered to some assigned ordering). The basic index heading is a basic index set with a preferred ordering not necessarily the natural ordering of the integers. Notation Let H = (h(1), h(2),....., h(m)) be a basic index heading for the LP: Min { c.x | Ax = b, x ≥ 0} where A is a m x n matrix. Then AH will denote the matrix A H = [a h(1) , ah(2) , … , ah(m) ], cH will denote the m-tuple cH = (ch(1), ch(2), … , ch(m)), and (aj)H will denote the m-tuple (column vector) (aj)H = (ah(1), ah(2), … , ah(m))T. Here aj is the jth column of A. Proposition. Let H = (h(1), h(2), … , h(m)) be a basic index heading for the basic index set B = {i(1),i(2), … , i(m)} for the LP: Min { c.x | Ax = b, x ≥ 0} . Let AB -1 a j= a′j, AB -1 b = b′, A H -1 a j = a′′j, and AH -1 b = b′′. Then (i) cHAH-1 = cBAB-1 , (ii) the sets of ratios for B and H are equal, i.e., S = { (b′i/a′ij) | a′ij > 0, i ∈ {1, … , m} } = { (b′′i/a′′ij) | a′′ij > 0, i ∈ 1, … , m} }, and (iii) if a′′kj > 0 and (b′′k/a′′kj) = min { (b′′i/a′′ij) | a′′ij > 0, 1, … , m} }, then h(k) leaves H in an iteration of the simplex algorithm Proof.(i). We have that there is a σ ∈ ℘(m) such that h(s(k)) = i(k) for k = 1, … , m. Here σ simply returns the basic heading set to its natural ordering, i.e., AB = AHPσ. In fact, multiplication of AH on the right by the permutation matrix Pσ interchanges the columns of AH so that the kth column of the product AHPσ is the column that occupied the σ(k)th column of AH. The σ(k)th of AH was occupied by ah(σ(k)). However, we have that h(σ(k)) = i(k). So the kth column of the product AHPσ is occupied by ai(k), the kth column of AB. So we have shown that the kth of both AB and AHPσ coincide and thus

Revised Simplex Method page 2

A H Ps = [ah(1), ah(2), … , ah(m)]Pσ = [ah(σ(1)), ah(σ(2)), … ,ah(σ(m))] = AB . Now we have that cH Pσ = cB . The proof just given actually includes this statement as well. Then we have that cBAB-1 = (cHPσ)(AHPσ)-1 = cHPσPσ-1AH-1 = cHAH-1.

Proof (ii). We have that multiplication on the left by Pσ-1 for the same σ as part (i) changes the rows by σ. Hence, multiplication on the left by Pσ-1 changes the rows by σ. Thus, we get that (a′1j, … , a′mj)T = AB-1aj = (AHPσ)-1aj = Pσ-1AH-1aj = Pσ-1(a′′1j, … , a′′mj)T = (a′′σ(1) j, … , a′′σ(1) j)T and (b′1j, … , b′mj)T = AB-1bj = (AHPσ)-1bj = Pσ-1AH-1bj = Pσ-1(b′′1j, … , b′′mj)T = (b′′σ(1) j, … , b′′σ(1) j)T

Since the sets {σ(1), … , σ(m)} and {1, … , m} are equal, we have that

{ (b′i/a′ij) | a′ij > 0, i ∈ 1, … , m} } = { (b′′σ(i)/a′′σ(i) j) | a′′σ(i) j > 0, i ∈ 1, … , m} } = { (b′′i′/a′′i j) | a′′i j > 0, i ∈ 1, … , m} } Proof (iii). We have that b′i = b′σ(i) and a′ij = a′′σ(i) j as above. Suppose a′′kj > 0 and (b′′k/a′′kj) = min { (b′′i/a′′ij) | a′′ij > 0}. Then a′′kj > 0 and (b′σ-1(k)/a′σ-1(k) j) = min { (b′σ-1(i)/a′′σ-1(i) j) | a′′σ-1(i) j) > 0}. So i(σ-1(k)) exits B and the corresponding index i(σ-1(k)) = h(σ(σ-1(k)) = h(k) exits H. Q.E.D.

This Proposition shows that we can revise the list of minimal information necessary to run the simplex algorithm to the following list. Revised Minimal List Needed to Implement the Simplex Algorithm. 1. H 2. cH AH -1 3. AH-1aj 4. AH-1b 5. Ratios of 3) and 4) (Basic Heading Set) (The Simplex Multiplier but now in terms of H) (jth column of a "twisted" Tableau) (constant column of the "twisted" Tableau)

Revised Simplex Method page 3

We can now see that our main problem is calculating AH-1. We try to avoid this by calculating AH-1 as infrequently as possible. We use the update procedures developed in a previous chapter. We put the important new procedures in italics. Method I for Computing Need Information (η-Factorization Method) 1. Find an initial basic feasible index set

B = H = H1 = {h(1), … , h(m)} with h(1) < … < h(m) as usual. Find AH-1 by some method. 2. Calculate the simplex multiplier cHAH-1 by direct multiplication. 3. Calculate ( cHAH-1)aj for some j ∉ B. If possible, choose a j that produces an easy calculation. Note that this is just a dot product once cHAH-1 is known. 4. Calculate rj = cj - ( cHAH-1)aj. If rj ≥ 0, proceed to calculate a second term rj′ for j′ ∈ H. Continue until the first strictly negative coordinate of the relative cost coefficient with respect to H is found or until a termination phase is reached. 5. If rj < 0, then proceed to calculate the ratios based on the jth column.Calculate the ratios by finding AH-1aj and AH-1b directly. 6. From 5) identify the entering index j = j1 and the leaving index i(k) and leaving variable. 7. Form the new Heading Set H2 =(h(1), , h(k-1) ,j, h(k+1), … , h(m)}. Notice that entering index j goes into the heading set in the same place that the exiting index i(k) vacates. 8. Find AH -1 as AH -1 = Ei(k)(AH-1aj) -1AH-1 as we showed in the Chapter on Matrices (p.VIII.8). Find the 2 2 the inverse of the h-matrix by inspection. Note that AH–1aj has been found in 5) and does not have to be calculated again. Do not multiply the product AH -1 =Ei(k)(AH-1aj)-1AH-1. 2 This would destroy the benefit of the h-matrix which has a lot of zeros. Alternately, use substitution to solve Ei(k)(AH-1aj)-1x =y. 9. Continue the calculations: Each time the entering index will repace the exiting variable in the basic index heading so that the update will be of the form -1 -1 -1 -1 -1 -1 -1 -1 -1 A A aj A aj A = Ej … Ej A aj A = Ej . Hn Hn - 1 H1 n - 1 Hn n - 1 n - 1 Hn - 1 n ± 1 1 H 1 11 Never multiply out the η-file. Also substitution may be used instead of the inversion of the η-matrices. 10. Remember that simplex multipliers, and ratios are computed in the form cHAH-1, AH-1a, AH-1, respectively.

Revised Simplex Method page 4

Computer Implementation η - factorization 1. Store an h-matrix Ej(a) as the tuple (j;a) since all other items can be supplied as needed. 2. The set of h-matrices is called the h-file. If several iterations are needed, the h-file produces a substantial error. The matrix AH-1 is recalculated at this stage from the heading H. Method II for Computing Needed Information LU Method 1. Find initial basic feasible index set B = H = {i(1),...,i(m)} by some method. 2. Factor AH by the LU method as LkPk....L1P1AH = Um....U1. 3. Compute cHAH-1 in the following way as Backward and Forward Substitution for Right Multiplication. The inverse AH-1 is given by AH-1 = U1-1…Um-1LkPk…L1P1 since AH-1P1-1L1-1…Pk-1Lk-1 = U1-1…Um-1. Then cH. AH-1 = cH U1-1…Um-1LkPk…L1P1 is calculated as the iteration for ym given by y1U 1 = cH y2U 2 = y2 … ym U m = ym - 1 followed by the multiplication by LkPk....L1P1 on the right to give cHAH-1 = ym LkPk…L1P1. The matrices U1,...,Um are h-matrices and calculating the inverse is done by substitution rather than inversion. The term cHAH-1 = ym LkPk…L1P1 is calculated from ym be multiplication by the matrices Lk,Pk, … , L1, P1, which is easy to implement due to the nature of the matrices. 3. Calculate (cHAH-1)aj for some j µ H. Again this is just a dot product. 4. Calculate rj = cj - ( cHAH-1)aj. 5. If rj < 0, then proceed to calculate the ratios based on the jth column. Calculate the ratios by finding AH-1aj and AH-1b again by Backward and Forward Substitution. Since multiplication by AH-1 is on the left, the substitution is a little different from 2). Substitution for Left Multiplication. As in 2), the inverse AH-1 is given by AH-1 = U1-1.…Um-1LkPk…L1P1. Thus, for any d ∈ ℜm, the inversion AH-1d is calculated as follows:

Revised Simplex Method page 5

d′ = LkPk....L1P1d d′ = U 1 y 1 y 1 = U2 y 2 … y m - 1 = Um y m , where the d′, y1, … , ym are the successive vectors that are computed by backward substitution (since the matrices Ui are upper triangular h-matrices). As before, we perform the multiplication LkPk…L1P1d in the usual way as 2k matrix multiplications to take advantage of the simple form of the factors (i.e., we never actually compute the product LkPk…L1P1 since some of the operations are just interchanges of multiplications by very simple lower triangular matrices. All this would be lost if we computed one grand product LkPk…L1P1.) Now we continue as before. If rj ≥ 0, proceed to calculate a second term rj for j ∉ H. Continue until the first strictly negative coordinate of the relative cost coefficient with respect to B is found or until a termination phase is reached. 6. From 5) identify the entering index j = j1 and the leaving index i(k) and leaving variable. 7. Form the new Heading Set H2 =(i(1), … , i(k-1),i(k+1), … , i(m), j). Notice that the entering index goes in the last position of the heading and all indices from the exiting index to the end of the tuple for the heading move forward one coordonate position so that a vacant space appears in the last coordinate to receive the entering index . 8. Form the new Heading Set H2=(h(1), … , h(k-1), h(k+1), … , h(m), j) . Notice that the entering index goes in the last position of the heading and all indices from the exiting index to the end of the tuple for the heading move forward one coordonate position so that a vacant space appears in the last coordinate to receive the entering index. 9. Refactor AH according to the LU Update Theorem and return to step 2). 2

Method III for Computing Needed Information. LU Method with Modified Update

1 to 6

Same as Method II

7. Form the new Heading Set H2 =(h(1), … , h(k-1), j, h(k+1), … , h(m)). Notice that the entering index is inserted at the same point from which the exiting index departs. 8. Refactor AH using η-matrices as follows: 2 AH = AH Ej(AH-1aj) 2 and LkPk....L1P1AH = LkPk…L1P1AH Ej(AH-1aj) = Um…U1Ej(AH-1aj). 2 9. Return to 2) and continue. Use backward and forward substitution with the new factorization.

Revised Simplex Method page 6

Example: Revised Simplex Method with η-Factorization. We work the following example using η-factorization: Minimize -3x1 - 2x2 -4x3 Subject to x 1 + x 2 + 2x 3 ≤

+ 3x 3 ≤ 2x 1 2x 1 + x 2 + 3x 3 ≤ x 1 , x2 , x3 ≥ 0.

4 5 7

Since the revised simplex method simply presents a way of implementing the calculations for the simplex method without use of the tableau, we have to set the problem in canonical form as Minimize -3x1 - 2x2 -4x3 Subject to x 1 + x 2 + 2x 3 + x 4 2x 1 + 3x 3 + x5

≤ ≤ + x6 ≤

4 5 7

2x 1 + x 2 + 3x 3

x 1 , … , x6 ≥ 0. We now proceed along the steps outlined previously for Method I. 1. The initial basic feasible index set is {4, 5, 6} We set the initial heading set H = H1 equal to the 3-tuple (4, 5, 6). Then we have that

100 A(H1) = AH = 0 1 0 001

= Ι.

We have to calculate A(H1)-1 by some available means, which is not specified as part of the h-factorization method. Here we get A(H1)-1 = I. We can obtain this by inspection.2. We calculate the simplex multiplier cHAH-1 = c(H1)A(H1)-1 by direct multiplication as c(H1)A(H1)-1 = (0,0,0)Ι = (0,0,0). 3. We calculate cHAH-1a1 = 0. 4. We calculate c1 - cHAH-1a1 = c1 - c(H1)A(H1)-1a1 as c1 - c(H1)A(H1)-1a1 = -3 -0 = -3 < 0. Thus the index 1 can enter the H1. 5. We calculate the ratios of the first column:

100 -1a1 = 0 1 0 A(H1) 001 and 1 1 2 = 2 2 2

100 A(H1)-1b = 0 1 0 001
The ratios are 4/1, 5/2, 7/2.

4 4 5 = 5 7 7

6. The conclusion is that 1 enters the heading set and 5 leaves the heading set.

Revised Simplex Method page 7

7. The new heading set is H2 = ( 4, 1, 6) since 1 is brought into the tuple as a replacement for 5. 8. The new η-factorization is
-1

110 A(H2)-1 = E2(A(H1)-1a1)-1A(H1)-1 = 0 2 0 021

100 010 = 001

1 -1/2 0 0 1/2 0 0 -1 1

.

Now we return to Step #2 and find the new simplex multiplier. We write down the steps. c(H2) = (c4, c1, c6) = (0, 3, 0), c(H2) A(H2)-1 = (0, 3, 0)

1 -1/2 0 0 1/2 0 0 -1 1

= (0, 3/2, 0) ,

r2 = c2 - c(H2) A(H2)-1a2 = -2 - (0, 3/2, 0) (1, 0, 1)T = -2 < 0 CONCLUSION: 2 enters H2. A(H2)-1b =

1 -1/2 0 0 1/2 0 0 -1 1

4 3/2 5 = 5/2 , 7 2

A(H2)-1a2 =

1 -1/2 0 0 1/2 0 0 -1 1

1 1 0 = 0 . 1 1

Ratios = (3/2)/1, 2/1 CONCLUSION: the first index h(1) = 4 exits and 2 enters and H 3 = (2, 1, 6), A(H3)-1 = E1(A(H2)-1a2)-1 E2(A(H1)-1a1)-1A(H1)-1
-1

100 = 010 101 and the new η file is

1 -1/2 0 0 1/2 0 0 -1 1

=

1 0 0 0 1 0 -1 0 1

1 -1/2 0 0 1/2 0 0 -1 1

1 0 0 0 1 0 , -1 0 1
Then we get

1 -1/2 0 0 1/2 0 0 -1 1

c(H3) = (c2, c1, c6) = ( -2,-3, 0),

c(H3) A(H3)-1 = (-2,-3,0)

1 0 0 0 1 0 , -1 0 1

1 -1/2 0 0 1/2 0 0 -1 1

= (- 2, -1/2, 0),

r3 = c3 - c(H3)A(H3)-1a3 = -4 - (-2, -1/2, 0) (2, 3, 3)T = 3/2 > 0, r4 = c4 - c(H3)A(H3)-1a4 = 0 - (-2, -1/2, 0) (1, 0, 0)T = 2 > 0, r5 = c5 - c(H3)A(H3)-1a5 = 0 - (-2, -1/2, 0) (0, 1, 0)T = 0 ,

Revised Simplex Method page 8

CONCLUSION: H3 yields optimum. A(H3)-1b =

1 0 0 0 1 0 -1 0 1

1 -1/2 0 0 1/2 0 0 -1 1

3/2 4 5 = 5/2 1/2 7

.

Thus, x*2 = 3/2, x*1 = 5/2, x*6 = 1/2, and x*3 = x*4 = x*5 = 0 and z = c⋅x* = -21/2 are the optimal values of the variables and the objective.

Revised Simplex Method page 9