Public Simplex Algorithm.sagews

A=matrix(QQ, [[4,4,400],[2,4,350],[10,12,0]]); A


m=A.nrows()        #p
n=A.ncols()        #q
isoptimal=0
isunbounded=0
XVar=[]
TVar=[]
#declaring our variables so we can switch after the pivot
for i in range(n-1):
    XVar.append('X'+`i+1`)

for j in range(m-1):
    TVar.append('T'+`j+1`)

p=-1
q=-1
isfeasible=1
problemfeasible=0
#Atemp=matrix(QQ, m,n)


while (isoptimal==0 and isunbounded==0):
    isoptimal=1
    isunbounded=1
    isfeasible=1
    problemfeasible=1
    p=-1
    q=-1

    #checks to see if current position is feasible 
    for i in range(m-1):
        if A[i,n-1]<0 and p<0:
            p=i
            isfeasible=0
            isoptimal=0 #if isfeasible is zero, means point is not feasible, no place for you to stand on graph, so this isn't an optimal point
            isunbounded=0 #We now don't really care if its unbounded.
    
    #Checks to see if problem is feasible
    if isfeasible==0:  
        problemfeasible=0
        for k in range(n-1):
            if A[p,k]<0 and q<0:
                q=k
                problemfeasible=1


    if problemfeasible==0:
        print('The problem has no feasible solutions')
        p
        q

    else:
        #checking last row to see if optimal (step 1), it's optimal when all are negative
        for i in range(n-1):
            if A[m-1,i]>0:
                isoptimal=0

        if isoptimal==1 and isfeasible==1:
            print('This is optimal, ignore everything after this')
    

        #finding the right [p,q] to pivot on and will only pivot if point is feasible
        if isoptimal!=1 and isfeasible==1:
            q=-1
            #finding position q to pivot on
            for i in range(n-1):
                if A[m-1,i]>0 and q<0:
                    q=i; q
            
            #checking column q to see if all negative (step 4)
            for k in range(m-1):
                #A[k,q]
                if A[k,q]>0:
                    isunbounded=0
        
            if isunbounded==1:
                print('This is unbounded')
        
        
            p=-1
            #finding position p to pivot on (step 5)
            for j in range(m-1):
                if A[j,q]!=0:
                    if A[j,n-1]/A[j,q]>=0 and A[j,q]>0:
                        if p<0:
                            p=j; p
                        if p>=0 and A[j,n-1]/A[j,q]<A[p,n-1]/A[p,q]:
                            p=j; p
            #printing out the position [p,q] to pivot on and setting declaring a temporary matrix to make for when we pivot
            print('pivot on position')
            p
            q
        Atemp=matrix(QQ, m,n)

            #the temporary matrix pivots on [p,q] 
        
        for i in range(m):
            for j in range(n):
                if i==p and j==q:
                    Atemp[i,j]=1/A[p,q]
                if i==p and j!=q:
                    Atemp[i,j]=A[i,j]/A[p,q]
                if i!=p and j==q:
                    Atemp[i,j]=-1*A[i,j]/A[p,q]
                if i!=p and j!=q: 
                    Atemp[i,j]=(A[i,j]*A[p,q]-A[i,q]*A[p,j])/A[p,q]

            #switches variables according to the pivots, and prints out ones we are switching
        Xp=XVar[q];Xp
        Tp=TVar[p];Tp

            #setting new variables to XVar and TVar
        XVar[q]=Tp
        TVar[p]=Xp
            
        #setting the temporary matrix (that we pivoted on) to be matrix A and printing new tableaux and the new variables after the pivot
        Atemp
        A=Atemp
        XVar
        TVar
    
        
p
q

[ 4 4 400] [ 2 4 350] [ 10 12 0] 0 0 pivot on position 0 0 'X1' 'T1' [ 1/4 1 100] [ -1/2 2 150] [ -5/2 2 -1000] ['T1', 'X2'] ['X1', 'T2'] 1 0 1 pivot on position 1 1 'X2' 'T2' [ 1/2 -1/2 25] [ -1/4 1/2 75] [ -2 -1 -1150] ['T1', 'T2'] ['X1', 'X2'] This is optimal, ignore everything after this 'T2' 'X2' [ 21/46 -12/23 0] [-35/92 10/23 0] [ 0 0 0] ['T1', 'X2'] ['X1', 'T2'] -1 -1