cycle.ms
Carl Lee
Fall 1997

Example of cyclng from Chvatal.  We will choose as the entering variable the one that has the largest positive entry on the bottom row.  If there are ties for the entering or the leaving variable, we will choose the one with the smallest subscript.

Here is the original table, with basis (5,6,7):

>	with(linalg):

Warning, the protected names norm and trace have been redefined and unprotected

>	T1:=matrix([ [x1,x2,x3,x4,x5,x6,x7,-z,RHS], [1/2,-11/2,-5/2,9,1,0,0,0,0], [1/2,-3/2,-1/2,1,0,1,0,0,0], [1,0,0,0,0,0,1,0,1], [10,-57,-9,-24,0,0,0,1,0] ]);

Pivot x1 in, x5 out, to get a primal feasible table with basis (1,6,7):

>	T2:=pivot(mulrow(T1,2,2),2,1,2..5);

Pivot x2 in, x6 out, to get basis (1,2,7):

>	T3:=pivot(mulrow(T2,3,1/4),3,2,2..5);

Pivot x3 in, x1 out, to get basis (3,2,7):

>	T4:=pivot(mulrow(T3,2,2),2,3,2..5);

Pivot x4 in, x2 out, to get basis (3,4,7):

>	T5:=pivot(mulrow(T4,3,1/2),3,4,2..5);

Pivot x5 in, x3 out, to get basis (5,4,7):

>	T6:=pivot(mulrow(T5,2,2),2,5,2..5);

Pivot x6 in, x4 out, to get basis (5,6,7):

>	T7:=pivot(mulrow(T6,1,1),3,6,2..5);

We have cycled back to our original table!


We can avoid cycling using Bland's smallest subscript rule.  We will choose as the entering variable the one with smallest index that has a positive entry in the bottom row.  If there are ties for the leaving variable, we will choose the one with the smallest subscript.

Starting with the original table, our pivoting will match the above sequence until we get to table T6:

>	evalm(T6);

Pivot x1 in, x4 out to get basis (5,1,7):

>	T2:=pivot(mulrow(T1,3,2),3,1,2..5);

Pivot x3 in, x7 out to get basis (5,1,3):

>	T3:=pivot(mulrow(T2,4,1),4,3,2..5);

This table is optimal, and we stop.


We could also avoid cycling using the perturbation method.

Starting with the original table T1, we add powers of an indeterminate e to the right-hand sides.  The starting basis is still (5,6,7):

>	T1:=matrix([ [x1,x2,x3,x4,x5,x6,x7,-z,RHS], [1/2,-11/2,-5/2,9,1,0,0,0,e], [1/2,-3/2,-1/2,1,0,1,0,0,e^2], [1,0,0,0,0,0,1,0,1+e^3], [10,-57,-9,-24,0,0,0,1,0] ]);

Pivot x1 in.  Check ratios:

>	e/(1/2);e^2/(1/2);(1+e^3)/1;

The second ratio is smaller, so we choose x6 to leave, getting basis (5,1,7):

>	T2:=pivot(mulrow(T1,3,2),3,1,2..5);

Pivot x3 in.  You must pivot x7 out, getting basis (5,1,3):

>	T3:=pivot(mulrow(T2,4,1),4,3,2..5);

This table is optimal.  You can set e:=0 to see the final table for the original, unperturbed problem.

>

>