Created
February 26, 2017 03:30
-
-
Save angellicadearaujo/ce1d18e8fff13f7ce37d7ab78b7c3fd7 to your computer and use it in GitHub Desktop.
SIMPLEX method Linear Programming
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
| ''' 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)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment