SharedximeraWorkshop / s17mat200 / simplexalgorithm / Simplex Algorithm Public.sagewsOpen in CoCalc
Author: Tien Chih
Views : 2
A=matrix(QQ, [[1,1,1,1,0,0,0,0,25],[-1,-1,-1,-1,0,0,0,0,-10],[0,0,0,0,1,1,1,1,25],[0,0,0,0,-1,-1,-1,-1,-10],[1,0,0,0,1,0,0,0,15],[-1,0,0,0,-1,0,0,0,-5],[0,1,0,0,0,1,0,0,15],[0,-1,0,0,0,-1,0,0,-5],[0,0,1,0,0,0,1,0,15],[0,0,-1,0,0,0,-1,0,-5],[0,0,0,1,0,0,0,1,15],[0,0,0,-1,0,0,0,-1,-5],[4,1,12,7,9,8,9,8,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
[ 1 1 1 1 0 0 0 0 25] [ -1 -1 -1 -1 0 0 0 0 -10] [ 0 0 0 0 1 1 1 1 25] [ 0 0 0 0 -1 -1 -1 -1 -10] [ 1 0 0 0 1 0 0 0 15] [ -1 0 0 0 -1 0 0 0 -5] [ 0 1 0 0 0 1 0 0 15] [ 0 -1 0 0 0 -1 0 0 -5] [ 0 0 1 0 0 0 1 0 15] [ 0 0 -1 0 0 0 -1 0 -5] [ 0 0 0 1 0 0 0 1 15] [ 0 0 0 -1 0 0 0 -1 -5] [ 4 1 12 7 9 8 9 8 0] 'X1' 'T2' [ 1 0 0 0 0 0 0 0 15] [ -1 1 1 1 0 0 0 0 10] [ 0 0 0 0 1 1 1 1 25] [ 0 0 0 0 -1 -1 -1 -1 -10] [ 1 -1 -1 -1 1 0 0 0 5] [ -1 1 1 1 -1 0 0 0 5] [ 0 1 0 0 0 1 0 0 15] [ 0 -1 0 0 0 -1 0 0 -5] [ 0 0 1 0 0 0 1 0 15] [ 0 0 -1 0 0 0 -1 0 -5] [ 0 0 0 1 0 0 0 1 15] [ 0 0 0 -1 0 0 0 -1 -5] [ 4 -3 8 3 9 8 9 8 -40] ['T2', 'X2', 'X3', 'X4', 'X5', 'X6', 'X7', 'X8'] ['T1', 'X1', 'T3', 'T4', 'T5', 'T6', 'T7', 'T8', 'T9', 'T10', 'T11', 'T12'] 'X5' 'T4' [ 1 0 0 0 0 0 0 0 15] [ -1 1 1 1 0 0 0 0 10] [ 0 0 0 0 1 0 0 0 15] [ 0 0 0 0 -1 1 1 1 10] [ 1 -1 -1 -1 1 -1 -1 -1 -5] [ -1 1 1 1 -1 1 1 1 15] [ 0 1 0 0 0 1 0 0 15] [ 0 -1 0 0 0 -1 0 0 -5] [ 0 0 1 0 0 0 1 0 15] [ 0 0 -1 0 0 0 -1 0 -5] [ 0 0 0 1 0 0 0 1 15] [ 0 0 0 -1 0 0 0 -1 -5] [ 4 -3 8 3 9 -1 0 -1 -130] ['T2', 'X2', 'X3', 'X4', 'T4', 'X6', 'X7', 'X8'] ['T1', 'X1', 'T3', 'X5', 'T5', 'T6', 'T7', 'T8', 'T9', 'T10', 'T11', 'T12'] 'X2' 'T5' [ 1 0 0 0 0 0 0 0 15] [ 0 1 0 0 1 -1 -1 -1 5] [ 0 0 0 0 1 0 0 0 15] [ 0 0 0 0 -1 1 1 1 10] [ -1 -1 1 1 -1 1 1 1 5] [ 0 1 0 0 0 0 0 0 10] [ 1 1 -1 -1 1 0 -1 -1 10] [ -1 -1 1 1 -1 0 1 1 0] [ 0 0 1 0 0 0 1 0 15] [ 0 0 -1 0 0 0 -1 0 -5] [ 0 0 0 1 0 0 0 1 15] [ 0 0 0 -1 0 0 0 -1 -5] [ 1 -3 11 6 6 2 3 2 -115] ['T2', 'T5', 'X3', 'X4', 'T4', 'X6', 'X7', 'X8'] ['T1', 'X1', 'T3', 'X5', 'X2', 'T6', 'T7', 'T8', 'T9', 'T10', 'T11', 'T12'] 'X3' 'T10' [ 1 0 0 0 0 0 0 0 15] [ 0 1 0 0 1 -1 -1 -1 5] [ 0 0 0 0 1 0 0 0 15] [ 0 0 0 0 -1 1 1 1 10] [ -1 -1 1 1 -1 1 0 1 0] [ 0 1 0 0 0 0 0 0 10] [ 1 1 -1 -1 1 0 0 -1 15] [ -1 -1 1 1 -1 0 0 1 -5] [ 0 0 1 0 0 0 0 0 10] [ 0 0 -1 0 0 0 1 0 5] [ 0 0 0 1 0 0 0 1 15] [ 0 0 0 -1 0 0 0 -1 -5] [ 1 -3 11 6 6 2 -8 2 -170] ['T2', 'T5', 'T10', 'X4', 'T4', 'X6', 'X7', 'X8'] ['T1', 'X1', 'T3', 'X5', 'X2', 'T6', 'T7', 'T8', 'T9', 'X3', 'T11', 'T12'] 'T2' 'T8' [ 1 -1 1 1 -1 0 0 1 10] [ 0 1 0 0 1 -1 -1 -1 5] [ 0 0 0 0 1 0 0 0 15] [ 0 0 0 0 -1 1 1 1 10] [ -1 0 0 0 0 1 0 0 5] [ 0 1 0 0 0 0 0 0 10] [ 1 0 0 0 0 0 0 0 10] [ -1 1 -1 -1 1 0 0 -1 5] [ 0 0 1 0 0 0 0 0 10] [ 0 0 -1 0 0 0 1 0 5] [ 0 0 0 1 0 0 0 1 15] [ 0 0 0 -1 0 0 0 -1 -5] [ 1 -4 12 7 5 2 -8 3 -175] ['T8', 'T5', 'T10', 'X4', 'T4', 'X6', 'X7', 'X8'] ['T1', 'X1', 'T3', 'X5', 'X2', 'T6', 'T7', 'T2', 'T9', 'X3', 'T11', 'T12'] 'X4' 'T12' [ 1 -1 1 1 -1 0 0 0 5] [ 0 1 0 0 1 -1 -1 -1 5] [ 0 0 0 0 1 0 0 0 15] [ 0 0 0 0 -1 1 1 1 10] [ -1 0 0 0 0 1 0 0 5] [ 0 1 0 0 0 0 0 0 10] [ 1 0 0 0 0 0 0 0 10] [ -1 1 -1 -1 1 0 0 0 10] [ 0 0 1 0 0 0 0 0 10] [ 0 0 -1 0 0 0 1 0 5] [ 0 0 0 1 0 0 0 0 10] [ 0 0 0 -1 0 0 0 1 5] [ 1 -4 12 7 5 2 -8 -4 -210] ['T8', 'T5', 'T10', 'T12', 'T4', 'X6', 'X7', 'X8'] ['T1', 'X1', 'T3', 'X5', 'X2', 'T6', 'T7', 'T2', 'T9', 'X3', 'T11', 'X4'] 0 0 pivot on position 0 0 'T8' 'T1' [ 1 -1 1 1 -1 0 0 0 5] [ 0 1 0 0 1 -1 -1 -1 5] [ 0 0 0 0 1 0 0 0 15] [ 0 0 0 0 -1 1 1 1 10] [ 1 -1 1 1 -1 1 0 0 10] [ 0 1 0 0 0 0 0 0 10] [ -1 1 -1 -1 1 0 0 0 5] [ 1 0 0 0 0 0 0 0 15] [ 0 0 1 0 0 0 0 0 10] [ 0 0 -1 0 0 0 1 0 5] [ 0 0 0 1 0 0 0 0 10] [ 0 0 0 -1 0 0 0 1 5] [ -1 -3 11 6 6 2 -8 -4 -215] ['T1', 'T5', 'T10', 'T12', 'T4', 'X6', 'X7', 'X8'] ['T8', 'X1', 'T3', 'X5', 'X2', 'T6', 'T7', 'T2', 'T9', 'X3', 'T11', 'X4'] 2 0 pivot on position 0 2 'T10' 'T8' [ 1 -1 1 1 -1 0 0 0 5] [ 0 1 0 0 1 -1 -1 -1 5] [ 0 0 0 0 1 0 0 0 15] [ 0 0 0 0 -1 1 1 1 10] [ 0 0 -1 0 0 1 0 0 5] [ 0 1 0 0 0 0 0 0 10] [ 0 0 1 0 0 0 0 0 10] [ 1 0 0 0 0 0 0 0 15] [ -1 1 -1 -1 1 0 0 0 5] [ 1 -1 1 1 -1 0 1 0 10] [ 0 0 0 1 0 0 0 0 10] [ 0 0 0 -1 0 0 0 1 5] [ -12 8 -11 -5 17 2 -8 -4 -270] ['T1', 'T5', 'T8', 'T12', 'T4', 'X6', 'X7', 'X8'] ['T10', 'X1', 'T3', 'X5', 'X2', 'T6', 'T7', 'T2', 'T9', 'X3', 'T11', 'X4'] 1 1 pivot on position 1 1 'T5' 'X1' [ 1 1 1 1 0 -1 -1 -1 10] [ 0 1 0 0 1 -1 -1 -1 5] [ 0 0 0 0 1 0 0 0 15] [ 0 0 0 0 -1 1 1 1 10] [ 0 0 -1 0 0 1 0 0 5] [ 0 -1 0 0 -1 1 1 1 5] [ 0 0 1 0 0 0 0 0 10] [ 1 0 0 0 0 0 0 0 15] [ -1 -1 -1 -1 0 1 1 1 0] [ 1 1 1 1 0 -1 0 -1 15] [ 0 0 0 1 0 0 0 0 10] [ 0 0 0 -1 0 0 0 1 5] [ -12 -8 -11 -5 9 10 0 4 -310] ['T1', 'X1', 'T8', 'T12', 'T4', 'X6', 'X7', 'X8'] ['T10', 'T5', 'T3', 'X5', 'X2', 'T6', 'T7', 'T2', 'T9', 'X3', 'T11', 'X4'] 4 1 pivot on position 1 4 'T4' 'T5' [ 1 1 1 1 0 -1 -1 -1 10] [ 0 1 0 0 1 -1 -1 -1 5] [ 0 -1 0 0 -1 1 1 1 10] [ 0 1 0 0 1 0 0 0 15] [ 0 0 -1 0 0 1 0 0 5] [ 0 0 0 0 1 0 0 0 10] [ 0 0 1 0 0 0 0 0 10] [ 1 0 0 0 0 0 0 0 15] [ -1 -1 -1 -1 0 1 1 1 0] [ 1 1 1 1 0 -1 0 -1 15] [ 0 0 0 1 0 0 0 0 10] [ 0 0 0 -1 0 0 0 1 5] [ -12 -17 -11 -5 -9 19 9 13 -355] ['T1', 'X1', 'T8', 'T12', 'T5', 'X6', 'X7', 'X8'] ['T10', 'T4', 'T3', 'X5', 'X2', 'T6', 'T7', 'T2', 'T9', 'X3', 'T11', 'X4'] 5 2 4 8 pivot on position 8 5 'X6' 'T9' [ 0 0 0 0 0 1 0 0 10] [ -1 0 -1 -1 1 1 0 0 5] [ 1 0 1 1 -1 -1 0 0 10] [ 0 1 0 0 1 0 0 0 15] [ 1 1 0 1 0 -1 -1 -1 5] [ 0 0 0 0 1 0 0 0 10] [ 0 0 1 0 0 0 0 0 10] [ 1 0 0 0 0 0 0 0 15] [ -1 -1 -1 -1 0 1 1 1 0] [ 0 0 0 0 0 1 1 0 15] [ 0 0 0 1 0 0 0 0 10] [ 0 0 0 -1 0 0 0 1 5] [ 7 2 8 14 -9 -19 -10 -6 -355] ['T1', 'X1', 'T8', 'T12', 'T5', 'T9', 'X7', 'X8'] ['T10', 'T4', 'T3', 'X5', 'X2', 'T6', 'T7', 'T2', 'X6', 'X3', 'T11', 'X4'] 0 2 4 pivot on position 4 0 'T1' 'X2' [ 0 0 0 0 0 1 0 0 10] [ 1 1 -1 0 1 0 -1 -1 10] [ -1 -1 1 0 -1 0 1 1 5] [ 0 1 0 0 1 0 0 0 15] [ 1 1 0 1 0 -1 -1 -1 5] [ 0 0 0 0 1 0 0 0 10] [ 0 0 1 0 0 0 0 0 10] [ -1 -1 0 -1 0 1 1 1 10] [ 1 0 -1 0 0 0 0 0 5] [ 0 0 0 0 0 1 1 0 15] [ 0 0 0 1 0 0 0 0 10] [ 0 0 0 -1 0 0 0 1 5] [ -7 -5 8 7 -9 -12 -3 1 -390] ['X2', 'X1', 'T8', 'T12', 'T5', 'T9', 'X7', 'X8'] ['T10', 'T4', 'T3', 'X5', 'T1', 'T6', 'T7', 'T2', 'X6', 'X3', 'T11', 'X4'] 2 2 pivot on position 2 2 'T8' 'T3' [ 0 0 0 0 0 1 0 0 10] [ 0 0 1 0 0 0 0 0 15] [ -1 -1 1 0 -1 0 1 1 5] [ 0 1 0 0 1 0 0 0 15] [ 1 1 0 1 0 -1 -1 -1 5] [ 0 0 0 0 1 0 0 0 10] [ 1 1 -1 0 1 0 -1 -1 5] [ -1 -1 0 -1 0 1 1 1 10] [ 0 -1 1 0 -1 0 1 1 10] [ 0 0 0 0 0 1 1 0 15] [ 0 0 0 1 0 0 0 0 10] [ 0 0 0 -1 0 0 0 1 5] [ 1 3 -8 7 -1 -12 -11 -7 -430] ['X2', 'X1', 'T3', 'T12', 'T5', 'T9', 'X7', 'X8'] ['T10', 'T4', 'T8', 'X5', 'T1', 'T6', 'T7', 'T2', 'X6', 'X3', 'T11', 'X4'] 0 4 pivot on position 4 0 'X2' 'T1' [ 0 0 0 0 0 1 0 0 10] [ 0 0 1 0 0 0 0 0 15] [ 1 0 1 1 -1 -1 0 0 10] [ 0 1 0 0 1 0 0 0 15] [ 1 1 0 1 0 -1 -1 -1 5] [ 0 0 0 0 1 0 0 0 10] [ -1 0 -1 -1 1 1 0 0 0] [ 1 0 0 0 0 0 0 0 15] [ 0 -1 1 0 -1 0 1 1 10] [ 0 0 0 0 0 1 1 0 15] [ 0 0 0 1 0 0 0 0 10] [ 0 0 0 -1 0 0 0 1 5] [ -1 2 -8 6 -1 -11 -10 -6 -435] ['T1', 'X1', 'T3', 'T12', 'T5', 'T9', 'X7', 'X8'] ['T10', 'T4', 'T8', 'X5', 'X2', 'T6', 'T7', 'T2', 'X6', 'X3', 'T11', 'X4'] 1 3 4 pivot on position 4 1 'X1' 'X2' [ 0 0 0 0 0 1 0 0 10] [ 0 0 1 0 0 0 0 0 15] [ 1 0 1 1 -1 -1 0 0 10] [ -1 -1 0 -1 1 1 1 1 10] [ 1 1 0 1 0 -1 -1 -1 5] [ 0 0 0 0 1 0 0 0 10] [ -1 0 -1 -1 1 1 0 0 0] [ 1 0 0 0 0 0 0 0 15] [ 1 1 1 1 -1 -1 0 0 15] [ 0 0 0 0 0 1 1 0 15] [ 0 0 0 1 0 0 0 0 10] [ 0 0 0 -1 0 0 0 1 5] [ -3 -2 -8 4 -1 -9 -8 -4 -445] ['T1', 'X2', 'T3', 'T12', 'T5', 'T9', 'X7', 'X8'] ['T10', 'T4', 'T8', 'X5', 'X1', 'T6', 'T7', 'T2', 'X6', 'X3', 'T11', 'X4'] 3 2 4 pivot on position 4 3 'T12' 'X1' [ 0 0 0 0 0 1 0 0 10] [ 0 0 1 0 0 0 0 0 15] [ 0 -1 1 -1 -1 0 1 1 5] [ 0 0 0 1 1 0 0 0 15] [ 1 1 0 1 0 -1 -1 -1 5] [ 0 0 0 0 1 0 0 0 10] [ 0 1 -1 1 1 0 -1 -1 5] [ 1 0 0 0 0 0 0 0 15] [ 0 0 1 -1 -1 0 1 1 10] [ 0 0 0 0 0 1 1 0 15] [ -1 -1 0 -1 0 1 1 1 5] [ 1 1 0 1 0 -1 -1 0 10] [ -7 -6 -8 -4 -1 -5 -4 0 -465] ['T1', 'X2', 'T3', 'X1', 'T5', 'T9', 'X7', 'X8'] ['T10', 'T4', 'T8', 'X5', 'T12', 'T6', 'T7', 'T2', 'X6', 'X3', 'T11', 'X4'] This is optimal, ignore everything after this 'X8' 'X4' [ -14/93 -4/31 -16/93 -8/93 -2/93 83/93 -8/93 0 0] [ -7/31 -6/31 23/31 -4/31 -1/31 -5/31 -4/31 0 0] [ -7/93 -33/31 85/93 -97/93 -94/93 -5/93 89/93 1 0] [ -7/31 -6/31 -8/31 27/31 30/31 -5/31 -4/31 0 0] [ 86/93 29/31 -8/93 89/93 -1/93 -98/93 -97/93 -1 0] [ -14/93 -4/31 -16/93 -8/93 91/93 -10/93 -8/93 0 0] [ -7/93 29/31 -101/93 89/93 92/93 -5/93 -97/93 -1 0] [ 24/31 -6/31 -8/31 -4/31 -1/31 -5/31 -4/31 0 0] [ -14/93 -4/31 77/93 -101/93 -95/93 -10/93 85/93 1 0] [ -7/31 -6/31 -8/31 -4/31 -1/31 26/31 27/31 0 0] [-100/93 -33/31 -8/93 -97/93 -1/93 88/93 89/93 1 0] [ 79/93 27/31 -16/93 85/93 -2/93 -103/93 -101/93 0 0] [ 0 0 0 0 0 0 0 0 0] ['T1', 'X2', 'T3', 'X1', 'T5', 'T9', 'X7', 'X4'] ['T10', 'T4', 'T8', 'X5', 'T12', 'T6', 'T7', 'T2', 'X6', 'X3', 'T11', 'X8'] -1 -1