Método Simplex
 
Método Simplex
 


O método Simplex é um algoritmo que permite resolver problemas de Programação Linear.

A ideia básica do método Simplex consiste em resolver repetidas vezes um sistema de equações lineares para obter uma sucessão de SBA, cada uma "melhor" do que a anterior, até se chegar a uma SBA óptima.

Em teoria de otimização matemática, o algoritmo simplex de George Dantzig é uma técnica popular para dar soluções numéricas de problemas da programação linear. Um método sem relação, mas chamado de maneira similar é o método Nelder-Mead ou método simplex de baixo custo devido a Nelder e Mead (1965) e é um método numérico para otimização de problemas livres multidimensionais, pertencentes à classe mais geral de algoritmos de busca.

Em ambos os casos, o método usa o conceito de um simplex, que é um polítopo de N + 1 vértices em N dimensões: um segmento de linha sobre uma linha, um triângulo sobre um plano, um tetraedro em um espaço de três dimensões e assim sucessivamente.

Estes procedimentos são válidos para problemas de maximização:

  • Introduzir as variáveis de folga, uma para cada desigualdade;
  • Montar um quadro para os cálculos, colocando os coeficientes de todas as variáveis com os respectivos sinais e, na última linha, incluir os coeficientes da função objetivo transformada;
  • Estabelecer uma solução básica inicial, usualmente atribuindo valor zero às variáveis originais e achando valores positivos para as variáveis de folga;
  • Como próxima variável a entrar na base, escolher a variável não básica que oferece, na última linha, a maior contribuição para o aumento da função objetivo (ou seja, tem o maior valor negativo). Se todas as variáveis que estão fora da base tiverem coeficientes nulos ou positivos nesta linha, a solução atual é ótima. Se alguma dessas variáveis tiver coeficiente nulo, isto significa que ela pode ser introduzida na base sem aumentar o valor da função objetivo. Isso quer dizer que temos uma solução ótima, com o mesmo valor da função objetivo.
  • Para escolher a variável que deve deixar a base, deve-se realizar o seguinte procedimento:
  • Dividir os elementos da última coluna pelos correspondentes elementos positivos da coluna da variável que vai entrar na base. Caso não haja elemento nenhum positivo nesta coluna, o processo deve parar, já que a solução seria ilimitada.
  • O menor quociente indica a equação cuja a respectiva variável básica deverá ser anulada, tornando-se variável não básica.
  • Usando operações válidas com as linhas da matriz, transformar o quadro de cálculos de forma a encontrar a nova solução básica. A coluna da nova variável básica deverá se tornar um vetor identidade, onde o elemento 1 aparece na linha correspondente à variável que está sendo anulada.
  • Retornar ao passo 4 para iniciar outra iteração.

Obtido em "http://pt.wikipedia.org/wiki/Algoritmo_simplex"

Método Simplex passo a passo

Max Z = 3x1 + 5x2

Sujeito à = 2x1 + 4x2 <=10

6x1 + x2 <=20

x1 -4x2 <=10

x1, x2 >=0

1° Passo

Igualar a Função Objetivo a zero.

Z - 3x1 -5x2 = 0

2° Passo

Acrescentar variáveis de folga nas restrições.

2x1 + 4x2 + F3 = 10

6x1 + x2 + F4 = 20

x1 - x2 + F5 = 30

3°Passo

Construir um tableau contendo os coeficientes da função e das restrições.

Z

X1

X2

F3

F4

F5

BASE

1

-3

-5

0

0

0

0

F3

0

2

4

1

0

0

10

F2

0

6

1

0

1

0

20

F5

0

1

-1

0

0

1

30

Numero pivô 4

Linha pivô F3

Coluna pivô X2

 

Base: Valores encontrados após a igualdade.

4°Passo

Escolher a coluna pivô , identificando o coeficiente de maior valor negativo absoluto na primeira linha(1°).

5°Passo

Escolher as linha pivô, dividindo se os termos da base, pelos coeficientes positivos da coluna pivô.

BASE/COEFICIENTE DA COLUNA PIVO

10/4 = 2,5

20/1 = 20

OBS: Para a escolha da linha pivô só serão analisados valores que sejam positivos.

6° Passo

O numeropivô é o coeficiente entre a coluna e a linha pivô. Ex: No Tableau.

O objetivo e que não sobrem números negativos na 1° (primeira linha).

7° Passo

Calcular a nova linha pivô, dividindo  se a antiga linha pivôpelo numero pivô.

NLP = 0 , 0,5 , 1 , 0,25 , 0 , 0 ; 2,5

8° Passo

Reescrever cada uma das outras linhas da seguinte maneira:

1° multiplicar os elementos da nova linha pivô pelo coeficiente da coluna pivô na linha com o sinal trocado.

2° somar termo à termo com os elementos da linha em questão.

NL1 = (NLP)x5+Antiga linha 1

5 x ( 0 , 0,5 , 1 , 0,25 , 0 , 0 ; 2,5 )=(0 , 2,5 , 5 , 1,25 , 0 , 0 ; 12,5) + ( 1 , -3 , -5 , 0 , 0 , 0 ;0) =

NL1 : -0,5 , 0 , 1,25 , 0 , 0 ; 12,5

NL3

-1 x ( 0 , 0,5 , 1 , 0,25 , 0 , 0 ; 2,5)=(0 , -0,5 , -1 , -0,25 , 0 , 0 ; -2,5)+(0 , 6 , 1 , 0 , -0,25 , 1 , 0 ;20)=

NL3 : 0 , 5,5 , 0 , -0,25 , 1 , 0 ; 17,5

NL4

1 x (0 , 0,5 , 1 , 0,25 , 0 , 0 ; 2,5)=(0 , 0,5 , 1 , 0,25 , 0 , 0 ; 2,5)+(0 , 1 , -1 , 0 , 0 , 1 ; 30)=

NL4 : 0 , 1,5 , 0 , 0,25 , 0 , 1 ; 32,5

Z

X1

X2

F3

F4

F5

BASE

1

-0,5

0

1,25

0

0

12,5

F3

0

0,5

1

0,25

0

0

2,5

F2

0

5,5

0

-0,25

1

0

17,5

F5

0

1,5

0

0,25

0

1

32,5

9° Passo

Se restarem números negativos na primeira linha continuar as interações a partir do 4° Passo. Se sobrarem apenas números positivos parar as interações pois este e o resultado ótimo.

10° Passo

A cada construção de um tableau trocar os valores das variáveis da coluna e linha pivô do tableau anterior.

NLP = 0 , 1 , 0 , -0,045 , 0,18 , 0 ; 3,18

NL1 = (NLP)x5+Antiga linha 1

0,5 x (0 , 1 , 0 , -0,045 , 0,18 , 0 ; 3,18)=(0 , 0,5 , 0 , -0,022 , 0,09 , 0 ; 1,59) + ( 1 , -0,5 , 0 , 1,25 , 0 , 0 ; 12,5) =

NL1 : 1 , 0 , 0 , 1,227 , 0,09, 0 ; 14,9

NL2

-0,5 x (0 , 1 , 0 , -0,045 , 0,18 , 0 ; 3,18)=(0 , -0,5 , 0 , -0,0225 , -0.09 , 0 ; -1,59)+(0 , 0,5 , 1 , 0,25 , 0 , 0 ;2,5)=

NL2 : 0 , 0 , 1 , 0,2275 , -0,09 , 0 ; 0,91

NL4

-1,5 x (0 , 1 , 0 , -0,045 , 0,18 , 0 ; 3,18)=( 0 , -1,5 , 0 , 0,0675 , -0,27 , 0 ; -4,77)+(0 , 1,5 , 0 , 0,25 , 0 , 1 ; 32,5)=

NL4 : 0 , 0 , 0 , 0,3175 , -0,27 , 1 ; 27,73

Z

F3

F4

F3

F4

F5

BASE

1

0

0

1,227

0,09

0

14,09

X2

0

0

1

0,2275

-0.09

0

0,91

X1

0

1

0

-0,045

0,18

0

3,18

F5

0

0

0

0,3175

-0,27

1

27,73

X1 = 3,18

X2 = 0,91

F3 =27,73

Z = 14,09

Max Z = 3x1 + 5x2 = 3(3,18) + 5(0,91) = 9,54 + 4,55 = 14,09 valor de Z.

Minimizar

Min Z = 3x1 + 2x2

Sujeito à : 2x1 +x2 >=10

x1 + 5x2 >=15

x1, x2 >=0

OBS: Para transformar em um problema de maximização basta multiplicar a F.O por (-1).

Min Z = 3x1 + 2x2 (-1)

Max Z = -3x1 -2x2

Sujeito à : 2x1 +x2 >=10

x1 + 5x2 >=15

x1, x2 >=0

-Z + 3x1 + 2x2 = 0

2x1 +x2 +F1 = 10

x1 + 5x2 +F2 = 15

-Z

X1

X2

F1

F2

BASE

-Z

1

3

2

0

0

0

F1

0

2

1

1

0

10

F2

0

1

5

0

1

15

Base / Numero pivô

10/2 = 5

15/1 = 15

NLP = 0 , 1 , 0,5 , 0,5 , 0 ; 5

NL1 = -3 x (0 , 1 , 0,5 , 0,5 , 0 ; 5) = (0, -3 , -1,5 , -1,5 , 0 ; -15) + (1 , 3 , 2 , 0 , 0 ; 0) =

NL1: 1 , 0 , 0,5 , -1,5 , 0 ; -15

NL3 = -1 x (0 , 1 , 0,5 , 0,5 , 0 ; 5) = (0 , -1 , -0,5 , 0,5 , 0 , -5) + (0 , 1 , 5 , 0 , 1 ;15) =

NL3: 0 , 0 , 4,5 , 0,5 , 1 ; 10

-Z

X1

X2

F1

F2

BASE

-Z

1

0

0,5

-1,5

0

-15

F1

0

1

0,5

0,5

0

5

F2

0

0

4,5

0,5

1

10

Não considerar a coluna Z.

Base / Numero pivô

5/0,5 = 10

10/4,5 = 2,22

NLP = 0 , 0 , 1 , -0,11 , 0,22 ; 2,22

NL1 = -0,5 x (0 , 0 , 1 , -0,11 , 0,22 ; 2,22) = (0, 0 , -0,5 , 0,055 , -0,11 ; -1,11) + (1 , 0 , 0,5 , -1,5 , 0 ; -15) =

NL1: 1 , 0 , 0 , -1,445 , -0,11 ; -16,11

NL2 = -0,5 x (0 , 0 , 1 , -0,11 , 0,22 ; 2,22) = (0 , 0 ,

-0,5 , 0,055 , -0,11 ;-1,11) + (0 , 1 , 0,5 , 0,5 , 0 ; 5) =

NL2: 0 , 1 , 0 , 0,555 , -0,11 ; 3,89

 
Avalie este artigo:
4 voto(s)
 
Revisado por Editor do Webartigos.com


Leia outros artigos de Orlando Augusto Nunes
Talvez você goste destes artigos também
Sobre este autor(a)
Tecnólogo em Planejamento de Transportes pelo (IFG). Contato atravês do email: [email protected] - Visite meu Blog: http://planejamentodetransportes.blogspot.com
Membro desde julho de 2007
Facebook
Informativo Webartigos.com
Receba novidades do webartigos.com em seu
e-mail. Cadastre-se abaixo:
Nome:
E-mail: