1Métodos de Análise de Sistemas Produtivos
MASP
Sistemas produtivos
2Métodos de Análise de Sistemas Produtivos
MASP
Sistema Produtivo
Sistema ProdutivoMatéria PrimaEnergia
ProdutosServiços
Controlos
SubprodutosResíduos
ComponentesServiços Externos
Informação
3Métodos de Análise de Sistemas Produtivos
MASP
“Controlo” do Sistema Produtivo
Sistema Produtivo
Sistema de Controlo
ObjectivosInformaçãoExterna
Ordens Feedback
Fornecedores:Material
(→ Compras)
Clientes:Produtos
(→ Vendas)
4Métodos de Análise de Sistemas Produtivos
MASP
Diferentes vistas
Sistema Físico
Sistemade
Informação
Fornecedores:Material
(→ Compras)
Clientes:Produtos
(→ Vendas)
Sistemade
Decisão
Sistema de Controlo
5Métodos de Análise de Sistemas Produtivos
MASP
Abordagem holística
Sistema Produtivo
Empresa
Envolvente
...
6Métodos de Análise de Sistemas Produtivos
MASP
A Organização
MissãoCompras
Produção Expedição
Vendas
FinançasPagamentosFornecedoresColaboradores
StockMaterial
expedição
StockMaterialvenda
Clientes
Caixa eDepósitosbancários
StockMaterial
comprado
Informação
Workflow
Valor
Análise e algoritmos
João Borges de Sousa
“…I have found that students do not really master the material in it until they have used it to formulate and solve life problems of interest to them”
Carlos Daganzo
9Métodos de Análise de Sistemas Produtivos
MASP
Organização
Introdução• O quê?
• Porquê?
• Como?
Parte 1 - Análise com base modelos sucintos e sumários de dados• Formulação
• Método de resolução
Parte 2 - Problemas de fluxos em redes• Modelos e algoritmos
• Aplicações
• Design e análise de algoritmos
10Métodos de Análise de Sistemas Produtivos
MASP
Método
Descrever problemas
Colocar desafios
Discutir os desafios
Desenvolver modelos
Apresentar soluções
Analisar soluções
Métodos não se limitam a sistemas de produção• problemas de tráfego aéreo• problemas militares• etc.
11Métodos de Análise de Sistemas Produtivos
MASP
Bibliografia
Carlos Daganzo, Logistic Systems Analysis, Springer Verlag, 1998
Carlos Daganzo, A Theory of Supply-chains, Springer Verlag, 2003
R. Ahuja, T. Magnanti and J. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993
Introdução
13Métodos de Análise de Sistemas Produtivos
MASP
O quêDado um sistema produtivo, a projectar ou existente, integrado numaeconomia como optimizar o seu funcionamento?
Problema geral• Ferramentas de análise• Ferramentas computacionais• Heurísticas• Como endereçar a complexidade• Como integrar técnicas e análises
Requer• Familiariedade com:
- Técnicas e modelos (abstracções)- Viabilidade computacional (complexidade)
• Engenharia de sistemas (IEEE standard, System’s Engineering Handbooks)• Bom senso educado (Engenharia)• Experiência
Recomendação• Sejam WIP!!!
Porquê
Caso de estudo
Discussão
Case study
Logística: “Conjunto de actividades cujo objectivoé transportar items entre origens e destinos em
tempo útil”
16Métodos de Análise de Sistemas Produtivos
MASP
Elementos do case study
1. Características gerais de sistemas produtivos
2. Coordenação de actividades de múltiplos sistemas
3. Dimensão/complexidade
4. Modelos utilizados
5. Técnicas de análise
17Métodos de Análise de Sistemas Produtivos
MASP
O sistema
Fabricante de computadores, radios e televisões
3 fábricas• Green bay• Indianopolis• Denver
100 centros de distribuição
1 armazém localizado próximo da fábrica de Indianapolis
Componentes são montados antes de serem vendidos• nos centros de distribuição ou• no armazém
18Métodos de Análise de Sistemas Produtivos
MASP
Problema
Determinar a estratégia de distribuição que minimizaa soma dos custos de transporte e de manutenção de inventários
19Métodos de Análise de Sistemas Produtivos
MASP
Dados produto e produção
Fábrica Produtos Custo ($) Peso (lbs)Green Bay Computer modules 300 5Indianapolis Televisions Monitors/keyboards 400 10Denver Consoles 100 30
Denver Green Bay IndianapolisProdutos comercializados\Componentes Console Computer module Monitor\keyboard TelevisionTelevision 1Console 1Computer 1 1
20Métodos de Análise de Sistemas Produtivos
MASP
Dados da procura por centro de distribuição
Denver Green Bay IndianapolisProcura dia ano (250 dias) Console Computer module Monitor\keyboard TelevisionTelevision 10 2500 2500Console 10 2500 2500Computer 10 2500 2500 2500
Totais\fábrica 2500 2500 5000
21Métodos de Análise de Sistemas Produtivos
MASP
Dados de custos distribuição e inventário
Custos distribuição• Distâncias tabeladas
- Sumário- Distância média = 1000 Km
• Camiões: - Capacidade: 30.000 lbs- Preço por Km: $1
Custo inventário• Taxa 0.06% do custo
produto/dia de trabalho
• = 15% em 250 dias de trabalho
A
22Métodos de Análise de Sistemas Produtivos
MASP
Estratégias
1. O armazém não é utilizadoe tudo é enviadodirectamente das fábricaspara os centros de distribuição em camiõessem paragens intermédias
2. Todos os componentes sãomontados no armazém e oscamiões viajam semparagens das fábricas para o armazém e deste para oscentros de distribuição Qual parece melhor?
Depende de quê?
23Métodos de Análise de Sistemas Produtivos
MASP
Discussão estratégia 1
Custo transporte = cvt*nv
• Custo viagem típica cvt- cvt = 1000 km * $1 = $ 1000
• Número de viagens nv- nv = (nvDenver+ nvIndianapolis+ nvGreen Bay )*ncentros- nvIndianapolis = 5000*10/30.000 = 1.667- nvGreen Bay = 2500*5/30.000 = 0.417- nvDenver = 2500*30/30.000 = 2.5- ncentros = 100
cvt*nv = 1000*((1.667+.417+2.500)*100) = 4.6e5
24Métodos de Análise de Sistemas Produtivos
MASP
Discussão estratégia 1
Custo inventário = cigreenbay + ciindianapolis+ cidenver
• Tempo de espera em inventário na fábrica e no centro
- Fv = Período de viagens = 1/(Numero de viagens/ano)
- Tempo de espera médio no centro e na fábrica = Fv/2
• cixx = ncentros* nprocura * precoxx* Fv/2 *2 * taxa
- cigreenbay = 100 * 2500 * 300 *(.417-1) * .15
- cidenver = 100 * 2500 * 100 *(2.5)-1 * .15
- ciindianopolis = 100 * 2500 * 2*400 *(1.667)-1 * .15
Custo inventário = 46.5e6
Custo total = 4.6e5 + 46.5e6
A
É possível melhorar estes resultados?
25Métodos de Análise de Sistemas Produtivos
MASP
Discussão estratégia 2
Custos de transporte• Aumentam em função da ida ao armazém
• Distâncias médias são da ordem de 1000 km
• Entre armazém e centros- deverá ser da ordem do anterior- 1000*((1.667+.417+2.500)*100) = 4.6e5
• Entre fábricas e armazém- Deverá ser da ordem do anterior com excepção de Indianapolis- 1000*((.417+2.500)*100) = 3e5
• Custo total = 7.6e5
A
26Métodos de Análise de Sistemas Produtivos
MASP
Discussão estratégia 2
Custos de inventário• Green bay e Denver
• Armazém (Indianapolis) e centros- Cada centro recebe/ano cr = 2500*(15+30+10)lbs/ ano- N. viagens/ano nv = cr/30000 = 4.6- Custo inventário/item ci = (300+400+400+100)*.15/nv- Custo inventário c = ci*250000
Custo inventário = 10.1e6
Custo total = 10.5e6
N. items/centro N. centros Peso item N. viagens C. Inventário por item C. InventárioGreen bay 2500 100 5 41,7 1,08 270000Denver 2500 100 30 250 0,06 15000
Total 285000
Cinventário/item = precoxx* Fv/2 *2 * taxa
27Métodos de Análise de Sistemas Produtivos
MASP
É possível melhorar os resultados?Custo de inventário
• Custo inventário/item = (custo item)*taxa/(numero viagens)
Como é que o podemos baixar?• Aumentar numero de viagens• Utilizar camiões com cargas parcelares• Incorrendo em maiores custos de transporte para aumentar a frequência das
viagens
Existe uma frequência óptima de despacho
Custo óptimo• Custo/ano = 2*[(.15)*rate*flow*value]^0.5
• Rate – custo de transporte $• Flow – lbs por ano• Value – valor do produto $/lb
Implementação requer uma grande coordenação entre responsáveis de transporte e de inventário
28Métodos de Análise de Sistemas Produtivos
MASP
Evoluções das estratégias iniciais
3. Directa + frequência óptima
4. Armazém + frequência óptima
5. Parte directa + parte armazém
29Métodos de Análise de Sistemas Produtivos
MASP
Comparação de resultados
Q: o que aconteceria se a procura de televisões aumentasse?
30Métodos de Análise de Sistemas Produtivos
MASP
Problemas relaccionados
Determinação da localização de centros de distribuição
Planeamento de rotas
Sub-contratações• Transporte
• componentes
Optimização multi-critério
Outros…
31Métodos de Análise de Sistemas Produtivos
MASP
Problema geral
Como abordar?
Como decompôr?
Como agregar?
Propriedades (Robustez, Flexibilidade)?
Como integrar técnicas/metodologias?
Como?
33Métodos de Análise de Sistemas Produtivos
MASP
Tipos de abordagens
Problem-based• Case study como exemplo
• Modelos analíticos simples
• Agregação de dados e aproximações
• Privilegia a análise
Method-based• Baseados em formulações conhecidas
• Análises e algoritmos semelhantes
• Requer muitos dados
• Análise difícil
34Métodos de Análise de Sistemas Produtivos
MASP
Problem-based
Foi a abordagem utilizada no solução case study1. Mesmo que haja dados detalhados as principais
aproximações são efectuadas à partida2. Os métodos numéricos são substituídos por modelos
analíticos3. Os modelos analíticos são resolvidos com detalhe4. É possível identificar propriedades de soluções próximas do
óptimo5. Estas são utilizadas para formular guias para a
implementação6. O passo final de optimização pode ser efectuado com
recurso a um algoritmo de optimização computacional7. Mesmo que os dados mudem os princípios de projecto são os
mesmos
35Métodos de Análise de Sistemas Produtivos
MASP
Utilidade e flexibilidade• Modelos simples são fáceis de explicar• Facilidade em entender e explicar o funcionamento sistema
- São mais convincentes- Podem ajudar a encontrar problemas na formulação inicial e ajudar a
expandi-la
Accuracy dos resultados• A falta de dados precisos não deve ser desculpa para a falta de
análise• Não se deve procurar a precisão de dados só por si• Múltiplos factores que influenciam decisões. As soluções numéricas
podem ser demasiado rígidas• Fontes de erros
- Abordagem: simplificações- Tradicional: falha de algoritmos em encontrar boas soluções
36Métodos de Análise de Sistemas Produtivos
MASP
Method-based
Abordagem tradicional da logística1. Formulação de um problema de programação matemática
2. Grande volume de dados
3. Decisões: 1. não são baseadas em análises sistemáticas2. Baseadas em heurísticas que não são particularmente insightfull
4. Problemas NP-hard
Exemplo: Network flow methods
37Métodos de Análise de Sistemas Produtivos
MASP
Network flow methods
Problemas típicos• Caminho mais curto
• Máximo fluxo
• Mínimo custo de fluxo
Formulação bastante geral
Questões• Complexidade
• Não utilização de programação linear
38Métodos de Análise de Sistemas Produtivos
MASP
Mínimo custo de fluxo• É o mais fundamental de todos os network flow problems
Problema• Dada uma rede determinar o custo mínimo de transporte de
uma mercadoria através da rede a partir de nós de distribuição e com o objectivo de satisfazer a procura emdeterminados nós
Formulação num grafo G=(N,A)• N conjunto de n nós• A conjunto de arcos (i,j) com custo associado ci,j (linear)
39Métodos de Análise de Sistemas Produtivos
MASP
Mínimo custo de fluxo ∀i ∈ N • b(i) inteiro que representa a procura em i
- b(i)> 0 – nó fornecedor- b(i)< 0 – nó consumidor- b(i)= 0 – nó de transferência
• Variáveis de decisão- Fluxo xi,j nos arcos
40Métodos de Análise de Sistemas Produtivos
MASP
Mínimo custo de fluxo
Mass balance constraints
Flow bound constraints
41Métodos de Análise de Sistemas Produtivos
MASP
Caminho mais curto• O custo ci,j tem a interpretação de distância• Procurar caminho mais curto de um nó fonte s para um nó
poço t• Fazer
- b(s) > 1 – nó fonte- b(t) < -1 – nó poço- b(i) = 0 – todos os outros nós
• Outros problemas/interpretações1. Mandar um fluxo de v unidades de um nó fonte para um nó poço
em que a restrição de fluxo em todos os arcos é v2. Caminho mais curto de um nó fonte para todos os nós do grafo
1. b(s)=n-12. b(i)=-1 para todos os outros nós
42Métodos de Análise de Sistemas Produtivos
MASP
Máximo fluxo• Não há restrições de capacidades
• Existem restrições de fluxo
• ui,j é o fluxo máximo no arco (i,j)
• Formulação como problema de mínimo custo de fluxo- b(i)= 0 – todos os nós- ci,j = 0 – para todos os arcos- cs,t = -1- us,t = infinito
• Porquê- Maximizamos o fluxo no arco (s,t) - Qualquer fluxo em (s,t) tem que circular nos arcos do grafo
(b(i)=0)
43Métodos de Análise de Sistemas Produtivos
MASP
Alocação recursos• Dados
- Conjuntos N1 e N2
- #N1 = #N2
• A ⊂ N1 x N2 alocações
• ci,j custo associado a cada arco (i,j)
• Encontrar os pares de N1 e N2 com custo mínimo
• G = (N1 ∪ N2,A)
• b(i) = 1 para i em N1
• b(i) = -1 para i em N2
• ui,j = 1
44Métodos de Análise de Sistemas Produtivos
MASP
Outros problemas
Transportes
Circulação
Convexos
Generalizados
Multiple commodity flow problems
Parte 1Modelos sucintos e sumários de dados
Custos
Métodos de optimização
Caso de uma origem e de um destino
Projecto de redes
46Métodos de Análise de Sistemas Produtivos
MASP
Custos
Caminho de um item da produção para o destino• Transportado da produção para o armazenamento
• Espera em armazém por transporte
• Transportado do armazém para o veículo
• Transportado para o destino
• Transportado do veículo para o armazém (+operações destino)
• Espera em armazém por consumo
Tipos• Motion – para ultrapassar distância
• Holding – para ultrapassar tempo
47Métodos de Análise de Sistemas Produtivos
MASP
Tipos de custoHolding (não é uma terminologia universal)
• Rent• Waiting ou inventory
Motion• Handling fora do veículos de transporte (inclui packaging) • Transportation (inclui loading)
Análise• Identificar os quais os parâmetros que influenciam que custos• Identificar forma matemática das relações
Representação• Definir como representar os custos• Nem todas as representações de custo são válidas para análise• Utilizar factores de conversão constantes
48Métodos de Análise de Sistemas Produtivos
MASP
Holding costs: interpretação geométrica
Gráfico acumuladosi) produção
ii) shipments
iii) chegadas
iv) consumo
Contém informaçãorelevante
Procura = produção D’i) ii) iii) iv)
49Métodos de Análise de Sistemas Produtivos
MASP
cont
∀t, separações verticais• entre i e ii)
- numero de items à espera de transporte
• entre iii e iv) - numero de items à espera de serem consumidos
• entre ii e iii) - numero de items em transporte
Consider que os items passam numa order fifo
Separação horizontal• Tempo passado entre duas estações consecutivas
• tm – tempo de transporte
50Métodos de Análise de Sistemas Produtivos
MASP
cont
Integrais• Horas item passadas na origem
• Horas item passadas no destino
Separação média horizontal entre duas estações• Tempo médio passado por um item entre essas estações
Para este exemplo• Separação constante entre produção e consumo
- Tempo médio de espera entre produção e consumo- Wait = H1 + tm
- H1 = max{Hi}
Máxima acumulação• Maximum accumulation = D’ H1
51Métodos de Análise de Sistemas Produtivos
MASP
Holding costs: componentes
Rent• Para sistemas bem dimensionados ~ maximum accumulation• Factor de proporcionalidade cr = f(tamanho, requisitos armazém)
- Rent cost/year = cr * maximum accumulation em $/item-ano• Se a procura for constante
- Rent cost/item = cr(D’ H1)/D’= crH1- Independente do fluxo- Proporcional ao valor máximo de H
Waiting• Também chamado custo de inventário associado a espera
- Tempo de espera = H1+tm- Waiting cost/year = ci[D’ (H1+tm)]- Waiting cost/year/item = ci[D’ (H1+tm)]/D’ = ciH1+citm = civ/D’+citm
- ciH1 – stationary inventory cost- citm – pipeline inventory cost- v – maximum shipment size
52Métodos de Análise de Sistemas Produtivos
MASP
cont
A determinação dos valoresdos custos ci não é simples
Depende das condições de mercado
Exemplo• Π0 preço produção
• Π1 preço venda
• Π1 > Π0
Situações diferentes• Procura fixa
• Procura absorve tudo
53Métodos de Análise de Sistemas Produtivos
MASP
Transportation costs: expressões
Custo total transporte = soma custos de cada viagem• Shipment cost ≅ cf+ cvv
- v shipment size
Custo de sequência {vi} de n shipments no total de V items (V=∑ivi)
• Cost for n shipments = ∑icf + cv vi = ncf + cvV- Depende de n- Independente de quando são efectuados e do que consta- Depende do numero total de items tranportados
• Transportation cost/item = cf (n/V)+cv
- As economias de escala derivam de todos os items num mesmoshipment partilharem os custos fixos
- Diminui com o tamanho médio do shipment (V/n)
54Métodos de Análise de Sistemas Produtivos
MASP
Transportation costs: headways
Análise• Transportation cost/item = cf (n/V)+cv = cf (1/D’H) + cv
- V = ∑iD’Hi = D’Hn- H – valor médio dos headways Hi
• Custo de transporte diminuem com H
• Custo inventário aumentam com o valor máximo Hi
- Rent cost/item = cr(D’ H1)/D’= crH1
Logo• Os carregamentos devem ser espaçados com a máxima
regularidade praticável de forma a diminuir o máximoheadway e o associado holding cost
55Métodos de Análise de Sistemas Produtivos
MASP
Transportation costs: capacidade
Máximo shipment size vmax
cvvmax << cf os custos de operar o veículo devem ser insensíveis relativamente aoque contém
Transportation cost per shipment
• ft(v)• Subaditiva
- ft(x1+x2) ≤ ft(x1)+ ft(x2)• Porque não se reduz o custo
de transporte se se enviar porpartes
Shipment cost ≅ cf+ cvv
56Métodos de Análise de Sistemas Produtivos
MASP
Cont
Em muitos problemas basta consider a parte linear de ft entre 0 e vmax
• não é económico enviar shipments maiores
Vejamos porquê:• Ignore os custos de handling• Assuma que o espaçamento é fixo
Waiting cost/year/item =
ci[D’(H1+tm)]/D’= ciH+citm = civ/D’+citm
Transportation cost/item =
cf (n/nv)+cv = cf (1/v)+ cv
Optimal shiping size• Min {Av+b/v}s.t: v ≤ vmax
• A = ch/D’• B = cf
• ch= ci+cr
57Métodos de Análise de Sistemas Produtivos
MASP
Transportation costs: modos alternativos
Shipment cost ≅ cf+ cvv• Aumenta linearmente com v• Válido quando v varia num
intervalo grande
Considerar outros modos de transporte se a qualificaçãonão for verdadeira
• Vários modos terão cf e cvdiferentes
• Modo óptimo = f(tamanho)• Crescente e concava
- Subaditiva
Para uma frota poderepresentar diferentes tiposveículos
58Métodos de Análise de Sistemas Produtivos
MASP
Handling costs: expressões
Inclui• carregar items individuais num
contentor• Movimentar o contentor para o
veículo• Refazer o processo no destino
Custo shipment size• items tratados individualmente
- Handling cost ≅ c’vv• Items transportados em pallets
- Handling cost ≅ c’f + c’vv- v’max – numero de items numa
pallete
Formulação igual• Origem• Destino
59Métodos de Análise de Sistemas Produtivos
MASP
Handling costs: motion cost
A figura descreve a soma de handling e transportation costs quando v’max << vmax
60Métodos de Análise de Sistemas Produtivos
MASP
Handling costs: lot-sizing tradeoff
Da mesma forma queanteriormente
61Métodos de Análise de Sistemas Produtivos
MASP
Sumário distribuição 1-1
1. Podem-se obter estimativas precisas dos custos sem informaçãodetalhada
2. Perturbações moderadas de uma solução óptima não aumentamo custo de uma forma significativa
3. Dados detalhados podem introduzir complexidade adicional e eventualmente dificultar a procura do óptimo
4. Daganzo sugere uma abordagem de 2 níveis para o problema dalogística
1. Analítica1. Detalhe mínimo2. Conceitos de solução gerais
2. Afinação1. Soluções específicas2. Consistente com a primeira3. Utiliza toda a informação
62Métodos de Análise de Sistemas Produtivos
MASP
Transportation+holding costs
63Métodos de Análise de Sistemas Produtivos
MASP
Lot-sizing com procura constante
z = Min {Av+B/v : v ≤ vmax}
Caso vmax = ∞• v* = sqrt(B/A) • A = ch/D’ holding cost/item• ch= ci+cr
• B = cf fixed motion costs• v* torna os dois termos da função custo iguais
Custo óptimo• z* = (cost/item)* = 2 sqrt(AB)• aumenta a uma taxa decrescente com cf,ch
• diminui com D’ ⇒ economias de escala
64Métodos de Análise de Sistemas Produtivos
MASP
Robustez a erros
Variável de decisão• v0=v* β
• β’ = z0/z* = 0.5[β+1/β]- Independente de A e de B- .5 < β < 2 então β’< 1.025- Se a variável de decisão for 25% do valor óptimo o custo fica a
.25% do custo óptimo
Erros de dados• A’ = βA ou B’ = βB
• v0’= v*/sqrt(β)
• A robustez relativamente a erros de dados é grande- .5 < β < 2 então β’< 1.1
65Métodos de Análise de Sistemas Produtivos
MASP
cont
Erros de modelo
66Métodos de Análise de Sistemas Produtivos
MASP
cont
Combinações de erros• Pode não ser aditiva
67Métodos de Análise de Sistemas Produtivos
MASP
Lot-sizing com procura variávelExpressões
D’• Varia com o tempo• Variação conhecida D(t) = integral D’
Pretende-se determinar tempos e tamanhos de lote• t0, t1, t2, …, tn-1 tempos em que os carregamentos devem ser
recebidos• v0, v1, v2, …, vn-1tamanhos dos lotes
Que minimizem a soma dos custos
Dados• cf
• ch = cr + ci
• vmax
Inicialmente vamos assumir que a ultima restrição é relaxada
A matéria deste slide não será objecto de avaliação
68Métodos de Análise de Sistemas Produtivos
MASP
Lot-sizing com procura variávelExpressões
Caso holding cost = rent cost
A matéria deste slide não será objecto de avaliação
69Métodos de Análise de Sistemas Produtivos
MASP
Lot-sizing com procura variávelExpressões
Caso rent cost é desprezável
A matéria deste slide não será objecto de avaliação
70Métodos de Análise de Sistemas Produtivos
MASP
Lot-sizing com procura variávelExpressões
Aproximação contínua
A matéria deste slide nãoserá objecto de avaliação
Elementos para projecto de redes
72Métodos de Análise de Sistemas Produtivos
MASP
Considerações gerais
Problemas reais de logística• Como e quando despachar
• Projecto rede de distribuição
As economias de escala são traduzidas pelo facto de o custo óptimo por item diminuir com a D’
Vamos discutir elementos de projecto de redes com• Múltiplos destinos
• Trajecto de um item não está pré-determinado
• Custo decresce com o fluxo
73Métodos de Análise de Sistemas Produtivos
MASP
Exemplo ilustrativo
Procura = produção
Suponha que fracção x dos items para P2 são enviadosvia P1
• x1 = 4(1+x)• x2 = 4(1-x)• x3 = 4x
Custo de transporte• Soma dos custos dos arcos
- Válido desde que não se pretendacoordenar os horários nos 3 arcos
• ∑ixiz(xi)• z(xi) aumenta a uma taxa
decrescente (concava)• xi linear em x• Custo concavo em x
Formulação conhecida?O que se passa para multiplos produtos?
O que é uma função concava?E um conjunto concavo?Como se relacionam as duas definições?
74Métodos de Análise de Sistemas Produtivos
MASP
cont
Exemplo• z1 = 1/sqrt(x1)
• z2 = 3/sqrt(x2)
• z3 = 1
• x1 z1 = sqrt(x1)
• x2 z2 = 3sqrt(x2)
• x3 z3 = x3
• Custo total = 2sqrt(1+x)+6sqrt(1-x)+4x
Valor óptimo x*=1- Custo concavo- Extremo do intervalo
75Métodos de Análise de Sistemas Produtivos
MASP
Discussão
O mesmo princípio tudo ou nada aplica-se a problemas com múltiplas origens/destinos se função custo for concava
No caso de uma origem e múltiplos destinos isto implica apenasuma rota
Intuição• Existe uma partição do fluxo por várias rotas• Os flows nas várias rotas são lineares nessa partição• O custo total é concavo nessa partição
E se a função custo for convexa? • Existe um incentivo para deseconomias e para dividir o fluxo por
várias rotas• No caso de uma origem e um destino com várias rotas e funções
custo iguais para cada rota então prova-se que a solução óptima é dividir o fluxo igualmente por todas as rotas
76Métodos de Análise de Sistemas Produtivos
MASP
cont
Sensibilidade a mudanças de condições• Com deseconomias um melhoramento de uma das rotas leva a
uma pequena mudança da distribuição do fluxo óptimo
• Com economias a distribuição do fluxo óptimo ou se mantémou muda de uma quantidade discreta
- típico de problemas de minimização com funções concavas –pequenas mudanças nos dados podem levar a grandes mudançasna solução óptima
- Felizmente o custo não se comporta dessa maneira
ExemploIf z3 ≤ [2-sqrt(2)] then (x* =1 ∧ Custo total = 8)
else (x* =0 ∧ Custo total = sqrt(8)+4 z3)
77Métodos de Análise de Sistemas Produtivos
MASP
Métodos de solução
Redes com economias versus redes com deseconomias• Natureza da solução é diferente
• Método de solução tem que ser diferente- deseconomias – problema de optimização bem comportado- Economias – problema de optimização com mínimos locais que
podem não ser globais
Métodos de pesquisa local- Utilizados para encontrar soluções quase-óptimas para grandes
redes com custos convexos- No caso das redes de custo concavo estes mesmos métodos
podem falhar e como tal só funcionam para redes de dimensõesmais baixas
78Métodos de Análise de Sistemas Produtivos
MASP
cont
Métodos de pesquisa local
(bons para casos convexos)1. Determina uma solução inicial
admissível
2. Determina uma pequenaperturbação da solução anterior que melhore o custo
3. Se não melhora pára e o mínimofoi encontrado senão Volta a 2
Exemplo para função concava• Mínimos locais x = 0; x =1
• Se solução inicial < .61 converge para 0
• Exponencial
Parte 2Network flow problems
80Métodos de Análise de Sistemas Produtivos
MASP
Capítulos 3 e 4 Network flows
A matéria deste slide não será objecto de avaliação
Análise de complexidade
Desenvolvimento de algoritmos polinomiais
Algoritmos de pesquisa local
Algoritmos de decomposição de fluxo
Árvore de caminhos mais curtos
Caminho mais curto em redes acíclicas
Algoritmo de Dijkstra