PESQUISA OPERACIONAL DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS MATEMÁTICOS POR MEIO DA LINGUAGEM GAMS UNESP Aneirson Francisco da Silva- Doutorando-UNESP Fernando Augusto Silva Marins, Dr- UNESP Guilherme Martin Silva Paulo Roberto Marcondes de Andrade Lopes O objetivo desta apostila é fornecer conceitos matemáticos sobre a estrutura da linguagem de modelagem General Algebraic Modeling System – GAMS. Após a leitura desta apostila o leitor estará apto a desenvolver e otimizar modelos lineares e combinatórios utilizando a linguagem e o software GAMS. A estrutura da apostila está definida primeiramente pela revisão da história da pesquisa operacional, e em seguida a explicação a respeito dos modelos lineares, iniciando pelas particularidades desse modelo, teoria de redes DEA. Também são abordados modelos de otimização combinatória e problemas NP-HARD. Capítulo 1 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. Introdução________________________________________________________________________ 4 A otimização, portanto, produz a melhor solução para o problema que foi modelado. 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. Introdução________________________________________________________________________ 5 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 idé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 de produçã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; Introdução________________________________________________________________________ 6 PROGRAMAÇÃO 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: que é 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. Capítulo 2 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,j: Quantidade a ser produzida do produto i utilizando os recursos j. 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________________________________ 8 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. 2 Max Z MC i . X i i sujeito a : n R i, j .X i A j i X "SOLDADO " 40 X I ,J 0 A Tabela 2.1 mostra alguns comandos básicos da linguagem GAMS Tabela 2.1- Comandos básicos em linguagem GAMS Estruturação e otimização de modelos lineares estacionários________________________________ 9 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 1 radianos CEIL Função teto Maior inteiro ≥ arg COS Cosseno Cos (arg) argumento 1 em 1 Integral de distribuição normal 1 radianos ERRORF Função erro padrão EXP Exponencial earg 1 FLOOR Função piso Maior inteiro ≤ arg 1 Estruturação e otimização de modelos lineares estacionários________________________________ 10 Nome Descrição Definição Número de Argumentos LOG Logaritmo Log do arg na base e 1 Log de arg na base 10 1 natural Log10 Logaritmo comum MAPVAL Função Atribuiu números mapeamento especiais 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 Número 2* normal normalmente com argumento aleatório a valores distribuído 1 arg1 e desvio padrão arg2 POWER Potência inteira ROUND Arredondamento SIGN Sinal SIN Seno Sem (arg); arg em radianos SQR Quadrado arg x arg SQRT Raiz quadrada TRUNC Truncamento Sign (arg) x floor (abs(arg)) 1 UNIFORM Randômica Número 2* uniforme uniformemente entre arg1 e arg2 1 1 aleatório distribuído 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 Estruturação e otimização de modelos lineares estacionários________________________________ 11 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 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________________________________ 12 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 Produto 2 Produto 3 1 Tempo disponível Torno 5 3 5 400 Fresa 8 4 0 500 Furadeira 2 5 3 300 Lucro 20 15 18 Demanda Semanal 40 50 20 máxima 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. i, j Os objetos são os i produtos e j recursos 2 passo: Descrever os parâmetros. Estruturação e otimização de modelos lineares estacionários________________________________ 13 Ri, j: Consumo unitários por produto i de cada recurso j. Aj: Quantidade disponível do recurso j. 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. Margem: Define o lucro máximo Consumoj: Define o consumo por produto i do recurso j. Dprodutosi: Define a demanda máxima por produto i. 5 passo: Construção do modelo matemático. n Max Z L i .X i i sujeito a : n consumo j R i, j .X i A j i Dprodutos i X i D i X I,J 0 Estruturação e otimização de modelos lineares estacionários________________________________ 14 Estruturação e otimização de modelos lineares estacionários________________________________ 15 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. Desenvolva e otimize os modelos dos problemas descritos a seguir utilizando-se do software GAMS. 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? Estruturação e otimização de modelos lineares estacionários________________________________ 16 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. 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 Luxo Esferográfica 15.000 10.000 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: Estruturação e otimização de modelos lineares estacionários________________________________ 17 Standard Luxo R$ 0,70 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. 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 – Uma indústria de aparelhos eletrodomésticos tem equipamento para produzir geladeiras, máquinas de lavar e fogões. O regime de operação da indústria é de 45 horas semanais. Seu equipamento pode fabricar, por hora, 50 geladeiras ou 25 máquinas de lavar ou 75 fogões. Uma pesquisa de mercado revelou que a demanda semanal é de 1.000 geladeiras, 500 máquinas de lavar e 1.500 fogões. Estruturação e otimização de modelos lineares estacionários________________________________ 18 A geladeira proporciona, por cada unidade vendida, um lucro de R$ 40,00; a máquina de lavar R$ 120,00 e o fogão um lucro de R$ 30,00. Qual seria o modelo matemático da indústria que permitiria o lucro máximo semanal ? 7 – Um sapateiro faz 6 sapatos por hora, se fizer somente sapatos, e 5 cintos por hora, se fizer somente cintos. Ele gasta 2 unidades de couro para fabricar uma unidade de sapato e uma unidade de couro para fabricar uma unidade de cinto. Sabendo-se que o total disponível de couro é de 6 unidades e que o lucro unitário por sapato é de 5 unidades monetárias e o do cinto é de 2 unidades monetárias, pede-se: o modelo do sistema de produção do sapateiro, se o objetivo é maximizar seu lucro por hora. 8 – 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. 9 – Uma rede de televisão local tem o seguinte problema: foi descoberto que o programa “A” com 20 minutos de música e 1 minuto de propaganda chama a atenção de 30.000 telespectadores, enquanto o programa “B” com 10 minutos de música e 1 minuto de propaganda chama a atenção de 10.000 telespectadores. NO decorrer de uma semana, o patrocinador insiste no uso de no mínimo, 5 minutos para sua propaganda e que não há verba para mais de 80 minutos de música. Quantas vezes por semana cada programa devem ser levadas ao ar para obter o número máximo de telespectadores? Construa o modelo do sistema. 10 – Um fazendeiro está estudando a divisão de sua propriedade nas seguintes atividades produtivas. Estruturação e otimização de modelos lineares estacionários________________________________ 19 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? Capítulo 3 3. DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS LINEARES PRÁTICOS 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 AT RESTRIÇÕES Á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______________ 21 Tabela 3.1- Consumo anual por animal. Restrições RECURSOS DISPONÍVEIS RECURSOS CONSUMIDOS POR CATEGORIA Unidades 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 RO 51.729,07 R$/ano 42,60 32,23 28,87 Orçamento disponível: R$ 487.852,20 316,79 114,95 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 X1 X2 X3 X4 X5 Qtde Máxima 95 135 170 200 12 Qtde Mínima 39 53 60 100 - 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______________ 22 Índices: i associado às categorias de animais (Bezerras, Bezerros, Novilhas, Vacas e Touros). j associado às categorias dos recursos (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. Variáveis: Xi: Quantidade por categoria de animal. Z: Associada ao cálculo da função objetivo. Equações: Animais define a função objetivo AJ: Calcula o quanto a ser utilizado do recurso j por categoria de animal i. maxbezerrai: máximo de bezerras. minbezerrai: mínimo de bezerras. maxbezerrosi: máximo de bezerros. minbezerrosi: mínimo de bezerros. maxnovilhasi: máximo de novilhas. minnovilhasi: mínimo de novilhas. maxvacasi: máximo de vacas minvacasi: mínimo de vacas. mintouroi: mínimo de touro. maxtouroi: máximo de touro. Vamos introduzir outro comando na linguagem GAMS denominado SCALAR neste caso esse comando vai representar uma constante que não está ligado a nenhum índice. Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 23 n animais Z X i i sujeito a : n R i, j . X i Pj i maxbezerra i X "bezerras " 95 minbezerra i X "bezerras " 39 maxbezerro i X "bezerros " 135 minbezerro i X "bezerros " 53 maxnovilhas i X "novilhas" 170 minnovilhas i X "novilhas" 60 maxvacasi X "vacas" 200 minvacas i X "vacas" 100 maxtouro i X "touro" 12 mintouro i X "touro" 9 X i, j 0 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 contínua. 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______________ 24 Figura 3.1- Modelo agricultura em GAMS. Os ‘e as “ (estes pontos ‘ “) 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 Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 25 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. 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 14 Sexta-feira 14 Sábado 16 Índices: n: associado ao número de funcionários s: associado aos dias da semana. Parâmetros: Alocaçãos,n: associado ao número de funcionários n requeridos no dia da semana s. Funcionáriosn: associado ao número mínimo de funcionários n para trabalhar no dia da semana s. Variáveis: Z associada à função objetivo. Xs: número de funcionários i contratados no dia da semana s. Equações: Func: calcula a função objetivo. Alocadosn: calcula o número de funcionários alocados em cada dia da semana s. A Figura 3.2 mostra o resumo do modelo no GAMS. A solução ótima para o problema é contratar 22,6666 funcionários no total, sendo que seria contratado 5 funcionários no domingo, 1,666 na segunda, 4.667 na terça, 7,667 na quinta e 3.667 no sábado. Os totais de empregados disponíveis por dia da semana estão dispostos abaixo, sendo N1 número de funcionários que iniciam a atividade no domingo e N7 o número de funcionários que iniciam a atividade no sábado. N1= 16.333, N2= 18, N3= 15, N4= 15, N5= 19 e N6=14 e N7= 16 Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 26 n func. Z X s s sujeito a : alocados n alocacao s, n . X s funcionarios n s X s, n 0 Figura 3.2- Modelo correios pelo GAMS. 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 Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 27 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 R$ 50 R$ 90 R$ 120 R$ 65 R$ 92 R$ 140 produção Terceirização Índices: p: associado à produção. j: associado aos recursos. 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. cust: associado ao custo de terceirização t. demandap,: associado a decisão unitária de produção e terceirização. demandasp: associado a demanda do produto p que pode ser fabricado ou terceirizado. Variáveis. Z relacionado à função objetivo. Mincp,: quantidade a ser produzida e terceirizada do produto p visando a obtenção do menor custo. Produzidop: quantidade a ser fabricada do produto p. Terceirizadop: quantidade a ser terceirizada do produto p. Equações: Customin: calcula o custo mínimo. Consumop: calcula o consumo do recurso j pelo produto p. Decisãop,t: calcula a decisão entre produzir e terceirizar. Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 28 Modelo matemático: customin. Z produzido p .custo p terceirizado p .cus t p t Sujeito a : consumo j .. produzirp, j .produzido p A j p produzido p terceirzado p demandas p minc, produzido, terceirizado 0 A figura 3.3 resume o desenvolvimento desse modelo em GAMS. Desenvolvimento e Otimização de Modelos Lineares Práticos Por Meio do GAMS______________ 29 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 lucro máximo= R$ 43.900,00. Capítulo 4 4. DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS DINÂMICOS A maioria dos problemas de otimização práticos são multiperíodo ou dinâmicos, 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: i: associado ao produto veleiro. t: associado aos trimestres. Na linguagem GAMS há outra função chamada alias, esta função permite a inclusão de subíndices no modelo matemático. Neste caso vamos criar 2 subíndices, associados ao índice principal t t,textra: associado à produção utilizando horas extras no trimestre t. t,stoks: associado ao estoque do produto veleiro no trimestre t. Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 31 Parâmetros: Demandat: associado à demanda requerida do produto i para cada trimestre t. Producaot: associado à produção máxima para o produto i para cada trimestre t. Mt,i: associado à produção do produto i usando a mão de obra normal no trimestre t. Extratextra,i: associado à produção do produto i utilizando horas extras no trimestre t. Estocagemstoks,i: associado à estocagem do produto i no trimestre t. I0t,i,: associado ao estoque inicial do produto i no trimestre t. Contrt: controle de estoque inicial. Variáveis: Z função objetivo. produtoextrat,i: produção do produto i com mão de obra extra no trimestre t. produtoestoquet,i: estoque do produto i no trimestre t. Equações: Mincusto: calcula o custo mínimo da função objetivo. Limitet: calcula a produção do produto i no trimestre t. fabricaot: calcula o limite fabricado em horas disponíveis. calculoestoquet: calcula a capacidade de estoque no trimestre t. Z produto t,i .M t,i t,i produtoextra textra,i .extra textra,i textra,i produtoest0ques stoks, i .estocagem stoks,i stoks, i sujeito a : limite t . produto t,i produtoextra t,i I0t ,i produtoestoque t -1,i demanda t i i i fabricacao t produto t,i producao t i calculoestoque t produtoestoque t,i produto t,i produtoextra t,i I0 t,i i produtoestoque t -1,i i demanda t i produtos t,i , produtoextra t,i , produtoestoque t,i 0 A Figura 4.1 mostra este modelo em linguagem GAMS. i Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 32 Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 33 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 Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 34 término da 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 Meses de duração Retorno ao final do disponível no da aplicação investimento início dos meses 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. Equações: Aplicações: calcula a função objetivo. Cálculom: calcula o valor aplicado em cada tipo de investimento. Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 35 Aplicações.. Min Z UtilizadoA1 UtilizadoB1 UtilizadoC1 UtilizadoD1 sujeito a : n Investimentos j, a,m .Utilizado j,a D m j, a Utilizado j,a 0 A Figura 4.2 contempla o modelo fluxo de caixa em linguagem GAMS. Figura 4.2- Modelo fluxo de caixa em linguagem GAMS. Desenvolvimento e Otimização de Modelos Dinâmicos____________________________________ 36 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çãomaterial-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. Capítulo 5 5. DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS INTEIROS 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 Projeto 1 Investimento Inicial/ (UM 1.000,00) R$ 150,00 Valor Presente p/ I= 10% p/UM 1.000,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. Parâmetros: Investimentop: capital disponível para investir no projeto p. Desenvolvimento e Otimização de Modelos Inteiros______________________________________ 38 VPLp: Valor presente do projeto p. Variáveis: Z: Função objetivo MAXVPLp: associado à escolha do projeto p. Modelo matemático: n Max Z MAXVPL p .VPL p p sujeito a : 6 MAXVPL p 1 p MAXVPL p .Investimento p 650 MaxVPL p 0, 1 Desenvolvimento e Otimização de Modelos Inteiros______________________________________ 39 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.1. 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.1- Dados para a construção da nova Fábrica. Capital Decisão Sim ou Não VPL 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 Desenvolvimento e Otimização de Modelos Inteiros______________________________________ 40 Solução: Modelo Matemático: n Max Z selecao i, j .VPL i, j i, j sujeito a : n selecao i, j .capital i, j 25.000.000 Restrição orçamentária i, j selecao"itajuba", "fabrica" selecao"itajuba", "deposito" selecao i, j 0, 1 A Figura 5.2 mostra este modelo em linguagem GAMS. Desenvolvimento e Otimização de Modelos Inteiros______________________________________ 41 Figura 5.2- Modelo MIP2 em linguagem GAMS. Solução ótima: Construir tudo em Guaratinguetá. Gerando um VPL máximo de R$ 8.000.000,00. Repare que utilizamos o solver MIP (CPLEX 12.1.0), sendo este solver o mais adequado para resolver problemas mistos, binários e inteiros. Capítulo 6 6. DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS DE REDES 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______________________________________ 43 Figura 6.2- Exemplo de problemas de transporte. 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/ Recife Salvador Manaus Capacidade Rio 25 20 30 2000 SP 30 25 25 3000 BH 20 15 23 1500 Demanda 2000 2000 1000 Consumidor Solução: Índices: i: associado às fábricas j: associado aos destinos. Parâmetros: Custoi, j: associado ao envio da fábrica i para o destino j. Desenvolvimento e Otimização de modelos de redes______________________________________ 44 Capacidadei: associado à capacidade máxima de armazenagem da fábrica i. Demandasj: associado à demanda requerida pelo destino j. Variáveis: Z: função objetivo. Mincustoi, j: associada à quantidade enviada da fábrica i para o destino j ao menor custo. MODELO MATEMÁTICO: n Z envio i, j .custo i, j i, j sujeito a : envio i, j capacidade i envio i, j Demanda j j i envio i, j 0 A Figura 6.3 mostra este modelo em GAMS. Desenvolvimento e Otimização de modelos de redes______________________________________ 45 Figura 6.3: Modelo Rede 1. Desenvolvimento e Otimização de modelos de redes______________________________________ 46 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ó Neste caso a oferta é maior que a demanda. A Figura 6.5 contempla este exemplo modelado em linguagem GAMS. Desenvolvimento e Otimização de modelos de redes______________________________________ 47 Figura 6.5- Exemplo de modelo de rede em transportes. Desenvolvimento e Otimização de modelos de redes______________________________________ 48 6.2 DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS DE REDES EM PROBLEMAS DE ESCALA DE PRODUÇÃO Uma empresa fornece motores para um grande número de equipes de fórmula 1. A companhia detém uma série de contratos de entregas futuras programadas para o próximo ano. As entregas deverão ocorrer trimestralmente, de acordo com as necessidades das equipes. A Tabela a seguir resume por trimestre as entregas programadas, a capacidade máxima de produção e o custo unitário de produção. As entregas são feitas no final do trimestre e os motores podem ser armazenados por quantos trimestres forem necessários ao custo de 0,015 milhão de reais por trimestre. A diretoria deseja minimizar os custos totais de produção (produção + armazenagem). Quantos e quando os motores pedidos devem ser produzidos e entregues? Pedidos Capacidade de Custos unitários em milhares de Contratados Produção reais 1 10 25 1,08 2 15 35 1,11 3 25 30 1,1 4 20 10 1,13 Trimestre Para resolver este problema como um problema de transporte, precisamos primeiramente determinar quais serão as fontes, os destinos e as variáveis de decisão. Solução: Índices: i: associado à produção dos motores. j: associado à entrega dos motores. t: associado aos trimestres. Parâmetros: Custoi, t: associado ao custo de produção. Capacidadei: capacidade máxima de produção. Contratosj, t: associado à demanda dos motores em cada trimestre. Desenvolvimento e Otimização de modelos de redes______________________________________ 49 Demandasj, i, t: associado à entrega do motor produzido no trimestre t a ser entregue nos trimestres. capacidadesp11i, t: associado à entrega dos motores produzidos no trimestre t. estoquest: associado ao custo de estoque no trimestre t. estoquessi, t: associado ao estoque no trimestre t. Variáveis: Z: função objetivo. Envioi, t: quantidade a ser enviada do motor produzido no trimestre t. Stokt: associada à ociosidade no trimestre t. n n i ,t t Z envio i, t .custo i, t stok t .estoques t sujeito a : n envio i, t envio i, t t . capacidade i, t stok t .estoquess i, t capacidadei t .demandas j, i, t contratos j, t i n stok t 30 t envio i, j 0 stok t 0 Desenvolvimento e Otimização de modelos de redes______________________________________ 50 Desenvolvimento e Otimização de modelos de redes______________________________________ 51 Figura 6.6 - Exemplo de modelos de produção. 6.3 DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS DE REDE DE DISTRIBUIÇÃO Problemas que consideram múltiplas fontes, centros consumidores e locais intermediários por onde os produtos simplesmente passam são denominados de problemas de rede de distribuição. Os problemas de transporte podem ser vistos como uma simplificação do problema de rede de distribuição de custo mínimo, onde as localizações intermediárias não existem. Exemplo 1: Uma montadora de tratores está iniciando as suas operações no país, construindo duas fábricas: uma na Bahia e outra em São Paulo. A montadora está estudando a forma de distribuição de seus carros para as diversas revendas, localizadas nos estados de Goiás, Rio de Janeiro, Minas Gerais, Paraná, Santa Catarina e Rio Grande do Sul, que minimize o custo total de distribuição. As capacidades instaladas de cada uma das fábricas, as demandas das revendas, bem como os custos unitários de transporte entre fábricas e revendas estão evidenciadas na rede abaixo: Desenvolvimento e Otimização de modelos de redes______________________________________ 52 Figura 6.7- Diagrama de Rede do exemplo 1. Neste problema a oferta é maior que a demanda e, portanto, adota-se que as entradas- saídas ≤ oferta do nó. Solução: Índices: i: associado aos nós de oferta. j: associado aos nós de demanda. Parâmetros: Capacidadei: associado à capacidade máxima dos nós de oferta. Demandaj: associado à demanda máxima do destino j. Custoi, j: associado ao custo de envio da origem i para o destino j. Redei j: associado à distribuição da origem i para o destino j. Redesi, j: associado à distribuição da rede. Variáveis: Z: função Objetivo. Envioi, j: quantidade a ser enviada da origem i para o destino j. Desenvolvimento e Otimização de modelos de redes______________________________________ 53 Modelo: n Z envio i, j .custo i, j i, j sujeito a : envio i, j . rede i, j capacidade i envio i, j . redes i, j Demanda j j i envio i, j 0 A Figura 6.8 mostra esse modelo em linguagem GAMS. Solução ótima: Origem/Destino SC BA SP 100 D 50 Custo mínimo MG GO RJ 200 150 150 RS 200 300 250 R$ 28.000,00 PR Desenvolvimento e Otimização de modelos de redes______________________________________ 54 Figura 6.8- Modelo distribuição em GAMS. A variável D é uma adição de uma origem fictícia, pois a demanda é maior que a oferta e, em modelos de transporte a oferta total = demanda total. A leitura é a seguinte: não foram enviadas 50 e 250 unidades para SC e RS respectivamente. 6.4 DESENVOLVIMENTO E OTIMIZAÇÃO DE PROBLEMAS DO MENOR CAMINHO O problema do menor caminho representa um caso especial de problemas de redes, em que os arcos significam a distância entre dois pontos (vértices ou nós). Quando desejamos achar a rota que une estes pontos com distância mínima entre as possíveis rotas, temos um problema do tipo do menor caminho. Em problemas do menor caminho haverá sempre dois tipos de vértices especiais chamados de origem e destino. Entre estes nós há nós intermediários, que podem representar cidades que conectam rodovias, subestações em problemas de distribuição de energia, e assim por diante. Exemplo 2: A fábrica de artigos e decoração Águia, localizada em Lambari, Minas Gerais, deve entregar uma grande quantidade de peças na cidade de Baependi, localizada no mesmo estado. A empresa quer saber qual o caminho que seu caminhão de entregas deve percorrer para Desenvolvimento e Otimização de modelos de redes______________________________________ 55 minimizar a distância total percorrida. A Figura 6.9 mostra as cidades e as respectivas distâncias. Figura 6.9- Mapa rodoviário que liga as cidades de Lambari a Baependi Solução: Índices: i: associado aos nós de oferta. j: associado aos nós de demanda. Parâmetros: Distânciai, j: associado à distância da origem i para o destino j. Circuitoi, j: associado à rede entre a origem i para o destino j. Circuito2i, j: associado à rede entre a origem i para o destino j. Circuito3i, j: associado à rede entre a origem i para o destino j. Circuito4i, j: associado à rede entre a origem i para o destino j. Cicloi, j: associado à rede entre a origem i=lambari para o destino j. Ciclosi, j: associado à rede para o destino final. Nosi: associado ao nó especial da origem. Nosj: associado ao nó especial do destino final. Variáveis: Z: função Objetivo. Desenvolvimento e Otimização de modelos de redes______________________________________ 56 Envioi, j: quantidade a ser enviada da origem i para o destino j. Modelo: n Z envio i, j .distancia i, j i, j sujeito a : envio i, j . ciclo i, j Nos i envio i, j . ciclo i, j Nos j envio i, j . circuito i, j 0 envio i, j . circuito2 i, j 0 envio i, j . circuito3 i, j 0 envio i, j . circuito4 i, j 0 j i i i i i envio i, j 0;1 A Figura 6.10 mostra esse modelo em GAMS. Desenvolvimento e Otimização de modelos de redes______________________________________ 57 Figura 6.10- Problema do menor caminho em GAMS. Desenvolvimento e Otimização de modelos de redes______________________________________ 58 6.5 DESENVOLVIMENTO E OTIMIZAÇÃO DE PROBLEMAS DE FLUXO MÁXIMO O tipo de problema de fluxo máximo é utilizado quando queremos maximizar a quantidade de fluxo de um ponto de origem para um ponto de destino, sujeitos a restrições de capacidade de fluxo nos arcos. Estes problemas geralmente envolvem um fluxo de materiais como água, óleo, gás, energia por meio de uma rede de tubos ou cabos, porém, também podem representar o fluxo mínimo de carros em uma malha rodoviária, de produtos em linha de produção, e assim por diante. Exemplo: Uma empresa distribuidora de gás deseja determinar a quantidade máxima de metros cúbicos por segundo de gás que pode bombear da estação de campos para o centro consumidor do Rio de Janeiro, por meio da rede de gasodutos. A Figura 6.11 ilustra a estrutura da rede de distribuição e apresenta a capacidade de fluxo máximo nos trechos em metros cúbicos por segundo. Figura 6.11- Rede de gasodutos que ligam campos ao Rio de Janeiro. Solução: Índices: i: associado aos nós de oferta. ii: associado aos nós de destino. Parâmetros: Desenvolvimento e Otimização de modelos de redes______________________________________ 59 Capacidadei, ii: associado à capacidade máxima de fluxo de cada nó. Circuitoi,ii: associado ao circuito do nó A. Circuito2i,ii: associado ao circuito do nó 1. Circuito3i, ii associado ao circuito do nó 2. Circuito4i, ii: associado ao circuito do nó 3. Circuito5i, ii: associado ao circuito do nó 4. Circuito6i, ii: associado ao circuito do nó B. Variáveis: Z: função Objetivo. Envioi, ii: quantidade a ser enviada da origem i para o destino j. Z envio "b", "a" sujeito a : envio i, ii capacidade i, ii envio i, ii .circuito i, ii 0 envio i, ii .circuito2 i,ii 0 envio i, ii .circuito3 i, ii 0 envio i, ii .circuito4 i,ii 0 envio i, ii .circuito5 i, ii 0 envio i, ii .circuito i, ii 0 i, ii i, ii i, ii i, ii i, ii i, ii envio i, ii A Figura 6.12 contempla esse modelo em linguagem GAMS. Desenvolvimento e Otimização de modelos de redes______________________________________ 60 Desenvolvimento e Otimização de modelos de redes______________________________________ 61 Figura 6.12: Modelo fluxo máximo em GAMS. Solução ótima: Origem/destino A A 1 2 1 2 40 20 3 4 20 20 B 20 3 20 4 40 B 60 Fluxo máximo BA= 60. 6.6 DESENVOLVIMENTO E OTIMIZAÇÃO DE PROBLEMAS DE ESCALA DE PRODUCAO COMO MODELOS DE REDE POR MEIO DO GAMS O caso dos problemas de escala de produção pode ser visto como problemas de transporte na forma tradicional. Exemplo: A fábrica de eletrodomésticos Galáctica deseja realizar o escalonamento de sua produção de liquidificadores para os próximos quatro meses. A fábrica pode produzir mensalmente, em jornada normal, 150.000 unidades a um custo unitário de R$ 15. Por meio do pagamento de horas extras, a capacidade mensal de produção da fábrica pode ser aumentada em 50.000 liquidificadores, a um custo de produção unitário de R$ 22 (somente aos adicionais). Existe a possibilidade de armazenagem ilimitada de unidades de um mês para o outro a um custo unitário mensal de R$ 3. Sabendo que as demandas de liquidificadores para os próximos Desenvolvimento e Otimização de modelos de redes______________________________________ 62 quatro meses são de 120.000, 200.000, 120.000 e 180.000, resolva o problema utilizando-se da linguagem GAMS. Do nó Para o nó Custo 1 A 15 1 E 0 2 A 22 3 B 15 3 E 0 4 E 0 4 B 22 5 C 15 5 E 0 6 C 22 6 E 0 T D 15 T E 0 8 D 22 8 E 0 A B 3 A C 3 C D 3 Os nós ímpares são os nós de produção sem horas extras. As letras a, b, c e d referem-se à demanda por mês, o nó E é um nó fictício utilizado para equilibrar a oferta com a demanda. Solução: Índices: i: associado aos nós de oferta. j: associado aos nós de destino. Parâmetros: Desenvolvimento e Otimização de modelos de redes______________________________________ 63 Custoi ,j: associado ao custo entre os nós de saída com os nós de entrada. Cicloi,j: associado ao circuito entre os nós com o nó fictício. Circuitoi, j: associado ao circuito do nó A. Circuito2i, j: associado ao circuito do nó 1. Circuito3i, j associado ao circuito do nó b. Circuito4i, j: associado ao circuito do nó c. Circuito5i, j: associado ao circuito do nó e. Variáveis: Z: função Objetivo. Envioi, ii: quantidade a ser enviada da origem i para o destino j. Z envio i, j .custo i, j sujeito a : envio i, j .ciclo i, j demanda i j envio i, j .circuito i, j 120000 envio i, j .circuito2 i, j 200000 envio i, j .circuito3 i, j 120000 envio i, j .circuito4 i, j 180000 envio i, j .circuito5 i, j 180000 envio i, j A Figura 6.13 contempla este modelo em linguagem GAMS. Desenvolvimento e Otimização de modelos de redes______________________________________ 64 Desenvolvimento e Otimização de modelos de redes______________________________________ 65 Desenvolvimento e Otimização de modelos de redes______________________________________ 66 Figura 6.13: Modelo de escala de produção formulado em GAMS. 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 Tempo [hs] imediato 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.14- Atividades de um projeto de manutenção Desenvolvimento e Otimização de modelos de redes______________________________________ 67 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: C A 6 ou C A 6 C B 4 ou C B 4 A figura 6.15 mostra a modelagem em GAMS Desenvolvimento e Otimização de modelos de redes______________________________________ 68 Desenvolvimento e Otimização de modelos de redes______________________________________ 69 Figura 6.15- Modelo CPM EM GAMS Exercícios para diversão. Desenvolvimento e Otimização de modelos de redes______________________________________ 70 1) Análise a rede abaixo e faça o que é pedido. Considere que os números indicados em cada aresta significam o número de quilômetros necessários para um automóvel percorrer a estrada entre duas cidades indicadas pelo nós extremos das arestas observadas. Monte o modelo e determine a rota que um automóvel deve seguir para sair de Chapecó e chegar a porto alegre, percorrendo a menor quantidade de quilômetros possível. 2) Considere a reconstrução de um armazém que será feito. As atividades associadas são apresentados na Tabela a seguir: Atividad Descrição e A Demolir o armazém B Comprar materiais para atividade Predecessor Tempo imediato [dias] - 2 de - 1 alvenaria 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 Desenvolvimento e Otimização de modelos de redes______________________________________ 71 G Fazer fundações de concreto B, D 2 H Fazer acesso E 1 I Levantar paredes de alvenaria B, 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 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? 3) 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? 72 Capítulo 7 7. DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS DE OTIMIZAÇÃO COMBINATÓRIA 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_______________________73 n n Min Z C i , j . X i , j i 1 j 1 sujeito a : n X i 1 i, j Restrição de saída i, j Restrição de chegada n X j 1 u i u j nx i, j n - 1 (i j; i 2, 3,..., n; j 2,3,..., n) São subrotas X i , j 0,1, u j 0 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 subrotas ou subcircuitos garantem que a solução ótima não contenha subcircuitos. Exemplo1: PARA Sede Sede DE P1 P2 5 P3 P4 3.8 2.2 2.4 2.6 3.1 5.1 1.6 2.8 P1 5 P2 3.8 2.6 P3 2.2 3.1 1.6 P4 2.4 5.1 2.8 2.3 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_______________________74 Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________75 , Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________76 Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________77 Desenvolvimento e Otimização de Modelos de otimização combinatória_______________________78 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_______________________79 Figura 7.2-Modelo Caixeiro Viajante otimizado pelo GAMS. OBS: com n vértices há ( n 1)! ciclos distintos. 2 Capítulo 8 8. DESENVOLVIMENTO E OTIMIZAÇÃO DE MODELOS DE ANÁLISE POR ENVOLTÓRIA DE DADOS 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. No 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_________________ 81 Se uma unidade atingiu 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) O modelo DEA CCR (Charnes, Cooper e Rhodes, 1978) é apresentado no modelo abaixo. s u y j jc j 1 Max Ec m v x i ic i 1 s u y j jk j 1 S.a.: 1, k 1,2, , c, , n m v x i ik i 1 uj 0 , j, vi 0 , i Onde: c é o índice da unidade que está sendo avaliada. O problema acima envolve a procura de valores para u e v, que são os pesos, de modo que maximize a soma ponderada dos outputs (output “virtual”) dividida pela soma ponderada dos inputs (input “virtual”) da DMU em estudo, sujeita à restrição de que esse quociente seja menor ou igual a 1, para todas as DMUs. Esta função está sujeita à restrição de que, quando o mesmo conjunto de coeficientes de entrada e saída (vis e ujs) for aplicado a todas as outras unidades de serviços que estão sendo comparadas, nenhuma unidade de serviço excederá 100% de eficiência ou uma razão de 1,00.. Porém, o modelo acima não é linear e sim um problema de programação fracionária. Entretanto, o modelo linearizado é descrito abaixo. s u Max Ec yjc j j 1 S.a.: m v x i ic 1 i 1 s m j 1 i 1 uj yjk - vi xik 0 , k 1,2, ...,c,, n uj, vi 0 , x, y. Esta forma do problema é conhecida como problema dos multiplicadores, como também são chamados os pesos, uj e vi. Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 82 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) Capital Mão de obra Saídas (y) 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, uma para cada DMU. A Figura 8.1 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_________________ 83 Figura 8.1- 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.2 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_________________ 84 Figura 8.2- 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.3 mostra este exemplo. Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 85 Figura 8.3: Modelo DEA GLOBAL. Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 86 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. Outro tipo de modelo DEA que iremos ver nesta apostila é conhecido por BCC (Banker, Charnes e Cooper, 1984). No modelo DEA CCR há retornos de 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 Max Eff 0 j .y j0 u * j S.a.: v x i ic 1 i 1 v x i j 1 ik u j . y jk u * 0 ,k j uj, vi 0 , j, i. u* 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.4 mostra as diferenças entre estes modelos. Figura 8.4- Modelos DEA Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 87 A figura 8.5 contempla a solução deste exemplo pelo modelo BCC ou (VRS). Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 88 Figura 8.5- Modelagem em GAMS modelo DEA BCC ou VRS Neste exemplo foi necessário acrescentar outro objetivo (sets) chamado u que vai pertencer a variável do modelo BCC. Resolva os exercícios abaixo utilizando-se da linguagem de modelagem GAMS. Max Z 9w 1 4 w 2 16w3 sujeito a : 9w 1 4 w 2 16w3 - 5v1 14v 2 0 1) 5w 1 7 w 2 10w3 - 8v1 15v 2 0 4w 1 9w 2 13w3 - 7v1 12v 2 0 5v1 14 v 2 0 w j 0,001, v k 0,001 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) Agências Despesas menos Caixa Plataforma Gerente (excl. pessoal produtivas [pessoas] [pessoas] [pessoas] e aluguel) [$] A1 10,0 5,0 1,0 652.566 A3 3,0 2,5 1,0 468.637 A4 4,0 2,5 1,0 350.477 A5 9,0 7,0 1,0 1.059.526 A6 3,0 2,5 1,0 235.974 A8 4,5 3,5 1,0 353.235 A9 3,5 2,0 1,0 341.994 A11 7,5 3,5 1,0 768.338 A12 2,5 2,0 1,0 269.998 A13 9,0 6,5 1,0 1.112.090 Economia potencial (Saída) Área da agência [pé2] 3.818 1.728 1.941 5.640 2.200 1.350 2.346 3.243 1.422 5.400 Caixa 4,5 1,9 2,3 0,7 1,6 1,5 1,2 3,3 1,1 0,1 PlataGerente forma 1,8 1,6 1,4 1,9 1,4 1,3 0,7 0,7 1,1 0,1 0,3 0,7 0,7 0,1 0,6 0,3 0,4 0,2 0,7 - Despesas 222.928 295.989 189.745 367.020 122.474 10.526 116.716 329.403 122.433 131.389 Área da agência 1.304 1.133 1.051 1.899 1.556 40 976 774 889 1.477 Desenvolvimento e Otimização de modelos de análise por envoltória de dados_________________ 89 Recursos empregados (Entrada) Agências Despesas menos Caixa Plataforma Gerente (excl. pessoal produtivas [pessoas] [pessoas] [pessoas] e aluguel) [$] A14 3,5 4,0 1,0 433.868 A15 2,0 2,0 1,0 253.902 A18 4,0 2,5 1,0 571.090 A20 7,0 4,0 1,0 666.133 A22 7,5 3,5 1,0 929.668 A26 3,5 3,0 1,0 411.922 A27 5,5 5,5 1,0 545.976 A28 6,0 5,0 1,0 914.990 A29 7,0 4,0 1,0 568.054 A30 15,0 13,0 1,0 1.402.615 A31 5,5 6,0 1,0 679.451 A32 3,0 2,0 1,0 367.828 A33 17,5 18,0 1,0 3.191.789 Total 143,0 109,5 23,0 16.550.121 Economia potencial (Saída) Área da agência [pé2] 1.700 1.486 1.420 3.180 1.865 3.092 2.781 2.187 6.686 9.963 3.133 1.637 8.000 76.218 Caixa 0,7 1,1 2,0 3,0 5,2 1,0 1,9 1,8 1,7 4,0 0,8 0,9 3,3 45,6 PlataGerente forma 2,0 1,3 0,8 1,5 1,5 1,0 3,1 1,6 0,9 6,1 2,7 0,6 10,6 45,7 0,4 0,7 0,4 0,4 0,3 0,3 0,3 0,2 0,3 0,1 0,5 0,2 8,1 Área da agência 81.024 502 135.920 961 206.693 361 280.853 1.176 496.072 605 112.147 1.491 188.394 960 233.870 60 176.227 3.669 551.272 5.377 94.692 824 107.934 480 2.510.589 2.016 7.084.310 29.581 Despesas Desenvolva e otimize os modelos desse problema. Avalie o dual e conclua quais são as melhores agências e o que deveria ser feito pelo banco para que as agências não eficientes se tornem eficientes. 3) Considere as 6 empresas do setor X listadas na Tabela a seguir Empresa A B C D E F Receita 800.331 780.880 1.582.624 1.977.624 3.105.444 2.349.306 Ativo 1.487.845 1.599.784 3.886.613 5.147.807 5.299.049 7.475.831 Empregados 4.478 3.320 4.176 5.988 6.646 11.748 a- Utilize a DEA para classificar as empresas em termos de eficiência. Considere que as entradas são definidas pelos ativos e empregados e que a saída seja definida pela receita. Capítulo 9 9 Aplicações Reais O próximo exemplo foi adaptado de Silva (2009). Uma usina deseja programar sua produção para as próximas 5 semanas. Abaixo estão algumas informações sobre esta usina. Matéria-Prima: Própria: 150.000 toneladas Comprada: 100.00 toneladas. Estas matérias-primas devem ser consumidas totalmente nestas 5 semanas. Porcentagem de MP comprada por semana. Semana 1: 100% Semana 2: 100% Semana 3: 100% Semana 4: 80% Semana 5: 90% Porcentagem de MP própria por semana. Semana 1: 80% Semana 2: 80% Semana 3: 80% Semana 4: 80% Semana 5: 90% Capacidade de transporte da frota própria em toneladas: Semana 1: 47250 Semana 2: 47250 Semana 3: 51975 Semana 4: 51975 Aplicações reais___________________________________________________________________ 91 Semana 5: 51975 Capacidade de transporte da frota terceirizada em toneladas: Semana 1: 37250 Semana 2: 27250 Semana 3: 19750 Semana 4: 14000 Semana 5: 15.000 Capacidade de transporte da frota terceirizada em toneladas: Semana 1: 37250 Semana 2: 27250 Semana 3: 19750 Semana 4: 14000 Semana 5: 15.000 Capacidade de transporte da frota condomínio em toneladas: Semana 1: 2250 Semana 2: 3250 Semana 3: 8750 Semana 4: 1400 Semana 5: 1000 Estes transportes são alocados na parte agrícola, pois estas matérias primas são colhidas no campo. A Tabela abaixo mostra os níveis de moagem semanal, logo o total colhido na semana não deve ser maior que a capacidade máxima de moagem e nem menor que a capacidade mínima. Semana Moagem Máxima Moagem Mínima 1 40.00 30.200 2 42.000 31.600 3 45.000 32.500 4 50.000 33.000 5 55.000 36.000 Aplicações reais___________________________________________________________________ 92 A Tabela a seguir contempla a capacidade de estocagem em toneladas. Produto Estoque próprio Estoque terceirizado A 15.000 10.00 C 3000 0 D 14.000 3.000 A Tabela a seguir aborda o custo logístico agrícola em R$/toneladas. Semana Frota própria Frota terceirizada Frota condomínio 1 10 8 9 2 12 10 11 3 9 11 12 4 8 10 8 5 10 8.7 8 A próxima tabela contempla o custo por processo. No caso desta usina somente um processo pode ser utilizado por semana, logo essa é uma restrição binária. Processos Semana 1 Semana 2 Semana 3 Semana 4 Semana 5 Processo 1 7.3 6.74 6.26 6.26 6.26 Processo 2 12 10 11 11 11 Processo 3 9 11 12 12 12 Processo 4 8 10 8 8 8 Processo 5 10 8.7 8 8 8 A próxima Tabela mostra o rendimento por processo, ou seja, qual é o nível de produção do produto x utilizando o processo y na semana z. Rendimento Semana 1 Semana 2 Semana 3 Semana 4 Semana 5 A.proc1 B.proc1 C.proc1 0,11 0,20 0,22 0,19 0,13 0,23 0,12 0,10 0,23 0,06 0,06 0,19 0,23 0,07 0,25 Aplicações reais___________________________________________________________________ 93 A.proc2 B.proc2 C.proc2 A.proc3 B.proc3 C.proc3 A.proc4 B.pro4 C.proc4 A.proc5 B.proc5 0,13 0,20 0,20 0,20 0,17 0,13 0,17 0,20 0,14 0,11 0,14 0,21 0,12 0,13 0,25 0,18 0,05 0,14 0,21 0,20 0,21 0,13 0,11 0,07 0,19 0,22 0,09 0,05 0,16 0,22 0,14 0,10 0,12 0,12 0,07 0,19 0,14 0,14 0,25 0,08 0,14 0,11 0,07 0,13 0,22 0,21 0,19 0,06 0,13 0,10 0,25 0,06 0,13 0,12 0,11 C.proc5 0,19 0,11 0,06 0,12 0,21 A próxima Tabela aborda o custo de estocagem em R$/toneladas. Nesta tabela é disposto o custo por produto no estoque, ou seja, eprop (estoque próprio) e eterc(estoque terceirizado). Estoque Semana 1 Semana 2 Semana 3 Semana 4 Semana 5 A.eprop 4,00 9,00 3,00 9,00 5,00 4,00 3,00 10,00 9,00 5,00 7,00 10,00 7,00 8,00 3,00 5,00 4,00 9,00 3,00 4,00 10,00 8,00 8,00 10,00 5,00 3,00 9,00 5,00 4,00 A próxima Tabela contempla o custo por fonte de matéria-prima. 6,00 B.eprop C.eprop A.eterc B. eterc C. eterc Matéria-Prima Semana 1 Semana 2 Semana 3 Semana 4 Semana 5 Própria Comprada 8.4 9 8.55 9.6 10 20 22 25 30 27 A Tabela a seguir mostra o preço de venda desses produtos. Aplicações reais___________________________________________________________________ 94 Produtos Semana 1 Semana 2 Semana 3 Semana 4 Semana 5 A B C 530,00 745,00 510,00 680,00 579,00 527,00 726,00 567,00 892,00 359,00 690,00 585,00 998,00 977,00 1000,00 A demanda pelo produto A é de 25.000 toneladas, B=2.000 e C=1.000, ambas as demandas são referentes à quinta semana. Os produtos A e C possuem estoques iniciais no estoque próprio nas quantidades de 500 e 1000 respectivamente. Formule o modelo que auxilie às decisões agrícolas e industriais desta usina. Dica: ao todo são ( 134 variáveis e 155 restrições e 25 variáveis binárias). 4- Considere que no exemplo extraído de Silva (2009) essa usina exporte seus produtos e, para tanto utiliza de frota própria e terceirizada para realização deste transporte. O transporte é feito para dois destinos. A Tabela abaixo mostra com mais detalhes. Produtos Semana 1 Semana 2 Semana 3 Semana 4 Semana 5 A.Dest1 50 40 60 B.Dest1 40 20 A próxima Tabela aborda o preço de venda dos produtos exportados 50 Produtos Semana 1 Semana 2 Semana 3 Semana 4 Semana 5 A.Dest1 784,00 883,00 974,00 757,00 836,00 B.Dest1 944,00 918,00 929,00 785,00 742,00 A Tabela a seguir mostra o custo de transporte. Tterc= transporte terceirizado, Tprop= transporte próprio. Produtos A.Dest1.tterc B.Dest1.tprop A.Dest1.tprop A.Dest2.tterc Semana 1 Semana 2 Semana 3 Semana 4 Semana 5 81,00 98,00 86,00 71,00 92,00 86,00 91,00 93,00 86,00 72,00 89,00 93,00 78,00 87,00 71,00 95,00 95,00 100,00 74,00 82,00 Aplicações reais___________________________________________________________________ 95 Faça as análises inserindo esses dados no modelo matemático. 5- Resolva os problema abaixo utilizando-se dos modelos BCC e CCR. Loja Copacabana Ilha do Governador Ipanema Jacarepaguá Tijúca Angra dos Reis Miracema Niterói Nova Friburgo Petrópolis Resende Faturamento [R$ M] 29,24 18,39 30,54 20,48 23,27 28,98 27,85 31,81 17,99 23,94 15,17 Área [m2] 1.002 1.192 1.087 1.183 1.245 1.357 1.127 1.291 1.169 1.603 1.303 Empregados 140 147 103 160 156 136 160 159 106 142 119 Renda região [R$] 3.000 2.500 2.900 1.500 1.800 2.700 800 1.200 900 1.400 700 a) Analise os resultados duais dos modelos, e esboce um plano para tornar eficientes as unidades que não forem eficientes. 6- Resolva este problema pelo modelos CCR e BCC e analise os resultados. Empresa Telerj Telemig CTBC Telecom MG Telest Telebahia Telergipe Telasa Telpe Telpa Telern Teleceará Telepisa Telma Telepará Teleamapá Teleamazon Telaima Telesc MN 66.715 104.585 17.858 25.006 93.584 8.366 6.268 33.575 16.296 13.949 3.233 6.971 176 20.711 4.379 447 1.898 92.233 Saídas P 898.157 650.575 83.923 133.454 289.541 32.158 45.267 129.859 51.858 58.218 170.784 41.227 58.613 114.351 12.061 47.623 7.402 182.877 AS 3.348.768 2.746.105 362.485 50.388 1.302.615 159.206 227.226 714.117 293.823 294.634 761.737 236.549 299.971 513.635 69.287 301.052 46.024 1.049.553 L 13.707 10.947 2.373 1.837 4.785 314 256 2.821 686 556 303 649 868 105 220 1.039 183 3.461 Entradas PT 99.951 73.407 7.465 1.669 54.439 6.776 11.681 41.304 13.519 12.607 34.874 10.554 15.296 23.521 2.055 1.042 1.602 25.623 AI 3.692.804 2.895.328 464.154 561.042 1.406.159 170.519 25.135 831.171 328.803 329.721 791.541 24.633 32.177 532.904 7.147 315.052 4.812 1.193.985 Aplicações reais___________________________________________________________________ 96 Telepar Sercomtel Telems CTBC Telecom MS Telemat Telegoiás CTBC Telecom GO Telebrasília Teleron Teleacre CRT CTMR Telesp Ceterp CTBC Telecom SP CTBCampo 99.189 7.281 9.766 165 1.802 71.272 1.194 20.617 9.766 1.815 222.006 3.492 487.631 6.483 10.429 15.537 Saídas 382.924 37.475 36.771 1.629 80.212 226.598 4.391 19.946 36.771 11.903 404.249 23.321 2.289.167 47.654 35.251 318.203 1.710.688 13.919 387.969 6.143 328.261 957 22.076 74.912 180.469 6.833 1.826.485 99.406 9.413.366 184.837 164.842 964.195 10.659 851 2.633 44 195 4.859 86 3.278 718 313 9.731 469 4.955 1.307 374 5.294 Entradas 46.327 2.227.874 2.203 154.499 1.055 472.702 163 7.788 13.745 451.478 38.487 1.155.173 588 30.402 20.175 884.852 6.345 253.011 2.924 93.604 53.347 2.101.056 2.015 120.935 223.445 11.185.983 3.017 217.837 2.784 209.829 21.577 1.081.897 REFERÊNCIAS BIBLIOGRÁFICAS ANDRADE, E. L., 2004, Introdução à Pesquisa Operacional, LTC, Rio de Janeiro,Brasil. BERTRAND, J. W. M. & FRANSOO, J. C. Operations management research methodologies using quantitative modeling. International Journal of Operations & Production Management, v.22, n°2. pp. 241-264, 2002. BROOKE, A.; KENDRICK, D. & MEERAUS, A. GAMS: Sistema geral de modelagem algébrica. São Paulo: Edgard Blücher, 1997. BRUNETTA, M. R. Avaliação da eficiência técnica e de produtividade usando Análise por Envoltória de Dados: Um estudo de caso aplicado a produtores de leite. Curitiba: Programa de Pós-graduação de Métodos Numéricos em Engenharia, Universidade Federal do Paraná, 2004, 113p. Dissertação (Mestrado). CAIXETA-FILHO, José Vicente . Pesquisa Operacional.:Técnicas de otimização em aplicadas a sistemas agroindustriais. 2º .ed. – São Paulo: Atlas, 2004. COLIN, C.C. Pesquisa Operacional: 170 aplicações em Estratégia, Finanças, Logística, Produção, Marketing e Vendas. Rio de Janeiro LTC, 2007. COLIN, E. C.; CIPPARRONE, F. A. M.; SHIMIZU, T. Otimização do custo de transporte na distribuição-armazenagem de açúcar. Produção, v. 9. n°1. pp. 23-30, 1999. BATISTA, F. D. Metodologia para o uso da análise por envoltória de dados no auxílio à decisão. Itajubá: Programa de Pós-graduação em Engenharia de Produção, Universidade Federal de Itajubá, 2009, 107p. Dissertação de Mestrado COOPER, W.W.; SEIFORD, L.M.; Tone, K. – Introduction to Data Envelopment Analysis and its uses. Springer – 2006. LACHTERMACHER, Gerson pesquisa operacional na tomada de decisão: Modelagem em Excel. 2º ed.- º 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. NIEDERAUER, C. A. P. Avaliação dos bolsistas de produtividade em pesquisa da engenharia de produção utilizando Data Envelopment Analysis. Florianópolis: Programa de Pós-Graduação em Engenharia de Produção, Universidade Federal de Santa Catarina, 1998. Dissertação (Mestrado). PAIVA, F. C. Eficiência produtiva de programas de ensino de pós-graduação em engenharias: uma aplicação do método Análise Envoltória de Dados-DEA. Florianópolis: Programa de Pósgraduação em Engenharia de Produção, Universidade Federal de Santa Catarina, 2000, 79p. Dissertação (Mestrado). PAIVA, R. P. O. MORABITO, R.. An optimization model for the aggregate production planning of a Brazilian sugar and ethanol milling company. Annals Operations Research. 169 (2009) 117-130. PRADO, Darci Santos do, Programação linear – Belo Horizonte MG: Editora de Desenvolvimento gerencial , 2003. ( Série Pesquisa Operacional , Vol.1) SOARES DE MELLO, J. C. C .B.; MEZZA, L.A.; GOMES E.G.; BLONDI NETO, L. Curso de Análise de Envoltória de Dados. Em: XXXVII Simpósio Brasileiro de Pesquisa Operacional, Gramado-RS, 2005. SILVA, A. F. Modelagem do planejamento agregado da produção de uma usina sucroalcooleira. Itajubá: Programa de Pós-graduação em Engenharia de Produção, Universidade Federal de Itajubá, 2009, 92p. Dissertação de Mestrado. 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. ANEXO A – LINGUAGEM DE MODELAGEM GAMS Durante as décadas de 50 e 60 fez-se um progresso substancial no desenvolvimento de algoritmos e códigos computacionais para resolver grandes problemas de programação matemática (PAIVA, 2006). Sendo que, na década posterior, não surgiu um grande número de aplicações das ferramentas que foram desenvolvidas. Conforme Brooke et al (1997) comentou o fato de que grande parte do tempo requerido para o desenvolvimento de um modelo era despendido na preparação dos dados e dos relatórios de saída. Portanto, foram estudados os meios para reduzir esse tempo, e nesse sentido desenvolveram-se os geradores de matrizes para a programação linear, que faziam transformações dos modelos matemáticos para a forma algorítmica exigida pelos softwares. O percussor para adequação desses objetivos foi o desenvolvimento das linguagens de modelagem (LMs). Dentre as LMs que se destacaram a década de 80 e início da década de 90, cita-se: CML(Conversational Modeling Language), a LPM (System for Constructing Linear Programming System), a LAMP (Language for Interactive General Optimization), LINGO (Language for Interactive General Optimization) e o GAMS (General Algebraic Modeling System). Essas LMs vêm adquirindo maiores significâncias para os modeladores, visto que os problemas analisados estão se tornando cada vez mais complexos, e as LMs propiciam que os modeladores dediquem cada vez mais tempo para solucionar problemas referentes ao modelo, e não a implementação computacional. O GAMS é uma LMs e foi projetada para o desenvolvimento e solução de modelos de programação matemática complexa (BROOKE et al, 1997). As principais vantagens intrínsecas a utilização do GAMS são: I. Fornecer uma linguagem de alto nível para uma representação compacta de modelos extensos e complexos; II. Permitir mudanças na especificação dos modelos de forma simples e segura; III. Permitir relações algébricas enunciadas de forma não ambígua; IV. Permitir descrições de modelos independentes dos algoritmos de solução; Linguagem de Modelagem GAMS ___________________________________________________ 100 V. Simplificar a preparação de dados de entrada e relatórios de saída e transformar automaticamente os dados para a forma requerida pelos pacotes de programação matemática. Além destas vantagens, o GAMS é um compilador baseado na teoria de banco de dados (quando se faz manipulação dos dados) e na teoria de programação matemática ( para descrição e solução dos problemas). GAMS também disponibiliza um conjunto de Solvers, que são pacotes com opções de várias técnicas de solução de problemas de programação matemática (p.ex: PL, PIM, PNL, MIQCP, MINLP, DNPLP...), que podem ser utilizados conforme a escolha do modelador, A UNESP-Guaratinguetá-SP possuiu o GAMS [23.4.3]e o solver CPLEX [12.1.0], para a solução do problema programação inteira mista (PIM). Solver CPLEX A sigla CPLEX é a combinação da letra C, em referência à linguagem de programação C utilizada no desenvolvimento deste algoritmo, com a terminação PLEX, em referência ao algoritmo simplex de solução de problemas de PL. Este solver foi desenvolvido pela CPLEX Optimization Inc., empresa fundada em 1988 com a ideia de comercializar algoritmos de PL que pudessem ser utilizados para solucionar, de forma rápida, problemas grandes e difíceis de programação linear. Atualmente o CPLEX é um produto de propriedade da ILOG S.A. A primeira versão do CPLEX (CPLEX 1.0) foi lançada em 1988 com suporte para solucionar problemas de PL por meio do método primal simplex. Posteriormente, este algoritmo incorporou o suporte para utilizar o método dual simplex; incorporou o algoritmo barrier, que é uma alternativa ao método simplex para problemas de programação linear e programação quadrática; incorporou o algoritmo branch-and-bound, para solucionar problemas de PIM, programação inteira mista quadrática e programação inteira mista com restrições quadráticas; incorporou heurísticas de pré-processamento de dados, para gerar boas soluções iniciais; e incorporou técnicas de programação por restrições, para melhorar o desempenho de busca. Além disso, o CPLEX passou a utilizar um algoritmo branch-and-cut com cortes com famílias de desigualdades válidas e genéricas. Atualmente, também é possível utilizar processamento paralelo para solucionar grandes problemas práticos (ILOG,2008). A figura A1 mostra a Linguagem de Modelagem GAMS ___________________________________________________ 101 estrutura geral da linguagem GAMS. Dados de Entrada Definição e declaração de sets e alias; Definição e declaração de scalars, parameters, tables e equações de atribuição; Determinação de displays de controle sobre as equações de atribuição. FiguraAnexo A1 - Estrutura geral do modelo GAMS (Fonte: adaptada de Brooke et al., 1997 Elementos do modelo Definição e declaração, designação do tipo, limitantes e valores iniciais de variables; Definição e declaração de equations (função objetivo e restrições). Soluções do modelo Comandos: Models; Solve; Displays. Figura anexo A1- Estrutura geral do modelo GAMS (fonte: Adaptado de Brooke et al.,1997) ANEXO B – MODELAGEM E SIMULAÇÃO Pesquisa Quantitativa baseada em modelos Extraído de BATISTA (2009). Bertrand e Fransoo (2002) apresentam uma classificação das metodologias de pesquisa em Administração da Produção que utilizam modelagem quantitativa. O trabalho de Bertrand e Fransoo (2002) pode ser útil para os pesquisadores que trabalham com modelagem quantitativa, e será abordado com profundidade nessa seção. Pesquisa quantitativa baseada em modelos é a pesquisa onde são desenvolvidos, analisados e testados modelos de relações causais entre as variáveis de controle e desempenho. Estas partem do princípio que podemos construir modelos objetivos que expliquem parte do comportamento dos processos reais, ou que podem capturar parte dos problemas de tomada de decisão enfrentados pelos gestores na vida real. Os diferentes tipos de pesquisa quantitativa são dados na Figura B.1. Figura B.1 – Classificação das metodologias de pesquisa quantitativa Fonte: Bertrand e Fransoo (2002) Ambas as classificações, axiomática e empírica, podem ser subdivididas em descritiva e normativa. Normalmente a área descritiva relaciona-se com o estudo de um processo e a normativa está ligada ao estudo de um problema. Pesquisa axiomática: A pesquisa axiomática é definida pelas seguintes características: Modelagem e Simulação___________________________________________________________ 103 É guiada pelo modelo idealizado (assume-se que alguns aspectos do problema não afetam a solução); O objetivo primário é obter soluções que forneçam conhecimento acerca da estrutura do problema; São utilizados métodos formais de áreas científicas como matemática, estatística e ciências da computação; Os pesquisadores olham para os processos ou problemas através dos modelos matemáticos que possam ser utilizados; Necessita-se de um forte fundo matemático; Deve-se julgar quais formulações de problemas científicos são bons problemas, ou seja, problemas onde podem ser obtidos resultados de qualidade. Os passos para realizar uma pesquisa axiomática são os seguintes: 1. Descrever as características dos processos ou problemas a serem estudados. A descrição do modelo conceitual deve usar tanto quanto possível conceitos e termos aceitos como padrão na literatura; 2. Especificar o modelo científico do processo ou problema. Este deve ser apresentado de maneira formal, em termos matemáticos. Na pesquisa axiomática descritiva, a modelagem do processo é o centro. Busca-se analisar um modelo para explicar suas características. O pesquisador parte de um modelo conceitual e deriva um modelo científico. Depois são feitas algumas análises do modelo científico para ganhar conhecimento sobre o comportamento deste. Tipicamente não se passa à fase de solução do modelo e a qualidade da pesquisa está ligada à extensão na qual os resultados provam dar as características exatas do processo. A extensão para a solução do modelo é feita na pesquisa axiomática normativa, onde a solução é a pesquisa central reportada. Em muitos artigos axiomáticos normativos, o processo de modelagem também está incluído e os resultados retornam ao modelo conceitual. Nesse caso a qualidade da pesquisa pertence à extensão no qual o resultado prova ser a melhor solução possível para o problema. Quase todos os artigos no domínio da PO caem na área normativa. Pesquisa empírica: Modelagem e Simulação___________________________________________________________ 104 A pesquisa empírica possui as seguintes características: O objetivo principal é assegurar que há um ajustamento das observações e ações na realidade e no modelo feito daquela realidade; É voltada a criar um modelo que descreva adequadamente as relações causais que possam existir na realidade e levem ao entendimento do processo; Deve ser planejada para testar a validade de modelos teóricos quantitativos e suas soluções; A essência é validar o modelo conceitual ou a solução da pesquisa axiomática; Como os processos operacionais são todos diferentes, premissas básicas e características dos problemas são validadas para classes definidas de processos, implícitas nos modelos teóricos e problemas; Ao contrário da pesquisa axiomática quantitativa, a pesquisa empírica não tem sido muito produtiva. Os passos para aplicação de uma pesquisa empírica são os seguintes: 1. Identificar as premissas básicas dos processos onde estão baseados os modelos ou problemas teóricos em questão. Na literatura existem diferentes linhas de pesquisa que compartilham premissas comuns sobre processos ou problemas de decisão. Há por exemplo uma linha de pesquisa baseada na visão do processo produtivo como um modelo de filas. Essa é chamada de premissa básica; 2. Identificar o tipo de processo ou problema no qual as premissas básicas se apliquem; 3. Desenvolver um critério objetivo para decidir se um processo da vida real pertence à classe de processos considerada e para identificar o sistema de decisão que representa o problema em questão. Diferentes pesquisadores devem chegar ao mesmo resultado acerca dessas classificações; 4. Derivar das premissas básicas, hipóteses sobre o comportamento dos processos. Esse comportamento se refere a variáveis ou fenômenos que possam ser medidos; 5. Desenvolver uma maneira objetiva de medir ou fazer observações. Como não existe uma maneira geralmente aceita de medir as variáveis, os pesquisadores devem desenvolver Modelagem e Simulação___________________________________________________________ 105 maneiras próprias de medir e documentar essa etapa. Essa dificuldade ilustra a posição fraca da pesquisa quantitativa empírica na administração científica; 6. Aplicar os sistemas de medição, coletar e documentar os resultados; 7. Interpretar os dados, o que geralmente irá incluir o uso de análise estatística. Técnicas especiais são necessárias, pois os resultados não podem ser manipulados de maneira arbitrária como num projeto experimental. As hipóteses devem ser restritas ao comportamento dentro de um período esperado; 8. Interpretar os resultados em relação aos modelos teóricos ou problemas que deram origem às hipóteses testadas. Esse passo completa a fase de validação e pode resultar na confirmação do modelo teórico (ou partes) em relação ao problema de decisão e ao processo considerado, ou levar a rejeição (parcial ou não) e sugestões para melhorar os modelos teóricos. A pesquisa empírica descritiva é principalmente voltada a criar um modelo que descreva adequadamente as relações causais que possam existir na realidade e levem ao entendimento do processo corrente. A pesquisa empírica normativa busca desenvolver políticas, estratégias e ações que melhorem a situação atual. Essa área de pesquisa é pequena. Houve tentativa em alguns artigos, mas o procedimento de verificação normalmente não é muito forte. Essa é a forma mais completa de pesquisa científica, onde é conduzido o ciclo completo: Conceitualização, modelagem, solução do modelo e implementação. Em muitos casos essa pesquisa é construída em trabalhos publicados na categoria axiomática descritiva onde já foram desenvolvidos caminhos para os estágios de modelagem e solução do modelo. Não se deve confundir pesquisa empírica com uso dos resultados da pesquisa axiomática para melhorar os processos. Nesse caso, os resultados se baseiam na crença que as premissas admitidas nos modelos são válidas e as soluções irão funcionar bem. RESUMO ARTIGO “Modelling and simulation: operations management research methodologies using quantitative modeling” (BERTRAND; FRANSOO, 2002) O objetivo do artigo é apresentar uma revisão de um modelo de pesquisa quantitativa em gerenciamento de operações com foco na metodologia de pesquisa. A modelagem quantitativa em pesquisa operacional tem auxiliado no sentido de resolver problemas da vida real no gerenciamento de operações. O gerenciamento de operações é definido no artigo como o projeto de projetar, planejar, controlar e executar operações na indústria de manufatura de serviços. Para os pesquisadores os modelos quantitativos são baseados em um conjunto de variáveis que variam em um domínio específico, enquanto relações quantitativa e causal são definidas entre estas variáveis. Pesquisa de operações é considerada como parte de uma pesquisa quantitativa em gerenciamento de operações. Enquanto a abordagem de pesquisa operacional é um outro ramo da modelagem quantitativa que pretende incluir todos os aspectos do processo operacional, incluindo conhecimento, opiniões e atitudes das pessoas a nível operacional e gerencial. Classifica as pesquisas sobre gerenciamento de operações em duas classes distintas: 1) Pesquisa axiomática, onde a principal preocupação do pesquisador é obter soluções dentro do modelo definido e certificar-se que estas soluções forneçam insights na estrutura do problema tal como definido no modelo. Pesquisa axiomática produz conhecimento sobre o comportamento de certas variáveis no modelo, baseado em pressupostos sobre o comportamento de outras variáveis no modelo. Normalmente, pesquisa axiomática é normativa, embora a pesquisa descritiva, com o objetivo de compreender o processo que foi modelado, também esteja presente. Pesquisa normativa está essencialmente interessada em desenvolver políticas, estratégias e ações para melhorar ao longo dos resultados disponíveis na literatura existente, para encontrar a solução ótima para um problema definido recentemente ou para comparar várias estratégias para abordar um problema específico. Já a pesquisa descritiva está primeiramente interessada em analisar um modelo, o que leva a entender e explanar as características do modelo. Pesquisas na área de teoria das filas e dos jogos, são normalmente descritivas por natureza e na maioria dos modelos. 2) A segunda classe de pesquisas é a empírica, onde a principal preocupação do pesquisador é garantir que existe um modelo de ajuste entre observação e ação na realidade e o Bertrand e Fransoo________________________________________________________________ 107 modelo feito desta realidade. Este tipo de pesquisa pode ser tanto descritiva quanto normativa, onde a pesquisa empírica descritiva está normalmente preocupada em criar um modelo que descreve adequadamente as relações causais que possam existir na realidade, o que leva à compreensão do processo em curso. Pesquisa quantitativa empírica normativa está principalmente interessada no desenvolvimento de políticas, estratégias e ações para melhorar a situação atual. Em contraste com pesquisas quantitativas axiomáticas, modelos baseados em pesquisas quantitativas empíricas não são muito produtivos, visto que reportam a aplicação dos resultados das pesquisas teóricas nos processos operacionais da vida real. Na pesquisa quantitativa axiomática, a principal relevância científica é principalmente determinada pelo que cada pesquisador pretende contribuir para a literatura existente, o que pode ser de dois tipos: novas variações de processo ou problema usando técnicas de soluções conhecidas. A outra seria estudar um processo ou problema que já foi estudado antes, mas fornecendo novas ou melhores soluções para o problema, seja aplicando novos tipos de soluções técnicas, ou alcançando novos resultados com as soluções técnicas aceitas. Na pesquisa quantitativa axiomática usando simulação, os resultados são obtidos via simulação computacional. Usada nos casos em que o modelo ou problema é muito complexo para uma análise matemática formal. Os passos para este tipo de pesquisa são apresentados. Na pesquisa quantitativa baseada em modelos empíricos, a principal preocupação é testar a validade dos modelos científicos usados em pesquisas teóricas quantitativas ou testar o uso e desempenho da solução do problema obtido por meio da pesquisa teórica quantitativa nos processo operacionais da vida real.