Pesquisa Operacional fluxo de redes

Prévia do material em texto

25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 1/25
PESQUISA	OPERACIONAL
UNIDADE 4 - FLUXO EM REDES
Rayane Ester Felıćio Santiago
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 2/25
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 3/25
Introdução
Quando pensamos em �luxo em redes, a primeira coisa que vem à cabeça está relacionada ao transporte,
aquilo que pode ir de um ponto a outro em uma rede, o que pode ser direcionado de uma origem a um destino
por meio de uma rede. Esse pensamento é totalmente lógico, pois o �luxo em redes representa tudo isso.
A palavra �luxo	quer dizer aquilo que se movimenta de modo contı́nuo, ou o escoamento contı́nuo de algo que
segue um curso. O segundo conceito é o mais conveniente para o uso durante o aprendizado desta unidade, na
qual veremos justamente como funciona o escoamento de algo ao longo de uma rede – é o que determina o
curso desse �luxo.
Os arcos de uma rede podem orientar e designar a direção para o qual um �luxo seguirá, desde sua origem até
o seu destino; portanto, relacionar o �luxo em redes ao transporte é algo totalmente natural, já que a intenção
aqui será, justamente, determinar o �luxo ideal para que algo seja transportado de uma origem a um destino,
seja para garantir maior e�iciência de um processo, seja para reduzir um custo, entre outros.
O �luxo por meio de um arco é permitido apenas na direção que esse arco determina e quando está próximo à
origem. Os arcos tendem a apontar de forma a se afastarem do nó, enquanto no destino os arcos tendem a se
aproximar do nó. Mas, observando todos esses critérios, será que dá para conhecer o �luxo máximo que uma
rede pode suportar?
Há alguns casos em que precisamos determinar o custo mı́nimo para transportar o máximo possı́vel, portanto
algumas restrições devem ser respeitadas. Qual será a forma de encontrar uma solução ótima de �luxo em uma
rede de forma a respeitar essas restrições e garantir o menor custo? E quando há determinada quantidade de
unidades na origem, elas devem ser distribuı́das de forma ótima ao longo da rede até o destino, seria possı́vel
determinar esse �luxo?
Essa unidade responderá a todas essas questões, utilizando exemplos práticos que auxiliem a entender a
teoria e os cálculos envolvidos. Você está pronto para ver tanta coisa interessante? Então, bons estudos!
1.1 Caracterização do problema
Para que um �luxo em redes seja executado, algumas condições devem ser respeitadas e a primordial é
observar a orientação, o valor do arco no qual esse �luxo passará, os valores das origens e dos destinos. Esse
tipo de problema é de programação linear (PL), pois devemos de�inir a função objetivo que determinará se
devemos maximizar o retorno ou minimizar o custo, por exemplo, em uma rede. As restrições dizem respeito
aos valores disponı́veis nas origens e necessitados nos destinos. Conforme Lachtermarcher (2016), o �luxo
por redes resolve problemas de programação linear (PPL) especı́�icos, porém de uma forma mais e�iciente que
o método Simplex tradicional.
Por de�inição, o �luxo em uma rede (N,A)	é determinado por uma função de A	em Z 0.	Isso quer dizer que a
função (Z) atribui um valor não negativo a cada arco da rede, porém deve-se atentar para o fundamento básico
do problema de �luxo em rede: os valores de cada nó, que representam as restrições da rede.
Para se respeitar as restrições, é necessário observar os excessos	 em cada nó. Como? Supondo que Y
representa uma parte de N e x um �luxo, chamaremos de Y’	o complemento de Y	(Y’	=	N-Y) e x(Y’,	Y) a soma dos
valores de x	no conjunto de arcos que entram em Y.	Analogamente, x(Y,	 Y’) é a soma dos valores de x	no
conjunto de arcos que saem de Y.	Desse modo, temos que o excesso	de x	em Y	é a diferença entre o que entra e
o que sai de Y:
x(Y’,	Y) - x(Y,	Y’).
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 4/25
1.1.1 Tipos de problemas de fluxo
O �luxo em redes é aplicado para diversos tipos de problemas, mas seu uso mais comum é para problemas de
transporte, que visa minimizar o custo para o envio de algo da origem ao destino (função objetivo), mas que
vise satisfazer os limites de fornecimento e demanda, que em redes são as capacidades dos arcos (restrições).
O problema de transportes também pode solucionar problemas que não possuem nenhuma relação com
transportes, como: programação de estoque, controle de empregos, criação de cronograma de produção, entre
outros (TAHA, 2008).
Outro tipo de problema que pode ser solucionado com base no �luxo em redes é o de roteamento, em que os
designados são encaminhados para realizar tarefas e sua aplicação pode ser para designar um número de
pessoas para fazê-la, mas também pode ser aplicado a máquinas, carros e, até mesmo, os perı́odos que serão
destinados à realização de certa tarefa (HILLIER; LIEBERMAN, 2013).
VOCÊ QUER LER?
O professor Paulo Feo�iloff, da Universidade de São Paulo, desenvolveu uma apostila
que traz os conceitos tratados nesta unidade de forma mais teórica. E� possıv́el
complementar a literatura e os conhecimentos acerca de �luxos em redes e dos
problemas mais comuns sobre esse assunto. Essa apostila pode enriquecer os seus
conhecimentos e está disponıv́el no link:
https://www.ime.usp.br/~pf/�lows/mynotes/FluxoEmRedes.pdf.
1.2 Problema de transporte
De modo geral, o problema de transportes trata de determinar o custo mı́nimo para que seja realizado o envio
de um produto de algumas origens (fábricas) para seus destinos (centros de distribuição – CDs). Porém, não
basta minimizar o custo: deve-se respeitar que as fábricas não podem enviar uma quantidade maior de
mercadoria do que é capaz de produzir e os CDs não poder receber mais do que a sua demanda, por exemplo
(TAHA, 2008; ANDRADE, 2009; LACHTERMARCHER, 2016).
A representação geral de um problema de transportes pode ser demonstrada na rede da Figura a seguir, em que
há m	origens em n	destinos, sendo que as origens e os destinos estão representados por nós, já as rotas que
fazem a ligação entre as origens e os destinos são representadas pelos arcos (i,	 j). Os arcos apresentam as
seguintes informações: o custo de envio da mercadoria, por unidade (cij), e quantas unidades são enviadas
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 5/25
(xij). A quantidade que sai da origem i	é representada por ai e a demanda em no destino j	é bj. O problema deve
satisfazer as restrições de suprimento e demanda e determinar o �luxo xij que minimizará o custo total do
transporte.
Trocando em miúdos: temos que transportar o produto �inal de várias fábricas nas quais são produzidos para
vários CDs onde são necessários. Conhecendo o quanto cada fábrica pode produzir (ai), o quanto cada CD
precisa (bj) e o custo para transportar cada unidade produzida (cij), temos condição de de�inir quantas
unidades devem ser enviadas de cada fábrica para cada CD (xij), de modo a minimizar o custo desse envio.
1.2.1 Modelo linear do problema de transporte
A PL é aplicada para resolução de um problema de transportes, pois teremos uma variável de decisão (xij) que
determinará a quantidade a ser transportada de uma origem até o destino, teremos um objetivo, que é
minimizar o custo de transporte entre as origens até os destinos (cij), e temos as restrições para a realização
desse transporte. O exemplo a seguir, retirado da obra de Silva et	al.	(2010) nos ajudará a entender e montar o
PPL para problemas de transporte.
Veja a rede a seguir, quemostra as origens e as disponibilidades de produtos nessas origens (nós da esquerda)
e os destinos, bem como as necessidades de produtos desses destinos (nós da direita). A rede também nos
mostra o custo de transporte de cada unidade entre cada origem e cada destino.
Figura 1 - Rede geral para o problema de transportes.
Fonte: TAHA, 2008, p. 85.
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 6/25
A rede pode ser traduzida no simples quadro a seguir, onde temos as origens, os destinos, as disponibilidades
das origens e as necessidades dos destinos.
Como o objetivo é minimizar o custo de transporte, a função objetivo, para esse caso, é descrita da seguinte
forma:
Min C = 10X11 + 12X12 + 20X21 + 8X22 + 6X31+ 15X32
Sendo que 10X11, por exemplo, é o custo do transporte unitário da origem 1 ao destino 1 multiplicado pela
quantidade a ser transportada da origem 1 ao destino 1.
Figura 2 - Exemplo de rede para o problema de transportes.
Fonte: SILVA et al., 2010, p. 96.
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 7/25
As restrições para esse problema devem obedecer às quantidades retiradas em cada origem, que devem ser
iguais às suas disponibilidades. Além disso, as quantidades que chegarão a cada destino devem ser iguais às
suas necessidades. Desse modo, as restrições podem ser esquematizadas da seguinte forma:
O modelo para esse problema de transportes �ica do seguinte modo:
Min C = 10X11 + 12X12 + 20X21 + 8X22 + 6X31+ 15X32
Sujeito a:
No caso estudado, podemos dizer que o sistema está em equilı́brio, porque a disponibilidade das origens é
exatamente igual à necessidade nos destinos. Quando não há produtos su�icientes para satisfazer à demanda,
temos um sistema não equilibrado e, para resolvê-lo, devemos adicionar uma origem �ictı́cia; analogamente,
quando há mais disponibilidade nas origens do que demanda nos destinos, podemos criar um destino �ictı́cio.
Os custos de cada unidade acrescentada nas origens ou nos destinos �ictı́cios são zero e as quantidades que
são transportadas de origens �ictı́cias �icam faltando nos destinos, enquanto as quantidades transportadas
para destinos �ictı́cios �icam, na verdade, armazenadas nas origens. Entenderemos como isso funciona
observando o quadro a seguir, que mostra um sistema não equilibrado.
VAMOS PRATICAR?
Com base no conceito de origem e destino �ictıćio, observe a seguinte sit
determine se uma origem ou um destino �ictıćio deve ser adicionado.
Fornecimento: A1 = 10, A2 = 5, A3 = 4, A4 = 6.
Demanda: B1 = 10, B2 = 5, B3 = 7, B4 = 9.
Lembre-se de justi�icar sua resposta.
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 8/25
Para que o sistema �ique novamente em equilı́brio, criaremos uma origem �ictı́cia, que receberá a diferença
entre necessidade e disponibilidade: 95-90 = 5. O quadro desse sistema em equilı́brio �ica da seguinte forma:
Uma possı́vel solução para esse problema é mostrada no quadro a seguir, no qual os valores nas células
representam as unidades transportadas de cada origem para cada destino.
Observando o quadro, é possı́vel notar que todas as disponibilidades foram enviadas para os destinos e todas
as necessidades foram recebidas das origens. Com essa solução, os valores XA2 =1 e XA3 = 4 não chegam aos
destinos, pois partiram de uma origem �ictı́cia, criada apenas para equilibrar o sistema, portanto o destino 2
recebe apenas 44 unidades, e o destino 3 apenas 11.
1.2.2 O algoritmo dos transportes
Como já dito, o problema de transportes é um PPL. O procedimento para sua solução consiste em duas etapas:
a primeira é calculada a solução básica inicial, e a segunda é observado o critério da otimalidade.
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 9/25
A solução básica inicial é constituı́da por um conjunto de valores que determina a quantidade a ser
transportada e deve obedecer às seguintes condições: satisfazer as restrições de origem e destino e não
apresentar circuitos entre as variáveis básicas (não deve haver uma poligonal fechada ligando variáveis
básicas). Para encontrar a solução básica, podemos utilizar dois métodos: o método do canto noroeste e o
método das penalidades.
1º	método	(canto	noroeste): a partir da célula superior esquerda, devemos transportar o máximo possı́vel
da origem ao destino, de forma que a linha e a coluna correspondentes a essa célula �iquem iguais a zero. O
próximo transporte terá como objetivo zerar a coluna e a linha da célula mais próxima à anterior (à direita ou
abaixo) (ANDRADE, 2009).
Exemplo:	encontre a solução básica inicial do seguinte quadro, que representa um problema de transportes e
que já conta com uma origem �ictı́cia.
No primeiro transporte, devemos enviar o máximo de unidades para zerar as disponibilidades e as
necessidades (linhas e colunas). O primeiro transporte está representado no quadro a seguir.
VOCÊ SABIA?
O problema de transporte também pode ser resolvido pelo método Simplex, mas,
por ser um tipo especial de PPL, pode ser solucionado utilizando cálculos
simpli�icados, porém contendo as mesmas fases do Simplex. Todavia, se você
quiser modelar o PPL e resolver pelo Simplex, a solução ótima também será
encontrada.
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 10/25
Note que o máximo que poderia ser enviado no primeiro transporte, obedecendo à regra do canto noroeste,
eram 18 unidades, que fez com que o valor da coluna 1 fosse zerado e a linha 1 passou a ter o valor 2. Os
demais transportes serão apresentados a seguir.
Os transportes realizados e mostrados no quadro foram os relacionados a seguir. Clique nos itens.
Transporte 1
X11 = 18 (disponibilidade da primeira linha = 2).
Transporte 2
X12 = 2 (disponibilidade da primeira linha = 0,
disponibilidade da segunda coluna = 38).
Transporte 3
X22 = 30 (disponibilidade da segunda linha = 0,
disponibilidade da segunda coluna = 8).
•
•
•
•
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 11/25
Transporte 4
X32 = 8 (disponibilidade da terceira linha = 12,
disponibilidade da segunda coluna = 0).
Transporte 5
X33 = 12 (disponibilidade da terceira linha = 0,
disponibilidade da terceira coluna = 15).
Transporte 6
X43 = 15 (disponibilidade da quarta linha = 0,
disponibilidade da terceira coluna= 0).
As variáveis mostram as quantidades que devem ser enviadas das origens aos destinos, de forma que as
restrições de disponibilidade e necessidade fossem cumpridas.
2º	método	das	penalidades:	tem como objetivo fazer o transporte na linha ou coluna que apresente a maior
penalidade (diferença entre as células de menor custo em cada linha ou coluna). Fazendo o transporte na
célula de menor custo, esse método consegue garantir que não haja aumento de custo igual à penalidade
•
•
VOCÊ QUER VER?
Para entender melhor como funciona o método do canto noroeste para encontrar a
solução inicial de um problema de transportes, assista à aula do professor Matusalém.
Essa aula é bem rápida e nela o professor explica os passos apresentados aqui de
forma bem dinâmica para um problema semelhante (MARTINS, 2014). Disponıv́el em:
https://www.youtube.com/watch?v=4SSacL3ATuY (https://www.youtube.com/watch?
v=4SSacL3ATuY)
https://www.youtube.com/watch?v=4SSacL3ATuY
https://www.youtube.com/watch?v=4SSacL3ATuY
https://www.youtube.com/watch?v=4SSacL3ATuY
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html12/25
(ANDRADE, 2009).
Clique nos itens e veja as etapas para concretização desse método.
CASO
Determine a solução inicial utilizando o método das penalidades para o seguinte
problema de transportes já modelado como um PPL:
MinC = 5X11 + 3X12 + 2X21 + 1X22
Sujeito a:
1º	passo
2º	passo
Calcule a penalidade para cada linha e para cada coluna e escolha a
linha ou coluna que tenha a maior penalidade (em caso de empate,
escolha arbitrariamente).
Eleja a célula de menor custo unitário e transporte a maior
quantidade possı́vel, de modo a zerar a linha ou a coluna dessa
célula. Elimine a linha ou a coluna zerada.
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 13/25
Realizaremos um exemplo prático para entender melhor esse método, com base no seguinte quadro, que
apresenta um problema de transporte.
Transporte	1:	calcule a penalidade para cada linha e para cada coluna e escolha a maior.
Agora, realizaremos o transporte da maior quantidade possı́vel na célula com o menor custo, de modo a zerar
a linha ou a coluna:
3º	passo
Retorne ao primeiro item até que todas as linhas e todas as colunas
tenham sido zeradas.
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 14/25
A linha 4 teve sua disponibilidade zerada, portanto será eliminada e seguiremos com o segundo transporte.
Transporte	2:	escolha o da maior penalidade:
Transporte na célula com menor custo:
A coluna 1 teve sua disponibilidade zerada e será eliminada. Os demais transportes serão realizados do
mesmo modo e, ao �inal, a solução inicial usando o método das penalidades �icará da seguinte forma:
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 15/25
Vejamos,	agora,	o	critério	da	otimalidade.
1.2.3 Critério da otimalidade
Assim como em um PPL comum, resolvido com o auxı́lio do método Simplex, um problema de transporte
deve ser veri�icado para observar se a solução inicial pode ser melhorada. Isso se faz, analogamente ao
Simplex, observando os coe�icientes das variáveis não básicas (VNB) na função objetivo. Para tanto, é
necessário escrever a função objetivo nos termos das VNB, sendo que elas devem ser todas positivas, pois,
enquanto existirem variáveis negativas, signi�ica que o sistema ainda pode ser melhorado. Melhorar o sistema
consiste em:
entrar com uma VNB;
tirar uma variável básica (VB) para que a VNB entre.
Realizando esse processo, necessitamos agora passar por algumas etapas que serão explicadas uma a uma,
como base no exemplo retirado da obra de Silva et	al.,	(2010, p. 105).
Exemplo:	calcule o plano de transporte de menor custo para o problema que está representado no quadro a
seguir.
Podemos perceber que o sistema está em equilı́brio, portanto podemos calcular a solução	básica	inicial. Pelo
método do canto noroeste, essa solução �ica da seguinte forma:
•
•
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 16/25
No critério	da	otimalidade, devemos primeiramente saber se uma VNB pode ser melhorada; para isso, seu
coe�iciente deve ser negativo. Sabendo que o coe�iciente de uma VB é 0, multiplicaremos cada restrição de
linha por -Ui e cada restrição de coluna por -Vj,	 somaremos às variáveis de custo da função objetivo e
igualaremos a zero, que é o coe�iciente de uma VB. A solução do sistema pode ser obtida atribuindo um valor
arbitrário para uma das incógnitas (Ui	e Vj) e calculando o valor das outras. Esses valores permitem calcular o
coe�iciente das VNB do seguinte modo:
Para VB: Cij-Ui-Vj,=	0.
Para VNB: Cij-Ui-Vj,=	coe�iciente.
Desse modo, temos:
Agora, temos sete variáveis e seis equações. Atribuiremos um valor arbitrário a uma das variáveis: U1 =0.
Substituindo o valor de U1, podemos encontrar o valor das outras variáveis:
V1 = 6;
V2 = 5;
U2 = 7;
U3 = 4;
V3 = 1;
U4 = 3.
Os coe�icientes das VNB serão calculados como mostrado abaixo:
A solução não é ótima, pois ainda há coe�icientes de VNB negativos. O próximo passo é entrar com a VNB que
tenha o maior valor negativo absoluto no sistema (X23) e montar um circuito de compensação entre as VB a
partir da variável que entra.
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 17/25
Esse circuito tem o objetivo de manter as restrições de linha e coluna e é feito partindo da variável que entra e
seguindo de maneira alternativa na direção da linha e da coluna subtraindo e somando o valor da entrada até o
retorno à variável de entrada. Para esse problema, o circuito pode ser visualizado no quadro abaixo.
A variável que entra deve ter o maior valor possı́vel para garantir que nenhuma VB se torne negativa, porém
nula. Para o exemplo que estamos tratando, a variável que entra chamado de β na tabela terá valor 2. Desse
modo, a solução passa a ser a seguinte:
Note que a VB X33 deixou o sistema, e agora a variável X23 que era uma VNB passou a ser uma VB. Feito tudo
isso, identi�icaremos se a solução é ótima ou se há VNB que pode ser melhorada, voltando ao primeiro passo,
que é encontrar os coe�icientes das novas VNB:
VOCÊ O CONHECE?
O problema de transporte foi estudado pela primeira vez entre os anos de 1941 e
1942 por Kantorovich e Koopmans. Esses holandeses estudaram esse tipo de
problema de forma independente e, para sua solução, utilizaram métodos geométricos.
E� importante ressaltar que Tjalling Charles Koopmans ajudou a desenvolver a teoria
da PL em 1939 e, por isso, ganhou o Prêmio Nobel de Economia.
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 18/25
Colocando U1 = 0, temos:
V1 = 6;
V2 = 5;
U2 = 7;
U3 = 4;
V3 = -6;
U4 = 10.
E os coe�icientes das VNB são:
A solução ainda não é ótima, e a VNB X42 entra no sistema, pois tem o maior coe�iciente negativo em termos
de valor absoluto. O circuito de compensação �ica da seguinte forma:
Note que o circuito não passa pelos valores que já estão ‘compensados’, ou seja, que já obedecem a uma
restrição de linha e de coluna. O valor da variável que entra (β) será 13, pois assim será possı́vel eliminar uma
VB ainda cumprindo as restrições. A nova solução �ica:
A variável X43 saiu do sistema para a entrada da variável X42, e agora é uma VNB. Voltaremos ao inı́cio e
identi�icaremos se a solução é ótima.
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 19/25
Atribuindo 0 a U1, temos:
V1 = 6;
V2 = 5;
U2 = 7;
U3 = 4;
V3 = -6;
U4 = 1.
Os coe�icientes das VNB �icam assim:
A variável X31 ainda possui coe�iciente negativo, mostrando que a solução ainda não é ótima, portanto, ela
entra no sistema. O circuito de compensação �ica da seguinte forma:
Agora teremos β = 8, para que o sistema seja capaz de anular uma VB e não torne nenhum valor negativo. A
solução �icará da seguinte forma:
Voltando à etapa inicial, observaremos se a solução é ótima com as novas VB:
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 20/25
Fazendo U1 = 0, temos:
V2 =5;
U2 = 7;
V3 = -6;
U3 = 4;
V1 = 3;
U4 = 1.
Os coe�icientes das VNB serão:
Essa solução é ótima, pois as VNB não possuem coe�icientes negativos que podem ser melhorados. A forma
ótima de transporte para esse problema �ica assim:
10 unidades da origem 1 ao destino 2;
5 unidades da origem 2 ao destino 2;
15 unidades da origem 2 ao destino 3;
8 unidades da origem 3 ao destino 1;
4 unidades da origem 3ao destino 2;
13 unidades da origem 4 ao destino 2.
O custo total desse transporte será: C = 5.10 + 12.5 + 6.15 + 7. 8+ 9.4 + 6.13 = 370.
1.3 Problemas de fluxo
Durante a resolução dos problemas de �luxo em redes, como o problema de transportes, alguns impedimentos
podem surgir, di�icultando os cálculos ou a aplicação dos algoritmos. Portanto, veremos alguns exemplos de
problemas de �luxo nesta seção e como resolvê-los.
1.3.1 O problema da degenerescência
Esse problema se trata de casos em que haja menos variáveis básicas do que o necessário para a solução do
problema, resultando em menos equações do que as desejadas. No algoritmo para problemas de transportes,
vimos que igualando os coe�icientes das VB a zero, o resultado é sempre uma variável a mais do que o
número de equações, porém o que fazer se tiverem duas ou três equações a menos do que o número de
variáveis?
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 21/25
Nesse caso, a solução é degenerada e não conseguimos encontrar um conjunto único de valores para U e V;
portanto, devemos criar variáveis básicas auxiliares das quais permitirão que o número de equações seja um a
menos do que o número de variáveis. Essas variáveis devem ter um valor muito próximo de zero, para que
não alterem as restrições de origem e destino, e elas não podem formar circuito com as variáveis básicas
originais do problema.
Exemplo:	o quadro abaixo apresenta a solução inicial de um problema retirado de Silva et	al.	(2010, p. 111):
Aplicando o teste da otimalidade, percebe-se que esse sistema possui cinco equações e sete variáveis, então
uma variável auxiliar (A) deve ser acrescentada em uma célula que não forme circuito com outras VB, da
seguinte forma:
O acréscimo da variável auxiliar A fez com que o sistema passasse a ter sete variáveis e seis equações, e o
problema continua a ser resolvido até encontrar a solução ótima.
1.3.2 O caso da maximização
Esse caso acontece em modelos de PL que possuem objetivo de maximização, mas também podem ser
tratados como problema de transportes. Um exemplo disso é um problema que busca maximizar os lucros
obtidos nas vendas de mercadorias compradas nas origens e comercializadas nos destinos.
Como o modelo de transportes minimiza o objetivo, os problemas de maximização devem transformar o
objetivo em minimização e isso pode ser feito multiplicando a função objetivo por -1 e, do mesmo modo,
trocando o sinal dos custos de transporte. Outra forma de resolver esse problema é trabalhar com um novo
modelo, em que os custos unitários de transporte sejam os complementos dos preços originais para algum
valor �ixo, que deve ser o maior valor da tabela original.
1.3.3 A impossibilidade de transporte
Pode acontecer casos em que não seja possı́vel realizar o transporte de uma origem para determinado destino.
Quando isso ocorrer, devemos colocar um sı́mbolo na célula em que o transporte está impossibilitado:
podemos chamar esse sı́mbolo de ∆, que representa um número muito grande. Assim, quando construirmos a
solução básica inicial, evitamos essa célula na qual o transporte está impossibilitado.
Já que o número ∆ é muito grande, ao calcular os coe�icientes das VNB, esse coe�iciente jamais será negativo e,
então, ela nunca se tornará uma VB, impedindo que o custo desse transporte seja contabilizado.
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 22/25
1.4 Problema de roteamento
Esse tipo de problema de �luxo em rede também pode ser chamado de problema de designação e resolve
situações em que exatamente uma unidade da origem deve ser enviada para o destino. Aplica-se, por exemplo,
a problemas em que um conjunto de funcionários deve ser enviado cada um para a execução de uma tarefa, ou
casos em que máquinas devem ser enviadas cada uma para um posto de trabalho. De acordo com Taha (2008),
algumas condições devem ser satisfeitas no problema de roteamento:
o número de designados e o número de tarefas é o mesmo e é representado por n;
a cada designado deve ser atribuı́da exatamente uma tarefa;
cada tarefa deve ser realizada exatamente por um designado;
há um custo associado a cada designado (i) executando uma tarefa (j).
O objetivo para esse problema é determinar como cada roteamento deve ser feito de forma a minimizar o
custo total. As três primeiras condições são bem restritivas e, se não forem satisfeitas no problema inicial,
podemos reformulá-lo para que satisfaça essas condições. Isso se faz criando designados e tarefas �ictı́cias
(HILLIER; LIEBERMAN, 2013).
1.4.1 Algoritmo para o problema de roteamento
O algoritmo para resolução do problema de roteamento deve seguir alguns passos para de�inir qual a melhor
tarefa para cada designado. Utilizaremos um exemplo retirado da obra de Silva et	 al. (2010, p. 123), para
explanar cada passo do algoritmo para resolução do problema.
VOCÊ O CONHECE?
Após utilizar a ferramenta Solver do Excel para solucionar um problema de
designação, o resultado encontrado permitiu a seguinte solução:
X1→Y3; X2→Y1; X3→Y2; X4→Y5; X5→Y4.
Custo total de transporte: 180.
Sabendo que o problema se tratava de um grupo de vendedores, cada um localizado
em uma cidade (X) que deveriam ser designados para realizar suas vendas, cada um
em outra cidade (Y), escreva a interpretação da solução encontrada.
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 23/25
Exemplo:	o quadro a seguir representa os custos de transporte de uma máquina dos locais de depósito (L)
para as fábricas onde deverão ser instaladas (F). Designe uma máquina para cada fábrica com o menor custo
total possı́vel.
O primeiro	passo para resolução do problema é subtrair de cada linha o seu menor valor e, em seguida,
fazer o mesmo procedimento com as colunas. Desse modo, cada linha e cada coluna deverá apresentar pelo
menos um elemento nulo, da seguinte forma:
Primeiro subtrair o menor valor de cada linha:
Depois subtrair o menor valor de cada coluna:
O segundo	 passo é designar origens para destinos em que aparece o elemento nulo. Cada designação
efetuada invalida os outros elementos nulos da linha e da coluna do elemento designado. Se a designação se
completa, o problema está resolvido. Para o exemplo tratado, a designação é realizada conforme a tabela a
seguir, em que os elementos marcados por retângulo foram designados, e os demais elementos nulos foram
riscados.
A designação ainda não está completa, pois não houve designação de L3 para F3, portanto um terceiro	passo
deve ser realizado e esse consiste em cobrir os zeros da tabela com o menor número de linhas possı́vel,
realizando as seguintes etapas:
marcar as linhas sem designação;
marcar as colunas com zeros nas linhas marcadas;
marcar as linhas com designação nas colunas marcadas;
voltar a marcar as colunas com zeros nas linhas marcadas até que não haja mais possibilidade de marcar
novas linhas ou colunas;
riscar as linhas não marcadas e as colunas marcadas.
Para o problema tratado, a etapa de cobertura dos zeros é representada no quadro abaixo:
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 24/25
Feito isso, o quarto	passo é escolher o menor	valor, entre todos os valores não cobertos, e subtrair esse
valor de todos os elementos do quadro. A reposição que deve ser realizada nas linhas e colunas que possuem
zeros, de modo que se impeça o aparecimento de custos negativos deve seguir os seguintes critérios:
os elementos não cobertos �icam diminuı́dos do valor escolhido;
os elementos nas interseções da cobertura �icam acrescentados do valor escolhido;
os demais elementos permanecemiguais.
No exemplo utilizado, o valor escolhido deve ser o 2, que é o menor dentre os não cobertos. As subtrações e
as reposições são representadas a seguir:
Feito isso, voltaremos ao segundo passo e faremos uma nova designação para identi�icar se cada origem
designará uma máquina para cada destino. O quadro a seguir mostra como essa designação �icará.
Agora, cada origem designou uma máquina para cada destino. A solução �inal é a seguinte:
L1 → F1
L2 →F2
L3 →F4
L4 →F3
O custo total desse transporte é: 10 + 12 + 13 + 15 = 50.
Síntese
Aprendemos nesta unidade a caracterizar o problema de �luxo em redes, quais os possı́veis problemas de
�luxo, entender como funciona e como soluciona o problema de transportes e o problema de roteamento.
Nesta unidade, você teve a oportunidade de:
entender como funciona o fluxo em redes e como ele pode ser
usado para resolver diversos problemas;
•
25/10/2023, 19:14 Pesquisa Operacional
https://codely-fmu-content.s3.amazonaws.com/Moodle/EAD/Conteudo/ENG_PESOPE_19/unidade_4/ebook/index.html 25/25
observar a notação matemática que caracteriza um problema de
fluxo;
aprender sobre quais os problemas mais comuns que podem ser
resolvidos com fluxos em rede;
aprender sobre o clássico problema de transporte, como funciona
sua aplicação e quais as etapas para a sua solução;
observar os impedimentos mais comuns à solução de um
problema de fluxo;
aprender sobre o problema de roteamento, vimos sua aplicação
nua situação prática e como solucionar esse tipo de problema.
•
•
•
•
•
Bibliografia
ANDRADE, E. L. Introdução	à	pesquisa	operacional: métodos e modelos para análise de decisões. 4. ed. Rio
de Janeiro: LTC, 2009.
FEOFILOFF, P. Fluxo	 em	 redes. São Paulo: USP, 2018. Disponı́vel em:
https://www.ime.usp.br/~pf/�lows/mynotes/FluxoEmRedes.pdf. Acesso em: 18 ago. 2019.
HILLIER, F. S.; LIEBERMAN, G. J. Introdução	à	pesquisa	operacional. 9. ed. São Paulo: McGraw-Hill, 2013.
LACHTERMACHER, G. Pesquisa	operacional	na	tomada	de	decisões. 5. ed. Rio de Janeiro: LTC, 2016.
MARTINS, M. V. Pesquisa	operacional: o problema do transporte – método do canto noroeste – exemplo 1.
31 de maio de 2014. Disponı́vel em: https://www.youtube.com/watch?v=4SSacL3ATuY. Acesso em: 18 ago.
2019.
SILVA, E. M. et	 al. Pesquisa	 operacional:	para os cursos de administração e engenharia. 4. ed. São Paulo:
Atlas, 2010.
TAHA, H. A. Pesquisa	operacional. 8. ed. São Paulo: Pearson, 2008.