PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

CAPÍTULO I-PROGRAMAÇÃO EM REDES

1.1-Introdução

Um problema de programação em redes é modelado por meio de uma estrututa de grafo

ou rede que consiste em diversos nós, em que cada nó deve estar conectado a um ou mais
arcos.

Os modelos em rede vêm sendo bastante usados em diversas áreas de negócios, como
produção, transporte, localização de facilidades, gestão de projectos, finanças, entre
outras. Muitos deles podem ser formulados como problemas de programação linear e,
portanto, podem ser resolvidos pelo método Simplex.

A modelagem em redes facilita a visualização e a compreensão das características do

sistema. Dessa forma, versões simplificadas do método Simplex podem ser utilizadas
para resolver problemas de Programação Linear em redes. Além disso, outros algoritmos
mais eficientes vêm sendo propostos e utilizados para a solução de modelos em redes.

Dentre os principais problemas de programação em redes podemos citar o clássico

problema de transporte, o problema de transbordo, o problema de designação de tarefas, o
problema do caminho mais curto, entre outros.

Cada um dos problemas listados será estudado mais adiante. Apresentaremos,

inicialmente, a modelagem matemática de cada um deles, bem como a solução pelos
algoritmos clássicos.

1.2-A Terminologia de Grafos e Redes

Um grafo é definido a partir de um conjunto de nós ou vértices e um conjunto de arcos

ou arestas interconectando esses nós. Os nós, desenhados como círculos ou pontos,
podem representar facilidades (como fábricas, centros de distribuição, terminais ou portos
marítmos), estações de trabalho ou intersecções. Os arcos, ilustrados como segmentos de
recta, fazem conexão entre pares de nõs, podendo representar caminhos, rotas, fios,
cabos, canais, entre outros.

A notação de um grafo é ( ), em que é um conjunto de nós e é um conjunto

de arcos.

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 1

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Exemplo de um grafo

Muitas vezes, os arcos de um grafo que fazem conexões entre os nós estão associados a
uma variável numérica chamada fluxo que representa uma característica mensurável
dessa ligação, como distância entre nós, custo de transporte, tempo despendido, dimensão
do fio, quantidade de pessas transportadas, entre outras. Analogamente, os nós de um
grafo podem estar associados a uma variável numérica chamada capacidade, podendo
representar a capacidade de carga e descarga, suprimentos, demanda, entre outras.

Um grafo cujos arcos e / ou nós estão associados a uma variável numérica fluxo e / ou
capacidade é chamado de rede.

Exemplo de uma rede

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 2

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Os nós de uma rede podem ser divididos emtrês tipos:

1-Nós de oferta ou fontes: que representam entidades que produzem ou distribuem

determinado produto;

2-Nós de demanda: que representam entidades que consomem o produto;

3-Nós de transbordo: que são os pontos intermediários entre os nós de oferta e demanda
e representam os pontos de passagem desses produtos.

Os arcos podem ter uma seta indicando o sentido do arco. Quando o fluxo entre os nós
ocorre apenas num sentido, indicado por uma seta temos um arco direccionado. Quando
o fluxo entre os respectivos nós ocorre em ambos sentidos, tem-se um arco não
direccionado. Em casos em que há uma única conexão entre os nós, porém, sem a seta
indicando o sentido do arco, presume-se que o arco é não direccionado.

Diferença entre arco direccionado e não direccionado

Quando todos os arcos de uma rede são direccionados, tem-se uma rede direccionada.
No caso contrário, a rede é não direccionada.

Outras definições da teoria dos grafos, como caminho, caminho hamiltoniano, ciclo,
árvore são apresentadas a seguir.

Hillier e Liberman (2005) definem um caminho entre dois nós como a sequência de
diferentes arcos conectando esses nós. Em uma rede direccionada, pode-se ter um
caminho direccionado ou não direccionado. Um caminho que tem um único sentido é
chamado caminho direccionado. Por outro lado, se pelo menos um arco tem sentido
oposto aos demais, diz-se que o caminho é não direccionado

Um caminho é dito hamiltoniano quando visita cada nó uma única vez. Já um caminho
que começa e finaliza no mesmo nó forma um ciclo. Quando o caminho percorrido no
ciclo é direccionado, tem-se um ciclo direccionado. Analogamente, um caminho não
direccionado que começa e finaliza no mesmo nó é chamado ciclo não direccionado.

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 3

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Exemplo de uma rede direccionada

Uma rede ( ) não direccionada é dita conexa ou convexa quando existe um

caminho entre qualquer par qualquer de nós. A rde ( ) possui uma estrutura de
árvore se a mesma é conexa e acíclica.

Ainda dentro do conceito de árvore, afirma-se que:

 Uma árvore com nós tem arcos;

 Se um arco for adicionado à árvore, forma-se um ciclo;
 Se um arco for eliminado da árvore, a rede deixa de ser conexa.

Exemplo de uma árvore

1.3-Problema Clássico de Transporte

O problema clássico de transporte tem como objectivo determinar as quantidades de

produtos a serem transportadas a partir de um conjunto de fornecedores para um conjunto

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 4

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

de consumidores, de forma que o custo total de transporte seja minimizado. Cada

fornecedor fabrica um número fixo de produtos, e cada consumidor tem uma demanda
conhecida que será atendida. O problema é modelado a partir de dois elos da cadeia de
suprimentos, ou seja, não considera facilidades intermediárias (centros de distribuição,
terminal, porto marítimo ou fábrica). A notação matemática e a representação em redes
do problema clássico de transporte são apresentados a seguir.

Considere um conjunto de fornecedores que fornecem mercadorias para um conjunto

de consumidores. A quantidade máxima a ser transportada a partir de certo fornecedor
( ) corresponde à sua capacidade de unidades. Por outro lado, a
demanda de cada consumidor ( ) deve ser atendida, sndo representada
por . O custo unitário de transporte do fornecedor para o consumidor é representado
por . O objectivo é determinar as quantidades a serem transportadas do fornecedor
para o consumidor ( ), de modo a minimizar o custo total de transporte

Representação em Redes do Problema Clássico de Transporte

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 5

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Quadro do Problema Clássico de Transporte

1.3.1-Formulação Matemática do Problema Clássico de Transporte

Os parâmetros do modelo, as variáveis de decisão e a formulação matemática geral do

problema clássico de transporte estão especificados a seguir:

Parâmetros do modelo:

custo unitário de transporte do fornecedor ( ) para o consumidor

( )

capacidade de abastecimento do fornecedor ( )

demanda do consumidor ( ).

Variáveis de decisão:

quantidades transportadas do fornecedor ( ) para o consumidor

( ).

Formulação geral:

∑∑

Sujeito a:

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 6

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Que corresponde a um problema de programação linear.

Dessa forma, o problema poderia ser resolvido pelo método Simplex. Porém, a estrutura
especial do problema em redes permite a obtenção de algoritmos de solução mais
eficentes como veremos mais adiante.

Para que o problema ora apresentado tenha solução básica factível, a capacidade total de
fornecimento deve ser maior ou igual à demanda de todos consumidores, isto é,

∑ ∑

Se a capacidade total de fornecimento é exactamente igual à demanda total consumida, o

problema de transporte é dito equilibrado ou balanceado.

∑ ∑

E o problema pode ser reescrito como:

∑∑

Sujeito a:

Podemos ter um terceiro caso em que a capacidade total de fornecimento é menor que a
demanda total consumida ( ∑ ∑ ), de forma que a demanda total de alguns
consumidores não será atendida. Por outro lado, os fornecedores utilizarão sua
capacidade máxima. Esse caso pode ser formulado matematicamente como:

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 7

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

∑∑

Sujeito a:

Exemplo 1: Certa empresa possui dois armazéns, e , onde dispõe de 100 e 50

unidades de determinado produto, respectivamente, com o que abastece três mercados
, e , que consomem 80, 30 e 40 unidades respectivamente. Sabendo que os
custos de transporte são dados no quadro. Quê quantidades de produto devem ser
transportadas de modo que o custo seja mínimo?

Solução:

Temos o quadro que esquematiza os dados:

Oferta

Demanda

Como a capcidade total de produção é exactamente igual à demanda total consumida,

tem-se, um problema equilibrado.

Primeiramente, definem-se as variáveis de decisão do modelo:

quantidade de produtos a serem transportados do fornecedor para o consumidor .

Assim temos:

quantidade de produtos a serem trnsportados do fornecedor para o consumidor

quantidade de produtos a serem trnsportados do fornecedor para o consumidor

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 8

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

quantidade de produtos a serem trnsportados do fornecedor para o consumidor

quantidade de produtos a serem trnsportados do fornecedor para o consumidor

quantidade de produtos a serem trnsportados do fornecedor para o consumidor

quantidade de produtos a serem trnsportados do fornecedor para o consumidor

A função objectivo busca minimizar o custo toal de transporte:

As restrições do modelo estão especificadas a seguir:

1-Capacidade de cada fornecedor será utilizada para atender a demanda dos

consumidores:

2-A demanda de cada consumidor deve ser atendida:

3-As variáveis de decisão do modelo são não negativas:

Exemplo 2: Uma empresa pretende abastecer quatro fábricas, , , e com uma

matéria prima disponível em três mercados, , e . Os elementos relativos a
custos, necessidades e disponidbilidades constam no quadro seguinte:

Oferta

Procura

Como a capcidade total de produção é exactamente igual à demanda total consumida,

tem-se, um problema equilibrado.

Primeiramente, definem-se as variáveis de decisão do modelo:

quantidade de produtos a serem transportados do fornecedor para o consumidor .

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 9

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Assim temos:

quantidade de produtos a serem transportados do mercado para a fábrica

quantidade de produtos a serem transportados do mercado para a fábrica

quantidade de produtos a serem transportados do mercado para a fábrica

quantidade de produtos a serem transportados do mercado para a fábrica

quantidade de produtos a serem transportados do mercado para a fábrica

quantidade de produtos a serem transportados do mercado para a fábrica

quantidade de produtos a serem transportados do mercado para a fábrica

quantidade de produtos a serem transportados do mercado 2 para a fábrica

quantidade de produtos a serem transportados do mercado para a fábrica

quantidade de produtos a serem transportados do mercado para a fábrica

quantidade de produtos a serem trnsportados do mercado para a fábrica

quantidade de produtos a serem trnsportados do mercado para a fábrica

A função objectivo busca minimizar o custo total de transporte:

As restrições do modelo estão especificadas a seguir:

1-Capacidade de cada fornecedor será utilizada para atender a demanda dos

consumidores:

2-A demanda de cada consumidor deve ser atendida:

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 10

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

3-As variáveis de decisão do modelo são não negativas:

1.3.2-Equilibrando o problema de transporte quando a capacidade de fornecimento

total não é igual à demanda total consumida

Mais adiante veremos vários métodos para resolver um problema clássico de transporte.
Eles exigem que o problema esteja balanceado, de forma que um fornecedor ou
consumidor artificial ou fantasma (dummy) deve ser adicionado ao modelo.

Veremos a seguir cada um dos casos:

1º Caso: Quando a capacidade total de fornecimento total é maior do que a

demanda total consumida

Para restaurar balanceamento, deve-se criar um consumidor fantasma que absorverá o

excesso ofertado. Assim, a demanda desse novo destino corresponderá à diferença entre
a oferta total e a demanda total consumida, indicando a capacidade de fornecimento não
utilizada. O custo unitário de transporte de qualquer fornecedor para o consumidor
fantasma criado será nulo, já que o mesmo não é real.

Exemplo: Uma empresa actua no ramo alimentar com sede em Luanda possui três lojas.
Seus principais clientes estão localizados em Cuanza Sul, Benguela e Huambo. A
capacidade de fornecimento das lojas e a demanda dos clientes estão apresentadas no
quadro a seguir. A fim de minimizar o custo total de transporte, a empresa quer
determinar quanto distribuir de cada loja para os respectivos consumidores, respeitando a
capacidade de fornecimento e garantindo que as demandas serão atendidas. Formule o
problema de transporte dessa empresa.

Custo unitário de transporte Capacidade

Consumidor
Cuanza Sul Benguela Huambo
Fornecedor Loja 1
Loja 2
Loja 3
Demanda

Solução:

Podemos notar que estamos diante de um problema desequilibrado, já que a capacidade

de fornecimento ( ) é maior que a demanda consumida ( )

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 11

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Solução 1:

Uma maneira de representar o modelo matemático desse problema é representar as

restrições como desigualdades. Nesse modelo temos as seguintes variáveis de decisão:

quantidade de alimentos a transportar do fornecedor para o consumidor

Assim temos:

quantidade de produtos a serem transportados da loja para Cuanza Sul

quantidade de produtos a serem transportados da loja para Benguela

quantidade de produtos a serem transportados da loja para Huambo

quantidade de produtos a serem transportados da loja 2 para Cuanza Sul

quantidade de produtos a serem transportados da loja 2 para Benguela

quantidade de produtos a serem transportados da loja 2 para Huambo

quantidade de produtos a serem transportados da loja 3 para Cuanza Sul

quantidade de produtos a serem transportados da loja 3 para Benguela

quantidade de produtos a serem transportados da loja 3 para Huambo

A função objectivo busca minimizar o custo total de transporte:

As restrições do modelo estão especificadas a seguir:

1-Capacidade de fornecimento de cada loja deve ser respeitada:

2-A demanda de cada consumidor deve ser atendida:

3-As variáveis de decisão do modelo são não negativas:

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 12

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Solução 2:

Para que o algoritmo de transporte possa ser utilizado, o problema deve estar equilibrado
de forma que a capacidade total de fornecimento seja igual à demanda total consumida.
Para restaurar o equilíbrio nesse problema devemos criar um consumidor fantasma que
absorverá o excedente do fornecimento ( ).

Modelagem em redes do problema dado

O quadro torna:

Custo unitário de transporte Capacidade

Consumidor
Cuanza Sul Benguela Huambo D
Fornecedor Loja 1
Loja 2
Loja 3
Demanda

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 13

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

As novas variáveis de decisão são:

quantidade de produtos a serem transportados da loja para o novo destino

quantidade de produtos a serem transportados da loja para o novo destino

quantidade de produtos a serem transportados da loja para o novo destino

A função objectivo busca minimizar o custo total de transporte:

As restrições do modelo estão especificadas a seguir:

1-Capacidade de fornecimento de cada loja deve ser respeitada:

2-A demanda de cada consumidor deve ser atendida:

3-As variáveis de decisão do modelo são não negativas:

2º Caso: Quando a capacidade de fornecimento total é menor do que a demanda

total consumida

Para restaurar balanceamento, deve-se criar um fornecedor fantasma que atenderá a

demanda remanescente. Assim, a quantidade ofertada a partir desse novo fornecedor
corresponderá à diferença entre a demanda total consumida e a capacidade total de
fornecimento, indicando a demanda não atendida. O custo unitário de transporte do
fornecedor fantasma criado para qualquer consumidor será nulo, já que o mesmo não é

real.

Exemplo: Suponha que a mesma empresa do exemplo anterior adquiriu três novos
clientes, localizados nas províncias do Bengo, Malanje e Uíge, respectivamente. Como

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 14

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

formalizar o problema de transporte com as capacidades de fornecimento e demanda

apresentadas no quadro abaixo:

Custo unitário de transporte Capacidade

Consumidor
Bengo Malanje Uíge
Fornecedor Loja 1
Loja 2
Loja 3
Demanda

Solução:

Para que o algoritmo de transporte possa ser utilizado, o problema deve estar equilibrado
de forma que a capacidade total de fornecimento seja igual à demanda total consumida.
Para restaurar o equilíbrio nesse problema devemos criar um fornecedor fantasma que
suprirá a demanda não atendida ( ).

Modelo em redes do problema

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 15

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

O quadro fica:

Custo unitário de transporte Capacidade

Consumidor
Bengo Malanje Uíge
Fornecedor Loja 1
Loja 2
Loja 3
Loja D
Demanda

Como o custo unitário de transporte do novo fornecedor para cada destino é nulo, a
função objectivo não se altera:

As restrições do modelo estão especificadas a seguir:

1-Capacidade de fornecimento de cada loja deve ser respeitada:

2-A demanda de cada consumidor deve ser atendida:

3-As variáveis de decisão do modelo são não negativas:

1.3.3-Solução do Problema Clássico de Transporte

[Link]-Algoritmo de Transporte

A fim de facilitar a sua resolução o problema clássico de transporte pelos métodos que
veremos, o mesmo deve ser apresentado na sua forma tabular.

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 16

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Início: O problema deve estar balanceado e apresentado na sua forma tabular.

Passo 1: Encontrar uma Solução Básica Admissível (SBA) ou Solução Básica Factível
(SBF) inicial.

Para isso, apresentaremos três métodos: Método do Canto Noroete, Método do Custo
Mínimo e o Método de Aproximação de Vogel.

Passo 2: Teste de Optimalidade

Para verificar se uma solução encontrada é óptima, utiliza-se o método dos

multiplicadores, que é baseado na teoria da dualidade. Aplicar a condição de
optimalidade estudada no método Simplex ao problema de transporte. Se a condição é
satisfeita, o algoritmo termina aquí. Caso contrário, determina-se uma SBA adjacente
melhor.

Iteração: Determinar uma SBA adjacente melhor.

Para tal, três passos devem ser dados:

 Determinar a variável não básica que entrará na base, utilizando o método dos
multiplicadores;
 Escolher a variável básica que passará para o conjunto de variáveis não básicas
utilizando a condição de factibilidade do método Simplex;
 Recalcular a nova solução básica.

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 17

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

1º Método do Canto Noroeste (NW)

Etapas do método:

Início: Representar o problema na forma tabular. Nesse método os custos de transporte

podem estar representados ou não uma vez que não serão usados;

Passo 1: Seleccione a célula localizada no canto superior esquerdo (canto noroeste).

Logo será sempre a primeira variável seleccionada.

Passo 2: Aloque a maior quantidade possível de produto a essa célula, de forma que a
soma das células correspondentes na mesma linha e na mesma coluna não ultrapasse a
capacidade total de fornecimento e de demanda total, respectivamente.

Passo 3: A partir da célula seleccionada no passo anterior bloqueie (com um X ou traço)

as células correspondentes à mesma linha ou coluna que atingiu o limite máximo de
fornecimento ou demanda, respectivamente, já que nenhum outro valor diferente de zero
poderá ser atribuído a essas células. No caso de utilização do limite máximo, tanto na
linha como na coluna, bloqueie apenas uma delas. Essa condição garante que haverá
variáveis básicas com valores nulos. O algoritmo termina quando todas as células forem
bloqueadas ou alocadas.

Exemplo: Retomemos o Exemplo 1 deste material e obtenha-se uma solução básica

admissível utilizando o método do Canto do Noroeste.

Início:

1º Passo:

Atribui-se a (canto Noroeste) o maior valor possível, isto é, o mínimo entre a oferta

da origem 1 e a procura no destino 1, * + O destino 1 vê desta

forma satisfeita a procura respectiva. Traça-se a coluna 1 e ficam disponíveis

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 18

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

unidades na origem 1(dada a natureza do método, omitem-se os custos

unitários de transporte). Tem-se então o novo quadro:

A escolha da nova variável básica recai para * + . A origem 1 fica

assim esgotada. Traça-se a linha 1 e ficam por satisfazer unidades no

destino 2. Repete-se o procedimento no quadro:

Tem-se como nova variável básica * + e o quadro vem:

Resta agora apenas a quadrícula ( ) verificando-se evidentemente a igualdade entre a

oferta e a procura, pelo que .

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 19

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

A SBA obtida é então (variáveis básicas) e as

restantes e (variáveis não básicas), a que corresponde o valor da FO,

Esta solução, como se verifica tem ( ) ( ) variáveis básicas, e é

habitualmente apresentada em forma tabular de acordo com o quadro seguinte:

2 º Método do Mínimo da Matriz dos Custos ou Método do Menor Custo

O método do menor custo é uma adaptação do método do canto noroeste, em que, emvez
de seleccionar célula mais próxima do canto noroeste, selecciona-se aquela com menor
custo. O algoritmo completo está detalhado a seguir:

Etapas do método:

Início: Representar o problema na forma tabular

Passo 1: Seleccione a célula com menor custo possível

Passo 2: Aloque a maior quantidade possível de produto a essa célula, de forma que a
soma das células correspondentes na mesma linha e na mesma coluna não ultrapasse a
capacidade total de fornecimento e de demanda total, respectivamente.

Passo 3: A partir da célula seleccionada no passo anterior bloqueie (com um X ou traço)

as células correspondentes à mesma linha ou coluna que atingiu o limite máximo de
fornecimento ou demanda, respectivamente, já que nenhum outro valor diferente de zero
poderá ser atribuído a essas células. No caso de utilização do limite máximo, tanto na
linha como na coluna, bloqueie apenas uma delas. O algoritmo termina quando todas as
células forem bloqueadas ou alocadas.

Exemplo 1:

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 20

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

O menor dos custos da matriz é , pelo que * + . O destino 3

fica satisfeito, traçando-se a respectiva coluna, e ficam disponíveis

unidades na origem 2. Tem-se, deste modo, o novo quadro:

Para escolha da nova variável básica procura-se novamente o menor dentre os custos .

Como é o mínimo custo não traçado, vem * + . A origem 1 fica

esgotada, traçando-se a respectiva linha, e o destino 2 não é completamente satisfeito

faltando agora unidades. O quadro seguinte sintetiza o procedimento:

O custo relativo à origem 1 e destino 2 é o menor dos ainda não traçados, tendo-se assim

* + A procura do destino 2 é totalmente satisfeita e na

origem 1 ficam disponíveis unidades. Traça-se a coluna 2:

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 21

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Resta pelo que * + isto é, tem-se uma oferta disponível igual à

procura não satisfeita. A solução obtida é, portanto, a que consta no quadro seguinte, com

um custo total:

3º Método de Vogel ou Método das Penalidades

Vogel concebeu um método heurístico que identifica uma SBA inicial, em geral melhor
do que as obtidas pelos métodos anteriores. Assim, o método do Canto Noroeste ignora
completamente os custos e o método do Mínimo da Matriz de Custos identifica os
percursos e afecta quantidades aos mesmos em função dos custos, mas forma a que os
últimos percursos escolhidos resultam, em regra, em custos extremamente elevados.

Etapas do método:

Início: Representar o problema na forma tabular.

Passo 1: Para cada linha e cada coluna, calcule a penalidade que corresponde a
diferença entre os dois menores custos unitários de transporte na respectiva linha e
coluna. A penalidade para uma linha e coluna é calculada enquanto houver pelo menos
duas células ainda não alocadas e não bloqueadas na mesma linha e coluna.

Passo 2: Escolha a linha ou coluna com maior penalidade Em caso de empate, escolha
uma delas aleatoriamente. Na linha ou coluna seleccionada, escolha a célula com menor
custo.

Passo 3: Assim como no método do canto noroeste, aloque a maior quantidade possível
de produto a essa célula, de forma que a soma das células correspondentes na mesma
linha e na mesma coluna não ultrapasse a capacidade total de fornecimento e de
demanda total, respectivamente

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 22

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Passo 4: Analogamente ao método do canto noroeste, a partir da célula seleccionada no

passo anterior bloqueie (com um X ou traço) as células correspondentes à mesma linha
ou coluna que atingiu o limite máximo de fornecimento ou demanda, respectivamente, já
que nenhum outro valor diferente de zero poderá ser atribuído a essas células. No caso
de utilização do limite máximo, tanto na linha como na coluna, bloqueie apenas uma
delas. Enquanto restar mais de uma célula não alocada e não bloqueada, volte ao Passo
1. Caso contrário vá ao Passo 5.

Passo 5: Aloque a essa última célula a capacidade ou demanda remanescente.

Exemplo 2 deste material :

Oferta

Procura

Para a aplicação do Método de Vogel é útil acrescentar uma linha e uma coluna, em cada
quadro, onde se inscrevem as diferenças entre os dois menores custos em coluna e em
linha, respectivamente. Selecciona-se a maior das diferenças e em seguida o menor custo
na linha ou coluna correspondente.

A variável básica escolhida é * + . Calculam-se as novas

diferenças relativas apenas aos elementos não traçados e selecciona-se outra variável

básica de acordo com o procedimento anterior. Vem então:

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 23

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

A variável seleccionada é * + . Repetindo o procedimento tem-

se:

Dado que há empate, escolhe-se arbitrariamente uma linha ou coluna relativa à maior
diferença. Escolhendo a linha 2, vem: * + .

Procedendo de forma análoga, tem-se: * + .

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 24

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Como se verifica no quadro, já não há posssibilidade de escolha, pelo que o

preenchimento das restantes quadrículas é imediato, obtendo-se a SBA seguinte com

Passo 2: Teste de Optimalidade

Para verificar se a solução encontrada é óptima, utiliza-se o método dos multiplicadores

, que é baseado na teoria da dualidade. Assim, a cada linha e coluna associam-se os
multiplicadores e , respectivamente. Os coeficientes da função objectivo (custos
reduzidos) da variável ( ̅ ) são dados pela seguinte fórmula:

Como os custos reduzidos das variáveis básicas são nulos, a fórmula anterior resume-se
a:

Para cada variável básica .

Calculados os multiplicadores, pode-se determinar os custos reduzidos das variáveis não

básicas por meio da fórmula: ̅ .Para o problema de transporte

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 25

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

(problema de minimização) a solução encontrada será óptima se, e somente se, os

custos reduzidos de todas as variáveis não básicas forem não positivos:

para cada variável não básica .

Enquanto existir pelo menos uma variável não básica com custo reduzido positivo, há
solução básica admissível adjacente melhor.

Iteração: Determinar uma SBA adjacente melhor

Para encontrar uma SBA adjacente melhor, temos três passos:

1º Passo: Determinar a variável não básica que entrará na base, utilizando método dos
multiplicadores.

A variável não básica que entra na base é aquela com maior custo reduzido (maior
valor de ).

2º Passo: Escolher a variável básica que sairá da base.

3º Passo: Recalcular a nova soluçãobásica. Diferentemente do método Simplex, o

cálculo é feito directamente no quadro que representa o problema de transporte.

A escolha variável que sai da base e o cálculo da nova solução básica podem ser obtidos
por meio de um ciclo que inicia e finaliza na variável não básica escolhida para entrar
na base. O ciclo consiste em uma sequência de segmentos horizontais e verticais
conectados entre sí (movimentos na diagonal não são permitidos), em que cada esquina
está associada a uma variável básica, com excepção da variável não básica
seleccionada. Existe somente um ciclo que pode ser construído nessas condições.

Construído o ciclo, o passo seguinte consiste em determinar a variável que sairá da

base.

Assim, dentre as esquinas vizinhas à variável não básica (horizontal ou

verticalmente), escolhe-se a variável básica com menor valor, já que as restrições
decapacidade do fornecedor i e de demanda do consumidor j devem ser respeitadas. Em
caso de empate, escolhe-se uma delas, arbitrariamente.

Finalmente, recalcula-se a nova solução básica. Primeiramente, atribui-se o valor

correspondente à variável básica escolhida para sair da base à nova variável básica ,.
A variável que sai da base assume, portanto, o valor zero. Os novos valores das
variáveis básicas que formam o ciclo também devem ser recalculados, de forma que as
capacidades de fornecimento e as demandas requeridas continuem sendo satisfeitas.

Exemplo: Seja testar a optimalidade da SBA obtida pelo método do Canto Noroeste
relativa ao problema de transporte do Exemplo 2, apresentada no qudro a seguir:

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 26

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Solução:

Para os valores das variáveis no quadro, devemos calcular os multiplicadores para as

variáveis:

Fazendo , temos as soluções:

A partir desses multiplicadores, calculam-se os custos reduzidos das variáveis não básicas
por meio da fórmula ̅ :

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 27

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Como os custos reduzidos das variáveis não basicas são positivos, não temos
solução óptima. Dentre eles, o maior custo reduzido é ( ̅ ). A variável que entra na
base é , pois tem maior custo reduzido.

Construindo um ciclo no quadro vem:

* + , atribuimos esse valor a variável que entra na base ( ),

para .

O quadro será:

Testando essa solução vem:

Calculemos os multiplicadores para:

Fazendo , temos as soluções:

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 28

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

A partir desses multiplicadores, calculam-se os custos reduzidos das variáveis não básicas
por meio da fórmula ̅ :

Como os custos reduzidos das variáveis não basicas são todos não positivos, temos
solução óptima.

Temos, portanto:

Para os quais

1.4-O Problema de Transbordo

O troblema de transbordo é uma extensão do problema clássico de transporte, em que, em

vez de transportar directamente os produtos a partir das várias origens para os vários
destinos, consideram-se pontos intermediários de transbordo (facilidades como centro de
distribuição, terminal, porto marítimo ou fábrica) que podem conectar esses caminhos,
com o objectivo de reduzir os custos logísticos. O problema de transbordo é modelado a
partir de três elos na cadeia de suprimentos, e o processo de transporte ocorre em dois
estágios: transporte dos pontos fornecedores para os pontos de transbordo e transporte
dos pontos de transbordo para os pontos de demanda. O objectivo do problema de
transbordo é determinar o fluxo de mercadorias a serem transportadas a partir de um
conjunto de origens para um conjunto de destinos via facilidades intermediárias, a fim de
minimizar o custo total de transporte envolvido no sistema. A notação matemática e a
representação em redes são apresentadas a seguir.

Considere um conjunto de fornecedores que fornecem mercadorias para um conunto

de fornecedores via facilidades intermediárias. A quantidade máxima a ser
transportada a partir de determinado fornecedor ( ) corresponde à sua
capacidade unidades. Por outro lado, a demanda de cada consumidor ( )
deve ser atendida, sendo representada por . Os pontos de transbordo são representados
pelo índice ( ). O custo unitário de transporte do fornecedor para o

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 29

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

consumidor via ponto de transbordo é representado por .O objectivo é determinar

as quantidades a seremtransportadas do fornecedor para o consumidor passando por
um ponto de transbordo ( ), de modo a minimizar o custo total de transporte .

Representação em Redes do Problema de Transbordo

Podemos perceber pela figura que, o custo unitário de transporte do fornecedor para o
consumidor via ponto de transbordo é representado por corresponde à soma dos
custos unitários de transporte do fornecedor para o ponto de transbordo que é
representado por e do ponto de transbordo para o consumidor ( ):

Analogamente, a quantidade transportada do fornecedor para o consumidor via ponto

de transbordo é representado por corresponde à soma das quantidades
transportadas do fornecedor para o ponto de transbordo que é representado por e
do ponto de transbordo para o consumidor ( ):

1.4.1-Formulação Matemática do Problema de Transbordo

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 30

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Os parâmetros do modelo, as variáveis de decisão e a formulação matemática geral do

modelo são apresentados a seguir:

Parâmetros do modelo:

custo unitário de transporte do fornecedor para o consumidor via ponto de

transbordo

capacidade de abastecimento do fornecedor .

demanda do consumidor .

Variáveis de decisão:

quantidade transportada do fornecedor para o consumidor via ponto de

transbordo

Formulação geral:

∑∑

Sujeito a:

(1)

(2)

(3)

∑ ∑

(4)

Que corresponde a um problema de programação linear.

O objectivo é, portanto, minimizar o custo de tranporte envolvido na rede logística.

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 31

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

A restrição (1) do problema afirma que a capacidade total de cada fornecedor deve ser
respeitada. Já a restrição (2) garante que a demanda de todos consumidores será satisfeita.
A restrição (3) é de conservação de fluxos de entrada e de saída, isto é, a quntidade total
que chega ao ponto de transbordo , sai do mesmo ponto. Finalmente, a restrição (4) é de
não negatividade.

Analogamente ao problema clássico de transporte, para que o problema de transbordo

tenha solução básica factível, a capacidade total de fornecimento, deve ser maior ou igual
à demanda de todos os consumidores, isto é,

∑ ∑

Se a capacidade total de fornecimento é exactamente igual à demanda total consumida,

isto é,

∑ ∑

Tem-se um problema de transbordo balanceado ou equilibrado. Podendo ser reescrito

como:

∑∑

Sujeito a:

(1)

(2)

(3)

∑ ∑

(4)

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 32

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Ou:

∑∑ ∑∑

Sujeito a:

(1)

(2)

(3)

∑ ∑

(4)

Exemplo: A compainha Sonangol actua no sector Petroquímico e possui duas Plantas ou

Plataformas. Uma localizada em Luanda e é responsável pela produção de Alcatrão e
outra localizada em Benguela, é responsável pela produção de Vavolina. A fim de reduzir
os custos logísticos, os produtos sofrem uma etapa de transbordo em um dos centros de
distribuição, localizados em Cuanza Norte e Huambo. A partir dos centros de
distribuição, os produtos são transportados para os clientes finais localizados na Lunda
Norte, Lunda Sul e Moxico. A capacidade de fornecimento da Planta de Luanda é de
e da de Benguela é de e a demanda dos consumidores localizados na Lunda Norte,
Lunda Sul e Moxico são respectivamente: respectivamente. Os custos
unitários de transporte das fábricas para os pontos de transbordo e dos pontos de
transbordo para os consumidores finais estão dados no quadro abaixo. Formule o
problema de transbordo correspondente a esse problema.

Custos unitários de transporte das fábricas para os centros de distribuição

Cuanza Norte Huambo

Luanda
Benguela

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 33

PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Custos unitários de transporte dos centros de distribuição para os consumidores

finais

Lunda Norte Lunda Sul Moxico

Cuanza Norte
Huambo

Representação em redes do problema

Pode-se observar na figura que os nós e representam as plantas em Luanda e

Benguela respectivamente, os nós e representam os centros de distribuição
localizados em Cuanza Norte e Huambo respectivamente, e os nós e representam
os consumidores finais localizados na Lunda Norte, Lunda Sul e Moxico ,
respectivamente.

A fim de formular matematicamente o problema definimos primeiro as variáveis de

decisão:

quantidade transportada da fábrica para o ponto de transbordo k.

quantidade transportada do ponto de transbordo k para o consumidor j.

quantidade transportada da fábrica de Luanda para o centro de Cuanza Norte

quantidade transportada da fábrica de Luanda para o centro do Huambo

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 34

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

quantidade transportada da fábrica de Benguela para o centro de Cuanza Norte

quantidade transportada da fábrica de Benguela para o centro do Huambo

quantidade transportada do cento Cuanza Norte para o consumidor na Lunda Norte

quantidade transportada do cento Cuanza Norte para o consumidor na Lunda Sul

quantidade transportada do cento Cuanza Norte para o consumidor no Moxico

quantidade transportada do cento do Huambo para o consumidor na Lunda Norte

quantidade transportada do cento do Huambo para o consumidor na Lunda Sul

quantidade transportada do cento do Huambo para o consumidor no Moxico

A função objectivo busca minimizar o custo total de transporte, é dada por:

1-A capacidade de cada fábrica será utilizada para atender a demanda dos
consumidores via pontos de transbordo:

(Fábrica de Luanda)

(Fábrica de Benguela)

2-A demanda de cada consumidor será atendida a partir dos pontos de transbordo:

(Consumidor da Lunda Norte)

(Consumidor da Lunda Sul)

(Consumidor do Moxico)

3-Restrições de conservação dos fluxos de entrada e de saída em cada ponto de

transbordo:

(Centro de distribuição de Cuanza Norte)

(Centro de distribuição do Huambo)

4-As variáveis de decisão do modelo são não negativas:

1.4.2-Problema de Transbordo como um de Problema Transporte

Seja a resolver o problema anterior:

Aquí, apresentaremos como um problema de transbordo pode ser convertido em um

problema de transporte, e consequentemente resolvido pelo algoritmo de transporte.

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 35

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Primeiramente, identificam-se os nós de oferta ou fontes ( ), os nós de

transbordo ( ) e os nós de demanda ( ).

Para que esse problema de transbordo possa ser convertido num problema de transporte,
os nós de transbordo tornam-se tanto pontos de oferta como também pontos de demanda.
Dessa forma, o problema passa a ter quatro fontes: ( ) e cinco destinos
( ). Deve-se definir também a capacidade de fornecimento das novas fontes e
a demanda dos novos destinos. Como a capacidade total de fornecimneto do modelo
original ( ) pode ser concentrada em qualquer nó de transbordo, e
consequentemente enviada para os consumidores finais, consideraremos que a capacidade
que a capacidade de fornecimento e a demanda de cada nó de transbordo ( ) será de
para o novo problema de transporte. Assim temos a forma tabular desse novo
problema a seguir:

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 36

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Repare que os custos dos nós 1 e 2 para os nós 3 e 4, juntamente com os custos dos nós 3
e 4 para os nós 5, 6 e 7 representados, foram considerados. Obviamente os valores de
e são nulos. Como as demais células não fazem parte do problema original de
transbordo (por exemplo, não se pode percorrer directamente o arco ( )), atribui-se
uma penalização ( ) a essas células, de forma a obrigar que essas células
assumam valores nulos na solução óptima.

A solução óptima do problema pelo algoritmo dos transportes está no quadro a seguir,
para um .

1.5-O Problema de Designação de Tarefas

O problema de designação de tarefas, também conhecido como problema de alocação ou

ou atribuição, consiste em desinar um conjunto de tarefas a um conjunto de máquinas, de
forma a minimizar o custo total de designação. O problema de designação de tarefas pode
ser modelado como um problema de transportes, em que os fornecedores correspondem
às tarefas e as demandas correspondem às máquinas. Como cada tarefa pode ser
designada apenas a uma máquina, e cada máquina pode processar apenas uma tarefa, se o
problema de designação for modelado como um problema de transportes, a capacidade de
cada fornecedor e demanda de cada cliente corresponderá a Além disso, as variáveis de
decisão do problema de designação passam a ser binárias. A notação matemática e a
representação em redes do problema de designação de tarefas são apresentadas a seguir.

Considere um conjunto de tarefas ( ) e um conjunto de tarefas

( ). O custo de designar uma tarefa a uma máquina é . Cada tarefa
pode ser designada a apenas uma máquina , e cada máquina pode processar apenas
uma tarefa . O problema consiste em designar as tarefas às máquinas, de forma a
minimizar o custo total de designação ( ).

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 37

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Representação em Redes do Problema de Designação de Tarefas

1.5.1-Formulação Matemática do Problema de Designação de Tarefas

Os parâmetros do modelo, as variáveis de decisão, e formulação matemática geral do

problema de designação de tarefas são apresentados a seguir:

Parâmetros do modelo:

custo de designar uma tarefa a uma máquina

Variáveis de decisão:

Formulação geral

∑∑

Sujeito a:

ou .

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 38

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Que corresponde a um problema de programação binária, já que todas as variáveis são

binárias. Assim o modelo pode ser resolvido com um problema de programação linear
( ).

A função objectivo busca minimizar o custo total de designação das tarefas às

máquinas . A primeira restrição garante qua cada tarefa será designada a apenas uma
máquina. A segunda restrição garante que cada máquina processará uma única tarefa.
Finalmente, a terceira restrição garante que as váriáveis são binárias.

Exemplo: Uma empresa do sector de autopeças possui três máquinas ( ) e três

actividades que devem ser completadas no processo de fabricação de bancos
(acabamento, montagem e pintura). Cada actividade pode ser designada a apenas uma
máquina e cada máquina pode processar apenas uma actividade. O tempo de
processamento de cada actividade em cada máquina está ilustrado no quadro abaixo.
Formule o problema como um problema de Desinação de Tarefas.

Tempo em horas
Actividade
Acabamento
Montagem
Pintura

Solução:

Os parâmetros do modelo são:

tempo de processamento da tarefa i máquina j,

As variáveis de decisão do modelo são:

A função objectivo é dada por:

As restrições do modelo estão especificadas a seguir:

[Link] tarefa i pode ser designada a apenas uma máquina j:

(Acabamento)

(Montagem)

(Pintura)

2-Cada máquina j pode processar apenas uma tarefa i:

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 39

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

(Máquina 1)

(Máquina 2)

(Máquina 3)

3-As variáveis de decisão são binárias:

ou

1.5.2-Solução do Problema de Designação de Tarefas

O problema de designação de tarefas será resolvido pelo método Húngaro

[Link]-O Método Húngaro

Um algoritmo comumente utilizado na resolução do problema de designação de tarefas é

o método Húngaro. Para que um problema possa ser resolvido pelo método Húngaro, ele
deve estar representado na forma tabular da matriz de custos seguinte:

Os procedimentos do método Húngaro são descritos a seguir:

Início: O problema deve estar representado na forma matricial de custos.

Construir uma nova matriz em que os novos valores dos elementos de uma determinada
linha corresponderão à diferença entre os valores originais e o menor elemento da linha
seleccionado.

Passo 2: Para a matriz resultante do Passo 1, encontrar o elemento com menor custo em
cada coluna. Construir uma nova matriz (chamada matriz de custo reduzido) em que os
novos valores dos elementos de uma determinada coluna corresponderão à diferença
entre os valores originais e o menor elemento da coluna seleccionado.

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 40

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Passo 3: Cubra com rectas horizontais e verticais o menor número possível de linhas e
colunas, de forma que todos os elementos com valores nulos da matriz de custos
reduzidos sejam cobertos. Se m rectas são necessárias, então há uma solução óptima
entre os elementos com valores nulos cobertos na matriz. Se foram usadas menos de m
rectas, então vá ao passo 4.

Passo 4: Dentre os elementos não cobertos pelo passo 3, seleccione aquele com menor
valor, chamado [Link] uma nova matriz de custos, subtraindo k de cada elemento
não coberto na matriz de custo reduzido, e adicionando k para cada elemento coberto
tanto por linha como por coluna, [Link] demais elementos permanecem
[Link] ao Passo 3.

Exemplo: Uma empresa do sector de autopeças possui três máquinas ( ) e três

actividades que devem ser completadas no processo de fabricação de bancos
(acabamento, montagem e pintura). Cada actividade pode ser designada a apenas uma
máquina e cada máquina pode processar apenas uma actividade. O tempo de
processamento de cada actividade em cada máquina está ilustrado no quadro abaixo.
Resolva o problema pelo Método Húngaro.

Tempo em horas
Actividade
Acabamento
Montagem
Pintura

Solução:

Início:

Passo 1: Seleccionam-se os menores elementos de cada linha. Subtrai-se de cada

elemento original o menor elemento da linha correspondente, resultando na matriz a
seguir:

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 41

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Passo 2: Seleccionam-se os menores elementos de cada coluna. Subtrai-se de cada

elemento original o menor elemento da coluna correspondente, resultando na matriz de
custos reduzidos a seguir

Passo 3: Cubra com rectas horizontais e verticais o menor número possível de linhas e
colunas, de forma que todos os elementos com valores nulos da matriz de custo reduzido
sejam cobertos.

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 42

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Nesse caso, foram necessárias apenas duas rectas. Como vamos ao passo 4.

Passo 4: Dentre os elementos não cobertos, seleccionamos aquele com menor valor
( ). Construimos uma nova matriz de custos, subtraindo de cada elemento não
coberto na matriz de custo reduzido, e adicionando para cada elemento coberto tanto
por linha como por coluna ( ). Os demais permanecem inalterados.

Passo 5: Cubra com rectas horizontais e verticais o menor número possível de linhas e
colunas, de forma que todos os elementos com valores nulos da matriz de custo reduzido
sejam cobertos.

Nesse caso, foram necessárias apenas três rectas. Como há solução óptima entre
os elementos com valores nulos cobertos na nova matriz.

Para encontrar a solução óptima, verifica-se que o único elemento com zero coberto na
coluna é log . Assim, o elemento não pode mais ser usado restando o
elemento na coluna 2 , logo, . Analogamente o elemento não pode mais
ser usado restando o elemento na coluna 1 , logo, .

Portanto a solução óptima é: com .

1.6-O Problema do Caminho mais Curto

O problema do caminho mais curto, tambémconhecido como problema do caminho

mínimo Busca encontrar o menor caminho entre dois nós de uma rede. Em vez de
minimizar a distância total percorrida, pode-se minimizar também o custo total ou o
tempo total de viagem.

O problema considera apenas um nó de oferta que corresponde ao ponto de origem da

rede e apenas um nó de demanda que corresponde ao ponto de destino da rede. A
capacidade de fornecimento do nó de oferta e a demanda do nó de destino da rede
correspondem a uma unidade. Já os outos nós intermediários ou de transbordo terão
oferta e demanda iguais a zero.

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 43

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Considere determinado nó . Os nós de origem de são representados pelo índice

e os nós de destino de são representados por . O nó de oferta da rede é
representado por e o nó de demanda da rede por , com capacidade e demanda de uma
unidade, respectivamente. Se o nó analisado corresponder ao nó de oferta da rede, tem-
se que . Por outro lado, se o nó corresponder ao nó de demanda da rede, temos
. A distância entre os nós e é representada por . A fim de encontrar o caminho
mais curto entre os nós de oferta e de demanda da rede, busca-se determinar se o arco
( ) está contido nesse caminho.

1.6.1-Formulação Matemática do Caminho mais Curto

Os parâmetros do modelo, as variáveis de decisão, e formulação matemática geral do

problema do caminho mais curto são especificados a seguir:

Parâmetros do modelo:

distância do nó para o nó

Variáveis de decisão:

( )
{

Formulação geral:

∑∑

Sujeito a:

∑ ∑ {

ou

Ou:

∑∑

Sujeito a:

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 44

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

∑ ∑

ou

Que corresponde a um problema de programação binária.

O objectivo do problema do caminho mais curto é, portanto, determinar o menor

caminho entre o nó de oferta e o nó de demanda da rede, dentre os possíveis
caminhos. As trê primeiras restrições representam os fluxos de entrada e de saída em
cada nó Se o nó analisado for o nó de oferta da rede ( ), a restrição ∑
∑ resume-se a ∑ , já que o fluxo de entrada do nó é zero e sua
capacidade de fornecimento é de uma unidade. Se o nó analisado for o nó de demanda
da rede ( ) a restrição ∑ ∑ resume-se a ∑ , já que o fluxo
de saída do nó é zero e sua demanda é de uma unidade. Para todos os demais nós, o
fluxo de entrada menos o fluxo de saída é igual a zero.

Analogamente ao problema de designação de tarefas, o problema do caminho mais curto

também pode ser resolvido como um problema de programação linear.

Exemplo: A SGC Lda com sede no Uíge comercializa café, pretende entregar certa
quantidade de toneladas a um cliente localizado no Namibe. Para isso, o motorista pode
percorrer mais de uma rota (caminho), passando por diferentes províncias. O esquema a
seguir, indica os diferentes caminhos que um motorista pode percorrer até chegar a
Namibe, alem das distâncias entre as localidades. Formule o problema como o Problema
do Caminho mais Curto estudado.

Solução:

Primeiramente, definem-se as variáveis de decisão do modelo:

( )
{

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 45

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Assim, tem-se que:

se a rota ( ) está no caminho mais curto ; caso contrário.

se a rota ( ) está no caminho mais curto ; caso contrário.

se a rota ( ) está no caminho mais curto ; caso contrário.

se a rota ( ) está no caminho mais curto ; caso contrário.

se a rota ( ) está no caminho mais curto ; caso contrário.

se a rota ( ) está no caminho mais curto ; caso contrário.

se a rota ( ) está no caminho mais curto ; caso contrário.

se a rota ( ) está no caminho mais curto ; caso contrário.

se a rota ( ) está no caminho mais curto ; caso contrário.

se a rota ( ) está no caminho mais curto ; caso contrário.

se a rota ( ) está no caminho mais curto ; caso contrário.

se a rota ( ) está no caminho mais curto ; caso contrário.

se a rota ( ) está no caminho mais curto ; caso contrário.

A função objectivo busca o menor caminho entre o nó de oferta e o nó de demanda é

dada por:

As restrições do modelo estão especificadas a seguir:

1-Nó de oferta:

(Nó 1)

2-Nó de demanda:

(Nó )

3-Nós intermediários ou de transbordo:

(Nó )

(Nó )

(Nó )

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 46

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

(Nó )

(Nó )

(Nó )

(Nó )

4-As variáveis de decisão são binárias:

* +

1.6.2-Solução do Problema do Caminho mais Curto

O problema do caminho mais curto será resolvido pelo algoritmo de Dijkstra

[Link]-O Agoritmo de Dijkstra

O algoritmo de Dijkstra determina o menor caminho entre o nó fonte e o nó destino de

uma rede; assume que os custos de todos os arcos são não negativos, garantindo assim
que a solução óptima seja encontrada. Trata-se de um algoritmo eficiente que define um
nó como rotulado ou fechado quando se encontra o menor caminho do nó fonte até este
nó. Já os nós cujo caminho mínimo ainda não foram encontrados são chamados não
rotulados ou abertos. Considere o conjunto de nós rotulados e o conjunto de nós
não rotulados. Assim, inicialmente, o conjunto é vazio, enquanto o conjunto
contém todos os elementos da rede. O algoritmo de Dijkstra é descrito a seguir.

Início:

* +

Passo 1: Atribua o valor ao nó fonte e aos demais nós.

Passo 2: Enquanto o conjunto de nós não rotulados for não vazio ( ) faça o
seguinte:

 Seleccione o nó ainda não rotulado com o menor valor (nó k)

 Passe o nó k para o conjunto de nós rotulados
 Para todo nó j ainda não rotulado que seja sucessor de k, faça:
 Some o valor do nó k com o custo do arco que une os nós k e j, e atribua esse
valor ao nó j em caso de melhoria. Nesse caso, define-se o nó k como precedente
de j (só se houver melhoria)

Exemplo: Aplicando o Algoritmo de Dijkstra para solucionar o problema

recentemente formulado vem:

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 47

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Inicialmente temos o esquema que traduz o problema:

Passo 1: Atribui-se o valor ao nó fonte e aos demais nós.

Passo 2: Enquanto o conjunto de nós não rotulados for não vazio ( ) faça o
seguinte:

1ª Iteração do passo 2

O nó ( ) é seleccionado, pois possui custo nulo.

Logo, * + * +.

Os nós sucessores de (1) são os nós ( ) e ( ).

O novo valor do nó ( ) é ( ) e do nó ( ) é ( ).

Como houve melhoria para os nós ( ) e ( ), define-se o no ( ) como precedente dos nós
( ) e ( ), representando com uma linha tracejada.

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 48

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

2ª Iteração do passo 2

Dentre os nós ainda não rotulados, selecciona-se aquele com menor custo ( ) que
passa para o conjunto de nós rotulados.

Logo, * + * +.

Os nós sucessores de ( ) são os nós ( ) e ( ).

O novo valor do nó ( ) é ( ) e do nó ( ) é ( ).

Como houve melhoria para os nós ( ) e ( ), define-se o no ( ) como precedente dos nós
( ) e ( ), representando com uma linha tracejada.

3ª Iteração do passo 2:

Dentre os nós ainda não rotulados, selecciona-se aquele com menor custo ( ) que
passa para o conjunto de nós rotulados.

Logo, * + * +.

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 49

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Os nós sucessores de ( ) são os nós ( ) e ( ).

O novo valor do nó ( ) passa a ser ( ) e do nó ( ) permanece inalterdo

( ).

Como houve melhoria apenas para o nó ( ), define-se o nó ( ) como novo precedente

dos nós ( ).

4ª Iteração do passo 2:

Dentre os nós ainda não rotulados, selecciona-se aquele com menor custo ( ) ou nó
( ) que passa para o conjunto de nós rotulados.

Logo, * + * +.

Os nós sucessores de ( ) são os nós ( ) e ( ).

O novo valor do nó ( ) passa a ser ( ) e do nó ( ) é ( ).

Como houve melhoria para os nós ( ) e ( ), define-se o nó ( ) e como precedente dos

nós ( ) e ( )

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 50

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

5ª Iteração do passo 2:

Dentre os nós ainda não rotulados, selecciona-se aquele com menor custo ( ) que
passa para o conjunto de nós rotulados.

Logo, * + * +.

Os nós sucessores de ( ) são os nós ( ) e ( ).

O novo valor do nó ( ) permanece inalterado ( ) e do nó ( ) é

( ).

Como houve melhoria apenas para o nó ( ), define-se o nó ( ) como precedente do nó

( ).

6ª Iteração do passo 2:

Dentre os nós ainda não rotulados, selecciona-se aquele com menor custo ( ) que
passa para o conjunto de nós rotulados.

Logo, * + * +.

O nó sucessor de ( ) é ( ).

O novo valor do nó ( ) é ( ).

Como houve melhoria do nó ( ), define-se o nó ( ) como seu precedente.

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 51

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

7ª Iteração do passo 2:

Dentre os nós ainda não rotulados, selecciona-se aquele com menor custo ( ) que
passa para o conjunto de nós rotulados.

Logo, * + * +.

O nó sucessor de ( ) é ( ).

O novo valor do nó ( ) é ( ).

Como houve melhoria do nó ( ), define-se o nó ( ) como seu precedente.

8ª Iteração do passo 2:

Dentre os nós ainda não rotulados, selecciona-se aquele com menor custo ( ) que
passa para o conjunto de nós rotulados.

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 52

 PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

Logo, * + * +.

O nó sucessor de ( ) é o nó ( ).

Porém, seu valor permanece inalterado já que não houve melhoria ( ).

Assim, o nó ( ) passa a ser rotulado na nova rede.

9ª Iteração do passo 2:

Resta apenas o nó ( ) no conjunto de nós não rotulados.

Logo, * + .

O algoritmo finaliza aquí.

Como todos os nós da figura estão rotulados, pode-se obter o caminho mínimo entre o nó
origem e o nó destino da rede. Portanto o caminho mais curto obtido pelo algoritmo de
Dijkstra é com

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 53

PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 54

PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 55

PROGRAMAÇÃO MATEMÁTICA ISCED-UÍGE

4º ANO ENSINO DE MATEMÁTICA-2023/2024 Página 56