PUC-Rio Pesquisa Operacional - PO A Cont Mod 2013.2

Prévia do material em texto

Pesquisa Operacional. 
 Construção de Modelos. 
 Programação Linear. 
PO - PESQUISA OPERACIONAL 
 Profa.: Léa Mara 
PROCESSO DE TOMADA DE DECISÃO 
1 - CONSTRUÇÃO DE MODELOS 
1.1 - Problemas de Decisão 
 
� Problemas mal estruturados: poucas informações; muitas dúvidas sem 
uma resposta precisa (solução depende da experiência do analista). 
 
� Problemas bem estruturados: dados bem definidos (geralmente 
numéricos); inexistência de indagações sem respostas. 
São aplicados modelos formais de análise (modelos matemáticos). 
 
Na prática tem-se um ponto intermediário entre estes dois tipos de problemas. 
 
Modelagem: Processo de transformar dados em um problema e organizá-los 
segundo as necessidades formais de um modelo matemático. 
 
Para resolução de um Problema: 
- Análise Quantitativa (modelo matemático). 
- Análise Qualitativa. 
 
1.2 – Algumas Técnicas e Modelos Matemáticos Usados: 
 
� Análise Estatística (Probabilidade, Regressão e Técnicas Estatísticas); 
 
� Programação Linear: 
 
Programação Linear Simples: relações entre as variáveis são lineares. 
 
Programação Linear Inteira: obrigatoriedade de, pelo menos, uma das 
variáveis assumir valor inteiro. 
 
� Simulação: 
Envolve construção de um modelo. Visa obter soluções ou conhecer 
melhor as condições de operação da realidade. Em casos menos simples, a 
simulação é feita com auxílio de computadores. 
 
� Modelos de Rede: 
Aplicáveis ao estudo de sistemas de transporte. Visa obtenção e 
processamento da informação, planejamento de projeto de pesquisa e 
desenvolvimento. Usados para maximizar fluxo através de redes, para 
encontrar menor caminho entre pontos em uma rede. 
 2
 
� Teoria das Filas (Modelos de Linhas de Espera): 
Usados para melhorar a eficiência de instalações, cujas variáveis de 
incerteza são: 
 - Demanda do consumidor; 
 - Duração do atendimento; 
 - Comportamento do consumidor enquanto espera ser atendido. 
 
� Teoria da Decisão: 
Aplicáveis a problemas de decisão com vários graus de estruturação 
(depende das informações disponíveis). 
 
1.3 - Construções de Modelos (casos gerais) 
 
Problemas Resolvidos: 
 
1) Suponha que você é o gerente do Armazém ABC, que todo mês envia o 
produto X para ser vendido a varejo em três cidades: Pirauba, Guiricema e São 
Geraldo. Assuma que as quantidades enviadas para essas cidades são as 
seguintes: 
 
 Pirauba: X1 unidades; Guiricema: X2 unidades; São Geraldo: X3 unidades. 
 
a) Desenvolva um modelo para determinar o total mensal “T” de unidades 
do produto enviado para o conjunto das três cidades. 
 T = X1 + X2 + X3 
 
b) Suponha que a demanda de Pirauba nunca é superior a 5.000 unidades: 
incorpore esta restrição no modelo. 
X1 ≤ 5.000 (inequação que descreve a restrição) 
 
c) Suponha que a demanda de Guiricema é sempre maior que o dobro da 
demanda de São Geraldo. Incorpore mais esta restrição. 
X2 > 2X3 
Onde: X2: demanda de Guiricema; X3: demanda de São Geraldo. 
 
d) Suponha ainda que o Armazém ABC jamais terá mais que 20.000 
unidades do produto para enviar ao conjunto das três cidades. Logo: 
T ≤ 20.000 ou X1 + X2 + X3 ≤ 20.000 
* Esta restrição diz respeito à quantidade máxima que pode ser enviada. 
 
 
 
 3
2) No problema anterior, suponha que o Armazém ABC, por acordo com 
seus varejistas, tenha sobre si todos os encargos com custos de transporte; o 
Armazém quer enviar quantidades de produto tais que esse custo total de 
transporte seja mínimo, respeitadas as seguintes condições adicionais: 
 
a) Pirauba não pode receber menos que 4.000 unidades do produto. 
b) Guiricema não pode receber menos que 10.000 unidades do produto. 
c) Os custos de transporte por unidade do produto são os seguintes: 
 
Pirauba: R$ 100,00; Guiricema: R$ 120,00; São Geraldo: R$ 80,00. 
 
Montar as restrições adicionais e a expressão do custo total que se quer 
minimizar. 
 Novas restrições: X1 ≥ 4.000; X2 ≥ 10.000 
 
 Custo total: C = 100X1 + 120X2 + 80X3 
 
Solução do modelo é obter os valores de X1, X2 e X3, para o caso de custo 
total mínimo e restrições obedecidas. 
 
2 – PROGRAMAÇÃO LINEAR 
 
2.1 – Definição 
 
Programação Linear: 
 
• Modelo Matemático; 
• Relações entre variáveis são expressas por equações e 
inequações lineares; 
• Problemas envolvendo: 
- Lucros e Receitas (modelos de maximização). 
- Custos (modelo de minimização). 
 
Problemas de Programação Linear contém: 
- Uma expressão matemática que se deseja maximizar ou minimizar: 
FUNÇÃO OBJETIVO. 
 
- Um conjunto de restrições (equações e inequações matemáticas) que devem 
ser obedecidas obrigatoriamente: RESTRIÇÕES DO MODELO. 
 
Obs.: Deseja-se determinar a distribuição que satisfaça as restrições do 
problema, e que alcance o objetivo desejado (ex.: maximização de lucros ou 
minimização de custos) Solução obtida: SOLUÇÃO ÓTIMA. 
 4
 
obs.: Modelo de Programação Linear é constituído de: 
 
 Função Objetivo Linear 
 Restrições Lineares 
 
 
2.2 - Formulação de Modelos de Programação Linear 
 
Envolve: 
Parâmetros: valores conhecidas; 
Variáveis de decisão: valores a serem determinados (incógnitas); 
 Função objetivo e restrições: são compostas por variáveis de decisão. 
 
• Programação Linear Inteira: pelo menos uma das variáveis de decisão 
assume valor inteiro. 
 
• Programação Linear Simples: variáveis assumem valores reais (também 
chamada de Programação Linear). 
 
Como obter a Solução Ótima: 
a) Graficamente: quando o modelo apresenta duas incógnitas: gráfico 2D. 
 
b) Uso de técnicas especiais: quando o modelo apresenta mais que duas 
incógnitas (maioria dos casos reais). 
 
EXEMPLO 1: 
 
Problema da Análise das Atividades: 
Determinar X1, X2, ... , Xn (variáveis de decisão – incógnitas do modelo) que 
maximize a função objetivo Z, sendo: 
 
 Z = C1X1 + C2X2 + ... + CnXn, 
 
onde X1, X2, ... , Xn devem satisfazer o seguinte sistema de inequações 
lineares (restrições): 
 
 a11X1 + a12X2 + ... + a1nXn ≤ b1 
 a21X1 + a22X2 + ... + a2nXn ≤ b2 
 ... 
 am1X1 + am2X2 + ... + amnXn ≤ bm 
 
Restrições de não-negatividade (presente em todo problema de Prog. Linear): 
 X1 ≥ 0 ; X2 ≥ 0 ; ... Xn ≥ 0 
Solução 
Ótima 
 5
∑
=
=
n
i
iiXCZ
1
j
n
1i
ij bXia ≤∑
=
Forma compacta: 
 
Maximizar , sujeito às restrições 
 
 (i = 1, 2, ..., n) e Xi ≥ 0 (j = 1, 2, ..., m) 
O modelo acima pode ser associado a uma empresa que tem m recursos 
disponíveis para a realização de n atividades (neste caso, representam a 
fabricação de produtos). 
 
Tem-se que, p/ i = 1, 2, ... , n e j = 1, 2, ... , m: 
bj: quantidade de recurso j disponível p/ as n atividades (bj ≥ 0). 
 
Xi: nível de produção da atividade i (incógnitas do problema). 
 
Ci: lucro unitário do produto i. 
 
aij: quantidade do recurso j consumida na produção de uma unidade do 
produto i. 
 
Verifica-se então que: 
 
• A função objetivo a ser maximizada representa o lucro total da empresa 
nessas n atividades. 
 
• As m restrições informam que o total gasto do recurso j nas n atividades 
tem de ser menor ou no máximo igual à quantidade bj disponíveis daquele 
recurso. 
 
As restrições Xi ≥ 0 (i = 1, 2, ..., n) eliminaram a possibilidade de níveis 
negativos para as diversas atividades. 
 
Construção do Modelo Matemático - Roteiro: 
 
1 – Quais as variáveis de decisão? 
� Programação de produção: Variáveis de decisão são as quantidades a 
produzir no período. 
 
� Programaçãode investimento: variáveis de decisão representam as 
decisões de investimento (quanto investir em cada oportunidade de 
investimento, e em que período). 
 
Variáveis de decisão do problema: implícita na questão proposta, isto é, na 
pergunta do problema. 
 
 6
2 – Qual o objetivo? 
Identificar o objetivo da tomada de decisão. Aparece geralmente na forma de 
maximização de lucros ou receitas, minimização de custos ou perdas. 
 
Função objetivo: expressão que calcula o valor do objetivo. 
 
3 – Quais as restrições? 
Cada restrição imposta na descrição do sistema deve ser expressa como uma 
relação linear (igualdade ou desigualdade), montadas com as variáveis de 
decisão. 
 
EXEMPLO 2: 
 
 Certa empresa fabrica dois produtos P1 e P2. O lucro unitário do produto 
P1 é de 1000 unidades monetárias e o lucro unitário de P2 é de 1800 unidades 
monetárias. A empresa precisa de 20 horas 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 é de 1200 horas. A demanda esperada para cada produto é 
de 40 unidades anuais para P1 e 30 unidades anuais para P2. Qual o plano de 
produção para que a empresa maximize seu lucro nesses itens? Construa o 
modelo de programação linear para esse caso. 
 
Solução: 
Variáveis de decisão: X1: quantidade anual a produzir de P1. 
 X2: quantidade anual a produzir de P2. 
 
“Plano de Produção”: quais as quantidades anuais devem ser produzidas de P1 
e P2. 
 
Função objetivo: Maximizar o lucro total L = 1000 X1 + 1800 X2 
 
Lucro devido a P1: 1000 . X1 (lucro por unidade de P1 x quantidade produzida 
de P1). 
 
Lucro devido a P2: 1800 . X2 (lucro por unidade de P2 x quantidade produzida 
de P2). 
 
Restrições: 
a) Disponibilidade de horas para a produção: 1200 hs: 
20 X1 + 30 X2 ≤ 1200 
b) Disponibilidade de mercado para os produtos (demanda): X1 ≤ 40 
X2 ≤ 30 
 
 7
Resumo do modelo: 
 Maximizar L = 1000 X1 + 1800 X2 
 Sujeito a: 20 X1 + 30 X2 ≤ 1200 
 X1 ≤ 40; X2 ≤ 30 
 Restrição não-negatividade: X1 ≥ 0 e X2 ≥ 0 
 
EXEMPLO 3: 
 
Para uma boa alimentação, o corpo necessita de vitaminas e proteínas. 
A necessidade mínima de vitaminas é de 32 unidades por dia e a de proteínas 
de 36 unidades por dia. Uma pessoa tem disponível carne e ovos para se 
alimentar. Cada unidade de carne contém 4 unidades de vitaminas e 6 
unidades de proteínas. Cada unidade de ovo contém 8 unidades de vitaminas e 
6 unidades de proteínas. 
 Qual a quantidade diária de carne e ovo que deve ser consumida para 
suprir as necessidades de vitaminas e proteínas com o menor custo possível? 
Cada unidade de carne custa 3 unidades monetárias e cada unidade de ovo 
custa 2,5 unidades monetárias. 
 
Solução: 
Variáveis de decisão: X1: quantidade de carne a consumir no dia; 
 X2: quantidade de ovo a consumir no dia. 
 
Decidir quais as quantidades de carnes e ovos a pessoa deve consumir no dia. 
Função objetivo: Minimizar o custo C = 3 X1 + 2,5 X2 
 
Custo devido à carne: 3 . X1 (custo/unid. x quantidade a consumir de carne). 
Custo devido aos ovos: 2,5 .X2 (custo/unid. x quantidade a consumir de ovos). 
Restrições: 
a) Necessidade mínima de vitaminas: 32 unidades. 
 4 X1 + 8 X2 ≥ 32 
 
 
 
 
 
b) Necessidade mínima de proteínas: 36 unidades. 
 6 X1 + 6 X2 ≥ 36 
 
 
 
vitamina de 
ovos. 
vitamina de 
carne. 
proteína de 
ovos. 
proteína de 
carne. 
 8
 
Resumo: 
 Min. C = 3 X1 + 2,5 X2 
 
 Sujeito a: 4 X1 + 8 X2 ≥ 32 
 6 X1 + 6 X2 ≥ 36 
 Restrições não-negativas: X1, X2 ≥ 0 
 
OBS.: CONSTRUÇÃO DE MODELOS: 
Discriminar as variáveis do problema: X1, ..., Xn; 
Definir a função objetivo; 
Definir as restrições do problema; 
Marcar restrições de não-negatividade. 
 
Para determinar as incógnitas do problema: Método Gráfico; 
 Método Simplex.