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:
  • <!--[if !supportLists]--><!--[endif]-->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.
  • <!--[if !supportLists]--><!--[endif]-->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