Created
May 9, 2017 07:10
-
-
Save angellicadearaujo/b8e1ad95066f616ab0ddf7ff483583d2 to your computer and use it in GitHub Desktop.
simplexWithOutput.py
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import time | |
| ''' Simplex method ''' | |
| # Funcao objetivo na ultima linha | |
| def Simplex(A, nonBasicMap): | |
| EPSILON = 0.0001 | |
| m = len(A) # Linhas | |
| n = len(A[0]) # Colunas | |
| fxLine = len(A) - 1 | |
| pivotCol = -1 | |
| pivotLine = -1 | |
| minor = abs(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: | |
| printTable(A) | |
| print("# 1) Buscando o coeficiente de maior contribuicao na funcao objetivo") | |
| # Busca o elemento de maior valor absoluto na linha da funcao objetivo | |
| minor = abs(A[fxLine][0]) | |
| pivotCol = 0 | |
| for i in range(n): # Colunas | |
| # Variavel nao basica original | |
| if (nonBasicMap[i]==1 and minor < abs(A[fxLine][i]) and abs(A[fxLine][i]) > EPSILON): | |
| minor = abs(A[fxLine][i]) | |
| pivotCol = i | |
| print(" Coeficiente encontrado: " + str(minor)) | |
| print(" Coluna que sera pivot e entra na base: " + str(pivotCol + 1)) | |
| print(" ") | |
| print("# 2) Buscando a linha para escolha do elemento pivot (que sai da base)") | |
| # Busca a linha que fornecera o pivot para a iteracao atual | |
| minors = [] | |
| for j in range(m - 1): # Linhas, exceto a da funcao objetivo | |
| if(A[j][pivotCol] < EPSILON): | |
| coef = 0 | |
| else: # A[j][pivotCol] e um numero positivo | |
| coef = (1/float(A[j][pivotCol]))*A[j][n - 1] | |
| print(" Calculando " + str(A[j][n - 1]) + "/" + str(A[j][pivotCol]) + " = " + str(coef)) | |
| minors.append(coef) | |
| lastMinor = minors[0] | |
| for i in range(len(minors)): | |
| if(lastMinor==0 and i < (len(minors) - 1)): | |
| lastMinor = minors[i + 1] | |
| pivotLine = i + 1 | |
| elif(minors[i] < lastMinor and minors[i] > 0): | |
| lastMinor = minors[i] | |
| pivotLine = i | |
| if(all(p == 0 for p in minors)): | |
| print(" ") | |
| print("# _) Fim do processo: A solucao e ilimitada") | |
| printTable(A) | |
| return | |
| print(" Menor valor encontrado foi " + str(lastMinor)) | |
| print(" Linha " + str(pivotLine + 1) + " sai da base") | |
| print(" ") | |
| print("# 3) Realizando operacoes entre linhas") | |
| # Recalcula a linha pivot se for necessario | |
| if(A[pivotLine][pivotCol] != 1): | |
| coef = A[pivotLine][pivotCol] | |
| print(" L" + str(pivotLine + 1) + " = L" + str(pivotLine + 1) + " + (1/" + str(coef) + ")*L"+str(pivotLine + 1)) | |
| 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 | |
| print(" L" + str(i + 1) + " = L" + str(i + 1) + " + (" + str(coef) + ")*L"+str(pivotLine + 1)) | |
| for j in range(n): | |
| A[i][j] = A[i][j] + coef*A[pivotLine][j] | |
| printTable(A) | |
| print(" ") | |
| print("# 4) Teste de otimalidade") | |
| # 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 | |
| if(negativeExists): | |
| print(" Ainda existem custos relativos negativos, a solucao atual nao e otima") | |
| else: | |
| print(" Nao existem custos relativos negativos, a solucao atual e otima e limitada") | |
| printSolution(A) | |
| return A | |
| def getTableByFile(name): | |
| f = open(name, 'r') | |
| lines = f.readlines() | |
| mainFunction = lines[1] | |
| bVector = lines[2] | |
| totalColumns = len(mainFunction.split()) + 1 # Add b colum | |
| totalLines = len(lines) - 2 # Consider only tableu lines | |
| A = [[ 0 for j in range(totalColumns)] for i in range(totalLines)] | |
| # First, complete restriction lines | |
| for i in range(0, totalLines - 1): | |
| k = 3 + i | |
| columns = lines[k].split() | |
| for j in range(len(columns)): | |
| A[i][j] = int(columns[j]) | |
| # Second, complete last line with the main function | |
| for i, item in enumerate(mainFunction.split()): | |
| A[totalLines - 1][i] = (-1)*int(item) | |
| # Then, input b vector | |
| for i, item in enumerate(bVector.split()): | |
| A[i][totalColumns - 1] = int(item) | |
| # Get Non Basic Variables map | |
| nonBasicMap = [0 for i in range(totalColumns)] | |
| for i in range(len(lines[0].split())): | |
| nonBasicMap[i] = 1 | |
| f.close(); | |
| return A, nonBasicMap | |
| def printTable(A): | |
| print(" ") | |
| print("# _) Tabela") | |
| for i in range(len(A)): | |
| line = " " | |
| if(i==(len(A) - 1)): | |
| line = "f(x)" | |
| for j in range(len(A[i])): | |
| line = line + " | " + str("%.2f" % A[i][j]) | |
| print(line) | |
| print(" ") | |
| def printSolution(A): | |
| m = len(A) # linhas | |
| n = len(A[0]) # total de colunas | |
| Ab = [] | |
| x = [] | |
| # Get the bases | |
| for i in range(n): # colunas | |
| for j in range(m): | |
| Ab.append(A[j][i]) | |
| if(Ab.count(0)==(m-1) and Ab.count(1)==1): | |
| x.append("x" + str(i + 1)) | |
| Ab = [] | |
| print(" ") | |
| print("# _) Valores das variaveis basicas") | |
| for i in range(len(x)): | |
| print(" _) " + str(x[i]) + " = " + str(A[i][n-1])) | |
| # Matriz com Fx, Restricoes e Identidade | |
| A = getTableByFile('input.txt') | |
| start_time = time.clock() | |
| Simplex(A[0], A[1]) | |
| end_time = time.clock() | |
| elapsedTime = end_time - start_time | |
| print "# _) Tempo de execucao %.4gs" % elapsedTime |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment