Otimização

Matemática

O problema dos Transportes

O problema de afetação

Optimização em Redes

Certezas e incertezas

O Docente: José AntónioFazenda

1
 TEMA NOVE
PROBLEMA DE TRANSPORTE

1. Noções Gerais

2. Um Exemplo de Problema de Transporte

3. Formulação de um Problema de Transporte
4. Arranjos a forma genérica
5. Propriedade do Modelo de Transporte
6. Método de stepping-Stone
5.6.1. O método do custo mínimo por linha
5.6.2. O método do custo mínimo por coluna
5.6.3. Desenvolvimento do método stepping-stone
7. Dificuldades do Problema de transporte
8. Exercícios para resolver
TEMA DEZ
ANÁLISES DE REDES

1. Conceito Básico em Teoria de Grafos

2. O Problema da Árvore Geradora de Custo Mínimo
2.1.O Algoritmo de Kruskal
2.2.O Algoritmo de PRIM
3. O problema do caminho mais curto

3.1.1. O algoritmo de DIJKSTRA

3.1.2. Outra forma de Resolver o Problema
3.1.3. O algoritmo de Ford
3.1.4. O algoritmo de Floyd

4. O problema do Fluxo Máximo

4.1.1. Corte de uma Rede

4.1.2. O algoritmo de Ford – Fukerson
4.1.3. Resolução de Problema
4.1.4. Casos especiais do Fluxo Máximo

5. O Problema do Fluxo de Custo Mínimo

5.1.1. Situação
5.1.2. Formulação do problema
5.1.3. O algoritmo de BUSACRER – GOWEN
5.1.4. Exercícios Proposto

2
TEMA UM:
O PROBLEMA DOS TRANSPORTES

1. NOÇÕES GERAIS
O problema dos transportes é um caso particular dos problemas de programa
matemática e é utilizado sempre que nos deparamos com um produto homogéneo, dado
por um conjunto de um centro de oferta ou origens e procurado por outro conjunto de
centros de procura ou destinos, desde que:

Se pretenda transportar o produto dado dos centros de oferta para os centros de procura.

Seja nosso objectivo, encontrar a oferta mais barata ou mais rápida de o fazer.

1.1.Um exemplo de problema de transporte

Uma empresa tem 4 padarias e pretende distribuir o pão que produz diariamente por 6
pastelarias 8 exploradas. As 4 padarias têm capacidade diária de produção de
300,400,400 e 500 pães respectivamente.

Entretanto, o consumo de pão nas pastelarias estima-se em 250,360,280,200,250 e 200

por dia os custos de transportes por unidade, de cada uma das padarias para cada uma
das pastelarias, constam a seguinte tabela:

Pastelarias

Padarias 𝑃1 𝑃2 𝑃3 𝑃4 𝑃5 𝑃6 Oferta total

01 3 2 5 1 1 3 300

0 2 2 4 3 2 5 400

0 5 4 2 4 5 1 400

0 3 4 3 4 3 2 500

Procura 250 360 280 200 250 200

O objectivo é determinar o melhor plano de distribuição do pão por forma de

minimização os custo de transportes. As restrições do problema, relacionam-se quer
maximização da que de pão a produzir quer a minimização do consumo em cada
pastelaria.

3
O quadro anterior pode simplificar no seguinte diagrama:

01 300 250 𝑃1

02 400 360 𝑃2

400 280 𝑃3

𝑂4 500 200 𝑃4

111226 250 𝑃5

𝑃6
200

Consideremos que devemos transportar um único produto homogéneo desde m origens

ou pontos de embarque até n destinos que podem ser armazéns ou fábricas.Denotemos
por a1,a2, …, am as ofertas ou quantidade de produtos disponível e por b1, b2, …, bn a
procura ou necessidades existentes deste produto em n destinos. É possível transportar
este produto a partir de qualquer origem para qualquer destino sendo C ij o custo de
transportação de uma unidade de produto desde a origem i até ao destino j.

Neste caso em que se supõem que a oferta existente nas origens é igual a procura nos
destinos, o objectivo é determinar as quantidades de produto que deveram ser enviadas
desde cada origem até a cada destino de forma que se satisfaça a procura existente e se
esgotem as ofertas das origens a um custo mínimo de transportação.A situação que
descrevemos atrás, pode ser representada mediante o esquema que segue, também
conhecido como fluxograma.

a1 b1

a2 b2

a3 b3

Am bn

4
NOTA: Para concluir pode-se dizer que, desde que a oferta total seja igual a procura
total, o problema de transportes tem sempre solução.

Analisemos o exemplo anterior:

3𝑥11 + 2𝑥12 + 5𝑥13 + 𝑥14 + 𝑥15 + 3𝑥16

+2𝑥21 + 2𝑥22 + 4𝑥23 + 3 𝑥24 + 2𝑥25 + 5𝑥26

+5𝑥31 + 4𝑥32 + 2𝑥33 + 4𝑥34 + 5𝑥35 + 𝑥36

+3𝑥41 + 4𝑥42 + 3𝑥43 + 4 𝑥44 + 3𝑥45 + 2𝑥46

𝑥11 + 𝑥12 + 𝑥13 + 𝑥14 + 𝑥15 + 𝑥16 ≤ 300 Restrições

𝑥21 + 𝑥22 + 𝑥23 + 𝑥24 + 𝑥25 + 𝑥26 ≤ 400 de

𝑥31 + 𝑥32 + 𝑥33 + 𝑥34 + 𝑥35 + 𝑥36 ≤ 400 oferta

𝑥41 + 𝑥42 + 𝑥43 + 𝑥44 + 𝑥45 + 𝑥46 ≤ 500

𝑥11 + 𝑥21 + 𝑥31 + 𝑥41 ≤ 250

𝑥12 + 𝑥22 + 𝑥32 + 𝑥42 ≥ 360 Restrições

𝑥13 + 𝑥23 + 𝑥33 + 𝑥43 ≥ 280 de

𝑥14 + 𝑥24 + 𝑥34 + 𝑥44 ≥ 200 procura

𝑥15 + 𝑥25 + 𝑥35 + 𝑥45 ≥ 250

𝑥16 + 𝑥26 + 𝑥36 + 𝑥46 ≥ 200

𝑥11 , 𝑥12 , 𝑥13 , 𝑥14 , 𝑥15 , 𝑥16 ≥ 0

𝑥21 , 𝑥 , 𝑥23 , 𝑥24 , 𝑥25 , 𝑥26 ≥ 0 Restrições

𝑥31 , 𝑥32 , 𝑥33 , 𝑥34 , 𝑥35 , 𝑥36 ≥ 0 de não

𝑥41 , 𝑥42 , 𝑥43 , 𝑥44 , 𝑥45 , 𝑥46 ≥ 0 negatividade

Neste caso, oferta total das padarias é igual a 1600 pães enquanto as 6 pastelarias
procuram 1540 pães, devemos criar uma pastelaria fictícia que consuma os 60 pães
excedentes. Assim sendo: 𝑚𝑖𝑛. 𝐶𝑇𝑇 = 3𝑥11 + 2𝑥12 + 5𝑥13 + 𝑥14 + 𝑥15 + 3𝑥16 +
0𝑥17 +2𝑥21 + 2𝑥22 + 4𝑥23 + 3 𝑥24 + 2𝑥25 + 5𝑥26 + 0𝑥27

5
 2. FORMULAÇÃO DE UM PROBLEMA DE TRANSPORTES

Seja:

𝑐𝑖𝑗0 → o custo de transporte de uma unidade de produto da origem i até ao destino j.

𝑆𝑖 → a quantidade de produto disponível para ser transportada de cada centro de oferta i.

dj → a quantidade de produto procurada em cada centro de procura j.

𝑥𝑖𝑗 → a quantidade de produto a transportar de cada centro de oferta i para cada outro
centro de procura j ao custo unitário de 𝑐𝑖𝑗 .

Com estas definições, a formulação genérica do problema será:

0 0 0 0
𝑀𝐼𝑁 𝐶 = 𝐶11 𝑥11 + 𝐶12 𝑥12 + 𝐶13 𝑥13 + … + 𝐶14 𝑥14
0 0 0 0
+𝐶21 𝑥21 + 𝐶22 𝑥22 + 𝐶23 𝑥23 +. . . +𝐶24 𝑥24 + ⋯
0 0 0 0
+ 𝐶𝑚1 𝑥𝑚1 + 𝐶𝑚2 𝑋𝑚2 + 𝐶𝑚3 𝑥𝑚3 +. . . +𝐶𝑚,4 𝑥𝑚 4

S.a

𝑥11 + 𝑥12 + 𝑥13 +. . . + 𝑥14 ≤ 𝑥1

𝑥21 + 𝑥22 + 𝑥23 +. . . + 𝑥24 ≤ 𝑥2 Restrições

… … … de

𝑥𝑚1 + 𝑥𝑚2 + 𝑥𝑚3 +. . . +𝑥𝑚 4 ≤ 𝑆4 oferta

𝑥11 + 𝑥21 + 𝑥31 +. . . + 𝑥𝑚 1 ≥ 𝑆1

𝑥12 + 𝑥22 + 𝑥32 +. . . + 𝑥𝑚 2 ≥ 𝑥2 Restrições

… … … de

𝑥1𝑚 + 𝑥2𝑚 + 𝑥3𝑚 +. . . +𝑥𝑚 4 ≥ 𝑆4 procura

𝑥11 , 𝑥12 , 𝑥13 , . .. , 𝑥14 ≥ 0

𝑥21 , 𝑥22 , 𝑥23 , . . . , 𝑥 24 ≥ 0 Restrições

… … … da

𝑥𝑚 1 , 𝑥𝑚 2 , 𝑥𝑚 3 , . .. , 𝑥𝑚 𝑚 ≥ 0 não negatividade

6
Simplificadamente:
𝑛 𝑛

𝑀𝑖𝑛 𝐶𝑇𝑇 ∑ ∑ 𝐶𝑖𝑗0 𝑥𝑖𝑗

𝑖=1 𝑗=1

𝑆. 𝑎: ∑ 𝑥𝑖𝑗 ≤ 𝑆𝑖 ; 𝑖 = 1, … , 𝑚
𝑗=1

∑ 𝑥𝑖𝑗 ≥ 𝑑𝑗 ; 𝑗 = 1, … , 𝑛
𝑗=1

𝑥𝑖𝑗 ≤ 0 ; 𝑖 = 1, … , 𝑚 ; 𝑗 = 1, … , 𝑛

1. ARRANJOS NA FORMA GENÉRICA

Por norma o problema só terá solução se a quantidade total de procura não exceder a
quantidade total de oferta, ou seja se ∑𝑛𝑖=, 𝑆𝑖 ≥ ∑𝑛𝑗=1 𝑑𝑗

NOTA: Na vida real compreende-se que solução passará a transportar o possível,

deixando um ou mais outros de oferta com quantidades de escoar.

Se o total do produto a oferecer for superior ao total do produto procurado, então a

quantidade total a transportar será apenas o limite dos produtos procurados ficando
alguns produtos em stock, na origem.

Se o total de produtos a oferecer for inferior ao total do produto procurados, então a

quantidade total a transportar será apenas o limite do produto oferecido, ficando alguma
procura por satisfazer.

Desta forma para conseguir-se que a oferta total seja igual a procura total deve-se criar
um destino fictício quando a oferta total e superior a procura total ou uma origem
fictícia sempre que a procura total seja superior a oferta total.

Os custos de transporte das unidades que saem da origem fictícia ou que entram para o
destino fictício serão nulos. As quantidades transportadas “caminhos
fictícios”correspondem a oferta que fica por utilizar ou a procurar que fica por
satisfazer.

A partir do momento em fica garantido que ∑𝑛𝑖=1 𝑆𝑖 ≥ ∑𝑛𝑗=1 𝑑𝑗, pode-se formular o
problema de transporta com todas as restrições sob forma de igualdade, pois assegura-se
que toda quantidade oferecida terá destino e que toda quantidade procurada será
satisfeita. Diz-se então que o problema esta equilibrado.

7
Simbolicamente tem-se:
0 0 0 0
𝑀𝑖𝑛 𝐶𝑇𝑇 = 𝐶11 𝑥11 + 𝐶12 𝑥12 + 𝐶13 𝑥13 + … + 𝐶14 𝑥14
0 0 0 0
+𝐶21 𝑥21 + 𝐶22 𝑥22 + 𝐶23 𝑥23 +. . . +𝐶24 𝑥24
0 0 0 0
+ 𝐶𝑚1 𝑥𝑚1 + 𝐶𝑚2 𝑥𝑚2 + 𝐶𝑚3 𝑥𝑚3 +. . . +𝐶𝑚,4 𝑥𝑚 4

S.a.:

𝑥11 + 𝑥12 + 𝑥13 + ⋯ + 𝑥14 = 𝑠1

𝑥21 + 𝑥22 + 𝑥23 +. . . + 𝑥24 = 𝑠2

… … …

𝑥𝑚1 + 𝑥𝑚2 + 𝑥𝑚3 +. . . +𝑥𝑚 4 = 𝑠4

𝑥11 + 𝑥21 + 𝑥31 +. . . + 𝑥𝑚 1 = 𝑑1

𝑥12 + 𝑥22 + 𝑥32 +. . . + 𝑥𝑚 2 = 𝑑2

… … …

𝑥1𝑛 + 𝑥2𝑛 + 𝑥3𝑛 +. . . +𝑥𝑚 4 = 𝑑4

𝑥11 , 𝑥12 , 𝑥13 , . .. , 𝑠14 ≥ 0

𝑥21 , 𝑥22 , 𝑥23 , . . . , 𝑥 24 ≥ 0

… … …

𝑥𝑚 1 , 𝑥𝑚 2 , 𝑥𝑚 3 , . .. , 𝑥𝑚 4 ≥ 0

OBS: 𝑥1 + 𝑥2 +. . . +𝑥𝑚 = 𝑥1 + 𝑥2 +. . . +𝑥4

Simbolicamente:
𝑛 𝑛

𝑀𝑖𝑛 𝐶𝑇𝑇 ∑ ∑ 𝐶𝑖𝑗0 𝑥𝑖𝑗

𝑖=1 𝑗=1

𝑆. 𝑎. : ∑ 𝑥𝑖𝑗 = 𝑠𝑖 ; 𝑖 = 1, … , 𝑚
𝑖=1

∑ 𝑥𝑖𝑗 = 𝑑𝑖 ; 𝑗 = 1, … , 𝑛
𝑖=1

𝑥𝑖𝑗 0 ≥ 𝑖 = 1, … , 𝑚; 𝑗 = 1, … , 𝑛

8
Em que: ∑𝑚 𝑚
𝑖=1 ∑𝑗=1 = 𝑑𝑗.

2. PROPRIEDADES DO MODELO DE TRANSPORTE

Teorema nº1: O modelo de transporte tem duas soluções possíveis.

Demonstração: devemos demonstrar que existe xij ; i  1,..., m; j  1,..., n

n m m n
Tal que:  xij  b j ;  xij  ai sendo que
j 1 i 1
 ai 
i 1
b j 1
j  A(oferta e procura)

ai b j n b j
ai . A
x
j 1
Seja xij  i, y então xij  0 sendo que: ij  ai   ai
A j 1 A A

m m ai b j m
ai b j . A
 xij  
i 1 i 1 A
 bj 
i 1 A

A
 bj

Teorema nº2: No modelo de transporte, qualquer uma das equações do sistema de

restrições pode ser expressa como combinação linear das restantes.

Demonstração:

Sabemos que o sistema de equações lineares do modelo de transporte é:

n m

 xij  b j x
i 1
ij  ai ; i  1,, m; j  1,, n
j 1

Desta forma podemos escrever:

 x11  x12    x1n  a1

x  x    x  a
 21 22 2n 2

    
 xm1  xm 2    xmn  a
m

 x11  x21    xm1  b1

x  x    x  b
 12 22 m2 2

    
 x1n  x2 n    xmn  b
n

9
A demonstração não perde generalidade se por exemplo verificarmos que a primeira
equação se pode expressar como combinação linear das restantes.

Com efeito, se somarmos as n equações do segundo tipo de restrições obteremos:

x11  x12    x1n   x21  x22    x2n     xm1  x2m   xmn   b1  b2  bn
Equação A. Se somarmos as equações do primeiro tipo de restrições a partir da segunda
equação obteremos uma nova equação que chamaremos de B ou seja:

x21  x22    x2n     xm1  xm 2   xmn   a2    am  B

A  B  x11  x12    x1n   x21  x22    x2 n     xm1  x2 m   xmn  

x21  x22    x2n     xm1  xm 2   xmn   b1    bn  a2  a3    am

Ou seja
n m
x11    x1n   b j   ai  a1 obteremos a primeira equação. Como A – B
j 1 1 2

Como A é combinação linear das equações do segundo tipo e B é combinação linear de

m-1 equações do primeiro tipo (não se inclui a primeira), então A – B é combinação
linear das equações do sistema a partir da segunda.

Como a primeira equação é igual a A – B, então fica demonstrado que a primeira

equação se pode expressar como combinação linear das restantes m+n-1 equações do
sistema. Como consequência desta demonstração, podemos afirmar que nos problemas
de transporte, uma das equações do sistema é redundante e portanto se pode eliminar
ficando então o modelo com nxm variáveis e n+m-1 restrições.

TERCEIRO TEOREMA (construção de uma solução básica possível)

O problema de transporte admite uma solução, quanto mais m+n-1 variáveis positivas.

Demonstração:

Consiste em indicar um procedimento para obter uma solução básica possível. Este
procedimento denomina – se método da esquina noroeste e foi proposto por Dantzig.
Vemos detalhar o método para um sistema de três origens e quatro destinos, ou seja:

x11 x12 x13 x14 a1

x21 x22 x23 x24 a2
x31 x32 x33 x34 a3

10
 b1 b2 b3 b4

Determinemos um valor para x11 (esquema noroeste). X11=Min (a1.b1). se x11=a1, então
x1j = 0;

J= 2, 3, 4. Se x11 = b1, então xij = 0; i = 2, 3.

Primeiro passo: x11 = a1

a1 0 0 0 0
x21 x22 x23 x24 a2
x31 x32 x33 x34 a3

b1  a1 b2 b3 b4

Seguidamente passam a determinar X21=Min (a2,b1-a1). Suponhamos que Min (a2.b1 –

a1) = b1 - a1, então teremos a tabela do segundo passo:

Segundo passo:

a1 0 0 0 0
b1  a1 x22 x23 x24 a2  b1  a1
0 x32 x33 x34 a3

0 b2 b3 b4

Seguidamente detalha – se os passos seguintes:

Terceiro passo: suponhamos que a2 - b1+a1 = b2

a1 0 0 0 0
b1  a1 b2 x23 x24 a2  b1  a1  b2
0 0 x33 x34 a3

0 b2 b3 b4

Quarto passo: Supõe – se que a2 – b1+a1- b2< b3

11
 a1 0 0 0 0
b1  a1 b2 a2  b1  a1  b2 x24 a2  b1  a1  b2
0 0 x33 x34 a3

0 0 b3  a2  b1  a1  b2 b4

Neste caso vemos que: x33  b3  a2  b1  a1  b2

Resumidamente teremos:

x11  a1 x21  b1  a1 x22  b2 x23  a2  b1  a1  b2 x33  b3  a2  b1  a1  b2

x34  b4

Nota – se claramente que as suas variáveis tem valores positivos. O número de equações
deste modelo é 3+4=7, isto é, obtivemos uma solução básica possível.

De notar que a1, a2, a3, b1, b2, b3, b4 são números inteiros não negativos e
consequentemente a solução obtida (como combinação da soma e o resto dos a i e dos
bj), também consistirá em números inteiros não negativos.

Exemplo: Determine uma solução básica com: a1=2, a2=4, a3=7, b1=3, b2=2, b3=4, b4=2,
b5=2

2 0 0 0 0 2
1 2 1 0 0 4
0 0 3 2 2 7

3 2 4 2 2

Quarto teorema: Cada conjunto m+n-1 vectores LI do sistema de equações do modelo

de transporte reduzido pode ser arranjado como uma matriz triangular.

Neste teorema também se pode enunciar da seguinte forma: “todas as bases do

problema de transportes são triangulares”.

A importância deste teorema radica no fato de facilitar a resolução destes sistemas de

equações por métodos como o de substituição.

Definição: Um sistema de equações lineares AX = b, é triangular se a matriz A se pode

arranjar como uma matriz triangular.

Exemplo: o sistema de equações anterior será agora resolvido pelo método de retro
substituição.

12
 1 1 0 0 0 0 0  x11  3
0
 1 1 1 0 0 0  x21  4
0 0 1 0 0 0 0  x22  2
    
0 0 0 1 1 0 0. x23   4
0 0 0 0 1 1 1  x33  7 
    
0 0 0 0 0 1 0  x34  2
0
 0 0 0 0 0 1  x35  2

x11  x21  3
x21  x 22  x23  4
x22  2
x23  x23  4
x33  x34  x35  7
x34  2
x35  2
x33  2  2  7  x33  3
x23  3  4  x23  1
x21  2  1  4  x21  1
x11  1  3  x11  2

0btivemos assim uma solução original. Quando o sistema de equações é triangular então
pelo menos uma equação tem contem apenas uma variável ( que pode ser isolada
directamente) se substituir este valor no resto das equações do sistema obtém – se pelo
menos uma equação com uma incógnita e assim sucessivamente até achar todas as
variáveis e isto consiste precisamente no método de retro substituição.

Quinto teorema: Supondo que ai e bj são números inteiros não negativos, então todas as
soluções básicas possíveis do problema de transportes têm valores inteiros.

Sexto teorema: Existe sempre nos problemas de transporte uma solução possível
mínima finita.

Demonstração: Já se demonstrou no primeiro teorema que estes problemas admitem

solução.

Como os coeficientes das equações do sistema são não negativos e todos os ai e bj são
não negativos, então nenhum xij será infinitamente grande.

De facto, os xij não podem ser maiores que os seus correspondentes ai ou bj. Se ai ou bj
são inteiros então uma solução possível mínima básica tem valores finitos inteiros.

Métodos para construção de uma solução básica inicial dos problemas de transporte.

13
O algoritmo de transporte que estudaremos é igual ao método Simplex e parte de uma
solução básica possível para começar as iterações. Vamos tratar de três métodos para
construir uma solução básica possível, um dos quais já foi abordado. Estes métodos são:

I. Método da esquina nordeste (já abordado)

II. Método do custo mínimo por fila
III. Método do custo mínimo por coluna

3. MÉTODO DO CUSTO MÍNIMO POR FILA

Seja c1k o custo mínimo da primeira fila (se existir mas do que um custo mínimo
seleccionaremos aquele que tenha menor sub índice j)

Seja x1k = Min (a1,bk)

Se x1k = a1 então passamos a segunda fila depois de trocar bk por bk – a1. Seguidamente
encontramos na segunda fila o escaque que tenha custo mínimo e repetimos o processo

Se x1k=bk , então trocamos a1 por a1 – bk e bk por zero e encontramos o seguinte cij mais
pequeno que na primeira fila repetindo o processo.

Exemplo: Determine uma solução básica inicial pelo método do custo mínimo por fila,
no problema cujos dados se oferecem na seguinte tabela:

cij D1 D2 D3 D4 O

O1 8 15 24 12 60

O2 16 25 7 9 70

O3 70 15 24 32 100

D 50 80 30 50 210

14
Solução pelo método de custo mínimo por fila

D1 D2 D3 D4 O

O1 8 15 24 12 40

40

O2 16 25 9
7
40 70
30

O3 32
70 15 24
10 100
10 80

D 50 80 30 50

Valor da f.o. = 40x8+30x7+40x9+70x10+80x15+32x6

= 320+210+360+700+1200+320

= 3110

Localizamos o escaquecorrespondente ao custo mínimo na primeira fila e neste caso

será o primeiro escaque, sendo assim:

x11= Min (40,50) = 40

Passamos para segunda fila e localizamos o escaque do custo mínimo na e neste caso
será x23 , sendo assim: x23= Min (30,50) = 30, nesta mesma fila o escaque seguinte de
acordo com o custo mínimo é x24, logo:

x24= Min (70 - 30, 50) = 40

Na terceira fila teremos:

x32 = Min (80,100) = 80

x32 = Min (100 - 80,50 - 40) = (20 – 10) = 10

x32 = Min (50 - 40,100 - 90) = 10

Assim podemos concluir que estamos diante de uma solução básica possível.

15
 4. MÉTODO DO CUSTO MÍNIMO POR COLUNA

Este método é análogo ao anterior, só que aqui o processo decorre nas colunas.

Exemplo: Determine uma solução básica inicial pelo método do custo mínimo por
coluna, no problema cujos dados se oferecem na seguinte tabela:

D1 D2 D3 D4 O

O1 8 24 12
15
40 40

O2 16 25 9
7
10 30 70
30

O3 70 15 32
24
80 20 100

D 50 80 30 50

X11= Min (50, 40) = 40

x21 = Min (70,50 - 40) = 10

x23 = Min (100 ,80) = 80

x32 = Min (30, 70- 10) = 30

x42= Min (50, 7 – 30 - 10) = 30

x43 = Min (100 – 80, 50 - 30) = 20

Valor da f.o. = 40x8+16x10+80x15+30x7+30x9+20x32 = 2800

Estes dois métodos explicados caracterizam – se pelas seguintes propriedades:

A soma das variáveis básicas que aparecem numa fila i, é igual a a i, (oferta
correspondente a origem i).

A soma das variáveis básicas que aparecem numa coluna j, é igual a bj (procura
correspondente ao destino j).

No total há m + n – 1 variáveis básicas já quês nos três métodos estudados quando

colocamos uma variável básica num escaque (i, j), então não é possível colocar

16
simultaneamente mais variáveis básicas na fila e coluna correspondente ao dito
escaque.

Estas propriedades fazem com que a solução obtida seja básica e possível.

5. MÉTODO STEPING STONE

Ao resolver qualquer método de PL devemos de forma geral esperar que o número total
de iterações requeridas dependerá do mais próximo que se encontre o valor da FO na
solução possível inicial do mínimo real. Como o método da esquina noroeste não
considera os coeficientes cij não podemos esperar que o valor da FO numa solução
inicial pelo método da esquina noroeste se aproxime do mínimo.

Estudaremos o método que toma em conta os cij e que portanto deverá der uma solução
inicial melhor que o método da esquina noroeste.

a. Desenvolvimento do método de Stepping-Stone

O método de stepping-stone chega à solução óptima partindo se uma solução inicial e
pesquisando se alguma solução melhor pode ser obtida. Como o método parte de uma
solução inicial, devemos encontrar uma solução viável qualquer para poder utilizar o
método.

Solução inicial

Vamos utilizar como exemplo o problema apresentado na Seção 6.1. Para encontrar
uma solução inicial, será utilizado o método do mínimo custo. Este método consiste nos
seguintes passos:

1. Atribuir o máximo possível à variável com menor custo unitário e preenche com
zeros a linha ou coluna satisfeita. No exemplo, faz-se x31 = 80 já que c31 = 3, utilizando
completamente o fornecimento da Fonte 3. Desta forma, x32 e x33 devem ser iguais a 0.

2. Ajustar os elementos da linha ou coluna não ajustada a partir da variável com menor
custamos. Assim, no exemplo, na primeira coluna temos que fazer x11 = 70 (menor custo
unitário), de forma a atender a capacidade do Destino 1. Logo, x21 deve ser igual a 0.

3. O processo é repetido para as variáveis com outros custos, em ordem crescente.

Dessa forma, devemos fazer x12 = 50, de forma a completar o fornecimento da Fonte 1,
igualando a zero assim a variável x13. Para completar o quadro, devemos definir x22 = 20
(capacidade do Destino 2) e x23 = 60.

17
 D1 D2 D3

O1 8 5 6

70 50 0 120

O2 15 10
12
0 20 80
60

O3 9
3 10
0 80
80 0

D 150 70 60

Processo iterativo

Cada célula vazia representa uma variável não básica que poderia entrar na base. Para
entrar, a contribuição da variável não básica deve implicar a redução do custo total.
Calculando essas contribuições para a célula x13:

1. Atribua 1 unidade a x13. Assim, não é mais 60, mas 61 o total de unidades na coluna
3.

2. Para não violar a restrição da coluna 3, uma unidade deverá ser subtraída de x23, que
passa a ter 59 unidades, e a coluna 3 com um total de 60 novamente.

3. Agora a linha 2 totaliza 79 e não 80, o que pode ser corrigido com a adição de uma
unidade a x22 (20 → 21).

4. A coluna 2 fica então com um total de 71, o que pode ser corrigido com a subtração
de uma unidade de x12.

5. A linha 1 é automaticamente corrigida em função do passo anterior.

Para cada variável zerada, devemos determinar um caminho fechado de forma a calcular
a sua contribuição na função objectivo. Estes caminhos são definidos por linhas
verticais ou horizontais, delimitando um polígono fechado. Apenas em um vértice deste
polígono deve haver uma variável zerada, que é a própria variável não básica que será
incluída na base. Só é possível formar um único caminho com essas características para
cada variável zerada.

Encontrado o caminho mínimo da variável, sua contribuição é calculada alternando

soma e subtracção dos custos unitários dos vértices, começando da variável a ser
incluída na base.

18
Vamos agora calcular a contribuição de cada variável não básica na função objectivo

.Variável Caminho Contribuição

x13x13 →x23 → x22 →x12 6 - 12 + 10 - 5 = -1

x21x21 →x22 → x12 →x11 15 - 10 + 5 - 8 = 2

x32x32 →x12 → x11 →x31 9-5+8-3=9

x33x33 →x23 →x22 →x12 →x11 →x31 10 - 12 + 10 - 5 + 8 - 3 = 8

Como é um problema de minimização, a variável a entrar na base será aquela que

contribui com a maior redução no valor da função objectivo, que é a variável x13. O
valor a ser alocado a esta célula deve ser o máximo, de modo que nenhuma das
variáveis fique com valor negativo. Este valor é o menor valor das variáveis que estão
nos vértices do caminho mínimo com sinal negativo. No caso, as variáveis com sinal
negativo são x12 e x23. Logo, o valor a ser alocado é 50.

As demais variáveis vão adicionar ou subtrair 50, conforme o sinal do vértice

correspondente à variável seja positivo ou negativo. Ou seja, as variáveis passarão a ter
os seguintes valores:

x13 = 0 + 50 = 50;
x23 = 60 - 50 = 10;
x22= 20 + 50 = 70;
x12 = 50 - 50 = 0.
Logo, a variável que sai da base é x12. A seguir, é apresentado o quadro após a primeira
iteração.

D1 D2 D3

O1 8 5 6

70 0 50 120

O2 15 10
12
0 70 80
10

O3 9
3 10
0 80
80 0

D 150 70 60

Recalculando as contribuições de cada variável não básica na função objectivo, temos

que:

19
Variável Caminho Contribuição

x12 x12 →x13 → x23 →x22 5 - 6 + 12 - 10 = 1

x21x21 →x23 → x13 →x11 15 - 12 + 6 - 8 = 1

x32 x32 →x22 → x23 →x13 →x11 →x31 9 - 10 + 12 - 6 + 8 - 3 = 10

x33 x33 →x13 → x11 →®x31 10 - 6 + 8 - 3 = 9

Como todas as variáveis têm contribuição positiva, isto indica que a inclusão de
qualquer uma delas fará aumentar o valor da função objectivo, portanto a solução
encontrada é óptima.

6. DIFICULDADES DO PROBLEMA DE TRANSPORTE

Não balanceamento entre oferta e demanda

Caso isso ocorra, o problema não pode ser resolvido da maneira apresentada. Deve-se
então criar uma origem ou destino fictício para que o problema esteja balanceado.

Para o problema inicial, se a produção total for maior que a capacidade total, criar um
depósito fictício com capacidade = produção total - capacidade total, com custos de
distribuição nulos. Se a produção total for menor que a capacidade total, criar uma
fábrica fictícia.

Outra maneira de se resolver o problema seria tratar as restrições pertinentes não mais
como equações e sim como inequações.

Soluções múltiplas

Ocorrem quando, detectada a solução óptima, um dos valores das contribuições for
zero. O caminho fechado para a variável xij correspondente indicará a forma de obtenção
da solução alternativa.

TEMA DEZ

PROBLEMA DE AFECTAÇÃO

Os problemas de acfectação envolvem a indicação de trabalhadores a tarefas numa base

de um para um (mais geralmente, envolvem permutaçoes de um conjunto de objecto)
assume - se que numeros de trabalhadores é igual ao numero de tarefa – Uma condição
pode ser garantida pela criação de trabalhadores ficticios ou tarefas ficticias, se

20
necessário - e que é conhecido o tempo cjj necessário para o i-esimo trabalhador
treminar a j-esíma tarefa (ou o valor do i-esímo obecto na j-esímo posiçao O objectivo
é afectar cada um dos trabalhadores a cada uma das tarefas, de modo a que estas sejam
concluídas num tempo total minimo (ou encontrar a permutação que tenha o maior valor
total).

Os problemas de afectação podem ser convertidos em problemas de transporte,

considerando-se os operários como origens e as tarefas como destinos em que todas as
ofertas e todas as procuras são iguais a 1. A resoluçao deste pode fazer-se com o
algorítimo dos transportes, mas o Método de Hungaro, que utiliza apenas a matriz de
custo, Quadro como entrada é mais eficiente. Neste método há quatro passos:

Trabalhos

1 2 3 ... n
1 c11 c12 c13 ... c1n
2 c21 c22 c23 ... c2n
3 c31 cc32 c33 ... c3n
... ... ... ... ... ...
n c1n c2n c3n cnn

PASSO 1:Em cada linha do quadrdo 9.1 localiaza-se o menor elemento , subtraindo-se
este de todos os elementos dessa linha.repete –se este procedimento para cada uma das
coluna (o menor valor das colunas é deterniado apos subtracção ).

A matriz de custo actualizada contera pelo menos um elemento nulo em cada uma das
liha e em cada uma das colunas.

PASSO2: determina-se se há uma afectação admissível envolvendo unicamente custos

nulos na matriz de custos actualizada. Por outras palavras, verifica-se se a matriz de
custo actualizada possui n elementos nulos, sem que existam dois deles (ou mais)
elementos nulo sobre uma mesma linha ou coluna. Se esta afectação existir, trata-se de
afectação optíma. Se ela não existir, procede-se para o passo 3 .

PASSO 3 : Cobre-se todos os zeros da matriz de custos actualizados com o menor

números possível de rectas horizontais e verticais. Cada uma destas recta horizontais
deve corta intregralmente a linha e cada uma das rectas verticais deve cortar
integralmente a coluna. Este números minímo possível de recta sera inferior a n .
Localiza-se o menor número de matriz de custo não intersectado por uma recta.Subtraí-
se este número por cada um dos elementos não cortado por uma recta e adiciona-se o
número em questão a cada um dos elementos situado na interseção de duas rectas .

PAASO 4 :Retornar ao passo 2.

Ver o problema 9.5. de acordo com um resultado basíco da teoria dos grafos ,o número
de rectas necessária na etapa 3 sera precisamente igual ao maior número de zero da

21
matriz de custo actualizada tais que dois deles não estejam sobre uma mesma linha ou
coluna.

22
NÁLISE DE REDES

1. CONCEITOS BÁSICOS EM TEORIA DOS GRAFOS

Diversos problemas de programação linear, inclusive os problemas de transporte,
podem ser modelados como problemas de fluxo de redes. Algoritmos específicos para
determinados tipos de problemas podem ser mais convenientes para a sua solução do
que algoritmos mais genéricos.

Em muitos problemas que nos seguem, a forma mais simples os descrever é, representa-
los em formas de grafos, sendo que um grafo proporciona uma representação visual que
trás vantagens na construção modelo matemático com vista a resolução do problema.

A análise de redes tem-se revelado útil na formulação e resolução de vários problemas

de pesquisa operacional, tais como rede de comunicação (estrada ou caminho de ferro,
energia eléctrica, telefones, relações de parentesco entre grupos de indivíduos, etc.),
planificação de actividades e alguns problemas de produção ou distribuição, pois a
representação de um sistema através de uma rede permite visualizar de uma maneira
clara as relações entre os seus elementos.

Os problemas de fluxo em rede esta associado questões que envolvem distancia como a
forma mais curta de ir de um local ao outro, ou ainda como ligar um conjunto de
localidades entre si com a menor distancia possível. O estudo das redes poderá ir mais
longe do que isto, como os casos dos problemas a serem estudados neste tema:

O problema de árvore geradora mínima

Este tipo de problema acontece quando se pretende instalar uma rede de distribuição gás
natural, água, electricidade, telefone de modo a que todos os beneficiários fiquem
ligados entre si ou seja que as condutas a instalar tenham o menor comprimento
possível, de modo a minimizar os custos.

O problema do caminho mais curto

Este é um caso típico da deslocação de uma localidade A para uma localidade B,

percorrendo a menor distância possível, sabendo que há um determinado número de
escalas alternativas a satisfazer, é um problema típico em que se pretende determinar o
caminho mais curto a efectuar entre a origem e o destino.

Problema do fluxo máximo

Estamos diante de um problema de um fluxo máximo quando se pretende determinar a

quantidade máxima de um dado produto que é possível transportar de uma origem para
um.

23
O problema do fluxo do custo mínimo

Se pretendemos transportar uma quantidade fixa de um produto da origem para um

destino da forma mais barata possível, estamos diante de um problema de um fluxo
mínimo.

Os problemas de optimização em rede são situações particulares dos problemas de

optimização lineares, podendo desta forma ser valido uma validação do algoritmo da
simplex.

O algoritmo utilizado é conhecido por simplex para redes. No entanto a especificidade

do problema de redes, fez com que se tenham desenvolvido algoritmos mais eficientes
para resolver cada tipo de problema quatro citados

2. TEORIA DOS GRAFO

Definição: Um grafo G, em um conjunto finito V de pontos a que chamamos vértice,

nós ou nodos, e um conjunto A de linha, a que chamamos de arcos, ligações ou ramos,
que ligam todo ou alguns desses pontos. Se…

Nota: Podemos identificar qualquer arco a (ligação ou ramo) atribuindo-lhe um nome ou

letra ou através do vértice de onde parte e do vértice onde termina, colocando um par
ordenado a=(…) ou apenas a= (i.f). Quando i=f o arco denomina-se lacete.

Definição: um grafo considera-se orientado se lhe é associado um sentido. Os sentidos

são esquematicamente representados por setas. A seta do arco (v1, v2) significa que este
arco é dirigido de v1 para v2.

Nota: Um grafo é orientado se todos os seus arcos forem orientados e não orientados
quando os seus arcos não apresentam sentidos. Os arcos não orientados denominam-se
também por arestas.

Se o grafo tem arcos e arestas então diz-se um grafo misto

EXEMPLO: Considerem o grafo formado pelo conjunto dos vértice v =

{1,2,3,4,5,6,7,8} e pelo conjunto das ares A =
{(1,2),(1,3),(1,4),(2,6),(2,7),(3,6),(4,5),(5,6),(5,8),(6,7),(6,8),(7,8)}

Graficamente
2 7

1 3 6 8

4 5
24
Gráfico orientado
2 5

3
1 6
8

4
7

Grafo não orientado

2 5

1 6 8
3

4 7

Definição: denominam-se antecessores de um vértice v todos os vértice donde partem

ares que terminam em v, são todos os vértices em que terminam ares que começam com
vértice v.

Definição: Dos ares consideram - se adjacentes ou conexos se possuírem um vértice.

EXEMPLO: (1ª figura)

Antecessor de 5 ={4}; porque o vértice 4 é o único de onde sai um arco que termina no
vértice 5.

Sucessor de 5 = {6,8}; porque do vértice 5 saem arcos que terminam nos vértices 6 e 6.

Os ares (1,2) e (6,8) são conexos porque possuem o vértice 3 em comum.

Os ares (2,7) e (6,8) são desconexos.

Definição: Chama-se cadeia entre um vértice inicial i e um vértice final f, a uma

sequência de ares ligam estas dos vértices.

Nota: Não é necessário que os arcos que os arcos estejam todos orientados no mesmo
sentido. Os que estiverem orientados de i para f designam-se por ares directo enquanto

25
de f para i chamam-se ares inválidos. Se o vértice inicial for também o vértice final ou
seja de sairmos de um vértice e voltarmos a ele, então estaremos diante de ciclo.

EXEMPLO: Consideremos o grafo da figur

2 4 6

1 8

3 7
5

Podemos identificar uma cadeia entre os vértices 1 e 8

4 6
2

8
1

3 5 7

Podemos identificar uma cadeia entre os vértices 1 e 8

OBS: O arco (5,7) esta a ser utilizado no sentido inverso ao da sua orientação.

Podemos também encontrar ciclos

5 6
2

1 8

3 4 7

OBS: Não é possível sair do sair do vértice 1 e voltar posteriormente ao mesmo sem
utilizar pelo menos um dos arcos ao sentido inverso.

26
NOTA: Se numa cadeia, os arcos estiverem todos orientados no sentido de i para f,
obteremos um caminho de i para f. Se o vértice inicial do caminho for também o vértice
final, termos um circuito

EXEMPLO: (Neste caso não temos circuito).

4 6
3

8
1

2 5 7

Definição: Um grafo denomina-se conexo ou fracamente conexo se, para todo par do
vértice do grafo existir pelo menos uma cadeia interligando o par, ou seja se for possível
deslocar-se de um vértice qualquer para um outro através de uma cadeia.

Definição: Um grafo denomina-se fortemente conexo se for sempre possível estabelecer

um caminho entre quaisquer dos seus vértices.

NOTA: Uma forma mais intuitiva de concluir sobre a conexidade de um grafo é não
permitindo “linha de vértices “EXEMPLO:

Grafo conexo Grafo desconexo

8 3
2 4

1
2

3 2
3 5

NOTA: Podemos concluir que, os conceitos de cadeia ciclo ou conexidade nos grafos
não orientados correspondem os conceitos de caminho, circuitos e conexidade forte nos
grafos orientados.

Definição: Um grafo diz-se completo se cada dois vértices esta ligada por um arco.
Assim o diagrama de um grafo completo com N vértices tem N(N-1) arcos pois deve-se
considerar que cada um dos restante (N-1 ) vértices. Se o grafo for não orientado divide-

27
 se estes valor por dois, porque a aresta esta entre um vértice i e um vértice f substitui os
arcos (i,f) e (f,i).

EXEMPLO

2 3
Vértice: {1,2,3,4}

4(4-1) = 12 Arcos

⟹ (1,2)(2,1)(1,3)(3,1)(1,4)(4,1)

1 4

(2,3)(3,2)(2,4)(4,2)(3,4)(4,3)

Definição: Denomina-se grafo parcial ao grafo cujo vértice é todos os elementos de um

subconjunto de A intuitivamente, podemos dizer que um grafo parcial resulta do grafo
inicial suprimindo alguns arcos.

Definição: Subgrafo é o grafo cujos vértices são elemento de um subconjunto de V e os

arcos são elemento de A que tem ambos os extremos nestes subconjunto isto é um
subgrafo resulta do grafo inicial qual se suprime um ou mais vértices e os arcos de que
estes vértices são extremos.

NOTA: Se consideramos em simultaneamente duas definições anteriores obteremos um

sub grafo parcial.

EXEMPLOS

Grafo parcial (partindo da figura)

2 5

6 8
1 3

4 7

28
O grafo parcial é gerado pelo subconjunto:

𝐴1 = {(1,2)(1,3)(1,4)(2,7)(3,6)(4,5)(5,8)(6,7)(6,7)(7,8)

Subgrafo (da Figura * )

𝑉1 = {1,2,3,6}
3

1 4
2

Subgrafo Parcial

Subgrafo parcial gerado por 𝑉1 = {1,2,3,6 }e 𝐴2 = {(1,2), (1,3), (3,6), (6,7)}

1
2 4

𝐴2 = {(1,2), (1,3), (3,6), (3,6)}

3. Noção de rede
Definição: Uma rede é um grafo onde existem valores associados a todos os arcos ou
arestas. A estes valores dá-se o nome capacidades e podem representar custos, distancia,
tempo volumes, etc.

EX:

12 20
10 26
17
2
33

33 17 6
17 3

3
15
21
15
20

10
29
REDE OREITADA 12
10
2 4 7 26
17
10 8 8
1 3
4
8
21 3 5 6 6
15 6 10
6
REDE NÃO ORIENTADA
8
NOTA: Em relação ao valor que apresentam as capacidades, por exemplo, a capacidade
17 associada ao arco (1,2) poderá apresentar o caudal máximo permitido ao canal fluvial
entre as barragens situadas nos locais correspondentes a, vértices 1 e 2 enquanto a
capacidade 8 associada a aresta (5,7) poderá representar o tempo que um carteiro leva a
distribuir correio em cada um dos sentidos da rua que se situa entre os cruzamentos
representados pelas vértices 5 e7.

Para simplificar as notações utilizadas em diante nos problemas que estudaremos,

assumiremos sem perder a generalidade que o vértice inicial das redes em estudo será
identificado com o número 1 sendo os restantes vértices identificados com os números
2,3,4…, N.

4. O problema da àrvore geradora de custo mínimo

As aplicações práticas deste problema são diverso em exemplo disso será a constituem
de uma infra-estrutura que sirva um conjunto de localidades. Não é necessário existir
uma ligação directa entre cada par de localidades, mas é obrigatório estabelecer uma
ligação de qualquer uma localidade para qualquer outra. Se tivermos em conta que
quanto for maior a extensão total da infra-estrutura maior será a quantidade de material
a utilizar maior será o número de horas maquinas necessário este facilmente se perceba
que o objectivo principal neste caso é tentar minimizar o comprimento total.

O problema da árvore geradora de custo mínimo assegura a construção de uma árvore

geradora cujo comprimento seja mínimo

Problema:

A empresa REDE VIVA LDA, precisa determinar sob que ruas deverão instalar cabos
telefónicos para ligar todas as estações usando o menor comprimento total de cabos. A
figura abaixo ilustra as 8 estações e o plano de ruas. Sobres cada aresta está
representado o comprimento de cabos necessário para efectuar a respectiva ligação.

12 20
17 4 26
17 2 7
4 8

1
30
8 6 15
3 5
2
3 15
Definição: Chama-se arvore (T) a um grafo com N vértice que seja conexo e sem ciclo,
ou ainda:

→ T é um grafo conexo com (N – 1) arcos

→ T é um grafo com (N – 1) arcos e seu ciclo → T não terá ciclos mas adicionando
qualquer arco novo a T, resulta num grafo com exactamente um ciclo.

→ T tem uma única cadeia a ligar cada par de vértice.

Definição: Dado o grafo G ≡ (V, A) com N vértices, chama-se árvore geradora de G ou

árvore de suporte G, a um grafo parcial de G que construa uma árvore

Vejamos exemplo de arvores geradoras de uma rede, em que passamos a trabalhar na

medida em que associamos capacidades as arestas dos grafo
12 26
2 4 7
17

1 4 8

3 5 6
21 15

10

NOTA: A partir da def de árvore geradora temos aqui de facto um grafo parcial do
esquema anterior (aumentará todos os vértices e considera apenas algumas arestas).
Verifica-se também que o grafo é conexo (não existem ilhas de vértices) e sem ciclo e
devera ter N – 1 = 8 -1 = 7 arestas.

Podemos constatar também que existe uma cadeia entre qualquer par de vértices ou seja,
que é possível encontrar uma ligação de um qualquer vértice para qualquer outro que é
essa ligação é única.

Ao somar as capacidades das arestas utilizadas nesta árvore

6 obtêm-se a suas
capacidades total: 17+21+12+4+10+26+15=105 3

2º
12
4
2 7
17 16

3 8
1 8

15
3 5 31 6
10
17+3+12+15+10+8+26=91

20
2 4 7

3 4
1 8
17

21 10 15
3 5 6

21+3+17+20+4+10+15=90

12
2 4 7
17

8 4
1 3 8

5 6
3
10

17+ 3+12+8+10+4+15=69

NOTA: Dado um grafo G ≡ (V,A) com capacidade associados as arestas ou arcos,

chama-se arvore geradora de custo mínimo a qualquer geradora de G cuja a soma das
capacidades seja a mínima.

5. Formulação do problema
Este problema pode ser formulado em P.L.. seja uma variável de decisão que toma
valor 1 se a aresta (i;j) esta incluída na arvores e o valor o caso contrario.

As restrições deverão transmitir as seguintes ideias:

Não existe vértices que não estejam ligados.

O número de aresta a ser colocado deve ser N – 1.

32
Não devem existir ciclos. Se Cij for o custo associado a aresta (i,j) teremos:

Minimizar

𝑛 𝑛

𝑍=∑ ∑ 𝐶𝑖𝑗 𝑥𝑖𝑗

𝑖=0 𝑗(𝑖,𝑗)𝐸𝐴

𝑛 𝑛

𝑆. 𝐴: ∑ 𝑥𝑖𝑗 + ∑ 𝑥𝑖𝑗𝑖 ≥ 1, ∀ 𝑖 = 1, … , 𝑁
𝑗:(𝑖,𝑗)𝐸𝐴=0 𝑗:(𝑗,𝑖)𝐸𝐴=0

𝑛 𝑛

∑ ∑ 𝑋𝑖𝑗 = 𝑁 − 1
𝑖=1 𝑗:(𝑖𝑗)𝐸𝐴=

𝐹𝐷 ∑ ∑ 𝑋𝑖𝑗 ≤ |𝑠| − 1 → 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑜 𝑆 ⊆ 𝑉

𝑖𝐸𝑆 𝑗:(𝑖𝑗)𝐸𝐴

𝑥𝑖𝑗𝐸 (0,1), ∀𝑖𝑗 = 1, … , 𝑁: (𝑖, 𝑗)𝐸𝐴

O primeiro conjunto de restrições garante que para cada um dos vértices, o número total
de arestas que, “sai” e que “entra” nesse vértice é no mínimo uma, ou seja, existe para
cada um dos vértices pelo menos uma aresta considerada na árvore, isto é não existe
vértice que não estejam ligados.

O segundo conjunto de restrições exige que sejam colocados exactamente N – 1 aresta e

o terceiro conjunto garante a não formação de ciclos.

Embora o problema assim formulado possa ser resolvido por um algoritmo de P.L,
como o simplex, a estrutura particular dos problemas de redes permite o
desenvolvimento de algoritmo específico para o efeito.

33
 6. ALGORITMO DE KRUSKAL

O algoritmo do KRUSKAL desenvolve a árvore geradora de custo mínimo permitindo

de uma rede com todos os vértices e sem aresta colocadas, ordenando-as por ordem
crescente de capacidades.

Em seguida vai introduzindo as arestas por uma nas árvores desde que a sua inclusão
não origine a formação de ciclos com as arestas já colocados. O algoritmo termina
quando estiverem N – 1 aresta colocadas.

Seja o caso da REDE VINA:

12 20
2 4 15
7
17 54 26

8
3 17
1
8
15
21 3 5 6
15 10
Sendo a rede composta por 8 vértices a arvore geradora terá N – 1 = 8 – 1 = 7 vértices.

1º Passo: Ordenar as aresta por ordem crescente das capacidades. Seja tabela

AREST CAPACIDAD ARESTA CAPACIDADE

A E
(6,8) 15
(2,3) 3
(1,2) 17
(4,6) 4
(3,4) 17
(5,7) 8
(4,7) 20
(5,6) 10
(1,3) 21
(2,4) 12
(7,8) 26
(3,5) 15

2º Passo: Iniciar a construção da árvore colocando as arestas na ordem dada pela tabela
anterior.

2.1.

34
 2 4 7

1 8

3 5 6

Capacidade: 3

2.2.

2 4 7

1 8

3 5 6

Capacidade 3+4=7

2.3. Segundo o raciocínio análogo, colocam-se as três arestas seguintes: (5,7) (5,6) e
(2,4). Deve-se ter atenção que, embora passe a existir um cruzamento entre as aresta
(5,7) e (4,6) isto não constitui um ciclo e depende apenas da posição relativa dos
vértices, pois bastará que o vértice 7 se encontrasse abaixo do vértice 5 para que
deixasse de existir esse cruzamento assim sendo, teremos

12
2 4 7
8

1 8
3 4

3 6
5

Capacidade: 7+8+10+12=37

2.4. A sexta aresta a ser colocada seria a (3,5) entretanto ela dá origem ao surgimento de
um ciclo (repetir a figura). Logo, ignora-se esta aresta e colocamos a aresta seguinte
também com a capacidade 15 a aresta (6,8). Teremos então:
12

35
 2 4 4 7

8
1
3 8

5 6 15
3
10
Capacidade: 37+15=52

3º Passo:

Estas colocadas 6 arestas. A próxima aresta a ser colocada será a aresta (1,2) com
capacidade 17 e que não fecha nenhum ciclo. Tratando-se da 7ª aresta, obtemos a árvore
geradora de mínimo custo com capacidade igual a 52+17=69.

Com a relação de N – 1 arestas a arvore geradora esta completa, traduzindo o final do

algoritmo
7
2 4

8
1

3 5 6

7. Algoritmo de PRIM
Uma das formas de aplicação do algoritmo de PRIM consiste na construção de uma
matriz triangular inferior cujo elemento são as capacidades entre os vértices (como os
mapas das estradas).

O facto de estarmos diante de uma rede não orientadas origina a utilização a aresta (i,j)
no sentido de i para j ou de j para. A matriz das distâncias resultante é uma matriz
triangular inferior

36
 31

41

1 81

2 121

3 21 101

4 17 151

5 151

6 171

7 20

8
26

1 2 34 5 6 7 8

1º Passo: escolhe-se um vértice qualquer. Ex. Ver. 5

2º Passo: cortar a linha e a coluna do vértice 5, isto é seleccionar todas as ligações que
envolvem o vértice 5. Entre os elementos cortados uma vez escolhesse o menor, ou seja
escolhe-se a aresta adjacente com o menor comprimento, neste caso =8, na ligação com
vértice 7.

3º Passo: assinala-se essa aresta com um círculo e cortam-se a linha e a coluna do

vértice assinalado de forma a identificar as novas arestas que se ligam a estrutura criada.

37
4º passo: mais uma vez escolhe-se o mínimo entre os elementos cortados uma vez, que
neste caso corresponde ao 10 na ligação entre os vértices 5 e 6.

5º Passo: analogamente prossegue o processo. No entanto, neste caso, cortando a linha

do vértice 3 determina-se o menor dos elementos cortados é o 15 da ligação entre os
vértice 5 e. Sendo este elemento já cortado duas vezes implicaria formar um ciclo.

Teremos então que escolher o 2º mínimo dos elementos cortados. e, também de valor
15, más é a ligação entre os vértices 6 e 8.

6º Passo: mais uma vez se cortam a linha e coluna do vértice 8 e determina-se o menor
dos elementos cortados uma vez que corresponde ao 17 da ligação dos vértices 2 e 1.

Cortam-se as linhas e as colunas do vértice um e conclui-se que árvore geradora mínima

está terminada a partir do momento em que todos os vértices foram cortados em linhas e
colunas.

→ Determina-se então as ligações que formam a árvore geradora do aresto mínimo, que
são os assinalados.

17+3+12+4+10+8+15=69

8. O problema do caminho mais curto

O problema do caminho mais curto consiste na determinação do caminho de
comprimento mínimo entre dois vértices. Eles aparecem associados a redes orientadas.

No entanto, também podem ser aplicadas a redes não orientadas, pois, uma rede não
orientada pode ser considerada como um caso especial de redes orientadas fazendo
corresponder a cada vértice um par arco orientados em sentidos opostos.

PROBLEMA

A empresa, REDE VIVA pretende agora encontrar o caminho mais curto entre a sede da
empresa (vértice 1) e o centro de distribuição (vértice 8) através do sistema de ruas
assinalado na figura abaixo.

Os valores dos arcos representam as distancia.

12 20
2 4 7 26
4
17 8 8
1 3
4 4

15
3 5 6
15 10

38

3
Este problema pode ser formado em programação linear e tal como no caso da arvore
geradora de custo mínimo, que define as variáveis de decisão como sendo a opção de,
inclusão ou não de cada uma das ligações (i, j) no caminho de custo mínimo ou seja,
neij é uma variável que tenha o valor 1 se o arco (i,j) está incluído no caminho mais
curto entre o vértice final N e toma valor 0 (zero) caso contrario.

As restrições deveram transmitir as seguintes ideias:

O caminho mínimo tem inicio no vértice 1 que representa a origem.

O caminho mínimo termina no vértice N que representa o destino.

O caminho mínimo é constituído por uma sequência de arcos onde cada um deles
começa um vértice e acaba noutro.

Se cij for o comprimento do arco (i.j) o problema pode ser formulado da seguinte
forma:
𝑁 −

𝑀𝐼𝑁𝐼𝑀𝐼𝑍𝐴𝑅 𝑍 = ∑ ∑ 𝐶𝑖𝑗 𝑥𝑖𝑗

𝑖=1 𝑗:(𝑖,𝑗)𝐸𝐴

𝑆𝑢𝑔𝑒𝑖𝑡𝑎: ∑ 𝑋𝑖𝑗 − ∑ 𝑋𝑖𝑗 = 1

𝑗:(𝑖;𝑗)𝐸𝐴 𝑗:(𝑗,𝑖)𝐸𝐴

∑ 𝑋𝑖𝑗 − ∑ 𝑋𝑗𝑖 = 0, ∀𝑖 = 2, … , 𝑁 − 1
𝑗:(𝑖,𝑗)𝐸𝐴 𝑗:(𝑗,𝑖)𝐸𝐴

∑ 𝑋𝑁𝑗 − ∑ 𝑋𝑗𝑁 = 1
𝑗:(𝑁,𝑗)𝐸𝐴 𝑗:(𝑗,𝑁)𝐸𝐴

𝑋𝑖𝑗 𝐸 {0,1}, ∀𝑖, 𝑗 = 1, … , 𝑁: (𝑖𝑗)𝐸𝐴

A primeira restrição garante que o numero de arcos que sai e o número de arcos que
entra no vértice inicial 1 e1; A terceira restrição garante que a diferença entre o número
de arcos e o número de arcos que entra no vértice 1 é -1.

O segundo conjunto de restrições garante que em todos os outros vértices a quantidade

total de arcos que lá entram no caminho mais curto é igual a quantidade total de arcos
que lá saem.

É a necessidade de minimizar uma combinação linear dos arcos que forem utilizados
que nos garante que só teremos um arco a sair ou a entrar em cada vértice.

39
Se consideramos que não estão definidas quaisquer arco a ir dar ao vértice 1 (o que
equivale a ter 𝑋𝑘1 = 0, ∀ 𝑘 = 1, … , ) ou quaisquer outro arco a sair do vértice N (o
que significa ) a ter X 𝑛 𝑘 = 0 ∀𝑘 = 1, … , 𝑁 a formulação simplifica-se da seguintes
forma:
𝑁 −

𝑀𝐼𝑁𝐼𝑀𝐼𝑍𝐴𝑅 𝑍 = ∑ ∑ 𝐶𝑖𝑗 𝑥𝑖𝑗

𝑖=1 𝑗:(𝑖,𝑗)𝐸𝐴

𝑆𝑢𝑔𝑒𝑖𝑡𝑎: ∑ 𝑋𝑖𝑗 − ∑ 𝑋𝑖𝑗 = 1

𝑗:(𝑖;𝑗)𝐸𝐴 𝑗:(𝑗,𝑖)𝐸𝐴

∑ 𝑋𝑖𝑗 − ∑ 𝑋𝑗𝑖 = 0, ∀𝑖 = 2, … , 𝑁 − 1
𝑗:(𝑖,𝑗)𝐸𝐴 𝑗:(𝑗,𝑖)𝐸𝐴

∑ 𝑋𝑗𝑁 = 1
𝑗:(𝑁,𝑗)𝐸𝐴

𝑋𝑖𝑗 𝐸 {0,1}, 𝑖, 𝑗 = 1, … , 𝑁: (𝑖𝑗)𝐸𝐴

RESOLUÇÃO DO PROBLEMA

12 20
4
17 2 7
26

1
3 17 4 8

3 5 8
21
6 15
15 10

→ Seja o caminho C = {(1,2), (2,4), (4,7), (7,8)}. A ligação entre os vértices 1 e 8 terá o
comprimento M= 17+12+20+26=75.

→ Seja o caminho C= {(1,3), (3,4),(4,6),(6,8)} cujo o comprimento M = 21+17+4+15

=57.

Esta seria uma maneira de resolver este problema enumerando todos os caminhos em
escolher o que apresentam menos comprimentos. Podemos concluir facilmente que esta

40
pratica é complicada e ……. a medida que aumenta o numero de vértices ou de arcos de
rede.

9. ALGORITMO DE DIJKSTRA

Este algoritmo determina o, caminho mais curto entre o vértice inicial i (chamamos-lhe
1) e todos os vértices de rede com comprimento não negativo. Neste algoritmo, atribui-
se uma etiqueta (sinal qualquer) permanente a qualquer vértice W da rede quando
houver a certeza de que já obtivemos o caminho mais curto entre o vértice inicial 1 e o
vértice 20.

Assim sendo, vamos definir alguns vértice que nos permitirão facilidade e rapidez na
aplicação do.

JC(j) → é o comprimento do caminho mais curto entre o vértice inicial 1 e o vértice j,

obtido até ao momento. Se considerarmos C𝑎 𝑏 o coprimento do arco (ou aresta) entre
o vértice a e b, isto permitimos definir que no inicio JI(1) = 0 ou seja 1 é o vértice inicial
logo o comprimeto do caminho mais curto entre o vértice inicial e o vértice 1 é igual a
zero.

𝐶1𝑗 → 𝑠𝑒𝑗é 𝑢𝑚𝑠𝑢𝑐𝑒𝑠𝑠𝑜𝑟𝑑𝑖𝑟𝑒𝑐𝑡𝑜𝑑𝑜𝑣𝑒𝑟𝑡𝑖𝑐𝑒 1

JC(j) = {
+ ∞ → 𝑛𝑜𝑐𝑎𝑠𝑜𝑐𝑜𝑛𝑡𝑟á𝑟𝑖𝑜
P(j) → é um vértice antecessor do j no caminho mais curto entre 1 e j. Assim sendo, no
inicio teremos:

*P(1) = (por começar, considera-se que 1 é antecessor de 1)

1 → 𝑠𝑒 𝑗 é 𝑢𝑚 𝑠𝑢𝑐𝑒𝑠𝑠𝑜𝑟 𝑑𝑖𝑟𝑒𝑐𝑡𝑜 𝑑𝑜 𝑣𝑒𝑟𝑡𝑖𝑐𝑒 1

*P(j) = {
0 → 𝑛𝑜 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟á𝑟𝑖𝑜.
Este algoritmo, pode ser aplicado directamente sobre a rede, mas existe uma aplicação
sobre tabela que torna mais fácil a própria resolução. Representam-se todos os vértices j
em linha e para cada interacção do problema e actualizam-se todos os vértices P(j) e
𝜋(j) voltemos a rede:

12
4 20
2 7
17 26
4
1
3 8
17

21 15
3 5 6
15
41
 10

Determinemos o caminho mais curto entre os vértices 1 e 8.

No inicio temos: 𝜋(1) = 0 𝑒 𝑃 (1) = 1

Isto significa que já obtivemos o caminho mais curto entre 1 e 1. Etiqueta-se

permanentemente o vértice com (*) e em seguida pesquisamos todos os vértice sucessor
do vértice 1. São os vértices 2 e 3.

Claramente se verifica que o caminho mais curto entre eles é da ligação entre o vértice 1
e 2 logo 𝜋(2) = 17. Sabendo que o vértice antecessor de 2 nesse caminho é o vértice 1,
logo P(2) =1.

De forma análoga temos que o caminho mais curto 1e 3 é o da ligação directa entre eles
donde 𝜋(3) = 21 𝑒 𝑃(3) = 1

Aos restantes vértices que não são sucessor directo de 1 consideramos não termos
obtidos ainda um caminho até eles e assim atribui-se o valor + ∞ ao respectivo 𝜋 e o
valor 0 (zero) ao respectivo P. vejamos a tabela:

vert. 1* 2 3 4 5 6 7 8

Vect

𝜋 0 17 21 +∞ +∞ +∞ +∞ +∞

P 1 1 1 0 0 0 0 0

Em seguida escolhe-se o vértice que se encontra mais perto de1 ou seja, entre todos os
que ainda não têm etiqueta permanente aquele cujo 𝜋 é o mínimo do 𝜋´𝑠 (17 para o
vértice o que se assinala radiado) e etiqueta-se o vértice 2 com (*). Isto significa que
está encontrado o caminho mais curto entre 1 e 2.

Como certificar?

Qualquer outro caminho passaria obrigatoriamente por outro vértice, no caso e 3, que
sabemos não se encontra a uma menor distância é a que liga 1 e 2. Desta forma não é
possível encontrar outro caminho mais curto. Mesmo que a distância entre 1 e 3 fosse

42
igual a de 1e 2 e tivemos que ir pelo vértice 3, para chegarmos ao 2 teríamos ainda a
distancia entre 3 e 2. Assim o estado da tabela será:

Vert. 1* 2* 3 4 5 6 7 8
vect
𝜋 ⑰ 21 +∞ +∞ +∞ +∞ +∞ +∞
P 1 1 0 0 0 0 0 0

A partir do último vértice e etiqueta 2 podemos ir para os vértices 3 e 4 comprimentos:

Arco (2,3) 𝜋 (2) + 𝐶2 3

=17 + 3

=20

Arco (2,4): 𝜋 (2) + 𝐶 2 4

= 17 + 12

=29

Consultando a tabela podemos concluir que o caminho até o vértice 3 tinha como
antecessor o vértice 1 e 𝜋(3) = 21. Assim como o valor agora obtido é menor 𝜋(3) =
20 ao anterior, selecciona-se o novo caminho e actualiza-se este mesmo 𝜋 = 20. Isto
significa que o antecessor do vértice 3 passa a ser o 2 logo P(3)=2.

Em relação ao vértice 4, segundo a tabela não há ainda caminho para o vértice 4. O

caminho que parte do vértice 2 certamente é melhor pois 29 é menor que + ∞. O quadro
apresenta-se desta forma:

Vert. 1* 2* 3 4 5 6 7 8
vect
𝜋 17 21 +∞ +∞ +∞ +∞ +∞ +∞
P 1 1 0 0 0 0 0 0
𝜋 ⑳ 29 +∞ +∞ +∞ +∞
P 2 2 0 0 0 0
Etiqueta-se o vértice 3 na rede e na tabela com (*) e podemos a partir dele ir para o
vértice 4 e 5.

O caminho mais curto de 1 a 4 passando por 3 seria este composto pelo caminho curto
de 3 e pelo arco (3,4).

𝜋(3) + 𝐶34 = 20 + 17 = 37

Entretanto, existe já outro caminho de 1 a cujo 𝜋 = 29 logo não nos interessa este
caminho agora obtido. Para o vértice 5 não existe ainda caminho mais curto a partir de
1, por isso o caminho que chega ao 5 tendo como antecessor o 3, será o caminho mais

43
curto até 3 acrescido do arco (3,5) cujo comprimento determina-se: 𝜋(3) + 𝐶35 = 20 +
25 = 35

Comparando com o actual 𝜋(5) = +∞, decidimos actua 𝜋(5) é o antecessor do vértice
5 passa a ser o 3 ou seja: P(5)=. Eis o quadro actual:

Vert. 1* 2* 3 4 5 6 7 8
vect
𝜋 17 21 +∞ +∞ +∞ +∞ +∞ +∞
P 1 1 0 0 0 0 0 0
…. … … … … … … … …

𝜋 35 +∞ +∞ +∞
29
3 0 0 0 +∞
P 2 0

Repetindo o raciocínio, mais uma vez escolhemos o vértice que se encontra mais perto
de 1, ou seja aquele que apresenta o mínimo dos 𝜋´𝑠 entre os vértices não

Sabe-se que já foi obtido o caminho mais curto entre os vértices 1 e 4. Etiqueta-se o
vértice 4 e verifica-se que os sucessores são 6 e 7. Vejamos:

12 20
7
17 2 4 26

3
1 8
17

3 12 5 6
21 15
15
10

→ Para o vértice 6 o caminho mais curto imediatamente pelo vértice 4 será o caminho
mais curto até 4 nos arcos (4,6) o que originara um comprimento total: 𝜋(4) + 𝐶4 6 =
29 + 4 = 33. Comparando com o actual 𝜋(6) + ∞, preferimos o caminho novo e
actualizamos 𝜋(6) = 33 𝑒 𝑃(6) = 4

→ Para o vértice 7 faz-se o raciocínio análogo e actualizando 𝜋(7) = 4 + 𝐶4 7 = 29 +

20 = 49 𝑒 𝑃(7) = 4. O quadro toma a seguinte forma:

44
 Vert. 1* 2* 3 4 5 6 7 8
vect
… … … … … … … … …
𝜋 49 48
35
4 6
P 3

Neste momento nota-se que o vértice com o caminho mais curto desde o vértice 1 e o 6
com 𝜋(6) = 33 logo o vértice 6 etiquetado, sendo o vértice 8 o seu sucessor não
etiquetado.

2 4 7
12 20
17 26
4

1 3 8
17
12
21 3 5 6 15

15 10

O caminho mais curto para 8 tendo 6 por vértice antecessor será então o caminho mais
curto até 6 seguido do arco (6,8) com comprimento total𝜋(6) + 𝐶6 8 = 35 + 5 = 48.
Comparando com o actual comprimento 𝜋(8) = +∞, novamente preferimos o novo
caminho e actualizamos 𝜋(8) = 48 𝑒 𝑃(8) = 6, logo teremos:

Vert. 1* 2* 3 4 5 6 7 8
vect
… … … … … … … … …
𝜋 49 48
35
4 6
P 3

Actualmente, etiqueta-se o vértice 5. O seu sucessor não etiquetado é o 7. O

comprimento do caminho mais curto até ao 7 passando por 5 será:

45
𝜋(5) + 𝐶5 7 = 35 + 8 = 43; comparando com o actual 𝜋(7) = 49, verifica-se que é
preferível optar pelo novo caminho, actualizando 𝜋(7) = 43 𝑒 𝑃(7) = 5. Assim o
quadro terá a forma:

Vert. 1* 2* 3 4 5 6 7 8
Vect
… … … … … … … … …
𝜋 43 48
4 6
P

Etiqueta-se em seguida o vértice 7, porque o caminho mais curto e o seu sucessor não
etiquetado é o 8.

→ Comparando novamente 𝜋(7) + 𝐶7 8 = 43 + 26 = 69 com o actual vértice 8

chegamos ao fim do algoritmo.

O quadro completo terá a forma:

Vert. 1* 2* 3 4 5 6 7 8
vect
𝜋 0 ⑰ 21 +∞ +∞ +∞ +∞ +∞
P 1 1 1 0 0 0 0 0
𝜋 ⑳ 29 +∞ +∞ +∞ +∞
P 2 2 0 0 0 0
𝜋 29 35 +∞ +∞ +∞
29
P 2 3 0 0 0

49 46
35
𝜋 4 6

P 3
𝜋 48
35
P 5 6

𝜋
35
P 6

Resta apenas reconstruir o caminho mais curto donde o vértice 1 ate ao vértice 8. Para
isso verifica-se que o antecessor de 8 e 6 esse caminho é o 6, ou seja 𝜋(8) = 6, temos
assim:

46
 6 8

Vamos ao vértice 6 verificamos que o seu antecessor é o 4, ou seja: 𝜋(6) = 4, assim:

4 6 4

Qualogamente verificamos que o antecessor de 4 é o 2 e que o antecessor deste é 1:

𝜋 (4) = 2 (2) = 1. Assim o caminho mais curto entre os vértice 1 e 8 será:

1 2 3 4 5

Com o comprimento 𝜋(8) = 48, ou seja:

12
2 4 7 26
17
4

3 17 8
1

8
21 4
15
3 5 6
4 10
4

A tabela resultante da aplicação do algoritmo de DIJKSTRA permite não só obter o

caminho mais curto entre o vértice inicial e o vértice final, soma também obter o
caminho mais curto mais curto entre o vértice inicial e qualquer outro vértice.

NOTA: Para concluir pode-se dizer que, desde que a oferta total seja igual a procura
total, o problema de transportes tem sempre solução.

47
REFERÊNCIAS BIBLIOGRÀFICAS

1. Mirshawka Victor: Aplicações de Pesquisa Operacional, São Paulo 1981.

2. K. M. Anstreicher: Linear programming in Operations.SIAM Journal on

Optimization Vol. 9, N. 4, pp. 803-812, 1999.

3. Marcos Arenales Vinícios Armentano, Reinado Morabito e Horácio Yanasse :

Pesquisa Operacional para Cursos de Engenharia, 2006.

4. A. Arbel. Exploring Interior-Point Linear Programming: Algorithms

and Software. Foundations of Computing Series, MIT Press, 1993.

5. E. R. Barnes. A variation on Karmarkar’s algorithm for solving Linear

Programming problems Mathematical Programming 36 (1986) 174-182.

6. L. Boldrini, S. I. R. Costa, V. L. Figueiredo e H. G. Wetzler : Algebra

.3a edição, Harbra, 1984.

7. P. F. Bregalda, A. A. F. de Oliveira e C. T. Bornstein. Introdução á

Programação Linear. 3a edição, Campus, 1988.

8. I. I. Dikin. On the convergence of an iterative process. Upravlyaemye

Sistemy 12 (1974) 54-60. (Em Russo.)

9. V. G. Karmanov : Programação Matrmática. Moscovo 1989 ( em russo)

10. M. C. Goldbarg e H. P. L. Luna. Optimização combinatória e Programa

ção Linear: Modelos e Algoritmos. Campus, 2000.

11. P. E. Danko, A. G. Papov e T. Y. Kojevnikova : Matemática Superior “

Elementos de programação Linear” pp 271 – 293. 6ª edição 2007 ( em russo).

12. Miguel Loureiro : Investigação Operacional – Licenciatura terminal. 2006 –

Lisboa.

13. D. Goldfarb e J. K. Reid. A practicable steepest-edge simplex algorithm.

Mathematical Programming 12 (1977) 361-371.

14. N. Karmarkar. A new polynomial time algorithm for linear programming.

Combinatorica 4 (1984) 373-395.

15. E. L. Lima. Curso de Análise. Volume 2, Projeto Euclides,

IMPA/CNPq, 1981.

16. N. Maculan e M. V. F. Pereira. Programação Linear. Atlas, 1980.

17. N. Maculan. Programação Linear: Método do Simplex. Notas de aula

48
 em 1998.
18. C. A. de J. Martinhon. Programação Linear e Algoritmos de Pontos
Interiores: uma introdução a VI Semana do Instituto de Matemática e
Física da UFG (Minicurso), 27 páginas, 1991.

19. M. A. F. Menezes e R. Vieira. Um protótipo parcial para um sistema

de rações para bovinos. II Encontro de Matemaática Aplicada e
Computacional em Brasília, 2001.

20. M. A. F. Menezes. Um algoritmo de ponto-interior-inviável com

Complexidade O (pnl) iterações para programação linear. Tese de
Doutorado pela COPPE/UFRJ, defendida sob a orientação do
Professor Clóvis C. Gonzaga em 1998.

21. A. A. Namen e C. T. Bornstein. Uma ferramenta para avaliação de

Resultados de diversos modelos de otimização de dietas. Pesquisa
Operacional, v. 24, n. 3, p. 445-465, 2004.

22. R. J. Vanderbei, M. S. Meketon e B. A. Freedman. A Modification of

Karmarkar’s Linear Programming Algorithm. Algorithmica 1 (1986)
395-407.

23. Richard Brouson e Govindasami Naadimuthu : Investigação Operacional. 2001.

24. Manuela Hill, Mariana Marques dos Santos e Ana Líbano: Investigação
Operacional I, II, III. 2008

25. Manuel Alberto Ferreira e Isabel Amaral: Matemática – Programação

Matemática. Lisboa 1995.

26. Saul I. Gass : Programação Linear – Métodos e aplicações. 1971, Cidade do

México.

27. Jorge Guerreiro Alípio, Manuel Ramalhete, MacGrawn – Hill: Programação

Linear I, II. 1998

28. H. Libermen e MacGrawn – Hill :Introducion to operational research. 2009.

29. http//www.ericolisboa.eng.br

30. Documentos do XXIV Encontro Nacional de engenharia de produção – Brasil

2004.

31. Erico Lisboa : Apostila de Pesquisa Operacional – 2006

32. Fernando Martins : Introdução a Pesquisa Operacional – Teoria dos grafos –

2001.
33. BARBIER, Rene. A pesquisa-Ação. Tradução Lucie Didio. Brasilia: Liber
Livro Editora, 2004.159 p. Serie Pesquisa em Educação. v. 3.
49
34. BIEMBENGUT, Maria Salett; HEIN, Nelson. Modelagem Matemática no
Ensino. São Paulo: Contexto, 2000. 127 p.
35. CHESLT, Kenneth R; EDWARDS,Thomas G. Does This Line Ever
Move?:Everyday Applicationsof Operations Research. Emeryville, CA: Key
Curriculum Press, 2005. 144 p. ISBN: 1-55953-673-X.
36. COSTA, José de Jesus da. Tópicos de Pesquisa Operacional. 2. ed. Rio de
Janeiro: Editora Rio, 1975. p. 280.
37. LOESCH, Cláudio; HEIN, Nelson. Pesquisa Operacional: Fundamentos e
modelos. Blumenal: Editora da FURB, 1999. 270 p.
38. CUKIERMAN, Zigmundo Salomao. O modelo PERT/COM aplicado a
projectos: panejamento para o futuro. 7. ed. Rio de Janeiro: Reichman & Affonso
Editora, 2000. 216 p.
39. HAGUETTE, Teresa M. Frota. Metodologia Qualitativa da Sociologia. 2. ed.
Rio de Janeiro: vozes, 1990. 168 p.
40. HERNANDEZ Fernando. Transgressão e Mudança na Educação: os
projectos de trabalho. Tradução
Jussara Haubert Rodrigues. Porto Alegre: ArtMed, 1998.
41. HILLER, Frederick S; LIEBERMAN, Gerald J. Introdução à Pesquisa
Operacional. Tradução
42. Helena L. Lemos. 1. ed. Rio de Janeiro: Campus; São Paulo: Editora da
Universidade de São Paulo, 1988. 805 p. Tradução de: Introduction to Operations
Research. Third edition.
43. LOESCH, Cláudio; HEIN, Nelson. Pesquisa Operacional: fundamentos e
modelos. Blumenau: Editora da FURBE, 1999. 270 p
44. MATOS, João Filipe (Coord.); CAREIRA Paula Susana; SANTOS, Madalena
Pinto dos; AMORIM, Isabel. Modelação Matemática. Lisboa: Universidade
Aberta, 1995. 188 p.
45. MORGADO, Augusto C., WAGNER, Eduardo, ZANI. Sheila C. Progressão e
Matemática Financeira. Rio de Janeiro: Sociedade Brasileira de Matemática, 1993.
100 p. Colecção do Professor de Matemática.
4
6. MOURA, Dacio Guimarães de, BARBOSA, F. Barbosa. Trabalhando com
Projectos: panejamento e gestão de projectos educacionais. Petropolis, RJ: Vozes,
2006. 246 p.

50
47. PRADO, Darci Santos do. Programação Linear. Belo Horizonte: INDG
Tecnologia e Serviços Ltda, 2003, 206 p, il.: (Serie Pesquisa Operacional v. 1).
48. STEFE, Rodrigo. Projectos Pedagógicos Interdisciplinares Utilizando
Softwares de Produtividades: uma experiencia no ensino fundamental. Dissertação
(Mestrado Integrado Profissional em Computacao) – Universidade Estadual do
Ceara (UECE) e Centro Federal de Educacao Tecnologica do Ceara (CEFET-CE).
Ceara, 2006. 122 p.
49. STANGER, Luiz B. Nocoes Preliminares. Estabelecimento de um Programa de
Pesquisa ou de Producao. Tecnica para Montagem de uma Rede PERT. In: CPM-
CPM: tecnica de planejamento e controle. 1. ed. rev. Rio de Janeiro: Livros
Tecnicos e Cientificos, 1976 (cap. 1, 2 e 3).
50. THIOLLENT, Michel. Metodologia da pesquisa-ação. 13. ed. São Paulo:
Cortez, 2004. (Colecção temas básicos de pesquisa-acao).
51. TRALDI JUNIOR, Armando. Sistema de Inequações do 1º. Grau: uma
abordagem do processo
Ensino -aprendizagem focando os registos de representações. Dissertação (Mestrado
em Educação Matemática) -Pontifícia Universidade Católica de São Paulo, São
Paulo, 2002. 112 p. Impresso.
52. TRIVINOS, Augusto Nibaldo Silva. Introdução à Pesquisa em Ciências
Sociais: a pesquisa qualitativa em educacao. 1. ed. Sao Paulo: Atlas, 1928. 175 p.
53. SILVA, Carlos Alberto da. Uma metodologia para o ensino Operacional no
Ensino Técnico de Nível médio: Estudo de Caso na UNED- Imperatriz/MA.
Dissertação (Mestrado Integrado Profissional em Computação) – Universidade
Estadual do Ceara (UECE) e Centro Federal de Educação Tecnológica do Ceara
(CEFET-CE). Ceara, Fevereiro/2009. 54. WEISS, Neil; YOSELOFF, Mark.
Matemática Finita. Tradução Roberto Angelo de Barros Padilha. Inc. 1975; Rio de
Janeiro: Guanabara Dois: 1978. 584 p. Tradução de: Finite Mathematics.Worth
Publishers Inc.: New York.

51