Aula 1 Definição e Modelagem colocar no RG PO

Prévia do material em texto

Prof. MSc. Marcos dos Santos
O PROCESSO DE DEFINIÇÃO e
MODELAGEM DE UM PROBLEMA
OBJETIVOS
- Compreender como se dá a estruturação de um
problema; e
- Realizar a modelagem de problemas básicos.
Prof. MSc. Marcos dos Santos
ESTRATÉGIAS PARA A ESTRUTURAÇÃO DE UM PROBLEMA
Prof. MSc. Marcos dos Santos
Uma causa é todo e qualquer fato que origina um problema. Um problema deve,
necessariamente, ter pelo menos uma causa. Usualmente, problemas Complexos são
oriundos de várias causas, que ocorrem em cadeia ou simultaneamente. Na maioria dos
casos, a determinação das causas de um problema demanda análise ampla e minuciosa
de todo o contexto e das variáveis da situação.
Já um efeito evidencia e externaliza a ocorrência de um problema, tomando esse
problema perceptível. Todo problema tem pelo menos um efeito, o qual é sempre
originado por uma ou mais causas.
A grande dificuldade na modelagem dos problemas reside
na abstração do cenário, justamente a etapa que não exige
conhecimentos matemáticos ou estatísticos, nem sequer o
uso de uma lógica formalizada, ao contrário do que imaginam
muitos iniciantes em pesquisa operacional.
O processo de abstração de cenário pode ser resumido na
capacidade do praticante da pesquisa operacional de mapear
determinada situação, estabelecer as relações existentes
nela, bem como identificar todos os participantes e suas
interações com o problema.
ESTRATÉGIAS PARA A ESTRUTURAÇÃO DE UM PROBLEMA
Prof. MSc. Marcos dos Santos
MODELAGENS BÁSICAS
Prof. MSc. Marcos dos Santos
MODELAGENS BÁSICAS
MODELAGENS BÁSICAS
MODELAGENS BÁSICAS
(para entregar)
1939 – Kantorovich (formulou rigorosamente um problema de
Programação Linear no trabalho Métodos Matemáticos de
Organização e Planejamento da Produção, mas não apresentou um
algoritmo de resolução)
O grande salto da Programação Linear é dado
através das aplicações em problemas de transportes na
década de 40 (em particular, pelas Forças Armadas durante
a Segunda Guerra Mundial).
Prof. MSc. Marcos dos Santos
1947 – Dantzig (trabalhou no Pentágono como
conselheiro matemático, onde era frequentemente
chamado para resolver problemas de planejamento.
No entanto, contrariamente ao que Dantzig pensou, os
economistas ainda não tinham métodos de resolução de
tais problemas.
Foi então que Dantzig propôs o Método Simplex que
tornou possível a solução de problemas de otimização de
vários tipos.
Prof. MSc. Marcos dos Santos
APLICAÇÕES DA PL
Os domínios de aplicação da Programação Linear são vastíssimos. Por exemplo:
 Gestão de empresas;
 Problemas de transportes;
 Estrutura financeira dos bancos;
 Obtenção de misturas ótimas;
 Planejamento agrícola;
Entre muitos outros.
PROGRAMAÇÃO LINEAR:
Preocupação em encontrar a melhor solução para problemas associados a
modelos lineares.
MODELO DE PROGRAMAÇÃO LINEAR:
Maximização (ou minimização) de uma função objetivo linear com relação
as variáveis de decisão do modelo.
Respeitando-se as limitações (restrições) do problema expressas
por um sistema de equações e/ou inequações lineares associadas com as
variáveis de decisão do modelo.
PROGRAMAÇÃO LINEAR
Prof. MSc. Marcos dos Santos
1. Grande variedade de situações podem ser aproximadas por
modelos lineares.
2. Existência de técnicas (algoritmos) eficientes para a solução de
modelos lineares.
3. Possibilidade de realização de análise de sensibilidade nos dados do
modelo.
4. Elevada capacidade de processamento dos computadores atuais.
RAZÕES PARA O USO DA PL
Prof. MSc. Marcos dos Santos
x1 , x2,...,xn , são as chamadas Variáveis de Decisão.
 As variáveis de decisão são aqueles valores que representam o cerne do problema, e
que podemos escolher (decidir) livremente.
 As variáveis de decisão representam as opções que um administrador têm para
atingir um objetivo.
 Quanto produzir para maximizar o lucro?
 Quanto comprar de uma ação para minimizar o risco da carteira?
VARIÁVEIS DE DECISÃO
• Um problema de programação matemática é linear se a função-objetivo
e cada uma das funções que representam as restrições forem lineares, isto é, na
forma abaixo:
O Modelo de PL
O Modelo Reduzido
ix
pjbxa
as
xcLMax
i
n
i
jiji
n
i
ii
xxx n







 0
,...,1 
.
1
1
,....,, 21
Prof. MSc. Marcos dos Santos
• A presença de qualquer das expressões abaixo tornam o problema não linear. 
Exemplos:
•
•
•
  1 para 1 nx
n
  a basequalquer para log 1xa aa x devalor qualquer para 1
Quebrando a Linearidade
0,
60020180
2042
s.r.
max
21
21
21
21




xx
xx
xx
xx
0,
60020180
2032
s.r.
2min
21
21
21
21




xx
xx
xx
xx
Exemplos de Problemas Lineares
Prof. MSc. Marcos dos Santos
Existem 4 características para um problema na forma padrão:
– A função-objetivo é de Maximizar;
– As restrições têm sinal de menor ou igual;
– As constantes de todas as restrições são não negativas;
– As variáveis podem assumir valores não negativos.
Problema na Forma Padrão
Prof. MSc. Marcos dos Santos
0x,...x,x,x
bxa...xaxa
bxa...xaxa
bxa...xaxa
xc...xcxcZ
n321
mnmn22m11m
2nn2222121
1nn1212111
nn2211





 :a Sujeito
 Maximizar
Não negativos
Problema na Forma Padrão
• Forma Padrão  Forma Não Padrão
0,
60020180
2032
s.r.
2min
21
21
21
21




xx
xx
xx
xx
0,
60020180
2042
s.r.
max
21
21
21
21




xx
xx
xx
xx
0,
60020180
2042
s.r.
max
21
21
21
21




xx
xx
xx
xx
Problema na Forma Padrão
Hipóteses da PL
Prof. MSc. Marcos dos Santos
Hipóteses da PL
• Solução
– No campo de Programação Linear é qualquer especificação de valores para as variáveis de
decisão, não importando se esta especificação se trata de uma escolha desejável ou não.
• Solução Viável
– É uma solução em que todas as restrições são satisfeitas;
• Solução Inviável
– É uma solução em que alguma das restrições ou as condições de
não-negatividade não são atendidas.
Terminologia
0,
800100180
2042
max
21
21
21
21




xx
xx
xx
s.r.
xx
x1 = 3 ; x2 = 2
S = (3, 2)
solução viável: todas as restrições são respeitadas.
x1 = 3 ; x2 = 4
S = (3, 4)
solução inviável: pelo menos uma das restrições é 
violada
Exemplos de Soluções
Prof. MSc. Marcos dos Santos
É especialmente importante verificar como fica o valor da função-objetivo (z) nas 
soluções viáveis que podemos determinar:
0,
800100180
2042
 max
21
21
21
21




xx
xx
xx
s.r.
xxz
)1,1(S 2z )1,2(S 3z )2,3(S 5z
Valor da Função Objetivo (F.O.)
Prof. MSc. Marcos dos Santos
A Solução Ótima é uma solução viável especial. Dentre todas as soluções viáveis,
é aquela que produz o valor da função-objetivo otimizado (valor máximo se a F.O.
for de maximização, e valor mínimo se a F.O. for de minimização).
Num primeiro momento aprenderemos a modelar um PPL. Em seguida
encontraremos a “solução ótima” via solução gráfica ou via método Simplex.
Solução Ótima
Prof. MSc. Marcos dos Santos
PASSOS PARA A MODELAGEM DE UM PPL
Prof. MSc. Marcos dos Santos
MODELAGEM DE UM PPL - EXEMPLO
Fabricação de dois modelos de brinquedos: B1 e B2. 
• Lucros unitários/dúzia: R$8,00 para B1 e R$5,00 para B2
• Recursos disponíveis:
1000 kg de plástico especial.
40 horas para produção semanal.• Requisitos do Departamento de Marketing:
Produção total não pode exceder 700 dúzias;
A quantidade de dúzias de B1 não pode exceder em 350 a quantidade de 
dúzias de B2.
• Dados técnicos:
B1 requer 2 kg de plástico e 3 minutos por dúzia.
B2 requer 1 kg de plástico e 4 minutos por dúzia.
A Gerência está procurando um 
programa de produção que aumente o 
lucro da Companhia. 
MODELAGEM DE UM PPL - EXEMPLO
Variáveis de decisão:
X1: produção semanal de B1 (em dúzias).
X2: produção semanal de B2 (em dúzias).
Função Objetivo: Maximizar o Lucro semanal
MODELAGEM DE UM PPL - EXEMPLO
F.O.: Max 8X1 + 5X2 (Lucro semanal)
sujeito a:
2X1 + 1X2 ≤ 1000 (Plástico - Kg)
3X1 + 4X2 ≤ 2400 (Tempo de produção - minutos)
X1 + X2 ≤ 700 (Produção total)
X1 - X2 ≤ 350 (mix)
Xj  0, j = 1,2 (Não negatividade)
MODELAGEM DE UM PPL - EXEMPLO
LISTA DE EXERCÍCIOS
(SOMENTE A MODELAGEM)
Prof. MSc. Marcos dos Santos
Prof. MSc. Marcos dos Santos
1) Um modelo não pode ser melhor do que as informações contidas nele. Para
ilustrar esse princípio, é preciso citar uma máxima utilizada por programadores de
computadores: “Lixo que entra é igual a lixo que sai" (GIGO - abreviatura em
inglês para Garbage In, Garbage Out). Se as informações contidas no modelo
forem incertas e imprecisas, não há como esperar resultados exatos e fidedignos.
2) Modelos não podem substituir decisores. Um modelo, por mais elaborado que
seja, representa tão somente o equacionamento lógico de uma situação
problemática. Ele nunca sobreporá a capacidade humana de percepção e análise
das coisas e fatos. Devemos, portanto, manter os modelos na condição de boas
ferramentas que proporcionam auxílio na tomada de decisão. Não se esqueça de
que, no final das contas, quem vai decidir é uma pessoa ou um grupo de pessoas.
ALGUMAS CONSIDERAÇÕES IMPORTANTES
Prof. M.Sc. Marcos Santos
Email: marcosdossantos_doutorado_uff@yahoo.com.br
DÚVIDAS
View publication statsView publication stats