Baixe o app para aproveitar ainda mais
Prévia do material em texto
PESQUISA OPERACIONAL AULA 3 Prof. Ricardo Zanardini 2 CONVERSA INICIAL Olá! Estamos começando a nossa aula 3 de Pesquisa Operacional. Veremos o que são problemas de transporte e como faremos para obter as respostas desses tipos de problemas. Aprenderemos também o que é um problema de designação bem como uma forma de resolvê-lo. Vamos começar falando sobre os problemas de transporte, que são muito comuns em diversas áreas, principalmente na Logística e na Produção Industrial. TEMA 1 - PROBLEMAS DE TRANSPORTE Um problema de transporte consiste basicamente em determinar as quantidades a serem transportadas de uma ou mais origens para um ou mais destinos de modo que o custo total referente a esse problema seja o menor possível. Para podermos resolver um problema de transporte, inicialmente precisamos conhecer as capacidades de cada origem, as demandas de cada destino e os custos unitários de transporte de cada origem para cada destino. Se o problema a ser resolvido possuir apenas uma origem, não há dificuldades em obtermos a solução ótima do problema. Basta iniciarmos a resolução do problema enviando a quantidade necessária da origem para o destino cujo custo unitário de transporte é o menor. Em seguida, enviaremos o que for necessário para o segundo destino de menor custo e assim por diante. Ao final do processo, se a demanda total for igual à capacidade da origem, não haverá falta e nem sobra do material transportado. Se a capacidade da origem for maior do que a demanda, teremos uma quantidade excedente em estoque. Se a demanda for maior do que a capacidade de fornecimento da origem, teremos falta do material transportado. É importante ressaltar que um ou mais destinos de maior custo unitário de transporte deixarão de receber esses itens. 3 A figura a seguir exemplifica essa situação. Observe que a capacidade do depósito é de 1.200 unidades e que a demanda total referente às três lojas corresponde a 1.100 unidades. Nesse caso, como a oferta é maior do que a demanda, teremos um estoque de 100 unidades no depósito. Fazendo a distribuição dos produtos, a solução do problema é dada por: No caso de duas ou mais origens ou dois ou mais destinos, a solução do problema nem sempre é tão óbvia e nesses casos devemos recorres à pesquisa operacional para obtermos a solução ótima do problema. Um problema de transporte é um caso particular de um problema de programação linear que pode ser resolvido pelo método simplex ou por métodos específicos desenvolvidos para esses tipos de problemas, tais como o método de Vogel, método do canto noroeste ou o método do custo mínimo. 4 Para que possamos aprender a resolver problemas de transporte, vamos considerar como exemplo, uma indústria fictícia de automóveis com duas unidades localizadas em Curitiba e São Paulo. A unidade de Curitiba possui 20.000 automóveis e a unidade de São Paulo 25.000 automóveis a serem transportados para os portos de Santos, Paranaguá e Itajaí cujas demandas são, respectivamente, de 12.000, 16.000 e 8.000 veículos. Os custos unitários de transporte são apresentados na figura a seguir. Observe que o nosso objetivo é, sempre que possível, atender às demandas dos destinos, dentro das capacidades de cada origem, com o menor custo total de transporte. Nesse caso, a formulação do problema é dada por: 5 Observe que a função objetivo apresenta como coeficientes os custos unitários de transporte de cada origem para cada destino. As restrições garantem que as quantidades transportadas não ultrapassem as capacidades de cada origem e também respeitam as demandas de cada destino. O sinal de menor ou igual (<=) é usado, pois a capacidade de cada destino é igual ou inferior a 20.000 e 25.000, respectivamente, ou seja, as quantidades ofertadas não podem ser maiores do que 20.000 e 25.000. As restrições que se referem às demandas são de maior ou igual (>=) por que a demanda mínima de cada destino deve ser suprida. É claro que esse problema só terá solução se o sistema for equilibrado, ou seja, se a capacidade total for igual à demanda total. Caso a capacidade seja maior do que a demanda, haverá sobra em estoque. Para esse tipo de problema, devemos criar então um destino fictício. Mas o que é um destino fictício? É uma forma de representarmos matematicamente que haverá sobra em uma ou mais origens. Como essa quantidade excedente não será transportada, pois permanecerá em estoque, o custo de transporte de cada origem para o destino fictício é igual a zero. Podemos ter também uma demanda total maior do que a capacidade total das origens. Nesse caso haverá falta em um ou mais destinos. Matematicamente, a solução de um problema assim requer a criação de uma origem fictícia, também com custos de transporte nulos. A origem fictícia, além de possibilitar a resolução do problema, servirá também para indicar qual ou quais destinos não terão a demanda atendida. Após a criação de uma origem ou de um destino fictício, a formulação do problema de transporte pode ser feita novamente. Nesse caso, podemos, além de adicionar a origem ou destino fictício, substituir as desigualdades por igualdades, já que o sistema passa a estar em equilíbrio. No nosso exemplo, como a oferta 20.000+25.000=45.000 é maior do que a demanda que corresponde a 12.000+16.000+8.000=36.000, iremos criar um destino fictício cuja demanda corresponde a 45.000-36.000=9.000. Fazendo isso, a formulação fica assim: min z = 400x11 + 150x12 + 280x13 + 0x14 + 110x21 + 380x22 + 410x23 + 0x24 s.a. x11 + x12 + x13 + x14 = 20000 6 x21 + x22 + x23 + x24 = 25000 x11 + x21 = 12000 x12 + x22 = 16000 x13 + x23 = 8000 x14 + x24 = 9000 xij ≥ 0 onde xij é a quantidade de automóveis a serem transportados da fábrica i para o depósito j. Na prática, a quantidade a ser transportada para o destino fictício corresponde à quantidade que ficará no estoque. A solução de um problema de transporte pode ser obtida pelo método Simplex. No entanto, devido às particularidades dos problemas de transporte, temos métodos exclusivos destinados à solução desses problemas. O uso desses métodos minimiza os esforços necessários para a obtenção da solução ótima. Você pode notar que existem várias maneiras de resolvermos um problema de transporte. Aprenderemos a resolver esses problemas utilizando o método do custo mínimo e também o WinQSB. Acompanhe como é possível resolver um problema de transporte utilizando o método do custo mínimo. TEMA 2 - MÉTODO DO CUSTO MÍNIMO Vamos aprender a resolver um problema de transporte utilizando o método do custo mínimo. Como exemplo, vamos considerar a indústria fictícia de automóveis com duas unidades localizadas em Curitiba e São Paulo. Sabemos que a unidade de Curitiba possui 20.000 automóveis e a unidade de São Paulo 25.000 automóveis a serem transportados para os portos de Santos, Paranaguá e Itajaí cujas demandas são, respectivamente, de 12.000, 16.000 e 8.000 veículos e que os custos unitários de transporte são apresentados na figura a seguir. 7 O primeiro passo é construir uma tabela com as ofertas, demandas, custos unitários de transporte e também com um espaço para que possamos anotar as quantidades que serão transportadas. Para iniciarmos a solução do problema de transporte pelo método do custo mínimo, teremos que anotar o máximo que pode ser transportado na célula de menor custo. Havendo empate,a escolha é feita de forma aleatória. Nesse caso, iremos colocar 9.000 na célula (1,4) que corresponde à quantidade a ser transportada de Curitiba para o destino fictício. É importante reduzir o valor adicionado da coluna da capacidade e da linha da demanda para que as capacidades e as demandas estejam sempre de acordo com o que já está sendo transportado. 8 Iremos escolher agora a próxima célula de menor custo. Fazendo isso, deveremos adicionar 12.000 na célula (2,1). Em seguida, colocaremos 11.000 na célula (1,2). Observe que sempre iremos escolher a célula de menor custo. Agora devemos colocar 5.000 na célula (2,2). Finalmente basta adicionar 8.000 na célula (2,3). Observe que nessa solução inicial todas as demandas estão sendo atendidas e todas as capacidades foram utilizadas. A quantidade referente ao destino fictício corresponde ao estoque que na realidade não será enviado. 9 Os dados da solução inicial são os seguintes: A solução inicial é viável, mas por enquanto não sabemos se essa solução, de fato, possui o menor custo total para o envio dos automóveis das fábricas para os devidos portos. Para sabermos se a solução obtida é ótima, precisamos calcular os custos reduzidos denotados por dij. Para as variáveis básicas, isto é, as variáveis que fazem parte da solução, os custos reduzidos são iguais a zero. Para as variáveis não básicas, esses custos reduzidos são diferentes de zero. Caso algum custo reduzido referente a uma variável não básica seja negativo, temos que a solução atual não é ótima e que o custo total de transporte pode ser menor do que o atual. As variáveis ui e vj são conhecidas como variáveis duais. Essas variáveis serão utilizadas para o cálculo dos custos reduzidos. Vamos calcular os valores das variáveis duais. Como ainda não temos o valor dessas variáveis, inicialmente iremos atribuir o valor zero para a variável u1. Com isso é possível encontrar o valor de v2. Tendo o valor de u1, é possível também encontrarmos o valor de v4. 10 Com o valor de v2, podemos calcular o valor de u2. Seguindo essa ideia, é possível agora encontrarmos o valor de v1. Finalmente, com o valor de u2, podemos encontrar o valor de v3. Para sabermos, então, se a solução é ótima, iremos agora calcular os valores dos custos reduzidos referentes às variáveis não básicas. O que fazer então? 11 O valor negativo referente à variável não básica x24 indica que se essa variável entrar na base, ou seja, se transportarmos tantos veículos quanto forem possíveis de São Paulo para o depósito fictício, teremos uma redução no custo total de transporte. Apenas ressaltando, transportar veículos para o depósito fictício, na prática, significa que esses veículos ficarão no estoque. Uma maneira bem simples de alterarmos as quantidades a serem transportadas, sempre respeitando a capacidade de cada depósito e a demanda de cada destino, é traçarmos um caminho onde os vértices são formados por variáveis básicas. Como o nosso objetivo é colocar a variável x24 na base, isto é, transportar o máximo possível de São Paulo para o destino fictício, precisamos, primeiramente, saber qual é o valor máximo a ser transportado. Para isso, vamos verificar quais são os valores pertencentes aos vértices do caminho e, depois disso, vamos escolher o menor deles. Os valores que pertencem aos vértices do caminho são: 5.000, 11.000 e 9.000. Como o menor deles é igual a 5.000, vamos colocar 5.000 na célula (2,4). Para continuarmos atendendo às demandas e as capacidades, termos que somar e subtrair 5.000 dos vértices, alternadamente. Vamos ver como isso pode ser feito. 12 Note que adicionamos 5.000 na célula (2,4) e subtraímos 5.000 da célula (2,2). Em seguida, somamos 5.000 na célula (1,2) e, finalmente, subtraímos 5.000 da célula (1,4). Fazendo isso, as capacidades e demandas continuam sendo atendidas e a variável x24 entrou na base, fazendo com que a variável x22 saísse da base. Com essas alterações, a nossa tabela ficou assim: É importante ressaltar que a mudança implicou em uma redução no custo total de transporte. No entanto, ainda não sabemos se essa nova solução é a solução ótima ou se ainda podemos obter uma solução de menor custo. Para verificarmos se a solução ainda pode ser melhorada, vamos calcular os custos reduzidos. Para isso precisamos, primeiro, dos valores das variáveis duais u e v. 13 Agora que já calculamos os valores das variáveis duais, vamos calcular os custos reduzidos para cada variável não básica. Nesse caso, a variável x13 deverá entrar na base. Vamos fazer o caminho para determinarmos qual variável deixará de ser básica. 14 Observe que o menor valor das células que forma o caminho é 4.000. Logo, iremos somar e subtrair, alternadamente, esse valor, no caminho escolhido. As novas quantidades a serem transportadas de cada origem para cada destino são: É possível perceber que houve, mais uma vez, uma redução do custo total de transporte conforme o esperado. Mas ainda não sabemos se essa solução é a solução ótima ou ainda não. Novamente teremos que obter os valores dos custos reduzidos referentes às variáveis não básicas e, para isso, teremos que calcular os valores das variáveis duais como já fizemos anteriormente. 15 Agora que já temos os valores das variáveis duais, vamos calcular os custos reduzidos. 16 Após estudar o texto do PDF, aproveite o momento para ler o capítulo 5 da obra Iniciação à Pesquisa Operacional no Ambiente de Gestão, 2. ed., dos professores Marcos Antônio Barbosa e Ricardo A. D. Zanardini, da editora Intersaberes, em que poderemos aprender um pouco mais sobre problemas de transporte e sobre o método do custo mínimo. TEMA 3 - RESOLUÇÃO DE PROBLEMAS COM O WINQSB Uma outra alternativa para a resolução de problemas de transporte é o uso de algum software de Pesquisa Operacional. Veja como é possível resolver um problema de transporte utilizando o WinQSB. Resolução de Problemas de Transporte Utilizando o WinQSB Uma alternativa para obtermos a solução de um problema de transporte é a utilização de um software. Há vários programas gratuitos ou pagos: LINGO, LINDO, Pesquisa Operacional, WinQSB... 17 Mostraremos a seguir como utilizar o software WinQSB para resolvermos problemas de transporte. Após a instalação, basta clicar no menu Iniciar. Em seguida, Clicar em WinQSB, Network Modeling. Aparecerá uma tela indicando que a rotina Network Modeling está sendo inicializada. 18 O próximo passo é clicar em File, Nem Problem. A tela inicial apresenta diversas opções de problemas. Deveremos selecionar a opção Transportation Problem. Em seguida preencher o campo Number os Sources, número de origens, com o número 2 e o campo Number of Destinations, número de destinos, com o número 3. O critério da função objetivo é Minimization, pois o objetivo é minimizar o custo total de transporte. 19 Clicando em OK, o WinQSB abrirá uma tela com uma tabela para que possamos colocar as informações pertinentes ao problema: capacidade de cada origem (Supply), demanda de cada destino (Demand) e os custos unitários de cada origem para cada destino. Mas antes de colocarmos essas informações, é importante efetuarmos a troca dos nomesdas origens e dos destinos para facilitar o preenchimento da tabela e a interpretação da solução do problema. 20 Como faremos para trocar os nomes das origens e dos destinos? É bem simples. Basta clicar em Edit, Node Names. Depois é só alterar os nomes da seguinte maneira: no lugar de Source 1 e Source 2 é só digitar Curitiba e São Paulo e no lugar de Destination 1, Destination 2 e Destination 3 basta digitar Santos, Paranaguá e Itajaí. 21 Fazendo isso, teremos a tabela pronta para que os dados do problema sejam informados. Preenchendo a tabela com os custos unitários, demandas e ofertas, teremos a seguinte tabela. E, finalmente, para obtermos a solução ótima do problema de transporte, é só clicar em Solve and Analyze, Solve the Problem. 22 Fazendo isso, teremos a solução ótima para o problema que consiste em transportar 16.000 veículos de Curitiba para Paranaguá, 4.000 de Curitiba para Itajaí, 12.000 de São Paulo para Santos e 4.000 veículos de São Paulo para Itajaí. Como a oferta é maior do que a demanda, São Paulo terá, em estoque, 9.000 unidades (Unused_Supply). O custo total corresponde a R$ 6.480.000,00. Caso a oferta supere a demanda, o WinQSB irá informar qual ou quais destinos deixarão de receber a quantidade solicitada (Unfilled_Demand). Um caso particular de um problema de transporte é uma classe de problemas conhecida como problemas de designação. Mas, o que é um problema de designação? TEMA 4 - PROBLEMAS DE DESIGNAÇÃO Um problema de designação é um caso particular de um problema de transporte onde a capacidade de cada origem é igual a 1 e a demanda de cada destino também é igual a 1. Mesmo havendo métodos específicos, é possível resolvermos um problema de designação utilizando os mesmos métodos já existentes para a resolução de problemas de transporte. O número de origens deve ser igual ao número de destinos. Assim como nos problemas de transporte, caso haja mais origens, devemos acrescentar tantos destinos fictícios quantos forem necessários, todos com um custo igual a zero. No caso de existirem mais destinos, o procedimento é criar uma ou mais origens, quantas forem necessárias, com custo zero para cada uma delas. 23 Vamos ver como é possível utilizar o software WinQSB para que possamos resolver problemas de designação. Para ilustrarmos melhor vamos considerar o seguinte problema de designação: Uma empresa tem quatro regiões onde seus produtos são oferecidos e, para atuarem nessas regiões, tem quatro representantes comerciais. O histórico de vendas mostra, em porcentagem, o potencial de cada vendedor nas respectivas regiões que pode ser observado na tabela a seguir. Com base nessas informações, como a empresa deve relacionar cada vendedor com cada região para que o potencial total dos vendedores seja o maior possível? O WinQSB possui uma rotina específica para a resolução de problemas de designação, mas para resolvermos esse problema, utilizaremos a opção “Transportation Problem” do WinQSB. Inicialmente, basta clicar no menu Iniciar. Em seguida, Clicar em WinQSB, Network Modeling. 24 Em seguida, clicaremos em File, Nem Problem. Deveremos selecionar a opção Transportation Problem. Em seguida preencher o campo Number os Sources, número de origens, com o número 4 e o campo Number of Destinations, número de destinos, com o número 4. O critério da função objetivo é “Maximization”, pois o objetivo é maximizar o potencial total dos vendedores. 25 Clicando em OK, o WinQSB abrirá uma tela com uma tabela para que possamos colocar as informações pertinentes ao problema: a capacidade de cada origem (Supply) deve ser igual a 1 e a demanda de cada destino (Demand) também deve ser igual a 1. As porcentagens de cada representante são as fornecidas pelo exemplo. Mas antes de colocarmos essas informações, é importante clicarmos em Edit, Node Names, para efetuarmos a troca dos nomes das origens e dos destinos. No lugar de Source 1, Source 2, Source 3 e Source 4 iremos digitar Vendedor 1, Vendedor 2, Vendedor 3 e Vendedor 4 e no lugar de Destination 1, Destination 2, Destination 3 e Destination 4 digitaremos Região 1, Região 2, Região 3 e Região 4. 26 O próximo passo é preenchermos a tabela com as porcentagens dos representantes. É importante lembrarmos que no caso dos problemas de designação, as ofertas e as demandas são iguais a 1. E, finalmente, para obtermos a solução ótima do problema de transporte, é só clicar em Solve and Analyze, Solve the Problem. A solução que maximiza o potencial total dos representantes é: Vendedor 1 para a Região3 Vendedor 2 para a Região1 Vendedor 3 para a Região2 27 Vendedor 4 para a Região4 Como foi colocar em prática o que estudamos até agora? Para complementar ainda mais o conteúdo visto junto com os exercícios, acesse os links a seguir, neles você encontrará algumas sugestões bem interessantes de leitura. http://aquarius.ime.eb.br/~webde2/prof/vania/pubs/2009-2010/PLURIS- CARGA.pdf http://www.isegi.unl.pt/docentes/vlobo/IO/IO_5_Transportes_2.pdf http://www.celiomoliterno.eng.br/Arquivos/Pesop/Designacao.pdf
Compartilhar