Baixe o app para aproveitar ainda mais
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.
Compartilhar