''' Simplex method '''

# Funcao objetivo na ultima linha

def Simplex(A):

	EPSILON = 0.0001

	m = len(A) # Linhas
	n = len(A[0]) # Colunas

	fxLine = len(A) - 1

	pivotCol  = -1
	pivotLine = -1

	minor = A[fxLine][0]

	negativeExists = False
	i = 0
	while (i < (n-1)) and not negativeExists:
		negativeExists = (A[m - 1][i] < 0)
		i = i + 1

	while negativeExists:

		# Busca o elemento de menor valor na linha da funcao objetivo
		for i in range(n): # Colunas
			if (minor > A[fxLine][i]):
				minor = A[fxLine][i]
				pivotCol = i

		minor = A[0][n - 1]
		print("pivotCol: " + str(pivotCol))

		# Busca a linha que fornecera o pivot para a iteracao atual
		for j in range(m - 1): # Linhas, exceto a da funcao objetivo
			if(abs(A[j][pivotCol]) < EPSILON):
				coef = 0
			else:
				coef = (1/float(A[j][pivotCol]))*A[j][n - 1]
			print("coef: " + str(coef) + ", minor: " + str(minor))

			if (minor >= coef and coef > 0): # Elemento com menor valor positivo
				minor = coef
				pivotLine = j

		# Recalcula a linha pivot se for necessario
		if(A[pivotLine][pivotCol] != 1):
			coef = A[pivotLine][pivotCol]
			if(coef < EPSILON):
				coef = 0

			for i in range(n):
				A[pivotLine][i] = 1/float(coef) * (A[pivotLine][i])

		# Recalcula as outras linhas, exceto a linha pivot
		l = range(m)
		del l[pivotLine]

		for i in l:
			coef = A[i][pivotCol]
			coef = (-1)*coef
			for j in range(n):
				A[i][j] = A[i][j] + coef*A[pivotLine][j]

		# Busca por negativos na funcao objetivo
		i = 0
		negativeExists = False
		while (i < (n-1)) and not negativeExists:
			negativeExists = (A[m - 1][i] < 0)
			i = i + 1


	return A


# Matriz com Fx, Restricoes e Identidade
A = [[1, 1, 1, 0, 0, 6], [1, -1, 0, 1, 0, 4], [-1, 1, 0, 0, 1, 4], [-1, -2, 0, 0, 0, 0]]
print(Simplex(A))