Aplicações da Programação Linear

Prévia do material em texto

<p>DESCRIÇÃO</p><p>Modelagem de problemas clássicos de programação linear: fabricação versus compra, problemas de</p><p>mistura, planejamento, produção e estoques, transporte, transbordo e alocação.</p><p>PROPÓSITO</p><p>Discutir os problemas clássicos de programação linear a fim de entender a técnica de modelagem e a</p><p>importância desse campo do conhecimento, essencial para a sua formação e atuação no processo de</p><p>decisão de problemas complexos.</p><p>PREPARAÇÃO</p><p>Tenha em mãos uma calculadora ou um software editor de planilhas eletrônicas para que possa realizar as</p><p>operações matemáticas necessárias.</p><p>OBJETIVOS</p><p>MÓDULO 1</p><p>Aplicar a técnica de modelagem em problemas clássicos de programação linear</p><p>MÓDULO 2</p><p>Aplicar a técnica de modelagem nos problemas de transporte e transbordo</p><p>MÓDULO 3</p><p>Aplicar a técnica de modelagem em problemas de alocação</p><p>INTRODUÇÃO</p><p>Os modelos são simplificações do objeto ou problema de decisão que representam. Você pode estar se</p><p>perguntando: como a modelagem matemática pode auxiliar o processo de tomada de decisão, em especial</p><p>em problemas complexos? A modelagem matemática possibilita examinar diferentes cenários, em geral, de</p><p>forma mais rápida e barata do que analisar a situação na realidade.</p><p>O foco deste conteúdo é a programação linear, uma das técnicas mais difundidas na Pesquisa Operacional</p><p>(PO). Aqui, reforçaremos os conceitos sobre a construção de modelos de programação linear na</p><p>modelagem de problemas clássicos de programação linear, abordando suas diferentes aplicações. Com</p><p>isso, passaremos a dominar a técnica de modelagem e entenderemos melhor a importância desse campo do</p><p>conhecimento, em especial, a sua aplicação no planejamento de redes logísticas, por meio do problema de</p><p>transporte e transbordo, e de alocação, problemas clássicos de programação linear que merecem ser</p><p>destacados!</p><p>APRESENTAÇÃO DO TEMA</p><p>No vídeo a seguir, o especialista apresenta o tema programação linear como ferramenta de gestão (Crédito</p><p>Digital), reforçando a importância da modelagem e apresentando alguns problemas clássicos que podem ser</p><p>solucionados pela programação linear.</p><p>MÓDULO 1</p><p> Aplicar a técnica de modelagem em problemas clássicos de programação linear</p><p>MODELAGEM DE PROBLEMAS DE</p><p>PROGRAMAÇÃO LINEAR</p><p>O processo de modelagem consiste em transformar a linguagem do problema em linguagem matemática.</p><p>Para isso, devemos começar definindo as variáveis de decisão e, posteriormente, a função objetivo e as</p><p>restrições, conforme os passos ilustrados abaixo:</p><p>IDENTIFICAÇÃO DAS VARIÁVEIS DE DECISÃO</p><p></p><p>IDENTIFICAÇÃO DA FUNÇÃO OBJETIVO</p><p></p><p>IDENTIFICAÇÃO DO CONJUNTO DE RESTRIÇÕES</p><p> ATENÇÃO</p><p>O passo mais importante no desenvolvimento de modelos de programação linear consiste na definição</p><p>correta das variáveis de decisão. Um equívoco na seleção das variáveis de decisão implica erros na</p><p>identificação da função objetivo e do conjunto de restrições.</p><p>Existem classes de modelos de programação linear que são adaptáveis a uma série de situações práticas,</p><p>sendo considerados como “problemas típicos.” Esses modelos seguem padrões semelhantes, de modo que</p><p>podemos considerar que formam diferentes “classes” de problemas. Assim, se soubermos modelar um</p><p>destes problemas típicos, provavelmente conseguiremos modelar os demais problemas da mesma classe.</p><p>Por isso, é tão importante conhecer esses padrões e entender a lógica por trás da construção destes</p><p>modelos matemáticos (RODRIGUES et al., 2014).</p><p>Neste módulo, serão abordados alguns dos principais modelos de programação linear considerados</p><p>“típicos.” Devemos entender como funciona o padrão de modelagem para cada problema típico para que,</p><p>então, possamos aplicar essa mesma lógica a outros problemas da mesma classe, ou seja, que seguem o</p><p>mesmo padrão.</p><p> DICA</p><p>Estude e faça a maior quantidade de exercícios possível. Apenas com a prática você internalizará a lógica e</p><p>desenvolverá seus modelos com maior facilidade.</p><p>Trataremos, a seguir, dos problemas da mistura, do planejamento de produção e de estoques, e fazer versus</p><p>comprar. Estes são problemas clássicos que podem ser aplicados em diferentes setores produtivos.</p><p>PROBLEMA DA MISTURA</p><p>Muitos modelos de programação linear representam situações em que o tomador de decisão deseja</p><p>minimizar o custo para atender a determinadas condições (restrições). O problema da mistura, também</p><p>conhecido como o problema da dieta, é um dos modelos clássicos que se encaixa neste tipo de padrão.</p><p>Veja mais informações sobre o problema da dieta:</p><p>O PROBLEMA DA DIETA</p><p>O problema da dieta foi proposto pela primeira vez por Stiger (1945), tendo sido um dos primeiros problemas</p><p>de otimização linear a ser implementado na prática com sucesso. Neste tipo de problema, o tomador de</p><p>decisão deseja determinar níveis de utilização de matérias-primas na composição de uma ração alimentar,</p><p>que deve respeitar certas características nutricionais, estando limitado à disponibilidade de matérias-primas</p><p>e insumos, bem como ao atendimento da demanda. É importante destacar que este tipo de problema não se</p><p>limita à dieta humana, sendo aplicado também à elaboração de rações para gado, peixe, aves etc.</p><p>Entretanto, de forma mais ampla, o problema da mistura não se restringe apenas à composição de rações</p><p>alimentares. O problema da mistura pode ser aplicado à produção de ligas metálicas, à especificação de</p><p>combustíveis, à fabricação de remédios ou de produtos químicos em geral, à produção de adubos ou de</p><p>papel. Em suma, o problema da mistura representa uma classe de modelos clássicos, que podem ser</p><p>aplicados a diferentes setores. Neste tipo de problema, diferentes insumos devem ser misturados em uma</p><p>proporção ideal para fabricar produtos para a comercialização.</p><p>TEORIA NA PRÁTICA</p><p>EXEMPLO - PROBLEMA DA DIETA</p><p>Uma mãe está muito preocupada com a alimentação de seus filhos. Ela deseja que as crianças tenham uma</p><p>alimentação equilibrada e, assim, consultou uma nutricionista que lhe recomendou que eles comam, no</p><p>mínimo, 10mg de vitamina A, 70mg de vitamina C e 250mg de vitamina D por dia.</p><p>Porém, além de se preocupar com a qualidade da alimentação, essa mãe também está preocupada com os</p><p>custos. Ela deseja oferecer aos seus filhos essa dieta equilibrada, porém ao menor custo possível. Por isso,</p><p>ela fez uma pesquisa e descobriu as informações nutricionais para diferentes tipos de alimento, conforme</p><p>apresentado na tabela a seguir:</p><p>Vitamina Leite (l) Carne (kg) Peixe (kg) Salada (100g)</p><p>A 2 2 10 20</p><p>C 50 20 10 30</p><p>D 80 70 10 80</p><p>Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal</p><p>Tabela de informações nutricionais em mg</p><p>Fonte: Adaptado de Goldbarg e Luna (2005)</p><p>A mãe também foi ao supermercado e verificou que um litro de leite custa R$2,00, um quilo de carne custa</p><p>R$20,00, um quilo de peixe custa R$25,00 e para preparar 100g de salada ela gastaria R$3,00.</p><p>Vamos usar nossos conhecimentos de programação linear para ajudar essa mãe a escolher a melhor dieta</p><p>para seus filhos com o menor custo possível!</p><p>RESOLUÇÃO</p><p>DEFINIR VARIÁVEIS DE DECISÃO</p><p>O primeiro passo para a modelagem deste exemplo de um clássico problema da dieta é a definição das</p><p>variáveis de decisão. A variável de decisão deve ser xi, sendo x a quantidade de alimento do tipo “i” a ser</p><p>consumida por dia. Logo, temos:</p><p>x1 = litros de leite a serem consumidos por dia pelas crianças;</p><p>x2 = quilos de carne a serem consumidos por dia pelas crianças;</p><p>x3 = quilos de peixe a serem consumidos por dia pelas crianças;</p><p>x4 = 100g de salada a serem consumidos por dia pelas crianças.</p><p>IDENTIFICAR A FUNÇÃO OBJETIVO</p><p>Em seguida, devemos identificar a função objetivo. Sabemos que a mãe deseja gastar o menor valor</p><p>possível, de modo que este deve ser um problema de minimização! A mãe já fez a pesquisa de preços,</p><p>então só nos falta montar a função objetivo:</p><p>MIN Z= 2X1+20X2+25X3+3X4</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>IDENTIFICAR O CONJUNTO DE INEQUAÇÕES</p><p>Porém, não se esqueça de que a mãe também está preocupada com a qualidade nutricional</p><p>da</p><p>alimentação de seus filhos e que a nutricionista indicou que as crianças devem comer, no mínimo, 10mg de</p><p>vitamina A, 70mg de vitamina C e 250mg de vitamina D por dia. As informações nutricionais em mg de</p><p>vitamina A, C e D dos alimentos leite, carne, peixe e salada são apresentadas na tabela de informações</p><p>nutricionais, já apresentada. Assim, podemos identificar o conjunto de inequações que representam estas</p><p>restrições. São elas:</p><p>2x1+2x2+10x3+20x4≥10→Vitamina A</p><p>50x1+20x2+10x3+30x4≥70→Vitamina C</p><p>80x1+70x2+10x3+80x4≥250 →Vitamina D</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Não podemos nos esquecer das restrições de não negatividade para as variáveis de decisão. Logo, temos</p><p>que:</p><p>x1,x2,x3,x4≥0</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>MODELO</p><p>Enfim, temos que o modelo para este exemplo do problema da dieta é:</p><p>Min Z= 2x1+20x2+25x3+3x4</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Sujeito a:</p><p>2x1+2x2+10x3+20x4≥10</p><p>50x1+20x2+10x3+30x4≥70</p><p>80x1+70x2+10x3+80x4≥250</p><p>x1,x2,x3,x4≥0</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>PROBLEMA DO PLANEJAMENTO DE PRODUÇÃO</p><p>E DE ESTOQUES</p><p>Neste tipo de problema, deseja-se determinar níveis para atividades de produção, considerando que a</p><p>capacidade de produção de cada atividade sofra restrições de caráter tecnológico e prático.</p><p>O problema do planejamento de produção pode ser estático ou dinâmico.</p><p>PROBLEMA ESTÁTICO</p><p>No problema estático, considera-se a produção em determinado horizonte de programação finito, de modo</p><p>que as formulações contemplam apenas um período, conforme verificaremos no exemplo a seguir:</p><p>TEORIA NA PRÁTICA</p><p>PROBLEMA DO PLANEJAMENTO DE PRODUÇÃO ESTÁTICO</p><p>Uma fábrica de bicicletas está planejando seus níveis de produção para o próximo semestre. O custo</p><p>unitário da produção da bicicleta infantil é de R$280,00, enquanto o custo unitário da produção da bicicleta</p><p>para adultos é de R$620,00.</p><p>São necessários seis trabalhadores para fazer um lote de 8 bicicletas infantis por dia, enquanto três</p><p>trabalhadores conseguem fabricar 5 bicicletas de adulto por dia. Existem 200 pessoas disponíveis para a</p><p>produção de bicicletas, podendo ser alocadas em qualquer um dos dois serviços.</p><p>A fábrica tem capacidade máxima de produção de 300 bicicletas. Ainda, para atender à demanda existente,</p><p>devem ser produzidos, no mínimo, 20 lotes de bicicletas infantis e 15 lotes de bicicletas de adultos. Formule</p><p>o modelo de programação linear para minimizar o custo de produção da fábrica.</p><p>RESOLUÇÃO</p><p>O primeiro passo para a construção de qualquer modelo consiste em identificar as variáveis de decisão</p><p>para o problema. Neste caso, a variável de decisão deve ser xi, sendo x a quantidade de bicicletas do tipo</p><p>“i” a ser produzida por dia. Logo, temos:</p><p>x1 = número de bicicletas infantis a serem produzidas por dia;</p><p>x2 = número de bicicletas infantis a serem produzidas por dia.</p><p>Em seguida, passamos à definição da função objetivo. A fábrica tem como meta minimizar o seu custo de</p><p>produção diário. Assim, como o custo unitário da produção da bicicleta infantil é de R$280,00, e da bicicleta</p><p>de adulto é de R$620,00, temos a seguinte função objetivo:</p><p>Min Z= 280x1+620x2</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>A fábrica emprega 200 funcionários por dia. São necessários seis trabalhadores para fazer um lote de 8</p><p>bicicletas infantis por dia, logo, cada trabalhador produziria 0,75 bicicletas por dia. Três trabalhadores</p><p>fabricam 5 bicicletas de adulto por dia, logo, cada trabalhador produziria 0,625 bicicletas. Com esses</p><p>dados, conseguimos definir a restrição da fábrica com relação à capacidade de mão de obra:</p><p>0,75x1+0,6x2 ≤200</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>A fábrica tem capacidade máxima de produção de 300 bicicletas. Logo, a restrição com relação à</p><p>capacidade da fábrica é:</p><p>x1+x2 ≤300</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Além disso, para atender à demanda existente devem ser produzidos, no mínimo, 20 lotes de bicicletas</p><p>infantis. Como cada lote é composto por 8 bicicletas infantis, devem ser produzidas, ao menos, 160</p><p>bicicletas infantis.</p><p>x1 ≥160</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Por sua vez, devem ser produzidos 15 lotes de bicicletas de adultos, com 5 bicicletas em cada um, de</p><p>modo que:</p><p>x2 ≥75</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Enfim, temos que o modelo para este exemplo do problema de planejamento da produção estático é:</p><p>Min Z= 280x1+620x2</p><p>Sujeito a:</p><p>0,75x1+0,6x2 ≤200</p><p>x1+x2 ≤300</p><p>x1 ≥160</p><p>x2 ≥75</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Repare que, neste caso, não são necessárias as restrições de não negatividade das variáveis de decisão</p><p>devido às restrições para o atendimento mínimo da demanda.</p><p>Neste exemplo, resolvemos um problema de planejamento de produção estático. Contudo, em situações</p><p>reais, é mais comum realizar o planejamento para diferentes períodos de tempo. Nesses casos, são</p><p>necessários modelos dinâmicos, ou seja, que utilizam formulações do tipo multiperíodo.</p><p>PROBLEMA DINÂMICO</p><p>Nos modelos de programação dinâmica, as disponibilidades de matéria-prima e de mão de obra, e até os</p><p>lucros, podem variar ao longo do tempo. Também são considerados os níveis de estoque, visando sempre</p><p>atender à demanda em todos os períodos, com o menor custo possível.</p><p>A seguir, vamos desenvolver o modelo matemático para um problema de planejamento de produção</p><p>dinâmico.</p><p>TEORIA NA PRÁTICA</p><p>PROBLEMA DO PLANEJAMENTO DE PRODUÇÃO DINÂMICO</p><p>Uma fábrica de bicicletas está planejando seus níveis de produção para os próximos seis meses. A fábrica</p><p>tem capacidade máxima de estocar 6.000 bicicletas. Os dados com relação à produção máxima mensal, ao</p><p>custo unitário de produção e à demanda mensal são apresentados na tabela a seguir:</p><p>Mês 1 2 3 4 5 6</p><p>Custo unitário</p><p>de produção</p><p>(R$)</p><p>240,00 250,00 265,00 285,00 280,00 260,00</p><p>Demanda</p><p>(unidades)</p><p>1.000 4.500 6.000 5.500 3.500 4.000</p><p>Produção</p><p>máxima</p><p>4.000 3.500 4.000 4.500 4.000 3.500</p><p>(unidades)</p><p>Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal</p><p>Dados de produção de bicicletas.</p><p>Fonte: Adaptado de Ragsdale (2009).</p><p>Sabe-se que o estoque inicial do semestre é de 2.750 unidades, e que o custo de estoque é equivalente a</p><p>1,5% do custo unitário de produção no mesmo mês. Desenvolva o modelo matemático para minimizar o</p><p>custo total da fábrica no próximo semestre.</p><p>RESOLUÇÃO</p><p>O primeiro passo para a modelagem deste exemplo de um clássico problema de planejamento de</p><p>produção dinâmico é a definição das variáveis de decisão. As variáveis de decisão devem ser xi, sendo x o</p><p>número de unidades de bicicletas a serem produzidas no mês “i”, e ei, sendo e o inventário inicial do mês</p><p>“i”. Logo, temos:</p><p>xi = número de unidades a produzir no mês i, i=1 a 6</p><p>ei = inventário inicial mês i, i=1 a 6</p><p> COMENTÁRIO</p><p>Repare que pela primeira vez estamos modelando um problema em que o índice da variável de decisão se</p><p>refere ao período de tempo, pois estamos analisando a situação ao longo do tempo.</p><p>Conhecendo o custo unitário de produção e o custo de estoque de cada mês, conseguimos determinar a</p><p>função objetivo para a minimização dos custos da fábrica:</p><p>Min Z= 240x1+250x2+265x3+285x4+280x5+260x6 + 3,6(e1+e2)/2 + 3,75(e2+e3)/2 + 3,98(e3+e4)/2+</p><p>4,28(e4+e5)/2 + 4,20(e5+ e6)/2 + 3,9(e6+e7)/2</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Observe que o estoque inicial em dado mês equivale ao estoque final do mês anterior, e que estamos</p><p>considerando o custo do estoque médio no mês. Assim, para o custo de estoque, consideramos que o</p><p>nível de estoque é a média entre o valor de inventário inicial e final do mês.</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>em =</p><p>ei + ei+1</p><p>2</p><p>A produção de unidades de bicicleta por mês deve ser, no mínimo, o suficiente para atender à demanda,</p><p>porém não pode superar a produção máxima mensal. Logo, temos as seguintes restrições com relação aos</p><p>níveis de produção.</p><p>2.000≤x1 ≤ 4.000 } mês 1</p><p>1.750 ≤ x2 ≤3.500 } mês 2</p><p>2.000 ≤ x3 ≤4.000 } mês 3</p><p>2.250 ≤ x4 ≤ 4.500 } mês 4</p><p>2.000 ≤ x5 ≤4.000 } mês 5</p><p>1.750 ≤ x6 ≤3.500 } mês 6</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Sabe-se também que a capacidade máxima de estoque na fábrica é de 6.000 unidades de bicicletas. Logo,</p><p>o estoque final em cada mês não pode ser superior a essa capacidade máxima, de modo que esta</p><p>restrição será do tipo ≤.</p><p>Como o Estoque final = Estoque inicial + produção - unidades vendidas, temos:</p><p>x1 + e1 - 1.000 < 6.000 } mês 1</p><p>x2 + e2 - 4.500 < 6.000 } mês 2</p><p>x3 + e3 - 6.000 < 6.000 } mês 3</p><p>x4 + e4 - 5.500 < 6.000 } mês 4</p><p>x5 + e5 - 3.500 < 6.000 } mês 5</p><p>x6 + e6 - 4.000 < 6.000 } mês 6</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Ainda em relação ao estoque, é necessário o balanço do inventário, representado pelas seguintes</p><p>restrições:</p><p>e1 = 2750</p><p>e2 = e1 + x1 – 1.000</p><p>e3 = e2 + x2 - 4.500</p><p>e4 = e3 + x3 - 6.000</p><p>e5 = e4 + x4 - 5.500</p><p>e6 = e5 + x5 - 3.500</p><p>e7 = e6 + x6 - 4.000</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Enfim, temos que o modelo para este exemplo do problema de planejamento da produção dinâmico é:</p><p>Min Z= 240x1+250x2+265x3+285x4+280x5+260x6 + 3,6(e1+e)/2 + 3,75(e2+e3)/2 + 3,98(e3+e4)/2+</p><p>4,28(e4+e5)/2 + 4,20(e5+ e6)/2 + 3,9(e6+e7)/2</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Sujeito a:</p><p>2.000≤x1 ≤ 4.000 } mês 1</p><p>1.750 ≤ x2 ≤3.500 } mês 2</p><p>2.000 ≤ x3 ≤4.000 } mês 3</p><p>2.250 ≤ x4 ≤ 4.500 } mês 4</p><p>2.000 ≤ x5 ≤4.000 } mês 5</p><p>1.750 ≤ x6 ≤3.500 } mês 6</p><p>x1 + e1 - 1.000 < 6.000 } mês 1</p><p>x2 + e2 - 4.500 < 6.000 } mês 2</p><p>x3 + e3 - 6.000 < 6.000 } mês 3</p><p>x4 + e4 - 5.500 < 6.000 } mês 4</p><p>x5 + e5 - 3.500 < 6.000 } mês 5</p><p>x6 + e6 - 4.000 < 6.000 } mês 6</p><p>e1 = 2750</p><p>e2 = e1 + x1 – 1.000</p><p>e3 = e2 + x2 - 4.500</p><p>e4 = e3 + x3 - 6.000</p><p>e5 = e4 + x4 - 5.500</p><p>e6 = e5 + x5 - 3.500</p><p>e7 = e6 + x6 - 4.000</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>PROBLEMA FAZER X COMPRAR</p><p>As organizações enfrentam, no seu dia a dia, o dilema de fazer ou comprar.</p><p>AO SE DECIDIR ENTRE A FABRICAÇÃO INTERNA OU A</p><p>AQUISIÇÃO DE DETERMINADO COMPONENTE NO MERCADO,</p><p>AS EMPRESAS COSTUMAM REALIZAR A ANÁLISE</p><p>ECONÔMICA, OU SEJA, COMPARAR OS CUSTOS DE</p><p>FABRICAÇÃO AO CUSTO DE AQUISIÇÃO.</p><p>DiSERIO; SAMPAIO, 2001</p><p>De acordo com Slack et al. (1997), fornecedores externos podem se especializar na produção de certos</p><p>componentes e produzi-los a custos menores e com melhor qualidade que a própria empresa. Assim sendo,</p><p>as empresas devem decidir entre “fazer ou comprar” determinado componente.</p><p>Modelos de programação linear podem ser utilizados para auxiliar no processo decisório em relação à</p><p>terceirização, tal como podemos verificar no exemplo a seguir.</p><p>TEORIA NA PRÁTICA</p><p>PROBLEMA FAZER X COMPRAR</p><p>Uma fábrica de bicicletas acaba de receber um pedido de R$750.000,00. Foram encomendadas 3.000</p><p>bicicletas do modelo 1, 2.000 do modelo 2 e 1.000 do modelo 3.</p><p>São necessárias 2 horas para a montagem da bicicleta do modelo 1 e 1 hora para sua pintura. Para a</p><p>bicicleta do modelo 2, leva-se 1,5 horas para a montagem e 2 horas para a pintura. Para a bicicleta do</p><p>modelo 3, são necessárias 3 horas de montagem e 1 hora de pintura. A fábrica tem disponibilidade de</p><p>10.000 horas para montagem e 6.000 horas para pintura até a entrega da encomenda.</p><p>Os custos para a fabricação das bicicletas são: R$350,00 para a bicicleta 1, R$400,00 para a bicicleta 2 e</p><p>R$430,00 para a bicicleta 3.</p><p>A fábrica teme não ter tempo hábil para produzir toda a encomenda e, por isso, cotou o custo de terceirizar a</p><p>sua fabricação. O custo para comprar uma bicicleta do modelo 1 seria de R$460,00, de R$540,00 para a</p><p>bicicleta do modelo 2 e de R$ 580,00 para a bicicleta do modelo 3.</p><p>Desenvolva o modelo de programação linear para minimizar o custo de produção da encomenda de</p><p>bicicletas.</p><p>RESOLUÇÃO</p><p>A fábrica teme não ter tempo hábil para realizar a produção de bicicletas para a entrega e, por isso, precisa</p><p>decidir entre fabricá-las ou comprá-las de outro fabricante. Assim, teremos dois tipos de variáveis de</p><p>decisão na modelagem deste problema.</p><p>xi = quantidade de bicicleta do modelo i a ser fabricada internamente;</p><p>ci = quantidade de bicicleta do modelo i a ser comprada de concorrente.</p><p>Logo, as variáveis de decisão para este exemplo são:</p><p>x1 = quantidade de bicicleta do modelo 1 a ser fabricada internamente;</p><p>x2 = quantidade de bicicletas do modelo 2 a ser fabricada internamente;</p><p>x3 = quantidade de bicicletas do modelo 3 a ser fabricada internamente;</p><p>c1 = quantidade de bicicletas do modelo 1 a ser comprada de concorrente;</p><p>c2 = quantidade de bicicletas do modelo 2 a ser comprada de concorrente;</p><p>c3 = quantidade de bicicletas do modelo 3 a ser comprada de concorrente.</p><p>Conhecendo os custos de produção e de aquisição dos diferentes modelos de bicicletas, temos a seguinte</p><p>função objetivo:</p><p>Min Z= 350x1+400x2+430x3+ 460c1+540c2+580c3</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Foram encomendadas 3.000 bicicletas do modelo 1, 2.000 do modelo 2 e 1.000 do modelo 3, de modo que</p><p>a restrição de demanda é representada pelas seguintes equações:</p><p>x1 + c1 = 3.000 } demanda para o modelo 1</p><p>x2 + c2 = 2.000 } demanda para o modelo 2</p><p>x3 + c3 = 1.000 } demanda para o modelo 3</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>A fábrica tem disponibilidade de 10.000 horas para montagem e 6.000 horas para pintura até a entrega da</p><p>encomenda. Essas restrições são:</p><p>2x1 + 1,5x2 + 3x3 ≤10.000 } montagem</p><p>1x1 + 2x2 + 1x3 ≤ 6.000 } pintura</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Além disso, há a condição de não negatividade das variáveis de decisão:</p><p>x1, x2, x3, c1, c2, c3 >= 0</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Enfim, temos que o modelo para este exemplo do problema de fazer x comprar é:</p><p>Min Z= 350x1+400x2+430x3+ 460c1+540c2+580c3</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Sujeito a:</p><p>x1 + c1 = 3.000</p><p>x2 + c2 = 2.000</p><p>x3 + c3 = 1.000</p><p>2x1 + 1,5x2 + 3x3 ≤10.000</p><p>x1 + 2x2 + x3 ≤ 6.000</p><p>x1, x2, x3, c1, c2, c3 >= 0</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>É importante ressaltar que a decisão sobre a terceirização é um pouco simplificada, pois focam-se apenas</p><p>os aspectos econômicos. Contudo, a terceirização de determinados produtos ou serviços deve incluir outras</p><p>considerações além de questões econômicas, devendo, além disso, considerar aspectos estratégicos como</p><p>competências essenciais e vantagens competitivas. Ao delegar certos serviços a terceiros (outsourcing), a</p><p>empresa pode se concentrar em sua competência central, mantendo-se competitiva no mercado.</p><p>VERIFICANDO O APRENDIZADO</p><p>1. A FÁBRICA XYZ PRODUZ RAÇÕES PARA A ALIMENTAÇÃO DE GADO. AS</p><p>RAÇÕES SÃO ELABORADAS A PARTIR DA MISTURA DE TRÊS DIFERENTES TIPOS</p><p>DE GRÃOS: GRÃO 1, 2 E 3. TRÊS NUTRIENTES SÃO CONSIDERADOS NO</p><p>PRODUTO FINAL: O NUTRIENTE A, B E C.</p><p>SABE-SE QUE O GRÃO DO TIPO 1 CUSTA R$35,00 POR KG. UM QUILO DE GRÃO 1</p><p>POSSUI 30MG DE NUTRIENTE A, 10MG DE NUTRIENTE B E 43MG DE NUTRIENTE C.</p><p>O GRÃO DO TIPO 2 CUSTA R$23,00 POR KG. ALÉM DISSO, 1KG DO GRÃO 2</p><p>POSSUI 28MG DO NUTRIENTE A, 17MG DO NUTRIENTE B E 40MG DO NUTRIENTE</p><p>C. O GRÃO DO TIPO 3 POSSUI APENAS 70MG DO NUTRIENTE TIPO A, E 1KG</p><p>DESTE TIPO DE GRÃO CUSTA R$78,00.</p><p>A RAÇÃO PARA GADO DEVE CONTER, NO MÍNIMO, 1.250MG DE NUTRIENTE A,</p><p>380MG DO NUTRIENTE B E 980MG DO NUTRIENTE C.</p><p>O ANALISTA DESEJA DETERMINAR A COMPOSIÇÃO DA RAÇÃO QUE MINIMIZE OS</p><p>CUSTOS DE PRODUÇÃO, CONSIDERANDO QUE AS NECESSIDADES MÍNIMAS DOS</p><p>NUTRIENTES SEJAM ATENDIDAS. LOGO,</p><p>É POSSÍVEL AFIRMAR QUE:</p><p>A) As variáveis de decisão que devem ser usadas na modelagem são: xa a quantidade de nutrientes A, xb a</p><p>quantidade de nutrientes B e xc a quantidade de nutrientes C.</p><p>B) A função objetivo do modelo é Máx Z=30xa+28xb+70xc, sendo xa a quantidade de nutrientes A, xb a</p><p>quantidade de nutrientes B e xc a quantidade de nutrientes C.</p><p>C) O modelo possui apenas duas restrições que garantem o suprimento mínimo da quantidade de nutrientes.</p><p>D) As variáveis de decisão do modelo não precisam atender à condição de não negatividade.</p><p>E) A função objetivo do modelo é Min Z= 35x1+23x2+78x3, sendo x1 = quilos de grão tipo 1 usado na</p><p>produção de um quilo de ração, x2 = quilos de grão tipo 2 usado na produção de um quilo de ração, e x3 =</p><p>quilos de grão tipo 3 usado na produção de um quilo de ração.</p><p>2. UMA FÁBRICA DE ELETRODOMÉSTICOS ESTÁ PLANEJANDO SEUS NÍVEIS DE</p><p>ESTOQUE PARA AS PRÓXIMAS QUATRO SEMANAS. A LOJA TEM CAPACIDADE</p><p>MÁXIMA DE ESTOQUE DE 100 GELADEIRAS. OS DADOS COM RELAÇÃO À</p><p>PRODUÇÃO MÁXIMA SEMANAL, AO CUSTO UNITÁRIO DE PRODUÇÃO E À</p><p>DEMANDA SEMANAL SÃO APRESENTADOS NA TABELA A SEGUIR.</p><p>30X1+28X2+70X3≥1250</p><p>10X1+17X2≥380</p><p>43X1+40X3≥980</p><p>X1,X2,X3,X4≥0</p><p>ATENÇÃO! PARA VISUALIZAÇÃO COMPLETA DA EQUAÇÃO UTILIZE A</p><p>ROLAGEM HORIZONTAL</p><p>MÊS 1 2 3 4</p><p>CUSTO</p><p>UNITÁRIO DE</p><p>PRODUÇÃO (R$)</p><p>1.240,00 1.300,00 1.265,00 1.285,00</p><p>DEMANDA</p><p>(UNIDADES)</p><p>60 50 65 70</p><p>PRODUÇÃO</p><p>MÁXIMA</p><p>(UNIDADES)</p><p>100 100 100 100</p><p>ATENÇÃO! PARA VISUALIZAÇÃOCOMPLETA DA TABELA UTILIZE A ROLAGEM</p><p>HORIZONTAL</p><p>DADOS DE PRODUÇÃO DE GELADEIRAS. FONTE: RENATA ALBERGARIA DE</p><p>MELLO BANDEIRA</p><p>SABE-SE QUE O ESTOQUE INICIAL DO MÊS É DE 30 UNIDADES E QUE O CUSTO</p><p>DE ESTOQUE É EQUIVALENTE A 2% DO CUSTO UNITÁRIO DE PRODUÇÃO DA</p><p>SEMANA. AO DESENVOLVER O MODELO MATEMÁTICO PARA MINIMIZAR O CUSTO</p><p>TOTAL DA FÁBRICA NO PRÓXIMO MÊS, CONSIDERAMOS QUE AS VARIÁVEIS DE</p><p>DECISÃO DEVEM SER XI, SENDO X O NÚMERO DE UNIDADES DE GELADEIRAS A</p><p>SEREM PRODUZIDAS NA SEMANA “I”, E EI, SENDO E O INVENTÁRIO INICIAL DA</p><p>SEMANA “I”. ASSIM, A(S) RESTRIÇÃO(ÕES) REFERENTE(S) AO ESTOQUE NA</p><p>SEMANA 3 É(SÃO) REPRESENTADA(S) PELA(S) SEGUINTE(S) EQUAÇÃO(ÕES):</p><p>A) x3 + e3 - 65 < 100</p><p>B) e3 = e2 + x2 – 50</p><p>C) e4 = e3 + x3 – 65</p><p>D) x3 + e3 - 65 < 100 e e3 = e2 + x2 – 50</p><p>E) x3 + e3 - 65 < 100, e3 = e2 + x2 – 50 e e4 = e3 + x3 – 65</p><p>GABARITO</p><p>1. A fábrica XYZ produz rações para a alimentação de gado. As rações são elaboradas a partir da</p><p>mistura de três diferentes tipos de grãos: grão 1, 2 e 3. Três nutrientes são considerados no produto</p><p>final: o nutriente A, B e C.</p><p>Sabe-se que o grão do tipo 1 custa R$35,00 por kg. Um quilo de grão 1 possui 30mg de nutriente A,</p><p>10mg de nutriente B e 43mg de nutriente C. O grão do tipo 2 custa R$23,00 por kg. Além disso, 1kg do</p><p>grão 2 possui 28mg do nutriente A, 17mg do nutriente B e 40mg do nutriente C. O grão do tipo 3</p><p>possui apenas 70mg do nutriente tipo A, e 1kg deste tipo de grão custa R$78,00.</p><p>A ração para gado deve conter, no mínimo, 1.250mg de nutriente A, 380mg do nutriente B e 980mg do</p><p>nutriente C.</p><p>O analista deseja determinar a composição da ração que minimize os custos de produção,</p><p>considerando que as necessidades mínimas dos nutrientes sejam atendidas. Logo, é possível afirmar</p><p>que:</p><p>A alternativa "E " está correta.</p><p>Como as rações são elaboradas a partir de três diferentes tipos de grãos, temos que as variáveis de decisão</p><p>são:</p><p>x1 = quilos de grão tipo 1 usado na produção de um quilo de ração;</p><p>x2 = quilos de grão tipo 2 usado na produção de um quilo de ração;</p><p>x3 = quilos de grão tipo 3 usado na produção de um quilo de ração.</p><p>Como se deseja minimizar o custo de produção, conhecendo o custo do quilo de cada tipo de grão, temos a</p><p>seguinte função objetivo:</p><p>MIN Z= 35X1+23X2+78X3</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Logo, podemos afirmar que a resposta certa para o exercício é a alternativa E. Porém, vamos seguir na</p><p>construção do modelo matemático para este problema.</p><p>A ração deve conter, no mínimo, 1250mg de nutriente A, 380mg do nutriente B e 980mg do nutriente C.</p><p>Assim, teremos três restrições com relação à quantidade dos diferentes tipos de nutrientes. São elas:</p><p>30x1+28x2+70x3≥1250→Nutriente A</p><p>10x1+17x2≥380→Nutriente B</p><p>43x1+40x3≥980→Nutriente C</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Logo, temos que o modelo para este exercício é:</p><p>MIN Z= 35X1+23X2+78X3</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Sujeito a:</p><p>30x1+28x2+70x3≥1250</p><p>10x1+17x2≥380</p><p>43x1+40x3≥980</p><p>x1,x2,x3,x4≥0</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>2. Uma fábrica de eletrodomésticos está planejando seus níveis de estoque para as próximas quatro</p><p>semanas. A loja tem capacidade máxima de estoque de 100 geladeiras. Os dados com relação à</p><p>produção máxima semanal, ao custo unitário de produção e à demanda semanal são apresentados</p><p>na tabela a seguir.</p><p>30x1+28x2+70x3≥1250</p><p>10x1+17x2≥380</p><p>43x1+40x3≥980</p><p>x1,x2,x3,x4≥0</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Mês 1 2 3 4</p><p>Custo unitário de</p><p>produção (R$)</p><p>1.240,00 1.300,00 1.265,00 1.285,00</p><p>Demanda (unidades) 60 50 65 70</p><p>Produção máxima</p><p>(unidades)</p><p>100 100 100 100</p><p>Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal</p><p>Dados de produção de geladeiras. Fonte: Renata Albergaria de Mello Bandeira</p><p>Sabe-se que o estoque inicial do mês é de 30 unidades e que o custo de estoque é equivalente a 2%</p><p>do custo unitário de produção da semana. Ao desenvolver o modelo matemático para minimizar o</p><p>custo total da fábrica no próximo mês, consideramos que as variáveis de decisão devem ser xi,</p><p>sendo x o número de unidades de geladeiras a serem produzidas na semana “i”, e ei, sendo e o</p><p>inventário inicial da semana “i”. Assim, a(s) restrição(ões) referente(s) ao estoque na semana 3</p><p>é(são) representada(s) pela(s) seguinte(s) equação(ões):</p><p>A alternativa "E " está correta.</p><p>As variáveis de decisão são:</p><p>xi = número de unidades a produzir na semana i, i=1 a 4</p><p>ei = inventário inicial na semana i, i=1 a 4</p><p>Conhecendo o custo unitário de produção e o custo de estoque de cada mês, conseguimos determinar a</p><p>função objetivo para a minimização dos custos da fábrica, considerando o custo do estoque médio da</p><p>semana</p><p>Min Z= 1.240x1+1.300x2+1.265x3+1.285x4+24,8(e1+e2)/2+26(e2+e3)/2+25,3(e3+e4)/2+ 25,7(e4+e5)/2</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>(es = ) :</p><p>ei + ei+1</p><p>2</p><p>A produção de unidades de geladeira por semana deve ser, no mínimo, o suficiente para atender à</p><p>demanda, porém não pode superar a produção máxima semanal. Logo, temos as seguintes restrições com</p><p>relação aos níveis de produção:</p><p>60≤x1 ≤ 100 } semana 1</p><p>50 ≤ x2 ≤100 } semana 2</p><p>65 ≤ x3 ≤100 } semana 3</p><p>70 ≤ x4 ≤ 100 } semana 4</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Sabe-se também que a capacidade máxima de estoque na fábrica é de 100 geladeiras. Logo, o estoque final</p><p>em cada semana não pode ser superior a tal capacidade máxima, de modo que esta restrição será do tipo ≤.</p><p>Como o Estoque final = Estoque inicial + produção - unidades vendidas, temos:</p><p>x1 + e1 - 60 < 100 } semana 1</p><p>x2 + e2 - 50 < 100 } semana 2</p><p>x3 + e3 - 65 < 100 } semana 3</p><p>x4 + e4 - 70 < 100 } semana 4</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Ainda em relação ao estoque, é necessário o balanço do inventário, que é representado pelas seguintes</p><p>restrições:</p><p>e1 = 30</p><p>e2 = e1 + x1 – 60</p><p>e3 = e2 + x2 - 50</p><p>e4 = e3 + x3 - 65</p><p>e5 = e4 + x4 - 70</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Enfim, temos que o modelo para este exemplo do problema de planejamento da produção dinâmico é:</p><p>Min Z= 1.240x1+1.300x2+1.265x3+1.285x4+24,8(e1+e2)/2+26(e2+e3)/2+25,3(e3+e4)/2+ 25,7(e4+e5)/2</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Sujeito a:</p><p>60≤x1 ≤ 100 } semana 1</p><p>50 ≤ x2 ≤100 } semana 2</p><p>65 ≤ x3 ≤100 } semana</p><p>3</p><p>70 ≤ x4 ≤ 100 } semana 4</p><p>x1 + e1 - 60 < 100 } semana 1</p><p>x2 + e2 - 50 < 100 } semana 2</p><p>x3 + e3 - 65 < 100 } semana 3</p><p>x4 + e4 - 70 < 100 } semana 4</p><p>e1 = 30</p><p>e2 = e1 + x1 – 60</p><p>e3 = e2 + x2 - 50</p><p>e4 = e3 + x3 - 65</p><p>e5 = e4 + x4 - 70</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Logo, as equações que representam as restrições referentes ao estoque na semana 3 são:</p><p>x3 + e3 - 65 < 100 } semana 3</p><p>e3 = e2 + x2 - 50</p><p>e4 = e3 + x3 – 65</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>MÓDULO 2</p><p> Aplicar a técnica de modelagem nos problemas de transporte e transbordo</p><p>PROBLEMAS DE TRANSPORTE</p><p>O problema de transportes é a aplicação de programação linear mais frequente na logística.</p><p>Esse padrão de problema envolve decisões como o volume a ser transportado entre localidades, podendo</p><p>envolver ou não decisões referentes ao desenho da cadeia e também problemas de localização.</p><p>O problema de programação linear para o problema clássico de transportes consiste em definir o melhor</p><p>caminho (ou rota) para fazer com que determinada quantidade de produtos de um ponto de suprimento</p><p>chegue a um ponto de demanda. O objetivo pode ser minimizar as distâncias percorridas, o custo de</p><p>transporte ou até mesmo maximizar os níveis de serviço ou o lucro com vendas.</p><p>O problema de transporte é um modelo fluxo em grafo bipartido, de modo que não existem nós</p><p>intermediários de transbordo ou transição para fluxo, conforme ilustrado .</p><p>Imagem: Renata Albergaria de Mello Bandeira.</p><p> Rede do problema de transportes.</p><p> ATENÇÃO</p><p>Na rede de transportes, os nós representam os pontos de suprimento e de demanda, enquanto os arcos</p><p>representam a conexão entre os nós.</p><p>Conforme pode ser observado, no problema de transportes, há m pontos de suprimento, cada um com</p><p>capacidade de oferta máxima designada por Si, onde o índice i representa o ponto de suprimento em</p><p>questão (i = 1,…, m). Existem ainda n pontos de demanda a serem abastecidos por estes pontos de</p><p>suprimento. Cada ponto de demanda recebe pelo menos Dj unidades do produto a ser transportado, sendo</p><p>que o índice j representa os pontos de demanda, tal que j = 1, …, n. Para cada unidade do ponto de</p><p>fornecimento i remetida ao ponto de demanda j incorre um custo cij, que é o custo de fornecer o produto ao</p><p>ponto de demanda j a partir do ponto de suprimento i.</p><p>Assim sendo, para modelar o problema de transportes, consideramos a variável de decisão xij, que</p><p>representa o número de unidades do produto específico despachadas do ponto de suprimento i para o ponto</p><p>de demanda j. Considerando que a função objetivo seja minimizar o custo total de transporte, temos que a</p><p>função objetivo é:</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>As condições de transporte estão sujeitas a restrições de fornecimento e de demanda. Logo, o total</p><p>transportado para o ponto de demanda tem que, ao menos, atender à quantidade mínima demandada,</p><p>enquanto o total transportado a partir do ponto de suprimento não pode ser superior à sua capacidade de</p><p>oferta. Logo, as restrições para o problema clássico de transportes podem ser representadas pelas</p><p>seguintes equações:</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Em suma, o modelo matemático para o problema clássico de transporte é:</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Sujeito a:</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Para facilitar o entendimento do modelo matemático para o problema clássico de transportes, vamos</p><p>resolver o exemplo a seguir:</p><p>TEORIA NA PRÁTICA</p><p>Min</p><p>m</p><p>∑</p><p>i=1</p><p>n</p><p>∑</p><p>j=1</p><p>cijxij</p><p>n</p><p>∑</p><p>j=1</p><p>xij ≤ si  (i = 1,   … ,  m)</p><p>mn</p><p>∑</p><p>i=1</p><p>xij ≥ dj  (j = 1,   … ,  n)</p><p>Min</p><p>m</p><p>∑</p><p>i=1</p><p>n</p><p>∑</p><p>j=1</p><p>cijxij</p><p>n</p><p>∑</p><p>j=1</p><p>xij ≤ si  (i = 1,   … ,  m)</p><p>m</p><p>∑</p><p>i=1</p><p>xij ≥ dj  (j = 1,   … ,  n)</p><p>xij ≥ 0 ∀i, j</p><p>PROBLEMA DE TRANSPORTE</p><p>Uma empresa fabricante de bicicletas conta com duas plantas, uma localizada em São Paulo e outra em</p><p>Recife. A empresa atende ao público por meio de três revendedores, localizados em Porto Alegre, Brasília e</p><p>Manaus.</p><p>Imagem: Renata Albergaria de Mello Bandeira</p><p> Rede do problema de transportes.</p><p>Plantas</p><p>Custos de envio por unidade</p><p>OfertasMercados</p><p>Porto Alegre Brasília Manaus</p><p>SP 25 30 70 600</p><p>Recife 60 35 50 700</p><p>Demandas 450 500 300</p><p>Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal</p><p>Distâncias para a rede do problema de transportes.</p><p>Fonte: Renata Albergaria de Mello Bandeira</p><p>Formule o problema de programação linear que minimize os custos de distribuição da empresa.</p><p>RESOLUÇÃO</p><p>Consideramos que i=1 para São Paulo e i=2 para Recife, enquanto j=1 para Porto Alegre, j=2 para Brasília</p><p>e j=3 para Manaus. Logo, as variáveis de decisão são:</p><p>x11= quantidade de produtos transportados de São Paulo para Porto Alegre;</p><p>x12= quantidade de produtos transportados de São Paulo para Brasília;</p><p>x13= quantidade de produtos transportados de São Paulo para Manaus;</p><p>x21= quantidade de produtos transportados de Recife para Porto Alegre;</p><p>x22= quantidade de produtos transportados de Recife para Brasília;</p><p>x23= quantidade de produtos transportados de Recife para Manaus.</p><p>A função objetivo para minimizar o custo total de transporte é:</p><p>Minz Z=25X11+30X12+70X13+60X21+35X22+50X23</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>O total transportado para Porto Alegre tem que ser, ao menos, igual a 450, para atender à demanda</p><p>mínima da cidade. Para Brasília e Manaus, devem ser transportadas, no mínimo, 500 e 300 bicicletas,</p><p>respectivamente. Assim, as restrições referentes à demanda são:</p><p>X11+X21 ≥450 à restrição quanto → demanda para Porto Alegre;</p><p>X12+X22 ≥500à restrição quanto → demanda para Brasília;</p><p>X13+X23 ≥300à restrição quanto → demanda para Manaus.</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>O total transportado de São Paulo não pode ser superior a 600 unidades, pois trata-se da capacidade</p><p>máxima de oferta da planta. Já o total transportado de Recife deve ser inferior a 700 unidades, que é a</p><p>capacidade máxima de oferta desta planta. Assim, as restrições referentes à oferta são:</p><p>X11+X12+X13+≤600à restrição quanto ao suprimento de São Paulo;</p><p>X21+X22+X23≤700à restrição quanto ao suprimento de Recife.</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>O modelo matemático deste problema é:</p><p>Minz Z=25X11+30X12+70X13+60X21+35X22+50X23</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Sujeito a:</p><p>X11+X21 ≥450</p><p>X12+X22 ≥500</p><p>X13+X23 ≥300</p><p>X11+X12+X13≤600</p><p>X21+X22+X23≤700</p><p>X11, X12, X13, X21, X22, X23≥0</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p> SAIBA MAIS</p><p>Os problemas de transporte são casos particulares de problemas de programação linear, de modo que sua</p><p>resolução algébrica pode ser desenvolvida por algoritmos de programação linear. Entretanto, é possível</p><p>aproveitar as particularidades do problema de transporte para resolvê-lo de forma mais eficiente que o caso</p><p>geral do simplex. Assim, existem algoritmos específicos para a solução do problema de transporte, como o</p><p>Método do Canto Noroeste e o Método de Vogel, porém não vamos abordá-los aqui. Caso você tenha</p><p>interesse em aprofundar os seus conhecimentos, recomenda-se a leitura do capítulo 7 de Winston (2004).</p><p>PROBLEMA DE TRANSBORDO</p><p>O problema de transbordo segue lógica semelhante ao problema de transportes, porém este não é um</p><p>modelo fluxo em grafo bipartido, pois existem nós intermediários de transbordo ou de transição para</p><p>fluxo, conforme ilustrado na figura a seguir:</p><p>Imagem: Renata Albergaria de Mello Bandeira</p><p> Rede do problema de transbordo.</p><p>Além de um conjunto de m nós, que representam os pontos de suprimentos, e n nós, que representam os</p><p>pontos de demanda, a rede também dispõe de l pontos de transbordo.</p><p>É importante que você saiba bem a diferença entre estes diferentes tipos</p><p>de nó:</p><p>PONTOS DE SUPRIMENTO</p><p>São responsáveis pelo fornecimento de insumos, de modo que podem remetê-los para outros pontos, porém</p><p>não podem recebê-los.</p><p>PONTOS DE DEMANDA</p><p>São os pontos de consumo, de modo que devem receber insumos de outros pontos, porém não podem</p><p>recebê-los.</p><p>PONTOS DE TRANSBORDO</p><p>Podem tanto receber insumos de outros pontos quanto remeter insumos para outros pontos, ou seja, são</p><p>locais onde é possível realizar a transferência da carga. Um centro de distribuição, por exemplo, pode</p><p>funcionar como um ponto de transbordo em uma cadeia logística, recebendo insumos de diversas plantas ou</p><p>diversos fornecedores, realizando a consolidação da carga e remetendo insumos para outras plantas, outros</p><p>centros de distribuição ou clientes. Um depósito também é um bom exemplo de um ponto de transbordo.</p><p>Uma particularidade do problema de transbordo é que aquilo que é transportado das unidades intermediárias</p><p>(de transbordo) aos mercados consumidores não deve ultrapassar a quantidade de produto que chega a tais</p><p>pontos.</p><p>A quantidade que insumos que chega a um ponto de transbordo deve ser igual à quantidade de insumos que</p><p>sai dele.</p><p>Com essa restrição, garantimos o equilíbrio do fluxo neste nó, ou seja, o fluxo que entra deve ser igual a</p><p>todo o fluxo que sai. Portanto, o modelo matemático para o problema de transbordo é semelhante ao do</p><p>problema clássico de transporte, porém acrescenta-se a restrição de equilíbrio nos nós que representam</p><p>pontos de transbordo.</p><p>Temos que o modelo matemático para o problema de transbordo é:</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Sujeito a:</p><p>Min</p><p>m</p><p>∑</p><p>i=1</p><p>n</p><p>∑</p><p>j=1</p><p>cijxij</p><p>n</p><p>∑</p><p>j=1</p><p>xij ≤ si  (i = 1,   … ,  m)</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Para facilitar o entendimento do modelo matemático para o problema clássico de transbordo, vamos resolver</p><p>o exemplo a seguir:</p><p>TEORIA NA PRÁTICA</p><p>PROBLEMA DE TRANSBORDO</p><p>Uma empresa fabricante de bicicletas conta com duas plantas, uma localizada em São Paulo e outra em</p><p>Recife, e atende o público por meio de dois revendedores, localizados em Porto Alegre e Manaus. A</p><p>empresa também dispõe de um centro de distribuição, localizado em Brasília, que pode ser usado como</p><p>ponto de transbordo caso contribua para reduzir o custo total de transporte.</p><p>Imagem: Renata Albergaria de Mello Bandeira</p><p> Rede do problema de transbordo.</p><p>Plantas/CD Custos de envio por unidade Ofertas</p><p>Mercados/CD</p><p>m</p><p>∑</p><p>i=1</p><p>xij ≥ dj  (j = 1,   … ,  n)</p><p>m</p><p>∑</p><p>i=1</p><p>xik =</p><p>n</p><p>∑</p><p>j=1</p><p>xkj  (k = 1,   … ,  l) →Equilíbrio nos nós de transbordo T</p><p>xij ≥ 0 ∀i, j</p><p>Porto Alegre Manaus Brasília</p><p>SP 25 70 30 600</p><p>Recife 60 50 35 700</p><p>Brasília 45 65 0</p><p>Demandas 450 500</p><p>Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal</p><p>Demandas e custos de transporte por unidade.</p><p>Fonte: Renata Albergaria de Mello Bandeira</p><p>RESOLUÇÃO</p><p>Consideramos que i=1 para São Paulo, i=2 para Recife e i=3 para Brasília, enquanto j=1 para Porto Alegre,</p><p>j=2 para Manaus e j=3 para Brasília. Logo, as variáveis de decisão são:</p><p>x11= quantidade de produtos transportados de São Paulo para Porto Alegre;</p><p>x12= quantidade de produtos transportados de São Paulo para Manaus;</p><p>x13= quantidade de produtos transportados de São Paulo para Brasília;</p><p>x21= quantidade de produtos transportados de Recife para Porto Alegre;</p><p>x22= quantidade de produtos transportados de Recife para Manaus;</p><p>x23= quantidade de produtos transportados de Recife para Brasília;</p><p>x31= quantidade de produtos transportados de Brasília para Porto Alegre;</p><p>x32= quantidade de produtos transportados de Brasília para Manaus.</p><p>A função objetivo para minimizar o custo total de transporte é:</p><p>Min Z=25X11+70X12+30X13+60X21+50X22+35X23+45X31+65X32</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>O total transportado para Porto Alegre tem que ser, ao menos, igual a 450, para atender à demanda</p><p>mínima da cidade. Para Brasília e Manaus, devem ser transportadas, no mínimo, 500 e 300 bicicletas,</p><p>respectivamente. Assim, as restrições referentes à demanda são:</p><p>X11+X21 +X31≥450 → restrição quanto à demanda para Porto Alegre;</p><p>X12+X22 +X32≥500 → restrição quanto à demanda para Manaus.</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>O total transportado de São Paulo não pode ser superior a 600 unidades, pois esta é a capacidade máxima</p><p>de oferta da planta. Já o total transportado de Recife deve ser inferior a 700 unidades, que é a capacidade</p><p>máxima de oferta desta planta. Assim, as restrições referentes à oferta são:</p><p>X11+X12+X13+≤600 → restrição quanto ao suprimento de São Paulo;</p><p>X21+X22+X23≤700 → restrição quanto ao suprimento de Recife.</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Lembre-se ainda da restrição de equilíbrio nos nós que representam pontos de transbordo. Tudo o que</p><p>chega no centro de distribuição de Brasília deve ser igual ao que sai de Brasília, conforme indicado na</p><p>equação a seguir:</p><p>X11+ X23+=X31+X32</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>O modelo matemático deste problema é:</p><p>Min Z=25X11+70X12+30X13+60X21+50X22+35X23+45X31+65X32</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Sujeito a:</p><p>X11+X21 +X31≥450</p><p>X12+X22 +X32≥500</p><p>X11+X12+X13+≤600</p><p>X21+X22+X23≤700</p><p>X11+ X23+=X31+X32</p><p>X11, X12 , X13, X21, X22, X23, X31,X32 ≥0</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>PROBLEMA DE TRANSPORTE E TRANSBORDO</p><p>A seguir, o especialista apresenta os problemas de transporte e de transbordo, abordando as</p><p>particularidades deste tipo de problema de programação linear e a importância de sua aplicação no ambiente</p><p>gerencial.</p><p>VERIFICANDO O APRENDIZADO</p><p>1. UMA FÁBRICA DE BEBIDAS TEM TRÊS DEPÓSITOS (O1, O2 E O3) NA CIDADE DO</p><p>RIO DE JANEIRO QUE SUPREM DUAS LOJAS (D1 E D2). AS DISTÂNCIAS, BEM</p><p>COMO AS QUANTIDADES OFERTADAS DE CADA DEPÓSITO E A DEMANDA DE</p><p>CADA LOJA, SÃO APRESENTADAS NA TABELA A SEGUIR:</p><p>DEPÓSITOS</p><p>DISTÂNCIA</p><p>OFERTAS</p><p>MERCADOS</p><p>D1 D2</p><p>O1 15 35 60</p><p>O2 43 27 90</p><p>O3 6 38 200</p><p>DEMANDAS 150 200</p><p>ATENÇÃO! PARA VISUALIZAÇÃOCOMPLETA DA TABELA UTILIZE A ROLAGEM</p><p>HORIZONTAL</p><p>FONTE: RENATA ALBERGARIA DE MELLO BANDEIRA</p><p>A FÁBRICA DESEJA PLANEJAR SUA DISTRIBUIÇÃO DE MODO A MINIMIZAR A</p><p>DISTÂNCIA TOTAL DE TRANSPORTE. ASSIM, EM RELAÇÃO AO MODELO</p><p>MATEMÁTICO QUE REPRESENTA ESTE PROBLEMA, É POSSÍVEL AFIRMAR QUE:</p><p>A) Deve possuir três variáveis de decisão.</p><p>B) Possui três inequações que representam as restrições com relação à demanda a ser atendida.</p><p>C) Possui duas inequações que representam as restrições com relação à capacidade de suprimento.</p><p>D) As restrições quanto à demanda devem ser do tipo ≤.</p><p>E) As restrições quanto à capacidade de suprimento devem ser do tipo ≤.</p><p>2. UMA EMPRESA DE BEBIDAS TEM TRÊS FÁBRICAS (O1, O2 E O3) E UM CENTRO</p><p>DE DISTRIBUIÇÃO (C1) NA CIDADE DO RIO DE JANEIRO QUE SUPREM DUAS</p><p>LOJAS (D1 E D2). AS DISTÂNCIAS, BEM COMO AS QUANTIDADES OFERTADAS DE</p><p>CADA DEPÓSITO E A DEMANDA DE CADA LOJA, SÃO APRESENTADAS NA TABELA</p><p>A SEGUIR:</p><p>FÁBRICAS E</p><p>CENTRO DE</p><p>DISTRIBUIÇÃO</p><p>DISTÂNCIA</p><p>OFERTAS</p><p>MERCADOS E CENTRO DE</p><p>DISTRIBUIÇÃO</p><p>D1 D2 C1 60</p><p>01 15 35 11 90</p><p>02 43 27 21 200</p><p>03 6 38 15</p><p>C1 10 20 -</p><p>DEMANDAS 150 200</p><p>ATENÇÃO! PARA VISUALIZAÇÃOCOMPLETA DA TABELA UTILIZE A ROLAGEM</p><p>HORIZONTAL</p><p>FONTE: RENATA ALBERGARIA DE MELLO BANDEIRA</p><p>A FÁBRICA DESEJA PLANEJAR SUA DISTRIBUIÇÃO DE MODO A MINIMIZAR A</p><p>DISTÂNCIA TOTAL DE TRANSPORTE. PARA DESENVOLVER O MODELO</p><p>MATEMÁTICO QUE REPRESENTA ESTE PROBLEMA, CONSIDERAMOS A VARIÁVEL</p><p>DE DECISÃO XIJ, QUE REPRESENTA O NÚMERO DE UNIDADES DO PRODUTO</p><p>ESPECÍFICO DESPACHADAS DO PONTO DE SUPRIMENTO OU DO CENTRO DE</p><p>DISTRIBUIÇÃO I PARA O PONTO DE DEMANDA OU CENTRO DE DISTRIBUIÇÃO J.</p><p>ASSIM, É POSSÍVEL AFIRMAR QUE:</p><p>A) Deve possuir 3 variáveis de decisão.</p><p>B) Deve possuir 6 variáveis de decisão.</p><p>C) Deve possuir 8 variáveis de decisão.</p><p>D) Deve possuir</p><p>11 variáveis de decisão.</p><p>E) Deve possuir 12 variáveis de decisão.</p><p>GABARITO</p><p>1. Uma fábrica de bebidas tem três depósitos (O1, O2 e O3) na cidade do Rio de Janeiro que suprem</p><p>duas lojas (D1 e D2). As distâncias, bem como as quantidades ofertadas de cada depósito e a</p><p>demanda de cada loja, são apresentadas na tabela a seguir:</p><p>Depósitos</p><p>Distância</p><p>Ofertas</p><p>Mercados</p><p>D1 D2</p><p>O1 15 35 60</p><p>O2 43 27 90</p><p>O3 6 38 200</p><p>Demandas 150 200</p><p>Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal</p><p>Fonte: Renata Albergaria de Mello Bandeira</p><p>A fábrica deseja planejar sua distribuição de modo a minimizar a distância total de transporte. Assim,</p><p>em relação ao modelo matemático que representa este problema, é possível afirmar que:</p><p>A alternativa "E " está correta.</p><p>As variáveis de decisão a serem adotadas neste modelo matemático são:</p><p>X11= quantidade de produtos transportados de O1 para D1;</p><p>X12= quantidade de produtos transportados de O1 para D2;</p><p>X21= quantidade de produtos transportados de O2 para D1;</p><p>X22= quantidade de produtos transportados de O2 para D2;</p><p>X31= quantidade de produtos transportados de O3 para D1;</p><p>X32= quantidade de produtos transportados de O3 para D2.</p><p>Logo, o modelo matemático deste problema é:</p><p>Minz Z=15X11+35X12+43X21+27X22+6X31+38X32</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Sujeito a:</p><p>X11+X21 +X31 ≥150</p><p>X12+X22 +X321 ≥200</p><p>X21+X22 ≤90</p><p>X11+X12≤60 [As restrições de capacidade são do tipo ≤.]</p><p>X31+X32 ≤200</p><p>X11, X12, X21, X22, X31, X32≥0</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>2. Uma empresa de bebidas tem três fábricas (O1, O2 e O3) e um centro de distribuição (C1) na</p><p>cidade do Rio de Janeiro que suprem duas lojas (D1 e D2). As distâncias, bem como as quantidades</p><p>ofertadas de cada depósito e a demanda de cada loja, são apresentadas na tabela a seguir:</p><p>Fábricas e</p><p>Centro de</p><p>Distribuição</p><p>Distância</p><p>Ofertas</p><p>Mercados e Centro de Distribuição</p><p>D1 D2 C1 60</p><p>01 15 35 11 90</p><p>02 43 27 21 200</p><p>03 6 38 15</p><p>C1 10 20 -</p><p>Demandas 150 200</p><p>Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal</p><p>Fonte: Renata Albergaria de Mello Bandeira</p><p>A fábrica deseja planejar sua distribuição de modo a minimizar a distância total de transporte. Para</p><p>desenvolver o modelo matemático que representa este problema, consideramos a variável de</p><p>decisão xij, que representa o número de unidades do produto específico despachadas do ponto de</p><p>suprimento ou do centro de distribuição i para o ponto de demanda ou centro de distribuição j.</p><p>Assim, é possível afirmar que:</p><p>A alternativa "D " está correta.</p><p>As variáveis de decisão a serem adotadas neste modelo matemático são:</p><p>X11= quantidade de produtos transportados de O1 para D1;</p><p>X12= quantidade de produtos transportados de O1 para D2;</p><p>X13= quantidade de produtos transportados de O1 para C1;</p><p>X21= quantidade de produtos transportados de O2 para D1;</p><p>X22= quantidade de produtos transportados de O2 para D2;</p><p>X23= quantidade de produtos transportados de O2 para C1;</p><p>X31= quantidade de produtos transportados de O3 para D1;</p><p>X32= quantidade de produtos transportados de O3 para D2;</p><p>X33= quantidade de produtos transportados de O3 para C1;</p><p>X41= quantidade de produtos transportados de C1 para D1;</p><p>X42= quantidade de produtos transportados de C1 para D2.</p><p>Assim, temos 11 variáveis de decisão e a função objetivo para o modelo deste problema é:</p><p>Minz Z=15X11+35X12+11X13 +43X21+27X22+21X23+6X31+38X32+15X33+10X41+20X42</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>MÓDULO 3</p><p> Aplicar a técnica de modelagem em problemas de alocação</p><p>PROBLEMAS DE ALOCAÇÃO</p><p>No problema de alocação, também denominado problema de designação ou de matching, existem dois</p><p>conjuntos e devem ser formados pares entre os elementos destes dois conjuntos.</p><p>O problema consiste em determinar a formação destes pares, ou seja, a combinação destes elementos de</p><p>modo a minimizar o custo total de todas as alocações, respeitando as restrições existentes.</p><p> ATENÇÃO</p><p>O problema da alocação visa designar tarefas a designados, podendo ser pessoas, máquinas, veículos ou</p><p>até mesmo fábricas. Neste tipo de problema, há um custo associado para o designado desempenhar cada</p><p>tarefa. Assim, o objetivo final é determinar a combinação de alocações que minimiza o custo total.</p><p>Também pode ser considerado que cada designado i tem determinado interesse em efetuar cada tarefa j,</p><p>dado por pij. Logo, o objetivo é realizar a alocação de maneira que a soma dos interesses seja maximizada.</p><p> ATENÇÃO</p><p>Destaca-se que, no problema de alocação, o número de designados e de tarefas devem ser iguais. Assim,</p><p>temos n designados e n tarefas. Cada tarefa deve ser atribuída a apenas um designado, que também só</p><p>deve realizar uma única tarefa. Além disso, todas as tarefas devem ser executadas.</p><p>O problema da alocação pode ser considerado um caso especial do modelo de transportes, no qual cada</p><p>origem tem uma unidade disponível e cada destino requer também uma unidade. Assim, o problema de</p><p>alocação é um problema de transporte balanceado, no qual todas as demandas e capacidades são iguais a</p><p>1. Desse modo, o problema de alocação utiliza variáveis binárias. A variável binária, ou booleana, pode</p><p>assumir apenas dois valores, zero ou 1. No problema de alocação, a variável de decisão xij recebe o valor</p><p>igual a “1” se decidirmos que a tarefa “i” será alocada para o designado “j”, sendo “0” se decidirmos o</p><p>contrário. De tal forma, temos que o modelo matemático para o problema da alocação é:</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Sujeito a:</p><p>Xij ꞓ {0,1}, (i=1,...n; j=1,...,n)</p><p>Xij=1, se o designado i for alocado para realizar a tarefa j.</p><p>Xij=0, caso contrário.</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p> SAIBA MAIS</p><p>Os modelos de alocação podem ser adotados para auxiliar no processo de tomada de decisão em diversas</p><p>situações reais, tal como na determinação da escala de vendedores para pontos de venda, na distribuição</p><p>de atividades para membros de uma equipe ou na alocação de máquinas para resolver diferentes tarefas.</p><p>Para facilitar o entendimento do modelo matemático para o problema clássico de alocação, vamos resolver o</p><p>exemplo a seguir:</p><p>MinZ =∑</p><p>i</p><p>∑</p><p>j</p><p>cijxij</p><p>∑</p><p>j</p><p>xij = 1  (i = 1,   … ,  n) →cada designado é alocado a uma só tarefa.</p><p>∑</p><p>i</p><p>xij = 1  (j = 1,   … ,  n) →cada tarefa é alocada a apenas um trabalhador.</p><p>TEORIA NA PRÁTICA</p><p>A supervisora de uma equipe de limpeza em um hotel necessita formar equipes de camareiras para realizar</p><p>a limpeza dos quartos na hora de troca de hóspedes. Os hóspedes que estão realizando check-out precisam</p><p>sair do quarto até às 12h, enquanto os novos hóspedes podem realizar o check-in a partir de 14h. Assim, as</p><p>esquipes têm pouco tempo para organizar e limpar todos os cômodos. Logo, a supervisora precisa organizar</p><p>as equipes de modo que os serviços sejam realizados o mais rápido possível.</p><p>A supervisora precisa formar a equipe para cuidar dos quartos do terceiro andar do hotel. As tarefas a serem</p><p>realizadas são: arrumar as camas, limpar o banheiro, varrer o quarto e tirar o pó. As camareiras</p><p>desempenham as tarefas, por quarto, nos seguintes tempos:</p><p>Camareira</p><p>Tarefa</p><p>Arrumar cama</p><p>Limpar</p><p>banheiro</p><p>Varrer quarto Tirar o pó</p><p>Lara 2 min 5 min 7 min 3 min</p><p>Ana 3 min 6 min 8 min 4 min</p><p>Julia 4 min 4 min 6 min 5 min</p><p>Talita 2 min 5 min 7 min 2 min</p><p>Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal</p><p>Tempo para execução das tarefas</p><p>Fonte: Renata Albergaria de Mello Bandeira</p><p>Formule o problema de programação linear que minimize o tempo de arrumação do quarto.</p><p>RESOLUÇÃO</p><p>Neste problema de alocação, a variável de decisão xij recebe o valor igual a “1” se decidirmos que a tarefa</p><p>“i” será alocada para o designado “j”, sendo “0” se decidirmos o contrário. De tal forma, temos:</p><p>x11= 1, se Lara arruma a cama; zero,</p><p>caso contrário;</p><p>x12= 1, se Lara limpa banheiro; zero, caso contrário;</p><p>x13 =1, se Lara varre o quarto; zero, caso contrário;</p><p>x14=1, se Lara tira o pó; zero, caso contrário;</p><p>x21= 1, se Ana arruma a cama; zero, caso contrário;</p><p>x22= 1, se Ana limpa banheiro; zero, caso contrário;</p><p>x23= 1, se Ana varre o quarto; zero, caso contrário;</p><p>x24= 1, se Ana tira o pó; zero, caso contrário;</p><p>x31= 1, se Julia arruma a cama; zero, caso contrário;</p><p>x32= 1, se Julia limpa banheiro; zero, caso contrário;</p><p>x33= 1, se Julia varre o quarto; zero, caso contrário;</p><p>x34= 1, se Julia tira o pó; zero, caso contrário;</p><p>x41= 1, se Talita arruma a cama; zero, caso contrário;</p><p>x42= 1, se Talita limpa banheiro; zero, caso contrário;</p><p>x43= 1, se Talita varre o quarto; zero, caso contrário;</p><p>x44= 1, se Talita tira o pó; zero, caso contrário.</p><p>O modelo matemático para o problema da alocação é:</p><p>Min Z= 2X11+5X12+7X13+3X14+3X21+6X22+8X23+4X24+4X31+4X32+6X33+5X34+2X41+5X42+7X43+2X44</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Sujeito a:</p><p>X11+X12+X13+X14=1</p><p>X21+X22+X23+X24=1</p><p>X31+X32+X33+X34=1 Cada trabalhador desempenha apenas uma tarefa.</p><p>X41+X42+X43+X44=1</p><p>X11+X21+X31+X41=1</p><p>X13+X23+X33+X43=1</p><p>X12+X22+X32+X42=1 Cada tarefa é alocada para apenas um trabalhador.</p><p>X14+X24+X34+X44=1</p><p>X11, X12, X13, X14, X21, X22, X23, X24, X31, X32, X33, X34, X41, X42, X43, X44 ꞓ {0,1}</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p> SAIBA MAIS</p><p>Assim como o problema de transportes, o problema da alocação também é um caso particular de problemas</p><p>de programação linear, de modo que sua resolução algébrica pode ser desenvolvida por algoritmos de</p><p>programação linear. Porém, tal como o problema de transportes, possui particularidades específicas que</p><p>podem ser aproveitadas para resolvê-lo de forma mais eficiente. Assim como para a solução do problema de</p><p>transporte, com o Método do Canto Noroeste e o Método de Vogel, também existem algoritmos específicos</p><p>para a solução do problema de alocação, a exemplo do algoritmo húngaro. Porém, não vamos abordá-los</p><p>aqui. Caso você tenha interesse em aprofundar os seus conhecimentos, recomenda-se a leitura do capítulo</p><p>7 de Winston (2004).</p><p>EXEMPLO DE PROBLEMA DE ALOCAÇÃO</p><p>No vídeo a seguir, o especialista apresenta um problema de alocação e desenvolve a resolução</p><p>detalhadamente, até a obtenção do resultado final.</p><p>VERIFICANDO O APRENDIZADO</p><p>1. UM TREINADOR NECESSITA FORMAR UM TIME DE NADADORES PARA</p><p>COMPETIR EM UMA PROVA OLÍMPICA DE 400 METROS MEDLEY. OS NADADORES</p><p>APRESENTAM AS SEGUINTES MÉDIAS DE TEMPO EM CADA ESTILO:</p><p>NADADOR</p><p>TEMPO (S) / 100M</p><p>LIVRE PEITO GOLFINHO COSTAS</p><p>1 54 54 51 53</p><p>2 51 57 52 52</p><p>3 50 53 54 56</p><p>4 56 54 55 53</p><p>ATENÇÃO! PARA VISUALIZAÇÃOCOMPLETA DA TABELA UTILIZE A ROLAGEM</p><p>HORIZONTAL</p><p>FONTE: RENATA ALBERGARIA DE MELLO BANDEIRA</p><p>O TREINADOR DESEJA DESIGNAR OS NADADORES PARA OS DIFERENTES</p><p>ESTILOS, A FIM DE OBTER O MENOR TEMPO POSSÍVEL PARA COMPLETAR O</p><p>MEDLEY. SOBRE O MODELO MATEMÁTICO QUE REPRESENTA ESTE PROBLEMA,</p><p>É POSSÍVEL AFIRMAR QUE:</p><p>A) As variáveis de decisão que devem ser usadas na modelagem são: x1 que representa o nadador alocado</p><p>ao nado livre, x2 que representa o nadador designado para o peito, x3 que representa o nadador alocado</p><p>para o golfinho, e x4 que indica o nadador alocado para o estilo de costas.</p><p>B) As variáveis de decisão que devem ser usadas na modelagem são: x1 que representa o estilo designado</p><p>para o nadador 1, x2 que representa o estilo designado para o nadador 2, x3 que representa estilo designado</p><p>para o nadador 3, e x4 que indica o estilo alocado para o nadador 4.</p><p>C) As variáveis de decisão usadas no modelo devem ser inteiras, porém não precisam ser binárias.</p><p>D) O modelo matemático possui 16 variáveis de decisão, que são variáveis binárias.</p><p>E) Não é possível tratar este problema como um problema de alocação, pois o número de tarefas (estilos) a</p><p>serem alocadas é igual ao número de designados (nadadores).</p><p>2. UM TREINADOR NECESSITA FORMAR UM TIME DE NADADORES PARA</p><p>COMPETIR EM UMA PROVA OLÍMPICA DE 400 METROS MEDLEY. OS NADADORES</p><p>APRESENTAM AS SEGUINTES MÉDIAS DE TEMPO EM CADA ESTILO:</p><p>NADADOR</p><p>TEMPO (S) / 100M</p><p>LIVRE PEITO GOLFINHO COSTAS</p><p>1 54 54 51 53</p><p>2 51 57 52 52</p><p>3 50 53 54 56</p><p>4 56 54 55 53</p><p>ATENÇÃO! PARA VISUALIZAÇÃOCOMPLETA DA TABELA UTILIZE A ROLAGEM</p><p>HORIZONTAL</p><p>O TREINADOR DESEJA DESIGNAR OS NADADORES PARA OS DIFERENTES</p><p>ESTILOS, A FIM DE OBTER O MENOR TEMPO POSSÍVEL PARA COMPLETAR O</p><p>MEDLEY. CONSIDERE QUE A VARIÁVEL DE DECISÃO DO MODELO MATEMÁTICO</p><p>PARA ESTE PROBLEMA SEJA XIJ, QUE RECEBE O VALOR IGUAL A “1” SE</p><p>DECIDIRMOS QUE O ESTILO “I” SERÁ ALOCADO AO DESIGNADO “J”, SENDO “0”</p><p>SE DECIDIRMOS O CONTRÁRIO. LOGO, É POSSÍVEL AFIRMAR QUE:</p><p>A) A equação X11+X12+X13+X14=1 restringe que o estilo 1 será desempenhado por apenas um nadador.</p><p>B) A equação X11+X12+X13+X14=1 restringe que o nadador 1 desempenha apenas um estilo.</p><p>C) A equação X11+X12+X13+X14=1 restringe que o estilo 1 pode ser desempenhado por todos os nadadores.</p><p>D) A equação X11+X21+X31+X41=1 restringe que o nadador 1 pode desempenhar todos os estilos.</p><p>E) A equação X11+X21+X31+X41=1 não é uma restrição do modelo.</p><p>GABARITO</p><p>1. Um treinador necessita formar um time de nadadores para competir em uma prova olímpica de 400</p><p>metros medley. Os nadadores apresentam as seguintes médias de tempo em cada estilo:</p><p>Nadador Tempo (s) / 100m</p><p>Livre Peito Golfinho Costas</p><p>1 54 54 51 53</p><p>2 51 57 52 52</p><p>3 50 53 54 56</p><p>4 56 54 55 53</p><p>Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal</p><p>Fonte: Renata Albergaria de Mello Bandeira</p><p>O treinador deseja designar os nadadores para os diferentes estilos, a fim de obter o menor tempo</p><p>possível para completar o medley. Sobre o modelo matemático que representa este problema, é</p><p>possível afirmar que:</p><p>A alternativa "D " está correta.</p><p>Neste problema de alocação, a variável de decisão xij recebe valor igual a “1” se decidirmos que o estilo “i”</p><p>será alocado ao designado “j”, sendo “0” se decidirmos o contrário. De tal forma, temos:</p><p>X11= 1, se o nado livre é alocado ao nadador 1; zero, caso contrário;</p><p>X12= 1, se o estilo de peito é alocado ao nadador 1; zero, caso contrário;</p><p>X13 =1, se o estilo de golfinho é alocado ao nadador 1; zero, caso contrário;</p><p>X14=1, se o estilo de costas é alocado ao nadador 1; zero, caso contrário;</p><p>X21= 1, se o nado livre é alocado ao nadador 2; zero, caso contrário;</p><p>X22= 1, se o estilo de peito é alocado ao nadador 2; zero, caso contrário;</p><p>X23= 1, se o estilo de golfinho é alocado ao nadador 2; zero, caso contrário;</p><p>X24= 1, se o estilo de costas é alocado ao nadador 2; zero, caso contrário;</p><p>X31= 1, se o nado livre é alocado ao nadador 3; zero, caso contrário;</p><p>X32= 1, se o estilo de peito é alocado ao nadador 3; zero, caso contrário;</p><p>.X33= 1, se o estilo de golfinho é alocado ao nadador 3; zero, caso contrário;</p><p>X34= 1, se o estilo de costas é alocado ao nadador 3; zero, caso contrário;</p><p>X41= 1, se o nado livre é alocado ao nadador 4; zero, caso contrário;</p><p>X42= 1, se o estilo de peito é alocado ao nadador 4; zero, caso contrário;</p><p>X43= 1, se o estilo de golfinho é alocado ao nadador 4; zero, caso contrário;</p><p>X44= 1, se o estilo de costas é alocado ao nadador 4; zero, caso contrário.</p><p>Logo, temos 16 variáveis de decisão binárias, o que faz com que a alternativa D seja a resposta correta.</p><p>O modelo matemático para este problema da alocação é:</p><p>Min Z=</p><p>54X11+54X12+51X13+53X14+51X21+57X22+52X23+52X24+50X31+53X32+54X33+56X34+56X41+54X42+55X43+53X44</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>Sujeito a:</p><p>X11+X12+X13+X14=1</p><p>X21+X22+X23+X24=1 Cada nadador desempenha apenas um estilo.</p><p>X31+X32+X33+X34=1</p><p>X41+X42+X43+X44=1</p><p>X11+X21+X31+X41=1</p><p>X13+X23+X33+X43=1 Cada estilo é alocado para apenas um nadador.</p><p>X12+X22+X32+X42=1</p><p>X14+X24+X34+X44=1</p><p>X11, X12, X13, X14, X21, X22, X23, X24, X31, X32, X33, X34, X41, X42, X43, X44 ꞓ {0,1}</p><p>Atenção! Para visualização completa da equação utilize a rolagem horizontal</p><p>2. Um treinador necessita formar um time de nadadores para competir em uma prova olímpica de 400</p><p>metros medley. Os nadadores apresentam as seguintes médias de tempo em cada estilo:</p><p>Nadador</p><p>Tempo (s) / 100m</p><p>Livre Peito Golfinho Costas</p><p>1 54 54 51 53</p><p>2 51 57 52 52</p><p>3 50 53 54 56</p><p>4 56 54 55 53</p><p>Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal</p><p>O treinador deseja designar os nadadores para os diferentes estilos, a fim de obter o menor tempo</p><p>possível para completar o medley. Considere que a variável de decisão do modelo matemático para</p><p>este problema seja xij, que recebe o valor igual a “1” se decidirmos que o estilo “i” será alocado ao</p><p>designado “j”, sendo “0” se decidirmos o contrário. Logo, é possível afirmar que:</p><p>A alternativa "B " está correta.</p><p>A equação X11+X12+X13+X14=1 restringe que o estilo 1 será desempenhado por apenas um nadador, pois</p><p>determina que apenas uma das variáveis X11, X12, X13 e X14 pode receber o valor 1. As demais passam a</p><p>ser zero, para que a soma seja igual a 1.</p><p>CONCLUSÃO</p><p>CONSIDERAÇÕES FINAIS</p><p>Vimos como a Pesquisa Operacional pode auxiliar no apoio a processos de decisão, em especial para</p><p>problemas complexos. Ao longo dos módulos, aprendemos sobre modelos matemáticos e como estes</p><p>podem nos ajudar na análise de decisão, em especial por permitirem avaliar a solução do problema em</p><p>diferentes cenários a um menor tempo e custo. Além disso, colocamos estes conceitos em prática à medida</p><p>que aprendemos a construir modelos matemáticos para problemas de programação linear.</p><p>Entretanto, é preciso ter em mente que a modelagem não é uma tarefa simples, principalmente para aqueles</p><p>que estão iniciando neste campo do conhecimento. Assim, para nos familiarizarmos com a técnica de</p><p>modelagem e podermos construir modelos com mais facilidade, é preciso praticar por meio de exercícios. A</p><p>prática é essencial para nos ajudar a entender e a dominar a lógica por trás da modelagem matemática.</p><p>Outro ponto que também facilita a internalização deste conhecimento é entender que alguns modelos,</p><p>conhecidos como problemas típicos, seguem padrões semelhantes. Portanto, se entendemos a lógica por</p><p>trás dessa “categoria” de problemas, conseguiremos modelar os demais problemas desta mesma classe.</p><p>Por isso, é importante conhecer esses padrões!</p><p>No módulo 1, apresentamos os problemas clássicos da mistura, do planejamento de produção e de</p><p>estoques, e fazer versus comprar. Dedicamos os módulos 2 e 3 para entender a lógica do problema de</p><p>transporte e de seus casos particulares. O destaque para o problema de transporte ocorre porque trata-se do</p><p>modelo de programação linear mais aplicado na área da logística. Abordamos, ainda, no módulo 2 o</p><p>problema de transbordo, enquanto no módulo 3 tratamos especificamente do problema de alocação.</p><p>Até o momento, aprendemos a solucionar os modelos matemáticos por meio da aplicação do Método</p><p>Gráfico. Contudo, tal método é restrito a problemas mais simples, com até duas variáveis de decisão.</p><p>AVALIAÇÃO DO TEMA:</p><p>REFERÊNCIAS</p><p>DiSERIO, L.; SAMPAIO, M. Projeto da cadeia de suprimento: uma visão dinâmica da decisão fazer versus</p><p>comprar. In: Revista de Administração de Empresas, v. 41, n. 1, p. 54-66, 2001.</p><p>GOLDBARG, M. C.; LUNA, H. P. Otimização combinatória e programação linear. 2. ed. São Paulo:</p><p>Campus, 2005.</p><p>LACHTERMACHER, G. Pesquisa operacional na tomada de decisões. Rio de Janeiro: LTC, 2016.</p><p>RAGSDALE, C. T. Modelagem e análise de decisão. São Paulo: Cengage Learning, 2009.</p><p>RODRIGUES, L. H.; AHLERT, F.; LACERDA, D. P.; CAMARGO, L. F. R.; LIMA, P. Pesquisa operacional:</p><p>programação linear passo a passo: do entendimento do problema à interpretação da solução. São Leopoldo:</p><p>Unisinos, .</p><p>SLACK, N.; CHAMBERS, S.; HARLAND, C.; HARRISON, A.; JOHNSTON, R. Administração da produção.</p><p>São Paulo: Atlas, 1997.</p><p>STIGER, G. J. The cost of Subsistence. Journal of Farm Economics 27(2), p. 303-314, 1945.</p><p>WINSTON, W. L.; GOLDBERG, J. B. Operations research: applications and algorithms. Vol. 3. Boston:</p><p>Cengage Learning, 2004.</p><p>EXPLORE+</p><p>Para obter mais conhecimento sobre os conteúdos discutidos, sugerimos a seguinte leitura:</p><p>WINSTON, W. L.; GOLDBERG, J. B. Operations research: applications and algorithms. Vol. 3.</p><p>Boston: Cengage Learning, 2004.</p><p>CONTEUDISTA</p><p>Renata Albergaria de Mello Bandeira</p><p> CURRÍCULO LATTES</p><p>javascript:void(0);</p><p>javascript:void(0);</p>