Metodo grafico

Prévia do material em texto

Pesquisa Operacional
Prof. Paulo Arce
Pesquisa Operacional - Prof Paulo Arce 1
Programação Linear – Solução Pelo Método Gráfico
Pesquisa Operacional - Prof Paulo Arce 2
Situação Problema 
(Diferentes 
naturezas)
Modelagem 
(Teoria, 
experiência, 
observação...)
Resolução 
(Técnicas) e 
Simulação
Aplicação na 
tomada de decisão
Programação Linear – Solução Pelo Método Gráfico
• Boa aplicação didática pois permite um entendimento claro sobre o 
que acontece na resolução de um problema de PL;
• Utilizado para resolução de problemas com duas variáveis;
• Três passos para obtenção da solução ótima
• (1) – Identificação da Região Viável
• (2) – Determinação das Curvas de Nível
• (3) – Identificação do Ponto Ótimo
Pesquisa Operacional - Prof Paulo Arce 3
Exemplo 1 – Mix de Produção
A Brinquedos S.A. fabrica dois tipos de brinquedos de madeira: soldados e trens. Um
soldado é vendido por R$ 27,00 e usa R$ 10,00 de matéria prima. Cada soldado
fabricado aumenta os custos diretos de mão de obra e custos indiretos em R$ 14,00. Um
trem é vendido a R$ 21,00 e utiliza R$ 9,00 de matéria prima. Cada trem aumenta custos
de mão de obra e indiretos em R$ 10,00. A fabricação requer dois tipos de mão de obra:
carpinteiro e pintor. A fabricação de um soldado requer 2 horas de um pintor e 1 hora de
um carpinteiro. Um trem demanda 1 hora de pintura e 1 hora de carpintaria. Para cada
semana, a Brinquedos pode conseguir toda a matéria prima necessária, mas apenas 100
horas de pintura e 80 horas de carpintaria. A demanda para os trens é ilimitada, mas a
de soldados é de no máximo 40 por semana.
A Brinquedos quer maximizar seu lucro semanal.
a) Encontre um modelo em PL para o problema apresentado;
b) Resolva o problema de PL pelo método gráfico.
Programação Linear – Solução Pelo Método Gráfico
Pesquisa Operacional - Prof Paulo Arce 4
a) Encontre um modelo em PL para o problema apresentado;
• 𝑥1: 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑠𝑒𝑚𝑎𝑛𝑎𝑙 𝑑𝑒 𝑠𝑜𝑙𝑑𝑎𝑑𝑜𝑠 𝑝𝑟𝑜𝑑𝑢𝑧𝑖𝑑𝑜𝑠
• 𝑥2: 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑠𝑒𝑚𝑎𝑛𝑎𝑙 𝑑𝑒 𝑡𝑟𝑒𝑛𝑠 𝑝𝑟𝑜𝑑𝑢𝑧𝑖𝑑𝑜𝑠
• Z: lucro semanal
max𝑍 = 3𝑥1 + 2𝑥2
𝑠. 𝑎.
2𝑥1 + 𝑥2 ≤ 100 𝑝𝑖𝑛𝑡𝑢𝑟𝑎
𝑥1 + 𝑥2 ≤ 80 𝑐𝑎𝑟𝑝𝑖𝑛𝑡𝑎𝑟𝑖𝑎
𝑥1 ≤ 40 (𝑚á𝑥 𝑑𝑒𝑚𝑎𝑛𝑑𝑎 𝑑𝑒 𝑠𝑜𝑙𝑑𝑎𝑑𝑜𝑠)
𝑥1, 𝑥2 ≥ 0 𝑛ã𝑜 − 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑𝑒
Programação Linear – Solução Pelo Método Gráfico
Pesquisa Operacional - Prof Paulo Arce 5
b) Resolva o problema de PL pelo método gráfico.
max𝑍 = 3𝑥1 + 2𝑥2
𝑠. 𝑎.
2𝑥1 + 𝑥2 ≤ 100 𝑝𝑖𝑛𝑡𝑢𝑟𝑎
𝑥1 + 𝑥2 ≤ 80 𝑐𝑎𝑟𝑝𝑖𝑛𝑡𝑎𝑟𝑖𝑎
𝑥1 ≤ 40 (𝑚á𝑥 𝑑𝑒𝑚𝑎𝑛𝑑𝑎 𝑑𝑒 𝑠𝑜𝑙𝑑𝑎𝑑𝑜𝑠)
𝑥1, 𝑥2 ≥ 0 𝑛ã𝑜 − 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑𝑒
(1) – Identificação da Região Viável
Programação Linear – Solução Pelo Método Gráfico
Pesquisa Operacional - Prof Paulo Arce 6
b) Resolva o problema de PL pelo método gráfico.
max𝑍 = 3𝑥1 + 2𝑥2
𝑠. 𝑎.
2𝑥1 + 𝑥2 ≤ 100 𝑝𝑖𝑛𝑡𝑢𝑟𝑎
𝑥1 + 𝑥2 ≤ 80 𝑐𝑎𝑟𝑝𝑖𝑛𝑡𝑎𝑟𝑖𝑎
𝑥1 ≤ 40 (𝑚á𝑥 𝑑𝑒𝑚𝑎𝑛𝑑𝑎 𝑑𝑒 𝑠𝑜𝑙𝑑𝑎𝑑𝑜𝑠)
𝑥1, 𝑥2 ≥ 0 𝑛ã𝑜 − 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑𝑒
(1) – Identificação da Região Viável
Programação Linear – Solução Pelo Método Gráfico
Pesquisa Operacional - Prof Paulo Arce 7
b) Resolva o problema de PL pelo método gráfico.
max𝑍 = 3𝑥1 + 2𝑥2
𝑠. 𝑎.
2𝑥1 + 𝑥2 ≤ 100 𝑝𝑖𝑛𝑡𝑢𝑟𝑎
𝑥1 + 𝑥2 ≤ 80 𝑐𝑎𝑟𝑝𝑖𝑛𝑡𝑎𝑟𝑖𝑎
𝑥1 ≤ 40 (𝑚á𝑥 𝑑𝑒𝑚𝑎𝑛𝑑𝑎 𝑑𝑒 𝑠𝑜𝑙𝑑𝑎𝑑𝑜𝑠)
𝑥1, 𝑥2 ≥ 0 𝑛ã𝑜 − 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑𝑒
(1) – Identificação da Região Viável
Programação Linear – Solução Pelo Método Gráfico
Pesquisa Operacional - Prof Paulo Arce 8
b) Resolva o problema de PL pelo método gráfico.
max𝑍 = 3𝑥1 + 2𝑥2
𝑠. 𝑎.
2𝑥1 + 𝑥2 ≤ 100 𝑝𝑖𝑛𝑡𝑢𝑟𝑎
𝑥1 + 𝑥2 ≤ 80 𝑐𝑎𝑟𝑝𝑖𝑛𝑡𝑎𝑟𝑖𝑎
𝑥1 ≤ 40 (𝑚á𝑥 𝑑𝑒𝑚𝑎𝑛𝑑𝑎 𝑑𝑒 𝑠𝑜𝑙𝑑𝑎𝑑𝑜𝑠)
𝑥1, 𝑥2 ≥ 0 𝑛ã𝑜 − 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑𝑒
(1) – Identificação da Região Viável
• A região viável forma um polígono
• A resposta ótima está em um dos vértices do 
polígono
• Para descobrir em qual dos vértices está a 
resposta ótima, traçamos as curvas de nível da 
F.O.
Programação Linear – Solução Pelo Método Gráfico
Pesquisa Operacional - Prof Paulo Arce
9
b) Resolva o problema de PL pelo método gráfico.
max𝑍 = 3𝑥1 + 2𝑥2
𝑠. 𝑎.
2𝑥1 + 𝑥2 ≤ 100 𝑝𝑖𝑛𝑡𝑢𝑟𝑎
𝑥1 + 𝑥2 ≤ 80 𝑐𝑎𝑟𝑝𝑖𝑛𝑡𝑎𝑟𝑖𝑎
𝑥1 ≤ 40 (𝑚á𝑥 𝑑𝑒𝑚𝑎𝑛𝑑𝑎 𝑑𝑒 𝑠𝑜𝑙𝑑𝑎𝑑𝑜𝑠)
𝑥1, 𝑥2 ≥ 0 𝑛ã𝑜 − 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑𝑒
(2) – Determinação das Curvas de Nível
• A partir das curvas de nível podemos 
identificar a direção de crescimento da 
F.O.
• O ponto de máximo será o último que 
alguma curva de nível ainda toca a região 
viável 
Programação Linear – Solução Pelo Método Gráfico
Pesquisa Operacional - Prof Paulo Arce 10
b) Resolva o problema de PL pelo método gráfico.
max𝑍 = 3𝑥1 + 2𝑥2
𝑠. 𝑎.
2𝑥1 + 𝑥2 ≤ 100 𝑝𝑖𝑛𝑡𝑢𝑟𝑎
𝑥1 + 𝑥2 ≤ 80 𝑐𝑎𝑟𝑝𝑖𝑛𝑡𝑎𝑟𝑖𝑎
𝑥1 ≤ 40 (𝑚á𝑥 𝑑𝑒𝑚𝑎𝑛𝑑𝑎 𝑑𝑒 𝑠𝑜𝑙𝑑𝑎𝑑𝑜𝑠)
𝑥1, 𝑥2 ≥ 0 𝑛ã𝑜 − 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑𝑒
(3) – Identificação do Ponto Ótimo
• O ponto ótimo atende às restrições que o tangem:
ቊ
2𝑥1 + 𝑥2 = 100
𝑥1 + 𝑥2 = 80
𝑅𝑒𝑠𝑜𝑙𝑣𝑒𝑛𝑑𝑜 𝑜 𝑠𝑖𝑠𝑡𝑒𝑚𝑎, 𝑜𝑏𝑡𝑒𝑚𝑜𝑠:
𝑥1 = 20 𝑒 𝑥2 = 60
𝑆𝑢𝑏𝑠𝑡𝑖𝑡𝑢𝑖𝑛𝑑𝑜 𝑒𝑠𝑡𝑒𝑠 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝑒𝑚 𝑧, 𝑜𝑏𝑡𝑒𝑚𝑜𝑠 𝑜 𝑙𝑢𝑐𝑟𝑜 ó𝑡𝑖𝑚𝑜
𝑍 = 3 ∗ 20 + 2 ∗ 60 = 180
Programação Linear – Solução Pelo Método Gráfico
Pesquisa Operacional - Prof Paulo Arce
11
Programação Linear – Solução Pelo Método Gráfico
Comentários Adicionais
• Região Viável e Solução
• Região Viável sempre será um polígono (2 dimensões), poliedro (3 
dimensões) ou hiperpoliedro (mais de 3 dimensões)
• Solução ótima sempre se encontra em um dos vértices (característica usada 
pelo Simplex para obter a solução)
Pesquisa Operacional - Prof Paulo Arce 12
Programação Linear – Solução Pelo Método Gráfico
Comentários Adicionais
• Restrições Ativas e Inativas
• Ativa: é uma barreira à melhoria
da solução ótima. Não há folga
nem excesso na restrição. Passa
pela solução ótima.
• Inativa: não influencia o valor da
F.O. diretamente. Não passa pela
solução ótima.
carpintaria
pintura
max dem soldados
Pesquisa Operacional - Prof Paulo Arce 13
Programação Linear – Solução Pelo Método Gráfico
Comentários Adicionais
• Restrições Ativas e Inativas
m
a
x
d
em
so
ld
a
d
o
s
• Quando alteramos uma restrição inativa, o ótimo não muda
• Quando alteramos uma restrição ativa, o ótimo muda
Pesquisa Operacional - Prof Paulo Arce
14
Aqui, diminuímos a 
demanda por soldados 
de 40 para 30 e não 
houve alteração da 
resposta ótima
Aqui, diminuímos a 
carpintaria de 80 horas 
para 70 horas e houve 
alteração da resposta 
ótima
Exemplo 2 – Empresa de Consultoria
Uma empresa presta consultoria para pessoas físicas e pessoas jurídicas (organizações). Os serviços prestados
são de alta qualidade e há uma grande procura pelos seus serviços. A empresa pode escolher quantos clientes
de cada tipo irá atender. Porém, existe uma demanda máxima para cada tipo de cliente. Suponha que o valor
cobrado por uma consultoria seja de um salário mínimo para uma pessoa física e de três salários mínimos para
uma pessoa jurídica. Suponha que essa empresa queira maximizar a receita.
Suponha também que a procura de clientes do tipo pessoa física seja de no máximo 15 clientes por mês. Já a
procura de clientes do tipo pessoa jurídica seria de no máximo 10 clientes por mês.
A consultoria para um cliente pessoa física utiliza 8 horas de trabalho e a consultoria para um cliente pessoa
jurídica utiliza 20 horas de trabalho. Além disso, a quantidade total de horas disponíveis é de 160 horas.
Formule a situação descrita como um problema de PL e resolva pelo método gráfico
Programação Linear – Solução Pelo Método Gráfico
Pesquisa Operacional - Prof Paulo Arce 15
Exemplo 2 – Empresa de Consultoria
Programação Linear – Solução Pelo Método Gráfico
Pesquisa Operacional - Prof Paulo Arce 16
Exemplo 2 – Empresa de Consultoria
Programação Linear – Solução Pelo Método Gráfico
(1) – Identificação da Região Viável
Pesquisa Operacional- Prof Paulo Arce 17
Exemplo 2 – Empresa de Consultoria
Programação Linear – Solução Pelo Método Gráfico
(1) – Identificação da Região Viável
Pesquisa Operacional - Prof Paulo Arce 18
Exemplo 2 – Empresa de Consultoria
Programação Linear – Solução Pelo Método Gráfico
(2) – Determinação das Curvas de Nível
Pesquisa Operacional - Prof Paulo Arce 19
Exemplo 2 – Empresa de Consultoria
Programação Linear – Solução Pelo Método Gráfico
(3) – Identificação do Ponto Ótimo
Pesquisa Operacional - Prof Paulo Arce 20
Exemplo 3
Programação Linear – Solução Pelo Método Gráfico
Um fazendeiro deseja saber as áreas de arroz e milho que devem ser plantadas para que seu lucro seja máximo. O seu
lucro por unidade de área plantada de arroz é de R$ 5,00, e de R$ 2,00 por unidade de área plantada de milho. As áreas
plantadas de arroz e de milho não devem ser maiores que 3 e 4 respectivamente. O consumo total de homens-hora nas
duas plantações não deve ser maior que 9. Cada unidade de área plantada de arroz consome 1 homem-hora e de milho
consome 2 homens-hora.
Modele a situação apresentada como um problema de PL e resolva pelo método gráfico.
Pesquisa Operacional - Prof Paulo Arce 21
Exemplo 4
Programação Linear – Solução Pelo Método Gráfico
Resolva graficamente o seguinte problema:
min 𝑧 = 2𝑥1 + 3𝑥2
𝑠. 𝑎.
5𝑥1 + 4𝑥2 ≤ 2000
𝑥1 ≥ 80
𝑥1 + 𝑥2 ≥ 300
𝑥2 ≥ 60
𝑥1, 𝑥2 ≥ 0
Pesquisa Operacional - Prof Paulo Arce 22
Referências
Programação Linear – Solução Pelo Método Gráfico
• Pesquisa Operacional – Emerson Colin – LTC
• Schaum´s Operations Research – Bronson and Naadimuthu – McGrawHill
• Pesquisa Operacional – Cesar Duarte Souto-Maior - UFSC
Pesquisa Operacional - Prof Paulo Arce 23