Pesquisa Operacional I

Prévia do material em texto

Pesquisa Operacional I
(CEP/CT025) – Aula 01
UNIVERSIDADE FEDERAL DO PIAUÍ
CAMPUS MINISTRO PETRÔNIO PORTELLA – CT
CURSO DE ENGENHARIA DE PRODUÇÃO
PROF. ÁLVARO LÉDO FERREIRA
CONTATO: a lvaro.ferre i ra@ufpi .edu.br 
Objetivos da disciplina
• Apresentar os conceitos básicos de o0mização;
• Capacitar o aluno para a iden0ficação, modelagem e o0mização de 
problemas reais da Engenharia de Produção.
Descrição da disciplina
• Ementa:
1. Introdução à Pesquisa Operacional e ao processo de modelagem;
2. Programação linear;
3. Método de resolução gráfica;
4. O algoritmo Simplex;
5. Dualidade;
Descrição da disciplina
• Ementa:
6. Análise de sensibilidade;
7. Problemas de transporte e designação;
8. Otimização em redes;
9. Programação inteira.
1. Introdução à Pesquisa Operacional e ao 
processo de modelagem
1.1. Histórico.
2. Programação linear
2.1. Problemas de programação linear;
2.2. Modelagem matemá0ca.
3. Método de resolução gráfica
3.1. Construção de gráficos;
3.2. Restrições.
4. O algoritmo Simplex
4.1. Condições de não negatividade;
4.2. Forma Padrão;
4.3. Forma canônica de um sistema;
4.4. Variáveis de folga e excesso;
4.5. Equivalência entre Maximização e Minimização;
4.6. Geração de solução inicial viável;
4.7. Teoremas fundamentais do Método Simplex;
4.8. Funcionamento do Método Simplex.
5. Dualidade
5.1. O par primal-dual;
5.2. Interpretação econômica do problema dual;
5.3. Soluções duais – teoremas.
6. Análise de sensibilidade
6.1. Análise de sensibilidade ou Análise pós-ó0ma;
6.2. Mudanças no coeficientes da função obje0vo;
6.3. Mudanças nos termos independentes;
6.4. Acréscimo de uma variável;
6.5. Eliminação de uma variável;
6.6. Acréscimo de uma restrição;
6.7. Eliminação de uma restrição;
6.8. Mudança em coeficientes tecnológicos.
7. Problemas de transportes e designação
7.1. Problemas de transportes;
7.2. Sistemas não-equilibrados;
7.3. Designação.
8. Otimização em Redes
8.1. Definições;
8.2. Problema do caminho mais curto;
8.3. Problema do fluxo máximo;
8.4. Problema de Transbordo;
8.5. Problema do caminho mais longo;
8.6. Problema da árvore geradora mínima.
9. Programação Inteira
9.1. Definições;
9.2. Aplicações;
9.3. Modelagem;
9.4. Modelagem de restrições especiais.
Descrição da disciplina
• Carga horária: 4 créditos (60h);
•Metodologia:
• Aulas exposiMvas;
• Slides;
• Discussão e resolução de exercícios.
Descrição da disciplina
• Avaliações:
• 1ª Avaliação (09/04/24): Prova escrita (6-8 pts) + Listas (2 pts) + 
AMvidades em sala (0-2 pts);
• 2ª Avaliação (16/05/24): Prova escrita (6-8 pts) + Listas (2 pts) + 
AMvidades em sala (0-2 pts);
• 3ª Avaliação (27/06/24): Prova escrita (6-8 pts) + Listas (2 pts) + 
AMvidades em sala (0-2 pts);
• Avaliação Final (04/07/24): Prova escrita (10 pts).
Descrição da disciplina
• Bibliografia:
• HILLIER, F. S.; LIEBERMAN, G. J. Introdução à pesquisa operacional. 9. 
ed. Porto Alegre: AMGH, 2013.;
• LACHTERMACHER, G. Pesquisa Operacional na tomada de decisões. 4ª 
Edição, São Paulo: Pearson Prentice Hall, 2009;
• TAHA, H. A. Operations Research: an introduction. Prentice Hall 
International, 1997.
Descrição da disciplina
DÚVIDAS?
1. Introdução à Pesquisa Operacional e 
ao processo de modelagem
• Aumento da complexidade e especialização das organizações: 
dificuldade de alocação de recursos;
• Surgimento da Pesquisa Operacional;
• Primórdios da 2ª Guerra Mundial: alocação de recursos escassos;
• Objetivo: condução e coordenação das operações em uma 
organização;
• Aplicação em áreas de manufatura, transportes, construção, 
telecomunicações, planejamento financeiro, serviços públicos, etc.;
1. Introdução à Pesquisa Operacional e 
ao processo de modelagem
• Processo de aplicação:
• Observação e formulação do problema;
• Coleta de dados;
• Construção do modelo científico (matemático, computacional,...);
• Hipótese: o modelo é uma representação suficientemente precisa da 
situação analisada e conclusões obtidas no modelo são válidas no 
mundo real;
• Experimentação do modelo para verificar essa e outras hipóteses.
1. Introdução à Pesquisa Operacional e 
ao processo de modelagem
• Tenta, frequentemente, encontrar a melhor solução para o 
problema analisado;
• Técnicas: método simplex, teoria das filas, simulação (Monte Carlo, 
discreta, contínua, baseada em agentes,...), teoria dos jogos, teoria 
da decisão...;
• Ferramentas: Excel Solver, Simuladores (Crystal Ball, Promodel, 
Arena), algoritmos, programação.
2. Programação linear
2.1. Problemas de programação linear;
2.2. Modelagem matemá0ca.
2.1. Problemas de programação linear
•Management Science: decisões gerenciais com bases racionais;
• Consiste de um problema de programação matemática em que as
funções-objetivo e de restrição são lineares;
•Modelo é formado por uma expressão linear (Função Objetivo) e
por um conjunto de expressões lineares envolvendo as variáveis de
decisão (Restrições);
• As restrições lineares podem ser representadas por igualdades (=)
ou desigualdades (≤,≥);
2.1. Problemas de programação linear
• Áreas de aplicação:
• Administração da produção;
• Análise de investimentos;
• Alocação de recursos limitados;
• Planejamento regional;
• Logística;
• Custo de transporte;
• Localização da rede de distribuição.
2.1. Problemas de programação linear
• Terminologia:
• Solução: qualquer especificação de valores, dentro do domínio da
função objetivo 𝑍 para as variáveis de decisão, independentemente de
ser uma escolha desejável ou permissível;
• Solução viável: uma solução em que todas as restrições são satisfeitas;
• Solução ótima: uma solução viável que possui o valor mais favorável da
função-objetivo 𝑍 , i.e., maximiza ou minimiza a função-objetivo,
podendo ou não ser única.
2.1. Problemas de programação linear
• Hipóteses:
• Proporcionalidade: o valor da função-objeMvo é diretamente
proporcional ao valor de cada variável de decisão;
• AdiMvidade: as variáveis de decisão de um modelo são independentes
entre si;
• Divisibilidade: as variáveis de decisão podem assumir valores
fracionários;
• Certeza: todos os parâmetros do modelo são constantes e conhecidos.
2.1. Problemas de programação linear
• Um agricultor deseja cultivar duas variedades de cereais, A e B, em
uma área de um hectare (100 ares). Para o plantio, cada are cultivado
de cereal A precisa de 3 homens-hora de trabalho, e o cultivado de
cereal B precisa de 2 homens-hora, sendo que se dispõe de até 240
homens-hora de trabalho para o cultivo. Além disso, são utilizados dois
inseticidas (um para cada cereal) e cada are necessita de 1 litro. A
disponibilidade de inseticida para o cereal tipo A é de 60 litros e a de
cereal tipo B é de 80 litros. Cada are de cereal tipo A gera um lucro de
600 u.m., e cada are de cereal tipo B gera um lucro de 800 u.m. O
agricultor deseja planejar sua produção de forma a maximizar o lucro.
2.2. Modelagem matemáMca
•Modelo: representação da realidade;
•Modelos matemáticos: abstrações da realidade representadas por
um conjunto de equações e relações;
• Primeira etapa na busca por uma solução de Programação Linear
(PL);
• Devem ser modelados somente os aspectos relevantes;
• Todo problema de Programação Linear pode ser descrito por meio
de uma função objetivo e um conjunto de restrições, todas lineares;
2.2. Modelagem matemática
•Metodologia para modelagem:
i. Dividir o problema em problemas menores (se possível);
ii. Identificar as variáveis e as suas unidades de medida;
iii. Identificar o objetivo e construir a função objetivo;
iv. Identificar os fatores restritivos e construir as restrições a partir deles
e das variáveis;
v. Estabelecer as relações entre as variáveis (também são restrições);
vi. Descartar aspectos que não comprometam a otimalidade da solução
e descartar redundâncias (restrições que não alterem as soluções
viáveis).
2.2. Modelagem matemática
• Na modelagem de problemas de programação linear (assim como
na inteira, mista e não-linear) devem ser estabelecidas:
a) As variáveisdo problema (ou decisórias): aquilo que se pode controlar
e que se deseja saber exatamente quanto vale;
b) A função objeMvo: sempre se deseja maximizar ou minimizar
determinado objeMvo, expresso em função das variáveis do problema;
c) As restrições: também expressas em função das variáveis do
problema, as restrições limitam as combinações das variáveis
determinados limites.
2.2. Modelagem matemáMca
•Modelo genérico:
𝑀𝐴𝑋,𝑀𝐼𝑁 𝑍 = 𝑐!𝑥! + 𝑐"𝑥" +⋯+ 𝑐#𝑥#
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎 𝑠. 𝑎.
𝑎!!𝑥! + 𝑎!"𝑥" +⋯+ 𝑎!#𝑥# =,≤,≥ 𝑏!
𝑎"!𝑥! + 𝑎""𝑥" +⋯+ 𝑎"#𝑥# =,≤,≥ 𝑏"
………………………………………………
𝑎$!𝑥! + 𝑎$"𝑥" +⋯+ 𝑎$#𝑥# =,≤,≥ 𝑏$
𝑥!, 𝑥", … , 𝑥# ≥ 0
2.2. Modelagem matemáMca
•Modelo genérico:
• Em notação matricial:
𝑀𝐴𝑋,𝑀𝐼𝑁 𝑍 = 𝑐𝑥
𝑠. 𝑎.
𝐴𝑥 =,≤,≥ 𝑏
𝑥 ≥ 0
2.2. Modelagem matemática
•Modelo genérico:
• Onde:
• 𝑥!, 𝑥", … , 𝑥# = conjunto de variáveis estruturais do problema;
• 𝑐!, 𝑐", … , 𝑐# = coeficientes da função objetivo;
• 𝑎$% 𝑒 𝑏% = coeficientes das restrições;
• 𝑍 = função objetivo com a meta que se deseja alcançar (máximo ou
mínimo).
2.2. Modelagem matemática
• Cada restrição pode ser uma igualdade = ou uma desigualdade
não-estrita ≥,≤ ;
• Todos os valores dos coeficientes são conhecidos na modelagem;
• Todas as variáveis devem assumir valores reais;
2.2. Modelagem matemáMca
• Para o nosso problema do fazendeiro, temos:
a) As variáveis de decisão (decisórias): quantidade de ares cultivados por
cada cereal ou quantidade produzida de cada tipo de cereal;
2.2. Modelagem matemáMca
• Para o nosso problema do fazendeiro, temos:
a) As variáveis decisórias: quantidade de ares cultivados por cada
cereal, ou quantidade produzida de cada tipo de cereal;
𝑥! = 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑑𝑒 𝑎𝑟𝑒𝑠 𝑐𝑢𝑙𝑡𝑖𝑣𝑎𝑑𝑜𝑠 𝑑𝑜 𝑐𝑒𝑟𝑒𝑎𝑙 𝑡𝑖𝑝𝑜 𝐴
𝑥" = 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑑𝑒 𝑎𝑟𝑒𝑠 𝑐𝑢𝑙𝑡𝑖𝑣𝑎𝑑𝑜𝑠 𝑑𝑜 𝑐𝑒𝑟𝑒𝑎𝑙 𝑡𝑖𝑝𝑜 𝐵
2.2. Modelagem matemática
• Para o nosso problema do fazendeiro, temos:
b) A função objetivo: maximizar o lucro;
max𝑍 = 𝐿𝑢𝑐𝑟𝑜 𝑇𝑜𝑡𝑎𝑙
𝐿𝑢𝑐𝑟𝑜 𝑇𝑜𝑡𝑎𝑙 = 𝑎𝑟𝑒𝑠 𝐴 ×𝑙𝑢𝑐𝑟𝑜 𝑎𝑟𝑒 𝐴
+𝑎𝑟𝑒𝑠 𝐵 ×𝑙𝑢𝑐𝑟𝑜 𝑎𝑟𝑒 𝐵
2.2. Modelagem matemática
• Para o nosso problema do fazendeiro, temos:
b) A função objeMvo: maximizar o lucro;
max𝑍 = 𝐿𝑢𝑐𝑟𝑜 𝑇𝑜𝑡𝑎𝑙
𝐿𝑢𝑐𝑟𝑜 𝑇𝑜𝑡𝑎𝑙 = 600𝑥! + 800𝑥"
2.2. Modelagem matemáMca
• Para o nosso problema do fazendeiro, temos:
c) As restrições:
i. Quantidade total de ares: 1 hectare = 100 ares;
𝑥! + 𝑥" ≤ 100
ii. Total de homens-hora: 240 homens-hora;
3𝑥! + 2𝑥" ≤ 240
2.2. Modelagem matemáMca
• Para o nosso problema do fazendeiro, temos:
c) As restrições:
iii. Quantidade máxima de inseticida A: 60 litros;
𝑥! ≤ 60
iv. Quantidade máxima de inseticida B: 80 litros;
𝑥" ≤ 80
2.2. Modelagem matemática
• Para o nosso problema do fazendeiro, temos:
c) As restrições:
v. Impossibilidade de produção negativa:
𝑥! ≥ 0 𝑒 𝑥" ≥ 0
2.2. Modelagem matemática
• Para o nosso problema do fazendeiro, temos:
𝑚𝑎𝑥 𝑍 = 600𝑥! + 800𝑥"
s.a.
𝑥! + 𝑥" ≤ 100
3𝑥! + 2𝑥" ≤ 240
𝑥! ≤ 60
𝑥" ≤ 80
𝑥! ≥ 0
𝑥" ≥ 0
Exemplo 1 - Problema
• Uma empresa fabril está interessada em maximizar o lucro mensal proveniente
de quatro de seus produtos, designados por I, II, III e IV. Para fabricar esses
quatro produtos, ela utiliza dois tipos de máquinas, M1 e M2, com
disponibilidade mensal de 800 e 200 máquina-hora/mês, respectivamente, e
dois tipos de mão-de-obra, MO1 e MO2, com disponibilidade de 12.000 e
16.000 homem-hora/mês, respectivamente. Sabe-se que para produzir uma
unidade de I são consumidas 5mh de M1, 2mh de M2, 2hh de MO1 e 7hh de
MO2; para o produto II, 4mh de M1, 6mh de M2, 4hh de MO1 e 3hh de MO2;
para o produto III, 8mh de M1 e 2hh de MO1; para o produto IV, 9mh de M1,
8mh de M2, 8hh de MO1 e 7hh de MO2. Sabe-se também que o lucro unitário
de cada produto é de 10, 8, 9 e 7 u.m., respectivamente. O setor de vendas
determinou o potencial de venda dos produtos igual a 70, 60, 40 e 20,
respectivamente. Qual deve ser a produção de modo a maximizar o lucro?
Exemplo 1 – Modelagem MatemáMca
𝑀𝑎𝑥 𝑍 = 10𝑥! + 8𝑥" + 9𝑥& + 7𝑥'
𝑠. 𝑎.
5x! + 4𝑥" + 8𝑥& + 9𝑥' ≤ 800
2x! + 6x" + 8x' ≤ 200
2x! + 4x" + 2𝑥& + 8x' ≤ 12.000
7x! + 3x" + 7x' ≤ 16.000
𝑥! ≤ 70
𝑥" ≤ 60
𝑥& ≤ 40
𝑥' ≤ 20
𝑥% ≥ 0, (𝑗 = 1, 2, 3, 4)
Exemplo 2 - Problema
• Uma pessoa deve fazer uma dieta que forneça diariamente pelo menos 80mg 
de vitamina A, 70mg de vitamina B, 100mg de vitamina C e 60mg de vitamina D. 
A dieta deve incluir leite, arroz, feijão e carne, que possuem as seguintes 
quantidades de vitaminas:
Vitaminas
Alimentos
Leite (copo) Arroz (100g) Feijão (100g) Carne (100g)
A 10 5 9 10
B 8 7 6 6
C 15 3 4 7
D 20 2 3 9
Exemplo 2 - Problema
• Os custos unitários desses alimentos são: 
• Leite: 1 u.m./copo;
• Arroz: 0,8 u.m./100g;
• Feijão: 1,2 u.m./100g;
• Carne: 3,5 u.m./100g.
• Qual deve ser o consumo diário de cada alimento de modo a saasfazer a dieta a 
um custo mínimo?
Exemplo 2 – Modelagem MatemáMca
𝑀𝑖𝑛 𝑍 = 1𝑥! + 0,8𝑥" + 1,2𝑥& + 3,5𝑥'
𝑠. 𝑎.
10x! + 5𝑥" + 9𝑥& + 10𝑥' ≥ 80
8x! + 7x" + 6x& + 6x' ≥ 70
15x! + 3x" + 4𝑥& + 7x' ≥ 100
20x! + 2x" + 3x& + 9x' ≥ 60
𝑥% ≥ 0, (𝑗 = 1, 2, 3, 4)
Pesquisa Operacional I
(CEP/CT025) – Aula 01
UNIVERSIDADE FEDERAL DO PIAUÍ
CAMPUS MINISTRO PETRÔNIO PORTELLA – CT
CURSO DE ENGENHARIA DE PRODUÇÃO
PROF. ÁLVARO LÉDO FERREIRA
CONTATO: a lvaro.ferre i ra@ufpi .edu.br