Pesquisa Operacional
na Tomada de Decisões
Resolvendo Programação Linear
Em um Microcomputador
2ª Edição
Capítulo 3.1
© Gerson Lachtermacher,2005
Conteúdos do Capítulo
 Resolvendo Problemas Usando Solver do Excel


Definindo o Modelo no Solver
Obtendo a Solução
 Teorema da Dualidade

Comparando as soluções do Primal e Dual
Capítulo 3.1
Problemas em Forma Padrão
 São 4 características de um problema na forma padrão
Maximizar
Z = c1 x1 + c 2 x 2 + ... + c n x n
Sujeito a :
a11 x1 + a12 x 2 + ... + a1 n x n  b1
a 21 x1 + a 22 x 2 + ... + a 2 n x n  b 2
:
a m 1 x1 + a m 2 x 2 + ... + a mn x n  b m
x1 , x 2 , x 3 ,... x n  0
Capítulo 3.1
positivos
Problemas em
Forma não Padrão
 Portanto, se qualquer uma das 4 características não
puder ser observada, o problema não está na sua forma
padrão.
Max 5 x1 + 5 x2 + 3x3
Min 5 x1 + 5 x2 + 3x3
s.r.
x1 + 3x2 + x3  3
- x1
+ 3x3  2
s.r.
x1 + 3x2 + x3  3
- x1
+ 3x3  -2
x1 , x2 , x3  0
x1 , x2 , x3  0
Capítulo 3.1
Resolvendo Problemas
em Forma não Padrão
 Existem técnicas de reduzir problemas em formas
genéricas para a forma padrão.
 Usaremos softwares genéricos e específicos para
resolver problemas de Programação Linear

Solver do Excel ®

LINDO ® (www.lindo.com para versão educacional)
Capítulo 3.1
Resolvendo Problemas
Usando Solver do Excel
 Considere o Problema
Max z = 3 x1 + 2 x 2
st
x1 + 2 x 2  6
2 x1 + x 2  8
- x1 + x 2  1
x2  2
x1 ; x 2  0
Capítulo 3.1
Usando Solver do Excel
Entrando os Parâmetros do Modelo
Max z = 3 x1 + 2 x 2
st
x1 + 2 x 2  6
2 x1 + x 2  8
- x1 + x 2  1
x2  2
x1 ; x 2  0
Capítulo 3.1
Usando Solver do Excel
Definindo a Célula do Valor Ótimo
Capítulo 3.1
Usando Solver do Excel
Definindo as variáveis de Folga ou Excesso
Capítulo 3.1
Usando Solver do Excel
Iniciando o Solver
Capítulo 3.1
Usando Solver do Excel
Definindo a Célula Ótima (Z)
Capítulo 3.1
Usando Solver do Excel
Definindo as Células Variáveis
Capítulo 3.1
Usando Solver do Excel
Definindo as Restrições
Capítulo 3.1
Usando Solver do Excel
Definindo Condições de Não Negatividade
Capítulo 3.1
Usando Solver do Excel
Condições de Não Negatividade
Capítulo 3.1
Usando Solver do Excel
Definindo Variáveis Inteiras e Binárias
Capítulo 3.1
Usando Solver do Excel
Definindo o Problema de Programação Linear
Capítulo 3.1
Usando Solver do Excel
Obtendo a Solução
Capítulo 3.1
Usando Solver do Excel
Verificando a Resposta
Capítulo 3.1
Solver do Excel
Relatório de Resposta
Capítulo 3.1
Solver do Excel
Relatório de Sensibilidade
Capítulo 3.1
Solver do Excel
Relatório de Limites
Capítulo 3.1
Resolvendo Problemas
Usando Solver do Excel
 Resolva o problema usando o solver do Excel.
Max 5x1 + 5x2 + 3x3
s. r.
x1 + 3x2 + x3  3
- x1
+ 3 x3  2
2 x1 - x2 + 2 x3  4
2 x1 + 3x2 - x3  2
x1 , x2 , x3  0
Capítulo 3.1
Resolvendo Problemas
Usando Solver do Excel - Modelo
= somarproduto(B3:D3;B4:D4)
=somarproduto($B$4:$D$4;B9:D9)
Capítulo 3.1
Definindo o Modelo no Solver
Capítulo 3.1
Definindo o Modelo no Solver
Capítulo 3.1
Obtendo a Solução
Capítulo 3.1
Teorema da Dualidade
Usando o Excel
 Compare a resposta do problema abaixo e seu dual.
Max Z = 3 x1 + 2 x2 + x3 + 6 x4 + 5 x5 + 4 x6
s.r. x1 + x2 + x3 = 10
x4 + x5 + x6 = 15
3 x1 + 2 x2 + x4 + 3 x5  20
x2 + x3 + 2 x4 + x6  30
x1 , x2 , x3  0
x4 , x5 , x6 sem restrições de sinal
Capítulo 3.1
Modelando em Excel
=somarproduto(B3:G3;B4:G4)
=somarproduto($B$4:$G$4;B9:G9)
Capítulo 3.1
Modelando em Excel
Parametrizando o Solver
Capítulo 3.1
Modelando em Excel
Solução do Primal
Capítulo 3.1
Modelo do Dual
Min 10 y1 + 15 y 2 + 20 y3 + 30 y 4
st
y1 + 3 y3  3
y1 + 2 y3 + y 4  2
y1 + y 4  1
y 2 + y3 + 2 y 4 = 6
y 2 + 3 y3 = 5
y2 + y4 = 4
y3 ; y 4  0 e y1 ; y 2 quaisquer
Capítulo 3.1
As duas primeiras restrições
são igualdades
Dual no Excel
Capítulo 3.1
Parametrizando o Solver
Capítulo 3.1
Solução do Dual
Capítulo 3.1
Comparação Primal x Dual
Primal
Dual
Capítulo 3.1