Pesquisa Operacional

Instituto de Engenharia de Produção e Gestão Universidade Federal de Itajubá

Prof. Dr. José Arnaldo Barra Montevechi Simplex

Programação Linear (PL)

Solução algébrica -método simplex

9Agora será apresentado mais um procedimento geral para resolução de problemas de PL, denominado “Método Simplex” e que foi desenvolvido em 1947 por George B.Dantzig.

Método Simplex

9O método simplex é um método interativo (algoritmo) utilizado para achar, algebricamente, a solução ótima de um problema de PL.

Procedimentos do Método Simplex

9Sabe-se que a solução ótima do modelo é uma solução básica do sistema, ou seja, um ponto extremo do polígono gerado pelas restrições.

9Para ser iniciado é necessário conhecer uma solução compatível básica (solução inicial) do sistema, isto é um dos pontos do polígono gerado.

Procedimentos do Método Simplex

9O método simplex verifica se a presente solução é ótima. Se for o processo esta encerrado. Se não for ótima, é porque um dos pontos adjacentes fornece um valor maior que o inicial.

9Neste caso, o método simplex faz então a mudança do ponto por um outro que mais aumente o valor da função objetivo.

9Agora tudo que foi feito para o primeiro ponto é feito para o novo ponto.

9O processo finaliza quando se obtém um ponto extremo onde todos os outros pontos extremos, forneçam valores menores para a função objetivo.

Procedimentos do Método Simplex

9Como fazer, algebricamente, a mudança de um ponto extremo para outro?

9Achar portanto a próxima solução básica exige a escolha de uma variável básica para deixar a base atual, tornando-se não básica, e a escolha de uma variável não básica para entrar na base em sua substituição.

Procedimentos do Método Simplex

Supondo o seguinte problema para maximização:

Procedimentos do Método Simplex

A(0, 0) B(3, 0)

C(3, 3)

D(1, 4) E(0, 4)

ZB=15 ZC=21

X2 X1

Procedimentos do Método Simplex

O Método Simplex é aplicado diretamente quando:

Passos do simplex

1.Achar uma solução compatível básica inicial;

2.Verificar se a solução é ótima. Se for pare. caso contrário, siga para o passo 3;

3.Determinar a variável não básica que deve entrar na base;

4.Determinar a variável básica que deve sair da base;

5.Achar a nova solução compatível básica e voltar ao passo 2.

Seja a formulação

Maximizar z = 3x1 + 2x2 + 5x3 Sujeito a

Primeiro passo: Transformar o sistema de M desigualdades lineares restritivas em um sistema de M equações lineares.

Assim temos: X1 + 2x2 + x3 + x4 = 430 3x1 + 2x3 + x5 = 460 xl+ 4x2 + x6 = 420

Segundo passo: Colocar as equações em forma de tabela

z -3x1 -2x2 -5x3= 0
x1 + 2x2 + x3 + x4= 430
3x1+ 2x3 + x5 = 460

xl+ 4x2 + x6 = 420

Terceiro passo: Determinar uma solução inicial viável.

X1 = X2 = X3 = 0 X4 = 430; X5 = 460 e X6 = 420

Quarto passo: verificar se a solução é ótima.

Não é ótima!

X1 = X2 = X3 = 0 X4 = 430; X5 = 460 e X6 = 420

Quinto passo: Determinar a variável que entra (xe)

Sexto passo: Determinar a variável que sai (xs).

sai entra

Pivô

Sétimo passo: Calcular a nova matriz de coeficientes, executando as operações convenientes nas linhas da matriz.

Base z X X X X X X b bi/aie

Oitavo passo: Repetir todos os passos, do 4 ao 7, tantas vezes quanto forem necessárias, até que a solução ótima seja encontrada.

O máximo Z é 1350, para X2 = 100, X3 = 230 e X6 = 20.

Resolvendo o problema de Giapetto pelo simplex

Max Z = 3X1 + 2X2 sujeito a:

2X1 + X2 ≤100
X1 + X2 ≤80
X1 ≤40
X1 ≥0

X2 ≥0

Converter o problema de PL na forma canônica

2X1 + X2 + X3= 100
X1 + X2+ X4 = 80
X1+ X5 = 40

Max Z = 3X1 + 2X2 sujeito a: X1, X2, X3, X4 e X5 ≥0

2X1 + X2 + X3= 100
X1 + X2+ X4 = 80
X1+ X5 = 40

Max Z = 3X1 + 2X2 sujeito a: X1, X2, X3, X4 e X5 ≥0

Variáveis não básicas: X1 = X2 = 0 Variáveis básicas: X3 = 100 X4 = 80 X5 = 40

Solução básica inicial

O problema pode ser representado assim:

Z X1 X2 X3 X4 X5 b Razão Base 1 -3 -2 0 0 0 0

X3 0 2 1 1 0 0 100 X4 0 1 1 0 1 0 80 X5 0 1 0 0 0 1 40

Indica que X1 entra no lugar de X5

Solução parcial: (0, 0, 100, 80, 40)

Próximo quadro -Base: X3, X4 e X1 Devem se colocadas na forma canônica

Pivo

X1 entra na base

Z X1 X2 X3 X4 X5 b Razão Base 1 0 -2 0 0 3 120

X3 0 0 1 1 0 -2 20 X4 0 0 1 0 1 -1 40 X1 0 1 0 0 0 1 40

Pivo Ainda não é a solução ótima

Indica que X2 entra no lugar de X3

Solução parcial: (40, 0, 20, 40, 0)

Próximo quadro -Base: X2, X4 e X1 Devem se colocadas na forma canônica

Segunda iteração

Z X1 X2 X3 X4 X5 b Razão Base 1 0 0 2 0 -1 160

X2 0 0 1 1 0 -2 20 X4 0 0 0 -1 1 1 20 X1 0 1 0 0 0 1 40

Ainda não é a solução ótima Pivo

Indica que X5 entra no lugar de X4

Solução parcial: (40, 20, 0, 20, 0)

Próximo quadro -Base: X2, X5 e X1 Devem se colocadas na forma canônica

Terceira iteração solução é ótima

Z X1 X2 X3 X4 X5 b Razão Base 1 0 0 1 1 0 180

X2 0 0 1 -1 2 0 60 X5 0 0 0 -1 1 1 20 X1 0 1 0 1 -1 0 20

Valor máximo possível para a função objetivo

Quarta iteração

2X1 + X2 + X3= 100
X1 + X2+ X4 = 80
X1+ X5 = 40

Max Z = 3X1 + 2X2 sujeito a: X1, X2, X3, X4 e X5 ≥0

Solução do problema de Giapetto pelo simplex

Exercício

9Resolver o problema do final do item 4.6.4 da apostila;

9Dois participantes por grupo;

9Entregar o resultado para fazer parte da avaliação da disciplina.

Resolva o problema abaixo pelo simplex maxZ = 5X1 + 2X2 sujeito a:

X1≤3
X2 ≤4
X1 + 2X2 ≤9
X1 ≥0
X2 ≥0

Método Gráfico (Exemplo já realizado anteriormente)

Indicando ponto ótimo -C (3, 3)

Z = 21

Comentários