Buscar

Modelos de Programação Matemática

Prévia do material em texto

1
Exemplos de modelos de 
PL ou PI
Prof. Eduardo Uchoa
http://www.logis.uff.br/~uchoa/POI/
2
� Toda a PO está baseada na construção de 
modelos matemáticos para representar de 
forma simplificada os sistemas reais.
Como funciona a PO?
3
Um modelo é uma representação 
simplificada de um sistema real
Modelo
Conclusões
do Modelo
Conclusões
sobre o
Sistema Real
Modelagem
Dedução
Interpretação
Sistema
Real
Graduação em Engenharia de Produção – Universidade Federal Fluminense
4
Para que serve um modelo?
Um modelo é útil quando permite que se 
chegue a conclusões adequadas sobre o 
sistema real, dentro de seu limite de 
aplicabilidade.
Como a PO trabalha com modelos 
matemáticos, a utilidade de um modelo 
também depende da existência de métodos 
matemático-computacionais capazes de 
resolver o modelo.
5
Um modelo de programação matemática é definido por 
um sistema de equações/inequações.
• As variáveis representam as decisões a serem 
tomadas.
• As equações/inequações representam as 
restrições que existem sobre essas decisões, 
refletindo as características do sistema real.
• Uma função objetivo indica qual dentre as 
possíveis decisões é a mais desejável (solução 
ótima).
Programação Matemática
6
Tipos de Modelos de Programação 
Matemática
� Programação Linear: todas as restrições e a FO 
são funções lineares
� Um número razoável de sistemas reais podem ser 
bem modelados como PLs
� Métodos de solução extremamente eficazes, 
problemas com milhões de variáveis e restrições 
podem ser resolvidos num laptop
7
Tipos de Modelos de Programação 
Matemática
� Programação Inteira: todas as restrições e a FO 
são funções lineares, mas algumas variáveis 
podem ser obrigadas a terem valores inteiros.
� Um número enorme de sistemas reais podem ser bem 
modelados como PIs
� Métodos de solução bem menos eficazes, problemas 
com alguns milhares de variáveis e restrições já
podem ser intratáveis
8
Problema da Dieta
� Em 1945, o economista George Stigler propôs o 
problema de calcular o “custo mínimo anual de 
sobrevivência” nos EUA. 
9
Problema da Dieta
� Segundo os nutricionistas 
da época, as necessidades 
de um homem de 70 Kg
são:
75 mgVit. C
18 mgNiacina
2,7 mgVit. B2
1,8 mgVit. B1
5000 UIVit. A
12 mgFerro
0,8 gCálcio
70 gProteína
3000 kcalCalorias
Mínimo/diaNutriente
10
Problema da Dieta
� Stigler pesquisou a 
quantidade desses 
nutrientes em 77 diferentes 
alimentos, bem como o 
custo desses alimentos no 
atacado.
75 mgVit. C
18 mgNiacina
2,7 mgVit. B2
1,8 mgVit. B1
5000 UIVit. A
12 mgFerro
0,8 gCálcio
70 gProteína
3000 kcalCalorias
Mínimo/diaNutriente
11
Problema da Dieta
� Depois de sucessivas tentativas, Stigler
encontrou a seguinte possível dieta:
$39,93Total
$16,80129,3 kgFeijão
$1,8510,4 kgEspinafre
$4,1150,3 kgRepolho
$3,8457 latasLeite Condensado
$13,33167,8 kgFarinha de trigo
CustoQuant.Alimento
http://en.wikipedia.org/wiki/Stigler_diet
12
Problema da Dieta
� Esse custo de $39,93 equivale a cerca de $600 
em valores atuais.
� Em 1947 Dantzig imediatamente percebeu que 
esse problema poderia ser modelado por PL e 
encontrou a solução ótima com um custo de 
$39,69. 
� Essa modelagem logo foi adotada na indústria de 
rações para animais
13
Dados do Modelo
� N: Número de alimentos considerados
� M: Número de nutrientes considerados
� Cj: Custo por unidade do alimento j; j=1,...,N
� Mini: Necessidade mínima do nutriente i; i=1,...,M
� aij: quantidade do nutriente i por unidade do 
alimento j; i=1,...,M, j=1,...,N
Os dados de um modelo são conhecidos a priori,
ou seja, antes de resolver o modelo.
14
Variáveis do Modelo
� xj: Quantidade do alimento j que deve ser incluída 
na dieta; j=1,...,N
As variáveis de um modelo representam as 
decisões a serem tomadas, seus valores
só serão conhecidos após a resolução do
modelo.
15
Formulação do Modelo
A formulação é o sistema de equações/inequações
montado sobre os dados e as variáveis e que deve
ser resolvido matematicamente
Njx
MiMinxa
xc
j
i
N
j
jij
N
j
jj
,,10
,,1S.a.
inM
1
1
K
K
=≥
=≥∑
∑
=
=
16
Um exemplo com M=2 e N=4
� Uma nutricionista de empresa quer montar 
porções de salada de frutas que contenham pelo 
menos 3000 UI de vitamina A e 50 mg de 
vitamina C. 
� As frutas disponíveis no dia são: abacaxi, 
banana, maçã e melancia.
17
Custo por kg e quantidade de nutrientes
1.50 2,00 0.80
7000 8000 6000
550 300 250
3,00
30000
400
A
C
Graduação em Engenharia de Produção – Universidade Federal Fluminense
18
Programa Linear
1,50 + 2,00 + 0,80
7 + 8 + 6
550 + 300 + 250
+ 3,00
+ 30
+ 400
A
C
x1 x2 x4
x1 x2 x4 ≥ 3
x1 x2 x4
min x3
x3
x3 ≥ 50
19
Programa Linear
1,50 + 2,00 + 0,80
7 + 8 + 6
550 + 300 + 250
+ 3,00
+ 30
+ 400
A
C
x1 x2 x4
x1 x2 x4 ≥ 3
x1 x2 x4
min x3
x3
x3 ≥ 50
Solução ótima: 88g de maçã e 60g de melancia. Custo: R$ 0,31/ porção
20
Todo modelo de PO deve ser criticado 
antes de ser adotado!
� Suponha que vc é o gerente de uma granja 
de frangos e vai usar o modelo do 
problema da dieta para determinar a 
composição ótima da ração nesse mês.
� Vc analisa todos os 73 possíveis 
ingredientes disponíveis no mercado com 
respeito a todos os 40 nutrientes 
considerados importantes para as aves.
21
Todo modelo de PO deve ser criticado 
antes de ser adotado!
� Mesmo assim, que críticas ainda poderiam 
ser levantadas sobre a validade do seu 
modelo?
� Em outras palavras, que elementos do 
sistema real ignorados no modelo poderiam 
fazer com que a solução ótima do modelo 
fique distante da solução ótima real?
22
Hipóteses de modelos de PL que podem 
levar a críticas
� Proporcionalidade: o efeito de uma variável 
na FO e nas restrições é proporcional a seu 
valor.
� Aditividade: o efeito total de duas (ou mais) 
variáveis é a soma dos seus efeitos 
individuais.
� Divisibilidade: as variáveis podem assumir 
valores fracionários. 
23
Exemplo de crítica e possíveis ações
� Crítica: os ingredientes só são vendidos em 
sacas de 60kg
� Ações:
� A granja é grande e as compras são da ordem 
de dezenas de toneladas? Sim => Manter o 
modelo como está
24
Exemplo de crítica e possíveis ações
� Não, a granja é pequena e as compras são da 
ordem de centenas de quilos.
� O excesso comprado em um mês pode ser estocado 
para o seguinte? Sim => Manter o modelo
� Não, os ingredientes são perecíveis => Transformar 
em um modelo de PI
25
Todo modelo de PO deve ser criticado 
antes de ser adotado!
� É possível que surjam críticas relevantes 
que não tem como ser rebatidas ou 
facilmente contornadas.
� Nesses casos pode ser preciso repensar 
todo o modelo.
26
Problema de Transporte Clássico
Suponha que uma empresa de cimento tenha m fábricas, cada 
uma delas uma capacidade de produção conhecida, que 
devem atender n cidades, com suas demandas conhecidas. Os 
custos (em R$) de se transportar uma tonelada de cimento 
entre uma fábrica e uma cidade qualquer são dados abaixo:
m/n 1 2 3 4 5
1 60 220 300 270 450
2 95 45 200 260 230
3 450 300 250 100 90
27
Problema de Transporte Clássico
As capacidades de produção de cimento (ton), bem como as 
demandas das cidades (ton), podem ser vistas a seguir:
m
Capacidade de 
produção
1 1100
2 1300
3 1100
n Demanda das Cidades
1 400
2 200
3 900
4 1200
5 750
28
Problema de Transporte Clássico
Determinar quanto cada fábrica deve enviar 
a cada cidade de maneira a minimizaros 
custos de transporte.
29
O Problema de Transporte é
modelado com PL
Solução ótima de custo R$611.500,00
Quantidades a serem transportadas:
m/n 1 2 3 4 5
1 400 700
2 200 200 100 750
3 1100
30
Problema do Caixeiro Viajante
� n cidades p/ visitar
� Distâncias dij entre 
as cidades i e j
� Escolher uma rota 
de comprimento 
mínimo visitando 
cada cidade uma 
única vez e 
voltando ao ponto 
de partida.
31
Problema do Caixeiro Viajante
� Modelável com 
PI
� Problemas 
muito grandes 
podem ser 
resolvidos de 
forma ótima
32
Problema do Roteamento de 
Veículos
K veículos saem de um depósito para fazer entregas em n 
clientes e depois retornar ao depósito. Cada veículo tem uma 
capacidade limitada em peso e volume. São conhecidas as 
distâncias entre o depósito e um cliente e entre cada par de 
clientes.
33
Problema do Roteamento de 
Veículos
Determinar quais clientes devem ser 
atendidos por cada caminhão e a seqüência 
de visitação de cada um deles, de forma a 
não estourar as capacidades e minimizar a 
distância total percorrida
Modelável com PI, difícil de resolver para 
problemas com > 75 clientes
34
Problema do Roteamento de 
Veículos
Modelável com PI, difícil de resolver de forma exata para 
problemas com > 75 clientes
Boas soluções aproximadas (digamos 1% do ótimo) para 
problemas maiores podem ser obtidas por métodos 
conhecidos como heurísticas
Os erros da aproximação ao se resolver o modelo se 
somam ao erro da própria modelagem
Mesmo, assim os ganhos típicos em relação ao 
planejamento manual são da ordem de 15-20%
35
Problema do Carteiro Chinês
Um carteiro tem que entregar 
correspondência em cada uma 
das ruas de um bairro, saindo 
da agência e retornando a ela.
Graduação em Engenharia de Produção – Universidade Federal Fluminense
36
Problema do Carteiro Chinês
Determinar o caminho que o carteiro deve 
seguir para minimizar a distância total 
percorrida.
Em certos casos é modelável por PL, em 
outros exige PI. De qualquer forma, 
problemas grandes podem ser resolvidos
37
� n clientes
� m locais potenciais p/ 
abrir algum serviço
� Distâncias dij entre 
cliente i e local j
� Escolher p locais para
minimizar a soma das 
distâncias de cada
cliente ao local aberto
mais próximo.
Localização de instalações: Problema das 
p-medianas
Graduação em Engenharia de Produção – Universidade Federal Fluminense
38
Modelo de PI
Variáveis (todas binárias):
� xj (j = 1, ..., m) = 1 se o local j é aberto
� yij (i = 1, ..., n; j = 1, ..., m) = 1 se o cliente i é
atendido no local j
39
Formulação
{ }
{ } mjx
mjniy
px
mjnixy
niy
yd
j
ij
m
j
j
jij
m
j
ij
n
i
m
j
ijij
K
KK
KK
K
,11,0
,1;,11,0
,1;,10
,11S.a
Min
1
1
1 1
=∈
==∈
=
==≤−
==
∑
∑
∑∑
=
=
= =
40
OBSERVAÇÃO
Este material refere-se às notas de aula do curso 
TEP117 (Pesquisa Operacional I) da Universidade 
Federal Fluminense (UFF) e não pode ser 
reproduzido sem autorização prévia do autor. 
Quando autorizado, seu uso é exclusivo para 
atividades de ensino e pesquisa em instituições 
sem fins lucrativos.

Outros materiais