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:

• <!--[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 = 3x₁ + 5x₂

Sujeito à = 2x₁ + 4x₂ <=10

6x₁ + x₂ <=20

x₁ -4x₂ <=10

x₁, x₂ >=0

1° Passo

Igualar a Função Objetivo a zero.

Z - 3x₁ -5x₂ = 0

2° Passo

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

2x₁ + 4x₂ + F₃ = 10

6x₁ + x₂ + F₄ = 20

x₁ - x₂ + F₅ = 30

3°Passo

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

Numero pivô 4

Linha pivô F₃

Coluna pivô X₂

 

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

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

X₁ = 3,18

X₂ = 0,91

F₃ =27,73

Z = 14,09

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

Minimizar

Min Z = 3x₁ + 2x₂

Sujeito à : 2x₁ +x₂ >=10

x₁ + 5x₂ >=15

x₁, x₂ >=0

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

Min Z = 3x₁ + 2x₂ (-1)

Max –Z = -3x₁ -2x₂

Sujeito à : 2x₁ +x₂ >=10

x₁ + 5x₂ >=15

x₁, x₂ >=0

-Z + 3x₁ + 2x₂ = 0

2x₁ +x₂ +F₁ = 10

x₁ + 5x₂ +F₂ = 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

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