Slides de Aula Unidade III

Prévia do material em texto

Unidade III
PESQUISA OPERACIONAL
Prof. Mauricio Fanno
Problemas de minimização
 Nas unidades I e II vimos problemas de maximização.
 Veremos, nesta unidade, um problema de minimização.
Para tanto, usaremos, como sempre, um exemplo:
 Um fornecedor deve preparar, no mínimo, cinco tipos de 
bebidas a base de frutas disponíveis em seu estoque, 500 litros 
de isotônico contendo pelo menos 20% de suco de laranja, 
10% de suco de uva e 5% de suco de tangerina. A partir dos 
dados da tabela seguinte, determinar a quantidade de cada 
uma das bebidas básicas que o fornecedor deve utilizar, de 
forma a obter a composição requerida a um custo mínimo.
Problemas de minimização: enunciado
Problemas de minimização: modelagem
 Variáveis de decisão:
 𝒙𝟏= quantidade de bebida A a ser utilizada.
 𝒙𝟐= quantidade de bebida B a ser utilizada.
 𝒙𝟑= quantidade de bebida C a ser utilizada.
 𝒙𝟒= quantidade de bebida D a ser utilizada.
 𝒙𝟓= quantidade de bebida E a ser utilizada.
Função Objetivo (custo mínimo):
𝑴𝒊𝒏𝑪 = 𝟏, 𝟓𝟎𝒙𝟏 + 𝟎, 𝟕𝟓𝒙𝟐 + 𝟐, 𝟎𝟎𝒙𝟑 + 𝟏, 𝟕𝟓𝒙𝟒 + 𝟎, 𝟐𝟓𝒙𝟓
Problemas de minimização: modelagem
 Restrições:
𝑸𝒖𝒂𝒏𝒕𝒊𝒅𝒂𝒅𝒆 𝒕𝒐𝒕𝒂𝒍 𝒅𝒆 𝒑𝒓𝒐𝒅𝒖𝒕𝒐 → 𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 + 𝒙𝟒 + 𝒙𝟓 = 𝟓𝟎𝟎
𝑺𝒖𝒄𝒐 𝒅𝒆 𝒍𝒂𝒓𝒂𝒏𝒋𝒂 →
𝟎, 𝟒𝒙𝟏 + 𝟎, 𝟎𝟓𝒙𝟐 + 𝒙𝟑
𝟓𝟎𝟎
≥ 𝟎, 𝟐
𝑺𝒖𝒄𝒐 𝒅𝒆 𝒖𝒗𝒂 →
𝟎, 𝟒𝒙𝟏 + 𝟎, 𝟏𝟎𝒙𝟐 + 𝒙𝟒
𝟓𝟎𝟎
≥ 𝟎, 𝟏
𝑺𝒖𝒄𝒐 𝒅𝒆 𝒕𝒂𝒏𝒈𝒆𝒓𝒊𝒏𝒂 →
𝟎, 𝟐𝟎𝒙𝟐 + 𝒙𝟒
𝟓𝟎𝟎
≥ 𝟎, 𝟎𝟓
𝑬𝒔𝒕𝒐𝒒𝒖𝒆𝒎á𝒙𝒊𝒎𝒐 𝒅𝒆 𝒃𝒆𝒃𝒊𝒅𝒂 𝑨 → 𝒙𝟏 ≤ 𝟐𝟎𝟎
𝑬𝒔𝒕𝒐𝒒𝒖𝒆 𝒎á𝒙𝒊𝒎𝒐 𝒅𝒆 𝒃𝒆𝒃𝒊𝒅𝒂 𝑩 → 𝒙𝟐 ≤ 𝟒𝟎𝟎
𝑬𝒔𝒕𝒐𝒒𝒖𝒆𝒎á𝒙𝒊𝒎𝒐 𝒅𝒆 𝒃𝒆𝒃𝒊𝒅𝒂 𝑪 → 𝒙𝟑 ≤ 𝟏𝟎𝟎
𝑬𝒔𝒕𝒐𝒒𝒖𝒆 𝒎á𝒙𝒊𝒎𝒐 𝒅𝒆 𝒃𝒆𝒃𝒊𝒅𝒂 𝑫 → 𝒙𝟒 ≤ 𝟓𝟎
𝑬𝒔𝒕𝒐𝒒𝒖𝒆𝒎á𝒙𝒊𝒎𝒐 𝒅𝒆 𝒃𝒆𝒃𝒊𝒅𝒂 𝑬 → 𝒙𝟓 ≤ 𝟖𝟎𝟎
Problemas de minimização: planilha base 
Dados de entrada
 Células B3 a F3 – custos das bebidas por litro. 
 Células B4 a F4 – variáveis de decisão – Qtd. de cada bebida.
 Células B5 a F5 – custo total por bebida = Linha 3 x Linha 4.
 Célula G4 – soma A4 a F4. 
 Célula G5 – soma A5 a F5.
 Célula H4 – quantidade de litros a ser produzida.
Problemas de minimização: planilha base 
Restrições
 Células B8 a F8 – qtd. % de suco de laranja por bebida. 
 Células B9 a F9 – qtd. % de suco de uva por bebida. 
 Células B10 a F10 – qtd. % de suco de tangerina por bebida. 
 Células B12 a F12 – estoque em litros de cada bebida.
Problemas de minimização: planilha base 
Restrições
 Células G8; G9 e G10 – quantidade ponderada de cada um dos 
sucos. Soma da porcentagem de cada bebida pela quantidade 
de cada bebida a ser usada (incógnitas). 
 Células H8 a H10 – % de cada tipo de suco obrigatório 
no produto final.
Problemas de minimização: parâmetros do Solver 
Variáveis
Observe que optamos pela minimização clicando em:
Problemas de minimização: parâmetros do Solver 
Restrições
Não esquecer de selecionar variáveis não nulas e LG Simplex.
Problemas de minimização: parâmetros do Solver
Problemas de minimização: Solver executado
Problemas de minimização: Solução final
Interatividade
Entende-se por problemas de minimização:
a) Problema em que as restrições são do tipo menor ou igual.
b) Problema em que as restrições têm importância mínima.
c) Problema em que a função objetivo deve assumir valor 
mínimo.
d) Problema em que as variáveis de decisão devem assumir 
valor mínimo. 
e) Problema em que os recursos são mínimos.
Resposta
Entende-se por problemas de minimização:
a) Problema em que as restrições são do tipo menor ou igual.
b) Problema em que as restrições têm importância mínima.
c) Problema em que a função objetivo deve assumir valor 
mínimo.
d) Problema em que as variáveis de decisão devem assumir 
valor mínimo. 
e) Problema em que os recursos são mínimos.
Resposta correta: C.
Minimizar é atingir o objetivo de mínimo valor.
Problema de transporte
 Aparece quando há a necessidade de distribuição
de bens e serviços. 
 de várias fontes de suprimento (como fábricas, 
por exemplo). 
 para várias localizações de demanda (como armazéns 
ou centros distribuidores).
 Em geral, a quantidade disponível de bens em cada fonte 
de suprimento é fixa ou limitada. 
 Cada destino, por sua vez, tem também uma demanda 
especificada.
Problema de transporte
 Existem rotas e custos de transporte diferentes entre cada 
fonte e cada destino. 
 É preciso determinar quanto deve ser enviado de cada fonte 
para cada destino, de maneira a satisfazer as demandas e 
minimizar o custo total de transporte.
Exemplo de aplicação
Existem três fontes de suprimento de um dado produto, as 
quais serão indicadas por F1; F2 e F3, com as seguintes 
capacidades mensais de produção:
 F1: 10.000 unidades; 
 F2: 15.000 unidades;
 F3: 5.000 unidades.
Exemplo de aplicação
Essas três fontes devem suprir as necessidades de quatro 
armazéns (destinos) indicados por D1, D2, D3 e D4, com as 
seguintes demandas do produto por mês:
 D1: 8.000 unidades; 
 D2: 4.000 unidades; 
 D3: 7.000 unidades; 
 D4: 11.000 unidades.
Exemplo de aplicação
Exemplo de aplicação
Admitamos que os custos de transporte nas várias 
rotas variem segundo a matriz:
Exemplo de aplicação: matriz de transporte
Com as informações sobre demanda dos destinos e capacidade 
de suprimento das fontes, construímos a chamada 
matriz de transporte:
Exemplo de aplicação: função objetivo
Função objetivo:
Minimizar custo: 13x11 + 8x12 + 9x13 + 12x14 + 12x21 + 9x22 + 
10x23 + 14x24 + 8x31 + 8x32 + 9x33 + 6x34
Exemplo de aplicação: restrições
Restrições relativas à produção das fontes:
Fonte F1
x11 + x12 + x13 + x14 = 10.000
Fonte F2
x21 + x22 + x23 + x24 = 15.000
Fonte F3
x31 + x32 + x33 + x34 = 5.000
Exemplo de aplicação: restrições
Restrições relativas às demandas dos destinos:
Destino D1:
x11 + x21 + x31 = 8.000
Destino D2:
x12 + x22 + x32 = 4.000
Destino D3:
x13 + x23 + x33 = 7.000
Destino D4:
x14 + x24 + x34 = 11.000
Exemplo de aplicação: modelagem matemática
Minimizar custo: 
13x11 + 8x12 + 9x13 + 12x14 + 12x21 + 9x22 + 10x23
+ 14x24 + 8x31 + 8x32 + 9x33 + 6x34
Sujeito a:
x11 + x12 + x13 + x14 = 10.000
x21 + x22 + x23 + x24 = 15.000
x31 + x32 + x33 + x34 = 5.000
x11 + x21 + x31 = 8.000
x12 + x22 + x32 = 4.000
x13 + x23 + x33 = 7.000
x14 + x24 + x34 = 11.000
Interatividade
No problema de transporte, podemos dizer que a restrição para 
custo mínimo é:
a) Maior ou igual à demanda e ao suprimento, porque devemos 
estar preparados para transportar um volume superior ao 
estabelecido.
b) Menor ou igual à demanda e ao suprimento, porque iremos 
transportar um volume inferior ao estabelecido.
c) Igual à demanda ou suprimento, porque, se trabalharmos com 
menor ou igual, a solução óbvia será transporte igual a zero.
d) Sempre que for minimização, será menor ou igual.
e) Sempre que for minimização, será maior ou igual.
Resposta
No problema de transporte, podemos dizer que a restrição para custo 
mínimo é:
a) Maior ou igual à demanda e ao suprimento, porque devemos 
estar preparados para transportar um volume superior ao 
estabelecido.
b) Menor ou igual à demanda e ao suprimento, porque iremos 
transportar um volume inferior ao estabelecido.
c) Igual à demanda ou suprimento, porque, se trabalharmos com 
menor ou igual, a solução óbvia será transporte igual a zero.
d) Sempre que for minimização, será menor ou igual.
e) Sempre que for minimização, será maior ou igual.
Resposta: C. A demanda eo fornecimento são dados constantes 
do problema.
Problema de transporte: resolução pelo método 
computacional
Minimizar custo: 
13x11 + 8x12 + 9x13 + 12x14 + 12x21 + 9x22
+ 10x23 + 14x24 + 8x31 + 8x32 + 9x33 + 6x34
Sujeito a:
 x11 + x12 + x13 + x14 = 10.000
 x21 + x22 + x23 + x24 = 15.000
 x31 + x32 + x33 + x34 = 5.000
 x11 + x21 + x31 = 8.000
 x12 + x22 + x32 = 4.000
 x13 + x23 + x33 = 7.000
 x14 + x24 + x34 = 11.000
Montagem da planilha do Solver
 Função objetivo:
Montagem da planilha do Solver
Restrições:
Montagem da planilha do Solver
Montagem da planilha do Solver
Montagem da planilha do Solver
Montagem da planilha do Solver
Interatividade
Uma das seguintes afirmativas é falsa. Qual?
a) O primeiro passo para a utilização do Solver é montar uma 
planilha com todas as informações do modelo matemático.
b) A função objetivo e as restrições devem ser colocadas no Excel 
como fórmulas matemáticas, usando as diversas células.
c) Na tela de parâmetros do Solver, deve ser colocada a função 
objetivo no campo Alterando Células Variáveis.
d) As restrições devem ser colocadas uma a uma na caixa 
Adicionar Restrição.
e) As restrições lógicas são atendidas por meio da seleção do 
campo Tornar Variáveis Irrestritas Não Negativas.
Resposta
Uma das seguintes afirmativas é falsa. Qual?
a) O primeiro passo para a utilização do Solver é montar uma 
planilha com todas as informações do modelo matemático.
b) A função objetivo e as restrições devem ser colocadas no Excel 
como fórmulas matemáticas, usando as diversas células.
c) Na tela de parâmetros do Solver, deve ser colocada a função 
objetivo no campo Alterando Células Variáveis.
d) As restrições devem ser colocadas uma a uma na caixa 
Adicionar Restrição.
e) As restrições lógicas são atendidas por meio da seleção do 
campo Tornar Variáveis Irrestritas Não Negativas.
Resposta correta: C. O campo correto é Definir Objetivo
Relatórios do Solver
Ferramenta Solver do Excel®: relatório de respostas
Ferramenta Solver do Excel®: relatório de 
sensibilidade
Ferramenta Solver do Excel®: relatório de limites
Problemas de minimização: Solver executado
Ferramenta Solver do Excel®: relatório de respostas
Ferramenta Solver do Excel®: relatório de 
sensibilidade
Ferramenta Solver do Excel®: relatório de limites
Interatividade
Vamos considerar que, no exemplo que utilizamos, 
desejássemos alterar valores das variáveis e restrições. Qual o 
relatório que nos mostraria os reflexos dessas alterações na 
solução ótima?
a) Relatório de respostas.
b) Relatório de limites.
c) Relatório de sensibilidade.
d) Relatório de limites junto com o de respostas.
e) Relatório de impactos.
Resposta
Vamos considerar que, no exemplo que utilizamos, 
desejássemos alterar valores das variáveis e restrições. Qual o 
relatório que nos mostraria os reflexos dessas alterações na 
solução ótima?
a) Relatório de respostas.
b) Relatório de limites.
c) Relatório de sensibilidade.
d) Relatório de limites junto com o de respostas.
e) Relatório de impactos.
É o relatório de sensibilidade que amplia a solução estática da 
programação linear, permitindo incorporar considerações sobre 
eventuais alterações.
ATÉ A PRÓXIMA!