Unidade IV - Problemas de Transporte e de Designação

Prévia do material em texto

Simulação e Tomada 
de Decisão
Material Teórico
Responsável pelo Conteúdo:
Prof. Ms. Roberto Luiz Garcia Vichinsky
Revisão Textual:
Prof. Ms. Fátima Furlan
Problemas de Transporte e de Designação
• Problema de Transporte
• Problema de Designação
• Conclusão
 · Estudar as classes especiais da Programação Linear com foco nos 
problemas relativos às operações de transporte de mercadorias ou 
produtos e alocação adequada de recursos de mão-de-obra para a 
realização de tarefas específicas.
OBJETIVO DE APRENDIZADO
Problemas de Transporte 
e de Designação
Orientações de estudo
Para que o conteúdo desta Disciplina seja bem 
aproveitado e haja uma maior aplicabilidade na sua 
formação acadêmica e atuação profissional, siga 
algumas recomendações básicas: 
Assim:
Organize seus estudos de maneira que passem a fazer parte 
da sua rotina. Por exemplo, você poderá determinar um dia e 
horário fixos como o seu “momento do estudo”.
Procure se alimentar e se hidratar quando for estudar, lembre-se de que uma 
alimentação saudável pode proporcionar melhor aproveitamento do estudo.
No material de cada Unidade, há leituras indicadas. Entre elas: artigos científicos, livros, vídeos e 
sites para aprofundar os conhecimentos adquiridos ao longo da Unidade. Além disso, você também 
encontrará sugestões de conteúdo extra no item Material Complementar, que ampliarão sua 
interpretação e auxiliarão no pleno entendimento dos temas abordados.
Após o contato com o conteúdo proposto, participe dos debates mediados em fóruns de discussão, 
pois irão auxiliar a verificar o quanto você absorveu de conhecimento, além de propiciar o contato 
com seus colegas e tutores, o que se apresenta como rico espaço de troca de ideias e aprendizagem.
Organize seus estudos de maneira que passem a fazer parte 
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Determine um 
horário fixo 
para estudar.
Aproveite as 
indicações 
de Material 
Complementar.
Procure se alimentar e se hidratar quando for estudar, lembre-se de que uma 
Não se esqueça 
de se alimentar 
e se manter 
hidratado.
Aproveite as 
Conserve seu 
material e local de 
estudos sempre 
organizados.
Procure manter 
contato com seus 
colegas e tutores 
para trocar ideias! 
Isso amplia a 
aprendizagem.
Seja original! 
Nunca plagie 
trabalhos.
UNIDADE Problemas de Transporte e de Designação
Contextualização
A resolução de modelos matemáticos por meio da Programação Linear não 
é uma tarefa simples, principalmente quando o número de variáveis de decisão 
envolvidas no modelo é muito grande, como acontece normalmente em problemas 
de transporte, onde se tem diversas origens (fábricas), com suas limitações de 
oferta, e diversos destinos (centros de consumo), com suas respectivas demandas. 
E ainda, para cada caminho entre origem e destino temos de considerar o custo 
de transporte.
Para esse tipo de problema, a aplicação do método Simplex se torna inviável 
se for feita de forma manual (geralmente, utiliza-se recursos computacionais para 
esse feito), por essa razão, foram desenvolvidos diversos métodos com o objetivo 
de simplificar e reduzir o trabalho braçal exigido pela resolução dos chamados 
“Problemas de Transporte”. Dentre os métodos existentes, destacamos o método 
do “Canto Noroeste”, que nos fornece uma solução inicial para o problema, 
que geralmente não é a solução ótima, e o método “Stepping Stone”, que parte 
da solução inicial e nos fornece a solução ótima do problema por meio de um 
algoritmo iterativo.
Conhecer os métodos para a resolução de problemas de programação linear, 
e saber aplicá-los adequadamente ao tipo de modelo em questão, são requisitos 
essenciais para um bom profissional de Pesquisa Operacional. Da mesma forma, 
são requisitos essenciais o conhecimento e a habilidade na utilização das ferramentas 
computacionais, que geralmente são utilizadas em ambientes organizacionais, 
visando à rapidez e à confiabilidade na resolução de problemas complexos de 
programação linear.
8
9
Problema de Transporte
Defi nição
Dentro da Pesquisa Operacional, o processo de envio de produtos ou mercadorias 
de determinadas origens (como por exemplo, fábricas) para determinados destinos 
(como por exemplo, depósitos ou centros de consumo) é tratado como um 
problema de programação linear, cujo objetivo é determinar a melhor programação 
de expedição, visando à minimização dos custos de transporte e, ao mesmo tempo, 
atendendo às demandas e às restrições de fornecimento. Esse tipo de problema 
recebe um nome bastante sugestivo: “Problema de Transporte”.
O Problema de Transporte pode ser representado graficamente por meio de 
uma rede, onde de um lado indicamos os pontos de origem dos produtos ou 
mercadorias que devem ser expedidos, e do outro lado indicamos os destinos desses 
produtos ou mercadorias. Os pontos de origem e destino são ligados por meio de 
arcos orientados, cada qual contendo duas informações: o custo de transporte por 
unidade de produto e a quantidade de produto a ser transportada. A figura a seguir 
mostra a representação gráfica do Problema de Transporte.
 
1 
2 
m 
. 
. 
. 
1 
2 
n 
. 
. 
. 
ORIGENS DESTINOS 
a1 
a2 
am 
b1 
b2 
bm 
Cij:Xij 
Figura 1
Observe que as origens, assim como os destinos, são representados por nós 
(círculos) numerados a partir de 1 (um). A letra “m” simboliza a quantidade de 
origens e a lera “n” simboliza a quantidade de destinos (que podem ser diferentes). 
Ao lado dos nós das origens, identificamos as quantidades disponíveis de produto 
por meio da letra “a” seguida pelo índice i (i=1, 2,...,m), e ao lado dos nós dos 
destinos, identificamos as demandas por meio da letra “b” seguida pelo índice j (j=1, 
2,...,n). Os arcos orientados (setas que ligam as origens aos destinos) carregam duas 
informações: Cij (custo de transporte da origem ai para o destino bj por unidade de 
produto) e Xij (quantidade de produto a enviar da origem ai para o destino bj).
No Problema de Transporte, temos como dados conhecidos o custo de transporte 
de cada item (Cij), as quantidades de itens disponíveis em cada origem (ai) e as 
9
UNIDADE Problemas de Transporte e de Designação
demandas de cada destino (bj). Como variáveis de decisão, temos as quantidades de 
itens a serem transportados de cada uma das origens i para os destinos j (Xij). Sendo 
assim, a função objetivo do modelo matemático deste tipo de problema pode ser 
escrita conforme equação 1:
Minimizar Z C X
i
m
j
n
ij ij� � �=
= =
∑∑
1 1
onde:
• m é o número de origens (fábricas);
• n é o número de destinos (depósitos ou centros de consumo);
• Cij é o custo por unidade transportada da origem i para o destino j;
• Xij é a quantidade de itens transportados da origem i para o destino j.
As restrições do Problema de Transporte devem traduzir a seguinte situação: 
as origens (fábricas) não podem produzir mais do que suas capacidades e os 
destinos (depósitos ou centros de consumo) não podem receber quantidades de 
itens superiores às suas demandas. Na modelagem dessas restrições, podemos nos 
deparar com três situações distintas, sendo elas:
1. As quantidades ofertadas pelas origens são iguais às quantidades 
demandadas pelos destinos;
2. As quantidades ofertadas pelas origens são maiores que as quantidades 
demandadas pelos destinos;
3. As quantidades ofertadas pelas origens são menores que as quantidades 
demandadas pelos destinos.
Na primeira situação, teremos um equilíbrio perfeito entre oferta e demanda, neste 
caso, as restrições podem ser escritas diretamente por meio de equações (igualdades).
Na segunda situação, onde a oferta é maior que a demanda, devemos introduzir 
no modelo um destino fantasma (dummy), que terá como custo de transporte 
igual a zero e demanda igual à diferença entre o total ofertado pelas origens e 
o total demandado pelos destinos. Dessa forma, o modelo ficará artificialmente 
equilibrado, ou seja,a oferta será igual à demanda, e assim podemos escrever as 
restrições como igualdades.
Na terceira situação, onde a oferta é menor que a demanda, devemos introduzir 
uma origem fantasma (dummy) que terá como custo de transporte igual a zero e 
capacidade de produção igual à diferença entre o total ofertado pelas origens e o 
total demandado pelos destinos. E assim também podemos escrever as restrições 
por meio de equações, já que a oferta e a demanda foram artificialmente igualadas.
10
11
Dessa forma teremos um equilíbrio no sistema, ou seja, o total ofertado pelas 
origens será igual, ou artificialmente igual, ao total demandado pelos destinos. 
Podemos então representar as restrições do modelo por meio das equações 2 e 3 
apresentadas a seguir:
Restriçõesdeofertas X a parai m
j
n
ij i� � :��� � ��� � ,�, ,
=
∑ = = …( )
1
1 2
Restriçõesdedemandas X b para j n
i
m
ij j� � :��� � ��� � ,�, ,
=
∑ = = …( )
1
1 2
Aplicação
Para demonstrar a aplicação da programação linear na resolução de um problema 
de transporte, vamos tomar um exemplo prático, definido pelo seguinte cenário:
A empresa TCOMP, fabricante de computadores, possui duas fábricas localizadas 
em São Paulo e Curitiba. Os computadores produzidos por essas fábricas 
devem ser enviados para os centros de consumo localizados em Natal, Recife e 
Salvador. Sabendo-se que as quantidades ofertadas pelas fábricas e as quantidades 
demandadas pelos centros de consumo, assim como os custos de transporte 
por unidade de computador, estão representados na tabela a seguir (dados do 
problema), determine as quantidades que devem ser enviadas por fábrica para 
cada centro de consumo, de maneira a minimizar os custos de transporte.
Tabela de dados do problema
C. de Consumo
Fábricas
Natal
(1)
Recife
(2)
Salvador
(3)
Capacidade
(oferta)
São Paulo (1) 45 17 21 1500
Curitiba (2) 14 18 19 1300
Demanda 1200 1400 700
Observações:
• Na tabela, os dados representados em vermelho correspondem aos custos 
de transporte, por unidade de item, entre as origens (linhas da tabela) e os 
destinos (colunas da tabela);
• Os dados representados em azul correspondem às capacidades de produção 
(oferta) de cada uma das origens (fábricas);
• Os dados representados em verde correspondem às quantidades demandadas 
pelos centros de consumo.
11
UNIDADE Problemas de Transporte e de Designação
Observando o cenário, podemos perceber que o total demandado pelos centros 
consumidores é de 3.300 unidades de computadores. Por outro lado, a capacidade 
produtiva das fábricas é de 2.800 computadores. Dessa forma, temos uma quanti-
dade demandada superior à quantidade ofertada, sendo assim, devemos introduzir 
no modelo uma origem fantasma (dummy) com capacidade produtiva igual à dife-
rença entre o total demandado e o total ofertado, que neste caso é de 500 unidades 
(3.300 - 2.800). Caso a situação fosse inversa, ou seja, se a oferta fosse maior que 
a demanda, deveríamos então introduzir um destino artificial (dummy) ao invés de 
uma origem artificial. A introdução de uma origem ou de um destino dummy tem 
por objetivo o equilíbrio do modelo (a oferta deve ser igual à demanda).
A representação gráfica do problema da empresa TCOMP é apresentada na 
figura a seguir.
 
Natal 
b1 = 1200 unidades 
Recife 
b2 = 1400 unidades 
Salvador 
b3 = 700 unidades 
São Paulo 
a1 = 1500 unidades 
Curi�ba 
a2 = 1300 unidades 
Dummy 
a3 = 500 unidades 
 
 
 
 
 
Figura 2
Analisando o cenário, podemos destacar os seguintes dados:
Variáveis de decisão
• X11 - Nº de computadores a enviar de São Paulo para Natal;
• X12 - Nº de computadores a enviar de São Paulo para Recife;
• X13 - Nº de computadores a enviar de São Paulo para Salvador;
• X21 - Nº de computadores a enviar de Curitiba para Natal;
• X22 - Nº de computadores a enviar de Curitiba para Recife;
• X23 - Nº de computadores a enviar de Curitiba para Salvador;
• X31 - Nº de computadores a enviar de dummy para Natal;
• X32 - Nº de computadores a enviar de dummy para Recife;
• X33 - Nº de computadores a enviar de dummy para Salvador.
12
13
Parâmetros
• C11=45 - Custo do transporte por unidade entre São Paulo e Natal;
• C12=17 - Custo do transporte por unidade entre São Paulo e Recife;
• C13=21 - Custo do transporte por unidade entre São Paulo e Salvador;
• C21=14 - Custo do transporte por unidade entre Curitiba e Natal;
• C22=18 - Custo do transporte por unidade entre Curitiba e Recife;
• C23=19 - Custo do transporte por unidade entre Curitiba e Salvador;
• C31=0 - Custo do transporte por unidade entre dummy e Natal;
• C32=0 - Custo do transporte por unidade entre dummy e Recife;
• C33=0 - Custo do transporte por unidade entre dummy e Salvador.
Restrições
• a1=1500 - Capacidade produtiva (oferta) da fábrica de São Paulo;
• a2=1300 - Capacidade produtiva (oferta) da fábrica de Curitiba;
• a3=500 - Capacidade produtiva (oferta) de dummy;
• b1=1200 - Demanda do centro consumidor de Natal;
• b2=1400 - Demanda do centro consumidor de Recife;
• b3=700 - Demanda do centro consumidor de Salvador.
Com os dados em mãos, devemos então construir o modelo matemático do 
problema, considerando as equações 1 (função objetivo), 2 (restrições de oferta) e 
3 (restrições de demanda).
Modelo Matemático
Minimizar Z=45X11 + 17X12 + 21X13 + 14X21 + 18X22 + 19X23
Sujeito a: X11 + X12 + X13 = 1500 (restrição de oferta - São Paulo)
 X21 + X22 + X23 = 1300 (restrição de oferta - Curitiba)
 X31 + X32 + X33 = 500 (restrição de oferta - dummy)
 X11 + X21 + X31 = 1200 (restrição de demanda - Natal)
 X12 + X22 + X32 = 1400 (restrição de demanda - Recife)
 X13 + X23 + X33 = 700 (restrição de demanda - Salvador)
 Xij ≥ 0 , para i=1,2,3 e j=1,2,3 (não negatividade)
Tendo o modelo matemático preparado, podemos resolver o problema aplicando 
um dos métodos da programação linear, como por exemplo, o método Simplex. 
No entanto, para o caso particular do problema de transporte, normalmente 
empregamos algoritmos específicos que reduzem o volume de trabalho, suprimindo 
algumas passagens do algoritmo Simplex.
13
UNIDADE Problemas de Transporte e de Designação
Vamos aqui adotar dois algoritmos largamente utilizados na resolução de 
problemas de transporte, sendo eles: o Método do Canto Noroeste e o Método 
Stepping Stone. O primeiro nos permitirá encontrar a solução inicial, e o segundo 
nos permitirá encontrar a solução ótima do problema a partir da solução inicial. 
Portanto, aplicaremos esses dois métodos, de forma complementar, a fim de 
resolvermos o problema da empresa TCOMP.
Solução Inicial – Aplicação do Método do Canto Noroeste
Para a aplicação desse algoritmo, devemos primeiramente construir uma tabela, 
conforme mostrado a seguir:
Destinos
Natal
(1)
Recife
(2)
Salvador
(3) Oferta
Origens
São Paulo (1) 45 17 21 1500
Curitiba (2) 14 18 19 1300
Dummy (3) 0 0 0 500
Demanda 1200 1400 700
Nesta tabela, as linhas representam as origens e as colunas representam os 
destinos. A última coluna da tabela deve indicar as capacidades produtivas (ofertas) 
das origens (dados representados em azul) e a última linha deve indicar as demandas 
dos destinos (dados representados em verde). Em cada uma das células internas da 
tabela (representadas em cinza), devemos indicar no canto esquerdo superior o 
custo de transporte entre a origem e o destino (dados representados em vermelho).
Em seguida, devemos encontrar a solução inicial do problema começando pela 
análise da célula do canto noroeste da tabela (célula do canto esquerdo superior da 
área interna da tabela), que no nosso caso é a célula correspondente à origem “São 
Paulo” e destino “Natal”, cujo custo de transporte por unidade de produto é de R$ 
45,00. Observe que a demanda de Natal é de 1200 unidades e a oferta de São 
Paulo é 1500 unidades, sendo assim, devemos alocar 1200 unidades na célula, 
zerando a demanda de Natal e subtraindo essas unidades da quantidade ofertada 
pela fábrica de São Paulo. Nossa tabela deverá tero seguinte aspecto:
Destinos
Natal
(1)
Recife
(2)
Salvador
(3) Oferta
Origens
São Paulo (1) 45 1200 17 21 1500 (300)
Curitiba (2) 14 18 19 1300
Dummy (3) 0 0 0 500
Demanda 1200 (0) 1400 700
14
15
Observe que a coluna de Natal já está resolvida, sendo assim, devemos agora 
analisar a célula do canto noroeste da nova área válida da tabela (área cinza), que 
no nosso caso é a célula correspondente à origem “São Paulo” e destino “Recife”. 
A origem tem agora a disponibilidade de 300 unidades do produto, ao passo que 
o destino demanda 1400 unidades, sendo assim, devemos indicar na célula em 
questão a quantidade de 300 unidades, zerando a oferta da origem e subtraindo 
essa mesma quantidade da demanda do destino, conforme demonstração a seguir.
Destinos
Natal
(1)
Recife
(2)
Salvador
(3) Oferta
Origens
São Paulo (1) 45 1200 17 300 21 300 (0)
Curitiba (2) 14 18 19 1300
Dummy (3) 0 0 0 500
Demanda (0) 1400 (1100) 700
Veja que o destino “Recife” ainda necessita de 1100 unidades do produto. 
A fábrica de São Paulo não consegue mais atender essa demanda, pois toda a 
sua produção já foi alocada. Dessa forma, a linha da origem São Paulo deve ser 
excluída da área válida da tabela.
Analisemos agora a próxima célula do canto noroeste da nova área válida, 
que é justamente a célula correspondente à origem “Curitiba” e destino “Recife”. 
A quantidade demandada pelo destino agora é de 1100 unidades, e a quantidade 
ofertada pela origem é de 1300 unidades. Devemos então alocar 1100 unidades na 
célula, zerando a demanda do destino “Recife” e subtraindo essa mesma quantidade 
da origem “Curitiba”, conforme demonstração a seguir.
Destinos
Natal
(1)
Recife
(2)
Salvador
(3) Oferta
Origens
São Paulo (1) 45 1200 17 300 21 0
Curitiba (2) 14 18 1100 19 1300 (200)
Dummy (3) 0 0 0 500
Demanda (0) 1100 (0) 700
Veja que a demanda do destino “Recife” foi plenamente atendida, sendo assim, 
a coluna desse destino deve ser excluída da área válida da tabela.
A próxima célula do canto noroeste da nova área válida é a célula correspondente 
à origem “Curitiba” e destino “Salvador”. A quantidade demandada pelo destino 
é de 700 unidades, e a quantidade ofertada pela origem agora é de 200 unidades. 
Devemos então alocar essas 200 unidades na célula, zerando a oferta da origem 
“Curitiba” e subtraindo essa mesma quantidade da demanda do destino “Salvador”, 
conforme demonstração a seguir.
15
UNIDADE Problemas de Transporte e de Designação
Destinos
Natal
(1)
Recife
(2)
Salvador
(3) Oferta
Origens
São Paulo (1) 45 1200 17 300 21 0
Curitiba (2) 14 18 1100 19 200 200 (0)
Dummy (3) 0 0 0 500
Demanda 0 0 700 (500)
Temos agora uma única célula na área válida da tabela, que é a célula correspon-
dente à origem artificial “Dummy” e destino “Salvador”, cujas quantidades oferta-
das e demandadas, respectivamente, são exatamente iguais (500 unidades). Vamos 
então alocar essa quantidade na célula em questão e zerar a oferta de “Dummy” e 
a demanda de “Salvador”. A nova versão da tabela terá o seguinte aspecto:
Destinos
Natal
(1)
Recife
(2)
Salvador
(3) Oferta
Origens
São Paulo (1) 45 1200 17 300 21 0
Curitiba (2) 14 18 1100 19 200 0
Dummy (3) 0 0 0 500 0
Demanda 0 0 0
Após a conclusão do processo (quando todas as demandas e ofertas apresenta-
rem quantidades zeradas), teremos a solução inicial do problema, que geralmente 
ainda não é a solução ótima, apesar de que todas as restrições (demandas e ofer-
tas) tenham sido atendidas.
Para encontrarmos o resultado dessa solução inicial, basta somarmos os custos 
totais de transporte (custo unitário X quantidade enviada) das células que contêm 
quantidades maiores que zero na tabela. Teremos assim o seguinte resultado para 
a função objetivo do nosso problema:
Z = 45x1200 + 17x300 + 18x1100 + 19x200 + 0x500 = 82700
Vamos agora aplicar o método Stepping Stone para encontrarmos a solução 
ótima do problema, ou seja, a solução que gerará o menor custo de transporte para 
a empresa TCOMP.
Solução Ótima – Aplicação do Método Stepping Stone
Para a aplicação desse método, devemos primeiramente introduzir o número 
zero nas células da tabela que estão vazias. Vamos também preencher as células da 
linha da demanda e da coluna da oferta com os dados originais. A tabela deverá se 
apresentar da seguinte forma:
16
17
Destinos
Natal
(1)
Recife
(2)
Salvador
(3) Oferta
Origens
São Paulo (1) 45 1200 (X11)
17 300 (X12)
21 0 (X13) 1500
Curitiba (2) 14 0 (X21)
18 1100 (X22)
19 200 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0 500 (X33) 500
Demanda 1200 1400 700
As células que contêm valores diferentes de zero correspondem às variáveis 
básicas do modelo, sendo elas: X11, X12, X22, X23 e X33. Por outro lado, as células 
zeradas correspondem às variáveis não básicas, sendo elas: X13, X21, X31 e X32. 
Com o intuito de facilitar a identificação das células, veja que em cada uma delas foi 
colocado, entre parênteses e com destaque em azul, o nome da respectiva variável.
A próxima etapa do algoritmo Stepping stone consiste em calcular a contri-
buição de cada uma das variáveis não básicas na composição do custo total. Esse 
processo é realizado por meio dos seguintes passos:
I. Localize na tabela a próxima célula que contém uma variável não básica 
(célula zerada), e a partir dessa célula, que chamaremos de “célula de 
partida”, trace um caminho fechado (loop) observando as seguintes regras:
Siga na direção horizontal ou vertical em qualquer sentido (para cima ou 
para baixo, para a direita ou esquerda) até encontrar uma célula que não 
seja zerada. Mude a direção (horizontal para vertical, ou vice-versa) fazendo 
uma curva de 90 graus e siga nessa direção até encontrar a próxima célula 
que não esteja zerada. Repita esse procedimento até que o caminho esteja 
fechado, ou seja, até retornar para a “célula de partida”;
II. Após a definição do caminho (loop), calcule a contribuição realizando uma 
soma algébrica dos custos de transporte das células que formam os vértices 
(quinas) desse caminho. Porém, para manter o equilíbrio do processo, 
devemos alternar os sinais desses custos, iniciando pelo + (mais), sendo 
assim, o custo da “célula de partida” será positivo, o custo do segundo 
vértice do caminho será negativo, o custo do terceiro vértice será positivo, e 
assim por diante até que o caminho seja completado;
III. Repita os passos I e II para as próximas células zeradas da tabela, até que 
todas as contribuições das variáveis não básicas sejam calculadas;
IV. Após calcular todas as contribuições, verifique se existem resultados 
negativos. Se isso ocorrer, significa que a solução ótima não foi encontrada, 
sendo assim, localize o menor resultado (resultado negativo que apresenta 
o maior valor absoluto). A variável não básica da célula que foi considerada 
como “célula de partida” do caminho que apresenta o menor valor, é 
denominada “variável que entra”.
17
UNIDADE Problemas de Transporte e de Designação
V. Considerando as quantidades de produtos alocadas nas células que formam 
os vértices do caminho iniciado pela “variável que entra”, localize a maior 
quantidade que pode ser transferida para a célula da «variável que entra», 
sem que haja desbalanceamento da tabela. Faça a transferência dessa 
quantidade e ajuste as demais quantidades das células que formam os 
vértices do caminho, de maneira que a tabela continue balanceada.
VI. Obtendo a nova tabela, repita os procedimentos a partir do passo I. A 
solução ótima será encontrada quando não existir nenhum valor negativo 
de contribuição, conforme descrito no passo IV.
Vamos então realizar esses passos sobre a nossa tabela inicial. Devemos localizar 
a primeira célula zerada para ser tomada como “célula de partida” para o caminho 
fechado. Note que essa célula corresponde a X13, nesse caso podemos definir o 
caminho X13→X12→X22→X23→X13, conforme demonstrado a seguir:
Destinos
Natal
(1)
Recife
(2)
Salvador
(3) Oferta
Origens
São Paulo (1) 45 1200 (X11)
17 300 (X12)
21 0 (X13)1500
Curitiba (2) 14 0 (X21)
18 1100 (X22)
19 200 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
Para acharmos a contribuição da célula X13, devemos realizar a soma algébrica 
dos custos das células que formam os vértices do caminho, alternando entre os 
sinais de positivo e negativo, iniciando pelo positivo. Teremos então:
Partida: X13 (origem 1 para destino 3): + 21 - 17 + 18 - 19 = 3
A próxima variável não básica encontra-se na célula X21. Tomando essa célula 
como partida, podemos definir o caminho X21→X22→X12→X11→X21, conforme 
demonstrado a seguir:
Destinos
Natal
(1)
Recife
(2)
Salvador
(3) Oferta
Origens
São Paulo (1) 45 1200 (X11)
17 300 (X12)
21 0 (X13) 1500
Curitiba (2) 14 0 (X21)
18 1100 (X22)
19 200 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
Teremos como contribuição:
Partida: X21 (origem 2 para destino 1): + 14 - 18 + 17 - 45 = -32
18
19
A próxima variável não básica ocupa a célula X31. Tomando essa célula 
como partida, podemos definir o caminho X31→X11→X12→X22→X23→X33→X31, 
conforme demonstrado a seguir:
Destinos
Natal
(1)
Recife
(2)
Salvador
(3) Oferta
Origens
São Paulo (1) 45 1200 (X11)
17 300 (X12)
21 0 (X13) 1500
Curitiba (2) 14 0 (X21)
18 1100 (X22)
19 200 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
Teremos como contribuição:
Partida: X31 (origem 3 para destino 1): 0 - 45 + 17 - 18 + 19 - 0 = -27
A última variável não básica está na célula X32. Tomando essa célula como 
partida, podemos então definir o caminho X32→X22→X23→X33→X32, conforme 
demonstrado a seguir:
Destinos
Natal
(1)
Recife
(2)
Salvador
(3) Oferta
Origens
São Paulo (1) 45 1200 (X11)
17 300 (X12)
21 0 (X13) 1500
Curitiba (2) 14 0 (X21)
18 1100 (X22)
19 200 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
Teremos como contribuição:
Partida: X32 (origem 3 para destino 2): 0 - 18 + 19 - 0 = 1
Dessa forma, teremos calculado todas as contribuições das variáveis não básicas. 
Agora vamos verificar se existem resultados negativos, se isso ocorrer, devemos 
tomar a variável da célula de partida que apresenta a menor contribuição, dentre 
os resultados negativos como “variável que entra”.
Verificamos então que a menor contribuição é apresentada pela variável não 
básica X21 (-32), conforme podemos observar no resumo a seguir:
X13 (origem 1 para destino 3): + 21 - 17 + 18 - 19 = 3
X21 (origem 2 para destino 1): + 14 - 18 + 17 - 45 = -32 (menor contribuição)
X31 (origem 3 para destino 1): 0 - 45 + 17 - 18 + 19 - 0 = -27
X32 (origem 3 para destino 2): 0 - 18 + 19 - 0 = 1
19
UNIDADE Problemas de Transporte e de Designação
Agora devemos verificar qual é a maior quantidade de produto alocada em uma 
das células que formam o vértice do caminho que tem como partida a célula da 
variável X21. Essa quantidade deve ser transferida para a célula da variável não básica 
X21, sem que haja desbalanceamento da tabela. Podemos facilmente verificar que a 
maior quantidade é 1200, que aparece na célula X11, conforme se observa a seguir.
Destinos
Natal
(1)
Recife
(2)
Salvador
(3) Oferta
Origens
São Paulo (1) 45 1200 (X11)
17 300 (X12)
21 0 (X13) 1500
Curitiba (2) 14 0 (X21)
18 1100 (X22)
19 200 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
No entanto, se a quantidade de 1200 unidades for transferida para a célula X21, 
não conseguiremos manter a tabela balanceada, pois, essa quantidade deverá ser 
subtraída da quantidade da célula X22, cujo valor é 1100, o que gerará um resultado 
negativo, contrariando a restrição de não negatividade. Portanto, devemos descartar 
o valor 1200 e procurar a próxima maior quantidade do caminho, que no nosso 
caso é 1100, encontrada na célula X22.
Devemos alocar a quantidade de 1100 unidades na célula de partida X21 (essa 
variável terá agora o valor 1100) e recalcular as quantidades dos demais vértices do 
caminho, obedecendo a seguinte regra: subtrair o valor de X21 da célula do segundo 
vértice (X22), somar o valor de X21 à célula do terceiro vértice (X12) e subtrair o valor 
de X21 da célula do quarto vértice (X11). Veja que devemos alternar os sinais positivo 
e negativo como o fizemos para calcular as contribuições. Teremos assim a nova 
tabela, conforme se observa a seguir.
Destinos
Natal
(1)
Recife
(2)
Salvador
(3) Oferta
Origens
São Paulo (1) 45 100 (X11)
17 1400 (X12)
21 0 (X13) 1500
Curitiba (2) 14 1100 (X21)
18 0 (X22)
19 200 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
Note que após o procedimento de recálculo, a tabela continua balanceada, ou 
seja, a soma das quantidades das colunas coincide com a demanda dos respectivos 
destinos, assim como a soma das quantidades das linhas coincide com a oferta das 
respectivas origens.
Para encontrarmos a nova solução do problema, basta somarmos os custos 
totais de transporte (custo unitário X quantidade enviada) das células que contêm 
quantidades maiores que zero na tabela. Teremos assim o seguinte resultado para 
a função objetivo:
Z = 45x100 + 17x1400 + 14x1100 + 19x200 + 0x500 = 47500
20
21
Veja que a nova solução (R$ 47.500,00) é melhor que a solução inicial (R$ 
82.700,00), mas será que esse novo resultado é a solução ótima do problema? Não 
saberemos sem antes realizarmos uma nova iteração do algoritmo stepping stone.
Vamos mais uma vez executar os passos para encontrarmos as contribuições 
das variáveis não básicas sobre o custo de transporte, lembrando que esses passos 
consistem na determinação dos caminhos fechados (loops) que partem de cada uma 
das variáveis não básicas (células zeradas). Em seguida, vamos verificar se existe 
alguma contribuição negativa, se isso ocorrer, devemos recalcular as quantidades 
da tabela e realizar uma nova iteração do algoritmo. Caso contrário, ou seja, se não 
existir nenhuma contribuição negativa, a solução ótima foi encontrada.
Contribuição da variável X13 = + 21 - 45 + 14 - 19 = -29
Destinos
Natal Recife Salvador Oferta
Origens
São Paulo (1) 45 100 (X11)
17 1400 (X12)
21 0 (X13) 1500
Curitiba (2) 14 1100 (X21)
18 0 (X22)
19 200 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
Contribuição da variável X22 = + 18 - 14 + 45 - 17 = 32
Destinos
Natal Recife Salvador Oferta
Origens
São Paulo (1) 45 100 (X11)
17 1400 (X12)
21 0 (X13) 1500
Curitiba (2) 14 1100 (X21)
18 0 (X22)
19 200 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
Contribuição da variável X31 = 0 - 14 + 19 - 0 = 5
Destinos
Natal Recife Salvador Oferta
Origens
São Paulo (1) 45 100 (X11)
17 1400 (X12)
21 0 (X13) 1500
Curitiba (2) 14 1100 (X21)
18 0 (X22)
19 200 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
Contribuição da variável X32 = 0 - 0 + 19 - 14 + 45 -17 = 33
Destinos
Natal Recife Salvador Oferta
Origens
São Paulo (1) 45 100 (X11)
17 1400 (X12)
21 0 (X13) 1500
Curitiba (2) 14 1100 (X21)
18 0 (X22)
19 200 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
21
UNIDADE Problemas de Transporte e de Designação
Observe que a contribuição da variável X13 é negativa. Neste caso, devemos 
recalcular as quantidades das células que formam os vértices do caminho que tem 
como partida a célula X13. Primeiramente devemos identificar a maior quantidade 
que pode ser transferida para a célula de partida, dentre as quantidades das células 
de vértice, as quais estão destacadas em azul na tabela a seguir.
Destinos
Natal Recife Salvador Oferta
Origens
São Paulo (1) 45 100 (X11)
17 1400 (X12)
21 0 (X13) 1500
Curitiba (2) 14 1100 (X21)
18 0 (X22)
19 200 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
Veja que a maior quantidade que pode ser transferida para a célula X13, sem que 
haja desbalanceamento da tabela e respeitando a restrição de não negatividade,é 
a quantidade de 100 unidades que se encontra alocada na célula X11. Realizando 
a transferência dessa quantidade e recalculando os novos vértices do caminho, 
teremos o seguinte resultado:
Destinos
Natal Recife Salvador Oferta
Origens
São Paulo (1) 45 0 (X11)
17 1400 (X12)
21 100 (X13) 1500
Curitiba (2) 14 1200 (X21)
18 0 (X22)
19 100 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
Recalculando a função objetivo com os dados da nova tabela, teremos a seguin- 
te solução:
Z = 17x1400 + 21x100 + 14x1200 + 19x100 = 44600
Podemos então constatar que a nova solução, que gera um custo de R$ 44.600, 
é melhor que a solução anterior, que gera um custo maior (R$ 47.500). Mas 
devemos voltar à pergunta: será que esse resultado é a solução ótima? 
Mais uma vez a resposta é a mesma: só saberemos após a realização de nova 
iteração do algoritmo stepping stone. Vamos então calcular as contribuições das 
variáveis não básicas da nova tabela.
Contribuição da variável X11 = + 45 - 21 + 19 - 14 = 29
Destinos
Natal Recife Salvador Oferta
Origens
São Paulo (1) 45 0 (X11)
17 1400 (X12)
21 100 (X13) 1500
Curitiba (2) 14 1200 (X21)
18 0 (X22)
19 100 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
22
23
Contribuição da variável X22 = + 18 - 19 + 21 - 17 = 3
Destinos
Natal Recife Salvador Oferta
Origens
São Paulo (1) 45 0 (X11)
17 1400 (X12)
21 100 (X13) 1500
Curitiba (2) 14 1200 (X21)
18 0 (X22)
19 100 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
Contribuição da variável X31 = 0 - 14 + 19 - 0 = 5
Destinos
Natal Recife Salvador Oferta
Origens
São Paulo (1) 45 0 (X11)
17 1400 (X12)
21 100 (X13) 1500
Curitiba (2) 14 1200 (X21)
18 0 (X22)
19 100 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
Contribuição da variável X32 = 0 - 0 + 21 - 17 = 4
Destinos
Natal Recife Salvador Oferta
Origens
São Paulo (1) 45 0 (X11)
17 1400 (X12)
21 100 (X13) 1500
Curitiba (2) 14 1200 (X21)
18 0 (X22)
19 100 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
Veja que agora não existe nenhuma contribuição negativa. Neste caso, o 
último resultado encontrado para a função objetivo (R$ 44.600,00) é a solução 
ótima do problema. Analisando a tabela resultante, podemos então determinar as 
quantidades de produtos que cada uma das origens deve enviar para os destinos.
Tabela resultante após aplicação do método stepping stone
Destinos
Natal Recife Salvador Oferta
Origens
São Paulo (1) 45 0 (X11)
17 1400 (X12)
21 100 (X13) 1500
Curitiba (2) 14 1200 (X21)
18 0 (X22)
19 100 (X23) 1300
Dummy (3) 0 0 (X31)
0 0 (X32)
0
 500 (X33) 500
Demanda 1200 1400 700
23
UNIDADE Problemas de Transporte e de Designação
Tabela resumo
Origem Destino Qtde. Custo (R$) Total (R$)
São Paulo Recife 1.400 17,00 23.800,00
São Paulo Salvador 100 21,00 2.100,00
Curitiba Natal 1.200 14,00 16.800,00
Curitiba Salvador 100 19,00 1.900,00
Dummy Salvador 500 0,00 0,00
Total 3.300 44.600,00
Veja que após a aplicação combinada dos métodos do “Canto Noroeste” e 
“stepping stone”, teremos a solução ótima do problema. Mas será que a solução 
seria a mesma se aplicássemos o método Simplex? Podemos adiantar a resposta: 
sim, a solução será a mesma. Mas lembre-se de que o método Simplex exige que a 
função objetivo seja de maximização, e o nosso problema procura o custo mínimo 
(minimização). Neste caso, se você pretende confrontar os resultados aplicando o 
Simplex, converta a função objetivo para maximização, utilizando a seguinte regra: 
Min(z) = Max(-z).
Entretanto, alguns softwares realizam automaticamente essa conversão, como é o 
caso do aplicativo LIPs, desenvolvido por Michael Melnick do departamento de Pes-
quisa Operacional da Universidade Estatal de Gerenciamento de Moscow - Rússia.
O aplicativo pode ser baixado gratuitamente através do link: https://goo.gl/DLyT5g
Ex
pl
or
A seguir, é apresentado um pequeno tutorial para a resolução do nosso problema 
através do software LIPs.
1. Abra o aplicativo LIPs (que deve estar instalado em seu computador) e 
acesse o menu “Arquivo/Modelo Tabela” para introduzir o modelo mate-
mático do problema.
2. Será apresentada a janela de parâmetros do modelo. Informe a quantidade 
de variáveis de decisão (no nosso caso são nove), o número de restrições 
técnicas (no nosso caso são seis) e o número de funções objetivo (no nosso 
caso é apenas uma). Selecione a opção “Minimização” e clique em “O.K.”.
24
25
3. O software apresentará uma tabela que deverá ser preenchida com os 
dados do modelo matemático. A única diferença entre o nosso modelo e 
o modelo apresentado pela tabela são os nomes das variáveis de decisão. 
No nosso modelo original, as variáveis são identificadas como X11, X12, X13, 
X21, X22, X23, X31, X32 e X33, ao passo que na tabela elas são identificadas, 
respectivamente, como X1 a X9. 
Modelo matemático original
Minimizar Z=45X11 + 17X12 + 21X13 + 14X21 + 18X22 + 19X23
Sujeito a: X11 + X12 + X13 = 1500 (restrição de oferta - São Paulo)
 X21 + X22 + X23 = 1300 (restrição de oferta - Curitiba)
 X31 + X32 + X33 = 500 (restrição de oferta - dummy)
 X11 + X21 + X31 = 1200 (restrição de demanda - Natal)
 X12 + X22 + X32 = 1400 (restrição de demanda - Recife)
 X13 + X23 + X33 = 700 (restrição de demanda - Salvador)
 Xij ≥ 0 , para i=1,2,3 e j=1,2,3 (não negatividade)
Tabela preenchida com dados do modelo original
25
UNIDADE Problemas de Transporte e de Designação
4. Após o preenchimento da tabela, tecle F5 (comando “Resolver Modelo”). 
Será apresentada uma nova janela contendo todos os passos do método 
Simplex para a solução do problema. No final da janela você encontrará a 
solução ótima. Veja que é a mesma resposta que obtivemos por meio do 
método stepping stone.
Problema de Designação
Um dos problemas bastante comuns nas organizações é a questão da alocação 
de mão-de-obra para a execução das diversas tarefas. O processo de designação de 
funcionários com diferentes graus de habilidade para ocupação de uma determinada 
função é tratado como um problema de Pesquisa Operacional, pois o objetivo 
é encontrar os funcionários cujas habilidades combinem com as exigências das 
tarefas. Uma tarefa realizada por pessoa habilitada custa menos do que se for 
realizada por pessoa não habilitada ou pouco habilitada.
O problema de designação pode ser resolvido com os mesmos métodos de 
resolução aplicados ao problema de transporte, onde os funcionários representam as 
origens, cada qual com quantidade ofertada igual a 1 (um), e as tarefas representam 
os destinos, cada qual com quantidade demandada também igual a 1 (um). Para cada 
funcionário (origem) determina-se o custo que gerará para cada tarefa, com base 
em suas habilidades. Esse custo corresponde ao custo de expedição do problema 
de transporte.
26
27
Conclusão
Os métodos utilizados para a resolução de problemas de transporte, assim 
como problemas de designação, são técnicas alternativas ao método Simplex, 
adaptadas para aplicação em problemas específicos de expedição de produtos 
ou de alocação de mão-de-obra. Apresentamos aqui os métodos do “Canto 
Noroeste” (que determina a solução inicial do problema) e “stepping stone” (que 
determina a solução ótima). A aplicação combinada desses métodos, apesar de 
gerar um volume de trabalho menor em comparação ao volume de trabalho 
gerado pelo método Simplex, é uma tarefa trabalhosa e demorada se realizada 
de forma manual. Porém, o conhecimento desses métodos e a habilidade em 
aplicá-los manualmente são de grande importância para o desenvolvimento da 
visão crítica e analítica do profissional.
27
UNIDADE Problemas de Transporte e de Designação
Material Complementar
Indicações para saber mais sobre os assuntos abordados nesta Unidade:
 Livros
Introdução à Pesquisa Operacional
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à Pesquisa Operacional. 9. ed. 
PortoAlegre: Mc Graw-Whill, 2013. Capítulo 8.
Pesquisa Operacional
TAHA, Hamdy A. Pesquisa Operacional. 8ª edição. Pearson, 2007. Capítulo 5
 Leitura
Programação Linear: Um estudo de Caso sobre os Custos de Transporte em uma Empresa do Setor de 
Confecções de Catalão-GO
https://goo.gl/w3hj3T
Minimização de Custos Logísticos de Transporte através da Alocação Ótima de Clientes a Centros de Distribuição
https://goo.gl/4NdVyI
28
29
Referências
ANDRADE, E. L. Introdução à Pesquisa Operacional: Métodos e Modelos Para a 
Análise de Decisão. 4. ed. Rio de Janeiro: Ltc-Livros Técnicos e Científicos, 2011.
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à Pesquisa Operacional. 9. ed. 
Porto Alegre: Mc Graw-Whill, 2013.
TAHA, Hamdy A. Pesquisa Operacional. 8ª edição. Pearson, 2007
29