Resolução de Matriz NxM

Publicado por Karl Phillip 14/08/2004

[ Hits: 19.498 ]

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

Script para screen shot

Herança em Python

Intefacil QEmu em pygtk

Geometria Analítica

ISOsync_pt-BR.py - Um Baixador Automático de ISOs de Sabayon, escrito em Python


  

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




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts