AULA 3 Problemas de transporte e método do custo mínimo

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 
Iremosescolher 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 nomes das 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 
http://aquarius.ime.eb.br/~webde2/prof/vania/pubs/2009-2010/PLURIS-CARGA.pdf
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