Slide de aula - unidade II

Prévia do material em texto

Prof. Felipe Chagas
UNIDADE II
Programação Linear
 Existem ferramentas computacionais que permitem ao programador diminuir sua 
tarefa de aplicar o método simplex para problemas específicos e que, muitas 
vezes, requerem adequações para a forma padrão.
Em aplicações de tomada de decisão na vida real, o número de equações e variáveis 
de um problema de Programação Linear pode crescer rapidamente, inviabilizando o 
cálculo e a análise de maneira manual. Imagine, por exemplo, um problema com 15 
restrições e 30 variáveis:
Programação Linear Utilizando o Excel
C = n! = 30! = 155117520 Soluções 
m! (n – m)! 15! (30-15)!
n
m
 Ou seja, resolver um problema dessa proporção manualmente é totalmente 
inviável. Portanto, programas como Excel, MATLAB, AMPL, Lotus, entre outros, 
permitem a utilização de suplementos computacionais que possibilitam resolver 
problemas de Pesquisa Operacional muito mais facilmente.
 Aprenderemos a utilizar o Solver, que é um complemento do Excel, futuramente.
Programação Linear Utilizando o Excel
 Um ponto importante de ser dito, primeiramente, é que muitos problemas de 
programação linear apresentam uma certa similaridade em suas características de 
modelagem e resolução.
Para entender essas características, primeiramente vamos definir o conceito de rede: 
uma rede é definida como um conjunto ordenado de “nós” e “arcos”:
Aplicações da Pesquisa Operacional e Problemas Característicos
Aplicações da Pesquisa Operacional e Problemas Característicos
Fonte: Adaptado de: universoprojeto.com
Início
Fim
Atividade 
D
Atividade 
L
Atividade 
G
Atividade 
E
Atividade 
A
Atividade 
B
Atividade 
C
Atividade 
H
Atividade 
I
Atividade 
J
Atividade 
D
Atividade 
F
Atividade 
K
 O termo rede é similar ao conhecimento comum de que uma rede é uma entidade 
que conecta vários pontos através de fios, cabos etc. No nosso caso, iremos nos 
referir, por exemplo, à rede de transporte de produtos, pessoas, informações, 
atribuições de equipamentos, volume de produção etc. 
 Através do conceito de rede, podemos representar diferentes tipos de problemas 
de programação linear, permitindo-nos modelar tais problemas com maior 
facilidade e avançar um pouco mais na resolução desses problemas.
Aplicações da Pesquisa Operacional e Problemas Característicos
Algumas formulações típicas para problemas de rede em programação linear:
 Problemas de transporte;
 Problemas de atribuição;
 Problemas de transbordo;
 Problemas de fluxo máximo;
 Problemas de rota mínima.
Aplicações da Pesquisa Operacional e Problemas Característicos
 Problema de transporte: o problema de transporte é um caso particular de 
Programação Linear, no qual se deve minimizar o custo de uma série de pontos de 
destino, a partir de pontos de origem, levando-se em conta os diferentes custos de 
transporte para cada ponto de destino.
Aplicações da Pesquisa Operacional e Problemas Característicos
O1
D1
D2
O2
C1
C2
C3
C4
Fonte: Autoria própria
 Problema de atribuição: esse tipo de problema também é chamado de problema de 
designação ou de alocação. Nesse tipo de problema, os recursos são alocados às 
atividades na base de um a um, ou seja, uma atividade é alocada a um único 
recurso apenas.
Aplicações da Pesquisa Operacional e Problemas Característicos
A1 R1
A2
A3
A4
R2
R3
R4
A – Atividade
R – Recurso
Fonte: Autoria própria
 Problema de atribuição: esse tipo de problema também é chamado de problema de 
designação ou de alocação. Nesse tipo de problema, os recursos são alocados às 
atividades na base de um a um, ou seja, uma atividade é alocada a um único 
recurso apenas.
Aplicações da Pesquisa Operacional e Problemas Característicos
A1 R1
A2
A3
A4
R2
R3
R4
Fonte: Autoria própria
 Problema de transbordo: é uma variante do problema de transporte quando há 
pontos intermediários entre a origem e o destino. Portanto, o modelo contempla, 
além dos pontos de origem e destino, os pontos de transbordo, que podem 
representar, por exemplo, o estoque de determinado insumo.
Aplicações da Pesquisa Operacional e Problemas Característicos
o1
o3
o2
t1
t2
d1
d2
d3
O – Origem
D – Destino
T – Transbordo
Fonte: Autoria própria
 Problema de fluxo máximo: está relacionado com a capacidade máxima de fluxo 
entre dois nós de uma rede. Com isso, o objetivo num problema desse tipo é 
desenvolver um esquema de transporte que maximize a quantidade de material 
enviada entre dois pontos de origem e destino.
Aplicações da Pesquisa Operacional e Problemas Característicos
o1 d1
Qmáx
Fonte: Autoria própria
 Problema de rota mínima: identifica a rota que minimiza a distância entre dois nós. 
Nesse problema, cada arco tem um valor associado que representa a distância.
Aplicações da Pesquisa Operacional e Problemas Característicos
Fonte: Autoria própria.
A
B
C
D
E
F
G
H
12
2
4
6
3
5
8
7
5
3
 Em aplicações reais, o número de equações e variáveis dos modelos de 
programação linear obtidos, por exemplo, através dos diagramas de rede, cresce 
rapidamente, de modo que fica muito difícil a solução manual.
A utilização de planilhas no Excel permite uma maior flexibilidade na resolução de 
problemas de programação linear:
Estruturação no Excel
Estruturação no Excel
Fonte: Autoria própria.
Diretrizes para a construção de planilhas:
1. Organize primeiro os dados, depois construa o modelo. Essa organização pode 
ser feita inicialmente à mão numa folha à parte, para então ser transferida para 
a planilha;
2. Não introduza constantes numéricas nas células onde se encontram as variáveis. 
Dependendo da forma como a planilha será construída, a utilização de 
constantes pode afetar a confiabilidade e a flexibilidade do modelo;
3. Informações que são correlacionadas devem ser 
estruturadas com proximidade física;
Estruturação no Excel
Diretrizes para a construção de planilhas:
4. Fazer a leitura das informações da parte superior para a inferior, e do lado 
esquerdo para o direito;
5. Use cores, bordas e regiões de inserção de dados para distinguir variáveis 
de parâmetros;
6. Documente o modelo sempre que houver chances de 
falta de entendimento. 
Estruturação no Excel
Sugestão para a formatação da planilha no Excel:
Estruturação no Excel
Fonte: Autoria própria.
Esse será o local onde sairá a resposta otimizada da função objetivo.
Esse será o local onde as variáveis 
de decisão aparecerão após a 
solução no Solver (dados de saída).
Sugestão para a formatação da planilha no Excel:
Estruturação no Excel
Esse será o local onde são
inseridas as restrições do problema 
(lado esquerdo da restrição).
Fonte: Autoria própria
Sugestão para a formatação da planilha no Excel:
Estruturação no Excel
Esse é o local onde são 
inseridas as restrições do 
problema (lado direito).
Sinal da Restrição Lado direito
para cada ponto de destino.
Problema de Transporte
O1 D1
D2
O2
C1
C2
C3
C4
Fonte: Autoria própria
O transporte é composto por duas funções básicas:
1. Movimentação de produtos: independentemente do produto, se é matéria-prima, 
peça para montagem, estoque em processo ou o produto final, o transporte é 
necessário para movê-los para o próximo estágio do processo produtivo.
2. Armazenagem de produtos: função menos comum, porém também importante. 
Custos de carga e descarga devem ser levados em consideração na tomada de 
decisão de um certo bem.
Problema de Transporte
Vejamos como modelar um problema de transporte, a partir do seguinte exemplo:
“Uma empresa tem três fábricas e três depósitos para distribuição de seus produtos, 
os quais podem ser transportados para qualquer um dos depósitos. Os custos de 
transporte e capacidades, de cada fábrica para cada depósito, são dados nas 
tabelas a seguir. Conhecendo-se os custos associados, como é possível obter um 
modelo para o problema proposto?”
Modelagem de um Problema de Transporte
Depósito
Fábrica I II III Fábrica Produção Depósito Capacidade
1 8 15 3 1 120 I 150
2 5 10 9 2 80 II 70
3 6 12 10 3 80 III 60
Modelagem de um Problema de Transporte
 A tabela apresenta os custos unitários de transporte, de determinada fábrica para 
determinado depósito. Por exemplo: para transportar uma unidade de produto da 
fábrica 1 para o depósito 1, o valor é R$ 8; para transportar da fábrica 3 para o 
depósito 2, o valor é R$ 12, e assim sucessivamente...
 A tabela nos mostra a quantidade produzida ou oferta de cada fábrica, enquanto 
que a última mostra a capacidade máxima ou demanda de cada depósito. Por isso, 
o problema do transporte é, muitas vezes, interpretado como um problema de 
oferta e demanda.
 Vejamos o diagrama de rede...
Vamos estabelecer agora as variáveis de decisão, função objetivo e restrições:
Modelagem de um Problema de Transporte
x → Quantidade de produto transportada
MIN Z = 8x11 + 15x12 + 3x13 + 5x21 + 10x22 + 9x23 + 6x31 +12x32 + 10x33
x11 + x12 + x13 = 120
x21 + x22 + x23 = 80
x31 + x32 + x33 = 80
x11 + x21 + x31 = 150
x12 + x22 + x32 = 70
x13 + x23 + x33 = 60
xij > 0, para (i, j) = 1,2,3
Sujeito a:
 E, assim, realizamos a modelagem para um problema 
de transporte. A solução para o problema apresentado 
pode ser obtida através da aplicação manual do 
algoritmo do Simplex, mas aprenderemos nas aulas 
de laboratório como resolvê-lo utilizando o Solver.
Se possível, tente sempre montar o diagrama de rede 
do problema, de maneira a facilitar sua visão para 
desenvolver o problema:
Modelagem de um Problema de Transporte
Fonte: Autoria própria.
F1
F3
F2
D1
D2
D3
 Problema de atribuição: esse tipo de problema também é chamado de problema 
de designação ou de alocação. Nesse tipo de problema, os recursos são alocados 
às atividades na base de um a um, ou seja, uma atividade é alocada a um único 
recurso apenas.
Problema de Atribuição
Cenários possíveis Cenário otimizado
R1
R3
R2
A1
A2
A3
Recurso Atividade
R1
R3
R2
A1
A2
A3
Recurso Atividade
Fonte: Autoria própria.
 Num problema de atribuição, inicialmente, qualquer um dos recursos pode ficar 
atrelado a quaisquer uma das atividades (cenários possíveis). 
 Entretanto, por questões de pontuação, escore, preço, tempo, qualidade no 
serviço, entre outras variáveis, após a otimização, cada recurso ficará responsável 
pela atividade a qual ele apresenta o melhor desempenho, ou seja, os recursos 
são alocados na base um a um, no cenário otimizado.
Problema de Atribuição
Vejamos como modelar um problema de atribuição:
“Uma fábrica possui quatro máquinas, sendo que cada uma delas realiza uma única 
tarefa por vez para fabricar determinado produto. A tabela a seguir especifica o 
tempo gasto por cada máquina para realização de cada tarefa. Qual é a melhor 
alocação de trabalho para cada máquina, de maneira que o tempo de fabricação de 
uma unidade do produto seja mínimo?”
Modelando um Problema de Atribuição
Tarefa
Máquina T1 T2 T3 T4
I 14 5 8 7
II 2 12 6 5
III 7 8 3 9
IV 2 4 6 10
 No problema de atribuição, a variável de 
decisão é bem simples: usar a máquina para 
essa atividade ou não. Com isso, temos aqui 
uma decisão lógica, o que implica uma 
resposta do tipo sim ou não. No caso da 
programação linear, utilizamos os valores 
binários, 1 para o sim e 0 para o não.
Modelando um Problema de Atribuição
M1
M3
M2
T1
T2
T3
Máquina Tarefa
M4 T4
Fonte: Autoria própria.
No nosso exemplo, a variável de decisão é definir “qual máquina fica com 
qual tarefa”:
Função objetivo: relacionamos o tempo de cada máquina para cada tarefa: 
Modelando um Problema de Atribuição
xij → Uso da máquina “i” na tarefa “j”
Min Z = 14x11 + 5x12 + 8x13 + 7x14
+ 2x21 + 12x22 + 6x23 + 5x24 + 
7x31 + 8x32 + 3x33 + 9x34 + 
2x41 + 4x42 + 6x43 + 10x44
 Restrições das máquinas: cada máquina só pode ter uma atividade:
 Restrições das tarefas: cada atividade pode usar apenas uma máquina:
Modelando um Problema de Atribuição
x11 + x12 + x13 + x14 = 1
x21 + x22 + x23 + x24 = 1
x31 + x32 + x33 + x34 = 1
x41 + x42 + x43 + x44 = 1
Restrições das máquinas:
x11 + x21 + x31 + x41 = 1
x12 + x22 + x32 + x42 = 1
x13 + x23 + x33 + x43 = 1
x14 + x24 + x43 + x44 = 1
Restrições das tarefas:
 E, assim, realizamos a modelagem 
para um problema de atribuição. A 
solução para o problema apresentado 
pode ser obtida através da aplicação 
manual do algoritmo do Simplex, mas 
aprenderemos nas aulas de laboratório 
como resolvê-lo utilizando o Solver.
Modelando um Problema de Atribuição
Fonte: https://img.freepik.com/vetores-
gratis/homem-de-negocios-feliz-
fazendo-sinal-de-polegar-para-
cima_1325-454.jpg?size=338&ext=jpg
Quatro navios petroleiros serão usados para transportar óleo advindo de quatro 
plataformas (indicados por 1, 2, 3 e 4). Qualquer navio pode ser usado para fazer 
qualquer uma dessas quatro viagens. Entretanto, em virtude das distâncias e do 
custo de transporte de cada um, o custo total de carregamento, transporte e 
descarga do óleo para as diferentes combinações navio-plataforma varia 
consideravelmente, conforme indicado na tabela:
Pergunta-se: qual é a função objetivo do problema acima?
Interatividade
Tarefa
Navio 1 2 3 4
A US$ 500 US$ 400 US$ 600 US$ 700
B US$ 600 US$ 600 US$ 700 US$ 500
C US$ 700 US$ 500 US$ 700 US$ 600
D US$ 500 US$ 400 US$ 600 US$ 600
a) b)
Interatividade
Min Z = 500x11 + 400x12 + 600x13 + 
700x14 + 600x21 + 600x22 + 700x23
+ 500x24 + 700x31 + 500x32 + 
700x33 + 600x34 + 500x41 + 400x42
+ 600x43 + 600x44
Min Z = 500x11 + 600x12 + 700x13 + 
500x14 + 400x21 + 600x22 + 500x23
+ 400x24 + 600x31 + 700x32 + 
700x33 + 600x34 + 700x41 + 500x42
+ 600x43 + 600x44
c) Min Z = 700x11 + 600x12 + 700x13 + 
500x14 + 400x21 + 400x22 + 500x23
+ 400x24 + 600x31 + 400x32 + 
700x33 + 600x34 + 700x41 + 400x42
+ 600x43 + 600x44
d) e)
Interatividade
Min Z = 300x11 + 600x12 + 700x13
+ 500x14 + 400x21 + 400x22 + 
500x23 + 400x24 + 600x31 + 400x32
+ 700x33 + 600x34 + 700x41 + 
400x42 + 600x43 + 600x44
Min Z = 300x11 + 600x12 + 700x13
+ 500x14 + 400x21 + 400x22 + 
500x23 + 400x24 + 600x31 + 400x32
+ 700x33 + 600x34 + 700x41 + 
400x42 + 500x43 + 700x44
b)
Resposta
Min Z = 500x11 + 600x12 + 700x13 + 
500x14 + 400x21 + 600x22 + 500x23
+ 400x24 + 600x31 + 700x32 + 
700x33 + 600x34 + 700x41 + 500x42
+ 600x43 + 600x44
 Problema de transbordo: é uma variante do problema de transporte quando há 
pontos intermediários entre a origem e o destino. Portanto, o modelo contempla, 
além dos pontos de origem e destino, os pontos de transbordo, que podem 
representar, por exemplo, o estoque de determinado insumo.
Problema de Transbordo
O1
O3
O2
T1
T2
D1
D2
D3
O – Origem
D – Destino
T – Transbordo
Fonte: Autoria própria.
 Um ponto de transbordo pode representar muitas coisas, como, por exemplo, um 
estoque intermediário de umsupermercado, um ponto de baldeação.
Problema de Transbordo
Fontes: http://www.infovarejo.com.br/wp-
content/uploads/2017/04/invent%C3%A1rio-rotativo-de-
estoque-740x360.png
http://2.bp.blogspot.com/-
f9bGUtu0SMY/VbFyjL2VkCI/AAAAAAAAAac/5B8n9Afr7dA/s16
00/fpso31.jpg
A formulação de um problema de transbordo faz com que as entradas que chegam 
aos pontos de transbordo sejam equivalentes às ofertas. Se houver possibilidade de 
estoque no transbordo, o ponto pode suportar um diferencial entre entradas e saídas. 
As saídas dos pontos de transbordo são iguais às demandas. Assim:
 Um ponto de oferta envia, mas não recebe recursos.
 Um ponto de transbordo recebe e envia recursos.
 Um ponto de demanda recebe, mas não envia recursos.
Problema de Transbordo
Premissas para tratarmos um problema de transbordo, de maneira a avaliar 
capacidade e demanda:
 Criar uma linha para cada ponto de fornecimento e transbordo;
 Criar uma coluna para cada ponto de demanda e transbordo;
 Cada ponto de fornecimento terá capacidade de 
fornecimento igual à sua capacidade original de 
fornecimento;
 Cada ponto de demanda terá demanda igual à sua 
demanda original. 
Problema de Transbordo
 Uma empresa de automóveis possui fábricas em três países, Brasil, Japão e EUA, 
produzindo em cada país 300, 220 e 400 unidades de carro, respectivamente. 
Entretanto, para escoar sua produção para a Rússia e Austrália, a empresa faz 
conexão em dois países como pontos de transbordo: Espanha e Nova Zelândia. 
Sabendo-se que a demanda da Rússia é de 400 unidades e a demanda da 
Austrália é de 520 unidades, e que o custo unitário de transporte para cada região 
segue de acordo com as tabelas a seguir, o objetivo da empresa é gerar o menor 
custo de transporte possível até os pontos de demanda. Como fica o diagrama de 
rede e a modelagem do problema? 
Modelagem do Problema de Transbordo
Modelagem do Problema de Transbordo
Transbordos
Origem Espanha Nova Zelândia
Brasil 40 45
EUA Sem Rota 35
Japão 55 30
Destino final
Origem Rússia Austrália Espanha
Nova 
Zelândia
Espanha 30 40 0 25
Nova Zelândia 35 40 25 0
Montamos o diagrama de rede conforme apresenta as tabelas, indicando os locais 
onde existem rotas:
Modelagem do Problema de Transbordo
BRASIL
EUA
Japão
ESPANHA
NOVA 
ZELÂNDIA
RÚSSIA
AUSTRÁLIA
1
2
3
4
5
6
7
Fonte: Autoria própria.
A função objetivo vai de acordo com a definição de custos para cada uma das rotas. 
Os subscritos indicam os códigos de cada uma das origens-destinos:
Modelagem do Problema de Transbordo
Min Z = 40x14 + 45x15 + 35x25 + 55x34 + 30x35 + 25x45 + 25x54 + 30x46 + 40x47 + 
35x56 + 40x57
Restrições do problema ficam de acordo com as ofertas e demandas de cada país:
Modelagem do Problema de Transbordo
BRASIL: x14 + x15 = 300
EUA: x25 = 400
JAPÃO: x34 + x35 = 220
ESPANHA (T1): x44 + x45 + x46 + x47 = 920
NOVA ZELÂNDIA (T2): x54 + x55 + x56 + x57 = 920
Restrições de oferta: 
Restrições 
de destino: 
RÚSSIA: x46 + x56 = 400
AUSTRÁLIA: x47 + x57 = 520
ESPANHA (T1): x14 + x34 + x44 + x54 = 920
NOVA ZELÂNDIA (T2): x15 + x25 + x35 + x45 = 920
 Veja que nos transbordos foi feita a soma total das ofertas das origens e, depois, 
dos destinos, para cada um dos nós.
 E, assim, realizamos a modelagem para um problema de transbordo. A solução 
para o problema apresentado pode ser obtida através da aplicação manual do 
algoritmo do Simplex, mas aprenderemos nas aulas de laboratório como resolvê-lo 
utilizando o Solver.
Modelagem do Problema de Transbordo
Duas montadoras de carros estão ligadas a três revendedoras por meio de duas 
centrais de distribuição. As capacidades de produção das fábricas das montadoras 
são de 1000 e 1200 unidades de automóveis e as demandas são de 800, 900 e 500 
unidades, respectivamente, nas três revendedoras. Os custos unitários de transporte 
são dados nas tabelas abaixo:
Como fica o diagrama de rede do problema?
Interatividade
Central 1 Central 2
Fábrica 1 R$ 300 R$ 400 
Fábrica 2 R$ 200 R$ 500 
Revendedora 1 Revendedora 2 Revendedora 3
Central 1 R$ 800 R$ 600 ---
Central 2 --- R$ 400 R$ 900 
a) b)
c)
Interatividade
Fab 1
Fab 2
Rev 1
Cen 1
Cen 2
Rev 2
Rev 3
Fab 1
Fab 2
Rev 1
Cen 1
Cen 2
Rev 2
Rev 3
Fab 1
Fab 2
Rev 1
Cen 1
Cen 2
Rev 2
Rev 3
d) e)
Interatividade
Fab 1
Fab 2
Rev 1
Cen 1
Cen 2
Rev 2
Rev 3
Fab 1
Fab 2
Rev 1
Cen 1
Cen 2
Rev 2
Rev 3
e)
Resposta
Fab 1
Fab 2
Rev 1
Cen 1
Cen 2
Rev 2
Rev 3
 Problema de fluxo máximo: está relacionado com a capacidade máxima de fluxo 
entre dois nós de uma rede. Com isso, o objetivo num problema desse tipo é 
desenvolver um esquema de transporte que maximize a quantidade de material 
enviada entre dois pontos de origem e destino.
Problema de Fluxo Máximo
O
t1
t2
t3
D
t4
Fonte: Autoria própria.
 Observe a figura abaixo. Esse exemplo é uma das situações em que vemos certa 
sobrecarga no translado em dois pontos, o que acontece no nosso cotidiano. 
O tráfego em rodovias, o escoamento de 
água em tubulações de abastecimento 
doméstico, dutos de produção de petróleo 
e gás, entre outros, são exemplos típicos 
em que a modelagem de um problema 
de fluxo máximo é aplicada.
Problema de Fluxo Máximo
Fonte: 
https://catracalivre.co
m.br/wp-
content/uploads/2014/
09/rodovias_-
_reproducao.jpg
 De maneira geral, um problema de fluxo máximo está relacionado com a 
capacidade máxima de fluxo entre dois pontos de uma rede. Com isso, o objetivo 
de um problema desse tipo é desenvolver um esquema que maximize a 
quantidade de material enviada entre esses dois pontos.
Problema de Fluxo Máximo
O D
Qmáx
Fonte: Autoria própria
Uma empresa está elaborando um plano para abastecer diversas cidades com 
gasolina, transportando-a por uma malha de dutos. Em razão das condições 
climáticas e geográficas entre a cidade de origem (O) e a última cidade (E), diferentes 
capacidades de fluxo são obtidas entre as cidades. Considerando que a empresa 
quer o volume total de gasolina que pode chegar ao destino final, qual modelo que 
representa as rotas deve ser escolhido para as diversas cidades, de modo a 
maximizar a quantidade total transportada?
Modelagem do Problema de Fluxo Máximo
O 6
4
5
3
1
2
5
5
4
4
7
3
1
2
4
1
9
6
Fonte: Autoria própria.
Comecemos pelas restrições de 
capacidade: elas indicam que 
cada variável de decisão deve 
estar abaixo da capacidade 
máxima entre cada um dos nós:
Modelagem do Problema de Fluxo Máximo
x01estabelecendo que a soma de todas 
as rotas de saída seja igual a -1 (porque só uma delas vai ser utilizada).
II. Da mesma forma, para o nó terminal, a soma de todas as rotas de chegada deve 
ser igual a 1.
III. O valor das variáveis deve ser 1 ou 0, ou seja, a rota é 
utilizada ou não é utilizada.
Problema de Rota Mínima
 Uma empresa de transporte logístico está buscando uma nova forma de distribuir 
seus produtos, por meio de uma rede de distribuição, passando por diversas 
cidades. A partir do diagrama apresentado a seguir, proponha o modelo para o 
trajeto que irá gerar o menor percurso da cidade A até a cidade H, dadas as 
distâncias de um nó em relação a outro, especificadas no diagrama.
Modelagem do Problema de Rota Mínima
Fonte: Autoria própria.
A
B
C
D
E
F
G
H
2
12
4
6
5
3
3
7
8
5
Para definir, primeiramente, a função objetivo, precisamos realizar a soma de todas 
as rotas possíveis do problema:
Modelagem do Problema de Rota Mínima
F.O: Min Z = 12xAB + 4xAC + 3xBE + 5xBD + 2xCD + 6xCF + 7xEG + 8xDH + 5xFH + 3xGH
Fonte: Autoria própria.
A
B
C
D
E
F
G
H
2
12
4
6
5
3
3
7
8
5
Com relação às restrições do problema, avaliamos as rotas que chegam e que saem 
em cada um dos nós. Por exemplo, para o nó D:
 Ou seja, o valor atribuído à variável de decisão é 1 ou 0, 
indicando se a rota é usada ou não. O sinal (+) ou (-) 
indica se a rota entra ou sai do nó em questão.
Modelagem do Problema de Rota Mínima
Restrição do nó D:
xBD + xCD - xDH = 0
Fonte: Autoria própria.
B
C
D
H
xBD
xCD
xDH
Assim, as restrições são:
Modelagem do Problema de Rota Mínima
Restrição do nó A: – xAB – xAC = -1
Restrição do nó B: xAB – xBE – XBD = 0
Restrição do nó C: xAC – xCD – xCF = 0
Restrição do nó D: xBD – xCD – xDH = 0
Restrição do nó E: xBE – xEG = 0
Restrição do nó F: xCF – xFH = 0
Restrição do nó G: xEG – xGH = 0
Restrição do nó A: xGH + xGH + xFH = 1
 Veja que as variáveis de decisão do problema são do tipo binária: 1- a rota é 
usada e 0- a rota não é usada.
 Assim, partindo do ponto de origem, sabemos que apenas uma rota vai ser 
seguida até o ponto de destino.
 Aprenderemos, futuramente, como solucionar os problemas no Solver.
Modelagem do Problema de Rota Mínima
Sobre as afirmações abaixo:
I. O problema de rota mínima se preocupa em encontrar mais de uma rota possível 
para chegar a um mesmo destino, enquanto que o problema de fluxo máximo 
se preocupa em definir a menor quantidade transportada entre as rotas.
II. O problema de rota mínima busca encontrar a menor rota entre dois pontos 
dentre as várias possibilidades distintas, enquanto que o problema de fluxo 
máximo visa definir a quantidade máxima a ser transportada entre dois pontos.
III. O problema de rota mínima é de minimização, 
enquanto que o problema de fluxo máximo é de 
maximização.
Interatividade
Podemos afirmar que estão corretas as alternativas:
a) I e II apenas.
b) II e III apenas.
c) I e III apenas.
d) I, II e III.
e) Nenhuma das alternativas.
Interatividade
Sobre as afirmações abaixo:
II. O problema de rota mínima busca encontrar a menor rota entre dois pontos 
dentre as várias possibilidades distintas, enquanto que o problema de fluxo 
máximo visa definir a quantidade máxima a ser transportada entre dois pontos.
III. O problema de rota mínima é de minimização, enquanto que o problema de fluxo 
máximo é de maximização.
Podemos afirmar que estão corretas as alternativas:
b) II e III apenas.
Resposta
ATÉ A PRÓXIMA!