Example3.6Cycling
load simplex.sage 
       
simplex functions loaded.
simplex functions loaded.
A=Matrix([[3,-3/4,20,-1/2,6,0,0,0],[0,1/4,-8,-1,9,1,0,0], [0,1/2,-12,-1/2,3,0,1,0],[1,0,0,1,0,0,0,1]]); Aorig=copy(A); A 
       
[   3 -3/4   20 -1/2    6    0    0    0]
[   0  1/4   -8   -1    9    1    0    0]
[   0  1/2  -12 -1/2    3    0    1    0]
[   1    0    0    1    0    0    0    1]
[   3 -3/4   20 -1/2    6    0    0    0]
[   0  1/4   -8   -1    9    1    0    0]
[   0  1/2  -12 -1/2    3    0    1    0]
[   1    0    0    1    0    0    0    1]
B=[5,6,7] 
       
pivot(A,1,1,B); A; A==Aorig 
       
Pivoting tableau on col= 1 row= 1
[   3    0   -4 -7/2   33    3    0    0]
[   0    1  -32   -4   36    4    0    0]
[   0    0    4  3/2  -15   -2    1    0]
[   1    0    0    1    0    0    0    1]
False
Pivoting tableau on col= 1 row= 1
[   3    0   -4 -7/2   33    3    0    0]
[   0    1  -32   -4   36    4    0    0]
[   0    0    4  3/2  -15   -2    1    0]
[   1    0    0    1    0    0    0    1]
False
pivot(A,2,2,B); A 
       
Pivoting tableau on col= 2 row= 2
[    3     0     0    -2    18     1     1     0]
[    0     1     0     8   -84   -12     8     0]
[    0     0     1   3/8 -15/4  -1/2   1/4     0]
[    1     0     0     1     0     0     0     1]
Pivoting tableau on col= 2 row= 2
[    3     0     0    -2    18     1     1     0]
[    0     1     0     8   -84   -12     8     0]
[    0     0     1   3/8 -15/4  -1/2   1/4     0]
[    1     0     0     1     0     0     0     1]
pivot(A,3,1,B); A 
       
Pivoting tableau on col= 3 row= 1
[    3   1/4     0     0    -3    -2     3     0]
[    0   1/8     0     1 -21/2  -3/2     1     0]
[    0 -3/64     1     0  3/16  1/16  -1/8     0]
[    1  -1/8     0     0  21/2   3/2    -1     1]
Pivoting tableau on col= 3 row= 1
[    3   1/4     0     0    -3    -2     3     0]
[    0   1/8     0     1 -21/2  -3/2     1     0]
[    0 -3/64     1     0  3/16  1/16  -1/8     0]
[    1  -1/8     0     0  21/2   3/2    -1     1]
pivot(A,4,2,B); A 
       
Pivoting tableau on col= 4 row= 2
[   3 -1/2   16    0    0   -1    1    0]
[   0 -5/2   56    1    0    2   -6    0]
[   0 -1/4 16/3    0    1  1/3 -2/3    0]
[   1  5/2  -56    0    0   -2    6    1]
Pivoting tableau on col= 4 row= 2
[   3 -1/2   16    0    0   -1    1    0]
[   0 -5/2   56    1    0    2   -6    0]
[   0 -1/4 16/3    0    1  1/3 -2/3    0]
[   1  5/2  -56    0    0   -2    6    1]
pivot(A,5,1,B); A 
       
Pivoting tableau on col= 5 row= 1
[   3 -7/4   44  1/2    0    0   -2    0]
[   0 -5/4   28  1/2    0    1   -3    0]
[   0  1/6   -4 -1/6    1    0  1/3    0]
[   1    0    0    1    0    0    0    1]
Pivoting tableau on col= 5 row= 1
[   3 -7/4   44  1/2    0    0   -2    0]
[   0 -5/4   28  1/2    0    1   -3    0]
[   0  1/6   -4 -1/6    1    0  1/3    0]
[   1    0    0    1    0    0    0    1]
pivot(A,6,2,B); A; A==Aorig 
       
Pivoting tableau on col= 6 row= 2
[   3 -3/4   20 -1/2    6    0    0    0]
[   0  1/4   -8   -1    9    1    0    0]
[   0  1/2  -12 -1/2    3    0    1    0]
[   1    0    0    1    0    0    0    1]
True
Pivoting tableau on col= 6 row= 2
[   3 -3/4   20 -1/2    6    0    0    0]
[   0  1/4   -8   -1    9    1    0    0]
[   0  1/2  -12 -1/2    3    0    1    0]
[   1    0    0    1    0    0    0    1]
True
# For lexicographic pivoting rules: 
       
       
[   3 -3/4   20 -1/2    6    0    0    0]
[   0  1/4   -8   -1    9    1    0    0]
[   0  1/2  -12 -1/2    3    0    1    0]
[   1    0    0    1    0    0    0    1]
[   3 -3/4   20 -1/2    6    0    0    0]
[   0  1/4   -8   -1    9    1    0    0]
[   0  1/2  -12 -1/2    3    0    1    0]
[   1    0    0    1    0    0    0    1]
scale_rows(A,1) 
       
Scaling rows so that every positive entry in the pivot column 1 is
1.
[   3 -3/4   20 -1/2    6    0    0    0]
[   0    1  -32   -4   36    4    0    0]
[   0    1  -24   -1    6    0    2    0]
[   1    0    0    1    0    0    0    1]
Scaling rows so that every positive entry in the pivot column 1 is 1.
[   3 -3/4   20 -1/2    6    0    0    0]
[   0    1  -32   -4   36    4    0    0]
[   0    1  -24   -1    6    0    2    0]
[   1    0    0    1    0    0    0    1]
pivot(A,1,1,B); A 
       
Pivoting tableau on col= 1 row= 1
[   3    0   -4 -7/2   33    3    0    0]
[   0    1  -32   -4   36    4    0    0]
[   0    0    4  3/2  -15   -2    1    0]
[   1    0    0    1    0    0    0    1]
Pivoting tableau on col= 1 row= 1
[   3    0   -4 -7/2   33    3    0    0]
[   0    1  -32   -4   36    4    0    0]
[   0    0    4  3/2  -15   -2    1    0]
[   1    0    0    1    0    0    0    1]
scale_rows(A,2) 
       
Scaling rows so that every positive entry in the pivot column 2 is
1.
[    3     0    -4  -7/2    33     3     0     0]
[    0     1   -32    -4    36     4     0     0]
[    0     0     1   3/8 -15/4  -1/2   1/4     0]
[    1     0     0     1     0     0     0     1]
Scaling rows so that every positive entry in the pivot column 2 is 1.
[    3     0    -4  -7/2    33     3     0     0]
[    0     1   -32    -4    36     4     0     0]
[    0     0     1   3/8 -15/4  -1/2   1/4     0]
[    1     0     0     1     0     0     0     1]
pivot(A,2,2,B); A 
       
Pivoting tableau on col= 2 row= 2
[    3     0     0    -2    18     1     1     0]
[    0     1     0     8   -84   -12     8     0]
[    0     0     1   3/8 -15/4  -1/2   1/4     0]
[    1     0     0     1     0     0     0     1]
Pivoting tableau on col= 2 row= 2
[    3     0     0    -2    18     1     1     0]
[    0     1     0     8   -84   -12     8     0]
[    0     0     1   3/8 -15/4  -1/2   1/4     0]
[    1     0     0     1     0     0     0     1]
scale_rows(A,3) 
       
Scaling rows so that every positive entry in the pivot column 3 is
1.
[    3     0     0    -2    18     1     1     0]
[    0   1/8     0     1 -21/2  -3/2     1     0]
[    0     0   8/3     1   -10  -4/3   2/3     0]
[    1     0     0     1     0     0     0     1]
Scaling rows so that every positive entry in the pivot column 3 is 1.
[    3     0     0    -2    18     1     1     0]
[    0   1/8     0     1 -21/2  -3/2     1     0]
[    0     0   8/3     1   -10  -4/3   2/3     0]
[    1     0     0     1     0     0     0     1]
pivot(A,3,2,B); A 
       
Pivoting tableau on col= 3 row= 2
[    3     0  16/3     0    -2  -5/3   7/3     0]
[    0     1 -64/3     0    -4  -4/3   8/3     0]
[    0     0   8/3     1   -10  -4/3   2/3     0]
[    1     0  -8/3     0    10   4/3  -2/3     1]
Pivoting tableau on col= 3 row= 2
[    3     0  16/3     0    -2  -5/3   7/3     0]
[    0     1 -64/3     0    -4  -4/3   8/3     0]
[    0     0   8/3     1   -10  -4/3   2/3     0]
[    1     0  -8/3     0    10   4/3  -2/3     1]
scale_rows(A,5) 
       
Scaling rows so that every positive entry in the pivot column 5 is
1.
[    3     0  16/3     0    -2  -5/3   7/3     0]
[    0     1 -64/3     0    -4  -4/3   8/3     0]
[    0     0   8/3     1   -10  -4/3   2/3     0]
[  3/4     0    -2     0  15/2     1  -1/2   3/4]
Scaling rows so that every positive entry in the pivot column 5 is 1.
[    3     0  16/3     0    -2  -5/3   7/3     0]
[    0     1 -64/3     0    -4  -4/3   8/3     0]
[    0     0   8/3     1   -10  -4/3   2/3     0]
[  3/4     0    -2     0  15/2     1  -1/2   3/4]
pivot(A,5,3,B); A 
       
Pivoting tableau on col= 5 row= 3
[17/4    0    2    0 21/2    0  3/2  5/4]
[   1    1  -24    0    6    0    2    1]
[   1    0    0    1    0    0    0    1]
[ 3/4    0   -2    0 15/2    1 -1/2  3/4]
Pivoting tableau on col= 5 row= 3
[17/4    0    2    0 21/2    0  3/2  5/4]
[   1    1  -24    0    6    0    2    1]
[   1    0    0    1    0    0    0    1]
[ 3/4    0   -2    0 15/2    1 -1/2  3/4]
# For Bland's Rule 
       
A=copy(Aorig); A 
       
[   3 -3/4   20 -1/2    6    0    0    0]
[   0  1/4   -8   -1    9    1    0    0]
[   0  1/2  -12 -1/2    3    0    1    0]
[   1    0    0    1    0    0    0    1]
[   3 -3/4   20 -1/2    6    0    0    0]
[   0  1/4   -8   -1    9    1    0    0]
[   0  1/2  -12 -1/2    3    0    1    0]
[   1    0    0    1    0    0    0    1]
pivot(A,1,1,B); A 
       
Pivoting tableau on col= 1 row= 1
[   3    0   -4 -7/2   33    3    0    0]
[   0    1  -32   -4   36    4    0    0]
[   0    0    4  3/2  -15   -2    1    0]
[   1    0    0    1    0    0    0    1]
Pivoting tableau on col= 1 row= 1
[   3    0   -4 -7/2   33    3    0    0]
[   0    1  -32   -4   36    4    0    0]
[   0    0    4  3/2  -15   -2    1    0]
[   1    0    0    1    0    0    0    1]
pivot(A,2,2,B); A 
       
Pivoting tableau on col= 2 row= 2
[    3     0     0    -2    18     1     1     0]
[    0     1     0     8   -84   -12     8     0]
[    0     0     1   3/8 -15/4  -1/2   1/4     0]
[    1     0     0     1     0     0     0     1]
Pivoting tableau on col= 2 row= 2
[    3     0     0    -2    18     1     1     0]
[    0     1     0     8   -84   -12     8     0]
[    0     0     1   3/8 -15/4  -1/2   1/4     0]
[    1     0     0     1     0     0     0     1]
pivot(A,3,1,B); A 
       
Pivoting tableau on col= 3 row= 1
[    3   1/4     0     0    -3    -2     3     0]
[    0   1/8     0     1 -21/2  -3/2     1     0]
[    0 -3/64     1     0  3/16  1/16  -1/8     0]
[    1  -1/8     0     0  21/2   3/2    -1     1]
Pivoting tableau on col= 3 row= 1
[    3   1/4     0     0    -3    -2     3     0]
[    0   1/8     0     1 -21/2  -3/2     1     0]
[    0 -3/64     1     0  3/16  1/16  -1/8     0]
[    1  -1/8     0     0  21/2   3/2    -1     1]
pivot(A,4,2,B); A 
       
Pivoting tableau on col= 4 row= 2
[   3 -1/2   16    0    0   -1    1    0]
[   0 -5/2   56    1    0    2   -6    0]
[   0 -1/4 16/3    0    1  1/3 -2/3    0]
[   1  5/2  -56    0    0   -2    6    1]
Pivoting tableau on col= 4 row= 2
[   3 -1/2   16    0    0   -1    1    0]
[   0 -5/2   56    1    0    2   -6    0]
[   0 -1/4 16/3    0    1  1/3 -2/3    0]
[   1  5/2  -56    0    0   -2    6    1]
pivot(A,1,3,B); A 
       
Pivoting tableau on col= 1 row= 3
[  16/5      0   24/5      0      0   -7/5   11/5    1/5]
[     1      0      0      1      0      0      0      1]
[  1/10      0  -4/15      0      1   2/15  -1/15   1/10]
[   2/5      1 -112/5      0      0   -4/5   12/5    2/5]
Pivoting tableau on col= 1 row= 3
[  16/5      0   24/5      0      0   -7/5   11/5    1/5]
[     1      0      0      1      0      0      0      1]
[  1/10      0  -4/15      0      1   2/15  -1/15   1/10]
[   2/5      1 -112/5      0      0   -4/5   12/5    2/5]
pivot(A,5,2,B); A 
       
Pivoting tableau on col= 5 row= 2
[17/4    0    2    0 21/2    0  3/2  5/4]
[   1    0    0    1    0    0    0    1]
[ 3/4    0   -2    0 15/2    1 -1/2  3/4]
[   1    1  -24    0    6    0    2    1]
Pivoting tableau on col= 5 row= 2
[17/4    0    2    0 21/2    0  3/2  5/4]
[   1    0    0    1    0    0    0    1]
[ 3/4    0   -2    0 15/2    1 -1/2  3/4]
[   1    1  -24    0    6    0    2    1]