Baixe o app para aproveitar ainda mais
Prévia do material em texto
PESQUISA OPERACIONAL DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS MATEMÁTICOS POR MEIO DA LINGUAGEM GAMS UNESP Aneirson Francisco da Silva- Doutor Em Engenharia de Produção na linha de { Gestão e Otimização-Pesquisa Operacional) FEG-UNESP-2013 Mestre em Engenharia de Produção-UNIFEI-2009 Prefácio Dedico esse trabalho A minha família, pela dedicação e pelo apoio durante toda minha formação, em especial para aos meus avós (in memoriam) Manuel Francisco da Silva e Maria Batista. Bons livros são capazes de mudar Nossos destinos “Allan Kardec” Apresentação Este livro teve como objetivo fornecer conceitos matemáticos sobre a linguagem de modelagem General Algebraic Modeling System – GAMS. A estrutura deste livro está constituída primeiramente pela revisão da história da Pesquisa Operacional, e em seguida uma explanação a respeito dos modelos lineares, iniciando pelas particularidades desse modelo, teoria de redes e DEA. Também são abordados modelos de otimização combinatória. Sumário Capítulo 1: Introdução à Pesquisa Operacional ..................................................................6 Capítulo 2: Estruturação de Modelos Lineares....................................................................11 Capítulo 3: Otimização de Problemas Reais .......................................................................23 Capítulo 4: Modelos Multiperíodos ........................................................................................33 Capítulo 5: Modelos Inteiros....................................................................................................40 Capítulo 6: Otimização em Redes e Grafos ........................................................................45 Capítulo 7: Otimização combinatória ..................................................................................55 Capítulo 8: Análise por Envoltória de Dados .......................................................................63 Capítulo 10: Otimização Estocástica ....................................................................................94 Capítulo 11: Otimização Multiobjetivo .................................................................................96 Capítulo 12: Otimização Quadrática .................................................................................102 6 Capítulo 1: Introdução à Pesquisa Operacional 1. A evolução da pesquisa operacional O termo Pesquisa Operacional “PO” foi empregado pela primeira vez em 1939. A partir de individualizada e batizada, tornou-se possível fixar suas origens em épocas remotas da história da ciência e da sociedade. 1.1. O método da pesquisa operacional A experimentação tomada no sentido restrito - isto é, a manipulação física das variáveis - é geralmente impossível ou impraticável quando se lida com organizações governamentais, militares ou industriais. Apesar disso, a experimentação é às vezes possível, particularmente no caso de subsistemas, e desempenha papel importante na PO. Na maioria das vezes, entretanto, o sistema global em estudo não pode ser submetido a um tratamento desta natureza. Quem trabalha em pesquisa operacional é geralmente obrigado a construir representações do sistema e do seu comportamento para se orientar durante a pesquisa. Os modelos em PO assumem a forma de uma ou mais equações ou inequações para traduzir a condição de que algumas, ou todas as variações controladas só podem ser manipuladas dentro de limites. O conjunto destas equações constitui, ao mesmo tempo, um modelo de sistema e um modelo de decisão. A solução pode ser extraída do modelo mediante experimentação (isto é, por simulação) ou mediante análise matemática. Para alguns tipos de função f (por exemplo, relações algébricas elementares), desde que as restrições não sejam numerosas, a matemática clássica fornece instrumentos perfeitamente adequados para a determinação dos melhores valores das variáveis controladas. Por outro lado, a função f pode consistir em um conjunto de regras de cálculo (um algoritmo) que nos permita medir a utilidade (U) do desempenho para qualquer conjunto de valores das variáveis controladas e não controladas. Em alguns casos o comportamento do elemento humano que toma a decisão não pode ser representado no modelo. Ocorre a necessidade do uso de simulações que envolverão a participação de seres humanos, sendo denominados jogos de operações. A otimização, portanto, produz a melhor solução para o problema que foi modelado. 7 A correspondência entre modelo e realidade terá de ser aferida (testada) e a solução avaliada. Isto é, teremos de comparar seu desempenho com o da política ou procedimento que ela irá substituir. Os resultados da pesquisa devem ser implantados. É nesta fase que se faz o teste e a avaliação final da pesquisa; proporcionando, pois, ao especialista as maiores e melhores oportunidades de aprender. Cinco fases num projeto de PO: 1. Formulação do problema; 2. Construção do modelo; 3. Obtenção da solução; 4. Teste do modelo e avaliação da solução; 5. Implantação e acompanhamento da solução (manutenção). As vantagens e desvantagens da utilização de modelos foram assim definidas: Vantagens a) Emerge sob a forma gráfica, para representar a realidade aprendida em determinado momento; b) Simplifica a visualização da amplitude das variáveis sem alterar a essência; c) Ajuda a identificar várias relações possíveis entre os elementos da realidade; d) Possibilita compreender relações complexas; e) Serve como base para estabelecer e aprimorar parâmetros. Desvantagens f) Limitações na identificação de todas as variáveis relevantes que influenciam em determinada situação; g) Problemas na definição das propriedades a serem mensuradas e na especificação de procedimentos para tal; h) Dificuldades no entendimento entre os provedores e os usuários da informação. 8 A representação simplificada de um problema prático por meio de um modelo matemático permite que sobre ele se aplique técnicas e métodos que facilitam a obtenção de uma solução. 1.2. O impacto da pesquisa operacional A Pesquisa Operacional tem tido um grande impacto crescente na administração de empresas nos anos recentes. Tanto o número quanto a variedade de suas aplicações continuam a crescer rapidamente. Algumas de suas técnicas envolvem ide ias sofisticadas em ciências políticas, matemática, economia, teoria da probabilidade e estatística. Como também sendo usada amplamente em outros tipos de organizações, inclusive negócios e indústria. Muitas indústrias, inclusive a de aviação e mísseis, automóveis, comunicações, computadores, energia elétrica, eletrônica, alimentos, metalúrgica, mineração, papel, petróleo e transporte, têm feito uso extensivo da pesquisa operacional. Mesmo instituições financeiras, agências governamentais e hospitais têm aumentado rapidamente o uso que fazem da pesquisa operacional. Vejamos alguns dos problemas que têm sido resolvidos por técnicas particulares de pesquisa operacional: Programação Linear: tem sido usada com sucesso na solução de problemas relativos à alocação de pessoal, mistura de materiais, distribuição, transporte, carteira de investimento, avaliação da eficiência; Programação Dinâmica: tem sido aplicada também com sucesso a áreas como planejamento de despesas de publicidade, distribuição do esforço de vendas e programação de produção; Teoria das Filas: tem tido aplicação na solução de problemas relativos a congestionamento de tráfego, máquinas de serviços sujeitas à quebra, determinação do nível de uma força de serviço, programação do tráfego aéreo, projetos de represas, programação deprodução e operação de hospitais; Programação Inteira: que é uma forma de programação linear onde as variáveis podem apenas apresentar números inteiros. Tem sido utilizada na resolução de problemas de investimento dentre outros; 9 Programação linear mista: que é uma forma de programação linear onde as variáveis podem assumir valores binários, inteiros e contínuos, este modelo também é definido como otimização combinatória, enquadrando-se em problemas de dificuldades não polinomiais NP-HARD; Programação Não Linear: modelo matemático onde a função objetivo, as restrições ou ambas, apresentam não linearidade em seus coeficientes. Programação Multiobjetivo: é uma forma de programação linear e não linear onde se analisa múltiplas funções objetivos; Goal Programming: é uma extensão dos modelos de programação multiobjetivo, contendo vários modelos específicos para cada problema de decisão. Outras técnicas de pesquisa operacional, tais como teoria de estoque, teoria dos jogos, teoria dos grafos e simulação, também tem sido aplicadas com sucesso a(em) diversos contextos. REFERÊNCIAS BANKS, J.; CARSON, J. S.; NELSON, B. L.; NICOL, D. M. (2005). Discrete-event system simulation. 4th ed. New Jersey: Prentice Hall. 608 p. ISBN 0-13-144679-7. CLÍMACO, J. N.; ANTUNES, C. H.;ALVES,M. J. G – Programação Linear Multiobjetiva: Do Modelo de Programação Linear Clássico à Consideração Explícita de Várias Funções Objectivos. Imprensa da Universidade de Coimbra, 2003 CHANG, C.T. Multi-Choice goal programming. The International Journal of Management Science, v.35, p. 389-396, 2007. CHARNES, A., and COOPER, W.W., Goal Programming and Multiple Objective Optimizations. European Journal of operations Research, v.1, p. 39-54, 1977. GOLDBARG, M. C. & LUNA, H. P. L. Otimização combinatória e programação linear: Modelos e algoritmos. Rio de Janeiro: Campus, 2005. IGNIZIO, J.P., Introduction to Linear Goal Programming. A Sage University Paper, Englewood Cliffs, New Jersey, 1985. LAW, A. M.; KELTON, W. D. Simulation modeling and analysis. 3.ed. New York: McGraw-Hill, 2000. 10 LUCE, R. D; RAIFFA, H. Games and Decision: Introduction and Critical Survey. New York: John Wiley, 1957. MIRRAZAVI S. V ; JONES, F.J e TAMIZ. M . A comparison of genetic and conventional methods for the solution of integer goal programmes. European Journal of Operational Research, v.132. p. 594- 602, 2001. MONTEVECHI, J. A. B., PINHO, A. F. de, FABIANO, L., & MARINS, F. A. S. Application of design of experiments on the simulation of a process in an automotive industry. Proceedings of the 2007 Winter Simulation Conference, 2007. POWELL. J.G e PREMACHANDRA I.M. Accommodating diverse institucional investment objectives and constraints using non-linear goal programming. European Journal of Operational Research, v.105, p. 447-456, 1998. 11 Capítulo 2: Estruturação de Modelos Lineares 2. Estruturação e otimização de modelos lineares estacionários O anexo A contempla a linguagem de modelagem GAMS. Abordando as principais funções e a estrutura dessa linguagem de modelagem, mostrando suas principais vantagens. O anexo B contempla as principais linguagens de modelagens, abordando as principais vantagens da linguagem GAMS em relação às demais linguagens. Vamos iniciar a modelagem do problema do Giapetto pela linguagem GAMS. A linguagem GAMS requer que o problema seja traduzido na forma algorítmica. 1- Giapetto fabrica dois tipos de brinquedos de madeira. Soldados e trens. Um soldado é vendido por R$ 27,00 e usa R$ 10,00 de matéria prima. Cada soldado que é fabricado tem um custo adicional de R$ 14,00 relativo à mão de obra. Um trem é vendido por R$ 21,00 e gasta R$ 90,00. O custo de mão de obra adicional para cada trem é de R$ 10,00. A fabricação destes brinquedos requer dois tipos de mão de obra: Carpintaria e Acabamento. Um soldado necessita de 2 horas para acabamento e 1 para carpintaria. Um trem necessita de 1 hora para acabamento e 1 hora de carpintaria. Cada semana, Giapetto pode obter qualquer quantidade de matéria prima, mas tem a disposição até 100 horas de acabamento e 80 de carpintaria. A demanda por trens é ilimitada, mas a venda de soldados é de no máximo 40 por semana. Giapetto quer maximizar seu lucro diário. Formular o modelo matemático que poderia ser usado por Giapetto para maximizar seu lucro semanal. 1 passo: Modelar o problema. Vamos descrever as variáveis do problema, o que na linguagem GAMS é chamada de (SETS ) numa tradução pode-se chamar de índices ou conjuntos. Índices: Xi: Quantidade a ser produzida do produto i. O GAMS é um software orientado ao objeto, logo temos que declarar esses objetos que no caso são os i produtos e os j recursos. Estruturação e otimização de modelos lineares estacionários________________________________ 12 12 2 passo: Definir os parâmetros (PARAMETER) do modelo: Neste caso sabemos a margem de contribuição unitária por produto i. Portanto, é necessário esse parâmetro que estará ligado ao índice i. Vamos chamar este parâmetro de MCi. Outro parâmetro é com relação à disponibilidade dos recursos, sendo este parâmetro ligado ao índice j. Vamos chamar este parâmetro de Aj. Finalmente, devemos criar um parâmetro que mostre o consumo unitário de cada recurso por produto, sendo este parâmetro pertencente aos índices i e j. Neste caso na linguagem GAMS deve ser criado uma Tabela (TABLE), que vamos chamar de R i, j. 3 passo: Definir as variáveis de decisão: Temos uma decisão que é saber o valor da margem de contribuição, vamos definir essa variável de Xi. Na linguagem GAMS é necessário informar uma variável que vai definir a função objetivo, neste caso chamaremos de Z, que vai definir os valores ótimos de produção de cada produto. 4 passo: Definir as equações (EQUATIONS): as equações são definidas por meio do número de restrições mais a função objetivo. A primeira equação vai definir o valor da margem de contribuição, portanto chamaremos a mesma de margem. A segunda equação vai determinar o quanto será consumido por recurso j vamos chamar essa equação de consumo. E a última equação definirá o limite máximo de demanda do produto soldado. Agora podemos resolver o problema do Amigo Giapetto. IiiX SOLDADOX Jj Ii jAiXijR Ii iXiMCMax 0 40"" . :asujeito . Z A Tabela 2.1 mostra alguns comandos básicos da linguagem GAMS Estruturação e otimização de modelos lineares estacionários________________________________ 13 13 Símbolo Significado G Define uma inequação de sinal maior ou igual L Define uma inequação de sinal de menor ou igual E Define uma equação (X= n) “ São fixadores de índices ‘ Também é um fixador de índices PROD Expressão para produto de uma série SUM Expressão para somatório Model Descreve o modelo estudado Solve Descreve a utilização de um solver específico Display Recurso utilizado para calcular o primal e o dual A Tabela 2.2 mostra as funções padrão de GAMS. Tabela 2.2- Funções padrão em GAMS Nome Descrição Definição Número de Argumentos ABS Valor absoluto |ARG| 1 ARCTAN Arco Tangente Arctan (arg); resultado em radianos 1 CEIL Função teto Maior inteiro ≥ arg 1 COS Cosseno Cos (arg) argumento em radianos 1 ERRORF Função erro Integral de distribuição normal padrão 1 EXP Exponencial earg 1 FLOOR Função piso Maior inteiro ≤ arg 1 LOG Logaritmo natural Log do arg na base e 1 Log10 Logaritmo Log de arg na base 10 1 Estruturação e otimização de modelos lineares estacionários________________________________ 14 14 Nome Descrição Definição Número de Argumentos comum MAPVAL Função mapeamento Atribuiu númerosa valores especiais 1 MAX Maior valor Max (arg1, arg2,...,argn) >1 MIN Menor valor Min (arg1, arg2,..,argn) >1 MOD Resto arg1-trunc(arg1/arg2) x arg3 2 Normal Randômica normal Número aleatório distribuído normalmente com argumento arg1 e desvio padrão arg2 2* POWER Potência inteira ROUND Arredondamento SIGN Sinal SIN Seno Sem (arg); arg em radianos SQR Quadrado arg x arg 1 SQRT Raiz quadrada 1 TRUNC Truncamento Sign (arg) x floor (abs(arg)) 1 UNIFORM Randômica uniforme Número aleatório distribuído uniformemente entre arg1 e arg2 2* A Figura 1.1 mostra os processos para obtenção do modelo do Giapetto em linguagem GAMS. Clicando em F9 é obtido a solução para este modelo. A solução ótima para este modelo seria. Produzir 20 soldados e 60 trens gerando um lucro máximo de R$ 180,00 reais. O GAMS oferece algumas estatísticas referentes ao tamanho do modelo, como se pode ver abaixo no caso do modelo Giapetto. As contagens de “BLOCKS” se refere ao número de equações genéricas e variáveis. As contagens de “SINGLE” se refere as linhas e colunas individuais que estão sendo Estruturação e otimização de modelos lineares estacionários________________________________ 15 15 geradas na instancia particular do modelo. Para os modelos não lineares, são fornecidas outras estatísticas para descrever o grau de não linearidade do problema (BROOKE et al., 1997). Estruturação e otimização de modelos lineares estacionários________________________________ 16 16 Figura 1.1- Modelo Giapetto em linguagem GAMS. 2- O Senhor Martins é dono de uma oficina muito movimentada na cidade de Guaratinguetá- SP. Ele querendo maximizar seus retornos e também, visando à realização de novos investimentos na sua oficina. Resolveu procurar você/SA, para fazer um planejamento da sua produção, visando à maximização do lucro, e identificar possíveis áreas para realização de novos investimentos. Os dados da empresa estão logo abaixo: Tipo de Máquina Produto 1 Produto 2 Produto 3 Tempo disponível Torno 5 3 5 400 Fresa 8 4 0 500 Furadeira 2 5 3 300 Lucro 20 15 18 Demanda Semanal máxima 40 50 20 Uma oficina mecânica deseja alocar o tempo ocioso disponível em suas máquinas para a produção de três produtos. A Tabela abaixo mostra as informações sobre as necessidades de horas de máquina para produzir uma unidade de cada produto, assim como a disponibilidade das máquinas, o lucro dos produtos e a demanda máxima existente no mercado. Deseja-se o esquema semanal de produção de lucro máximo. Resolvendo o exemplo do senhor Martins. 1 passo: Descrever os índices e conjuntos: i, j Os objetos são os i produtos e j recursos 2 passo: Descrever os parâmetros. Ri, j: Consumo unitários por produto i de cada recurso j. Aj: Quantidade disponível do recurso j. Estruturação e otimização de modelos lineares estacionários________________________________ 17 17 Di: Demanda máxima por produto i. Li: Lucro unitário por produto i. 3 passo: Descrever as variáveis de decisão. Xi: Define a produção do produto i. Z: Expressão da função objetivo. 4 passo: Descrever as equações. 5 passo: Construção do modelo matemático. IiiX iDiX JjjAijR Ii iX Ii iXiL ,0 :asujeito Max Z Estruturação e otimização de modelos lineares estacionários________________________________ 18 18 Figura 1.2: Modelo matemático exemplo 2 em linguagem GAMS. Solução ótima: Produzir 40 unidades do produto 1, 32 unidades do produto 2 e 20 unidades do produto 3. Gerando um lucro máximo de R$ 1.640,00. Solução Dual: Produto 1 R$ 14,00, produto 3 R$ 9,00 e Furadeira R$ 3,00. Interpretação econômica do dual. Se a oficina aumentasse a demanda do produto 1 em uma unidade o lucro aumentaria em R$ 14,00. Se a usina aumentasse a demanda em uma unidade do produto 2, o lucro aumentaria em R$ 9,00. Se o tempo disponível de utilização da furadeira fosse aumentada em uma hora o lucro aumentaria em R$ 3,00. Estruturação e otimização de modelos lineares estacionários________________________________ 19 19 Problemas propostos 1 – Uma indústria fabrica dois tipos de papel e para isso utiliza somente uma máquina. Devido a certas restrições de matéria prima, não se pode diariamente produzir mais do que 4 tons de papel do tipo A, nem mais do que 6 tons do tipo B. Requer-se 1 hora da máquina para produzir 1 ton. de papel do tipo A e 1 hora para produzir 1 ton. de papel do tipo B. O lucro por ton. produzida é de R$ 2,00 para o papel do tipo A e de R$ 5,00 para o papel do tipo B. O tempo de utilização da máquina é de 8 horas/dia. Elaborar o plano ótimo de produção. 2 – Uma pequena indústria usa três tipos de matérias primas, P, Q, R para a fabricação de dois produtos A e B. As matérias primas em disponibilidade na fábrica são: 20 unidades de P; 12 unidades de Q; e 16 unidades de R. Por razões tecnológicas, uma unidade do produto A necessita respectivamente de 2, 2 e 4 unidades de matérias primas P, Q e R. Para o produto B esses coeficientes técnicos são 4, 2 e 0, respectivamente. O fabricante sabe que o lucro na produção de A é de 0,5 unidades monetárias e de B é de 1 unidade monetária. Qual o lucro máximo e quais as quantidades produzidas das mercadorias A e B para se obter o lucro máximo? 3 – Uma companhia de investimento dispõe de R$ 100.000,00 para investir em ações e letras imobiliárias. Sua política de aplicação consiste em: Empregar, no máximo, 50% do disponível em ações; e Empregar, no máximo, 60% do disponível em letras imobiliárias. Através de uma pesquisa de mercado, a companhia verificou que deveria empregar, no máximo, 40% do disponível, na diferença entre o dobro da quantidade investida em ações e a quantidade investida em letras; e empregar, no máximo, 1% do disponível na soma da oitava parte investida em ações com a quinta parte investida em letras. Estruturação e otimização de modelos lineares estacionários________________________________ 20 20 As ações produzem uma rentabilidade de 5% ao mês e as letras 4% ao mês. Qual o investimento ótimo? 4 – Uma fábrica de canetas quer saber do Departamento de Engenharia quantas canetas de cada tipo (standard, luxo e esferográfica) deverão ser produzidas, para que o lucro da empresa seja máximo. INFORMAÇÕES: a) Do departamento de Produção Produções máximas mensais possíveis para cada um dos tipos de canetas (isto é, produzir-se só um tipo): Standard 15.000 Luxo 10.000 Esferográfica 20.000 b) Do Departamento de Vendas Máximo de vendas mensais para cada um dos tipos: Standard 12.000 Luxo 8.000 Esferográfica 30.000 c) Do Departamento de Contabilidade Lucro unitário para cada tipo: Standard R$ 0,70 Luxo R$ 0,50 Esferográfica R$ 0,30 5 – Uma fábrica de automóveis e caminhões possui os seguintes departamentos; 1. Estamparia de pranchas metálicas; 2. Montagem de motores; 3. Montagem de automóveis; e 4. Montagem de caminhões. Estruturação e otimização de modelos lineares estacionários________________________________ 2121 O departamento 1 deve estampar, no mínimo por mês, as pranchas necessárias para 25.000 automóveis ou 35.000 caminhões, ou as correspondentes combinações de automóveis e caminhões. O departamento 2 deve no mínimo por mês, montar 33.333 motores de automóveis e 16.667 motores de caminhões ou as correspondentes combinações de motores de automóvel e caminhão. O departamento 3 pode montar e terminar 40.000 automóveis e o departamento 4, mensalmente 25.000 caminhões (ambos utilizando sua capacidade máxima). Com o constante aumento do combustível, a fábrica sabe que o prejuízo na fabricação de um automóvel é de R$ 500,00 e na fabricação de um caminhão é de R$ 200,00. Qual a quantidade de automóveis e caminhões a ser produzida a fim de que a fábrica tenha o menor prejuízo possível, dadas as condições atuais do mercado? 6 – Um vendedor de frutas pode transportar 800 caixas de frutas para sua região de vendas. Ele necessita transportar 200 caixas com laranjas, tendo um lucro de 20 u.m. por caixa, pelo menos 100 caixas com pêssegos a 10 u.m. de lucro por caixa e no máximo 200 caixas com tangerinas a 30 u.m de lucro por caixa. Construir o modelo matemático que permita ao vendedor carregar o caminhão de modo a obter o lucro máximo. 7 – Um fazendeiro está estudando a divisão de sua propriedade nas seguintes atividades produtivas. A (Arrendamento) – Destinar certa quantidade de alqueires para a plantação de cana de açúcar, a uma usina local, que se encarrega da atividade e paga pelo aluguel da terra $ 300,00 por alqueire por ano. P (Pecuária) – Usar outra parte para criação de gado de corte. A recuperação das pastagens requer adubação (100 kg / Alq) e irrigação (100.000 l de água / Alq) por ano. O lucro estimado nessa atividade é de $ 400,00 / Alq no ano. S (Plantio de Soja) – Usar uma terceira parte para o plantio de soja. Essa cultura requer 200 kg por alqueire de adubos e 200.000 l de água / Alq para irrigação por ano. O lucro estimado nessa atividade é de $ 500,00 por alqueire no ano. Disponibilidade de recursos por ano: 12.750.000 l de água; 14.000 kg de adubo; e 100 alqueires de terra. Quanto alqueire deverá destinar a cada atividade para proporcionar o melhor retorno? Estruturação e otimização de modelos lineares estacionários________________________________ 22 22 REFERÊNCIAS ANDRADE, E. L. Introdução à Pesquisa Operacional. LTC, Rio de Janeiro, Brasil, 2004. BROOKE, A.; KENDRICK, D. & MEERAUS, A. GAMS: Sistema geral de modelagem algébrica. São Paulo: Edgard Blücher, 1997. CAIXETA-FILHO, J. V . Pesquisa Operacional: Técnicas de otimização em aplicadas a sistemas agroindustriais. 2º .ed. – São Paulo: Atlas, 2004. COLIN, E.C. Pesquisa Operacional: 170 aplicações em Estratégia, Finanças, Logística, Produção, Marketing e Vendas. Rio de Janeiro LTC, 2007. LACHTERMACHER, G. pesquisa operacional na tomada de decisão: Modelagem em Excel. 2º ed.- Rio de Janeiro: Elsevier, 2004. LINS, M .P. E; CALÔBA, G.M. Programação Linear: com aplicações em teoria dos jogos e avaliação de desempenho (Data Envelopment Analysis). Rio de Janeiro; Interciência - 2006. GOLDBARG, M. C; LUNA, H. P. L. Otimização combinatória e programação linear: Modelos e algoritmos. Rio de Janeiro: Campus, 2005. 23 Capítulo 3: Otimização de Problemas Reais 3. Desenvolvimento e otimização de problemas reais por meio do GAMS É comum durante o desenvolvimento de modelos matemáticos nos depararmos com problemas onde há limites de demanda para determinados produtos. Como exemplo, iremos modelar um problema em linguagem GAMS. Os dados estão dispostos abaixo. O Quadro 3.1 refere-se aos recursos disponíveis na fazenda para realização das atividades leiteiras e de corte. Quadro 3.1- Recursos disponíveis Abreviatura RESTRIÇÕES AT Área total disponível para a atividade leiteira – ha/ano TR Custo da terra (devendo ser considerado o custo de oportunidade e o custo de manutenção – adubação, reforma de pasto, limpeza e destoca) – R$/ano BE Custo e despesas com benfeitorias (considerando-se a depreciação, o custo de oportunidade e o custo de manutenção) – R$/ano MI Custo e despesas com máquinas e implementos (considerando-se a depreciação, o custo de oportunidade e o custo de manutenção) – R$/ano EQ Custo e despesas com equipamentos (considerando-se a depreciação, o custo de oportunidade e o custo de manutenção) – R$/ano RE Custo e despesas com reprodutores (considerando-se a depreciação e o custo de oportunidade) – R$/ano AL Custo e despesas com alimentação (considerando-se o gasto com concentrados, suplementos e forrageiras e o custo alternativo) – R$/ano PV Custo e despesas com produtos veterinários (considerando-se o gasto e o custo alternativo) – R$/ano IA Custo e despesas com inseminação artificial (considerando-se o gasto e o custo alternativo) – R$/ano TE Custo e despesas com transferência de embriões (considerando-se o gasto e o custo alternativo) – R$/ano DA Gastos com despesas administrativas (considerando-se também o custo alternativo) – R$/ano MK Gastos com marketing e propaganda (considerando-se também o custo alternativo) – R$/ano MO Custo e despesas com mão-de-obra (considerando-se o gasto efetivo, os encargos pagos e o custo alternativo) – R$/ano A Tabela 3.1 mostra os recursos disponíveis e o consumo por categoria de animal para o ano de 2004. Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 24 24 Tabela 3.1- Consumo anual por animal. Restrições Recursos disponíveis Unidades RECURSOS CONSUMIDOS POR CATEGORIA Bezerras Bezerros Novilhas Vacas Touro AT 196,50 ha/ano 0,09 0,09 0,25 0,35 0,42 TR 39.493,39 R$/ano 43,37 32,81 66,12 88,78 1535,85 BE 9.894,38 R$/ano 4,07 3,08 3,16 68,26 10,99 MI 51.601,87 R$/ano 70,83 53,59 45,25 276,01 57,34 EQ 13.605,94 R$/ano 3,73 2,83 2,17 99,14 15,12 RE 2.432,04 R$/ano 10,35 7,83 6,59 0,94 0,00 AL 235.063,69 R$/ano 161,32 122,07 393,56 1239,10 261,18 PV 19.243,82 R$/ano 42,26 31,98 27,62 73,10 21,38 IA 3.923,65 R$/ano 16,69 12,63 10,64 1,52 0,00 TE 7.240,00 R$/ano 30,81 23,31 19,63 2,81 0,00 DA 35.535,30 R$/ano 34,14 25,83 19,83 214,86 78,97 MK 18.089,05 R$/ano 69,52 52,60 51,92 5,61 80,40 MO 51.729,07 R$/ano 42,60 32,23 28,87 316,79 114,95 RO Orçamento disponível: R$ 487.852,20 Essa Tabela foi obtida por meio de rateio, considerando o consumo efetivo de recursos e o tempo de permanência de cada categoria animal na propriedade. Para garantir a sustentabilidade econômica da produção de leite e da produção animais da Fazenda , foram inseridas restrições adicionais as quantidades máximas e mínimas que cada categoria animal deveria possuir, conforme apresentado na Tabela 3,2. Esses valores são baseados na taxa de lotação histórica da fazenda no ano de 2003. Tabela 3.2- Categorias de animais Categoria Qtde Máxima Qtde Mínima X1 95 39 X2 135 53 X3 170 60 X4 200 100 X5 12 - O orçamento disponível é de R$ 487.852,20. O objetivo é maximizar a quantidade de animais. Formule o modelo utilizando-se da linguagem GAMS. Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 25 25 Índices: i associado às categorias de animais, iI, I= {Bezerras, Bezerros, Novilhas, Vacas e Touros}. j associado às categorias dos recursos, jJ, J= {AT, TR, BE, MI, EQ, RE, AL, PV, IA, TE, DA, MK, MO,RO}. Parâmetros: Pj: associado ao índice j define os limites máximos de cada recurso. Ri, j: associado ao consumo unitário do recurso j por categoria de animal i. D2i: demanda mínima por categoria de animal i. Di: demanda máxima por categoria de animal i. Variáveis: Xi: Quantidade por categoria de animal. Z: Associada ao cálculo da função objetivo. Vamos introduzir outrocomando na linguagem GAMS denominado SCALAR neste caso esse comando vai representar uma constante que não está ligado a nenhum índice. IiIiX IiiDiX IiiDiX JjjP Ii iXjiR n i iX 2 :a sujeito Max Z Para este modelo temos um problema de programação inteira. Este assunto será discutido nos próximos capítulos. Portanto, resolveremos o mesmo por meio da otimização linear tradicional. A Figura 3.1 mostra o modelo em linguagem GAMS. A solução ótima não inteira seria: bezerras= 39, bezerros= 132,33, novilhas= 132,172, vacas= 127,773 e touro= 8,71. Utilizando 486.350,05 do orçamento. Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 26 26 Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 27 27 Figura 3.1- Modelo agricultura em GAMS. As ( ‘ ) e as( “ ) são indexadores de índices na linguagem GAMS. Exemplo 4: Alocação de tarefas. Uma empresa de correios deseja estabelecer o número de funcionários de horários integral que deve contratar para iniciar suas atividades. Para fazê-lo, recebeu uma matriz da empresa com o número mínimo de funcionários por dia da semana. Estas informações se encontram na Tabela 3.3. O sindicato dos empregados de franqueadores dos correios mantém um acordo sindical que determina que cada empregado deve trabalhar cinco dias consecutivos e folgar em seguida dois dias, e que as franquias devem ter apenas empregados com horário integral. Desenvolva e otimize o modelo de maneira a determinar o número total de empregados que a franquia deve contratar e o número de empregados por dia, utilizando a linguagem de modelagem GAMS. Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 28 28 Tabela 3.3- Dados do problema da empresa correios. Dia da semana Número de funcionários Domingo 11 Segunda-feira 18 Terça-feira 12 Quarta-feira 15 Quinta-feira 19 Sexta-feira 14 Sábado 16 Figura 3.2- Modelo correios pelo GAMS. Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 29 29 Exemplo de decisão entre fazer ou comprar: A turbo motores LTDA, uma fábrica de motores especiais, recebeu recentemente R$ 100.000,00 em pedidos de seus três tipos de motores. Cada motor necessita de um determinado número de horas de trabalho no setor de montagem e acabamento. A turbo motores deseja determinar quantos motores devem ser produzidos em sua fábrica e quantos devem ser produzidos de forma terceirizada para atender à demanda de pedidos. A Tabela 3.4 mostra as informações referentes a esta empresa. Tabela 3.4- Dados da empresa turbo motores. Modelo 1 2 3 Disponibilidade Demanda 3000 unid 2500 unid 550 unid Montagem 1 h/unid 2h/unid 0,5 h/unid 6000 h Acabamento 2.5 h/unid 1h/unid 4h/unid 10000h Custo de produção R$ 50 R$ 90 R$ 120 Terceirização R$ 65 R$ 92 R$ 140 Índices: p: associado à produção, p P, P= {1,2,3}. j: associado aos recursos j J, J= {Montagem, acabamento}. Parâmetros: Aj: associado à disponibilidade dos recursos j. Produzirp,: associado ao consumo da recurso j pelo produto p. Custop: associado ao custo de produção do produto p. Cusp: associado ao custo de terceirização. Cp j define o quanto o produto p utiliza do recurso j. demandap,: associado a decisão unitária de produção e terceirização. Variáveis. Xp: quantidade a ser fabricada do produto p. Yp: quantidade a ser terceirizada do produto p. Modelo matemático: Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 30 30 ,, :aSujeito pcustoMin Z IpYIpX JjjA Pp jpCpX pDemandapYpX Pp pCuspY Pp pX A figura 3.3 resume o desenvolvimento desse modelo em GAMS. Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 31 31 Figura 3.3- Modelo de decisão de compra ou terceirização em GAMS Solução ótima: Produzir P1=3.000; P2= 500; P3= 500, terceirizando a produção de P2= 2.000. Gerando um custo mínimo= R$ 43.900,00. REFERÊNCIAS ANDRADE, E. L. Introdução à Pesquisa Operacional. LTC, Rio de Janeiro, Brasil, 2004. BROOKE, A.; KENDRICK, D. & MEERAUS, A. GAMS: Sistema geral de modelagem algébrica. São Paulo: Edgard Blücher, 1997. Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 32 32 CAIXETA-FILHO, J. V . Pesquisa Operacional: Técnicas de otimização em aplicadas a sistemas agroindustriais. 2º .ed. – São Paulo: Atlas, 2004. COLIN, E.C. Pesquisa Operacional: 170 aplicações em Estratégia, Finanças, Logística, Produção, Marketing e Vendas. Rio de Janeiro LTC, 2007. LACHTERMACHER, G. pesquisa operacional na tomada de decisão: Modelagem em Excel. 2º ed.- Rio de Janeiro: Elsevier, 2004. LINS, M .P. E; CALÔBA, G.M. Programação Linear: com aplicações em teoria dos jogos e avaliação de desempenho (Data Envelopment Analysis). Rio de Janeiro; Interciência - 2006. MEDEIROS, A. L. ; MONTEVECHI, J. A. B. ; TURRIONI, J. B. ; SILVA, L.B ; MENDES, L. Otimização do planejamento produtivo a partir da programação linear: uma aplicação na pecuária leiteira.. In: XI SIMPEP - Simpósio de Engenharia de Produção. Anais do XI Simpósio de Engenharia de Produção. Bauru : FEB/UNESP, 2004. GOLDBARG, M. C; LUNA, H. P. L. Otimização combinatória e programação linear: Modelos e algoritmos. Rio de Janeiro: Campus, 2005. SHIMIZU, T. Decisão nas organizações: introdução aos problemas de decisão encontrados nas organizações e nos sistemas de apoio à decisão. São Paulo: Atlas, 2010. Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 33 33 Capítulo 4: Modelos Multiperíodos 4. Desenvolvimento e otimização de modelos multiperíodo por meio do GAMS A maioria dos problemas de otimização práticos são multiperíodo, e neste caso o modelo matemático torna-se mais complexo. Resolvamos o problema de estoque: Uma empresa de barcos precisa determinar quantos veleiros devem ser produzidos durante cada um dos 4 próximos trimestres. A demanda de cada um dos trimestres é: primeiro trimestre, 40 veleiros; segundo trimestre, 60 veleiros, terceiro trimestre, 75 veleiros, quarto trimestre, 25 veleiros. A empresa quer atender a demanda prontamente. No início do primeiro trimestre, a empresa tem 10 veleiros em estoque. No início de cada trimestre, a empresa precisa decidir quantos veleiros devem ser produzidos durante o trimestre. Por simplicidade, assume-se que os veleiros são fabricados durante um trimestre podem ser usados para atender a demanda deste trimestre. Durante cada trimestre, a empresa pode produzir até 40 veleiros com sua mão de obra regular a um custo de R$ 400,00 por veleiros. Tendo de trabalhar com horas extras durante o trimestre, a empresa pode produzir veleiros a mais a um custo total de R$ 450,00 por barco. No final de cada trimestre após ter ocorrido a produção e a demanda do trimestre ter sido atendida, um custo de transporte ou armazenagem de R$ 20,00 por barco ocorre. Desenvolva o modelo matemático por meio do software GAMS. Solução: Índices j Períodos, j J; Conjuntos J Conjunto associado aos períodos {1, 2,...,4}; Parâmetros aj Custo de produção em horas normais ; bj Custo de produção utilizando horas extras c’ Custo de estocagem; dj Demanda no período j; Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 34 34 ej Capacidade de produção utilizando horas normais; Variáveis xj O quanto produzir no período j utilizando horas normais; yj O quanto produzir no período j utilizando horasextras; kj O quanto produzir no período j para estoque. Jjjkjyjx Jjjdjkjyjxjk Jjjejx Jj Jj jkjcjyjb Jj jxja ,0,0,0 1 Minimizar A Figura 4.1 mostra este modelo em linguagem GAMS. Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 35 35 Figura 4.1- Modelo dinâmico de estoque em linguagem GAMS. Solução ótima: produção utilizando horas normais: t1=40; t2= 40; t3= 40 e t4= 25. Produção utilizando horas extras: t2= 10; t3= 35. Estoques: t1= 10. Custo mínimo R$ 7.840,00 Exemplo 2: Fluxo de caixa multiperíodo. Uma empresa está construindo um novo restaurante que integrará a sua cadeia no próximo ano. Para tal, necessita de um total de R$ 500.000,00 que será pago à construtora em duas parcelas de R$ 150.000,00 ao final do 2º e 5º meses, e uma parcela de R$ 200.000,00 ao término da Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 36 36 construção no fim do 7º mês. A empresa dispõe de 4 tipos de investimentos que podem ser utilizados a fim de gerar caixa para quitar a construção de maneira a reduzir a necessidade total de caixa. Informações: Investimento Aplicação disponível no início dos meses Meses de duração da aplicação Retorno ao final do investimento Tipo A 1,2,3,4,5,6,7 1 1.5% Tipo B 1,3,5 2 3.2% Tipo C 1,4 3 4.5% Tipo D 1 7 9% Solução: Índices: j: associado aos tipos de investimento. m: associado aos meses. a: associado às aplicações disponíveis. Parâmetros: Investimentosj, a, m: associado a alocado do disponível a no tipo de investimento j no mês m. Dm: associado à parcela a ser paga no mês m. Variáveis: Z associada à função objetivo. Utilizadoj, a: associada ao valor aplicado no tipo de investimento j do disponível a. 0Utilizado DUtilizado.tosInvestimen :asujeito UtilizadoDUtilizadoCUtilizadoBA UtilizadoMin Z aj, n aj, maj,ma,j, 1111 A Figura 4.2 contempla o modelo fluxo de caixa em linguagem GAMS. Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 37 37 Figura 4.2- Modelo fluxo de caixa em linguagem GAMS. Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 38 38 Exercícios propostos Uma fábrica produz refrigeradores, freezers e fornos. A demanda mensal média destes produtos é, respectivamente, de 115.000, 58.000 e 48.000 unidades, e segue um esquema de médias móveis com período de 4, isto é, a demanda de quatro meses consecutivos e constantes ao longo do tempo. A demanda registrada nos últimos três meses foi à seguinte: Demanda mensal por (unidades) Produto Julho Agosto Setembro Refrigerador 125.000 108.000 136.000 Freezer 57.000 52.000 73.000 Forno 45.000 36.000 58.000 Para fabricar estes produtos, três recursos básicos são necessários (MDO, MP e energia), cujos consumos unitários estão apresentados no quadro abaixo. Consumo unitário Produto MDO/ horas Material Kg Energia kWh Refrigerador 1,4 17 25 Freezer 1,7 21 23 Forno 1,1 10 17 A fábrica dispõe de 1.900 empregados na linha de produção, cada um dos quais trabalha 200 horas por mês. O custo de armazenamento mensal de uma unidade de cada produto R$ 10, R$ 13, R$ 8, respectivamente. A disponibilidade mensal de energia é 5,5 x 106 KW/h. A empresa poderá comprar até 3.850 ton/ mês de material, que poderá ser armazenado a um custo mensal de R$ 0,15kg. Desenvolva o modelo matemático que permita determinar o plano ótimo de produção- material-pessoal para os próximos 12 meses, de modo a garantir que todos os empregados entrem em férias (1 mês) durante este período. Considere que no início do mês de outubro não existe estoque de produto acabado e que o estoque de matéria-prima é de 3.200 toneladas. REFERÊNCIAS ANDRADE, E. L. Introdução à Pesquisa Operacional. LTC, Rio de Janeiro, Brasil, 2004. BROOKE, A.; KENDRICK, D. & MEERAUS, A. GAMS: Sistema geral de modelagem algébrica. São Paulo: Edgard Blücher, 1997. Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 39 39 COLIN, E.C. Pesquisa Operacional: 170 aplicações em Estratégia, Finanças, Logística, Produção, Marketing e Vendas. Rio de Janeiro LTC, 2007. LACHTERMACHER, G. pesquisa operacional na tomada de decisão: Modelagem em Excel. 2º ed.- Rio de Janeiro: Elsevier, 2004. LINS, M .P. E; CALÔBA, G.M. Programação Linear: com aplicações em teoria dos jogos e avaliação de desempenho (Data Envelopment Analysis). Rio de Janeiro; Interciência - 2006. GOLDBARG, M. C; LUNA, H. P. L. Otimização combinatória e programação linear: Modelos e algoritmos. Rio de Janeiro: Campus, 2005. SHIMIZU, T. Decisão nas organizações: introdução aos problemas de decisão encontrados nas organizações e nos sistemas de apoio à decisão. São Paulo: Atlas, 2010. 40 Capítulo 5: Modelos Inteiros 5. Desenvolvimento e otimização de modelos inteiros por meio do GAMS Supondo que a empresa X, tenha uma disponibilidade máxima de R$ 650 reais para realizar vários investimentos. A taxa mínima de atratividade requerida por esta empresa é 10%, para cada um dos projetos. Os projetos 1 a 6 são mutuamente excludentes, ou seja, a escolha de um elimina os outros 5. Após a realização dos cálculos obtiveram os seguintes resultados Tabela 5.1- Dados do problema. Projeto Investimento Inicial/ (UM 1.000,00) Valor Presente p/ I= 10% p/UM 1.000,00 1 R$ 150,00 R$ 500,00 2 R$ 160,00 R$ 515,00 3 R$ 170,00 R$ 555,00 4 R$ 210,00 R$ 530,00 5 R$ 180,00 R$ 565,00 6 R$ 240,00 R$ 595,00 7 R$ 200,00 R$ 500,00 8 R$ 150,00 R$ 400,00 9 R$ 70,00 R$ 30,00 10 R$ 250,00 R$ 350,00 11 R$ 150,00 R$ 300,00 Selecionar o portfólio de projetos que maximize o valor presente desta empresa. Os recursos disponíveis são de R$ 650. Solução: Índices: p: associado aos projetos disponíveis, pP, P={1,2,...,11}. Parâmetros: Ip: capital disponível para investir no projeto p. Desenvolvimento e Otimização de Modelos Inteiros______________________________________ 41 41 VPLp: Valor presente do projeto p. Variáveis: Xp: associado à escolha do projeto p. Modelo matemático: 10, 650 1 6 :asujeito Max Z pX pIpX Pp pX Pp pVPLpX Desenvolvimento e Otimização de Modelos Inteiros______________________________________ 42 42 Figura 5.1- Modelo MIP1 em GAMS. Solução ótima: Investir nos projetos: P1, P7, P8 e P11. Gerando um VPL máximo R$ 1.700,00. Exemplo 2: Uma indústria quer se expandir, construindo nova Fábrica ou em Itajubá ou em Guaratinguetá. Também será considerada a construção de um novo Depósito na cidade que for selecionada para receber a nova Fábrica. O Valor Presente Líquido de cada alternativa está na Tabela 5.2. A última coluna dá o Capital Requerido para os investimentos, sendo o capital total disponível $25 milhões. Achar a combinação viável de alternativas que Maximize o Valor Presente Líquido Total. Tabela 5.2- Dados para a construção da nova Fábrica. Decisão Sim ou Não VPL Capital Requerido 1 Fábrica em Itajubá 7.000.000 20.000.000 2 Fábrica em Guaratinguetá 5.000.000 15.000.000 3 Depósito em Itajubá 4.000.000 12.000.000 4 Depósito em Guaratinguetá 3.000.000 10.000.000 Solução: Modelo Matemático: Desenvolvimento e Otimização de Modelos Inteiros______________________________________ 43 43 A Figura 5.2 mostra este modelo em linguagem GAMS. Figura 5.2- Modelo MIP2 em linguagem GAMS. Desenvolvimento e Otimização de Modelos Inteiros______________________________________ 44 44 Solução ótima: Construir tudo em Guaratinguetá. Gerando um VPLmáximo de R$ 8.000.000,00. Repare que utilizamos o solver MIP (CPLEX 12.1.0), sendo este, o solver mais adequado para resolver problemas mistos, binários e inteiros. REFERÊNCIAS ANDRADE, E. L. Introdução à Pesquisa Operacional. LTC, Rio de Janeiro, Brasil, 2004. BROOKE, A.; KENDRICK, D. & MEERAUS, A. GAMS: Sistema geral de modelagem algébrica. São Paulo: Edgard Blücher, 1997. COLIN, E.C. Pesquisa Operacional: 170 aplicações em Estratégia, Finanças, Logística, Produção, Marketing e Vendas. Rio de Janeiro LTC, 2007. LACHTERMACHER, G. pesquisa operacional na tomada de decisão: Modelagem em Excel. 2º ed.- Rio de Janeiro: Elsevier, 2004. LINS, M .P. E; CALÔBA, G.M. Programação Linear: com aplicações em teoria dos jogos e avaliação de desempenho (Data Envelopment Analysis). Rio de Janeiro; Interciência - 2006. GOLDBARG, M. C; LUNA, H. P. L. Otimização combinatória e programação linear: Modelos e algoritmos. Rio de Janeiro: Campus, 2005. 45 Capítulo 6: Otimização em Redes e Grafos 6. Desenvolvimento e otimização de modelos de rede por meio do GAMS De forma geral, modelos de rede são utilizados em casos especiais de otimização linear que são mais bem analisados por meio de uma representação gráfica. Modelos de rede são diagramas compostos por uma coleção de vértices ou nós ligados entre si por um conjunto de arcos, conforme mostra a Figura 6.1. Os nós são os círculos e os arcos são as retas de ligação. Figura 6.1- Componentes de uma rede. Os problemas modelados como redes geralmente apresentam números associados aos nós e aos arcos. Em problemas de transporte modelados como redes, por exemplo, os números associados aos nós podem representar a quantidade de produtos ofertados ou demanda pelo nó, ao passo que os valores dos arcos podem refletir os custos de transporte (ou tempo, ou à distância) entre um nó e o outro. Diversos problemas de tomada de decisão práticos estão categorizados como problemas de Rede. Entre eles pode-se citar: Problemas de Transporte; Escala de Produção; Rede de Distribuição; Problemas de Menor Caminho; Problemas de fluxo máximo; Problemas de caminho crítico; Problemas de árvores geradoras mínimas. A Figura 6.2 contempla um exemplo de redes em problemas de transporte. Desenvolvimento e Otimização de modelos de redes______________________________________ 46 46 Figura 6.2- Exemplo de problemas de transporte. Sendo os nós 1, 2 e 3 as origens e os demais nós os destinos. Exemplo 1: Uma empresa fabricante de bicicletas possui três fábricas localizadas no Rio, em São Paulo e em Belo Horizonte. A produção da empresa deve ser entregue em Recife, Salvador e Manaus. Considerando os custos de transporte unitários, a capacidade de produção das fábricas e a demanda dos centros consumidores ilustrados na Tabela a seguir. Determine quanto deve ser produzido e entregue por fábrica em cada centro consumidor, de forma a minimizar os custos de transporte. Fábrica/ Consumidor Recife Salvador Manaus Capacidade Rio 25 20 30 2000 SP 30 25 25 3000 BH 20 15 23 1500 Demanda 2000 2000 2000 6000/6.500 Solução: Índices: i: associado às fábricas, iI, I= {Rio, SP, BH}. j: associado aos destinos, jJ, J={Recife, Salvador, Manaus}. Desenvolvimento e Otimização de modelos de redes______________________________________ 47 47 Parâmetros: Ci, j: associado ao envio da fábrica i para o destino j. ai: associado à capacidade máxima de armazenagem da fábrica i. bj: associado à demanda requerida pelo destino j. Variáveis: Xij: associada à quantidade a ser enviada da fábrica i para o destino j. Modelo matemático: JjIijiX Ii Jj iajiX Jj Ii jbjiX Ii Jj jiCjiXMin ,,0 :asujeito A Figura 6.3 mostra este modelo em GAMS. Desenvolvimento e Otimização de modelos de redes______________________________________ 48 48 Figura 6.3: Modelo Rede 1. Este modelo pode ser representado por um formato de rede conforme contemplado pela Figura 6.4. Figura 6.4- Modelo de rede do exemplo 1. Em modelos de transporte as equações devem estar equilibradas, isto é, oferta total= demanda total. Entretanto, podemos adotar um fluxo de balanceamento. Hipótese do Problema Tipo de Restrição Oferta > Demanda Entradas-Saídas ≥ Oferta ou demanda do nó Oferta < Demanda Entradas- Saídas ≤ Oferta ou Demanda do nó Oferta= Demanda Entradas-Saídas= Oferta ou demanda do nó Desenvolvimento e Otimização de modelos de redes______________________________________ 49 49 A Tabela abaixo apresenta um plano de manutenção de uma estufa dinâmica da Pintura a Pó LTDA. Uma das aplicações desse tipo de estufa é curar a tinta pó (de alta resistência) que é aplicada em peças metálicas. Por meio de um processo eletromagnético, o pó de tinta fica impregnado na peça, que é levada para dentro da estufa. Quando a peça entra na estufa a uma temperatura de aproximadamente 200 graus, a tinta derrete e fica impregnada na peça, num processo denominado cura da tinta. Em casos de produção de alto volume de peças pequenas e médias, produtos são fixados em gancheiras, que são transportados por trilhos que passam dentro da estufa aquecida. Atividade Descrição Predecessor imediato Tempo [hs] A Desligar e desaquecer a estufa - 6 B Avaliar rolamentos danificados - 4 C Trocar rolamentos danificados B, A 7 D Avaliar e trocar resistências danificadas A 8 E Limpar estufa internamente D 10 F Lubrificar trilho com grafite C 2 G Fazer inspeção final E, F 1 H Religar estufa G 2 Figura 6.5- Atividades de um projeto de manutenção Desenvolvimento e Otimização de modelos de redes______________________________________ 50 50 As atividades A e B não possuem atividades precedentes e, portanto, não há arestas de entrada. A atividade C possui arestas como predecessores imediatos, as atividades A e B. A atividade D possui como predecessor apenas a atividade A. As outras atividades são introduzidas na rede da mesma forma. Os números na construção da rede, algumas regras são levadas em consideração. O tamanho da aresta não tem associação com as atividades; As atividades iniciadas no final da aresta não podem ser iniciadas antes das atividades que são iniciadas no inicio da arestas; As atividades são representadas exclusivamente pelo seu início e término (evento inicial e final); Nós não podem ser duplicados; Dois nós só podem ser conectados por uma única aresta; OBS: A função objetivo neste caso é o tempo total, logo é definida por H+2, ou seja, o horário de término da última atividade. Com relação às atividades A e B, como não há nenhuma atividade predecessora tem-se A=B= 0. Sobre a modelagem das atividades que possuem predecessoras, como por exemplo, a atividade C, que tem a atividade A e B como predecessoras, tem-se: 4ou 4 6ou 6 BCBC ACAC A figura 6.6 mostra a modelagem em GAMS Desenvolvimento e Otimização de modelos de redes______________________________________ 51 51 Desenvolvimento e Otimização de modelos de redes______________________________________ 52 52 Figura 6.6- Modelo CPM EM GAMS Exercícios propostos 1) Considere a reconstrução de um armazém que será feito. As atividades associadas são apresentados na Tabela a seguir: Atividad e Descrição Predecessor imediato Tempo [dias] A Demolir o armazém - 2 B Comprar materiais para atividade de alvenaria - 1 C Separar material reutilizável A 1 D Escavação de fundações A 2 E Preparação do acesso ao depósito A 1 F Fazer lista de outros materiais necessários C 1 G Fazer fundações de concreto B, D 2 H Fazer acesso E 1 I Levantar paredes de alvenariaB, G 8 J Nivelar chão e fazer o contra piso F, G 2 K Instalar fiação e sistema elétrico F, I 1 L Acabar paredes K, M, N 5 M Fazer telhado F, I 1 Desenvolvimento e Otimização de modelos de redes______________________________________ 53 53 N Acabar piso de concreto J 5 O Montar calhas e tubulações de escoamento F, M 1 P Limpar H, L, O 1 Crie a rede associada ao projeto de reconstrução e indique qual o menor tempo para realização do projeto. Qual é o caminho crítico? 2) A pessoa responsável pelo plano de atividade do armazém cometeu dois pequenos erros. Ela introduziu duas relações da precedência imediata redundantes. Isso é uma falha conceitual e acontece nos planos de atividades mal feitos. Quais são as duas relações de precedência que não deveriam ter sido colocadas no plano? REFERÊNCIAS ANDRADE, E. L. Introdução à Pesquisa Operacional. LTC, Rio de Janeiro, Brasil, 2004. BROOKE, A.; KENDRICK, D. & MEERAUS, A. GAMS: Sistema geral de modelagem algébrica. São Paulo: Edgard Blücher, 1997. CAIXETA-FILHO, J. V . Pesquisa Operacional: Técnicas de otimização em aplicadas a sistemas agroindustriais. 2º .ed. – São Paulo: Atlas, 2004. COLIN, E.C. Pesquisa Operacional: 170 aplicações em Estratégia, Finanças, Logística, Produção, Marketing e Vendas. Rio de Janeiro LTC, 2007. LACHTERMACHER, G. pesquisa operacional na tomada de decisão: Modelagem em Excel. 2º ed.- Rio de Janeiro: Elsevier, 2004. LINS, M .P. E; CALÔBA, G.M. Programação Linear: com aplicações em teoria dos jogos e avaliação de desempenho (Data Envelopment Analysis). Rio de Janeiro; Interciência - 2006. MEDEIROS, A. L. ; MONTEVECHI, J. A. B. ; TURRIONI, J. B. ; SILVA, L.B ; MENDES, L. Otimização do planejamento produtivo a partir da programação linear: uma aplicação na pecuária leiteira.. In: XI SIMPEP - Simpósio de Engenharia de Produção. Anais do XI Simpósio de Engenharia de Produção. Bauru : FEB/UNESP, 2004. GOLDBARG, M. C; LUNA, H. P. L. Otimização combinatória e programação linear: Modelos e algoritmos. Rio de Janeiro: Campus, 2005. Desenvolvimento e Otimização de modelos de redes______________________________________ 54 54 SHIMIZU, T. Decisão nas organizações: introdução aos problemas de decisão encontrados nas organizações e nos sistemas de apoio à decisão. São Paulo: Atlas, 2010. 55 55 Capítulo 7: Otimização combinatória 7. Desenvolvimento de modelos de otimização combinatória por meio do GAMS Neste tópico vamos comentar sobre problemas de dificuldade polinomial (P) e problemas de dificuldade não polinomiais (NP). Problemas polinomiais são problemas cujos algoritmos conhecidos fornecem soluções que podem ser obtidas por meio de uma função polinomial de n tamanho de entrada, ou seja: f (n) = O(nk) sendo que(k) uma constante. Problemas NP são problemas cujos algoritmos de solução conhecidos são baseados em enumeração, seja ela implícita ou não. De maneira geral, o número de combinações possíveis é assustadoramente grande, fazendo com que os algoritmos enumerativos não consigam resolver problemas com grande número de entradas em tempo hábil. São denominados algoritmos de tempo exponencial e, é nestes contextos que se encaixam os problemas de otimização combinatória. Os problemas NP podem ser classificado, conforme (COLIN, 2007): Problemas NP - Completos: são problemas que possuem uma forte evidência da não existência de um algoritmo cujo tempo de solução seja uma função polinomial do tamanho da entrada. São considerados os mais difíceis da classe NP, e, se algum deles for resolvido em tempo polinomial, então todos os problemas NP também serão. Quando se sabe que um problema de otimização é NP - difícil, tem-se a certeza de que nem sempre a solução ótima será encontrada. Portanto, tem se aplicado métodos heurísticos, como por exemplo, algoritmos genéticos, colônias de formigas, busca tabu, dentre outras. Abaixo encontra-se o modelo do problema do Caixeiro-Viajante (CV), sendo este modelo de otimização combinatória. Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________56 56 0u,1,0 subrotasSão n)2,3,...,jn;3,...,2,ij;(i1-nnxuu chegadadeRestrição saídadeRestrição :asujeito .Min Z j, ji,ji 1 , 1 , 1 1 ,, ji n j ji n i ji n i n j jiji X X X XC As restrições de saída e de chegada são binárias, e garantem que cada um dos xij seja 0 ou 1. As restrições de saída garantem que para cada cidade haverá apenas uma rota de saída e, analogamente uma chegada para as restrições de chegada. As restrições de sub-rotas ou sub-circuitos garantem que a solução ótima não contenha sub- circuitos. Exemplo1: PARA Sede P1 P2 P3 P4 Sede 5 3.8 2.2 2.4 P1 5 2.6 3.1 5.1 P2 3.8 2.6 1.6 2.8 P3 2.2 3.1 1.6 2.3 DE P4 2.4 5.1 2.8 2.3 A Figura 7.1 mostra a solução deste problema por meio da linguagem GAMS. Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________57 57 , Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________58 58 Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________59 59 Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________60 60 Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________61 61 Figura 7.1-Modelo caixeiro viajante em GAMS. A Figura 7.2 mostra os caminhos a serem percorridos. Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________62 62 Figura 7.2-Modelo Caixeiro Viajante otimizado pelo GAMS. OBS: com n vértices há 2 )!1( n ciclos distintos. 63 Capítulo 8: Análise por Envoltória de Dados 8. Desenvolvimento e otimização de modelos de análise por envoltória de dados por meio do GAMS Em termos de programação matemática, a análise por envoltória de dados (DEA- Data Envelopment Analysis), também chamada de análise de fronteiras ou análise de eficiência, é considerada uma técnica relativamente nova. Ao mesmo tempo, também é considerada um dos sucessos recentes da programação linear. Em DEA existem as chamadas DMU- Decision Making Units, ou seja, as unidades tomadoras de decisão. Em linhas gerais, a DEA avalia problemas com múltiplos recursos (usados para gerar produtos e ou serviços e múltiplas saídas para cada unidade,(COLIN, 2007). A capacidade com que as DMUs conseguem gerar saídas para determinadas entradas define sua eficiência. Supõe-se que as DMUs menos eficientes podem melhorar sua eficiência até o limite das melhores unidades , cuja eficiência é de 100%. Mais especificamente, a DEA determina, segundo Colin (2007): A melhor prática- grupo das DMUs mais eficientes; As DMUs menos eficientes comparadas com as melhores práticas; A quantidade de recursos utilizados de forma improdutiva nas DMUs menos eficientes; Para cada uma das DMUs menos eficientes, o grupo das unidades de melhor prática que são mais parecidas com elas e que poderiam ser usadas como benchmarks. Antes de prosseguir com o DEA, vamos entender alguns significados. Eficácia – Capacidade da unidade produtiva atingir as metas previamente estabelecidas; Produtividade – Razão entre o que foi produzido e o que foi gasto para produzir. Ex.: Peças/H.h; Eficiência – Conceito relativo que compara o que foi produzido com o que poderia ter sido produzido. Pode ser entendida como uma comparação entre as produtividades observadas; Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 64 64 Se uma unidadeatingiu a meta, foi eficaz. Se conhecermos os recursos que a unidade dispunha podemos avaliar se esta foi produtiva. Se soubermos quais foram os resultados da concorrência podemos avaliar a eficiência da unidade (SOARES DE MELLO, 2005). Segundo Batista (2009) as empresas ou unidades produtivas têm como principal função a produção de bens e serviços. A teoria da produção mostra como as empresas podem tomar decisões de produção baseadas na minimização dos custos e como estes custos podem variar com o volume produzido. Quando há dois insumos, há uma forma de descrever as relações de produção, conhecida como isoquanta. Para Pindyck e Rubinfeld (2002). A isoquanta representa todas as possíveis combinações de insumos que resultam no mesmo volume de produção, conforme Figura 3. Para motivos de ilustração, supondo que X1 fosse mão de obra e X2 matéria prima, ao dobrar-se a quantidade de insumos a produção mais do que dobra, para o caso de rendimentos crescentes. Quando o rendimento de escala é constante, significa que, quando se dobra a quantidade de insumos a produção também dobra, ou seja, mantém-se a mesma proporção, e quando o retorno é decrescente, ocorre quando se dobra a quantidade de insumos e a produção cresce de forma bem tímida ou pouco expressiva. Figura 8.1- Rendimentos de escala. Fonte: Pindyck e Rubinfeld (2002) Charnes, Cooper e Rhodes (1978) abordaram DEA pela primeira vez ao desenvolverem um modelo para uma nova medida de eficiência na avaliação de programas públicos. Cooper, Seiford e Tone (2006) definem alguns critérios de entrada e saída que cada DMU Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 65 65 deve atender. São eles: As variáveis e Decision Making Units (DMU’s) ou unidade de tomada de decisão devem ser escolhidas de modo a representar o interesse dos gestores, sendo as DMU = {Países, professores, cidades, departamentos, dentre outros}; Há dados numéricos positivos para cada entrada e saída, sendo que se deve preferir o uso de um menor do número de entradas comparado ao número de saídas. A Figura 4 contempla um exemplo da avaliação da eficiência, sendo as DMU (lojas) = {A, B,..., H}, e as variáveis de entrada input os funcionários e a variável de saída output as vendas. Realizando o cálculo de produtividade, isto é, a razão entre a saída pela entrada, percebe-se que apenas a DMU B foi eficiente, conforme a reta em vermelho, demonstrando que a DEA envelopa todas as DMU’s. Figura 8.2- Exemplo da modelagem de problemas de avaliação de eficiência. Fonte. Cooper. Seiford; Tonne (2006). Mello et al. (2005) diz que há três direções que podem ser adotadas nas projeções das DMU’s ineficientes sobre a fronteira de produção, conforme ilustrado na Figura . Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 66 66 Figura 8.3- Representação Gráfica para o modelo DEA três orientações do modelo. Fonte: Mello et al.(2005) Um procedimento é chamado de orientação a input, cujo objetivo é minimizar os inputs enquanto pelo menos mantém os níveis atuais de outputs, outro é chamado de orientação a output, cujo objetivo é maximizar os níveis de outputs mantendo o mesmo consumo atual de inputs, e uma terceira opção tenta combinar ambas as orientações, sendo representado pelos modelos Aditivos (Additive models) ou baseados em folgas (Slack Based Measure) (SANTOS; MARINS; SALOMON, 2011). O modelo DEA CCR (Charnes, Cooper e Rhodes, 1978) é apresentado no modelo abaixo. Os pesos para variável de entrada e saída do modelo geral da DEA podem ser obtidos a partir da solução do modelo proposto por Charnes; Cooper; Rhodes (1978), dado por (1) – (4): m i ii s r rr o xv yu w 1 0 1 0 . . max S.a: nj xv yu m i jii s r rjr ,...,2,1 ,1 1 1 .,...,2,1 ,0 srur .,...,2,1 ,0 mivi Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 67 67 com j representando o índice da DMU, j=1,...,n; r é o índice da saída, com r = 1,...,s; i é o índice da entrada, i = 1,...,m; yrj é o valor da r-ésima saída para a j-ésima DMU, xi j é o valor da i-ésima entrada para a j-ésima DMU, ur é o peso associado a r-ésima saída; vi é o peso associado a i-ésima entrada, wo é a eficiência relativa de DMUo, que é a DMU sob avaliação; e yr0 e xio são os coeficientes tecnológicos das matrizes de dados de saídas e entradas, respectivamente. Caso wo = 1, a DMU0 é eficiente quando comparada às demais unidades consideradas no modelo. Caso wo <1, esta DMU é ineficiente. Este modelo não é linear, sendo um caso da Programação Fracionária, mas que pode ser linearizado, conforme (5) – (9), pelo modelo conhecido por CCR (CHARNES; COOPER; RHODES, 1978), ou com Retornos Constantes de Escala. Entretanto, o modelo linearizado é descrito abaixo. x, y. , , v u n...,c, , k xv- yu xv S.a.: yuMax E ij m i iki s j jkj m i ici s j jcj c 0 ,,,210 1 11 1 1 Esta forma do problema é conhecida como problema dos multiplicadores, como também são chamados os pesos, uj e vi. Lembrando que há vários modelos de DEA, como por exemplo, modelos estocásticos, fuzzy, folgas, aditivo, dentro outros. Neste livro iremos mostrar apenas os modelos CCR e BCC modelados em GAMS, ao final do capítulo há uma vasta referência sobre o assunto. Exemplo 1: Um hospital deseja avaliar sua eficiência em relação aos demais hospitais da cidade. A Tabela abaixo contempla os dados de entrada e saída analisados Hospital Entradas (x) Saídas (y) Capital Mão de obra Jovens Adultos Idosos 1 5 14 9 4 16 2 8 15 5 7 10 3 7 12 4 9 13 Neste caso são 3 problemas de programação linear, um para cada DMU. Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 68 68 A Figura 8.4 mostra a solução deste modelos por meio do GAMS. Lembrando-os que Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 69 69 Figura 8.4- Modelo DEA em GAMS Basicamente o que muda de um modelo para o outro é a função objetivo e a equação 4 (calculo 4). Vamos interpretar a solução ótima para o último modelo. W2= 0,9 ; W3= 7.1% e V2= 8.3%. Neste caso as saídas adultos e jovens são importantes para manter a eficiência máxima do hospital 3. Deve-se conservar a mão de obra. A Figura 8.5 contempla um exemplo de como modelar o dual de um problema de DEA. Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 70 70 Figura 8.5- Modelo primal e Dual de problemas de DEA. Pelo GAMS também é possível rodar vários modelos continuamente. Vamos mostrar um exemplo tomando como base o exemplo exposto acima. A Figura 8.6 mostra este exemplo. Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 71 71 Figura 8.6: Modelo DEA GLOBAL. Repare que inseriu-se mais uma variável e também algumas equações e, ao rodar o modelo, deve ser informado apenas as equações pertencentes ao modelo desejado. Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 72 72 Outro tipo de modelo DEA que iremos ver neste livro é conhecido por BCC (Banker, Charnes e Cooper, 1984). No modelo DEA CCR há retornosde escalas constantes, válido para unidades operando em escala ótima. No modelo BCC ou VRS, substitui o axioma da proporcionalidade pelo axioma da convexidade linear, soma dos lambdas igual a 1. Fronteira côncava e linear por parte, também chamado de retorno variáveis de escala. u j, i. , , v u k ,uyuxv xv S.a.: uyuMax E ij j jkj j iki i ici j jjff * 0 0* 1 *. . 1 1 00 As eficiências no modelo DEA BCC são maiores ou iguais as eficiências do modelo CCR. No modelo CCR as eficiências independem da orientação; os outros resultados de DEA dependem da orientação No modelo BCC todos os resultados de DEA dependem da orientação. A Figura 8.7 mostra as diferenças entre estes modelos. Figura 8.7- Modelos DEA A figura 8.8contempla a solução deste exemplo pelo modelo BCC ou (VRS). Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 73 73 Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 74 74 Figura 8.8- Modelagem em GAMS modelo DEA BCC ou VRS Neste exemplo foi necessário acrescentar outro conjunto (sets) chamado u que vai pertencer a variável do modelo BCC. Modelo de Supereficiência A Supereficiência tem como objetivo ranquear as unidades de análise, ou seja, estabelecer uma ordem decrescente de prioridade. A ideia básica é remover a restrição que limita que o valor da eficiência seja de no máximo 1 ou 100. Desta forma, restrição que, a saída menos a entrada devem ser igual a zero é retirada do modelo. x, y. , , v u n...,c, , k xv- yu xv S.a.: yuMax E ij m i iki s j jkj m i ici s j jcj c 0 ,,,210 1 11 1 1 x, y. , i, vj u m i ic xiv S.a.: s j yjcjuMax Ec 0 1 1 1 Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 75 75 Tomando com exemplo o modelo BCC anterior a modelagem da Supereficiência seria: Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 76 76 Hospital Eficiência Supereficiência Hospital 1 1 2,888 Hospital 2 0,827 0,827 Hospital 3 1 1,613 Percebe-se que se a DMU não é eficiente seu valor na Supereficiência é igual ao valor de sua ineficiência. Em resumo a melhor DMU seria o hospital 1 seguido pelo hospital 2. Modelo aditivo: Os modelos de DEA anteriores (CCR e BCC) minimização a utilização dos insumos com o mesmo volume de produção (modelos orientados a insumo) ou maximizam a produção, com a mesma utilização de insumos (orientados ao produto), (FERREIRA e GOMES, 2009). O modelo aditivo pressupõe que o valor marginal das folgas dos insumos e produtos maiores do que zero seja igual. Deste modo, é necessário cautela ao se empregar esse modelo, uma vez que: a) as unidades de medida utilizadas para os insumos e produtos influenciam os resultados, ou seja, unidades diferentes resultam escores de eficiência diferentes; b) é preciso cuidado para não somar medidas que não sejam comensuráveis. Desse modo, recomenda-se, aliás como deve ser Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 77 77 em todos os casos em que utilizam-se modelos de DEA um bom conhecimento e experiência com o setor e organizações em análise. Este modelo foi desenvolvido por Charnes et al. (1985). Jj j te Constorno Jj j Variáveltorno Jj j rAcrescentaRVE R rIiJj rsisj R r Jj ryjryj Ii Jj ixjixjas rr rs Ii is 1 tanRe1 Re1 : ,,,0,, 0 0:. max Sendo: λj define a importância as DMus benchmarks, yrj matriz dos produtos r para a dmu j, xij matriz dos insumos i para a dmu j. yr0 matriz dos produtos r para a dmu que está sob análise, xi0 matriz dos insumos i para a dmu que está sob análise. is e rs são as variáveis de folga vinculada Cooper, Park e Pastor (1999) propuseram utilizar o inverso das amplitudes (Z-= x0maior x0menor; Z+= yomaior y0menor) para tornar o processo de maximização da função objetivo independente das unidades de medidas dos inputs e outputs. Desta forma, os pesos dos inputs serão wi -=1/ Z- e dos outputs wj +=1/ Z+. A solução ótima do modelo (eficiência) implica que a soma das folgas seja zero. Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 78 78 Aplicação: DMUs Insumo 1 Insumo 2 Produto 1 6 14 2 2 8 16 4 3 12 12 3 4 6 4 2 5 6 3 1 6 15 3 3 Modelagem em GAMS: Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 79 79 Figura 8.10- Modelagem GAMS modelo aditivo Folgas do modelo aditivo-MBF 0 10 0 0 0 0 3 6 0 0 0 0 5 2 0 0 0 0 Dados originais Alvos eficientes DMUs Insumo 1 Insumo 2 Produto Insumo 1 Insumo 2 Produto 1 6 14 2 6 4 2 2 8 16 4 8 16 4 3 12 12 3 9 6 3 4 6 4 2 6 4 2 5 6 3 1 1 4 1 6 15 3 3 15 3 3 Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 80 80 Exercícios propostos 1) Max 001,0 v,001,0w 0v145v 0v127v-w313w94w 0v158v-w310w75w 0v145v-w316w49w :asujeito w316w49w Z kj 21 2121 2121 2121 21 Formule o problema dual dos hospitais. E resolva-o pelos dois métodos. 2) O banco S/A está analisando a eficiência de suas agências a Tabela abaixo mostra os dados de entrada e saída analisados. Recursos empregados (Entrada) Economia potencial (Saída) Agências menos produtivas Caixa [pessoas] Plataforma [pessoas] Gerente [pessoas] Despesas (excl. pessoal e aluguel) [$] Área da agência [pé2] Caixa Plata- forma Gerente Despesas Área da agência A1 10,0 5,0 1,0 652.566 3.818 4,5 1,8 0,3 222.928 1.304 A3 3,0 2,5 1,0 468.637 1.728 1,9 1,6 0,7 295.989 1.133 A4 4,0 2,5 1,0 350.477 1.941 2,3 1,4 0,7 189.745 1.051 A5 9,0 7,0 1,0 1.059.526 5.640 0,7 1,9 0,1 367.020 1.899 A6 3,0 2,5 1,0 235.974 2.200 1,6 1,4 0,6 122.474 1.556 A8 4,5 3,5 1,0 353.235 1.350 1,5 1,3 0,3 10.526 40 A9 3,5 2,0 1,0 341.994 2.346 1,2 0,7 0,4 116.716 976 A11 7,5 3,5 1,0 768.338 3.243 3,3 0,7 0,2 329.403 774 A12 2,5 2,0 1,0 269.998 1.422 1,1 1,1 0,7 122.433 889 A13 9,0 6,5 1,0 1.112.090 5.400 0,1 0,1 - 131.389 1.477 A14 3,5 4,0 1,0 433.868 1.700 0,7 2,0 0,4 81.024 502 A15 2,0 2,0 1,0 253.902 1.486 1,1 1,3 0,7 135.920 961 A18 4,0 2,5 1,0 571.090 1.420 2,0 0,8 0,4 206.693 361 A20 7,0 4,0 1,0 666.133 3.180 3,0 1,5 0,4 280.853 1.176 A22 7,5 3,5 1,0 929.668 1.865 5,2 1,5 0,3 496.072 605 A26 3,5 3,0 1,0 411.922 3.092 1,0 1,0 0,3 112.147 1.491 A27 5,5 5,5 1,0 545.976 2.781 1,9 3,1 0,3 188.394 960 A28 6,0 5,0 1,0 914.990 2.187 1,8 1,6 - 233.870 60 A29 7,0 4,0 1,0 568.054 6.686 1,7 0,9 0,2 176.227 3.669 A30 15,0 13,0 1,0 1.402.615 9.963 4,0 6,1 0,3 551.272 5.377 A31 5,5 6,0 1,0 679.451 3.133 0,8 2,7 0,1 94.692 824 A32 3,0 2,0 1,0 367.828 1.637 0,9 0,6 0,5 107.934 480 A33 17,5 18,0 1,0 3.191.789 8.000 3,3 10,6 0,2 2.510.589 2.016 Total 143,0 109,5 23,0
Compartilhar