Resolução de Matriz NxM

Publicado por Karl Phillip 14/08/2004

[ Hits: 21.622 ]

Download po.py




Esse código escrito em Python resolve uma matriz NxM pelo método  Gauss-Jacobi e quando possível aplica Regressão/Eliminação (somente se todos os elementos da diagonal inferior forem igual a 0).
É um programa matemático para resolver problemas de Programação Linear (Pesquisa Operacional). Gostaria de agradecer a Aloysio de Paiva Figueiro pelo suporte durante todo o desenvolvimento do programa.

  



Esconder código-fonte

#!/usr/bin/env python

#  >> Desenvolvido em Python (LPOO)            *Windows*: http://www.cygwin.com/setup.exe
#  >> http://www.python.org                   *GNU/Linux*: http://www.python.org/download/
#  - Le uma matriz NxM do teclado 
#  - Aplica o metodo Gauss-Jacobi
#  - Aplica o Regrecao/Eliminacao 
#
# Universidade do Oeste de Santa Catarina - UNOESC / Videira
# Disciplina: Pesquisa Operacional
# Academico: Karl Phillip Buhr 

from __future__ import division                ##Para as divisoes retornarem floating points

import sys                                     ##Importa modulo Padrao

class InvalidSizeError(Exception):
  """Excessao pra levantar caso as linhas da matriz tenham tamanho diferente"""
  pass

def printM(m):                                 ##printM() imprime uma matriz na tela
  """Imprime a matriz"""
  for j in m:
    for elem in j:
      print "%3d" % elem, 
    print ""
  print ""

def readM():                                   ##readM() le uma matriz NxM do teclado
   """Le matriz do teclado"""
   matriz = []                                 ## Lista vazia para conter a matriz
   lastsize = 0                                ## Guarda o tamanho da ultima linha lida.. 
                                               ##..para comparar com a seguinte

   print ">> Entre com a MATRIZ:  (linha em branco para terminar):"
   while 1:
      r = sys.stdin.readline()                 ## Le uma linha da entrada padrao
      if r.strip():                            ## Come newlines/espacos em branco nos extremos
        l = r.split()                          ## Parte uma string nos espacos em branco.. 
                                               ##.. '1 2   32 1 2' --> ['1', '2', '32', '1', '2']
        s = len(l)                             ## s = tamanho de l
        if lastsize and  s != lastsize:        ## Se o tamanho da linha for diferente da anterior
          raise InvalidSizeError, "As linhas devem ter todas o mesmo numero de colunas." 
        matriz.append([float(elem) for elem in l]) ## Converte os elementos da linha pra inteiros..
                                                 ##.. e coloca na matriz
        lastsize = s                           ## Linha atual vira linha anterior... retoma o loop
      else:
        break                     ## Linha vazia: sai do loop
   return matriz                  ## retorna a matriz


##### Inicio da funcao que aplica os metodos  ######

def jacobi_reg(mat, ErroR, MaX): 
  COLUNAS = 0
  numIT = 1                  
  switchh = False  

##### Aplica o metodo Gauss-Jacobi ######

  LINHAS = len(mat)                              ## numero de linhas
  for C in mat[0]:
    COLUNAS += 1                                 ## numero de colunas

  print ">> Dimensao da Matriz: [%d][%d]\n" %(LINHAS, COLUNAS)  ## Imprime numero de Linhas X Colunas
  if ((COLUNAS - LINHAS) != 1):
    print ">> *** Existem mais linhas do que colunas ***\n"
    sys.exit(1)

  ###### Primeira iteracao ######
  B = list(zip(*mat)[-1])                        ## B[] Vetor que guarda a ultima coluna da matriz
  X0 = [B[i]/mat[i][i] for i in xrange(LINHAS)]  ## Guarda o result de X[i]= b1/a11 , X[i]=b2/a22 etc..
  X1 = list(X0)                                  ## X1(atual) = X0(anterior)

  ###### Segunda iteracao em diante.. ######
  numIT += 1                  
  while not switchh:
    sup = 0
    div = 0

    for i in xrange(LINHAS):
      X1[i] = B[i]
      for j in xrange(COLUNAS-1):
        if ( i != j):
          X1[i]=  (X1[i] - (mat[i][j] * X0[j]))
      X1[i] =  (1/mat[i][i] * X1[i])
      aux = X1[i] - X0[i]
      if (aux < 0) :
        aux = aux * -1
      aux2 = X1[i]
      if (aux2 < 0):
        aux2 = aux2 * -1
      if (aux > sup):
        sup = aux
      if (aux2 > div):
        div = aux2
    X0 = list(X1)
    if (sup / div) <= ErroR:
      switchh = True 
      numIT += 1
    if int(numIT) > int(MaX):
      print ">> **Impossivel** encontrar resultado em %s *iteracoes*.\n" % MaX   
      sys.exit(0)
 
  printM(mat)                                      ## Imprime MAT 
  my_cont = 0
  print "*** GauSS-JaCoBi ***"
  for i in X0:                                     ## Imprime  X, resultados de gauss-jacobi
    print "X%d = %f" % ((my_cont+1), i)
    my_cont += 1
  print "\n>> Numero de iteracoes: %d " % numIT
  print ">> Valor do erro: %s" % ErroR

####### Fim do Gauss-Jacobi #########

####### Inicio da Regrecao  #########

  print "\n\n*** ReGreSSaO/eLiMiNaCAo ***"

  for a in xrange(1, LINHAS):                      ## Checar a a triangular inferior esta zerada, 
    for b in xrange(0, COLUNAS):                 ## se nao estiver nao calcula regressao/elim
      if (int(a) != int(b)):
        if (int(mat[a][b]) != 0):
          print ">> **Impossivel** calcular com triangular inferior *diferente de 0*\n" 
          sys.exit(0)
      elif (int(a) == int(b)):
          break
        
  switchh = False
  i = LINHAS-1
  j = i 
  B[j] = B[j] / mat[i][j]
  i -= 1
  j = i
  t = 0
  numIT = 1
  COLUNAS -= 1

  while not (switchh):
    div = 0
    numIT += 1
    for t in xrange(j+1, COLUNAS):
      div = div + (mat[i][t] * B[t])
    B[j] = (B[j] - div) / mat[i][j]
    if int(i) == 0:
      switchh = True
    i -= 1
    j = i

  my_cont = 0
  for i in B:                                 ## Imprime B, vetor que guarda resultados da regressao/elim
    print "B%d = %f" % ((my_cont+1), i)
    my_cont += 1


####### Fim da Regressao #########


def main():
  erro = raw_input("\n>> Defina o ERRO: ")              ## Guarda o ERRO definido pelo usuario 
  maxx = raw_input(">> MAX iteracoes: ")                ## Guarda o MAX de iteracoes

  if int(maxx) <= 0:
    print "\n>> *** Maximo de iteracoes tem que ser > 0 ***\n"
    sys.exit(0)

  matriz = readM()                       ## Chama readM() e guarda o resultado em "matriz" 
  #matriz = [1, 0, 0, 0, 2], [0, 4, 0, 0, 15], [0, 0, 10, 0, 10], [0, 0, 0, 1, 1]
  #matriz = [1, 0, 0, 2], [0, 5, 0, 15], [0, 0, 10, 10]

  print "\n************************************************"
  jacobi_reg(matriz, erro, maxx)                      ## Chama gauss_jacobi() com paremetros
  print "\n-=*********************************************=-"
 
if __name__ == '__main__':
  main()


Scripts recomendados

QFacil 0.2 - Qemu simplificado.

Unescape de caracteres especiais ISO-8859-1

Geometria Analítica

Script para Away com varias funções para xchat.

Jogo de labirinto modo texto


  

Comentários
[1] Comentário enviado por poet em 09/08/2006 - 09:56h

Muito veio! Parabens!

[2] Comentário enviado por poet em 09/08/2006 - 09:56h

ops, Muito bom veio. Parabens!

[3] Comentário enviado por andreuebe em 06/02/2007 - 13:09h

Amigo

Este programa executa o Algoritmo Simplex?

Equivalente ao LINDO no windows?

Obrigado

Andre Uebe


Contribuir com comentário