Lista - Modelagem - Pesquisa Operacional 2 2021-2

Faculdade de Ciências Aplicadas - Unicamp Pesquisa Operacional Prof. Cleber Rocco Lista de exercícios: Modelagem 1. Um banco está elaborando uma política de empréstimo financeiro somando a quantia máxima de R$12 milhões. A tabela a seguir apresenta os dados sobre os tipos de empréstimos disponíveis. Empréstimo Taxa de Juros Inadimplência Pessoal 0,140 10% Automóvel 0,130 7% Imobiliário 0,120 3% Rural 0,125 5% Comercial 0,100 2% A política do banco impõe que pelo menos 40% dos fundos sejam alocados para empréstimos rurais e comerciais. O montante designado a empréstimos imobiliários deve ser pelo menos 50% do total designado a empréstimos do tipo Pessoal, Automóvel e Imobiliário. O banco quer que a taxa de inadimplência total não ultrapasse 4%. Determine quanto o banco deve designar a cada tipo de empréstimo, de modo a maximizar seu lucro. Implemente o modelo em algum software de otimização (Lpsolve, GAMS etc.). [Fonte: TAHA, 2008, pg. 17 (Exemplo 2.3-3)] 2. (Distribuição de calçados) A Calçados Romano possui 3 unidades de produção de calçados e 2 lojas que fazem vendas de produtos. A primeira unidade possui 1000 pares em estoque, a segunda, 2000 e a terceira, 2200. Para a próxima semana, as lojas vão requerer 2500 e 2700 pares, respectivamente. O custo de transporte de 100 pares da unidade 1 para a loja 1 é de R$20. Os outros custos entre unidades e lojas são oferecidos na tabela a seguir: Unidade Estoque [par] Custo de transporte por unidade para a loja [R$] 1 2 1 1000 20 10 2 2000 5 8 3 2200 6 19 Demanda loja 2500 2700 Os calçados podem ser deixados em estoques, mas a demanda das lojas deve ser atendida. Com o intuito de minimizar custos de transporte, que unidade atende que loja e em que quantidades? Implemente o modelo em algum software de otimização (Lpsolve, GAMS etc.). [Fonte: COLIN, 2017, pg. 18 (Exercício 7)] 3. A equipe técnica de um hospital deseja desenvolver um sistema de planejamento de menu automatizado. Para iniciar, eles começaram com o menu do almoço. Esse menu pode ser dividido em três categorias: vegetais, carnes e sobremesa. Pelo menos um representante de cada categoria deve ser servido. O custo por refeição dos itens de cada categoria, assim como suas contribuições de carboidratos, vitaminas, proteínas e gorduras estão na tabela abaixo: Carboidratos Vitaminas Proteínas Gorduras Custo/Refeição Vegetais Ervilha 1 3 1 0 0,10 Vagem 1 5 2 0 0,12 Quiabo 1 5 1 0 0,13 Milho 2 6 1 2 0,09 Macarrão 4 2 1 1 0,10 Arroz 5 1 1 1 0,07 Carne Frango 2 1 3 1 0,70 Carne de vaca 3 8 5 2 1,20 Peixe 3 6 6 1 0,63 Sobremesa Laranja 1 3 1 0 0,28 Maçã 1 2 0 0 0,42 Pudim 1 0 0 0 0,15 Gelatina 1 0 0 0 0,12 Suponha que as necessidades mínimas de carboidratos, vitaminas, proteínas e gorduras sejam 5, 10, 10 e 2, respectivamente. a) Formule o programa de planejamento de menu como um problema linear. b) Implemente o modelo em algum software de otimização (Lpsolve, GAMS etc.). [Fonte: BAZARAA, 2010, pg. 30 (Exercício 1.5)] 4. Um avião de carga possui três compartimentos para armazenamento de carga: anterior, central e posterior. Esses compartimentos possuem limites na capacidade de carga tanto em termos de peso quanto de espaço, conforme sintetizado abaixo: Compartimento Capacidade em Peso (t) Capacidade em Volume (pés) Anterior 12 7000 Central 18 9000 Posterior 10 5000 Além disso, o peso da carga no respectivo compartimento deve ser da mesma proporção da capacidade em termos de peso desse compartimento para manter o equilíbrio da aeronave. As quatro cargas a seguir serão embarcadas em um próximo voo, uma vez que há espaço disponível: Carga Peso (t) Volume (pés³/t) Lucro (US$/t) 1 20 500 320 2 16 700 400 3 25 600 360 4 13 400 290 Qualquer parcela dessas cargas pode ser aceita. O objetivo é determinar quanto (se alguma) de cada carga deve ser aceita e como distribuir cada uma delas entre os compartimentos de modo a maximizar o lucro total por voo. a) Formule um modelo de programação linear para esse problema. b) Solucione esse modelo pelo método simplex para encontrar uma das várias soluções ótimas. c) Implemente o modelo em algum software de otimização (Lpsolve, GAMS etc.). [Fonte: HILLIER E LIEBERMAN, 2006, pg. 94 (Exercício 3.4-13*)] 5. (Produção de cimento) A figura a seguir oferece o fluxo geral da fabricação, desde a retirada de calcário da jazida até a embalagem de dois tipos de cimento: CP320 (Cimento Portland 320) e AF250 (Cimento Alto-Forno 250). A tabela a seguir mostra a composição típica para cada um dos tipos de cimento produzidos: Elemento CP320 AF250 Clínquer 85% 50% Escória de alto-forno 7% 45% Gesso 3% 3% Aditivo 5% 2% A produção de clínquer é limitada pela capacidade do forno de no máximo 1,1 milhão de toneladas/ano. Da mesma forma, a produção dos dois tipos de cimento também é limitada a 1,1 milhão de toneladas/ano devido à capacidade do moinho. Outras restrições são conhecidas: •Pode-se vender clínquer a outros fabricantes de cimento. O volume é limitado em 200 mil toneladas/ano; •A escória de usinas siderúrgicas disponível para compra é de 180 mil toneladas/ano; •Gesso e aditivo estão disponíveis em 50 mil toneladas/ano cada um. Considere que a contribuição marginal seja a receita menos custos fixos e variáveis. Para se saber a margem de um produto precisa-se subtrair o custo dos insumos. Outras informações do problema são as seguintes: • Contribuição marginal: o CP320: R$41,00/t; o AF250: R$37,80/t; o Clínquer: R$34,40/t; • Preços dos insumos: o Gesso: R$34,20/t; o Escória: R$22,10/t; o Aditivo: R$1,90/t. Formule um modelo que defina a produção anual e maximize a margem total da empresa e implemente o modelo em algum software de otimização (Lpsolve, GAMS etc.). [Fonte: COLIN, 2017, pg. 17 (Exercício 6 - adaptado)] 6. Edmundo adora bifes e batatas. Assim, decidiu entrar em uma dieta regular usando somente esses alimentos (além de alguns líquidos e suplementos vitamínicos) em todas as suas refeições. Ele percebe que essa não é a dieta mais saudável e, portanto, quer certificar- se de que se alimenta das quantidades certas desses dois tipos de alimentos, a fim de atender a determinados requisitos nutricionais. Ele obteve as seguintes informações nutricionais e de custo: Ingrediente Nº de Gramas do Ingrediente por Exigência Diária (gramas) Exigência Diária (gramas) Bife Batatas Carboidratos 5 15 ≥ 50 Proteína 20 5 ≥ 40 Gordura 15 2 ≤ 60 Custo por refeição US$ 4 US$ 2 Edmundo quer determinar o número de refeições diárias (pode ser fracionário) com bife e batatas que atenderá a essas exigências a um custo mínimo. a) Formule um modelo de programação linear para esse problema. b) Utilize o método gráfico para solucionar esse modelo. c) Implemente o modelo em algum software de otimização (Lpsolve, GAMS etc.). [Fonte: HILLIER E LIEBERMAN, 2006, pg. 93 (Exercício 3.4-7)] 7. (Seleção de culturas para plantio) Um fazendeiro dispõe de 400 hectares de terra cultivável e está interessado em decidir sobre o que vai plantar no próximo ano. Ele tem dúvidas a respeito de três produtos: milho, soja e trigo. Por outro lado, ele tem certeza de que quer plantar em toda a propriedade. O plantio de milho requer investimentos de R$2.000/ha, 20 homens-dia de trabalho para preparar um ha, e promove um lucro de R$600/ha. O trigo requer R$2.400 investidos, promove R$800 de lucro e demanda 30 homens-dia de trabalho para preparar 1 ha. Finalmente, a soja demanda 24 homens-dia, R$1.400 de investimentos e gera um lucro de R$400. O fazendeiro só tem R$800.000 para investir em sua fazenda no próximo ano e pode contar também com 8.000 homens/dia de trabalho. Formule um modelo de programação linear para maximizar o lucro do fazendeiro, atendendo às restrições de recursos disponíveis e implemente o modelo no GAMS. [Fonte: COLIN, 2017, pg. 18 (Exercício 4 - adaptado)] 8. (Logística de vagões vazios) A companhia ferroviária Fepasa trabalha na região de São Paulo transportando uma grande diversidade de produtos. Como na grande maioria das empresas ferroviárias, há um desbalanceamento entre oferta e demanda de vagões. A empresa tem uma grande demanda por vagões vazios no interior do estado e uma grande oferta dos mesmos no Porto de Santos. Isso acontece porque vagões cheios de mercadorias para exportação são levados até o porto e não há demanda compatível para transporte de produtos importados de volta para o interior do estado. O desbalanceamento entre oferta e demanda faz com que empresas se esforcem em gerenciar bem suas ofertas e demandas de vagões vazios nos diversos terminais e estações. A tabela a seguir apresenta uma matriz de distâncias entre terminais de origem e destino da empresa, juntamente com as ofertas e demandas de vagões para os 3 primeiros dias da próxima semana. Destino Pindorama Araraquara Santos Passagem Pederneiras Oferta (2ª-feira) Origem Distâncias entre origem e destino [km] Pindorama 0 110 435 191 289 45 Araraquara 112 0 328 81 162 34 Santos 439 327 0 415 354 346 Passagem 190 83 413 0 240 45 Pederneiras 293 165 351 243 0 76 Demanda (4ª-feira) 36 140 64 272 31 O diferencial de 2 dias entre ofertas e demandas é suficiente para que o transporte dos vagões seja efetuado. O custo de transporte é proporcional à distância percorrida. A empresa está interessada em saber como os vagões devem ser movimentados para atender demandas com custo mínimo. Formule um modelo e o implemente no GAMS. [Fonte: COLIN, 2017, pg. 19 (Exercício 9)] 9. O Sr. Ferris tem US$ 60.000 que ele deseja investir agora, de modo a utilizar os rendimentos para comprar um plano de aposentadoria em cinco anos. Após falar com seu consultor financeiro, lhe foram propostos quatro tipos de investimentos de renda fixa que chamaremos investimentos A, B, C e D. Os investimentos A e B se encontram disponíveis no início de cada um dos próximos cinco anos (denominados anos 1 a 5). Cada dólar investido em A no início de um ano gera como retorno US$ 1,40 (um lucro de US$ 0,40) dois anos mais tarde (disponível então para reinvestimento imediato). Cada dólar investido em B no início de um ano gera como retorno US$ 1,70 três anos mais tarde. Os investimentos C e D estarão disponíveis em algum momento no futuro. Cada dólar investido em C no início do ano 2 gera como retorno US$ 1,90 no final do ano 5 e cada dólar investido em D no começo do ano 5 gera como retorno US$ 1,30 no final do ano 5. O Sr. Ferris deseja saber que plano de investimento maximiza a quantia que pode ser acumulada no início do ano 6. a) Todas as restrições funcionais para esse problema podem ser expressas na forma de restrições de igualdade. Para tanto, façamos com que At, Bt, Ct, e Dt, sejam a quantia investida, respectivamente, nos investimentos A, B, C e D no início do ano t para cada t no qual o investimento se encontra disponível e com vencimento no final do ano 5. Façamos também que Rt seja a quantidade de dólares disponível não investida no início do ano t (e, portanto, disponível para investimento em um ano futuro). Portanto, a quantia investida no início do ano t mais Rt tem de ser igual à quantidade de dólares disponível para investimento naquele momento. Escreva as equações necessárias em termos das variáveis relevantes anteriores para o início de cada um dos cinco anos para obter as cinco restrições funcionais para esse problema. b) Formule um modelo de programação linear completo para o problema. c) Solucione esse modelo pelo método simplex. d) Implemente o modelo em algum software de otimização (Lpsolve, GAMS etc.). [Fonte: HILLIER E LIEBERMAN, 2006, pg. 94 (Exercício 3.4-11*)] 10. (Produção de leite, doces e queijos) Um produtor de derivados do leite produz queijo e doce de leite. O produtor tem à disposição 800 litros de leite por dia oriundos de sua propriedade e de alguns vizinhos que fornecem para ele. A produção de cada quilo de queijo requer 9 litros de leite, e cada quilo de doce requer 7 litros de leite. O mercado impõe que a quantidade máxima de doce que pode ser feita por dia é 60 quilos, e a quantidade máxima de queijo diária não pode ultrapassar 90 quilos. Além disso, por questões relacionadas com equipamentos de produção, a quantidade de queijo produzido não pode exceder 150% da produção de doce. A produção utiliza 2 empregados que trabalham num regime de 7 horas diárias. Cada quilo de queijo requer 30 minutos de mão-de-obra, ao passo que cada quilo de doce requer 12 minutos de mão-de-obra. O queijo é vendido a R$5/kg e o doce, a R$4/kg. Formule um modelo para maximizar as receitas do produtor e o implemente no GAMS. [Fonte: COLIN, 2015, pg. 18 (Exercício 5 - adaptado)] 11. Uma refinaria de óleo compra dois tipos de óleo cru: leve e pesado. O custo por barril desses óleos são $ 20 e $15 unidades monetárias. As quantidades de gasolina comum, querosene e gasolina de aviação extraídas por barril são apresentadas no quadro abaixo: Gasolina Querosene Gasolina de Aviação Óleo leve 0,40 0,2 0,35 Óleo pesado 0,32 0,4 0,20 Sabe-se que no processo industrial há perdas de rendimento dos óleos leve e pesado em 5% e 8% respectivamente. A refinaria tem um contrato que deve ser cumprido para a entrega de 1 milhão de barris de gasolina comum, 500 mil barris de querosene e 300 mil barris de gasolina de aviação. Elabore o modelo de programação linear que encontre as quantidades dos tipos de óleo necessários para atender à demanda e minimizar o custo de produção do sistema. Implemente o modelo em algum software de otimização (Lpsolve, GAMS etc.). [Fonte: BAZARAA, 2010, pg. 33 (Exercício 1.10)] 12. (Problema do fluxo na indústria de processo) A Petrobras S.A. está avaliando seu processo de produção de óleos e gasolina a partir do petróleo bruto. A figura a seguir apresenta o fluxo de processos geral da empresa, desde a entrada da matéria-prima até a saída dos produtos finais Cada estágio de produção possui uma determinada capacidade, conforme apresentado na tabela a seguir. Processo Gasolina Bruta [t/ano] Gás e Óleo [t/ano] Destilação 500.000 600.000 Dessulfuração 700.000 500.000 Reforming 400.000 - Cracking - 450.000 Lucros unitários [$/t] 10,00 7,00 A Petrobras quer definir as produções de cada produto com o intuito de maximizar os lucros totais gerados pela venda de gás, óleos e gasolina. Formule uma modelo para maximizar os lucros da empresa e o implemente no GAMS ou outro software de otimização. [Fonte: COLIN, 2015, pg. 15 (Problema 3.5)] 13. A Fagersta Steelworks atualmente está trabalhando em duas minas para obter seu minério de ferro. Este minério de ferro é enviado para qualquer uma das duas instalações de armazenagem. Quando necessário, então é enviado para a siderúrgica da empresa. O diagrama abaixo apresenta essa rede de distribuição, onde M1 e M2 são as duas minas, S1 e S2 são as duas instalações de armazenamento, e P é a siderúrgica. O diagrama mostra também os valores mensais produzidos nas minas e necessários na usina, assim como o custo de transporte e a quantia máxima que pode ser enviada por mês através de cada rota de transporte. A administração agora quer determinar o plano mais econômico para o transporte do minério de ferro das minas através da rede de distribuição até a usina siderúrgica. a) Formule um modelo de programação linear para este problema. b) Resolva este modelo pelo método simplex. c) Implemente o modelo em algum software de otimização (Lpsolve, GAMS etc.). [Fonte: HILLIER e LIEBERMAN, 2001, pg. 96 (Exercício 3.4-12)] 14. (Produtos na prateleira do supermercado) Quase todas as empresas que atuam no varejo têm mais produtos do que espaço para vende-los. Esse problema é característico de supermercados, lojas de departamentos e até mesmo empresas de comércio eletrônico. Nessas empresas, a administração precisa decidir que produtos vender dado um espaço disponível, de modo que sua lucratividade seja máxima. Supondo que o supermercado tenha 20 itens que ele pode disponibilizar em suas prateleiras, conforme a tabela a seguir: Item Demanda entre reabastecimentos Lucro [R$/unidade] Área [𝑐𝑚2/unidade] 1 2 3 4 5 50 35 25 20 45 2 2 3 4 4 65 45 58 71 71 6 7 8 9 10 50 45 40 30 50 6 5 5 6 4 77 90 90 65 52 11 12 13 14 15 35 50 20 25 30 2 6 5 3 4 90 52 71 77 58 16 17 20 60 2 2 45 65 18 19 20 35 25 45 1 5 4 103 71 97 Se todos os itens fossem colocados à venda, seriam necessários 52.290 𝑐𝑚2 de área de prateleira. O supermercado só dispõe de 37.200 𝑐𝑚2 para alocar todos os itens a serem vendidos. Formule o problema do supermercado com o objetivo de maximizar o lucro total e o implemente no GAMS ou outro software de otimização. [Fonte: COLIN, 2015, pg. 19 (Exercício 11)] 15. Uma indústria produz tintas para exterior e interior a partir de duas matérias-primas, M1 e M2. Considere as seguintes informações: Material Exterior Interior (t/dia) M1 6 4 24 M2 1 2 6 Lucro/tonelada 5 mil 4 mil Uma pesquisa de mercado indicou que a demanda diária da tinta para interior não excede a da tinta para exterior em mais de 1 tonelada. Além disso, a demanda diária máxima da tinta para interior é de 2 toneladas. Construa um modelo de programação linear para determinar o mix de produtos ótimo, isto é, quanto produzir de cada tipo de tinta de modo a maximizar o lucro da empresa. Implemente o modelo em algum software de otimização (Lpsolve, GAMS etc.). [Fonte: TAHA, 2008, pg. 6 (Exemplo 2.1-1)] 16. (A Universidade Oxbridge mantém um computador poderoso para uso em pesquisa por seu corpo docente, Ph.D. estudantes e pesquisadores associados. Durante todas as horas de trabalho, um operador deve estar disponível para operar e realizar a manutenção no computador, bem como para executar alguns serviços de programação. Beryl Ingram, diretora da unidade de computação, supervisiona o trabalho. Está no início do segundo semestre, e Beryl é confrontada com o problema de atribuir diferentes horários de trabalho para seus operadores. Pelo fato de todos os operadores estarem atualmente inscritos na universidade, eles estão disponíveis para trabalhar apenas em um número limitado de horas cada dia, como se mostra na tabela a seguir. Máximo de horas disponíveis Operadores Taxa salarial Segunda Terça Quarta Quinta Sexta K. C. $ 10.00/h 6 0 6 0 6 D. H. $ 10.10/h 0 6 0 6 0 H. B. $ 9.90/h 4 8 4 0 4 S. C. $ 9.80/h 5 5 5 0 5 K. S. $ 10.80/h 3 0 3 8 0 N. K. $ 11.30/h 0 0 0 6 2 Há seis operadores (quatro estudantes de graduação e dois estudantes de pós-graduação). Todos eles têm diferentes pisos salariais por causa de diferenças em experiência com computadores e em habilidade de programação. A tabela acima mostra os pisos salariais, juntamente com o número máximo de horas que cada um pode trabalhar diariamente. A cada operador é garantido um número mínimo de horas por semana que irá manter um conhecimento adequado da operação. Este nível é definido arbitrariamente em 8 horas por semana para os alunos de graduação (K. C., D. H., H. B., e S. C.) e 7 horas por semana para os alunos de pós-graduação (K. S. e N. K.). A unidade de computação é para estar aberta para operação das 8h às 22h de segunda a sexta-feira com exatamente um operador de plantão durante estas horas. Aos sábados e domingos, o computador é operado por outra equipe. Por causa de um orçamento apertado, Beryl tem que minimizar o custo. Ela deseja determinar o número de horas que ela deveria atribuir a cada operador em cada dia. a) Formule um modelo de programação linear para este problema. b) Resolva este modelo utilizando algum software de otimização (Lpsolve, GAMS etc.). [Fonte: HILLIER e LIEBERMAN, 2001, pg. 98 (Exercício 3.4-18)] LIVROS: • TAHA: Pesquisa Operacional – 8ª edição • HILLIER e LIEBERMAN: Introdução à Pesquisa Operacional – 8ª edição • BAZARAA: Linear Programming and Network Flows – 4ª edição • COLIN: Pesquisa Operacional: 170 Aplicações em Estratégia, Finanças, Logística, Produção, Marketing e Vendas – 2ª edição OBS.: todos os livros estão disponíveis como conteúdo digital na biblioteca. CONTATOS PAD/PED: PESQUISA OPERACIONAL II PESQUISA OPERACIONAL I PED LUAN PABLO (ENG. PRODUÇÃO) L232715@DAC.UNICAMP.BR (19) 99655-3654 SEGUNDA-FEIRA 18h-19h PED MATHEUS EVANGELISTA (ENG. PRODUÇÃO) M150756@DAC.UNICAMP.BR (42) 99860-9024 TERÇA-FEIRA 15h-19h PAD MARCOS TAVARES (ENG. PRODUÇÃO) MARCOS.TAVARES159@GMAIL.COM (31) 98754-3468 QUARTA-FEIRA 10h-11h QUINTA-FEIRA 10h-11h PAD MARIANA KOLESKI (ENG. PRODUÇÃO) M241281@DAC.UNICAMP.BR (41) 99188-0997 QUARTA-FEIRA 17h-19h