Pesquisa Operacional
Modelagem Matemática
Pesquisa Operacional
O processo sistemático (científico) de tomada de decisão
pode ser utilizado em qualquer situação, seja ela simples, ou
mais complexa estabelecendo-se um modelo para a
obtenção da solução.
Nesse aspecto podemos considerar os modelos:
Modelo Mental
Modelo Formal
2
Evanivaldo C. Silva Jr.
Pesquisa Operacional
3
Modelo Mental: mais indicado para situações simples
EXEMPLO: Uma dona de casa precisa decidir entre
comprar manteiga ou margarina para o consumo doméstico.
Ela segue um raciocínio lógico através do qual procura
destacar as possíveis vantagens e desvantagens de cada
alternativa. Deve-se levar em consideração os fatores:
Custo de cada produto;
Sabor;
Os efeitos para a saúde;
A durabilidade;
A embalagem; e
A consistência quando gelado.
Evanivaldo C. Silva Jr.
Pesquisa Operacional
Modelo Formal: utilizado em problemas mais complexos
Dados de Entrada
• Processo tecnológico de
produção;
• Custos unitários;
• Disponibilidades;
• Preços de venda;
• Demandas dos produtos.
MODELO
Informações produzidas
• Relações entre:
• Lucro, custos,
recursos, etc...;
• Processos de
produção;
• Restrições à
utilização
• Margem total de lucro;
• Contribuição para o lucro
de cada produto;
• Quantidade a produzir; e
• Quantidade utilizada de
cada produto.
Exemplo de modelo complexo para a tomada de decisão (adaptado [1])
4
Evanivaldo C. Silva Jr.
Pesquisa Operacional
5
Ainda no aspecto de modelos, podemos considerar os seguintes
tipos de modelo:
1. Modelos conceituais: é o relacionamento de modo
sequencial e lógico entre as informações e as fases do
processo de decisão;
2. Modelos simbólicos ou matemáticos: é a suposição que o
problema pode ser equacionado e portanto quantificado
(transformado em números); e
3. Modelos heurísticos: é empregado quando a complexidade
matemática excede as ferramentas convencionais (sistemas
de busca inteligente).
Evanivaldo C. Silva Jr.
Pesquisa Operacional
6
Podemos dividir os modelos matemáticos em dois grandes
grupos:
1. Modelos de simulação;
2. Modelos de otimização.
Evanivaldo C. Silva Jr.
Pesquisa Operacional
Modelos de simulação
Simulação 1
Hipótese 1
Hipótese 2
MODELO DE
Hipótese 3
SIMULAÇÃO
PROCESSO DE
Simulação 2 ESCOLHA DA
MELHOR
Simulação 3
SOLUÇÃO
Solução
escolhida
Processo de decisão com modelos de simulação (adaptado [1])
7
Evanivaldo C. Silva Jr.
Pesquisa Operacional
Modelos de Otimização
Dados e
informações
do sistema
MODELO DE OTIMIZAÇÃO:
• Representação do sistema
• Critério de seleção da
alternativa
Solução
Ótima
DECISÃO
Processo de decisão com modelos de otimização (adaptado [1])
8
Evanivaldo C. Silva Jr.
Pesquisa Operacional
Modelo de Programação Linear (PPL)
9
Para que um sistema possa ser representado por meio de um
modelo PPL, ele deve possuir as seguintes características:
1. Proporcionalidade: a quantidade de recurso consumido por
uma dada atividade deve ser proporcional ao nível de
utilização dessa atividade;
2. Não negatividade: deve ser possível desenvolver qualquer
atividade em qualquer nível não negativo;
3. Aditividade: o custo total é a soma das parcelas associadas a
cada atividade; e
4. Separabilidade: pode-se identificar de forma separada o
custo específico das operações de cada atividade;
Evanivaldo C. Silva Jr.
Pesquisa Operacional
Modelo de Programação Linear (PPL)
Otimizar x = ∑ c x
n
0
j
j
j =1
n
∑a x
ij
j
≥ d j , i = 1, 2,K , p
j =1
n
Sujeito a:
∑a x = d ,
ij
j
i = p + 1, p + 2,K , m
j =1
xij ≥ 0,
j = 1, 2,K , q
xij ∈ , j = q + 1, q + 2,K , n
onde
M = {1, 2,K , m} , o conjunto dos índices das restrições do problema;
N = {1, 2,K , n} é o conjunto dos índices das variáveis;
M 1 ⊂ M e N1 ⊂ N
A = {aij } é a matriz das restrições;
a j é a j-ésima coluna de A;
x = ( x j ), j ∈ N é o vetor coluna de n componentes;
10
c = (c j ), j ∈ N é o vetor linha de n componentes;
Evanivaldo C. Silva Jr.
d = (di ), i ∈ M é o vetor coluna de m componentes;
Pesquisa Operacional
Modelo de Programação Linear (PPL)
11
No processo de modelagem de um problema de
programação linear (PPL) devemos seguir os seguintes
passos:
1. Definição do problema;
2. Identificação das variáveis relevantes;
3. Formulação da função objetivo;
4. Formulação das restrições;
5. Escolha do método matemático de solução;
6. Aplicação do método de solução; e
7. Avaliação da solução.
Evanivaldo C. Silva Jr.
Pesquisa Operacional
Modelo de Programação Linear (PPL)
12
EXEMPLO: Uma grande fábrica de móveis dispõe em estoque
de 250 metros de tábuas, 600 metros de pranchas e 500
metros de painéis de conglomerado. A fábrica normalmente
oferece uma linha de móveis composta por um modelo de
escrivaninha, uma mesa de reunião, um armário e uma
prateleira. Cada tipo de móvel consome uma certa quantidade
de matéria-prima, conforme a tabela abaixo. A escrivaninha é
vendida por 100 unidades monetárias (u.m.), a mesa por 80
u.m., o armário por 120 u.m. e a prateleira por 20 u.m.
Pede-se exibir um modelo de programação linear que
maximize a receita com a venda dos móveis.
Evanivaldo C. Silva Jr.
Pesquisa Operacional
Modelo de Programação Linear (PPL)
Quantidade de material em metros consumidos por
unidade de produto
Escrivaninha
Armário
Prateleira
Tábua
1
1
1
4
250
Prancha
0
1
1
2
600
Painéis
3
2
4
0
500
100
80
120
20
Valor de
Revenda
(u.m.)
13
Mesa
Disponibili
-dade de
Recurso (m)
Evanivaldo C. Silva Jr.
Pesquisa Operacional
Modelo de Programação Linear (PPL)
1. Escolha da variável de decisão:
•
xi= quantidade em unidades a serem produzidas do produto
escrivaninha (i=1), mesa (i=2), armário (i=3) e prateleira
(i=4)
• As variáveis de decisão são aquelas diretamente relacionadas
com a resposta do problema , ou seja, são elas que definem
o quanto se deve produzir.
14
Evanivaldo C. Silva Jr.
Pesquisa Operacional
Modelo de Programação Linear (PPL)
2. Função objetivo:
• Z=Maximizar : R( x) = 100 x1 + 80 x2 + 120 x3 + 20 x4
onde R(x) representa a receita bruta em reais em função da
quantidade produzida
• A função objetivo responde o valor total otimizado do
problema (custo, receita, lucro, etc.)
15
Evanivaldo C. Silva Jr.
Pesquisa Operacional
Modelo de Programação Linear (PPL)
3. Restrições do problema:
• Restrição associada à disponibilidade de tábuas:
x1 + x2 + x3 + 4 x4 ≤ 250
• Restrição associada à disponibilidade de pranchas:
x2 + x3 + 2 x4 ≤ 600
• Restrição associada à disponibilidade de painéis:
16
Evanivaldo C. Silva Jr.
3 x1 + 2 x2 + 4 x3 ≤ 500
Pesquisa Operacional
Modelo de Programação Linear (PPL)
3. Restrições do problema:
• Restrições de não-negatividade:
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0.
• OBS:
As restrições são funcionais que definem os limites dos
recursos utilizados nos processos de produção.
Quanto mais restrições um PPL tiver maior será o grau
de dificuldade em resolve-lo podendo até inviabilizar
uma solução.
17
Evanivaldo C. Silva Jr.
Pesquisa Operacional
Modelo de Programação Linear (PPL)
4. Modelo completo:
Maximizar: R( x) = 100 x1 + 80 x2 + 120 x3 + 20 x4
Sujeito a:
x1 + x2 + x3 + 4 x4 ≤ 250
x2 + x3 + 2 x4 ≤ 600
3x1 + 2 x2 + 4 x3 ≤ 500
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0.
18
Evanivaldo C. Silva Jr.
Modelo de Programação Linear (PPL)
Exercícios
19
Evanivaldo C. Silva Jr.
Pesquisa Operacional
Modelo de Programação Linear (PPL)
1 – Uma determinada empresa produz álcool anidro e álcool
20
hidratado, a partir de uma usina que está organizada em três
setores de produção. O processo de produção pode ser
resumido da seguinte forma: o álcool anidro passa pelos setores
I e III, sendo que cada tonelada desse produto consome 0,5 hora
do setor I e 1/3h do setor III, diariamente. Por outro lado, a
produção de uma tonelada do álcool hidratado demanda 1 hora
do setor II e 2/3h do setor III, também diariamente. Admitindo
que cada setor esteja em operação 8 horas por dia, e que as
receitas líquidas a serem obtidas para o álcool anidro e álcool
hidratado sejam $ 40 e $ 30 por tonelada, respectivamente,
determine
o modelo que resume o problema.
Evanivaldo C. Silva Jr.
Pesquisa Operacional
Modelo de Programação Linear (PPL)
2 – Um produtor comprou uma propriedade com 500 ha de
pasto. Ele tem um capital de $ 10.400 para gastar na compra de
gado ovino ou bovino. Os preços de mercado, os lucros anuais
estimados por animal e o número de hectares requeridos por
animal são dados na tabela apresentada abaixo. Obtenha o
modelo matemático (o PPL) afim de se obter a melhor
combinação de investimentos a ser perseguida.
Espécie de ovino
Carneiro Merino
Gado Hereford
Carneiro Romey
21
Evanivaldo C. Silva Jr.
Preço de mercado
$ 7,00
$ 100,00
$ 10,00
Hectares por animal
1.0
3,0
0,5
Lucro anual estimado
$12 ,00
$ 40,00
$ 7,00
Referências Bibliográficas
[1] Andrade, E. L., Introdução à Pesquisa Operacional, Rio de Janeiro,
ed. LTC, 1998.
[2] Caixeta-Filho, J. V. Pesquisa Operacional: técnicas de otimização
aplicadas a sistemas agroindustriais. Atlas, 2004.
[3] Lachtermacher, G. Pesquisa Operacional na Tomada de Decisões, ed.
Prentice Hall, 4ª.ed., 2009.
22
Evanivaldo C. Silva Jr.