ExampleOfPhaseI
load simplex.sage 
        
simplex functions loaded.
simplex functions loaded.
A=Matrix(ZZ,[[0,0,0,0,0],[6,1,1,-1,0],[4,2,3,0,1]]); A 
        
[ 0  0  0  0  0]
[ 6  1  1 -1  0]
[ 4  2  3  0  1]
[ 0  0  0  0  0]
[ 6  1  1 -1  0]
[ 4  2  3  0  1]
M=identity_matrix(ZZ,2); M 
        
[1 0]
[0 1]
[1 0]
[0 1]
Aux=matrix(ZZ,1,2,[1]*2).stack(M); Aux 
        
[1 1]
[1 0]
[0 1]
[1 1]
[1 0]
[0 1]
A=A.transpose().stack(Aux.transpose()).transpose(); A=Matrix(QQ,A); A 
        
[ 0  0  0  0  0  1  1]
[ 6  1  1 -1  0  1  0]
[ 4  2  3  0  1  0  1]
[ 0  0  0  0  0  1  1]
[ 6  1  1 -1  0  1  0]
[ 4  2  3  0  1  0  1]
B=[5,6]  # basis of artificial variables 
       
pivot(A,5,1,B)
pivot(A,6,2,B); A  # tableau is now ready to start simplex 
        
Pivoting tableau on col= 5 row= 1
Pivoting tableau on col= 6 row= 2
[-10  -3  -4   1  -1   0   0]
[  6   1   1  -1   0   1   0]
[  4   2   3   0   1   0   1]
Pivoting tableau on col= 5 row= 1
Pivoting tableau on col= 6 row= 2
[-10  -3  -4   1  -1   0   0]
[  6   1   1  -1   0   1   0]
[  4   2   3   0   1   0   1]
pivot(A,1,2,B); A 
        
Pivoting tableau on col= 1 row= 2
[  -4    0  1/2    1  1/2    0  3/2]
[   4    0 -1/2   -1 -1/2    1 -1/2]
[   2    1  3/2    0  1/2    0  1/2]
Pivoting tableau on col= 1 row= 2
[  -4    0  1/2    1  1/2    0  3/2]
[   4    0 -1/2   -1 -1/2    1 -1/2]
[   2    1  3/2    0  1/2    0  1/2]
# We have obtained optimal solution. 
       
A=Matrix(ZZ,[[0,0,0,0],[4,2,1,1],[2,1,1,2]]); A 
        
[0 0 0 0]
[4 2 1 1]
[2 1 1 2]
[0 0 0 0]
[4 2 1 1]
[2 1 1 2]
M=identity_matrix(ZZ,2)
Aux=matrix(ZZ,1,2,[1]*2).stack(M)
A=A.transpose().stack(Aux.transpose()).transpose(); A=Matrix(QQ,A); A 
        
[0 0 0 0 1 1]
[4 2 1 1 1 0]
[2 1 1 2 0 1]
[0 0 0 0 1 1]
[4 2 1 1 1 0]
[2 1 1 2 0 1]
B=[4,5] 
       
pivot(A,4,1,B)
pivot(A,5,2,B); A  # tableau is now ready to start simplex 
        
Pivoting tableau on col= 4 row= 1
Pivoting tableau on col= 5 row= 2
[-6 -3 -2 -3  0  0]
[ 4  2  1  1  1  0]
[ 2  1  1  2  0  1]
Pivoting tableau on col= 4 row= 1
Pivoting tableau on col= 5 row= 2
[-6 -3 -2 -3  0  0]
[ 4  2  1  1  1  0]
[ 2  1  1  2  0  1]
pivot(A,1,2,B); A 
        
Pivoting tableau on col= 1 row= 2
[ 0  0  1  3  0  3]
[ 0  0 -1 -3  1 -2]
[ 2  1  1  2  0  1]
Pivoting tableau on col= 1 row= 2
[ 0  0  1  3  0  3]
[ 0  0 -1 -3  1 -2]
[ 2  1  1  2  0  1]
# We have obtained an optimal solution with cost = 0, but y1 is still in the basis! 
       
pivot(A,2,1,B); A 
        
Pivoting tableau on col= 2 row= 1
[ 0  0  0  0  1  1]
[ 0  0  1  3 -1  2]
[ 2  1  0 -1  1 -1]
Pivoting tableau on col= 2 row= 1
[ 0  0  0  0  1  1]
[ 0  0  1  3 -1  2]
[ 2  1  0 -1  1 -1]
# We now have a BFS and a basis for Phase II.