Pesquisa Operacional - Todo Conteúdo

Prévia do material em texto

PESQUISA 
OPERACIONAL
FUNDAMENTOS
Prof. Severino Carlos de Oliveira Filho
https://iepg.gnomio.com
1
INTRODUÇÃO
• Todos nós devemos continuamente tomar
decisões na vida e nos negócios.
• Uma das maneiras mais eficazes de
analisar e avaliar alternativas de decisão
envolve o uso de planilhas eletrônicas.
• Hoje, as planilhas eletrônicas representam
a maneira mais útil e conveniente para os
executivos implementarem e analisarem
modelos em computador.
2
O QUE É UM MODELO EM COMPUTADOR?
• É um conjunto de relacionamentos matemáticos
e suposições lógicas implementados em um
computador como representação de algum
problema ou fenômeno de decisão do mundo
real.
3
O QUE É UM MODELO?
• Uma representação da realidade 
• Uma representação da realidade projetada 
para algum propósito definido.
• Uma representação da realidade que é 
planejada para ser usada por alguém 
responsável pelo gerenciamento ou 
entendimento da realidade.
4
O QUE É UM MODELO?
• Uma representação da realidade planejado
para ser usada por alguém no
entendimento, mudança, gerenciamento e
controle desta realidade.
5
O QUE É UM MODELO?
• Uma representação de parte da realidade
vista pelas pessoas que desejam usá-lo para
entender, mudar, gerenciar e controlar
aquela parte da realidade.
• Uma representação externa e explícita de
parte da realidade vista pelas pessoas que
desejam usá-lo para entender, mudar,
gerenciar e controlar parte daquela
realidade.
6
CARACTERÍSTICAS DOS MODELOS
• Modelos são versões simplificadas do objeto
ou problema de decisão que representam.
• Um modelo válido é aquele que representa
de maneira precisa as características
relevantes do objeto ou problema de decisão
que está sendo estudado.
7
BENEFÍCIOS DA MODELAGEM
• Economia - geralmente é mais barato analisar
problemas de decisão usando um modelo.
• Tempo - fornecem as informações necessárias no
tempo certo.
• Possibilidade - são úteis para examinar coisas que
seriam impossíveis de se fazer na realidade.
• Nos permitem ganhar conhecimento e
entendimento sobre o objeto ou problema de
decisão que está sendo investigado.
8
O MODELO MATEMÁTICO
Lucro = Receita - Despesas
ou
Lucro = f(Receita, Despesas)
ou
Y = f(X1, X2), onde
X1 : Receia X2 : Despesas
9
MODELO MATEMÁTICO GENÉRICO
Y = f(X1, X2,…,Xn)
Y = variável dependente 
• medida de desempenho final do problema
Xi = variáveis independentes 
• desempenham alguma função ou que têm algum 
efeito na determinação do valor de Y
f() = função que define o relacionamento entre as 
variáveis
Onde:
10
MODELOS MATEMÁTICOS E PLANILHAS
• A maioria dos modelos de planilha são
bastante similares ao modelo genérico
matemático:
Y = f(X1, X2,…,Xn)
11
CLASSIFICAÇÃO DOS MODELOS
• Modelos Esquemáticos
– representados por meio de gráficos,
tabelas, diagramas. Ex: arvores de decisão
• Modelos Matemáticos
– representado por equações e valores
numéricos ou lógicos. Ex: programação
linear
12
CLASSIFICAÇÃO DOS MODELOS
• Modelos Computacionais
–é um conjunto de relações matemáticas e
hipóteses lógicas implementadas em
computador como uma representação de
um problema real de tomada de decisão.
13
CATEGORIA DE MODELOS 
MATEMÁTICOS
14
CONCEITOS BÁSICOS
• Modelos determinísticos são resolvidos
através de sistemas de equações, utilizando-
se ferramentas computacionais como o
Solver do Excel, Lindo, Mathematica, etc...
• Modelos estocásticos são resolvidos através
de simulações, pois apresentam grande
dificuldade de obtenção de uma solução
analítica.
15
O PROCESSO DE
RESOLUÇÃO DE PROBLEMAS
Identifica-
ção do 
problema
Formulação 
e 
Implementa-
ção do 
modelo
Análise 
do 
modelo
Teste 
de 
resulta-
dos
Implemen-
tação de 
soluções
Resultados 
insatisfatórios
16
A RESOLUÇÃO DE PROBLEMAS
• Ler atentamente ao problema, quantas vezes 
for necessário.
• Retirar do enunciado do problemas os dados 
que traduzem o cenário apresentado.
• Declarar as variáveis iniciais do problema.
• Determinar as equações / inequações do 
problema
• Construir o modelo matemático (Sistema de 
Equações / Inequações)
17
EXEMPLO 1
• Um número mais a sua metade é igual a 18. 
Queremos encontrar esse número.
➢Modelo Matemático
Variáveis de decisão
x: o número que quero encontrar
Equações:
18
18
2
x
x + =
EXEMPLO 2
• Um teatro vendeu 120 entradas antecipadas,
recebendo por elas um total de R$ 8550,00. As
entradas têm os seguintes preços: inteira R$
90,00 e meia R$ 45,00. Queremos saber o
número vendido de inteiras e de meias.
19
EXEMPLO 2
❑Modelo Matemático
▪ Declaração das variáveis
I: Quantidade vendida de inteiras
M: Quantidade vendida de meias entradas
90I + 45M = 8550
I + M =120
20
EXEMPLO 3
• Um teatro vendeu 120 entradas antecipadas,
recebendo por elas um total de R$ 8550,00. As
entradas têm os seguintes preços: inteira R$
90,00 e meia R$ 45,00. O número de inteiras
vendidas não pode ultrapassar 100 bilhetes e o
número de meias não deve ser superior a 50
bilhetes. Queremos saber o número vendido
de inteiras e de meias.
21
EXEMPLO 3
❑Modelo Matemático
▪ Declaração das variáveis
I: Quantidade vendida de inteiras
M: Quantidade vendida de meias entradas
90I + 45M = 8550
I + M =120
I ≤ 100
M ≤ 50
22
EXEMPLO 4
• Uma fábrica produz dois tipos de doces: 
o doce de banana
o doce de goiaba
• Devido à limitações de matéria-prima, a produção máxima 
diária é de 5000 unidades.
• O doce de banana dá uma lucratividade de $0,37 por unidade 
produzida, enquanto que o de goiaba dá uma lucratividade de 
$0,27 por unidade produzida.
• Se a empresa pretende ter um lucro diário de $1500,00, 
quanto deve fabricar de cada sabor?
23
EXEMPLO 4
❑ Modelo Matemático:
• Variáveis de decisão
b: unidades de doce de banana produzidos
g: unidades de doce de goiaba produzidos
b + g <=5000
0,37b + 0,27g = 1500
b ≥ 0; g ≥ 0
24
EXEMPLO 5
• Um restaurante serve 3 tipos de pratos rápidos durante o horário 
do almoço aos seguintes preços:
executivo1: $8,00 executivo2: $10,00 executivo3: $12,00 
• Sabe-se que a demanda é igual e suficiente para qualquer tipo de 
prato, e que na falta de um deles o cliente faz opção por outro 
sem qualquer problema.
• Devido à limitações de matéria-prima, a capacidade máxima 
diária é de 500 refeições.
• A margem de contribuição unitária é de $4,20, $5,80 e $6,40
• Se a empresa pretende ter um lucro diário de $2735,00, num 
faturamento de $ 4900,00, quanto deve servir de cada tipo de 
prato?
25
EXEMPLO 5
❑ Modelo Matemático:
• Variáveis de decisão:
x1: quantidade de pratos Executivo1 vendidos
x2: quantidade de pratos Executivo2 vendidos
x3: quantidade de pratos Executivo3 vendidos
x1+x2+x3 ≤ 500
4,20x1+5,80x2+6,70x3 = 2375
8x1+10x2+12x3 = 4900
x1≥ 0; x2≥ 0; x3≥ 0
26
EXEMPLO 6
• Uma ceramista produz dois produtos, uma jarra e
uma vasilha. Gasta 1 hora para produzir uma
vasilha, que usa 4 quilos de argila. Uma jarra leva
2 horas e consome 3 quilos de argila. O lucro em
uma vasilha é de R$ 40,00 e de R$ 50,00 em uma
jarra. Ela trabalha 40 horas por semana, possui
120 quilos de argila disponíveis por semana, e
quer maximizar seu lucro. Neste cenários precisa
saber quanto produzir de cada produto.
27
EXEMPLO 6
Modelo Matemático (PL)
• x1: Quantidade produzida de Vasilhas
• x2: Quantidade produzida de Jarras
Função Objetivo: Max Z = 40x1 + 50x2
s.a. (conjunto de restrições)
x1 + 2x2  40
4x1 + 3x2  120
x1, x2  0
Testar valores de x1 e x2
28
29
PROGRAMAÇÃO LINEAR
❑Modelo matemático de um problema de PL
• F.O. Max Z= 1ax1 + bx2 (função objetivo)
• s.a (conjunto de restrições)
mx1+nx2 ≤ t
px1+qx2 ≤ w
x1≥0
x2≥0
FIM
30
1
PESQUISA 
OPERACIONAL
PROGRAMAÇÃO LINEAR 
MÉTODO GRÁFICO
Prof. Severino Carlos de Oliveira Filho
https://iepg.gnomio.com
2
PROGRAMAÇÃO LINEAR (PL)
• Desenvolvida conceitualmente após a segunda 
guerra pelo soviético Kolmogorov.
• Teve como objetivo resolver problemas de 
logística militar.
• Devido aos avanços computacionaisa PL 
passou a ser usada como ferramenta de gestão 
empresarial.
O MODELO MATEMÁTICO
• Um modelo matemático de PL é composto de uma 
função objetiva linear e por um conjunto de restrições 
representadas por inequações lineares.
Variáveis de decisão: x1;x2 
Função objetivo: f(x1,x2) = mx1+nx2
Restrições
ax1+bx2 ≤ p
cx1+dx2 ≤ q
x1≥0
x2 ≥0
técnicas
não negatividade
3
4
PL- EXEMPLO
• Max Z= 10x1 + 8x2 (função objetivo)
• s.a
3x1+3x2 ≤ 30
6x1+3x2≤48
x1≥0
x2≥0
5
RESOLUÇÃO GRÁFICA DE UM 
MODELO DE PL
• A indústria Maximóveis fabrica dois tipos de 
produtos: cadeiras e mesas.
Os produtos apresentam as seguintes margens 
de contribuição por unidade:
Produto Mg ($)
Cadeiras 10
Mesas 8
6
PL – EXEMPLO DE APLICAÇÃO
• Os produtos são processados por dois 
departamentos: montagem e acabamento. Ao 
passar por esses departamentos, cada unidade 
do produto consome determinado número de 
horas.
Deptos Consumo de horas em unid
Cadeiras Mesas
Montagem 3 3
Acabamento 6 3
7
PL – EXEMPLO DE APLICAÇÃO
• Os departamentos apresentam certa limitação 
em sua capacidade de produção no que diz 
respeito à disponibilidade de horas de 
trabalho.
Deptos Capacidade máx em 
horas
Montagem 30
Acabamento 48
8
PL – O OBJETIVO
• Desejamos saber: 
• Qual é a melhor combinação possível de cadeiras e 
mesas a serem produzidas, de forma a obter a maior 
margem de contribuição total, consideradas as 
limitações de capacidade dos departamentos?
9
PL- VARIÁVEIS
• Variáveis de decisão:
• x1: n.o de cadeiras produzidas
• x2: n.o de mesas produzidas
10
PL- FUNÇÃO OBJETIVO
• O objetivo do problema é maximizar a margem de 
contribuição total.
• Logo a função objetivo será:
• Máx Z=10x1+8x2
11
PL-RESTRIÇÕES
• Departamento de montagem:
• 3x1+3x2≤30
• Departamento de acabamento:
• 6x1+3x2≤48
• Não negatividade:
• x1≥0 e x2≥0
12
PL- MODELO COMPLETO
• Função objetivo 
Z=10x1+8x2
• Restrições
3x1+3x2≤30
6x1+3x2≤48
x1≥0
x2≥0
13
PL-SOLUÇÃO GRÁFICA
• Depto Montagem: 3x1+3x2≤30
10
10
Região de solução
x1
x2
14
PL-SOLUÇÃO GRÁFICA
• Depto de Acabamento: 6x1+3x2≤48
16
8 x1
x2
Região de soluções
15
PL-SOLUÇÃO GRÁFICA
• Intersecção
Dept montagem
Depto acabamento
x1
x2
8 10
10
16
Polígono de isosolução
10x1+8x2=40
x1=0→x2=5
x2=0→x1=4
0
5
4
16
PL-SOLUÇÃO GRÁFICA
• Intersecção
x1
x2
8 10
10
16
Linhas de isosolução
17
PL-SOLUÇÃO GRÁFICA
• Intersecção
x1
x2
8 10
10
16
Solução Ótima (6,4)
6
4
18
PL-SOLUÇÃO GRÁFICA
• A solução ótima sempre será um dos vértices do 
polígono de isosolução.
• Quem determina a solução ótima dentro da região de 
soluções é a função objetivo.
• Para se alterar a solução ótima deve-se mudar a 
inclinação da função objetivo, ou seja, alterar seu 
coeficiente angular.
19
EXEMPLO 3 - MIX DE PRODUTO. 
•Uma ceramista produz dois produtos, uma jarra e uma
vasilha. Gasta 1 hora para produzir uma vasilha, que usa 4 
libras de argila. Uma jarra leva 2 horas e consome 3 libras
de argila. O lucro em uma vasilha é de $40 e de $50 em
uma jarra. Ela trabalha 40 horas por semana, possui 120 
libras de argila disponíveis por semana, e quer maximizar
seu lucro.O que fazer de cada produto?
•x1: Qtidade de Jarras
•x2: Qtidade de Vasilhas
Max Z = 40x1 + 50x2 lucros
s.a.
1x1 + 2x2  40 horas
4x1+ 3x2  120 argila
x1, x2  0 não-negatividade
20
FORMULAÇÃO BÁSICA E CANÔNICA
Max Z = 40x1 + 50x2
s.a.
1x1 + 2x2  40
4x1 + 3x2  120
x1 , x2  0
Max Z = 40x1 + 50x2
s.a.
1x1 + 2x2 = 40
4x1 + 3x2 = 120
x1 , x2 ,  0
Forma canônica
21
REPRESENTAÇÃO GEOMÉTRICA
x2
40
4030
20
x1
Max Z = 40x1 + 50x2
s.a.
1x1 + 2x2 = 40
4x1 + 3x2 = 120
40x1+50x2=200
x1=0 → x2=4
x2=0 → x1= 5
0
4
5
22
REPRESENTAÇÃO GEOMÉTRICA
x2
40
4030
20
x1
Max Z = 40x1 + 50x2
s.a.
1x1 + 2x2 = 40
4x1 + 3x2 = 120
x1 = 0
x2 = 0
Z = 0
23
x2
40
4030
20
x1
REPRESENTAÇÃO GEOMÉTRICA
Max Z = 40x1 + 50x2
s.a.
1x1 + 2x2 = 40
4x1 + 3x2 = 120
x1 = 0
x2 = 20
Z = 1.000?
24
x2
40
4030
20
x1
REPRESENTAÇÃO GEOMÉTRICA
Max Z = 40x1 + 50x2
s.a.
1x1 + 2x2 = 40
4x1 + 3x2 = 120
x1 = 24
x2 = 8
Z = 1.360
25
x2
40
4030
20
x1
Representação Geométrica
Max Z = 40x1 + 50x2
s.a.
1x1 + 2x2 = 40
4x1 + 3x2 = 120
x1 = 30
x2 = 0
Z = 1.200
26
SOLUÇÃO
• Logo a solução ótima ocorrerá para
x1 = 24
x2 = 8
Z = 1.360
27
ATIVIDADE
1. Um alfaiate tem, disponíveis, os seguintes
tecidos: 16 metros de algodão, 11 metros de
seda e 15 metros de lã. Para um terno são
necessários 2 metros de algodão, 1 metro de
seda e 1 metro de lã. Para um vestido, são
necessários 1 metro de algodão, 2 metros de
seda e 3 metros de lã. Se um terno é vendido
por $300,00 e um vestido por $500,00, quantas
peças de cada tipo o alfaiate deve fazer, de
modo a maximizar o seu lucro?
28
ATIVIDADE
2.Um carpinteiro dispõe de 90, 80 e 50 metros de
compensado, pinho e cedro, respectivamente. O
produto A requer 2, 1 e 1 metro de
compensado, pinho e cedro, respectivamente. O
produto B requer 1, 2 e 1 metros,
respectivamente. Se A é vendido por $120,00 e
B por $100,00, quantos de cada produto ele
deve fazer para obter um rendimento bruto
máximo?
29
FIM
1
PESQUISA OPERACIONAL
PROGRAMAÇÃO LINEAR
MÉTODO SIMPLEX
Prof. Severino Carlos de Oliveira Filho
https://iepg.gnomio.com
O Método Simplex
❑Objetivo:
• Este é o procedimento geral para resolver
problemas de programação linear.
• É sempre usado um computador, e os
programas estão amplamente disponíveis.
2
O Método Simplex
• Utilizaremos em nosso curso o aplicativo
Solver disponível nas ferramentas do Excel.
• Serão apresentados os principais aspectos do
método simplex para resolver qualquer
problema de programação linear tal que bi > 0
para todo i = 1, 2, ...,m.
3
O Método Simplex
4
❑É aplicado diretamente quando:
• Todas as restrições são do tipo ≤ ou ≥
• Todos os bi são ≥ 0
• A função objetivo é de Maximização ou
Minimização
O Método Simplex
5
• O Método Simplex foi desenvolvido por 
George B. Dantzig em 1947.
• É um procedimento geral para resolução e 
análise de problemas de Programação Linear.
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.
6
O Método Simplex
• Consequentemente, 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. 
7
O Método Simplex
• Em resumo:
8
Estrutura dos Algoritmos:
Passo de inicialização Preparar para iniciar iterações
Passo iterativo Repetir quantas vezes necessário
Regra de parada Foi obtido o resultado desejado?
Se sim
Se não Pare
O Método Simplex
• Aplicação do 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.
9
O Método Simplex
• Sabe-se que a solução ótima do modelo é uma 
solução básica do sistema, ou seja, um dos 
vértices do polígono de iso-solução, que é gerado 
pelas restrições.
• Para se iniciar o Método Simplex é necessário 
conhecer uma solução compatível básica, 
conhecida como solução inicial do sistema.
• Esta solução corresponde a um dos pontos do 
polígono gerado pelas restrições.
10
O Método Simplex
• O Método Simplex verifica se esta solução é 
ótima, caso seja o processo está então encerrado.
• Caso contrário, se não for ótima, é porque um 
dos vértices adjacentes fornece uma solução 
melhor, com um valor maior que o inicial.
• Neste caso então o MétodoSimplex faz a 
mudança do ponto por um outro que aumente o 
valor da função objetivo.
11
O Método Simplex
• Agora tudo que foi feito para o primeiro ponto é 
feito para o novo ponto.
• O processo finaliza quando obtemos um ponto 
extremo (vértice), em que a função objetivo 
atinge seu maior valor, pois todos os outros 
pontos fornecem valores menores para a função 
objetivo.
12
13
RESOLUÇÃO PELO MÉTODO SIMPLEX DE UM 
MODELO DE PL
• A indústria Maximóveis fabrica dois tipos de 
produtos: cadeiras e mesas.
Os produtos apresentam as seguintes margens de 
contribuição por unidade:
Produto Mg ($)
Cadeiras 10
Mesas 8
14
PL – EXEMPLO DE APLICAÇÃO
• Os produtos são processados por dois 
departamentos: montagem e acabamento. Ao 
passar por esses departamentos, cada unidade do 
produto consome determinado número de horas.
Deptos Consumo de horas em unid
Cadeiras Mesas
Montagem 3 3
Acabamento 6 3
15
PL – EXEMPLO DE APLICAÇÃO
• Os departamentos apresentam certa limitação em 
sua capacidade de produção no que diz respeito à 
disponibilidade de horas de trabalho.
Deptos Capacidade máx em 
horas
Montagem 30
Acabamento 48
16
PL – O OBJETIVO
• Desejamos saber: 
• Qual é a melhor combinação possível de cadeiras e mesas a 
serem produzidas, de forma a obter a maior margem de 
contribuição total, consideradas as limitações de capacidade 
dos departamentos?
17
MÉTODO SIMPLEX
❑ Escrever o modelo matemático
❖ Construir a tabela base do modelo
• Determinar a coluna do menor coeficiente negativo
• Determinar a variável básica que entra
• Determinar a menor razão bi/xi
• Determinar a variável básica que sai
• Determina o Pivo no cruzamento
• Determinar a linha Pivo
18
MÉTODO SIMPLEX
❖ Construir a primeira Iteração 
• Entra x1 sai f2
• nLp = Lp / Pivo
• nL0 = L0 - coef x nLP
• nL1 = L1 -coef x nLp
❖ Construir a segunda Iteração
❖ Construir a segunda Iteração.................. 
19
PL- MODELO MATEMÁTICO
• Max Z= 10x1 + 8x2 (função objetivo)
• s.a
3x1+3x2 ≤ 30
6x1+3x2≤48
x1≥0
x2≥0
20
PL- MODELO MATEMÁTICO
• Max Z-10x1 - 8x2 = 0
• s.a
3x1+3x2 = 30
6x1+3x2=48
x1≥0
x2≥0
21
PL- MÉTODO SIMPLEX
Tabela Base
Menor coeficiente negativo -10
Variável básica que entra: x1
menor razão bi/xi 8
Variável básica que sai: f2
Linha Pivô: L2 Pivô 6
Var bi
Básica Linha Z x1 x2 f1 f2 bi xi
Z L0 1 -10 -8 0 0 0
f1 L1 0 3 3 1 0 30 10
f2 L2 0 6 3 0 1 48 8
22
PL- MÉTODO SIMPLEX
Iteração 1
Var bi
Básica Linha Z x1 x2 f1 f2 bi xi
Z L0 1 0 -3 0 1,667 80
f1 L1 0 0 1,5 1 -0,5 6 4
x1 L2 0 1 0,5 0 0,1667 8 16
 nL0 = L0 - coef x nLP nL1 = L1 -coef x nLp
nL0= 1-(-10)(0) = 1 nL1= 0-(3)(0) = 0
-10-(-10)(1) = 0 3-(3)(1) = 0
-8-(-10)(0,5) = -3 3-(3)(0,5) = 1,5
0-(-10)(0) = 0 1-(3)(0) = 1
0-(-10)(0,1667) = 1,667 0-(3)(0,1667) = -0,5
0-(-10)(8) = 80 30-(3)(8) = 6
23
PL- MÉTODO SIMPLEX
Iteração 2
Var bi
Básica Linha Z x1 x2 f1 f2 bi xi
Z L0 1 0 -3 0 1,66667 80 0
f1 L1 0 0 1,5 1 -0,5 6 4
x1 L2 0 1 0,5 0 0,16667 8 16
Entra x2 Sai f1
nLp = Lp / Pivo
nL0 = L0 - coef x nLP
nL1 = L1 -coef x nLp
Linha Pivô: L1 Pivô 1,5
24
PL- MÉTODO SIMPLEX
Iteração 2
Var bi
Básica Linha Z x1 x2 f1 f2 bi xi
Z L0 1 0 0 2 0,667 92
x2 L1 0 0 1 0,667 -0,333 4
x1 L2 0 1 0 -0,333 0,333 6
Parada: Todos os coeficientes da linha zero são não negativos
Solução Ótima: x2 = 4 Z= 92
x1 = 6
f1 = 0
f2 = 0
25
PL- MÉTODO SIMPLEX
❑Usando a Tecnologia
• OR Simplex
• Faça download o App para Android na Play 
Store 
• Instale e siga as instruções para resolver o 
exemplo anterior.
26
PL- MÉTODO SIMPLEX
❑OR Simplex
27
PL- MÉTODO SIMPLEX
❑OR Simplex
28
PL- MÉTODO SIMPLEX
❑OR Simplex
29
PL- MÉTODO SIMPLEX
❑OR Simplex
30
ATIVIDADE
1. Resolver pelo Método Simplex
• Min Z=4x1+x2
s.a.
2x1+2x2 ≥ 10
x1+6x2 ≥ 20
x1;x2 ≥ 0
R: x1=0, x2=5 e Z = 5
31
ATIVIDADE
2. Resolver pelo Método Simplex
• Max Z=5x1+4x2+3x3
s.a.
2x1+3x2+x3 ≤ 5
4x1+2x2+2x3 ≤ 11
3x1+2x2+2x3 ≤ 8
x1;x2;x3 ≥ 0
R: x1=2 ; x2=0; x3=1; Z=13
32
ATIVIDADE
3. Um alfaiate tem, disponíveis, os seguintes tecidos:
16 metros de algodão, 11 metros de seda e 15
metros de lã. Para um terno são necessários 2
metros de algodão, 1 metro de seda e 1 metro de
lã. Para um vestido, são necessários 1 metro de
algodão, 2 metros de seda e 3 metros de lã. Se um
terno é vendido por $300,00 e um vestido por
$500,00, quantas peças de cada tipo o alfaiate deve
fazer, de modo a maximizar o seu lucro?
R: Z= $3100,00 x1=7 ternos x2=2 vestidos
33
ATIVIDADE
4. Um carpinteiro dispõe de 90, 80 e 50 metros de
compensado, pinho e cedro, respectivamente. O
produto A requer 2, 1 e 1 metros de compensado,
pinho e cedro, respectivamente. O produto B
requer 1, 2 e 1 metros, respectivamente. Se A é
vendido por $120,00 e B por $100,00, quantos de
cada produto ele deve fazer para obter um
rendimento bruto máximo?
R: Z= $5800,00 x1=40 unid de A x2=10 unis de B
34
O Método Simplex
FIM
1
PESQUISA OPERACIONAL
PROGRAMAÇÃO LINEAR
USO DA FERAMENTA SOLVER
Prof. Severino Carlos de Oliveira Filho
https://iepg.gnomio.com
2
RESOLUÇÃO DE UM MODELO DE PL
ATRAVÉS DO SOLVER
• A indústria Maximóveis fabrica dois tipos de 
produtos: cadeiras e mesas.
Os produtos apresentam as seguintes margens 
de contribuição por unidade:
Produto Mg ($)
Cadeiras 10
Mesas 8
3
PL – EXEMPLO DE APLICAÇÃO
• Os produtos são processados por dois 
departamentos: montagem e acabamento. Ao 
passar por esses departamentos, cada unidade 
do produto consome determinado número de 
horas.
Deptos Consumo de horas em unid
Cadeiras Mesas
Montagem 3 3
Acabamento 6 3
4
PL – EXEMPLO DE APLICAÇÃO
• Os departamentos apresentam certa limitação 
em sua capacidade de produção no que diz 
respeito à disponibilidade de horas de 
trabalho.
Deptos Capacidade máx em 
horas
Montagem 30
Acabamento 48
5
PL – O OBJETIVO
• Desejamos saber: 
• Qual é a melhor combinação possível de cadeiras e 
mesas a serem produzidas, de forma a obter a maior 
margem de contribuição total, consideradas as 
limitações de capacidade dos departamentos?
6
PL- VARIÁVEIS
• Variáveis de decisão:
• x1: n.o de cadeiras produzidas
• x2: n.o de mesas produzidas
7
PL- FUNÇÃO OBJETIVO
• O objetivo do problema é maximizar a margem de 
contribuição total.
• Logo a função objetivo será:
• Máx MgT=10x1+8x2
8
PL-RESTRIÇÕES
• Departamento de montagem:
• 3x1+3x2 ≤ 30
• Departamento de acabamento:
• 6x1+3x2 ≤ 48
• Não negatividade:
• x1 ≥ 0 e x2 ≥ 0
9
PL- MODELO COMPLETO
• Função objetivo 
MgT=10x1+8x2
• Restrições
3x1+3x2 ≤ 30
6x1+3x2 ≤ 48
x1 ≥ 0
x2 ≥ 0
10
PL – USANDO O SOLVER
• A ferramenta SOLVER do MS-Excel trabalha com 
PL de forma rápida e eficiente.
• Abra o MS-Excel na aba Dados e verifique se o 
Solver está instalado.
• Se não tiver vá em:
Arquivos -> Opções-> Gerenciar Suplementos do 
Excel-> ir e selecione:
– Ferramenta de Análise
– Ferramenta de Análise VBA
– SOLVER
11
PL – SOLUÇÃO SOLVER
12
PL – SOLUÇÃO SOLVER
SOLVER
CADEIRAS MESAS
C M
Qtidade a produzir 6 4
MgT 10 8 92 Função objetivo
Restrições HD HU Folga
Depto Montagem 3 3 30 30 0
Depto Acabamento 6 3 48 48 0
13
EXEMPLO 3 - MIX DE PRODUTO. 
•Uma ceramista produz dois produtos, uma jarra e uma
vasilha. Gasta 1 hora para produzir uma vasilha, que usa 4 
libras de argila. Uma jarra leva 2 horas e consome 3 libras
de argila. O lucro em uma vasilha é de $40 e de $50 em
uma jarra. Ela trabalha 40 horas por semana, possue 120 
libras de argila disponíveis por semana, e quer maximizar
seu lucro.O que fazer de cada produto?
Max Z = 40x + 50y lucros
s.a.
1x + 2y  40 horas
4x + 3y  120 argila
x, y  0 não-negatividade
14
FORMULAÇÃO BÁSICA E CANÔNICA
Max Z = 40x1 + 50x2
s.a.
1x1 + 2x2  40
4x1 + 3x2  120
x1 , x2  0
Max Z = 40x1 + 50x2
s.a.
1x1 + 2x2 + f1 = 40
4x1 + 3x2 + f2 = 120
x1 , x2 , f1 , f2  0
Forma canônica
15
SOLUÇÃO - SOLVER
SOLVER
JARRA VAZILHA
J V
Qtidade a produzir 8 24MgT 50 40 1360 Função objetivo
Restrições HD HU Folga
Tempo produção 2 1 40 40 0
Qtidade argila 3 4 120 120 0
16
EXEMPLO 3 
• A indústria Selton fabrica três modelos de 
computadores: PC 100, PC 200 e PC 300 .
Os produtos apresentam as seguintes 
margens de contribuição por unidade:
Produto Mg ($)
PC100 150
PC200 210
PC300 280
17
PL – Exemplo de aplicação
• Os produtos são manufaturados por três 
departamentos: montagem, testes e embalagem. Ao 
passar por esses departamentos, cada unidade do 
produto consome determinado número de horas.
Deptos Consumo de horas em unid
PC100 PC200 PC300
Montagem 1 1,5 3
Testes 1 2 3
Embalagem 0.20 0.30 0.50
18
PL – Exemplo de aplicação
• Os departamentos apresentam certa 
limitação em sua capacidade de produção 
no que diz respeito à disponibilidade de 
horas de trabalho.
Deptos Capacidade máx em 
horas
Montagem 185
Testes 200
Embalagem 33
19
PL – O objetivo
• Desejamos saber: Qual é a melhor combinação 
possível de modelos de computadores a serem 
produzidos, de forma a obter a maior margem de 
contribuição total, consideradas as limitações de 
capacidade dos 3 departamentos?
20
PL- Variáveis
Variáveis de decisão:
• x1: n.o de PC100 produzidos
• x2: n.o de PC200 produzidos
• x3: n.o de PC300 produzidos
21
PL- Função Objetivo
• O objetivo do problema é maximizar a margem de 
contribuição total.
• Logo a função objetivo será:
• Máx MgT=150x1+210x2+280x3
22
PL-Restrições
• Departamento de montagem:
1x1 + 1,5x2 +3x2 ≤ 185
• Departamento de testes:
1x1+2x2+3x3 ≤ 200
• Departamento de empacotamento:
0,2x1+0,3x2+0,5x3 ≤ 33
• Não negatividade:
X1 ≥0; X2 ≥ 0; X3 ≥ 0 
23
PL- Modelo Completo
• Função objetivo 
MgT=150x1+210x2+280x3
• Restrições
1x1 + 1,5x2 +3x2 ≤ 185
1x1+2x2+3x3 ≤ 200
0,2x1+0,3x2+0,5x3 ≤ 33
x1 ≥0; x2 ≥ 0; x3 ≥ 0 
24
Solução usando o Solver
P100 P200 P300 Total
Produção 0 0 0
Mg 150 210 280 0
Horas Horas
Restrições Utilizadas Disponíveis
Depto Montagem 1 1,5 3 0 185
Depto Teste 1 2 3 0 200
Depto Embalagem 0,2 0,3 0,5 0 33
SELTON COMPUTADORES
25
SOLVER (Opções)
26
SOLVER (Opções)
27
Solução usando o Solver
P100 P200 P300 Total
Produção 0 100 0
Mg 150 210 280 21000
Horas Horas
Restrições Utilizadas Disponíveis
Depto Montagem 1 1,5 3 150 185
Depto Teste 1 2 3 200 200
Depto Embalagem 0,2 0,3 0,5 30 33
SELTON COMPUTADORES
28
Solução usando o Solver
P100 P200 P300 Total
Produção 60 70 0
Mg 150 210 280 23700
Horas Horas
Restrições Utilizadas Disponíveis
Depto Montagem 1 1,5 3 165 185
Depto Teste 1 2 3 200 200
Depto Embalagem 0,2 0,3 0,5 33 33
SELTON COMPUTADORES
29
Solução usando o Solver
P100 P200 P300 Total
Produção 165 0 0
Mg 150 210 280 24750
Horas Horas
Restrições utilizadas disponíveis
Depto Montagem 1 1,5 3 165 185
Depto Teste 1 2 3 165 200
Depto Embalagem 0,2 0,3 0,5 33 33
SELTON COMPUTADORES
EXERCÍCIO 
• Certa empresa fabrica dois produtos P1 e P2. O 
lucro unitário do produto P1 é de $1000 e o de P2 é 
$1800. A empresa precisa de 20 h para fabricar uma 
unidade de P1 e de 30 horas para fabricar uma 
unidade de P2.O tempo anual de produção 
disponível para isso é 1200 h. A demanda esperada 
para P1 é 40 unid anuais e para P2 é 30 unidades 
anuais. Qual é o plano de produção para que a 
empresa maximize seu lucro nesses itens? Construa 
o modelo matemático. 
30
EXERCÍCIO 
Produtos: P1 e P2
Variáveis de decisão: x1; x2
x1: quantidade anual produzida de P1
x2: quantidade anual produzida de P2
Função Objetivo: Max L=1000x1+1800x2
Restrições:
20x1+30x2≤1200
x1 ≤40
x2 ≤30
x1;x2 ≥0 31
32
SOLVER
FIM
	PO - Fundamentos
	PESQUISA OPERACIONAL FUNDAMENTOS Prof. Severino Carlos de Oliveira Filho https://iepg.gnomio.com 
	INTRODUÇÃO
	 O QUE É UM MODELO EM COMPUTADOR?
	 O QUE É UM MODELO?
	 O QUE É UM MODELO?
	O QUE É UM MODELO?
	CARACTERÍSTICAS DOS MODELOS
	BENEFÍCIOS DA MODELAGEM
	O MODELO MATEMÁTICO
	MODELO MATEMÁTICO GENÉRICO
	MODELOS MATEMÁTICOS E PLANILHAS
	CLASSIFICAÇÃO DOS MODELOS
	CLASSIFICAÇÃO DOS MODELOS
	CATEGORIA DE MODELOS MATEMÁTICOS
	 CONCEITOS BÁSICOS
	O PROCESSO DE RESOLUÇÃO DE PROBLEMAS
	 A RESOLUÇÃO DE PROBLEMAS
	 EXEMPLO 1
	 EXEMPLO 2
	 EXEMPLO 2
	 EXEMPLO 3
	 EXEMPLO 3
	 EXEMPLO 4
	 EXEMPLO 4
	 EXEMPLO 5
	EXEMPLO 5
	 EXEMPLO 6
	 EXEMPLO 6
	PROGRAMAÇÃO LINEAR
	Slide 30 
	Programação Linear - Método Gráfico
	PESQUISA OPERACIONAL PROGRAMAÇÃO LINEAR MÉTODO GRÁFICO Prof. Severino Carlos de Oliveira Filho https://iepg.gnomio.com 
	PROGRAMAÇÃO LINEAR (PL)
	 O MODELO MATEMÁTICO
	PL- EXEMPLO
	 RESOLUÇÃO GRÁFICA DE UM MODELO DE PL
	PL – EXEMPLO DE APLICAÇÃO
	PL – EXEMPLO DE APLICAÇÃO
	PL – O OBJETIVO
	PL- VARIÁVEIS
	PL- FUNÇÃO OBJETIVO
	PL-RESTRIÇÕES
	PL- MODELO COMPLETO
	PL-SOLUÇÃO GRÁFICA
	PL-SOLUÇÃO GRÁFICA
	PL-SOLUÇÃO GRÁFICA
	PL-SOLUÇÃO GRÁFICA
	PL-SOLUÇÃO GRÁFICA
	PL-SOLUÇÃO GRÁFICA
	EXEMPLO 3 - MIX DE PRODUTO. 
	FORMULAÇÃO BÁSICA E CANÔNICA
	REPRESENTAÇÃO GEOMÉTRICA
	REPRESENTAÇÃO GEOMÉTRICA
	REPRESENTAÇÃO GEOMÉTRICA
	REPRESENTAÇÃO GEOMÉTRICA
	Slide 25 
	SOLUÇÃO
	ATIVIDADE
	ATIVIDADE
	Slide 29 
	O Metodo SIMPLEX
	PESQUISA OPERACIONAL PROGRAMAÇÃO LINEAR MÉTODO SIMPLEX Prof. Severino Carlos de Oliveira Filho https://iepg.gnomio.com
	O Método Simplex
	O Método Simplex
	O Método Simplex
	O Método Simplex
	O Método Simplex
	O Método Simplex
	O Método Simplex
	O Método Simplex
	O Método Simplex
	O Método Simplex
	O Método Simplex
	 RESOLUÇÃO PELO MÉTODO SIMPLEX DE UM MODELO DE PL
	PL – EXEMPLO DE APLICAÇÃO
	PL – EXEMPLO DE APLICAÇÃO
	PL – O OBJETIVO
	MÉTODO SIMPLEX
	MÉTODO SIMPLEX
	PL- MODELO MATEMÁTICO
	PL- MODELO MATEMÁTICO
	PL- MÉTODO SIMPLEX
	PL- MÉTODO SIMPLEX
	PL- MÉTODO SIMPLEX
	PL- MÉTODO SIMPLEX
	PL- MÉTODO SIMPLEX
	PL- MÉTODO SIMPLEX
	PL- MÉTODO SIMPLEX
	PL- MÉTODO SIMPLEX
	PL- MÉTODO SIMPLEX
	ATIVIDADE
	ATIVIDADE
	ATIVIDADE
	ATIVIDADE
	Slide 34 
	Programação Linear - Solver