USF EAD Unidade 4 Pesquisa e modelagem operacional

Prévia do material em texto

Livro - Texto 
 
Título do Livro: Pesquisa Operacional 
Autor: Washington Lemos 
Unidade n.º 4: Modelos de Transporte e Teoria das Filas 
 
Introdução 
Empresas precisam abastar e serem abastecidas por fornecedores, 
definir qual a melhor rota a ser escolhida, quantos caminhões e a capacidade 
produtiva. Sistemas de softwares necessitam saber como fazer a informação ser 
acessada mais rapidamente. Redes de transporte público precisam definir a 
melhor malha rodoviária ou ferroviária para integrar bairros e cidades da forma 
mais econômica para sua construção. Processos de atendimento necessitam 
identificar se é economicamente viável ter mais atendentes ou se a fila existente 
é inevitável. Todas estas decisões envolvem processos que serão vistos nesta 
unidade. Muitos destes problemas podem ser modelados graficamente como 
problemas de rede, dentre eles os problemas de transporte. 
As formas de resolução neste caso começam envolvendo Programação 
Linear, mas vão além, envolvendo Teoria das Filas e Processos Estocásticos, e 
Cadeias de Markov. Entretanto tudo aqui apresentado está dentro do que 
chamamos de Pesquisa Operacional e Processos de Tomada de decisão. 
 
1. Redes e Modelo de transportes 
As aplicações da modelagem em rede são variadas e poderosas para 
resolução de uma série de problemas, com aplicações desde logística até 
computação. Estes problemas surgem em diferentes áreas do conhecimento e 
a representação em rede fornece uma ferramenta conceitual e visual tão 
poderosa para descrever como estruturas se relacionam que acabaram sendo 
usadas em praticamente todos os ramos do conhecimento humano (HILLIER, 
LIEBERMAN, 2010, p. 360). O processo de otimização de redes consiste em um 
dos mais importantes avanços da Pesquisa Operacional no final do século XX e 
início do XXI. Muitos destes problemas de rede são casos especiais de 
problemas de Programação Linear, como por exemplo o problema de transporte 
que veremos com mais detalhes a frente nesta unidade. 
 
Livro - Texto 
 
Há uma extensa aplicação e, consequentemente, uma infinidade de 
possibilidades de modelagem e resolução de problemas de rede. Estudaremos 
aqui três modelos de problemas de rede (caminho mínimo, fluxo máximo e 
problema da árvore de expansão mínima), além do problema de transporte. 
É conveniente representar o que se entende por rede. Nada mais é do 
que um conjunto de nós (ou vértices) interligados por conectores denominados 
arcos (são as arestas ou ligações). Estes arcos podem ser direcionados (quando 
o fluxo é permitido em apenas uma direção e é representado por uma seta) ou 
não-direcionados (o fluxo é permitido em ambas as direções). A figura 1 
apresenta um exemplo desta estrutura de rede. Tradicionalmente os números 
indicados nos arcos (setas) são os recursos consumidos (tempo, distância, 
dinheiro etc), além disso o nó 1 seria chamado de origem (pois não possui 
nenhum arco entrando nele) e o nó 4 seria chamado de destino (pois não possui 
nenhum arco saindo dele). 
 
Figura 1 | Exemplo de uma rede 
 
Fonte: Autor 
 
1.1 O problema do caminho mais curto (Caminho Mínimo) 
Apesar de chamarmos o problema como Caminho Mínimo, é importante 
já inicialmente deixar claro que de acordo com as necessidades da situação real, 
pode ser que seja conveniente encontrar o caminho máximo e não mínimo, para 
isso sempre será possível fazer simples ajustes. Então, ao longo deste tópico, 
quando for dito “minimizar” considere que pode ser maximizar se assim o 
tomador de decisão julgar mais conveniente. 
 
 
Livro - Texto 
 
Este problema consiste em uma rede conectada e dois nós (pontos de 
“chagada” e/ou “saída” de especiais denominados origem e destino. Vamos 
verificar um exemplo e com base nele resolver um problema de caminho mínimo. 
 
Exemplo 1 – A pizza precisa chegar quente 
Uma pizzaria possui entrega em domicílio e se orgulha de ter o processo de 
entrega mais rápido da cidade, de modo que garante aos clientes que caso 
a pizza não chegue quente, não precisam pagar. Por isso a cidade é dividida 
em várias redes de atendimento de acordo com as distâncias da pizzaria, 
assim os entregadores podem sempre chegar ao destino com a pizza quente 
se escolherem o caminho correto. Um dos entregadores atende os bairros 
indicados na rede abaixo e precisa entregar uma pizza no destino indicado 
do cliente. Para fazer isso de modo seguro e sem correr, qual caminho ele 
deve escolher, se na figura 2 cada número nos arcos indica o tempo em 
minutos de deslocamento entre os bairros? 
 
Figura 2 | Distância entre os bairros 
 
Fonte: Autor 
 
 Há diferentes formas de se resolver este problema, e vamos apresentar 
aqui duas delas. Uma delas será exclusivamente gráfica e outra será por meio 
de modelagem em programação linear, como feito nas unidades anteriores. 
Vamos começar pelo método gráfico. 
 
 
 
Livro - Texto 
 
Algoritmo do Caminho Mínimo (etiquetagem) 
 Quando a rede não possui grande complexidade e um número muito 
grande de conexões, como é o caso do exemplo 1, podemos resolver o problema 
“na mão”, usando apenas a rede existente e uma forma de notação bem simples 
que chamaremos de “etiquetagem”. O nome se refere a uma “etiqueta” que seria 
colocada em cada nó, caso ele estivesse em um quadro o a pessoa que o resolve 
estivesse com uma série de etiquetas com as informações de qual é o nó 
antecedente “de onde veio” e qual é a distância acumulada até a origem. 
 
Um passo a passo desta forma de resolução seria: 
1. Marca-se o nó referente à origem como sendo antecessor de si próprio, 
indicando "0" em sua etiqueta e distância total acumulada "0". 
2. Identificar quais são os nós subsequentes, colocando uma etiqueta em cada 
um dos nós a partir da origem até o destino. 
3. Na etiqueta deve haver dois campos: um indicando o nó imediatamente 
antecessor através do qual o caminho é mais curto até a origem (nó “de onde 
vem”) e outro campo indicando a distância acumulada até a origem. 
4. Dentre todos as possibilidades para definir o nó “de onde vem”, seleciona-se 
aquele que irá resultar na menor distância acumulada (se o problema for de 
maximizar, então deve-se escolher a maior distância acumulada). 
5. Quando todos os nós tiverem etiquetados, deve-se analisar e definir a etiqueta 
que representa a solução ótima para o problema. 
6. Para se saber o caminho ótimo, deve-se “retornar” do destino para a origem, 
obedecendo as sinalizações das etiquetas que indicam sempre o nó “de onde 
vem”. 
 Vamos aplicar este passo a passo no nossos Exemplo 1. Devemos 
começar indicando a etiqueta da origem (1º passo), como na figura 3. A etiqueta 
é o que está entre colchetes [ _ ; _ ]. Observe que ara a origem sempre haverá 
a mesma etiqueta [0 ; 0], que significa que a antes dela não existe nenhum nó 
(nó zero) e que a distância acumulada até a origem é zero. 
 
 
 
 
Livro - Texto 
 
Figura 3 | Colocando a primeira etiqueta na origem 
 
Fonte: Autor 
 
O 2º passo consiste em identificar os nós subsequentes à origem e ir 
colocando um a uma a etiqueta. No nosso exemplo vemos que os nós 
subsequentes são os nós 2, 3 e 4, e, portanto, serão eles a receberem as 
próximas etiquetas (não importa a ordem). Em seguida o 3º passo é colocar nas 
etiquetas as duas informações: o nó imediatamente antecessor através do qual 
o caminho é mais curto até a origem (nó “de onde vem”) e qual é a distância 
acumulada até a origem. Isso resultará na configuração indicada na figura 4. 
 
Figura 4 | Etiquetando os nós subsequente à origem 
 
Fonte: Autor 
 
 
Livro - Texto 
 
Observe que os nós 2, 3 e 4 agora possuem cada um uma etiqueta que 
indica a distância acumulada até a origem (segundo número na etiqueta) e qual 
é o nó pelo qual você deve passar para ter essa distância. Verifique no nó 4 que 
o 4º passo foi dado, pois para este nó temos 3 possiblidades: vir pelo nó 1, 2 ou3. Se vier pelo nó 1, o entregador irá percorrer 9 minutos. Se vier pelo nó 3, o 
entregador irá percorrer 11 minutos (6 minutos do nó 1 ao nó 3 e depois 4 
minutos do nó 3 para o nó 4). Caso o entregador venha pelo nó 2, ele irá 
percorrer 8 minutos e como este é o menor caminho, será ele o escolhido. Desta 
forma, para o nó 4 existe a etiqueta [2;8], isso significa que o no 3 está a 8 
minutos da origem e que este caminho até a origem passa pelo nó 2. Já para o 
nó 3, a etiqueta é [1;6] o que significa que este nó está a 6 minutos da origem e 
que este caminho passa pelo nó 1. Deve-se continuar etiquetando os nós que 
sobram, o que irá resultar na figura 5. Para o nó 5 há dois caminhos possíveis, 
um caminho vindo pelo nó 2, que resultará em uma distância acumulada de 11 
minutos até a origem (basta somar 8 da aresta entre 2 e 5 com o segundo valor 
da etiqueta existente no nó 2, que é 3). Outra possibilidade para chegar ao nó 5 
é passar pelo nó 4, o que resultará em uma distância acumulada até a origem 
de 10 minutos. Desta forma a escolha para o problema será passar pelo nó 4 e 
por isso a etiqueta do nó 5 fica [4;10]. 
 
Figura 5 | Todos os nós etiquetados 
 
Fonte: Autor 
 
Livro - Texto 
 
Desta forma podemos dar o 5º passo e etiquetar o nó 6. O procedimento 
é o mesmo, de modo que é melhor chegar em 6 passando pelo nó 5 e não pelo 
nó 3. Agora o 6º passo é “retornar” a partir do nó 6 (destino) para a origem, 
obedecendo as sinalizações das etiquetas que indicam sempre o nó “de onde 
vem”. Então veja que olhando o nó 6, a etiqueta indica que se deve passar pelo 
nó 5 (primeiro valor na etiqueta), chegando ao nó 5, observa-se na etiqueta dele 
que o melhor caminho passa pelo nó 4. O nó 4 indica que se deve passar pelo 
nó 2 e este por fim indica que se deve ir para o no 1. Então o caminho ótimo é: 
1 → 2 → 4 → 5 → 6. Além disso sabe-se que o temo mínimo que o entregador irá 
gastar para ir da origem até o destino será a soma de todos os valores pelos 
quais passou: 3 + 5 + 2 + 5 = 15 𝑚𝑖𝑛𝑢𝑡𝑜𝑠. Observe que este número pode ser 
encontrado sem necessidade de somar nada, apenas olhando para o nó de 
destino (nó 6), que indica a distância acumulada até a origem como sendo 15. 
 Desta maneira resolvemos o problema e já temos o caminho ótimo a ser 
percorrido e o tempos mínimo de deslocamento. Este problema, por ser tratar de 
um problema relativamente simples, com poucas ramificações na rede, não 
apresentou dificuldades para se etiquetar, porém muitas vezes isso não 
acontece e por isso iremos apresentar uma segunda ferramenta para resolução 
deste problema. 
 
Modelando como Programação Linear problemas do tipo Caminho Mínimo 
 Os problemas de caminho mínimo são também problemas que podem ser 
modelados exatamente como fizemos nas unidades anteriores, usando 
Programação Linear, e, portanto, podemos usar tanto o MS Solver como o 
Simplex para resolvê-los. Aqui vamos mostrar como é sua modelagem e resolver 
um exemplo usando o MS Solver. Para tornar a explicação mais didática, vamos 
partir de um exemplo. 
Exemplo 2 – Reduzindo custo de uma transportadora 
Uma empresa de transportes precisa oferecer uma cotação para um 
transporte que a leva de um porto determinado como origem até um cliente. 
Como nunca fez este trajeto, a transportadora necessita analisar sua melhor 
opção de modo que consiga atender o cliente pelo menor preço possível, 
 
Livro - Texto 
 
pois é estrategicamente muito importante prestar este serviço, para agradar 
a empresa contratante. A figura 6 indica todas as opções de trajetórias para 
se levar a carga do porto para o cliente, nesta rede os nós indicam as 
cidades por onde se pode passar e os números nos arcos indicam o custo 
de transporte entre as cidades. Desta forma, determine qual é o melhor 
trajeto para que a transportadora minimize o custo total de transporte para 
esta entrega. 
 
Figura 6 | Distância entre os bairros 
 
Fonte: Autor 
A resolução de problemas como o do exemplo 2 pelo método da 
etiquetagem exigiria muito mais cuidado e atenção por parte do analista, e no 
mundo real os problemas costumam ser ainda mais complexos. Por isso é 
imprescindível que o estudante tenha acesso a outras ferramentas de resolução, 
e é isso que é mostrado neste tópico. Uma forma de se resolver problemas 
complexos de caminho mínimo é usando a modelagem de programação linear. 
Vamos então modelar este problema tal como fizemos nas unidades 
anteriores. Começaremos definindo as variáveis de decisão e este é o momento 
mais crítico desta modelagem. Atente que no caso do caminho mínimo trata-se 
de escolher qual é o caminho a ser percorrido e uma vez escolhido um arco, ele 
é percorrido integralmente, ou seja, considere por exemplo o arco entre o nó 1 e 
2, uma vez escolhido este nó obrigatoriamente a transportadora irá gastar R$ 60, 
não existe a possibilidade de se passar pelo arco entre 1 e 2 sem gastar este 
valor integralmente. A palavra integralmente aqui é importante. Perceba que 
então as variáveis de decisão precisam indicar se cada um dos arcos foi ou não 
 
Livro - Texto 
 
escolhidos, apenas isso. A variável de decisão não indica o quanto se gastou, 
pois isso será definido em função da escolha dos caminhos, a variável de 
decisão apenas diz se um arco foi usado ou não. Sendo assim, haverá uma 
variável de decisão para cada um dos arcos existentes na rede. Vamos nomear 
colocando nos índices de cada uma das variáveis de decisão o nó de onde sai e 
o nó para onde vai. 
 
𝑥12 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 1 𝑒 2 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
𝑥13 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 1 𝑒 3 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
𝑥14 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 1 𝑒 4 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
𝑥15 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 1 𝑒 5 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
𝑥26 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 2 𝑒 6 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
𝑥37 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 3 𝑒 7 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
𝑥48 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 4 𝑒 8 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
𝑥49 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 4 𝑒 9 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
𝑥410 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 4 𝑒 10 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
𝑥58 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 5 𝑒 8 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
𝑥67 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 6 𝑒 7 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
𝑥79 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 7 𝑒 9 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
𝑥810 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 8 𝑒 10 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
𝑥910 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 9 𝑒 10 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
𝑥911 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 9 𝑒 11 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
𝑥1011 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 10 𝑒 11 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
Como na rede existem 16 arcos, então precisa haver 16 variáveis de 
decisão. Como em muitos casos reais o número de variáveis é ainda maior, 
podendo chegar a dezenas de centenas, então muitas vezes optamos por 
escrever as variáveis de decisão desta forma. 
 
𝑥𝑖𝑗 = 𝑑𝑒𝑐𝑖𝑠ã𝑜 𝑠𝑒 𝑜 𝑐𝑎𝑚𝑖𝑛ℎ𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 𝑖 𝑒 𝑗 𝑓𝑜𝑖 𝑒𝑠𝑐𝑜𝑙ℎ𝑖𝑑𝑜 
 
Além disso outra informação é importante, atente que a variável de 
decisão apenas deve dizer se um arco foi ou não escolhido e não deve modificar 
 
Livro - Texto 
 
o valor gasto naquele deslocamento. A variável de decisão diz sim ou não, 
apenas isso. Em matemática, uma forma de dizer sim ou não é usar os números 
1 e zero. Ou seja, as variáveis de decisão devem obrigatoriamente assumirem 
os valores 1 ou zero, nenhumoutro. Por isso dizemos que são binárias. Vamos 
colocar isso no modelo adiante. 
Uma vez definidas as variáveis de decisão, vamos escrever a função 
objetivo, que neste caso refere-se ao valor total que a transportadora irá gastar 
para fazer o transporte. Para isso, vamos pensar juntos. Imagine que a 
transportadora escolheu passar pelos nós 1 e 2, isso significa que ela vai gastar 
R$ 60 neste deslocamento, se depois disso a transportadora for de 2 para 6 
(única possibilidade, uma vez que 2 tenha sido escolhido) então a transportador 
vai gastar mais R$ 95, o que significa que para ir de 1 até 6 ela gastou 60 + 95 
reais. Perceba que somamos todos os caminhos pelos quais a empresa passa, 
então vamos fazer isso para todos os arcos existentes e deixar que o Solver 
identifique a melhor solução. Desta forma, para a função objetivo seria: 
 
 
𝑍𝑚í𝑛 = 60𝑥12 + 107𝑥13 + 82𝑥14 + 79𝑥15 + 75𝑥26 + 45𝑥37 + 25𝑥48 +
35𝑥49 + 71𝑥410 + 39𝑥58 + 95𝑥67 + 50𝑥79 + 48𝑥810 + 37𝑥910 + 123𝑥911 + 98𝑥1011 
 
Não se assuste com o tamanho da função objetivo, você vai se acostumar 
com o tamanho dos modelos de rede, sempre grandes, mas sempre iguais. 
Então, mesmo que você tenha alguma dúvida agora, este modelo será sempre 
feito da mesma forma, identicamente. Ou seja, para problemas de caminho 
mínimo, a função objetivo será sempre todos os arcos somados multiplicados 
pela respectiva variável de decisão. Lembre-se de que a variável de decisão 
pode apenas assumir valores “zero” ou 1, e isso fará algo extraordinário. À 
medida que os variáveis de decisão foram assumindo valores, saberemos se um 
determinado caminho foi ou não usado e se ele foi usado a variável de decisão 
será 1 e consequentemente o valor será somado em Z, porém se o arco não foi 
escolhido, a variável de decisão assumirá o valor zero e ao multiplicarmos pela 
constante, tudo irá desaparecer (todo número multiplicado por zero é zero!). Esta 
é a genialidade por trás deste modelo. 
Eq. 1 
 
Livro - Texto 
 
Vamos ver agora como ficam as restrições. Para problemas de caminho 
mínimo haverá uma restrição para cada um dos nós. 
Para o nó 1, a origem, é importante termos a ideia de que a transportadora 
só pode escolher um único caminho para percorrer. É óbvia esta observação, 
mas muito importante. Podem existir vários caminhos ótimos, mas todos eles 
partem da premissa de que o caminhão só pode escolher um por vez. Isso 
significa que, para sair da origem (nó 1) o caminhão vai passar ou pelo arco 1-2, 
ou pelo arco 1-3, ou pelo arco 1-4 ou pelo 1-5. Não existe a possibilidade do 
caminhão passar simultaneamente (observe a palavra simultaneamente) por 
dois destes arcos. É necessário escolher um dos caminhos para sair da origem. 
Então podemos escrever: 
 
𝑥12 + 𝑥13 + 𝑥14 + 𝑥15 = 1 
 
Esta restrição obriga o modelo a escolher apenas uma das variáveis, pois, 
lembre-se: as variáveis de decisão só podem assumir valores zero ou 1 neste 
modelo. Se o caminho passar por 𝑥12 isso significa que 𝑥12 = 1, 
consequentemente todas as outras variáveis precisam ser iguais a zero, pois o 
somatório delas é igual a 1. Quando estiver modelando um problema de caminho 
mínimo, isso sempre será feito na origem! Sempre irá identificar a origem, somar 
todas as variáveis de decisão referente à origem e igualar a 1. 
Vamos agora fazer as restrições dos nós intermediários (sem ser Origem 
nem destino). Para estes nós é preciso observar que todo caminhão que chega 
obrigatoriamente precisa sair. Assim, não existe a possibilidade do caminhão 
passar pelo arco 1-2 e não passar pelo arco 2-6. Se ele chegou no nó 2, ele 
precisa sair do nó 2. Por isso podemos escrever: 
𝑥12 = 𝑥26 
 
Atente que para o nó 2, se o caminho 1-2 foi escolhido isso significa que 
𝑥12 é igual a 1, logo o caminhão chegou em 2 e precisa sair de 2. Como a única 
forma de sair de 2 é pelo 2-6, significa que 𝑥26 também será igual a 1. De outra 
forma, se o caminhão não passou por 1-2 então 𝑥12 = 𝑧𝑒𝑟𝑜 e consequentemente 
𝑥26 é zero. Mas, como vimos na unidade 1, é conveniente que não haja variáveis 
Eq. 2 
Eq. 3 
 
Livro - Texto 
 
de decisão do lado direito da restrição, por isso vamos rearranjar 𝑥26 passando 
para o lado esquerdo e alterando o sinal: 
𝑥12 − 𝑥26 = 0 
 
Deste exemplo podemos definir uma regra geral para todas as restrições 
referentes aos nós intermediários. A regra é: some sempre os nós que entram 
no nós e subtraia sempre os nós que saem. Vamos aplicar este conceito para o 
nó 3. Quem entra é 𝑥13 e quem sai é o 𝑥37. Desta forma teremos: 
𝑥13 − 𝑥37 = 0 
 
 Para o nó 4 temos entrando o 𝑥14 e saindo 𝑥48, 𝑥49 e 𝑥410. O que resulta 
em: 
𝑥14 − 𝑥48 − 𝑥49 − 𝑥410 = 0 
 
Para o nó 5 temos entrando 𝑥15 e saindo 𝑥58. 
𝑥15 − 𝑥58 = 0 
 
Para o nó 6 é 𝑥26 que entra e é 𝑥67 que sai. 
𝑥26 − 𝑥67 = 0 
 
No nó 7 temos 𝑥37 e 𝑥67 entrando, enquanto o 𝑥79 está saindo. 
𝑥37 + 𝑥67 − 𝑥79 = 0 
 
No nó 8 𝑥48 e 𝑥58 estão entrando e 𝑥810 está saindo. Então: 
𝑥48 + 𝑥58 − 𝑥810 = 0 
 
Em 9 temos 𝑥49 e 𝑥79 entrando e 𝑥910 e 𝑥911 saindo. 
𝑥49 + 𝑥79 − 𝑥910 − 𝑥911 = 0 
 
Por fim, para o nó 10 teremos 𝑥410, 𝑥810 e 𝑥910 entrando e 𝑥1011 saindo: 
𝑥410 + 𝑥810 + 𝑥910 − 𝑥1011 = 0 
 
Eq. 4 
Eq. 5 
Eq. 6 
Eq. 7 
Eq. 8 
Eq. 9 
Eq. 10 
Eq. 11 
Eq. 12 
 
Livro - Texto 
 
Até aqui temos a restrição da origem e todas as restrições dos nós 
intermediários. Resta definir a restrição do destino (nó 11). Para este nó, vale 
exatamente o mesmo raciocínio feito para a origem. Obrigatoriamente o 
caminhão deve passar por um dos nós que chega em 11 (9-11 ou 10-11), porém 
só pode chegar por um destes caminhos. Então podemos escrever: 
𝑥910 + 𝑥1011 = 1 
 
Em alguns livros ou literatura você poderá encontrar esta restrição em 
outro formato, multiplicando tudo por -1 (−𝑥910 − 𝑥1011 = −1). É uma forma 
também válida e isso não altera a modelagem. 
Sendo assim, podemos escrever o modelo completo para este problema 
de caminho mínimo, sendo: 
 
𝑍𝑚í𝑛 = 60𝑥12 + 107𝑥13 + 82𝑥14 + 79𝑥15 + 75𝑥26 + 45𝑥37 + 25𝑥48 + 35𝑥49
+ 71𝑥410 + 39𝑥58 + 95𝑥67 + 50𝑥79 + 48𝑥810 + 37𝑥910 + 123𝑥911
+ 98𝑥1011 
Sujeito a: 
𝑥12 + 𝑥13 + 𝑥14 + 𝑥15 = 1 
𝑥12 − 𝑥26 = 0 
𝑥13 − 𝑥37 = 0 
𝑥14 − 𝑥48 − 𝑥49 − 𝑥410 = 0 
𝑥15 − 𝑥58 = 0 
 
𝑥26 − 𝑥67 = 0 
𝑥37 + 𝑥67 − 𝑥79 = 0 
𝑥48 + 𝑥58 − 𝑥810 = 0 
𝑥49 + 𝑥79 − 𝑥910 − 𝑥911 = 0 
𝑥410 + 𝑥810 + 𝑥910 − 𝑥1011 = 0 
𝑥910 + 𝑥1011 = 1 
𝑥𝑖𝑗 = 𝑏𝑖𝑛á𝑟𝑖𝑜 (𝑧𝑒𝑟𝑜 𝑜𝑢 1) 
 
Resumindo como você deve modelar problemas de caminho mínimo: 
Eq. 13 
 
Livro - Texto 
 
1) Sempre terá na função objetivo o produto entre cada valor dos arcos 
e a variável de decisão. 
2) Sempre terá na origem e destino a soma de todas as variáveis de 
decisão que passam pela origem e destino e igualando a zero. 
3) Para os nós intermediários, sempre deve fazer: a soma dos nós que 
entram subtraídos os nós que entram iguala a zero. 
4) Sempre a variável de decisão será binária (zero ou 1). 
 
Uma vez que a modelagem esteja definida, para a resolução deste modelo 
podemos usar o MS Solver, da mesma forma que fizemos nas unidades 
anteriores. Na figura 7 apresentamos como o modelo foi transportado para o 
Excel, de modo que cada variável de decisão tenha uma coluna e casa linha da 
modelagem (função objetivo e restrição) tenha uma linha. 
 
Figura 7 | Modelagem do Exemplo 2 no Excel 
 
Fonte: Autor 
 
Ao colocar no Excel deve-se ter grande atenção para não trocar algum 
dos sinais, pois isso pode afetar toda a solução. Uma vez que esteja no Excel, 
pode-se usar o MS Solver disponível no Excel. 
 
 
 
 
 
 
Livro - Texto 
 
Figura 8 | Aplicação do MS Solver no Exemplo 2 no Excel 
 
Fonte: Autor 
 
O preenchimento do Solver é similar ao que já foi feito, na figura 8 
indicamos alguns lembretes. 
 
1) No primeiro campo preenchido deve constar a célulaonde se encontra a 
fórmula referente à função objetivo. Lembre-se: ali deve existir uma fórmula, 
e não digitar o número zero. O número zero aparece em decorrência da 
fórmula. Pode verificar as fórmulas usadas nas unidades anteriores. 
2) Não esqueça de que, tratando de caminho mínimo, neste problema deve-se 
escolher minimizar quando assim o problema afirmar. 
3) As variáveis de decisão devem ser selecionadas, na única linha destacada 
da planilha em Excel. 
4) Não deixe de colocar entre as restrições, a restrição de binário. Para esta 
restrição você irá selecionar o campo no qual aparece o valor das variáveis 
de decisão e defini-las como binária (veja figura 9) 
5) Não esqueça de escolher simplex como algoritmo de otimização. 
 
 
 
Livro - Texto 
 
Figura 9 | Definindo as variáveis como Binárias no MS Solver no Exemplo 2 
 
 
Fonte: Autor 
 
Uma vez que todas as informações tenham sido colocadas no MS Solver 
e o mesmo seja executado, o resultado ótimo será encontrado. A figura 10 
apresenta esta solução. Na linha onde contam os valores das variáveis de 
decisão (linha 4 do Excel) pode-se verificar uma sucessão de números zeros e 
1. Onde há número zero significa que a solução ótima não contempla aquele 
arco, e onde há o número 1 representa que aquele arco é utilizado na solução 
ótima. Desta forma, a solução ótima é aquela que passa pelos arcos: 1-4, 4-10 
e 10-11. Ou seja, o caminho ótimo (mínimo) é 1 → 4 → 10 → 11. Então este é o 
caminho que deve ser escolhido pela transportadora. É prudente sempre 
analisar se o caminho realmente leva da origem até o destino (saindo do nó 1 e 
chegando ao nó 11). Se isso não acontecer é sinal de algum erro foi cometido e 
deve-se revisar o modelo e em seguida a planilha do Excel. 
 
Figura 10 | Solução do MS Solver para o Exemplo 2 
 
 
Fonte: Autor 
 
Livro - Texto 
 
Além disso, olhando ainda na figura 10 percebemos que o total a ser gasto 
pela transportadora será R$ 251 (valor que está na célula R5 da planilha), na 
linha da função objetivo. 
 
1.2 O problema do Fluxo Máximo 
 Muitas vezes nas empresas a principal preocupação é obter uma forma 
de fazer com que o máximo de quantidade de um item saia da de uma origem e 
chegue a um destino. Atente que isso é diferente da busca de um caminho 
mínimo (ou máximo), pois o desejo é que o máximo saia de uma origem e para 
isso é permitido que se utilizem vários caminhos simultaneamente, é como se 
fosse uma torneira ligada a uma rede de mangueiras de modo que a água passe 
por todas as mangueiras para abastecer um determinado reservatório. Vamos 
ver um exemplo desse tipo de problema. 
Exemplo 3 – Reduzindo custo de uma transportadora 
Uma refinaria de petróleo é abastecida por um sistema de oleoduto que 
transporta petróleo desde o reservatório. Este sistema é composto por 
tubulações que possuem limites de sua capacidade de transporte de óleo 
bruto por hora. A rede desenhada abaixo representa toda a tubulação bem 
como as capacidades de cada uma das tubulações (em milhares de litros 
por hora). Determine qual é o máximo de óleo bruto que chega na refinaria 
por hora bem como quais as tubulações utilizadas. 
Figura 11 | Rede de distribuição de óleo bruto 
 
Livro - Texto 
 
 
Fonte: Autor 
 
 
Para resolvermos este problema podemos usar também a modelagem em 
programação linear. A modelagem ficará parecida com a feita para o caminho 
mínimo e muitos dos conceitos lá usado serão úteis aqui, entretanto há 
diferenças importantes, e a primeira delas é sobre o significado das variáveis de 
decisão. Todo problema de Fluxo Máximo necessita definir o quanto será usado 
de capacidade de cada um dos arcos, ou seja, para o nosso exemplo, se a 
tubulação 1-2 é utilizada, não necessariamente isso significa que toda a sua 
capacidade foi usada, pode ser que por ali passe não 3 mil litros por hora, mas 
sem 2 ou 2,5 litros por hora. Desta forma, as variáveis de decisão podem ser 
definidas como sendo: 
𝑥12 = 𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑𝑒 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑑𝑜 𝑎𝑟𝑐𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 1 𝑒 2 
𝑥13 = 𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑𝑒 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑑𝑜 𝑎𝑟𝑐𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 1 𝑒 3 
𝑥14 = 𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑𝑒 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑑𝑜 𝑎𝑟𝑐𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 1 𝑒 4 
𝑥15 = 𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑𝑒 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑑𝑜 𝑎𝑟𝑐𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 1 𝑒 5 
𝑥26 = 𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑𝑒 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑑𝑜 𝑎𝑟𝑐𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 2 𝑒 6 
𝑥36 = 𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑𝑒 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑑𝑜 𝑎𝑟𝑐𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 3 𝑒 6 
𝑥46 = 𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑𝑒 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑑𝑜 𝑎𝑟𝑐𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 4 𝑒 6 
𝑥47 = 𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑𝑒 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑑𝑜 𝑎𝑟𝑐𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 4 𝑒 7 
𝑥57 = 𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑𝑒 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑑𝑜 𝑎𝑟𝑐𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 5 𝑒 7 
 
Livro - Texto 
 
𝑥68 = 𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑𝑒 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑑𝑜 𝑎𝑟𝑐𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 6 𝑒 8 
𝑥78 = 𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑𝑒 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑑𝑜 𝑎𝑟𝑐𝑜 𝑒𝑛𝑡𝑟𝑒 𝑜𝑠 𝑛ó𝑠 7 𝑒 8 
 
Uma vez que tenhamos as variáveis de decisão, devemos modelar a 
função objetivo. O problema deseja maximizar o fluxo, ou seja, quer que chegue 
no destino o máximo de óleo bruto, então basta que o fluxo nos arcos que 
chegam ao destino seja maximizado para que toda a rede seja maximizada. 
𝑍𝑚á𝑥 = 𝑥68 + 𝑥78 
 
Para problemas de fluxo máximo, sempre deve-se maximizar a soma de 
todos os arcos que chegam no destino. Outra opção seria fazer o mesmo com 
os arcos que saem da origem, ou seja, maximizar a soma de todo os arcos que 
saem da origem, desta forma, uma função objetivo alternativa seria: 
𝑍𝑚á𝑥 = 𝑥12 + 𝑥13 + 𝑥14 + 𝑥15 
 
Ambas estão corretas e levarão ao mesmo resultado final. Pode-se 
escolher qual delas usar. Aqui usaremos sempre a maximização do destino. 
Para problemas de Fluxo Máximo não há nenhuma restrição para os nos 
de origem ou destino, e para os nós intermediários o procedimento de 
modelagem é exatamente o mesmo do caminho mínimo, pois é necessário 
garantir que absolutamente todo o fluxo que chegue ao nó também saia dele. 
Então, podemos considerar que quem entra em um nó é positivo e quem 
sai é negativo e que o fluxo deve ser zero. Para o nó 2, temos entrando 𝑥12 e 
quem sai é 𝑥26. Logo: 𝑥12 − 𝑥26 = 0 
Para os outros nós temos: 
 No nó 3 entra 𝑥13 e sai 𝑥36: 𝑥13 − 𝑥36 = 0 
 No nó 4 entra 𝑥14 e saem 𝑥46 e 𝑥47: 𝑥14 − 𝑥46 − 𝑥47 = 0 
 No nó 5 temos 𝑥15 entrando e 𝑥57 saindo: 𝑥15 − 𝑥57 = 0 
 No nó 6 temos entrando 𝑥26, 𝑥36 e 𝑥46 e saindo 𝑥68: 𝑥26 + 𝑥36 + 𝑥46 − 𝑥68 = 0 
 No nó 7 entra 𝑥47 e 𝑥57, e sai 𝑥78: 𝑥47 + 𝑥57 − 𝑥78 = 0 
 
 
Livro - Texto 
 
Desta forma todas as restrições de fluxo foram feitas, e garantimos que 
todo o fluxo que chega em um nó saia deste mesmo nó. Entretanto falta garantir 
que os limites de cada arco sejam respeitados. Então para cada arco devemos 
fazer uma restrição, por exemplo, a quantidade de fluxo no arco 1-2 deve ser no 
máximo 3 mil litros por hora, ou seja: 𝑥12 ≤ 3. Então listando a restrição de todos 
os arcos: 
 
𝑥12 ≤ 3 
𝑥13 ≤ 9 
𝑥14 ≤ 6 
𝑥15 ≤ 6 
𝑥26 ≤ 9 
𝑥36 ≤ 9 
𝑥46 ≤ 8 
𝑥47 ≤ 8 
𝑥57 ≤ 2 
𝑥68 ≤ 13 
𝑥78 ≤ 20 
 
 Com isso temos o modelo completo do problema de fluxo máximo para o 
exemplo 3: 
 
𝑍𝑚á𝑥 = 𝑥68 + 𝑥78 
Sujeito a: 
 𝑥12 − 𝑥26 = 0 
𝑥13 − 𝑥36 = 0 
𝑥14 − 𝑥46 − 𝑥47 = 0 
𝑥15 − 𝑥57 = 0 
𝑥26 + 𝑥36 + 𝑥46 − 𝑥68 = 0 
𝑥47 + 𝑥57 − 𝑥78 = 0 
𝑥12 ≤ 3 
𝑥13 ≤ 9 
 
Livro - Texto 
 
𝑥14 ≤ 6 
𝑥15 ≤ 6 
𝑥26 ≤ 9 
𝑥36 ≤ 9 
𝑥46 ≤ 8 
𝑥47 ≤ 8 
𝑥57 ≤ 2 
𝑥68 ≤ 13 
𝑥78 ≤ 20 
 
𝑥𝑖𝑗 ≥ 0 
 
 A resolução deste modelo pode ser feita usando o MS Solver, e para isso 
a primeira coisa a ser feita é transferir o modelo para o Excel, como está na figura 
12. 
 
Figura 12 | Modelagem do Fluxo Máximo no Excel 
 
Fonte: Autor 
 
 
Livro - Texto 
 
Para cada coluna foi colocada uma variávelde decisão, e cada restrição 
tem uma linha, inclusive as restrições que limitam o fluxo de cada arco. 
 
Figura 13 | Preenchendo o Solver para o Fluxo Máximo 
 
Fonte: Autor 
 
Em seguida, deve-se colocar as informações no Solver, de modo que na 
figura 13, no campo 1 tenha a célula na qual está a fórmula referente à função 
objetivo (Célula M5). Em 2 deve contar todas as células abaixo das variáveis de 
decisão. Em 3 devem constar as restrições, que podem ser colocadas uma a 
uma ou em dois blocos, um bloco com todas as restrições que possuem o sinal 
= e outro bloco com todas as restrições de sinal ≤. Atente que no caso do fluxo 
máximo, não há restrições sobre variáveis binárias, pois elas podem assumir 
qualquer valor desde que atendida as restrições, não necessitando serem 
binárias. No campo 4 deve-se escolher o método de resolução LP Simplex. 
 
 
 
 
 
 
 
 
Livro - Texto 
 
Figura 14 | Solução ótima para o Exemplo 3 
 
 
Fonte: Autor 
 
 O resultado ótimo para o exemplo 3 pode ser visto na solução proposta 
pelo solver na figura 14. Na linha 4 estão as capacidades utilizadas para cada 
um dos arcos. Por exemplo, para o arco 1-3, a capacidade máxima era 3 e de 
fato foi utilizada toda a capacidade disponível, porém para o arco 1-5, a 
capacidade máxima é de 6 mil litros por segundo, porém na solução ótima serão 
utilizados apenas 2 mil litros por segundo. Desta forma o analista pode verificar 
onde há capacidade ociosa e onde está no limite. Além disso, na célula M5, está 
indicado que o fluxo máximo que chegará até a refinaria será de 20 mil litros por 
hora. Desta forma, todas as perguntas do problema do exemplo 3 foram 
respondidas. 
 
1.3 O problema da Árvore de Expansão Mínima 
Um tipo de problema frequente nas empresas e nos processos de decisão 
é quando há a necessidade de se construir uma rede de distribuição ou 
transporte. A construção de um metrô, a definição das linhas de ônibus urbano 
ou a estrutura de uma rede de ar-condicionado, todos estes desafios podem ser 
transformados em um problema denominado Árvore de Expansão Mínima. 
 
Livro - Texto 
 
Convém diferenciar este caso do Problema do Caminho Mínimo. No Problema 
do Caminho Mínimo o objetivo é encontrar um caminho entre a origem e o 
destino, que não necessariamente necessita passar por todos os nós. No caso 
da Árvore de Expansão Mínima o objetivo é criar uma rede de modo que todos 
os nós estejam integrados à rede. 
Neste tipo de problema, são fornecidos os nós mas não as ligações, ao 
invés disso são fornecidas as ligações em potencial e a quantidade de recursos 
que aquele arco consumirá caso seja construído. O objetivo é que ao escolher 
os arcos que serão de fato utilizados ou construídos, uma rede seja formada 
possibilitando integrar todos os nós, com o mínimo possível de recursos. Vamos 
mostrar como resolver utilizando um exemplo. 
Exemplo 4 – Reduzindo custo de uma transportadora 
Uma prefeitura deseja melhorar a interligação entre sete bairros de um 
determinado distrito, porém os recursos são escassos. Para contornar o 
limite de recursos financeiros, os gestores municipais decidiram que vão 
asfaltar e melhorar as estradas sem que nenhum dos bairros seja 
especialmente beneficiado e por isso desejam uma decisão técnica, porém 
as estradas a serem construídas devem interligar todos os bairros a uma 
rede. Quais devem ser as estradas a serem construídas e qual o mínimo de 
quilômetros de estradas a serem construídas, sabendo-se que a figura 15 
indica os quilômetros entre os bairros considerando todas as potencialidades 
de estradas? 
Figura 15 | Rede de distribuição de óleo bruto 
 
Fonte: Autor 
 
Livro - Texto 
 
O algoritmo de resolução do problema da Árvore de Expansão Mínima é 
simples e pode ser feito manualmente. Vamos fazer o nosso tradicional passo 
a passo. 
1º Passo: Listar todos os arcos em ordem crescente de consumo de 
recursos. A escolha de como representar o arco (se 𝐴 − 𝐷 ou 𝐷 − 𝐴 por exemplo) 
é arbitrária. Caso haja empate, o desempate é arbitrário e isso não afetará o 
valor ótimo alcançado, mas sim apenas a solução ótima. Para o exemplo que 
estamos vendo os arcos ficam ordenados assim: 
 
𝐴 − 𝐷 = 3 
𝐵 − 𝐹 = 4 
𝐷 − 𝐹 = 5 
𝐸 − 𝐺 = 5 
𝐶 − 𝐺 = 6 
𝐴 − 𝐵 = 7 
𝐶 − 𝐸 = 7 
𝐷 − 𝐸 = 7 
𝐴 − 𝐶 = 8 
𝐸 − 𝐹 = 9 
𝐵 − 𝐷 = 11 
2º Passo: Fazer as ligações dos arcos na sequência apresentada, porém 
sem nunca fechar um polígono, ou seja, não pode haver um circuito fechado, 
não pode existir a possibilidade de sair de um determinado nó e retornar a este 
nó por um outro caminho. Por exemplo, na figura 16 apagamos todos os arcos e 
vamos reescrevendo os arcos na ordem de sua construção listada no passo 
anterior, nesta figura já se encontra desenhado o arco 𝐴 − 𝐷 = 3. 
 
 
 
 
 
 
 
 
Livro - Texto 
 
Figura 16 | Primeiro arco preenchido do Exemplo 4 
 
Fonte: Autor 
 
 Deve-se seguir no preenchimento seguindo o 2º passo, na ordem definida 
no 1º passo. Assim, na figura 17, vemos 𝐴 − 𝐷 = 3; 𝐵 − 𝐹 = 4; 𝐷 − 𝐹 = 5; 𝐸 −
𝐺 = 5 e 𝐶 − 𝐺 = 6. 
 
Figura 17 | Outros arcos preenchidos do Exemplo 4 
 
Fonte: Autor 
 Agora atente que, caso seja desenhado o próximo arco da sequência 
definida no 1º passo (𝐴 − 𝐵 = 7), haverá um polígono fechado, como mostrado 
na figura 18. Este arco não deve ser construído. 
 
 
 
 
Livro - Texto 
 
Figura 18 | Polígono fechado sendo construído 
 
Fonte: Autor 
 
 Desta forma, o arco deve ser pulado e ir para o seguinte, no caso seria 
𝐶 − 𝐸 = 7, que também irá formar um polígono, logo este arco também é 
descartado. Em seguida vem o arco 𝐷 − 𝐸 = 7 que é o último que pode ser 
construído sem que haja um polígono. Na figura 19 existe a solução final. 
 
Figura 19 | Solução Final da Árvore de Expansão Mínima 
 
Fonte: Autor 
 
Observe que qualquer arco adicional obrigatoriamente formaria um 
polígono e consequentemente seria um desperdício de recursos, pois o objetivo 
já foi alcançado: todos os bairros (nós) estão integrados através da rede, e 
sabemos exatamente quais estradas devem ser construídas. Para saber o total 
 
Livro - Texto 
 
de estradas a serem construídas, basta somar todos os arcos escolhidos, ou 
seja: 3+5+4+7+5+6= 30 km. 
A resposta a ser dada para os gestores municipais seria: construam as 
estradas 𝐴 − 𝐷, 𝐵 − 𝐹, 𝐷 − 𝐹, 𝐸 − 𝐺, 𝐶 − 𝐺 e 𝐷 − 𝐸 e o total de quilômetros 
construídos será de 30 km. 
 
1.4. Modelo de transporte 
 O modelo de transporte é uma forma singular dos problemas clássicos de 
programação linear vistos anteriormente. Apesar disso sua aplicação é vasta e, 
curiosamente, extrapola o contexto de transporte. É muito importante entender 
que é a estrutura matemática e da modelagem que configura um problema como 
sendo “um problema de transporte” e não seu contexto (HILLIER, LIEBERMAN, 
2010, p. 311). 
 O problema de transporte genérico se refere a qualquer necessidade de 
transportar qualquer grandeza de uma ou mais origens para um grupo de 
destinos, buscando sempre minimizar o consumo de recursos. É importante ficar 
claro que cada origem tem uma capacidade fixa da mesma forma que também 
são fixas as demandas dos destinos. Os problemas de transporte denominam-
se equilibrados quando a oferta e a demanda são iguais, isso significa que toda 
a carga disponível nas origens será transportada para os destinos. Há, porém a 
possibilidade, no mundo real, de oferta e demanda não se igualarem. Caso a 
oferta seja maior que a demanda, isso significa que o modelo a ser desenvolvido 
deve prever a sobra de entidades na origem. Caso a demanda seja maior que a 
oferta, o modelo deve permitir que alguma demanda não seja atendida. Estes 
pontos, apesar de óbvios, são muito importantes para evitar que ao se buscar 
uma solução, o mecanismo escolhido para resolução (o MS Solver por exemplo) 
indique que não existe solução.Sempre que isso acontecer, antes de qualquer 
coisa, sempre revise seu modelo para verificar se alguma destas considerações 
não foi ignorada de modo não intencional. 
 
 
 
 
 
Livro - Texto 
 
Exemplo 5 – Abastecendo as lojas 
Considere uma rede varejista com 3 lojas (A, B e C) que possuem demandas 
fixas semanais de caixas de roupas. Estas lojas podem ser abastecidas por 
dois Centros de Distribuição (CD) que possuem capacidades semanais 
limitadas. Os custos de transporte por unidade de caixas de roupas estão 
indicados na tabela a seguir, bem como as capacidades e demanda de cada 
loja e centro de distribuição. 
 
Tabela 1 | Mapa de abastecimento 
 Loja A Loja B Loja C Capacidade 
CD1 R$ 15 R$ 19 R$ 16 30 
CD2 R$ 24 R$ 31 R$ 21 60 
Demanda 20 30 50 
 
Determine qual é a solução ótima que minimize os custos de transporte 
desta rede varejista. 
 
 Este problema representa bem um caso de transporte, e poderia ser 
desenhado também como uma rede, como indicado na figura 20. 
 
Figura 20 | Rede de distribuição 
 
Fonte: Autor 
 
 
Livro - Texto 
 
 Vamos resolver utilizando a modelagem como programação linear e 
depois o MS Solver. Sendo assim, a primeira coisa para a modelagem é definir 
a variável de decisão. Para este problema a variável de decisão é quanto será 
transportado de cada origem para cada destino, ou seja, quantas caixas vão sair 
do CD 1 e chegar até a loja A por exemplo? 
𝑥1𝐴 = 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑡𝑟𝑎𝑛𝑠𝑝𝑜𝑟𝑡𝑎𝑑𝑎 𝑑𝑜 𝐶𝐷 1 𝑝𝑎𝑟𝑎 𝑎 𝑙𝑜𝑗𝑎 𝐴 
𝑥1𝐵 = 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑡𝑟𝑎𝑛𝑠𝑝𝑜𝑟𝑡𝑎𝑑𝑎 𝑑𝑜 𝐶𝐷 1 𝑝𝑎𝑟𝑎 𝑎 𝑙𝑜𝑗𝑎 𝐵 
𝑥1𝑐 = 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑡𝑟𝑎𝑛𝑠𝑝𝑜𝑟𝑡𝑎𝑑𝑎 𝑑𝑜 𝐶𝐷 1 𝑝𝑎𝑟𝑎 𝑎 𝑙𝑜𝑗𝑎 𝐶 
𝑥2𝐴 = 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑡𝑟𝑎𝑛𝑠𝑝𝑜𝑟𝑡𝑎𝑑𝑎 𝑑𝑜 𝐶𝐷 2 𝑝𝑎𝑟𝑎 𝑎 𝑙𝑜𝑗𝑎 𝐴 
𝑥2𝐵 = 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑡𝑟𝑎𝑛𝑠𝑝𝑜𝑟𝑡𝑎𝑑𝑎 𝑑𝑜 𝐶𝐷 2 𝑝𝑎𝑟𝑎 𝑎 𝑙𝑜𝑗𝑎 𝐵 
𝑥2𝐶 = 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑡𝑟𝑎𝑛𝑠𝑝𝑜𝑟𝑡𝑎𝑑𝑎 𝑑𝑜 𝐶𝐷 2 𝑝𝑎𝑟𝑎 𝑎 𝑙𝑜𝑗𝑎 𝐶 
 
 Uma vez que as variáveis de decisão estejam definidas, podemos 
modelar a função objetivo. A função Objetivo deve traduzir o custo total de 
transporte e o desejo é minimizá-la. 
𝑍𝑚í𝑛 = 15𝑥1𝐴 + 19𝑥1𝐵 + 16𝑥1𝐶 + 24𝑥2𝐴 + 31𝑥2𝐵 + 21𝑥2𝐶 
 
 Em seguida é o momento de se analisar se o problema está ou não 
equilibrado. Somando-se todas as demandas há a necessidade de 100 caixas 
semanais (20 + 30 + 50). Já do lado da oferta, existem 90 caixas disponíveis (30 
+ 60). Assim, podemos definir que não se trata de um problema equilibrado. E 
mais: a modelagem deve prever que a demanda não será plenamente atendida. 
Assim podemos escrever as restrições de demanda, dizendo que tudo o que 
chega em cada uma das lojas deve ser menor ou igual à demanda daquela loja 
(atente que só fazemos isso por sabemos analisando a oferta e a demanda que 
não há oferta suficiente para atender toda a demanda, então estamos prevendo 
demanda não atendida). 
𝑥1𝐴 + 𝑥2𝐴 ≤ 20 
𝑥1𝐵 + 𝑥2𝐵 ≤ 30 
𝑥1𝐶 + 𝑥2𝐶 ≤ 50 
 
Estas foram as restrições de demanda. Agora é preciso fazer as restrições 
de oferta. As restrições de oferta podem ser desenhadas sempre com o sinal 
 
Livro - Texto 
 
contrário ao sinal usado nas restrições de demanda (se o problema estiver 
equilibrado, permite-se também que todas as restrições tenham o mesmo sinal 
de igual). Desta forma, como sabemos que todas as ofertas serão consumidas, 
as restrições podem ser modeladas com sinal de igualdade (=) ou de maior ou 
igual (≥) (só não podem ter o sinal de menor ou igual (≤). 
𝑥1𝐴 + 𝑥1𝐵 + 𝑥1𝐶 ≥ 30 
𝑥2𝐴 + 𝑥2𝐵 + 𝑥2𝐶 ≥ 60 
 
Assim fechamos o modelo indicando que todas as variáveis de decisão 
devem ser não-negativas. Ou seja: 
𝑍𝑚í𝑛 = 15𝑥1𝐴 + 19𝑥1𝐵 + 16𝑥1𝐶 + 24𝑥2𝐴 + 31𝑥2𝐵 + 21𝑥2𝐶 
Sujeito a: 
𝑥1𝐴 + 𝑥2𝐴 ≤ 20 
𝑥1𝐵 + 𝑥2𝐵 ≤ 30 
𝑥1𝐶 + 𝑥2𝐶 ≤ 50 
𝑥1𝐴 + 𝑥1𝐵 + 𝑥1𝐶 ≥ 30 
𝑥2𝐴 + 𝑥2𝐵 + 𝑥2𝐶 ≥ 60 
𝑥𝑖𝑗 ≥ 0 
Agora podemos passar este modelo para o Excel como indicado na figura 
21, exatamente como feito em outros problemas já resolvidos. 
 
Figura 21 | Problema de Transporte – Transposição para Excel 
 
 
Fonte: Autor 
 
Livro - Texto 
 
 Na figura 22 observa-se o preenchimento do MS Solver, em 1 deve haver 
a célula correspondente à função objetivo (H5 no exemplo). Atenção para marcar 
a opção de minimizar. Em seguida marque no campo “Alternando células 
variáveis” (2) as células referentes aos valores das variáveis de decisão. EM 3 
coloque os dois blocos de restrição e não deixe de marcar LP Simplex em 4. 
 
Figura 22 | Problema de Transporte – Modelagem Solver 
 
Fonte: Autor 
 
Isso irá resultar na solução ótima proposta pelo MS Solver. Ao observar o 
campo H5 na figura 23, identifica-se que o valor mínimo de transporte será de 
R$ 1820 por semana e que a distribuição de transporte será dada por: 10 caixas 
sendo enviadas do CD 1 para a loja A; 20 caixas sendo enviadas do CD 1 para 
a loja B; nenhuma caixa sendo enviadas do CD 1 para a loja C; 10 caixas sendo 
enviadas do CD 2 para a loja A; nenhuma caixa sendo enviadas do CD 2 para a 
loja B; e por fim, 50 caixas sendo enviadas do CD 2 para a loja C. 
 
 
 
 
 
 
 
Livro - Texto 
 
 
Figura 23 | Problema de Transporte – Solução Ótima 
 
Fonte: Autor 
 
 
2. Introdução a processos estocásticos e Risco e incerteza. 
As situações empresariais estão sempre submetidas a um conjunto 
grande de variáveis que mudam de acordo com o tempo. Sempre que uma 
variável assume valores aleatórios ao longo do tempo, dizemos que ela está em 
um processo estocástico. Pode definir-se um Processo Estocástico como um 
conjunto de variáveis aleatórias indexadas a uma variável qualquer, geralmente 
tempo. É conveniente lembrar que qualquer sistema real opera sempre em 
ambientes nos quais há algum grau de incerteza, principalmente quando o 
sistema envolve ações humanas. Recorremos a Processos Estocásticos como 
uma forma de tratar quantitativamente estes fenômenos, aproveitando certas 
características de regularidade que eles apresentam para serem descritos por 
modelos probabilísticos. 
Os fenômenos estocásticos são de interesse por descreverem o 
comportamento de um sistema operando ao longo de algum período, oferecendo 
uma representação matemática de como o sistema evolui ao longo do tempo 
(HILLIER, LIEBERMAN, 2010, p. 713) 
 
 
. 
 
 
Livro - Texto 
 
3. Cadeias de Markov e Estudos de cadeias redutíveis. 
Sempre que um determinado evento futuro depende apenas do estado 
atua de um sistema, e não dos eventos passados, dizemos que estamos diante 
de uma cadeia de Markov, que é uma forma de processo estocástico. Existe uma 
forma de fazer as notações das cadeias de Markov. 
 
Exemplo 6 – Prevendo o tempo 
Considere que o tempo na cidade de Resende possa mudar de modo brusco 
de um dia para outro. As chances de amanhã o tempo estar seco (sem 
chuvas) é de 0,8 caso hoje esteja também seco. Entretanto, caso hoje esteja 
chovendo, a probabilidade de manhã estar chovendo é de 0,6. Como seria 
a formulação da cadeia de Markov? 
 
A notação usada pode parecer complicada, mas vamos traduzir. Este é 
um evento estocástico no qual a variável clima (𝑋) varia em função do tempo (t). 
 
𝑥𝑡 = {
0 → 𝑠𝑒 𝑜 𝑑𝑖𝑎 𝑡 𝑒𝑠𝑡𝑖𝑣𝑒𝑟 𝑠𝑒𝑐𝑜
1 → 𝑠𝑒 𝑜 𝑑𝑖𝑎 𝑡 𝑒𝑠𝑡𝑖𝑣𝑒𝑟 𝑐ℎ𝑜𝑣𝑒𝑛𝑑𝑜
 
 
Quando o clima estiver seco, chamaremos de estado zero. Quando o 
clima estiver chuvoso, o estado será chamado de 1. Então, se 𝑥1 = 1 significa 
que no dia 1 o dia estava chovendo, se 𝑥1 = 0 significa que no dia 1 está seco. 
Então, olhe só: 
Se 𝑃{𝑥2 = 0|𝑥1 = 0} = 0,8 isso significa que a probabilidade de que no dia 
2 esteja seco é de 0,8 caso no dia anterior (dia 1) esteja também seco. 
Se 𝑃{𝑥2 = 0|𝑥1 = 1} = 0,6 isso significa que a probabilidade de que no dia 
2 esteja seco é de 0,6 caso no dia anterior (dia 1) esteja chovendo. 
 
Podemos reescrever estas duas expressõesde modo genérico, 
substituindo um dia específico por um dia genérico t: 
𝑃{𝑥𝑡+1 = 0|𝑥𝑡 = 0} = 0,8 
𝑃{𝑥𝑡+1 = 0|𝑥𝑡 = 1} = 0,6 
 
 
Livro - Texto 
 
Uma notação comum de ser usada é aquela na qual os estados presentes 
e futuros aparecem na probabilidade, nesta ordem: 
𝑃00 = 𝑃{𝑥𝑡+1 = 0|𝑥𝑡 = 0} = 0,8 → Qual é a probabilidade, visto que o clima 
está seco hoje, de estar seco amanhã. 
𝑃10 = 𝑃{𝑥𝑡+1 = 0|𝑥𝑡 = 1} = 0,6 → Qual é a probabilidade, visto que o clima 
está chuvoso hoje, de estar seco amanhã. 
 
Visto que consideramos que só existem dois estados, ou está seco ou 
está chovendo, então as probabilidades devem ser iguais a 1 quando somadas. 
Ou seja, se hoje está seco e a probabilidade de amanhã estar seco é 0,8, então 
a probabilidade de que amanhã esteja chuvoso visto que hoje está seco é de 0,2 
(𝑃01). Da mesma forma, se hoje está chuvoso e a probabilidade de que amanhã 
esteja seco é de 0,6, logo a probabilidade de que amanhã esteja chuvoso é de 
0,4 (𝑃11). Com estas informações podemos criar o que chamamos de matriz de 
transição: 
 
𝑃 = [
𝑃00 𝑃01
𝑃10 𝑃11
] = [
0,8 0,2
0,6 0,4
] 
 
Esta notação deve ser lida como uma transição da linha para a coluna, ou 
seja, a probabilidade de sair do estado 0 para o estado 0 é de 0,8, ou seja, se 
hoje está seco então há 80% de chance de amanhã também estar seco. Se hoje 
está chuvoso, a chance de amanhã estar seco é de 0,6. 
 
4. Introdução à teoria das filas. 
Todos os processos gerenciais precisam enfrentar um dilema, o mesmo 
dilema que consta na primeira unidade deste livro: a escassez de recursos. A 
necessidade de se otimizar os recursos surge justamente do fato de estes 
recursos serem escassos e ser impossível disponibilizá-los indefinidamente. É 
neste momento que surgem as filas. Filas nada mais são do que entidades a 
espera de recursos para serem processadas. Embora nem sempre se perceba, 
em toda fila existe embutido um problema econômico que surge porque em 
qualquer fila existem 2 custos envolvidos: O Custo da Fila e o Custo do Serviço. 
 
Livro - Texto 
 
O custo de fila é muitas vezes difícil de ser calculado ou mensurado, 
porém ele sempre existirá. Quantos clientes você perderá se a fila de 
atendimento do estabelecimento crescer muito? Qual o valor monetário da 
quantidade de peças esperando para serem processadas? Qual o custo de se 
manter os produtos acabado em estoque, aguardando a transportadora? O 
Custo da fila é o quanto de recurso financeiro é consumido devido à existência 
da fila. 
Já o Custo do Serviço é o valor monetário gasto para atender as entidades 
que chegam para a fila. Quanto mais recursos existir, menor será a fila e 
consequentemente menor será o custo da fila, entretanto o Custo do Serviço 
será maior. Existe um momento no qual não é vantajoso reduzir a fila, pois o 
custo será proibitivo. 
O estudo da Teoria das Filas é abrangente, neste livro consideraremos 
um tipo especial de fila: 
 
• Tamanho da população: infinito 
A taxa de chegada de entidades na fila não afeta as taxas futuras, pois a 
população de entidades que entram na fila não afeta as chegadas futuras. 
 
• Tamanho permitido para a fila: infinito 
Consideraremos sempre que as filas podem crescer indefinidamente e que não 
existe um limite máximo para que alguma entidade entre na fila. 
 
• Fila: única 
Há sempre um único atendente ou recurso para atender as entidades. 
 
• Seleção para atendimento: FIFO 
Sempre que houver uma fila, a entidade que chega primeiro é atendida antes 
das outras que chegam depois. 
Denominaremos este modelo como sendo M/M/1. Este é o modelo mais 
simples de fila com tamanho população infinito, tamanho infinito, chegadas 
seguindo uma distribuição Poisson, duração do serviço seguindo a Exponencial, 
fila única no regime FIFO e 1 estação de serviço. (Santos, 2003, p. 83) 
 
Livro - Texto 
 
 Para o desenvolvimento das formulações, iremos considerar: 
λ ⇒ taxa de chegada 
μ ⇒ taxa de serviço 
∆t ⇒ unidade de tempo muito pequena 
n = número de unidades no sistema (inclui as da fila e a sendo servida). 
 
 Probabilidade de zero unidades no sistema, ou seja, a probabilidade do 
sistema estar vazio: 
 𝑃0 = 1 −
𝜆
𝜇
 
 Probabilidade de existirem n unidades no sistema: 
 𝑃𝑛 = 𝑃0 (
𝜆
𝜇
)
𝑛
 
 Probabilidade de existirem mais de k unidades no sistema: 
𝑃(𝑛 > 𝑘) = 𝑃0 (
𝜆
𝜇
)
𝑘+1
 
 Número médio (esperado) de unidades no sistema: 
𝐿 =
𝜆
𝜇 − 𝜆
 
 
 Número médio (esperado) de unidades na fila: 
𝐿𝑞 =
𝜆2
𝜇 (𝜇 − 𝜆)
 
 
 Tempo médio (esperado) que cada unidade permanece no sistema: 
𝑊 =
1
𝜇 − 𝜆
 
 
 Tempo médio (esperado) que cada unidade permanece na fila: 
𝑊𝑞 =
𝜆
𝜇(𝜇 − 𝜆)
 
 
 
Livro - Texto 
 
 Fator de utilização da estação de serviço: 
𝜌 =
𝜆
𝜇
 
 
Exemplo 7 – Atendentes em uma loja 
As pessoas chegam com uma duração média entre chegadas de 20 minutos 
a uma loja que possui um único atendente. O atendente gasta em média 15 
minutos com cada cliente. 
a) Qual a probabilidade de um cliente não ter que esperar para ser 
atendido? 
b) Qual é o número cliente esperado na fila da loja? 
c) Quanto tempo, em média, um cliente permanece na loja? 
d) Quanto tempo, em média, um cliente espera na fila? 
 
 A solução deste exemplo é feita exclusivamente utilizando as formulações 
indicadas. A primeira coisa a ser feita é identificar a taxa de chegadas e a taxa 
de serviço. 
𝜆 ⇒ taxa de chegada: se em cada 20 minutos chega 1 cliente, então em 60 
minutos (1 horas) chegam 3 clientes, assim: 𝜆 = 3 
𝜇 ⇒ taxa de serviço: Em 15 minutos um cliente é atendido, logo são atendidos 
4 clientes por hora. 𝜇 = 4 
 
a) Com estas informações podemos definir que a probabilidade de um cliente 
não ter que esperar para ser atendido é a mesma de o cliente chegar e não ter 
ninguém na loja, ou seja: P0 
𝑃0 = 1 −
𝜆
𝜇
= 1 −
3
4
= 0,25 = 25% 
b) O número cliente esperado na fila da loja é número médio de unidades na fila: 
𝐿𝑞 =
𝜆2
𝜇 (𝜇 − 𝜆)
=
32
4 (4 − 3)
= 2,25 𝑐𝑙𝑖𝑒𝑛𝑡𝑒𝑠 
 
c) O tempo, em média, um cliente permanece na loja é o tempo médio (esperado) 
que cada unidade permanece no sistema: 
 
Livro - Texto 
 
𝑊 =
1
𝜇 − 𝜆
=
1
4 − 3
= 1 ℎ𝑜𝑟𝑎 
 
d) O tempo, em média, um cliente espera na fila é dado por: 
𝑊𝑞 =
𝜆
𝜇(𝜇 − 𝜆)
=
3
4(4 − 3)
= 0,15 ℎ𝑜𝑟𝑎𝑠. 
 
 
Considerações finais 
 Nesta unidade foram abordados conceitos de inestimável valor prático, 
todas as ferramentas são usadas frequentemente nos processos de decisão de 
empresas e organizações. É conveniente indicar que, todas as ferramentas 
vistas devem ser utilizadas pelos estudantes quando estiverem em vivências 
práticas, sempre buscando levar para as organizações o estado da arte dos 
processos decisórios. 
 Os problemas de rede e transporte configuram uma ferramenta para 
solucionar situações que vão além das aplicações em transporte, sempre 
observe que o que caracteriza o problema é a modelagem e não seu contexto 
prático. 
 
Referências Bibliográficas 
HILLIER, Frederick S.; LIEBERMAN, Gerald J. Introdução à Pesquisa 
Operacional, 8a ed., New York: McGrawHill, 2010. 
 
LACHTERMACHER, Gerson. Pesquisa Operacional na Tomada de Decisões, 
3ª ed., Amsterdã: Editora Elsevier, 2007. 
 
LAWRENCE, John A.; PASTERNACK, Barry A. Applied Management Science: 
Modeling, Spreadsheet Analysis, and Communication for Decision Making, 2ª ed. 
Hoboken: Wiley, 2002. 
 
PASSOS, Eduardo José Pedreira Franco. Programação Linear como 
instrumento de Pesquisa Operacional, São Paulo: Editora Atlas, 2008. 
 
TAHA, Hamdy A. Pesquisa Operacional. 8º Edição. Londres: Editora Pearson, 
2008. 
 
SANTOS, Maurício Pereira, Pesquisa Operacional. 2003