Programacao Linear Modelagem de Problemas Classicos - Fabricacao, Transporte e Alocacao

DESCRIÇÃO Modelagem de problemas clássicos de programação linear fabricação versus compra problemas de mistura planejamento produção e estoques transporte transbordo e alocação PROPÓSITO Discutir os problemas clássicos de programação linear a fim de entender a técnica de modelagem e a importância desse campo do conhecimento essencial para a sua formação e atuação no processo de decisão de problemas complexos PREPARAÇÃO Tenha em mãos uma calculadora ou um software editor de planilhas eletrônicas para que possa realizar as operações matemáticas necessárias OBJETIVOS MÓDULO 1 Aplicar a técnica de modelagem em problemas clássicos de programação linear MÓDULO 2 Aplicar a técnica de modelagem nos problemas de transporte e transbordo MÓDULO 3 Aplicar a técnica de modelagem em problemas de alocação INTRODUÇÃO Os modelos são simplificações do objeto ou problema de decisão que representam Você pode estar se perguntando como a modelagem matemática pode auxiliar o processo de tomada de decisão em especial em problemas complexos A modelagem matemática possibilita examinar diferentes cenários em geral de forma mais rápida e barata do que analisar a situação na realidade O foco deste conteúdo é a programação linear uma das técnicas mais difundidas na Pesquisa Operacional PO Aqui reforçaremos os conceitos sobre a construção de modelos de programação linear na modelagem de problemas clássicos de programação linear abordando suas diferentes aplicações Com isso passaremos a dominar a técnica de modelagem e entenderemos melhor a importância desse campo do conhecimento em especial a sua aplicação no planejamento de redes logísticas por meio do problema de transporte e transbordo e de alocação problemas clássicos de programação linear que merecem ser destacados APRESENTAÇÃO DO TEMA No vídeo a seguir o especialista apresenta o tema programação linear como ferramenta de gestão Crédito Digital reforçando a importância da modelagem e apresentando alguns problemas clássicos que podem ser solucionados pela programação linear MÓDULO 1 Aplicar a técnica de modelagem em problemas clássicos de programação linear MODELAGEM DE PROBLEMAS DE PROGRAMAÇÃO LINEAR O processo de modelagem consiste em transformar a linguagem do problema em linguagem matemática Para isso devemos começar definindo as variáveis de decisão e posteriormente a função objetivo e as restrições conforme os passos ilustrados abaixo IDENTIFICAÇÃO DAS VARIÁVEIS DE DECISÃO IDENTIFICAÇÃO DA FUNÇÃO OBJETIVO IDENTIFICAÇÃO DO CONJUNTO DE RESTRIÇÕES ATENÇÃO O passo mais importante no desenvolvimento de modelos de programação linear consiste na definição correta das variáveis de decisão Um equívoco na seleção das variáveis de decisão implica erros na identificação da função objetivo e do conjunto de restrições Existem classes de modelos de programação linear que são adaptáveis a uma série de situações práticas sendo considerados como problemas típicos Esses modelos seguem padrões semelhantes de modo que podemos considerar que formam diferentes classes de problemas Assim se soubermos modelar um destes problemas típicos provavelmente conseguiremos modelar os demais problemas da mesma classe Por isso é tão importante conhecer esses padrões e entender a lógica por trás da construção destes modelos matemáticos RODRIGUES et al 2014 Neste módulo serão abordados alguns dos principais modelos de programação linear considerados típicos Devemos entender como funciona o padrão de modelagem para cada problema típico para que então possamos aplicar essa mesma lógica a outros problemas da mesma classe ou seja que seguem o mesmo padrão DICA Estude e faça a maior quantidade de exercícios possível Apenas com a prática você internalizará a lógica e desenvolverá seus modelos com maior facilidade Trataremos a seguir dos problemas da mistura do planejamento de produção e de estoques e fazer versus comprar Estes são problemas clássicos que podem ser aplicados em diferentes setores produtivos PROBLEMA DA MISTURA Muitos modelos de programação linear representam situações em que o tomador de decisão deseja minimizar o custo para atender a determinadas condições restrições O problema da mistura também conhecido como o problema da dieta é um dos modelos clássicos que se encaixa neste tipo de padrão Veja mais informações sobre o problema da dieta O PROBLEMA DA DIETA O problema da dieta foi proposto pela primeira vez por Stiger 1945 tendo sido um dos primeiros problemas de otimização linear a ser implementado na prática com sucesso Neste tipo de problema o tomador de decisão deseja determinar níveis de utilização de matériasprimas na composição de uma ração alimentar que deve respeitar certas características nutricionais estando limitado à disponibilidade de matériasprimas e insumos bem como ao atendimento da demanda É importante destacar que este tipo de problema não se limita à dieta humana sendo aplicado também à elaboração de rações para gado peixe aves etc Entretanto de forma mais ampla o problema da mistura não se restringe apenas à composição de rações alimentares O problema da mistura pode ser aplicado à produção de ligas metálicas à especificação de combustíveis à fabricação de remédios ou de produtos químicos em geral à produção de adubos ou de papel Em suma o problema da mistura representa uma classe de modelos clássicos que podem ser aplicados a diferentes setores Neste tipo de problema diferentes insumos devem ser misturados em uma proporção ideal para fabricar produtos para a comercialização TEORIA NA PRÁTICA EXEMPLO PROBLEMA DA DIETA Uma mãe está muito preocupada com a alimentação de seus filhos Ela deseja que as crianças tenham uma alimentação equilibrada e assim consultou uma nutricionista que lhe recomendou que eles comam no mínimo 10mg de vitamina A 70mg de vitamina C e 250mg de vitamina D por dia Porém além de se preocupar com a qualidade da alimentação essa mãe também está preocupada com os custos Ela deseja oferecer aos seus filhos essa dieta equilibrada porém ao menor custo possível Por isso ela fez uma pesquisa e descobriu as informações nutricionais para diferentes tipos de alimento conforme apresentado na tabela a seguir Vitamina Leite l Carne kg Peixe kg Salada 100g A 2 2 10 20 C 50 20 10 30 D 80 70 10 80 Atenção Para visualizaçãocompleta da tabela utilize a rolagem horizontal Tabela de informações nutricionais em mg Fonte Adaptado de Goldbarg e Luna 2005 A mãe também foi ao supermercado e verificou que um litro de leite custa R200 um quilo de carne custa R2000 um quilo de peixe custa R2500 e para preparar 100g de salada ela gastaria R300 Vamos usar nossos conhecimentos de programação linear para ajudar essa mãe a escolher a melhor dieta para seus filhos com o menor custo possível RESOLUÇÃO DEFINIR VARIÁVEIS DE DECISÃO O primeiro passo para a modelagem deste exemplo de um clássico problema da dieta é a definição das variáveis de decisão A variável de decisão deve ser xᵢ sendo x a quantidade de alimento do tipo i a ser consumida por dia Logo temos x₁ litros de leite a serem consumidos por dia pelas crianças x₂ quilos de carne a serem consumidos por dia pelas crianças x₃ quilos de peixe a serem consumidos por dia pelas crianças x₄ 100g de salada a serem consumidos por dia pelas crianças IDENTIFICAR A FUNÇÃO OBJETIVO Em seguida devemos identificar a função objetivo Sabemos que a mãe deseja gastar o menor valor possível de modo que este deve ser um problema de minimização A mãe já fez a pesquisa de preços então só nos falta montar a função objetivo MIN Z 2X₁20X₂25X₃3X₄ Atenção Para visualização completa da equação utilize a rolagem horizontal IDENTIFICAR O CONJUNTO DE INEQUAÇÕES Porém não se esqueça de que a mãe também está preocupada com a qualidade nutricional da alimentação de seus filhos e que a nutricionista indicou que as crianças devem comer no mínimo 10mg de vitamina A 70mg de vitamina C e 250mg de vitamina D por dia As informações nutricionais em mg de vitamina A C e D dos alimentos leite carne peixe e salada são apresentadas na tabela de informações nutricionais já apresentada Assim podemos identificar o conjunto de inequações que representam estas restrições São elas 2x₁2x₂10x₃20x₄10Vitamina A 50x₁20x₂10x₃30x₄70Vitamina C 80x₁70x₂10x₃80x₄250 Vitamina D Atenção Para visualização completa da equação utilize a rolagem horizontal Não podemos nos esquecer das restrições de não negatividade para as variáveis de decisão Logo temos que x₁x₂x₃x₄0 Atenção Para visualização completa da equação utilize a rolagem horizontal MODELO Enfim temos que o modelo para este exemplo do problema da dieta é Min Z 2x₁20x₂25x₃3x₄ Atenção Para visualização completa da equação utilize a rolagem horizontal Sujeito a 2x₁2x₂10x₃20x₄10 50x₁20x₂10x₃30x₄70 80x₁70x₂10x₃80x₄250 x₁x₂x₃x₄0 Atenção Para visualização completa da equação utilize a rolagem horizontal PROBLEMA DO PLANEJAMENTO DE PRODUÇÃO E DE ESTOQUES Neste tipo de problema desejase determinar níveis para atividades de produção considerando que a capacidade de produção de cada atividade sofra restrições de caráter tecnológico e prático O problema do planejamento de produção pode ser estático ou dinâmico PROBLEMA ESTÁTICO No problema estático considerase a produção em determinado horizonte de programação finito de modo que as formulações contemplam apenas um período conforme verificaremos no exemplo a seguir TEORIA NA PRÁTICA PROBLEMA DO PLANEJAMENTO DE PRODUÇÃO ESTÁTICO Uma fábrica de bicicletas está planejando seus níveis de produção para o próximo semestre O custo unitário da produção da bicicleta infantil é de R28000 enquanto o custo unitário da produção da bicicleta para adultos é de R62000 São necessários seis trabalhadores para fazer um lote de 8 bicicletas infantis por dia enquanto três trabalhadores conseguem fabricar 5 bicicletas de adulto por dia Existem 200 pessoas disponíveis para a produção de bicicletas podendo ser alocadas em qualquer um dos dois serviços A fábrica tem capacidade máxima de produção de 300 bicicletas Ainda para atender à demanda existente devem ser produzidos no mínimo 20 lotes de bicicletas infantis e 15 lotes de bicicletas de adultos Formule o modelo de programação linear para minimizar o custo de produção da fábrica RESOLUÇÃO O primeiro passo para a construção de qualquer modelo consiste em identificar as variáveis de decisão para o problema Neste caso a variável de decisão deve ser xi sendo x a quantidade de bicicletas do tipo i a ser produzida por dia Logo temos x₁ número de bicicletas infants a serem produzidas por dia x₂ número de bicicletas infants a serem produzidas por dia Em seguida passamos à definição da função objetivo A fábrica tem como meta minimizar o seu custo de produção diário Assim como o custo unitário da produção da bicicleta infantil é de R28000 e da bicicleta de adulto é de R62000 temos a seguinte função objetivo Min Z 280x₁620x₂ Atenção Para visualização completa da equação utilize a rolagem horizontal A fábrica emprega 200 funcionários por dia São necessários seis trabalhadores para fazer um lote de 8 bicicletas infants por dia logo cada trabalhador produziria 075 bicicletas por dia Três trabalhadores fabricam 5 bicicletas de adulto por dia logo cada trabalhador produziria 0625 bicicletas Com esses dados conseguimos definir a restrição da fábrica com relação à capacidade de mão de obra 075x₁06x₂ 200 Atenção Para visualização completa da equação utilize a rolagem horizontal A fábrica tem capacidade máxima de produção de 300 bicicletas Logo a restrição com relação à capacidade da fábrica é x₁x₂ 300 Atenção Para visualização completa da equação utilize a rolagem horizontal Além disso para atender à demanda existente devem ser produzidos no mínimo 20 lotes de bicicletas infants Como cada lote é composto por 8 bicicletas infants devem ser produzidas ao menos 160 bicicletas infants x₁ 160 Atenção Para visualização completa da equação utilize a rolagem horizontal Por sua vez devem ser produzidos 15 lotes de bicicletas de adultos com 5 bicicletas em cada um de modo que x₂ 75 Atenção Para visualização completa da equação utilize a rolagem horizontal Enfim temos que o modelo para este exemplo do problema de planejamento da produção estático é Min Z 280x₁620x₂ Sujeito a 075x₁06x₂ 200 x₁x₂ 300 x₁ 160 x₂ 75 Atenção Para visualização completa da equação utilize a rolagem horizontal Repare que neste caso não são necessárias as restrições de não negatividade das variáveis de decisão devido às restrições para o atendimento mínimo da demanda Neste exemplo resolvemos um problema de planejamento de produção estático Contudo em situações reais é mais comum realizar o planejamento para diferentes períodos de tempo Nesses casos são necessários modelos dinâmicos ou seja que utilizam formulações do tipo multiperíodo PROBLEMA DINÂMICO Nos modelos de programação dinâmica as disponibilidades de matériaprima e de mão de obra e até os lucros podem variar ao longo do tempo Também são considerados os níveis de estoque visando sempre atender à demanda em todos os períodos com o menor custo possível A seguir vamos desenvolver o modelo matemático para um problema de planejamento de produção dinâmico TEORIA NA PRÁTICA PROBLEMA DO PLANEJAMENTO DE PRODUÇÃO DINÂMICO Uma fábrica de bicicletas está planejando seus níveis de produção para os próximos seis meses A fábrica tem capacidade máxima de estocar 6000 bicicletas Os dados com relação à produção máxima mensal ao custo unitário de produção e à demanda mensal são apresentados na tabela a seguir Mês 1 2 3 4 5 6 Custo unitário de produção R 24000 25000 26500 28500 28000 26000 Demanda unidades 1000 4500 6000 5500 3500 4000 Produção máxima unidades 4000 3500 4000 4500 4000 3500 Atenção Para visualizaçãocompleta da tabela utilize a rolagem horizontal Dados de produção de bicicletas Fonte Adaptado de Ragsdale 2009 Sabese que o estoque inicial do semestre é de 2750 unidades e que o custo de estoque é equivalente a 15 do custo unitário de produção no mesmo mês Desenvolva o modelo matemático para minimizar o custo total da fábrica no próximo semestre RESOLUÇÃO O primeiro passo para a modelagem deste exemplo de um clássico problema de planejamento de produção dinâmico é a definição das variáveis de decisão As variáveis de decisão devem ser xᵢ sendo x o número de unidades de bicicletas a serem produzidas no mês i e eᵢ sendo e o inventário inicial do mês i Logo temos xᵢ número de unidades a produzir no mês i i1 a 6 eᵢ inventário inicial mês i i1 a 6 COMENTÁRIO Repare que pela primeira vez estamos modelando um problema em que o índice da variável de decisão se refere ao período de tempo pois estamos analisando a situação ao longo do tempo Conhecendo o custo unitário de produção e o custo de estoque de cada mês conseguimos determinar a função objetivo para a minimização dos custos da fábrica Min Z 240x₁250x₂265x₃285x₄280x₅260x₆ 36e₁e₂2 375e₂e₃2 398e₃e₄2 428e₄e₅2 420e₅ e₆2 39e₆e₇2 Atenção Para visualização completa da equação utilize a rolagem horizontal Observe que o estoque inicial em dado mês equivale ao estoque final do mês anterior e que estamos considerando o custo do estoque médio no mês Assim para o custo de estoque consideramos que o nível de estoque é a média entre o valor de inventário inicial e final do mês eₘ eᵢ eᵢ₁2 Atenção Para visualização completa da equação utilize a rolagem horizontal A produção de unidades de bicicleta por mês deve ser no mínimo o suficiente para atender à demanda porém não pode superar a produção máxima mensal Logo temos as seguintes restrições com relação aos níveis de produção 2000x₁ 4000 mês 1 1750 x₂ 3500 mês 2 2000 x₃ 4000 mês 3 2250 x₄ 4500 mês 4 2000 x₅ 4000 mês 5 1750 x₆ 3500 mês 6 Atenção Para visualização completa da equação utilize a rolagem horizontal Sabese também que a capacidade máxima de estoque na fábrica é de 6000 unidades de bicicletas Logo o estoque final em cada mês não pode ser superior a essa capacidade máxima de modo que esta restrição será do tipo Como o Estoque final Estoque inicial produção unidades vendidas temos x₁ e₁ 1000 6000 mês 1 x₂ e₂ 4500 6000 mês 2 x₃ e₃ 6000 6000 mês 3 x₄ e₄ 5500 6000 mês 4 x₅ e₅ 3500 6000 mês 5 x₆ e₆ 4000 6000 mês 6 Atenção Para visualização completa da equação utilize a rolagem horizontal Ainda em relação ao estoque é necessário o balanço do inventário representado pelas seguintes restrições e₁ 2750 e₂ e₁ x₁ 1000 e₃ e₂ x₂ 4500 e₄ e₃ x₃ 6000 e₅ e₄ x₄ 5500 e₆ e₅ x₅ 3500 e₇ e₆ x₆ 4000 Atenção Para visualização completa da equação utilize a rolagem horizontal Enfim temos que o modelo para este exemplo do problema de planejamento da produção dinâmico é Min Z 240x₁250x₂265x₃285x₄280x₅260x₆ 36e₁e2 375e₂e₃2 398e₃e₄2 428e₄e₅2 420e₅ e₆2 39e₆e₇2 Atenção Para visualização completa da equação utilize a rolagem horizontal Sujeito a 2000x₁ 4000 mês 1 1750 x2 3500 mês 2 2000 x3 4000 mês 3 2250 x4 4500 mês 4 2000 x5 4000 mês 5 1750 x6 3500 mês 6 x1 e1 1000 6000 mês 1 x2 e2 4500 6000 mês 2 x3 e3 6000 6000 mês 3 x4 e4 5500 6000 mês 4 x5 e5 3500 6000 mês 5 x6 e6 4000 6000 mês 6 e1 2750 e2 e1 x1 1000 e3 e2 x2 4500 e4 e3 x3 6000 e5 e4 x4 5500 e6 e5 x5 3500 e7 e6 x6 4000 Atenção Para visualização completa da equação utilize a rolagem horizontal PROBLEMA FAZER X COMPRAR As organizações enfrentam no seu dia a dia o dilema de fazer ou comprar AO SE DECIDIR ENTRE A FABRICAÇÃO INTERNA OU A AQUISIÇÃO DE DETERMINADO COMPONENTE NO MERCADO AS EMPRESAS COSTUMAM REALIZAR A ANÁLISE ECONÔMICA OU SEJA COMPARAR OS CUSTOS DE FABRICAÇÃO AO CUSTO DE AQUISIÇÃO DiSERIO SAMPAIO 2001 De acordo com Slack et al 1997 fornecedores externos podem se especializar na produção de certos componentes e produzilos a custos menores e com melhor qualidade que a própria empresa Assim sendo as empresas devem decidir entre fazer ou comprar determinado componente Modelos de programação linear podem ser utilizados para auxiliar no processo decisório em relação à terceirização tal como podemos verificar no exemplo a seguir TEORIA NA PRÁTICA PROBLEMA FAZER X COMPRAR Uma fábrica de bicicletas acaba de receber um pedido de R75000000 Foram encomendadas 3000 bicicletas do modelo 1 2000 do modelo 2 e 1000 do modelo 3 São necessárias 2 horas para a montagem da bicicleta do modelo 1 e 1 hora para sua pintura Para a bicicleta do modelo 2 levase 15 horas para a montagem e 2 horas para a pintura Para a bicicleta do modelo 3 são necessárias 3 horas de montagem e 1 hora de pintura A fábrica tem disponibilidade de 10000 horas para montagem e 6000 horas para pintura até a entrega da encomenda Os custos para a fabricação das bicicletas são R35000 para a bicicleta 1 R40000 para a bicicleta 2 e R43000 para a bicicleta 3 A fábrica teme não ter tempo hábil para produzir toda a encomenda e por isso cotou o custo de terceirizar a sua fabricação O custo para comprar uma bicicleta do modelo 1 seria de R46000 de R54000 para a bicicleta do modelo 2 e de R 58000 para a bicicleta do modelo 3 Desenvolva o modelo de programação linear para minimizar o custo de produção da encomenda de bicicletas RESOLUÇÃO A fábrica teme não ter tempo hábil para realizar a produção de bicicletas para a entrega e por isso precisa decidir entre fabricálas ou comprálas de outro fabricante Assim teremos dois tipos de variáveis de decisão na modelagem deste problema xi quantidade de bicicleta do modelo i a ser fabricada internamente ci quantidade de bicicleta do modelo i a ser comprada de concorrente Logo as variáveis de decisão para este exemplo são x1 quantidade de bicicleta do modelo 1 a ser fabricada internamente x2 quantidade de bicicletas do modelo 2 a ser fabricada internamente x3 quantidade de bicicletas do modelo 3 a ser fabricada internamente c1 quantidade de bicicletas do modelo 1 a ser comprada de concorrente c2 quantidade de bicicletas do modelo 2 a ser comprada de concorrente c3 quantidade de bicicletas do modelo 3 a ser comprada de concorrente Conhecendo os custos de produção e de aquisição dos diferentes modelos de bicicletas temos a seguinte função objetivo Min Z 350x1400x2430x3 460c1540c2580c3 Atenção Para visualização completa da equação utilize a rolagem horizontal Foram encomendadas 3000 bicicletas do modelo 1 2000 do modelo 2 e 1000 do modelo 3 de modo que a restrição de demanda é representada pelas seguintes equações x1 c1 3000 demanda para o modelo 1 x2 c2 2000 demanda para o modelo 2 x3 c3 900 demanda para o modelo 3 Atenção Para visualização completa da equação utilize a rolagem horizontal A fábrica tem disponibilidade de 10000 horas para montagem e 6000 horas para pintura até a entrega da encomenda Essas restrições são 2x1 15x2 3x3 10000 montagem 1x1 2x2 1x3 5000 pintura Atenção Para visualização completa da equação utilize a rolagem horizontal Além disso há a condição de não negatividade das variáveis de decisão x1 x2 x3 c1 c2 c3 0 Atenção Para visualização completa da equação utilize a rolagem horizontal Enfim temos que o modelo para este exemplo do problema de fazer x comprar é Min Z 350x1400x2430x3 460c1540c2580c3 Atenção Para visualização completa da equação utilize a rolagem horizontal Sujeito a x1 c1 3000 x2 c2 2000 x3 c3 900 2x1 15x2 3x3 10000 x1 2x2 x3 5000 x1 x2 x3 c1 c2 c3 0 Atenção Para visualização completa da equação utilize a rolagem horizontal É importante ressaltar que a decisão sobre a terceirização é um pouco simplificada pois focamse apenas os aspectos econômicos Contudo a terceirização de determinados produtos ou serviços deve incluir outras considerações além de questões econômicas devendo além disso considerar aspectos estratégicos como competências essenciais e vantagens competitivas Ao delegar certos serviços a terceiros outsourcing a empresa pode se concentrar em sua competência central mantendose competitiva no mercado VERIFICANDO O APRENDIZADO MÓDULO 2 Aplicar a técnica de modelagem nos problemas de transporte e transbordo PROBLEMAS DE TRANSPORTE O problema de transportes é a aplicação de programação linear mais frequente na logística Esse padrão de problema envolve decisões como o volume a ser transportado entre localidades podendo envolver ou não decisões referentes ao desenho da cadeia e também problemas de localização O problema de programação linear para o problema clássico de transportes consiste em definir o melhor caminho ou rota para fazer com que determinada quantidade de produtos de um ponto de suprimento chegue a um ponto de demanda O objetivo pode ser minimizar as distâncias percorridas o custo de transporte ou até mesmo maximizar os níveis de serviço ou o lucro com vendas O problema de transporte é um modelo fluxo em grafo bipartido de modo que não existem nós intermediários de transbordo ou transição para fluxo conforme ilustrado Rede do problema de transportes ATENÇÃO Na rede de transportes os nós representam os pontos de suprimento e de demanda enquanto os arcos representam a conexão entre os nós Conforme pode ser observado no problema de transportes há m pontos de suprimento cada um com capacidade de oferta máxima designada por Si onde o índice i representa o ponto de suprimento em questão i 1 m Existem ainda n pontos de demanda a serem abastecidos por estes pontos de suprimento Cada ponto de demanda recebe pelo menos Dj unidades do produto a ser transportado sendo que o índice j representa os pontos de demanda tal que j 1 n Para cada unidade do ponto de fornecimento i remetida ao ponto de demanda j incorre um custo cij que é o custo de fornecer o produto ao ponto de demanda j a partir do ponto de suprimento i Assim sendo para modelar o problema de transportes consideramos a variável de decisão xij que representa o número de unidades do produto específico despachadas do ponto de suprimento i para o ponto de demanda j Considerando que a função objetivo seja minimizar o custo total de transporte temos que a função objetivo é Atenção Para visualização completa da equação utilize a rolagem horizontal As condições de transporte estão sujeitas a restrições de fornecimento e de demanda Logo o total transportado para o ponto de demanda tem que ao menos atender à quantidade mínima demandada enquanto o total transportado a partir do ponto de suprimento não pode ser superior à sua capacidade de oferta Logo as restrições para o problema clássico de transportes podem ser representadas pelas seguintes equações Atenção Para visualização completa da equação utilize a rolagem horizontal Em suma o modelo matemático para o problema clássico de transporte é Atenção Para visualização completa da equação utilize a rolagem horizontal Sujeito a Atenção Para visualização completa da equação utilize a rolagem horizontal Para facilitar o entendimento do modelo matemático para o problema clássico de transportes vamos resolver o exemplo a seguir TEORIA NA PRÁTICA PROBLEMA DE TRANSPORTE Uma empresa fabricante de bicicletas conta com duas plantas uma localizada em São Paulo e outra em Recife A empresa atende ao público por meio de três revendedores localizados em Porto Alegre Brasília e Manaus Rede do problema de transportes Custos de envio por unidade Plantas Mercados Ofertas Porto Alegre Brasília Manaus SP 25 30 70 600 Recife 60 35 50 700 Demandas 450 500 300 Atenção Para visualizaçãocompleta da tabela utilize a rolagem horizontal Distâncias para a rede do problema de transportes Fonte Renata Albergaria de Mello Bandeira Formule o problema de programação linear que minimize os custos de distribuição da empresa RESOLUÇÃO Consideramos que i1 para São Paulo e i2 para Recife enquanto j1 para Porto Alegre j2 para Brasília e j3 para Manaus Logo as variáveis de decisão são x11 quantidade de produtos transportados de São Paulo para Porto Alegre x12 quantidade de produtos transportados de São Paulo para Brasília x13 quantidade de produtos transportados de São Paulo para Manaus x21 quantidade de produtos transportados de Recife para Porto Alegre x22 quantidade de produtos transportados de Recife para Brasília x23 quantidade de produtos transportados de Recife para Manaus A função objetivo para minimizar o custo total de transporte é Minz Z25X1130X1270X1360X2135X2250X23 Atenção Para visualização completa da equação utilize a rolagem horizontal O total transportado para Porto Alegre tem que ser ao menos igual a 450 para atender à demanda mínima da cidade Para Brasília e Manaus devem ser transportadas no mínimo 500 e 300 bicicletas respectivamente Assim as restrições referentes à demanda são X11X21 450 à restrição quanto demanda para Porto Alegre X12X22 500à restrição quanto demanda para Brasília X13X23 300à restrição quanto demanda para Manaus Atenção Para visualização completa da equação utilize a rolagem horizontal O total transportado de São Paulo não pode ser superior a 600 unidades pois tratase da capacidade máxima de oferta da planta Já o total transportado de Recife deve ser inferior a 700 unidades que é a capacidade máxima de oferta desta planta Assim as restrições referentes à oferta são X11X12X13600à restrição quanto ao suprimento de São Paulo X21X22X23700à restrição quanto ao suprimento de Recife Atenção Para visualização completa da equação utilize a rolagem horizontal O modelo matemático deste problema é Minz Z25X1130X1270X1360X2135X2250X23 Atenção Para visualização completa da equação utilize a rolagem horizontal Sujeito a X11X21450 X12 X22500 X13 X23300 X11X12X13600 X21 X22 X23700 X11 X12 X13 X21 X22 X230 Atenção Para visualização completa da equação utilize a rolagem horizontal SAIBA MAIS Os problemas de transporte são casos particulares de problemas de programação linear de modo que sua resolução algébrica pode ser desenvolvida por algoritmos de programação linear Entretanto é possível aproveitar as particularidades do problema de transporte para resolvêlo de forma mais eficiente que o caso geral do simplex Assim existem algoritmos específicos para a solução do problema de transporte como o Método do Canto Noroeste e o Método de Vogel porém não vamos abordálos aqui Caso você tenha interesse em aprofundar os seus conhecimentos recomendase a leitura do capítulo 7 de Winston 2004 PROBLEMA DE TRANSBORDO O problema de transbordo segue lógica semelhante ao problema de transportes porém este não é um modelo fluxo em grafo bipartido pois existem nós intermediários de transbordo ou de transição para fluxo conforme ilustrado na figura a seguir Rede do problema de transbordo Além de um conjunto de m nós que representam os pontos de suprimentos e n nós que representam os pontos de demanda a rede também dispõe de l pontos de transbordo É importante que você saiba bem a diferença entre estes diferentes tipos de nó PONTOS DE SUPRIMENTO São responsáveis pelo fornecimento de insumos de modo que podem remetêlos para outros pontos porém não podem recebêlos PONTOS DE DEMANDA São os pontos de consumo de modo que devem receber insumos de outros pontos porém não podem recebêlos PONTOS DE TRANSBORDO Podem tanto receber insumos de outros pontos quanto remeter insumos para outros pontos ou seja são locais onde é possível realizar a transferência da carga Um centro de distribuição por exemplo pode funcionar como um ponto de transbordo em uma cadeia logística recebendo insumos de diversas plantas ou diversos fornecedores realizando a consolidação da carga e remetendo insumos para outras plantas outros centros de distribuição ou clientes Um depósito também é um bom exemplo de um ponto de transbordo Uma particularidade do problema de transbordo é que aquilo que é transportado das unidades intermediárias de transbordo aos mercados consumidores não deve ultrapassar a quantidade de produto que chega a tais pontos A quantidade que insumos que chega a um ponto de transbordo deve ser igual à quantidade de insumos que sai dele Com essa restrição garantimos o equilíbrio do fluxo neste nó ou seja o fluxo que entra deve ser igual a todo o fluxo que sai Portanto o modelo matemático para o problema de transbordo é semelhante ao do problema clássico de transporte porém acrescentase a restrição de equilíbrio nos nós que representam pontos de transbordo Temos que o modelo matemático para o problema de transbordo é Min sumi1m sumj1n cij xij Atenção Para visualização completa da equação utilize a rolagem horizontal Sujeito a sumj1n xij si i1 m sumi1m xij dj j1 n sumi1m xik sumj1n xkj k1 l Equilíbrio nos nós de transbordo T xij 0 ij Atenção Para visualização completa da equação utilize a rolagem horizontal Para facilitar o entendimento do modelo matemático para o problema clássico de transbordo vamos resolver o exemplo a seguir TEORIA NA PRÁTICA PROBLEMA DE TRANSBORDO Uma empresa fabricante de bicicletas conta com duas plantas uma localizada em São Paulo e outra em Recife e atende o público por meio de dois revendedores localizados em Porto Alegre e Manaus A empresa também dispõe de um centro de distribuição localizado em Brasília que pode ser usado como ponto de transbordo caso contribua para reduzir o custo total de transporte Rede do problema de transbordo PlantasCD Custos de envio por unidade MercadosCD Ofertas Porto Alegre Manaus Brasília SP 25 70 30 600 Recife 60 50 35 700 Brasília 45 65 0 Demandas 450 500 Atenção Para visualizaçãocompleta da tabela utilize a rolagem horizontal Demandas e custos de transporte por unidade Fonte Renata Albergaria de Mello Bandeira RESOLUÇÃO Consideramos que i1 para São Paulo i2 para Recife e i3 para Brasília enquanto j1 para Porto Alegre j2 para Manaus e j3 para Brasília Logo as variáveis de decisão são x11 quantidade de produtos transportados de São Paulo para Porto Alegre x12 quantidade de produtos transportados de São Paulo para Manaus x13 quantidade de produtos transportados de São Paulo para Brasília x21 quantidade de produtos transportados de Recife para Porto Alegre x22 quantidade de produtos transportados de Recife para Manaus x23 quantidade de produtos transportados de Recife para Brasília x31 quantidade de produtos transportados de Brasília para Porto Alegre x32 quantidade de produtos transportados de Brasília para Manaus A função objetivo para minimizar o custo total de transporte é Min Z25X1170X1230X1360X2150X2235X2345X3165X32 Atenção Para visualização completa da equação utilize a rolagem horizontal O total transportado para Porto Alegre tem que ser ao menos igual a 450 para atender à demanda mínima da cidade Para Brasília e Manaus devem ser transportadas no mínimo 500 e 300 bicicletas respectivamente Assim as restrições referentes à demanda são X11X21 X31450 restrição quanto à demanda para Porto Alegre X12X22 X32500 restrição quanto à demanda para Manaus Atenção Para visualização completa da equação utilize a rolagem horizontal O total transportado de São Paulo não pode ser superior a 600 unidades pois esta é a capacidade máxima de oferta da planta Já o total transportado de Recife deve ser inferior a 700 unidades que é a capacidade máxima de oferta desta planta Assim as restrições referentes à oferta são X11X12X13600 restrição quanto ao suprimento de São Paulo X21X22X23700 restrição quanto ao suprimento de Recife Atenção Para visualização completa da equação utilize a rolagem horizontal Lembrese ainda da restrição de equilíbrio nos nós que representam pontos de transbordo Tudo o que chega no centro de distribuição de Brasília deve ser igual ao que sai de Brasília conforme indicado na equação a seguir X11 X23X31X32 Atenção Para visualização completa da equação utilize a rolagem horizontal O modelo matemático deste problema é Min Z25X1170X1230X1360X2150X2235X2345X3165X32 Atenção Para visualização completa da equação utilize a rolagem horizontal Sujeito a X11X21 X31450 X12X22 X32500 X11X12X13600 X21X22X23700 X11 X23X31X32 X11 X12 X13 X21 X22 X23 X31X32 0 Atenção Para visualização completa da equação utilize a rolagem horizontal PROBLEMA DE TRANSPORTE E TRANSBORDO A seguir o especialista apresenta os problemas de transporte e de transbordo abordando as particularidades deste tipo de problema de programação linear e a importância de sua aplicação no ambiente gerencial VERIFICANDO O APRENDIZADO MÓDULO 3 Aplicar a técnica de modelagem em problemas de alocação PROBLEMAS DE ALOCAÇÃO No problema de alocação também denominado problema de designação ou de matching existem dois conjuntos e devem ser formados pares entre os elementos destes dois conjuntos O problema consiste em determinar a formação destes pares ou seja a combinação destes elementos de modo a minimizar o custo total de todas as alocações respeitando as restrições existentes ATENÇÃO O problema da alocação visa designar tarefas a designados podendo ser pessoas máquinas veículos ou até mesmo fábricas Neste tipo de problema há um custo associado para o designado desempenhar cada tarefa Assim o objetivo final é determinar a combinação de alocações que minimiza o custo total Também pode ser considerado que cada designado i tem determinado interesse em efetuar cada tarefa j dado por pij Logo o objetivo é realizar a alocação de maneira que a soma dos interesses seja maximizada ATENÇÃO Destacase que no problema de alocação o número de designados e de tarefas devem ser iguais Assim temos n designados e n tarefas Cada tarefa deve ser atribuída a apenas um designado que também só deve realizar uma única tarefa Além disso todas as tarefas devem ser executadas O problema da alocação pode ser considerado um caso especial do modelo de transportes no qual cada origem tem uma unidade disponível e cada destino requer também uma unidade Assim o problema de alocação é um problema de transporte balanceado no qual todas as demandas e capacidades são iguais a 1 Desse modo o problema de alocação utiliza variáveis binárias A variável binária ou booleana pode assumir apenas dois valores zero ou 1 No problema de alocação a variável de decisão xij recebe o valor igual a 1 se decidirmos que a tarefa i será alocada para o designado j sendo 0 se decidirmos o contrário De tal forma temos que o modelo matemático para o problema da alocação é MinZΣiΣjcijxij Atenção Para visualização completa da equação utilize a rolagem horizontal Sujeito a Σjxij1 i1n cada designado é alocado a uma só tarefa Σixij1 j1n cada tarefa é alocada a apenas um trabalhador Xij 01 i1n j1n Xij1 se o designado i for alocado para realizar a tarefa j Xij0 caso contrário Atenção Para visualização completa da equação utilize a rolagem horizontal SAIBA MAIS Os modelos de alocação podem ser adotados para auxiliar no processo de tomada de decisão em diversas situações reais tal como na determinação da escala de vendedores para pontos de venda na distribuição de atividades para membros de uma equipe ou na alocação de máquinas para resolver diferentes tarefas Para facilitar o entendimento do modelo matemático para o problema clássico de alocação vamos resolver o exemplo a seguir TEORIA NA PRÁTICA A supervisora de uma equipe de limpeza em um hotel necessita formar equipes de camareiras para realizar a limpeza dos quartos na hora de troca de hóspedes Os hóspedes que estão realizando checkout precisam sair do quarto até às 12h enquanto os novos hóspedes podem realizar o checkin a partir de 14h Assim as equipes têm pouco tempo para organizar e limpar todos os cômodos Logo a supervisora precisa organizar as equipes de modo que os serviços sejam realizados o mais rápido possível A supervisora precisa formar a equipe para cuidar dos quartos do terceiro andar do hotel As tarefas a serem realizadas são arrumar as camas limpar o banheiro varrer o quarto e tirar o pó As camareiras desempenham as tarefas por quarto nos seguintes tempos Camareira Tarefa Arrumar cama Limpar banheiro Varrer quarto Tirar o pó Lara 2 min 5 min 7 min 3 min Ana 3 min 6 min 8 min 4 min Julia 4 min 4 min 6 min 5 min Talita 2 min 5 min 7 min 2 min Atenção Para visualização completa da tabela utilize a rolagem horizontal Tempo para execução das tarefas Fonte Renata Albergaria de Mello Bandeira Formule o problema de programação linear que minimize o tempo de arrumação do quarto RESOLUÇÃO Neste problema de alocação a variável de decisão xij recebe o valor igual a 1 se decidirmos que a tarefa i será alocada para o designado j sendo 0 se decidirmos o contrário De tal forma temos x11 1 se Lara arruma a cama zero caso contrário x12 1 se Lara limpa banheiro zero caso contrário x13 1 se Lara varre o quarto zero caso contrário x141 se Lara tira o pó zero caso contrário x21 1 se Ana arruma a cama zero caso contrário x22 1 se Ana limpa banheiro zero caso contrário x23 1 se Ana varre o quarto zero caso contrário x24 1 se Ana tira o pó zero caso contrário x31 1 se Julia arruma a cama zero caso contrário x32 1 se Julia limpa banheiro zero caso contrário x33 1 se Julia varre o quarto zero caso contrário x34 1 se Julia tira o pó zero caso contrário x41 1 se Talita arruma a cama zero caso contrário x42 1 se Talita limpa banheiro zero caso contrário x43 1 se Talita varre o quarto zero caso contrário x44 1 se Talita tira o pó zero caso contrário O modelo matemático para o problema da alocação é Min Z 2X115X127X133X143X216X228X234X244X314X326X335X342X415X427X432X44 Atenção Para visualização completa da equação utilize a rolagem horizontal Sujeito a X11X12X13X141 X21X22X23X241 X31X32X33X341 Cada trabalhador desempenha apenas uma tarefa X41X42X43X441 X11X21X31X411 X13X23X33X431 X12X22X32X421 Cada tarefa é alocada para apenas um trabalhador X14X24X34X441 X11 X12 X13 X14 X21 X22 X23 X24 X31 X32 X33 X34 X41 X42 X43 X44 01 Atenção Para visualização completa da equação utilize a rolagem horizontal SAIBA MAIS Assim como o problema de transportes o problema da alocação também é um caso particular de problemas de programação linear de modo que sua resolução algébrica pode ser desenvolvida por algoritmos de programação linear Porém tal como o problema de transportes possui particularidades específicas que podem ser aproveitadas para resolvêlo de forma mais eficiente Assim como para a solução do problema de transporte com o Método do Canto Noroeste e o Método de Vogel também existem algoritmos específicos para a solução do problema de alocação a exemplo do algoritmo húngaro Porém não vamos abordálos aqui Caso você tenha interesse em aprofundar os seus conhecimentos recomendase a leitura do capítulo 7 de Winston 2004 EXEMPLO DE PROBLEMA DE ALOCAÇÃO No vídeo a seguir o especialista apresenta um problema de alocação e desenvolve a resolução detalhadamente até a obtenção do resultado final VERIFICANDO O APRENDIZADO CONCLUSÃO CONSIDERAÇÕES FINAIS Vimos como a Pesquisa Operacional pode auxiliar no apoio a processos de decisão em especial para problemas complexos Ao longo dos módulos aprendemos sobre modelos matemáticos e como estes podem nos ajudar na análise de decisão em especial por permitirem avaliar a solução do problema em diferentes cenários a um menor tempo e custo Além disso colocamos estes conceitos em prática à medida que aprendemos a construir modelos matemáticos para problemas de programação linear Entretanto é preciso ter em mente que a modelagem não é uma tarefa simples principalmente para aqueles que estão iniciando neste campo do conhecimento Assim para nos familiarizarmos com a técnica de modelagem e podermos construir modelos com mais facilidade é preciso praticar por meio de exercícios A prática é essencial para nos ajudar a entender e a dominar a lógica por trás da modelagem matemática Outro ponto que também facilita a internalização deste conhecimento é entender que alguns modelos conhecidos como problemas típicos seguem padrões semelhantes Portanto se entendemos a lógica por trás dessa categoria de problemas conseguiremos modelar os demais problemas desta mesma classe Por isso é importante conhecer esses padrões No módulo 1 apresentamos os problemas clássicos da mistura do planejamento de produção e de estoques e fazer versus comprar Dedicamos os módulos 2 e 3 para entender a lógica do problema de transporte e de seus casos particulares O destaque para o problema de transporte ocorre porque tratase do modelo de programação linear mais aplicado na área da logística Abordamos ainda no módulo 2 o problema de transbordo enquanto no módulo 3 tratamos especificamente do problema de alocação Até o momento aprendemos a solucionar os modelos matemáticos por meio da aplicação do Método Gráfico Contudo tal método é restrito a problemas mais simples com até duas variáveis de decisão PODCAST Agora o especialista encerra o tema com um resumo sobre aplicações de programação linear REFERÊNCIAS DiSERIO L SAMPAIO M Projeto da cadeia de suprimento uma visão dinâmica da decisão fazer versus comprar In Revista de Administração de Empresas v 41 n 1 p 5466 2001 GOLDBARG M C LUNA H P Otimização combinatória e programação linear 2 ed São Paulo Campus 2005 LACHTERMACHER G Pesquisa operacional na tomada de decisões Rio de Janeiro LTC 2016 RAGSDALE C T Modelagem e análise de decisão São Paulo Cengage Learning 2009 RODRIGUES L H AHLERT F LACERDA D P CAMARGO L F R LIMA P Pesquisa operacional programação linear passo a passo do entendimento do problema à interpretação da solução São Leopoldo Unisinos SLACK N CHAMBERS S HARLAND C HARRISON A JOHNSTON R Administração da produção São Paulo Atlas 1997 STIGER G J The cost of Subsistence Journal of Farm Economics 272 p 303314 1945 WINSTON W L GOLDBERG J B Operations research applications and algorithms Vol 3 Boston Cengage Learning 2004 EXPLORE Para obter mais conhecimento sobre os conteúdos discutidos sugerimos a seguinte leitura WINSTON W L GOLDBERG J B Operations research applications and algorithms Vol 3 Boston Cengage Learning 2004 CONTEUDISTA Renata Albergaria de Mello Bandeira CURRÍCULO LATTES