Baixe o app para aproveitar ainda mais
Prévia do material em texto
PESQUISA OPERACIONAL AULA 3 Prof. Ricardo Alexandre Deckmann Zanardini 2 CONVERSA INICIAL Nesta aula estudaremos aplicações da programação linear em algumas importantes áreas: produção, transporte e comércio. Em seguida, estudaremos problemas de transporte e de designação, que são casos particulares de problemas de programação linear. Serão apresentados exemplos reais, mas de uma forma simplificada. É importante ressaltar que temos muitas outras aplicações da programação linear, não só nestas áreas, mas em outras também. TEMA 1 – PROGRAMAÇÃO LINEAR APLICADA À PRODUÇÃO Dentre diversas áreas, a produção é uma que utiliza muito a pesquisa operacional e, em particular, a programação linear. A seguir, apresentaremos alguns exemplos com as respectivas soluções ótimas obtidas a partir do uso da biblioteca PuLP do Python. São exemplos inspirados em problemas reais, mas apresentados de uma forma simplificada. Lembrando que para resolvermos um problema de PL por meio da biblioteca PuLP, no Google Colab, precisamos importar a biblioteca utilizando os comandos import sys !{sys.executable} -m pip install pulp e em seguida utilizar os comandos from pulp import * prob = LpProblem('Exemplo',LpMaximize) x1=LpVariable("XXXXX",0) x2=LpVariable("XXXXX",0) x3=LpVariable("XXXXX",0) prob += XXXXX prob += XXXXX prob += XXXXX prob += XXXXX prob.solve() for v in prob.variables(): print(v.name, "=", v.varValue) print("Lucro máximo = ", value(prob.objective)) 3 onde XXXXX são os campos a serem substituídos pelos dados do problema. Apresentaremos a seguir alguns problemas simples relacionados à produção. Exemplo 1: A produção de uma indústria de artigos esportivos consiste na fabricação de blusões e de calças em um único tamanho. Para a produção de cada blusão, a indústria utiliza 1,2 metros de tecido e, para a produção de cada calça, utiliza 1,3 metros deste mesmo tecido. Em virtude de máquinas e de mão de obra, a produção máxima é de 800 blusões e de 900 calças. A quantidade máxima de tecido disponível por dia é igual a 2000 metros. Foi informado que o lucro referente à venda de cada blusão é de R$ 75,00, e o lucro referente à venda de cada calça corresponde a R$ 60,00. O objetivo da indústria é determinar quantas unidades de cada produto devem ser produzidos diariamente de modo que o lucro seja o maior possível. Formule e resolva o problema como um problema de programação linear. Resolução: Variáveis: x1 = quantidade de blusões a serem produzidos x2 = quantidade de calças a serem produzidas Formulação: max L=75x1+60x2 s.a. 1,2x1+1,3x2<=2000 x1<=800 x2<=900 x1>=0, x2>=0 No Python: import sys !{sys.executable} -m pip install pulp from pulp import * prob = LpProblem('Exemplo',LpMaximize) x1=LpVariable("Blusões",0) x2=LpVariable("Calças",0) prob += 75*x1+60*x2 prob += 1.2*x1+1.3*x2<=2000 4 prob += x1<=400 prob += x2<=480 prob.solve() for v in prob.variables(): print(v.name, "=", v.varValue) print("Lucro máximo = ", value(prob.objective)) Solução ótima: 800 blusões 800 calças Lucro máximo: R$ 108.000,00 Exemplo 2: Um agricultor produz feijão e soja e pretende decidir quantos hectares irá dedicar a cada cultura de modo a maximizar o lucro total. Para cada hectare de feijão irrigado, o lucro líquido estimado é de R$ 1.600,00, e para cada hectare de soja irrigada, estima-se que o lucro seja de R$ 2.500,00. A quantidade máxima de terra disponível é de 80 hectares. Contratos assinados exigem que a produção mínima de feijão seja de 20 hectares e a produção mínima de soja seja de 32 hectares. Formule e resolva o problema como um problema de programação linear. Resolução: Variáveis: 5 x1 = hectares de feijão a serem plantados x2 = hectares de soja a serem plantados Formulação: max L=1600x1+2500x2 s.a. x1+x2<=80 x1>=20 x2>=32 No Python: import sys !{sys.executable} -m pip install pulp from pulp import * prob = LpProblem('Exemplo',LpMaximize) x1=LpVariable("Feijão",0) x2=LpVariable("Soja",0) prob += 1600*x1+2500*x2 prob += x1+x2<=80 prob += x1>=20 prob += x2>=32 prob.solve() for v in prob.variables(): print(v.name, "=", v.varValue) print("Lucro máximo = ", value(prob.objective)) Solução ótima: 6 Feijão: 20 hectares Soja: 60 hectares Lucro máximo: R$ 182.000,00 TEMA 2 – PROGRAMAÇÃO LINEAR APLICADA AO TRANSPORTE A programação linear pode nos auxiliar na resolução de problemas de diversas áreas. A seguir, apresentaremos alguns exemplos relacionados ao transporte. Exemplo 1: Uma empresa da área de logística precisa adquirir uma certa quantidade de empilhadeiras e de porta pallets. A seguir são apresentadas algumas informações importantes: o custo referente à aquisição de cada um destes itens e as quantidades mínimas e máximas a serem adquiridas. Custo Unitário Quantidade Mínima Quantidade Máxima Empilhadeira R$ 70.000,00 15 50 Porta Pallet R$ 1.200,00 400 Sabendo que a empresa tem R$ 1.600.000,00 para investir na compra das empilhadeiras e dos porta pallets e que deseja minimizar o custo total referente à aquisição destes itens, determine quantas empilhadeiras e quantos porta pallets deverá comprar. Resolução: Variáveis: x1 = quantidade de empilhadeiras a serem adquiridas x2 = quantidade de porta pallets a serem adquiridas Formulação: min C=70000x1+1200x2 s.a. 70000x1+1200x2<=1600000 x1>=15 x1<=50 x2>=400 No Python: 7 import sys !{sys.executable} -m pip install pulp from pulp import * prob = LpProblem('Exemplo',LpMinimize) x1=LpVariable("Empilhadeira",0) x2=LpVariable("Porta Pallet",0) prob += 70000*x1+1200*x2 prob += 70000*x1+1200*x2<=1600000 prob += x1>=15 prob += x1<=50 prob += x2>=400 prob.solve() for v in prob.variables(): print(v.name, "=", v.varValue) print("Custo mínimo = ", value(prob.objective)) Solução ótima: 15 empilhadeiras 400 porta-pallets Custo mínimo: R$ 1.530.000,00 Exemplo 2: O objetivo de uma transportadora é otimizar a utilização mensal de sua frota de caminhões obtendo assim o maior lucro total referente aos serviços 8 prestados. Atualmente a transportadora conta com os seguintes veículos: 8 carretas, 16 caminhões médios e 12 caminhões pequenos. A empresa tem 32 motoristas e 61 ajudantes. Cada caminhão precisa de 1 motorista e o número de ajudantes depende do tipo de veículo: 1 ajudante para cada caminhão pequeno, 2 ajudantes para cada caminhão médio e 3 ajudantes para cada carreta. O lucro mensal referente a cada carreta corresponde a R$ 5.800,00. O lucro mensal relacionado a cada caminhão médio corresponde a R$ 3.300,00 e o lucro para cada caminhão pequeno é de R$ 2.800,00. A empresa deseja saber quantos caminhões de cada modelo irá utilizar mensalmente. Formule e resolva o problema como um problema de PL. Resolução: Variáveis: x1 = quantidade de caminhões pequenos x2 = quantidade de caminhões médios x3 = quantidade de carretas Formulação: max L=2800x1+3300x2+5800x3 s.a. x1+x2+x3<=32 x1+2x2+3x3<=61 x1<=12 x2<=16 x3<=8 x1>=0, x2>=0, x3>=0 No Python: import sys !{sys.executable} -m pip install pulp from pulp import * prob = LpProblem('Exemplo',LpMaximize) x1=LpVariable("Caminhão pequeno",0) x2=LpVariable("Caminhão médio",0) x3=LpVariable("Carreta",0) prob += 2800*x1+3300*x2+5800*x3 prob += x1+x2+x3<=32 prob += x1+2*x2+3*x3<=61 prob += x1<=12 9 prob += x2<=16 prob += x3<=8 prob.solve() for v in prob.variables(): print(v.name, "=", v.varValue) print("Lucro máximo = ", value(prob.objective)) Solução ótima: Caminhões pequenos: 11 Caminhões médios: 13 Carretas: 8 Lucro máximo: R$ 120.100,00 Exemplo 3: Uma transportadora precisa ampliar a suacapacidade de entregas e está estudando a viabilidade da compra de três novos caminhões. O custo para a aquisição de um caminhão grande é de R$ 3,4 milhões, R$ 2,1 milhões para um caminhão médio e $ 1,9 milhões para a compra de um caminhão pequeno. O orçamento destinado à compra desses caminhões é de R$ 80 milhões. Com base nos valores atuais dos fretes, o lucro anual líquido estimado para a compra dos novos caminhões será de R$ 80.000,00 para cada caminhão grande, R$ 67.000,00 para cada caminhão médio e R$ 36.000,00 para cada caminhão pequeno. A transportadora precisa adquirir pelo menos quatro caminhões de 10 cada tipo. Como o objetivo é determinar quantos caminhões de cada tipo devem ser adquiridos para maximizar o lucro anual, formule e resolva o problema como um problema de programação linear. Resolução: Variáveis: x1 = quantidade de caminhões pequenos x2 = quantidade de caminhões médios x3 = quantidade de caminhões grandes Formulação: max L=36000x1+67000x2+80000x3 s.a. 1,9x1+2,1x2+3,4x3<=80 x1>=4 x2>=4 x3>=4 No Python: import sys !{sys.executable} -m pip install pulp from pulp import * prob = LpProblem('Exemplo',LpMaximize) x1=LpVariable("Caminhão pequeno",0) x2=LpVariable("Caminhão médio",0) x3=LpVariable("Caminhão grande",0) prob += 36000*x1+67000*x2+80000*x3 prob += 1.9*x1+2.1*x2+3.4*x3<=80 prob += x1>=4 prob += x2>=4 prob += x3>=4 prob.solve() for v in prob.variables(): print(v.name, "=", v.varValue) print("Lucro máximo = ", value(prob.objective)) 11 Solução ótima: Caminhões pequenos: 4 Caminhões médios: 28 Carretas: 4 Lucro máximo: R$ 2.340.000,00 TEMA 3 – PROGRAMAÇÃO LINEAR APLICADA AO COMÉRCIO No comércio, é possível utilizarmos a programação linear em diversas situações. Vamos resolver alguns exemplos em que o objetivo é otimizar a compra de produtos de modo a maximizar o lucro na venda destes itens. Exemplo 1: Uma revenda de equipamentos agrícolas deseja investir R$ 2.535.000,00 na compra de novos produtos para a loja. O setor de compras está analisando três tipos de equipamentos chamados de A, B e C. O equipamento A tem um custo unitário de R$ 9.200,00 e representa um lucro de R$ 3.400,00. O equipamento B custa R$ 6.700,00 com um lucro de R$ 2.900,00, e o equipamento C tem um custo unitário de R$ 17.000,00 com um lucro de R$ 4.300,00. O estoque mínimo de cada equipamento deverá ser de 20 unidades. A revenda precisa definir quantas unidades de cada equipamento serão 12 adquiridas de modo que o lucro total referente à venda dos equipamentos seja o maior possível. Resolução: Variáveis: x1 = quantidade de equipamentos A x2 = quantidade de equipamentos B x3 = quantidade de equipamentos C Formulação: max L=3400x1+2900x2+4300x3 s.a. 9200x1+6700x2+17000x3<=2535000 x1>=20 x2>=20 x3>=20 No Python: import sys !{sys.executable} -m pip install pulp from pulp import * prob = LpProblem('Exemplo',LpMaximize) x1=LpVariable("Equipamento A",0) x2=LpVariable("Equipamento B",0) x3=LpVariable("Equipamento C",0) prob += 3400*x1+2900*x2+4300*x3 prob += 9200*x1+6700*x2+17000*x3<=2535000 prob += x1>=20 prob += x2>=20 prob += x3>=20 prob.solve() for v in prob.variables(): print(v.name, "=", v.varValue) print("Lucro máximo = ", value(prob.objective)) 13 Solução ótima: Equipamento A: 20 Equipamento B: 300,14925 Equipamento C: 20 Lucro máximo: R$ 1.024.432,83 Exemplo 2: Um açougue tem R$ 22.000,00 para comprar carne de frango, carne de gado e carne de porco. Para a compra da carne de frango, o custo por quilo é R$ 8,00. O custo referente a um quilo de carne de gado é R$ 17,00 e o custo referente a um quilo de carne de porco é R$ 15,00. O lucro associado à venda da carne de frango corresponde a R$ 10,00 por quilo, para a venda de um quilo de carne de gado o lucro é de R$ 19,00 e o lucro referente à venda de cada quilo de carne de porco é de R$ 16,00. Levando em consideração o histórico de vendas, a quantidade mínima a ser comprada de cada tipo de carne é de 500 quilos. O objetivo do açougue é maximizar o lucro referente à venda das carnes. Assim, quantos quilos de cada uma delas deverão ser comprados? Formule e resolva o problema como um problema de programação linear. Resolução: Variáveis: x1 = quantidade de carne de frango 14 x2 = quantidade de carne de gado x3 = quantidade de carne de porco Formulação: max L=10x1+19x2+16x3 s.a. 8x1+17x2+15x3<=22000 x1>=500 x2>=500 x3>=500 No Python: import sys !{sys.executable} -m pip install pulp from pulp import * prob = LpProblem('Exemplo',LpMaximize) x1=LpVariable("Carne de frango",0) x2=LpVariable("Carne de porco",0) x3=LpVariable("Carne de gado",0) prob += 10*x1+19*x2+16*x3 prob += 8*x1+17*x2+15*x3<=22000 prob += x1>=500 prob += x2>=500 prob += x3>=500 prob.solve() for v in prob.variables(): print(v.name, "=", v.varValue) print("Lucro máximo = ", value(prob.objective)) 15 Solução ótima: Carne de frango: 750 Carne de gado: 500 Carne de porco: 500 Lucro máximo: R$ 25.000,00 TEMA 4 – PROBLEMAS DE TRANSPORTE Problemas de transporte consistem em um caso particular da programação linear em que o objetivo é determinar as quantidades a serem transportadas de uma ou mais origens para um ou mais destinos de modo que o custo total referente ao transporte seja o menor possível. Há métodos específicos destinados à resolução destes problemas, mas eles podem ser resolvidos a partir da formulação do problema como um problema de programação linear. Podemos ter problemas em que a demanda e a oferta são iguais. Podemos ter também problemas em que a demanda é maior do que a oferta ou problemas em que a oferta é maior do que a demanda. No primeiro exemplo, vamos considerar a situação em que a demanda é maior do que a oferta. Note que neste caso, na formulação, na restrição relacionada à capacidade do depósito, utilizaremos uma restrição de maior ou 16 igual e, nas restrições relacionadas às demandas, utilizaremos restrições de menor ou igual. Exemplo 1: Um fornecedor de manetes esportivos para motocicletas recebeu pedidos de algumas lojas. A figura a seguir apresenta a capacidade do fornecedor, as demandas de cada loja e os respectivos custos unitários de transporte. Sabendo que o objetivo do fornecedor é minimizar o custo total de transporte, determine quantas unidades deverão ser transportadas do fornecedor para cada uma das lojas. Resolução: Variáveis: x1 = quantidade de manetes a serem transportados do depósito para a loja 1 x2 = quantidade de manetes a serem transportados do depósito para a loja 2 x3 = quantidade de manetes a serem transportados do depósito para a loja 3 Obs.: Demanda maior do que a oferta. Formulação: min C=3x1+7x2+5x3 s.a. x1+x2+x3>=2000 x1<=550 x2<=1200 17 x3<=720 No Python: import sys !{sys.executable} -m pip install pulp from pulp import * prob = LpProblem('Exemplo',LpMinimize) x1=LpVariable("Depósito para loja 1",0) x2=LpVariable("Depósito para loja 2",0) x3=LpVariable("Depósito para loja 3",0) prob += 3*x1+7*x2+5*x3 prob += x1+x2+x3>=2000 prob += x1<=550 prob += x2<=1200 prob += x3<=720 prob.solve() for v in prob.variables(): print(v.name, "=", v.varValue) print("Custo mínimo = ", value(prob.objective)) Solução ótima: Do depósito para a loja 1: 550 18 Do depósito para a loja 2: 730 Do depósito para a loja 3: 720 Custo mínimo: R$ 10.360,00 No próximo exemplo, vamos considerar a situação em que a demanda é menor do que a oferta. Quando isto ocorre, na formulação, nas restrições relacionadas à capacidade dos depósitos, utilizaremos restrições de menor ou igual e, nas restrições relacionadas às demandas, utilizaremos restrições de maior ou igual.Exemplo 2: O problema de transporte de uma fábrica de chapas de MDF cru de 15 mm consiste em determinar quantas unidades serão transportadas de cada depósito para cada revenda. No Depósito 1 há 2000 chapas e no Depósito 2 o estoque é de 4000 chapas. A Revenda 1 precisa de 1400 chapas, a Revenda 2 tem uma demanda de 3000 chapas e a Revenda 3 necessita de 1100 chapas. A tabela a seguir apresenta os custos unitários de transporte das chapas de cada depósito para cada revenda: Revenda 1 Revenda 2 Revenda 3 Depósito 1 R$ 10,00 R$ 12,00 R$ 9,00 Depósito 2 R$ 15,00 R$ 11,00 R$ 17,00 Sabendo que o objetivo da fábrica é determinar quantas unidades serão transportadas de cada depósito para cada revenda a fim de minimizar o custo total, formule e resolva o problema como um problema de programação linear. Resolução: Variáveis: x11 = quantidade de chapas a serem transportadas do depósito 1 para a revenda 1 x12 = quantidade de chapas a serem transportadas do depósito 1 para a revenda 2 x13 = quantidade de chapas a serem transportadas do depósito 1 para a revenda 3 x21 = quantidade de chapas a serem transportadas do depósito 2 para a revenda 1 x22 = quantidade de chapas a serem transportadas do depósito 2 para a revenda 2 19 x23 = quantidade de chapas a serem transportadas do depósito 2 para a revenda 3 Obs.: Demanda menor do que a oferta. Formulação: min C=10x11+12x12+9x13+15x21+11x22+17x23 s.a. x11+x12+x13<=2000 x21+x22+x23<=4000 x11+x21>=1400 x12+x22>=3000 x13+x23>=1100 No Python: import sys !{sys.executable} -m pip install pulp from pulp import * prob = LpProblem('Exemplo',LpMinimize) x11=LpVariable("Depósito 1 para revenda 1",0) x12=LpVariable("Depósito 1 para revenda 2",0) x13=LpVariable("Depósito 1 para revenda 3",0) x21=LpVariable("Depósito 2 para revenda 1",0) x22=LpVariable("Depósito 2 para revenda 2",0) x23=LpVariable("Depósito 2 para revenda 3",0) prob += 10*x11+12*x12+9*x13+15*x21+11*x22+17*x23 prob += x11+x12+x13<=2000 prob += x21+x22+x23<=4000 prob += x11+x21>=1400 prob += x12+x22>=3000 prob += x13+x23>=1100 prob.solve() for v in prob.variables(): print(v.name, "=", v.varValue) print("Custo mínimo = ", value(prob.objective)) 20 Solução ótima: Do depósito 1 para a revenda 1: 900 Do depósito 1 para a revenda 2: 0 Do depósito 1 para a revenda 3: 1100 Do depósito 2 para a revenda 1: 500 Do depósito 2 para a revenda 2: 3000 Do depósito 2 para a revenda 3: 0 Custo mínimo: R$ 59.400,00 TEMA 5 – PROBLEMAS DE DESIGNAÇÃO Problemas de designação podem ser considerados como casos particulares de problemas de transporte em que a capacidade de cada origem é igual a 1 e a demanda de cada destino também é igual a 1. São problemas importantes em que o objetivo é associar elementos de modo a maximizar a função objetivo. Podemos, por exemplo, indicar pessoas a determinados cargos, máquinas a localidades, professores a disciplinas a serem ministradas, além de muitas outras possibilidades. 21 Vamos resolver um problema em que o objetivo é alocar representantes a determinadas regiões de modo a maximizar o potencial de vendas de uma empresa. Exemplo 1: Uma empresa de medicamentos possui representantes que atuam em três regiões. A tabela a seguir apresenta o potencial de venda, em porcentagem, dos representantes em cada uma das regiões. Região 1 Região 2 Região 3 Representante 1 85% 97% 82% Representante 2 79% 83% 74% Representante 3 81% 85% 89% Qual deve ser a designação dos representantes para as regiões de modo que o potencial total de venda da empresa seja o maior possível? Resolução: Variáveis: x11 = representante 1 para a região 1 x11 = representante 1 para a região 2 x11 = representante 1 para a região 3 x21 = representante 2 para a região 1 x21 = representante 2 para a região 2 x21 = representante 2 para a região 3 x31 = representante 3 para a região 1 x31 = representante 3 para a região 2 x31 = representante 3 para a região 3 Formulação: max V=85x11+97x12+82x13+79x21+83x22+74x23+81x31+85x32+89x33 s.a. x11+x12+x13==1 x21+x22+x23==1 x31+x32+x33==1 x11+x21+x21==1 x12+x22+x32==1 x13+x23+x33==1 No Python: import sys 22 !{sys.executable} -m pip install pulp from pulp import * prob = LpProblem('Exemplo',LpMaximize) x11=LpVariable("Representante 1 para a região 1",0) x12=LpVariable("Representante 1 para a região 2",0) x13=LpVariable("Representante 1 para a região 3",0) x21=LpVariable("Representante 2 para a região 1",0) x22=LpVariable("Representante 2 para a região 2",0) x23=LpVariable("Representante 2 para a região 3",0) x31=LpVariable("Representante 3 para a região 1",0) x32=LpVariable("Representante 3 para a região 2",0) x33=LpVariable("Representante 3 para a região 3",0) prob += 85*x11+97*x12+82*x13+79*x21+83*x22+74*x23+81*x31+85*x32+89*x33 prob += x11+x12+x13==1 prob += x21+x22+x23==1 prob += x31+x32+x33==1 prob += x11+x21+x31==1 prob += x12+x22+x32==1 prob += x13+x23+x33==1 prob.solve() for v in prob.variables(): print(v.name, "=", v.varValue) print("Potencial máximo = ", value(prob.objective)) 23 Solução ótima: Representante 1 para a região 2 Representante 2 para a região 1 Representante 3 para a região 3 FINALIZANDO Nesta aula estudamos algumas das muitas aplicações da programação linear. Inicialmente, vimos alguns exemplos relacionados ao uso da PL em problemas relacionados à produção. Resolvemos também problemas de PL com aplicações no transporte e no comércio. Estudamos problemas denominados problemas de transporte, que são casos particulares da programação linear. Finalizamos a aula abordando problemas de designação que, mesmo tendo métodos específicos destinados à obtenção da solução ótima, podem ser resolvidos seguindo a mesma abordagem dos problemas de transporte. 24 REFERÊNCIAS BARBOSA, M. A.; ZANARDINI, R. A. D. Iniciação à pesquisa operacional no ambiente de gestão. 3. ed. Curitiba: InterSaberes, 2015. COLIN, E. C. Pesquisa operacional: 170 aplicações em estratégia, finanças, logística, produção, marketing e vendas. São Paulo: Atlas, 2019. HILLIER, F. S.; LIEBERMAN, G. J. Introdução à pesquisa operacional. 9. ed. Porto Alegre: AMGH,2013. LACHTERMACHER, G. Pesquisa operacional na tomada de decisões. 5. ed. Rio de Janeiro: LTC, 2016. TAHA, H. Pesquisa operacional. 8. ed. São Paulo: Pearson Prentice Hall, 2008.
Compartilhar