Faculdade Machado Sobrinho

Métodos Quantitativos

Aula_09 Programação Linear

Método Simplex

Denilson C. Resende

http://buscatextual.cnpq.br/buscatextual/visualizacv.jsp?id=K4761097J7&tipo=completo&idiomaExibicao=2 resendedc@gmail.com

2-O Método Simplex

Este é o procedimento geral para resolver problemas de programação linear.

É sempre usado um computador, e os programas estão amplamente disponíveis.

Utilizaremos em nosso curso o aplicativo Solver disponível nas ferramentas do Excell.

Serão apresentados os principais aspectos do método simplex para resolver qualquer problema de

2-O Método Simplex

O método simplex é um algoritmo.

Um algoritmo é um processo onde um procedimento sistemático é repetido (iterado) seguidamente até que o resultado desejado seja obtido.

Cada percurso do procedimento sistemático é chamado de iteração.

Conseqüentemente, um algoritmo substitui um problema difícil por uma série de outros fáceis.

Além das iterações, os algoritmos também incluem um procedimento de dar início e um critério para determinar quando parar.

2-O Método Simplex

Em resumo:

Passo de inicialização

Passo interativo

Regra de Parada

Preparação para iniciar interações

Repetir quantas vezes necessário

Foi obtido o resultado desejado?

Fim sim não

2-O Método Simplex

Estabelecimento do Método Simplex

É muito mais conveniente lidar com equações do que com relações de desigualdade.

Por isso, o primeiro passo para se estabelecer o método simplex é converter as restrições funcionais de desigualdade em restrições equivalentes de igualdade.

Isto é feito introduzindo variáveis de folga.

2-O Método Simplex

Seja o problema abaixo x x

x x

2-O Método Simplex

Consideremos a primeira restrição do exemplo:

A variável de folga para esta restrição é: Portanto,

A constate original x1<4 se mantém sempre que x3>0.

Conseqüentemente, x1<4 é inteiramente equivalente ao conjunto de restrições

2-O Método Simplex

Pela introdução de variáveis de folga de maneira idêntica para as outras variáveis funcionais, o modelo de programação linear original pode agora ser substituído pelo modelo equivalente.

sujeito a

2-O Método Simplex

Note-se que o novo sistema de restrições funcionais tem duas variáveis mais que equações. (3 equações e 5 variáveis)

Isto nos dá dois graus de liberdade na solução do sistema, uma vez que quaisquer duas variáveis podem ser escolhidas para serem consideradas igual a qualquer valor arbitrário a fim de resolver as três equações em termos das três variáveis restantes.

O método simplex usa o zero para este valor arbitrário.

As variáveis consideradas zero são chamadas de variáveis nãobásica.

As outras são chamadas de variáveis básicas.

A solução resultante é chamada de solução básica.

Se todas as variáveis básicas forem não-negativas, tratar-se-á de uma solução básica viável.

Pela teoria da programação linear, uma solução ótima tem que ser uma solução básica viável.

2-O Método Simplex

É conveniente considerar e manipular a equação da função-objetivo ao mesmo tempo que as novas equações de restrição. Por isso, antes de começar o método simplex o problema é escrito mais uma vez de maneira equivalente como:

Maximizar Z,

(0)Z -3x1-5x2 = 0
(1)x1+ x3= 4

sujeito a (2)2x2+x4= 12

2-O Método Simplex

Agora podemos resumir simplesmente a idéia básica do método simplex.

O sistema de equações é resolvido repetidamente para uma seqüência de soluções básicas viáveis, cada uma melhor que a sua predecessora, até que seja alcançada uma solução (básica viável) ótima.

Cada nova solução básica viável é obtida a partir de sua predecessora, transformando uma variável não-básica em variável básica (a variável básica entrando) e transformado uma variável básica numa variável não-básica ( a variável básica saindo).

Duas destas soluções básicas viáveis diferindo apenas por uma única troca de variáveis básica e não-básica são chamadas de adjacentes.

2-O Método Simplex

Resumo do Método Simplex

Passo de inicializaçãoIdentificar uma solução básica viável inicial

Passo iterativoMover-se para a melhor solução básica viável adjacente

Regra de paradaParar quando não houver nenhuma solução básica viável adjacente melhor.

Cada uma destas partes do algoritmo será descrita para o exemplo.

2-O Método Simplex

Passo de inicialização:

Introduza variáveis de folga (x3,x4,x5) como descrito acima.

Selecione as variáveis originais (x1,x2) para serem as variáveis não-básicas originais, iguale a zero e considere as variáveis de folga como sendo as variáveis básicas iniciais.

Quando estiver resolvendo um problema à mão, é conveniente usar a forma tabular do método simplex.

2-O Método Simplex

Passo de inicialização:

O quadro simplex para registro de informações inclui:

1.Os coeficientes das variáveis

2.As constantes do lado direito das equações e

3.A variável básica que aparece em cada equação. O quadro simplex para o exemploé mostrado abaixo:

Variável básica

Eq.

No.Zx1x2x3x4x5Lado direito

Coeficiente de

2-O Método Simplex

Passo de inicialização:

Uma vez que cada equação contém apenas uma variável básica, a qual tem um coeficiente de +1, cada variável básica é igual à constante do lado direito de sua equação.

Assim, a solução básica viável inicial para o

determinar se essa solução é ótima

2-O Método Simplex

Regra de parada:

A atual solução básica viável é ótima se e somente se cada coeficiente na Eq. (0) for não-negativo (> 0).

Se assim é, pare; de outro modo, vá para o passo iterativo para obter a próxima solução básica viável – a qual envolve transformar uma variável não-básica numa variável básica (parte 1) e vice-versa (parte 2) e então resolva para a nova solução (parte 3).

O exemplo possui dois coeficientes negativos, portanto, vá para o passo iterativo.

2-O Método Simplex

Determine a variável básica entrando selecionando a variável com o maior coeficiente negativo na Eq. (0).

Faça um retângulo circunscrevendo a coluna abaixo deste coeficiente que será chamada de coluna pivô.

Determine a variável básica saindo

1. selecionando cada coeficiente na coluna circunscrita que seja estritamente positivo.

2. Dividindo o valor “lado direito” de cada linha pelo coeficiente correspondente.

3. Identificando as equações que tenham as menores destas razões.

4. Selecionando a variável básica para esta equação.

2-O Método Simplex

Faça um retângulo circunscrevendo esta linha da equação no quadro à direita da coluna Z, e chame a linha circunscrita de linha pivô.

Chame também o número que está em ambos os retângulos de número pivô.

2-O Método Simplex

Passo iterativo: Parte 3:

Determine a nova solução básica viável a partir da construção de um novo quadro simplex abaixo do atual.

As três primeiras colunas não são modificadas com exceção de que a variável básica saindo na primeira coluna é substituída pela variável básica entrando.

O coeficiente da nova variável básica deverá ser mudado para +1, dividindo-se toda a linha pivô pelo número pivô, de modo que:

Nova linha pivô =antiga linha pivô número pivô

2-O Método Simplex

Variável básica

Eq.

No.Zx1x2x3x4x5Lado direito

Coeficiente de Maior coeficiente negativo

Coluna pivô Razão

12 =6 (mín) 2

Linha pivôNúmero pivô

Variável Básica que sai

Variável básica que entra

2-O Método Simplex

Variável básica

Eq.

No.Zx1x2x3x4x5Lado direito

Coeficiente de

Iteração 1

2 Nova linha pivô = antiga linha pivô número pivô

Para eliminar a nova variável básica das outras equações, todas as Linhas (inclusive da Eq.0), exceto a linha pivô, são modificadas para Usando se a seguinte fórmula: Nova linha = antiga linha – (coeficiente da coluna pivô)x nova linha pivô

2-O Método Simplex

As nova linhas do exemplo são:

-(-5)[ 0 101/20,6]
Nova linha=[ -3005/20, 30]
Linha 3 [ 32001,18]
-(2) [ 0101/20,6]
Nova linha =[ 300-1, 6]

Linha 1. Não modificada pois o coeficiente da coluna pivô é zero O novo quadro para a iteração 1, é mostrado a seguir:

2-O Método Simplex

Variável básica

Eq.

No.Zx1x2x3x4x5Lado direito

Coeficiente de

Iteração 1

Uma vez que cada variável básica é igual ao lado direito de sua equação, a nova solução viável é (0, 6, 4, 0, 6), com Z=30 Como a Eq.0 ainda possui um coeficiente negativo a solução ainda não é ótima e deve ser feita uma nova iteração.

2-O Método Simplex

Iteração

Razão

6=2 (mín) 3Linha 3 = Esta é a nova linha pivô

Nova linha= 1/3 [ 300-1,6]
=[ 100-1/31/3, 2]
Linha 0[ -300-5/20,30]
-(-3) [100-1/31/3, 2]
Nova linha =[ 0 03/2 1, 36]
Linha 1[ 10100,4]
-(1) [100-1/31/3, 2]

Nova linha = [ 0 1/3 -1/3, 2]

2-O Método Simplex

Variável básica

Eq.

No.Zx1x2x3x4x5Lado direito

Coeficiente de

Iteração 0

A solução básica viável é (2, 6, 2, 0, 0) com Z = 36 => solução ótima

Comentários