Slides

Investigação Operacional
Técnicas de Investigação Operacional
Ano letivo 2020/2021
Francisco Saldanha da Gama

(Gabinete: 4.6.37A | E-mail: fsgama@ciencias.ulisboa.pt)
UNIVERSIDADE DE LISBOA | FACULDADE DE CIÊNCIAS IO / Técnicas de IO, 2020/2021
DEPARTAMENTO DE ESTATÍSTICA E INVESTIGAÇÃO OPERACIONAL
Programa
1. Introdução
2. Programação Matemática
3. Problemas em Grafos
4. Planeamento de projetos
5. Problemas de afetação
6. Gestão de stocks
Bilbliografia
F. S. Hillier, G. J. Lieberman, “Introduction to Operations Research”,
McGraw-Hill, 10ª Edição, 2014.
H. A. Taha, “Operations Research: An Introduction”, Prentice Hall,

8ª Edição, 2007.
W. L. Winston, “Operations Research: Applications and Algorithms”,

Cengage Learning, 4ª Edição, 2004.
Programa
1. Introdução
DEPARTAMENTO DE ESTATÍSTICA E INVESTIGAÇÃO OPERACIONAL 1. Introdução
O que é?
Um pouco de História…
➢ 2ª Guerra Mundial (Operações militares)
▪ Desenvolvimento do radar
▪ Controle de fogo antiaéreo
▪ Dimensionamento de frotas
▪ Deteção de submarinos
Slide 5
O que é?
➢ Anos 1950 a 1970 (Operações de caráter económico)

▪ Gestão de recursos materiais e humanos
▪ Planeamento da produção industrial

▪…
Slide 6
O que é?
➢ Anos 1980 e 1990 (Novos tipos de aplicações)

▪ Gestão de recursos naturais
▪ Saúde
▪ Aplicações financeiras (‘real options’)
▪…
Slide 7
O que é?
➢ Século XXI
▪ Implantação consumada nas mais diversas
áreas de atividade mas … novos desafios:
✓ Globalização;
✓ Desenvolvimento sustentável;
✓ Informação…ou dados?!
✓ Industry 4.0
✓ Internet of things
Slide 8
Economia
Matemática Investigação Gestão

Operacional
IO consiste na representação de sistemas reais através da utilização de

modelos matemáticos combinada com o uso de métodos quantitativos
(algoritmos) para a resolução de tais modelos, com o objetivo de otimizar.
Slide 9
Operational Research Society (UK)
“A IO consiste na aplicação do método científico a problemas complexos que

ocorrem na direção e gestão de grandes sistemas de homens, máquinas,
materiais e capital na indústria, no governo e na defesa. A abordagem
característica da IO consiste no desenvolvimento de um modelo científico do
sistema, incorporando fatores de probabilidade e risco, para prever e
comparar o efeito de diferentes decisões, estratégias e controlos. O objetivo é
o de auxiliar a gestão na tomada racional de decisões.”
INFORMS (USA) – Institute for the Operations Research and Management Sciences
“A IO dedica-se ao processo científico de decisão sobre a melhor conceção
e operação de sistemas homem-máquina, normalmente em condições que
requerem a alocação de recursos escassos.”
Slide 10
APDIO – Associação Portuguesa de Investigação Operacional
“Trata-se de uma ciência aplicada voltada para a resolução de problemas

reais, em que se procura trazer para o campo da tomada de decisões (sobre a
conceção, o planeamento ou a operação de sistemas) a atitude e os métodos
próprios de outras áreas científicas. Através de desenvolvimentos de base
quantitativa, a Investigação Operacional visa também introduzir elementos de
objetividade e racionalidade nos processos de tomada de decisão, sem
descurar no entanto os elementos subjetivos e de enquadramento
organizacional que caracterizam os problemas.”
Slide 11
Alguns sites sobre IO

Associação Portuguesa de Investigação Operacional
http://www.apdio.pt
The Association of European Operational Research Societies

http://euro-online.org
Institute for the Operations Research and Management Sciences

http://www.informs.org
The Operational Research Society

http://www.theorsociety.com
Diversos links na área de IO

http://opsresearch.com
Slide 12
Alguns sites sobre IO
Decision Support Puzzles for Applied Mathematicians

http://www.puzzlor.com/
http://www.scienceofbetter.org/
Slide 13
Exemplos de aplicação de IO
Problema do caixeiro viajante
Um estafeta tem que visitar clientes em cinco pontos distintos da cidade de
Lisboa: Lumiar, Parque Nações, Benfica, Algés e Docas.
As distâncias entre os diferentes pontos são as seguintes:

Distâncias (km) Lumiar P. Nações Benfica Algés Docas
Lumiar 0 6 5 12 14
Parque Nações 6 0 10 16 15
Benfica 5 10 0 7 12
Algés 12 16 7 0 4
Docas 14 15 12 4 0
Pretende-se determinar a ordem pela qual se devem visitar os clientes de

modo a minimizar a distância total percorrida. O ponto de partida do
estafeta é o Lumiar, pelo que pretende iniciar e terminar as suas visitas
nesse ponto
Slide 14
Lumiar
P. Nações
Benfica
Algés Docas
Slide 15
Um processo para obter ✓ Partindo do Lumiar vai-se para o ponto mais

uma solução admissível: próximo, que é Benfica;
✓ Daí, segue-se para o ponto mais próximo que
ainda não foi visitado, que é Algés;
✓ …
Distâncias (km) Lumiar P. Nações Benfica Algés Docas

Lumiar 0 6 5 12 14
P. Nações 6 0 10 16 15
Benfica 5 10 0 7 12
Algés 12 16 7 0 4
Docas 14 15 12 4 0
Slide 16
Lumiar 6
P. Nações
5
Benfica
15
7
Algés 4 Docas
Distância total percorrida: 37 km.
Slide 17
A solução anterior constitui uma solução admissível para o problema

Como ter a garantia de que se trata da melhor solução?
solução ótima!
Gerar todas as soluções admissíveis, calcular os respetivos custos e

selecionar a melhor ?!
Se o problema tiver n pontos
𝑛−1 ! Se a matriz de distâncias for simétrica

2 !!!
𝑛−1 ! Se a matriz de distâncias for assimétrica
Slide 18
Lumiar Lumiar Lumiar
EXPO EXPO EXPO

Benfica Benfica Benfica
37 57 43
Docas Docas Docas
Algés Algés Algés
EXPO EXPO EXPO

60 49 46
Docas Docas Docas
Slide 19
EXPO EXPO EXPO

52 58 44
Docas Docas Docas
EXPO EXPO EXPO

64 55 41
Docas Docas Docas
Slide 20
Problema de determinação de Rotas Ótimas
Uma fábrica de refrigerantes possui um depósito, D, a partir do qual fornece 4
clientes.
Num certo dia, as encomendas de cada um dos clientes são de 22, 25, 30 e 15
unidades respetivamente, para os clientes 1, 2, 3 e 4.
Os custos de transporte (em unidades monetárias apropriadas) estão
esquematizados no seguinte diagrama:
10
1 A capacidade máxima de cada um dos camiões
15
disponíveis no depósito é de 50 unidades. Os
D 12
2 camiões existentes no depósito são em número
suficiente para satisfazer os pedidos dos
14
8 8 clientes.
4
18
3 Pretende-se determinar, para o dia em causa, as
rotas que minimizam o custo total de transporte.
Slide 21
Neste exemplo pequeno podemos gerar todas as rotas admissíveis:
Rota 1: cliente 1 com uma carga de 22 unidades, custo 20 u.m.

Rota 5: clientes 1 e 2 com uma carga de 47 unidades, custo 37 u.m.
Rota 8: clientes 3 e 4 com uma carga de 45 unidades, custo total 40 u.m.
Slide 22
Soluções Admissíveis:
10 10 1 10
10 1 10 1
12 12 15
D D 2 D
2 2
12 12 12
8 14 14 8 14
8 8 8
4 14 4 3 4 14
3 18 3
Custo: 88 u.m. Custo: 84 u.m. Custo: 81 u.m.
10 1 10 1
15 10
14
D 2 D
14 3
12
14 12
8 8
4 3 4 2 Custo: 94 u.m.
18 26
Custo: 77 u.m.
Slide 23
Problemas de gestão florestal
menor unidade de uma floresta
Talhão ou unidade de gestão
sobre a qual se tomam decisões
A constituição dos diversos talhões tem a ver com múltiplos fatores:

➢ A pertença ou não ao mesmo dono
➢ Homogeneidade das árvores que o constituem
➢ Área total
➢…
Slide 24
Problemas que surgem na gestão de uma floresta
▪ Corte de madeira com fins lucrativos mas tendo em conta:

✓ O impacto ambiental de grandes cortes;
✓ Uma boa gestão da limpeza das florestas de modo a prevenir os
riscos de incêndio.
▪ Construção de vias de escoamento da madeira.
▪ Localização e construção de armazéns e de serrações.
▪ Instalação de postos de vigia para prevenção de incêndios.
▪ Gestão dos recursos de modo a proteger a biodiversidade.
▪…
Slide 25
Um problemas de corte de talhões numa floresta e

a b
g
Uma certa zona florestal foi dividida num conjunto c d f
de talhões.
Os talhões foram definidos de tal modo que podem ser completamente cortados.
O tamanho dos talhões foi definido a priori e limitado a determinado valor de
modo a que a clareira aberta não exceda um determinado tamanho (pois o corte
aumenta a erosão, o impacto visual e a destruição de habitats).
Pretende-se determinar os talhões a cortar numa dada altura de modo a
maximizar o lucro mas assegurando que dois talhões adjacentes não são
cortados nessa mesma altura.
Assume-se que a madeira obtida com o corte é vendida na totalidade.
Slide 26
Um problemas de corte de talhões numa floresta Talhão Lucro (u.m.)

a 20
b 15
e c 25
a b d 10
g
e 25
c d f f 15
g 20
A = {Talhões adjacentes}
= {{a,b},{a,c},{b,c},{b,d}, {b,e},{b,f},{c,d},{d,f},{e,f},{e,g},{f,g}}
Soluções Admissíveis
Cortar apenas um talhão: a, b, c, d, e, f ou g
Cortar 2 talhões não adjacentes: {a, d}, {a, e}, {a, f}, {a, g}, {c, e}, {c, f}, {c, g},
{b, g}, {d, e} ou {d, g}
Cortar 3 talhões não adjacentes: {a,d,e}, {a,d,g}
Slide 27
Um problemas de corte de talhões numa floresta
Cortar os talhões a lucro 20 u.m.

e
a b d lucro 10 u.m.
g
g lucro 20 u.m.
c d f
Lucro: 50 u.m.
Cortar os talhões a lucro 20 u.m.

e
a b d lucro 10 u.m.
g
e lucro 25 u.m.
c d f Lucro: 55 u.m.
Slide 28
Um problema de aquisição e substituição de equipamento
➢ Uma empresa que faz entregas ao domicílio pretende ter uma viatura
automóvel disponível durante os próximos dois anos.
➢ A empresa tem como opções unicamente dois modelos de viatura: A e B.
➢ Os custos de aquisição e operação / manutenção são diferentes.
➢ No fim do primeiro ano é possível trocar de viatura (ou por outra do mesmo
modelo ou por uma do outro modelo), obtendo-se uma receita proveniente da
venda.
➢ No fim dos dois anos a empresa venderá a viatura que tiver na altura.
Slide 29
Custo de operação e
manutenção Valor de venda
Preço de No 1º ano de No 2º ano de 1 ano de 2 anos de
aquisição atividade atividade atividade atividade
Modelo A 600 300 400 350 210
Modelo B 300 500 600 170 130
Questões:
1. Que viatura adquirir de início;
2. Deve trocar-se de viatura no fim do primeiro ano? Se sim, para que modelo?
Slide 30
Diferentes opções,
árvore de decisão:
Trocar por novo modelo A
Slide 31
Associando custos:
-210
-350+600+300
-350
-170
-130
-170+600+300
-350
-170
Slide 32
Associando custos:
400
550 -210
900 450 -350
-170
-130
600
800
730 -350
630 -170
Slide 33
1300
Melhor sequência de
decisões? 400
900 1450
550 -210 min{1090,1100,1180,
1270,1180,1260}
900 450 1350 -350
-170
1400
-130
600
800
800 1530
730 -350
630 1430 -170
Slide 34
1300
Melhor sequência de
decisões? 400
900 1450
550 -210 min{1090,1100,1180,
1270,1180,1260}
900 450 1350 -350
-170
1400
-130
600
800
800 1530
730 -350
630 1430 -170
Slide 35
Outra representação:
Modelo A
400 Com 2 anos
-210
Modelo A
Com 1 ano 550
900 Modelo A -350
Com 1 ano
450
-170
600 Modelo B
730 Com 1 ano
800
Modelo B -130
Com 1 ano
Modelo B
630 Com 2 anos
Slide 36
Fases de um projeto de IO
1. Identificação do problema;
2. Formulação de um modelo;
3. Validação do modelo;
4. Resolução do modelo;
5. Implementação;
Slide 37
Fases de um projeto de IO
Problema
Formulação
Modelo // validação do modelo
Algoritmo
Solução numérica
Implementação
Slide 38
Programa
1. Introdução
DEPARTAMENTO DE ESTATÍSTICA E INVESTIGAÇÃO OPERACIONAL 2. Programação Matemática
Modelar ou formular um problema ‘Tradução’ do problema para uma

linguagem’ mais conveniente para
análise
Representação Construção de um Outras

através de uma rede modelo matemático possibilidades…
Problemas de caminho ótimo O problema é expresso

Árvores de suporte ótimas através de um conjunto
... de expressões e
relações matemáticas
Slide 40
Conceitos iniciais
Problema de programação matemática
ou
Problema de otimização
Modelo matemático que se traduz pela otimização (maximização ou

minimização) de uma função real de variáveis reais ou inteiras sujeita a um
conjunto de restrições nessas variáveis
A Programação Matemática é uma área que se dedica ao estudo de problemas

deste tipo, nomeadamente
➢ Identificando as propriedades matemáticas do problema;

➢ Desenvolvendo e implementando algoritmos para resolver estes problemas;
➢ Aplicando estes algoritmos a problemas do dia-a-dia.
Slide 41
Conceitos iniciais
Forma geral de um problema de programação matemática:
minimizar f(x1,x2,...,xn)
sujeito a (x1,x2,…xn)  X X  n
f: n → 
maximizar f(x1,x2,...,xn)
sujeito a (x1,x2,…xn)  X
x1,x2,...,xn Variáveis do problema
f(x1,x2,...,xn) Função objetivo
(x1,x2,...,xn)  X Condição que representa as restrições do problema
Slide 42
Conceitos iniciais
Ponto (x1,x2,...,xn)  X Solução admissível
X Conjunto de soluções admissíveis
Exemplo
Maximizar z = 800x1+ 600x2 Função objetivo
sujeito a
5x1+ 3x2 ≤ 30
2x1 + 3x2 ≤ 18 (1,2)
Restrições
x1 + 3x2 ≤ 24
x1  0, x2  0 Uma solução
admissível
Slide 43
Conceitos iniciais
Programação Matemática, várias sub-áreas:
Programação não Linear;
Programação linear;
Programação linear Inteira Mista;
Programação linear Inteira;
Programação linear 0-1.
“Reconhecimento” de uma função linear:

função definida por um termo linear ou pela soma de vários termos
lineares, entendendo-se como termo linear, a multiplicação de uma
constante por uma variável.
Exemplos
2x 2x+3y Funções lineares
x2 x2+y2 Funções não lineares
Slide 44
Conceitos iniciais
➢ Define-se como problema de programação linear um problema de

programação matemática em que todas as funções envolvidas são
lineares e, além disso, todas as variáveis podem tomar valores
fracionários;
➢ Quando algumas variáveis podem tomar valores fracionários e as

restantes só podem tomar valores inteiros (continuando a assumir a
linearidade de todas as funções envolvidas) estaremos no domínio da
programação linear inteira mista;
➢ Numa situação em que todas as variáveis têm que tomar valores inteiros o
problema dir-se-á de programação linear inteira. Um caso particular deste
é aquele em que as variáveis só podem tomar os valores 0 ou 1, caso em
que o problema será classificado como de programação linear 0-1.
Slide 45
Modelação
Fases na formulação de um problema em programação matemática:
i. Compreender e definir bem o problema;
ii. Definir as variáveis de decisão (que decisão deve ser tomada),

especificando ainda as unidades em que são consideradas;
iii. Escrever as restrições do problema (utilizando as variáveis de decisão);
iv. Escrever a função objetivo (em função das variáveis de decisão);
v. Verificar a formulação, confrontando-a com o problema.
Slide 46
Modelação: exemplos
Programação não linear
Exemplo
Quais as dimensões (comprimento e largura) do retângulo que tem área
igual a 2m2 e perímetro mínimo?
Variáveis de decisão: x2
x1 Medida da base (metros)
x2 Medida da altura (metros) x1
Função objetivo:
2x1+2x2 Perímetro total
min z = 2x1+ 2x2
Restrições:
s. a: x1 x2 = 2
x1x2=2 Área total = 2m2
x1  0, x2  0
x10, x20 Medidas não negativas
Slide 47
Programação linear inteira
Exemplo
Um campista tem uma mochila com uma capacidade máxima de 6 kg.
O indivíduo tem um conjunto de objetos que gostaria de transportar na mochila.
O valor que o indivíduo atribui a cada objeto e o respetivo peso são dados por:
Objeto Valor Peso (kg)

1 7.5 4
2 4 3
3 3 2
4 3.5 1
? Que objetos deve o campista por na mochila de forma a maximizar o

valor total dos objetos escolhidos não excedendo a capacidade? ?
Slide 48
Exemplo (continuação)
Variáveis de decisão:
1 se se selecionar o objeto i
xi =  i=1,2,3,4
0 caso contrário
Modelo de programação 0-1
Consideremos o objeto 2 (por exemplo):
Peso do objeto 2 3 Valor do objeto 2 4
3 se se selecionar o objeto 2 4 se se selecionar o objeto 2

3 x2 =  4 x2 = 
0 caso contrário 0 caso contrário
Contribuição do objeto 2 para Contribuição do objeto 2
o peso total a transportar para o valor total da mochila
Slide 49
Função objetivo:
7.5x1 + 4x2 + 3x3 + 3.5x4 Valor dos objetos a transportar
Restrições:
O peso dos objetos selecionados não
4x1 + 3x2 + 2x3 + 1x4 ≤ 6 pode exceder a capacidade da mochila
x1 , x2 , x3 , x4  {0,1} As variáveis só podem tomar os valores 0 ou 1
Max z = 7.5x1+ 4x2 + 3x3 + 3.5x4 Max z = 7.5x1+ 4x2 + 3x3 + 3.5x4
s. a: 4x1 + 3x2 + 2x3 + x4 ≤ 6 s. a: 4x1 + 3x2 + 2x3 + x4 ≤ 6
xi  {0,1} i=1,2,3,4 0 ≤ xi ≤ 1, i=1,2,3,4
xi inteiro, i=1,2,3,4
Slide 50
Programação linear
Exemplo
Uma pequena refinaria de petróleo produz um tipo de gasolina e um tipo de
gasóleo. Para tal, a refinaria utiliza três qualidades diferentes de petróleo bruto,
as quais provêm, respetivamente, do Médio Oriente (MO), do Norte da Europa
(NE) e da América do Sul (AS). Para produzir 1000 litros de gasolina é
necessário utilizar 5 barris de petróleo proveniente do Médio Oriente, 2 barris
de petróleo proveniente do Norte da Europa e 1 barril de petróleo proveniente
da América do Sul. A produção de 1000 litros de gasóleo requer 3 barris de
cada um dos diferentes tipos de petróleo. Diariamente, a refinaria dispõe de 30
barris de petróleo proveniente do Médio Oriente, 24 barris de petróleo
proveniente do Norte da Europa e 18 barris de petróleo proveniente da América
do Sul. Após uma prospeção de mercado é possível prever um lucro de €
800,00 por cada milhar de litros de gasolina e € 600,00 por cada milhar de litros
de gasóleo. Pretende-se planear a produção diária de gasolina e gasóleo de
forma a maximizar o lucro total obtido.
Slide 51
Petróleo Bruto
(diariamente)
Médio Oriente (30 barris) Refinaria
Produção
(diária)
Gasolina
Norte da Europa (24 barris)
Gasóleo
América do Sul (18 barris)
5 barris M. O.
2 barris N. E. 1000 litros de gasolina Lucro de € 800,00
1 barril A. S.
3 barris M. O.
3 barris N. E. 1000 litros de gasóleo Lucro de € 600,00
3 barril A. S.
? Produção diária
Gasolina / Gasóleo
? Maximização do lucro
Slide 52
x1 Quantidade (em milhares de litros) a produzir de gasolina – diariamente
x2 Quantidade (em milhares de litros) a produzir de gasóleo - diariamente
Função objetivo:
11000 litros de gasolina € 800 de lucro

x11000 litros de gasolina € 800x1 de lucro
800x1 Lucro obtido com a produção de x1 milhares de litros de gasolina
600x2 Lucro obtido com a produção de x2 milhares de litros de gasóleo
Lucro total (função objetivo a maximizar) Z = 800x1 + 600x2
Slide 53
Restrições:
Quantidade utilizada de Quantidade disponível

petróleo bruto M. O.
(diariamente)
≤ de petróleo bruto M. O.
(diariamente)
30 barris

petróleo bruto N. E
(diariamente)
≤ de petróleo bruto N. E.
(diariamente)
24 barris

petróleo bruto A. S.
(diariamente)
≤ de petróleo bruto A. S.
(diariamente)
18 barris
Quantidades
produzidas ≥ 0
Slide 54
Produção de 1000 são necessários
5 barris de petróleo M. O.
litros de gasolina
Produção de x11000 são necessários
5x1 barris de petróleo M. O.
litros de gasolina

3 barris de petróleo M. O.
litros de gasóleo
3x2 barris de petróleo M. O.
litros de gasóleo
Quantidade utilizada de petróleo M. O. se forem produzidos x1

5x1 + 3x2
milhares de litros de gasolina e x2 milhares de litros de gasóleo
5x1 + 3x2 ≤ 30 Restrição 1
Slide 55
2 barris de petróleo N. E.
litros de gasolina
2x1 barris de petróleo N. E.
litros de gasolina

3 barris de petróleo N. E.
litros de gasóleo
3x2 barris de petróleo N. E.
litros de gasóleo
Quantidade utilizada de petróleo N. E. se forem produzidos x1

2x1 + 3x2
2x1 + 3x2 ≤ 24 Restrição 2
Slide 56
Produção de 1000 é necessário
1 barril de petróleo A. S.
litros de gasolina
1x1 barris de petróleo A. S.
litros de gasolina

3 barris de petróleo A. S.
litros de gasóleo
3x2 barris de petróleo A. S.
litros de gasóleo
Quantidade utilizada de petróleo A. S. se forem produzidos x1

x1 + 3x2
x1 + 3x2 ≤ 18 Restrição 3
Slide 57
Formulação:
max z = 800x1+ 600x2

s. a: 5x1 + 3x2 ≤ 30
2x1 + 3x2 ≤ 24
x1 + 3x2 ≤ 18
x1, x2 ≥ 0
Slide 58
Programação linear (PL): generalidades
Um problema de programação linear é um problema de otimização em

que se pretende maximizar (ou minimizar) uma função linear nas
variáveis de decisão (função objetivo), tendo os valores das variáveis
de decisão que satisfazer um conjunto de restrições, as quais são
equações lineares ou desigualdades lineares;
a1x1 + a2x2 + … + anxn = b a1x1 + a2x2 + … + anxn ≤(≥) b

(a1,a2,…,an,b constantes)
Slide 59

Exemplos de objetivos num problema de otimização
❖ Maximizar lucros
❖ Minimizar custos
❖ Maximizar o retorno de um investimento
❖ Minimizar o número de equipamentos
❖ Maximizar a satisfação dos clientes
❖ Maximizar a probabilidade de sobrevivência
❖ …
Exemplos de restrições num problema de otimização

❖ Restrições relativas à capacidade de produção (máquinas, mão-de-obra)
❖ Restrições relativas à disponibilidade de matérias-primas
❖ Restrições relativas à procura e às limitações do mercado
❖ Restrições de equilíbrio
❖ …
Slide 60

Um modelo de programação linear pressupões válidos as seguintes princípios:
1. Proporcionalidade;
2. Aditividade;
3. Continuidade:
4. Certeza.
1. Princípio da proporcionalidade
A contribuição de cada variável de decisão para a função objetivo e para o
termo esquerdo de uma restrição é proporcional ao valor dessa variável
consome
se 1 a
dá um lucro de
consome
então x ax
dá um lucro de
Slide 61
Exemplo (problema da refinaria)
11000 litros de gasolina € 800 de lucro

x11000 litros de gasolina € 800x1 de lucro
2. Princípio da aditividade
A contribuição de cada variável de decisão para a função objetivo e para o
termo esquerdo de uma restrição é independente dos valores das outras
variáveis de decisão
Z = 800x1 + 600x2
Lucro total = Lucro com gasolina + lucro com gasóleo
Slide 62
3. Princípio da continuidade
As variáveis de decisão podem tomar valores fracionários
x1 = 2,543 São valores possíveis para as variáveis de decisão

x2 = 2,7564
Significam que devemos produzir 2543 litros de
gasolina e 2756,4 litros de gasóleo (diariamente)
4. Princípio da certeza
Nenhum parâmetro do problema (coeficientes das variáveis de decisão na
função objetivo e nas restrições e termos independentes das restrições) está
sujeito a incerteza.
Slide 63
Problemas de PL com duas variáveis de decisão

Resolução gráfica
Quando um problema de programação linear tem apenas duas variáveis de

decisão pode ser representado/resolvido graficamente no plano definido
pelas variáveis:
i. Representa-se o conjunto de soluções admissíveis;

ii. Determina-se a solução ótima.
Possíveis formas de uma restrição de um problema de PL com duas variáveis

de decisão
Se a=0 a reta é horizontal
ax1 + bx2 = c Reta
Se b=0 a reta é vertical
ax1 + bx2 ≥ c
Semiplano limitado pela reta ax1 + bx2 = c
ax1 + bx2 ≤ c Se b>0 os pontos ‘abaixo’ da reta verificam ax1 + bx2 < c
Se b<0 os pontos ‘abaixo’ da reta verificam ax1 + bx2 > c
Slide 64

Função objetivo de um problema de PL com duas variáveis de decisão
z = c1x1 + c2x2 c1 e c2 fixos (e conhecidos…)
Se z’ for um valor concreto para z então z’= c1x1 + c2x2 define uma reta.
z = c1x1 + c2x2 Família de retas (uma para cada valor de z)
O declive é igual para todas -c1/c2

(as retas são todas paralelas)
x2 = -(c1/c2) x1 + z/c2
A ordenada na origem varia z/c2
Slide 65

Função objetivo de um problema de PL com duas variáveis de decisão

z = c1x1 + c2x2 x2 = -(c1/c2) x1 + z/c2
aumentar o valor de z equivale a aumentar a ordenada na

origem da reta ou seja, a ‘deslocar’ a reta para ‘cima’;
c2 > 0
diminuir o valor de z equivale a diminuir a ordenada na
origem da reta ou seja, a ‘deslocar’ a reta para ‘baixo’;
aumentar o valor de z equivale a diminuir a ordenada na

origem da reta ou seja, a ‘deslocar’ a reta para ‘baixo’;
c2 < 0
diminuir o valor de z equivale a aumentar a ordenada na
origem da reta ou seja, a ‘deslocar’ a reta para ‘cima’;
Slide 66

“Metodologia” para resolver graficamente um problema de PL:
i. Representar graficamente o conjunto de soluções admissíveis;
ii. Identificar e traçar uma reta da família c1x1 + c2x2 = z

O mais simples é considerar z=0. O importante nesta fase é ficar a
conhecer a inclinação (declive) comum de todas as retas desta família
iii. Dependendo do sinal de c2 ‘desloca-se’ a reta traçada em (ii) o mais

possível para ‘cima’ ou para ‘baixo’ mas dentro do conjunto de soluções
admissíveis.
O(s) ‘último(s)’ ponto(s) encontrado(s) será(ão) a(s) solução(ões) ótima(s).
Slide 67

max z = 800x1+ 600x2

s. a: 5x1 + 3x2 ≤ 30
2x1 + 3x2 ≤ 24
x1 + 3x2 ≤ 18
x1, x2 ≥ 0
Vamos começar por representar o conjunto de soluções admissíveis.
As restrições de domínio (x1≥0, x2≥0) restringem o conjunto de soluções admissíveis

ao primeiro quadrante
Slide 68

x2
10 x1  0
x2  0
5 10 x1
Podemos agora introduzir / representar, uma a uma, as outras restrições do problema
Slide 69

x2
Restrição 1 5x1 + 3x2 ≤ 30
10 x1  0
Semiplano limitado pela reta 5x1 + 3x2 = 30

(define dois semiplanos)
x1 = 0  x2 = 10
5
A reta passa no ponto (0,10) x2  0

5x1+3x2 30
x2 = 0  x1 = 6
A reta passa no ponto (6,0) 5 10 x1
5x1+3x2 = 30
O ponto (0,0) satisfaz a desigualdade com que estamos a trabalhar

Então o semiplano que nos interessa é o que está ‘abaixo’ da reta 5x1 + 3x2 = 30
Slide 70

Exemplo (continuação) x2
Restrição 2 2x1 + 3x2 ≤ 24 10 x1  0
Semiplano limitado pela reta 2x1 + 3x2 = 24

(define dois semiplanos)
5 2x1+3x2  24
x1 = 0  x2 = 8
A reta passa no ponto (0,8) x2  0
5x1+3x2  30
x2 = 0  x1 = 12
A reta passa no ponto (12,0) 5 10 x1
5x1+3x2 = 30 2x1+3x2 = 24

Então o semiplano que nos interessa é o que está ‘abaixo’ da reta 2x1 + 3x2 = 24
Slide 71

x2
Restrição 3 x1 + 3x2 ≤ 18
10 x1  0
Semiplano limitado pela reta x1 + 3x2 = 18

2x1+3x2  24
x1 = 0  x2 = 6 5
A reta passa no ponto (0,6) x1+3x2  18

x1+3x2 = 18
x2  0
x2 = 4  x1 = 6 5x1+3x2  30
A reta passa no ponto (6,4)
5 x1
10
5x1+3x2 = 30 2x1+3x2 = 24

Então o semiplano que nos interessa é o que está ‘abaixo’ da reta x1 + 3x2 = 18
Slide 72

Agora que o conjunto de soluções admissíveis já está identificado, passamos à

determinação da solução ótima...
Função objetivo: z = 800x1+ 600x2 x2 = -(800/600)x1+ z/600

x2 = -(4/3)x1+ z/600
Para cada valor de z tem-se
uma reta de declive -4/3
z=0  x2 = -(4/3)x1
Estamos a trabalhar com a reta formada por todas as soluções—
pares (x1,x2)—que dão à função objetivo valor 0
x2 = -(4/3)x1 x1 = 0  x2 = 0 A reta passa no ponto (0,0)

x1 = -3  x2 = 4 A reta passa no ponto (-3,4)
Slide 73

x2
10
x1+3x2 = 18
-5 5 x1
10
z=0 5x1+3x2 = 30 2x1+3x2 = 24
Slide 74

Função objetivo: z = 800x1+ 600x2 x2 = -(800/600)x1+ z/600

x2 = -(4/3)x1+ z/600
Para cada valor de z tem-se
uma reta de declive -4/3
z=2400  x2 = -(4/3)x1+2400/600
Estamos a trabalhar com a reta formada por todas as soluções -

pares (x1,x2) - que dão à função objetivo o valor 2400
x2 = -(4/3)x1 + 4 Reta paralela a x2 = -(4/3)x1

…mas com ordenada na origem igual a 4
Slide 75

x2
Todos os pontos do
segmento de recita de 10 O aumento do valor de z de 0 para
extremos (3,0) e (0,4) 2400 pode ser visto como um
correspondem a soluções ‘deslocamento’ da reta original
admissíveis que dão à
função objetivo valor 2400
5
x1+3x2 = 18
Quanto maior o valor de z melhor!
x1
Quanto mais ‘para cima’ deslo- -5 5 10
carmos a reta associada à z=0 z = 2400 5x1+3x2 = 30 2x1+3x2 = 24

função objetivo melhor!
Mas não podemos ‘sair’ do conjunto de soluções admissíveis…
Slide 76

Solução ótima 10 Solução ótima:

5 x1 + 3x2 = 30 x = 3
x1 = 3 x2 = 5 z = 5400    1
 x1 + 3x2 = 18  x2 = 5
Devemos produzir diariamente z = 800  3 + 600  5 = 5400
3000 litros de gasolina 5
5000 litros de gasóleo x1+3x2 = 18
Lucro diário (máximo)

€ 5400,00 -5 5 10
x1
z=0 z = 2400 5x1+3x2 = 30 2x1+3x2 = 24
Todo o petróleo M.O. e A. S. é utilizado...

Sobram 3 barris de petróleo N. E.
Slide 77

Definição
Define-se como restrição redundante uma restrição cuja remoção não altera
o conjunto das soluções admissíveis.

A restrição 2 (que estabelece que a quantidade utilizada diariamente de
petróleo N. E. não pode exceder a quantidade disponível) é redundante.
Observação
O facto de uma restrição ser redundante não significa que possa
simplesmente ser retirada do problema pois tal restrição estabelece uma
limitação concreta e, por isso, pode ter um papel a desempenhar se houver
alguma alteração nos parâmetros.
Slide 78

Definição
Define-se como restrição ativa num ponto uma restrição que é satisfeita com
igualdade por esse ponto. Se tal não acontecer, a restrição diz-se não ativa
no ponto considerado.
x1=3
Consideremos o ponto que define a solução ótima
x2=5
Restrição 1 5x1 + 3x2 ≤ 30 5×3+ 3×5 = 30

A restrição 1 é ativa no ponto ótimo
Todo o petróleo M.O. disponível diariamente é utilizado
Restrição 2 2x1 + 3x2 ≤ 24 2×3+ 3×5 = 21 < 24

A restrição 2 não é ativa no ponto ótimo
Diariamente sobram 3 barris de petróleo N. E.
Restrição 3 x1 + 3x2 ≤ 18 3+ 3×5 = 18
A restrição 3 é ativa no ponto ótimo
Todo o petróleo A. S. disponível diariamente é utilizado
Slide 79

Resolução gráfica: casos particulares
Quando um problema de programação matemática tem mais do que uma
solução ótima dizemos que há soluções ótimas alternativas.
Graficamente, essa situação ocorre quando, após se ter ‘deslocado o mais
possível’ a reta associada à função objetivo, há mais do que um ponto
admissível a pertencer à ‘última’ reta traçada.
Exemplo
Consideremos o problema da refinaria mas vamos admitir que o lucro obtido com
1000 litros de gasolina é de € 1000,00 e não de € 800,00. O problema a resolver é o
seguinte:
max z = 1000x1 + 600x2
s. a: 5x1 + 3x2 ≤ 30
2x1 + 3x2 ≤ 24
x1 + 3x2 ≤ 18
x1, x2 ≥ 0
Slide 80

x2
Graficamente tem-se
10 Soluções ótimas: AB A (3,5)
B (6,0)
z = 1000  3 + 600  5 = 6000
5
A
x1+3x2 = 18
B
-5 5 10 x1
5x1+3x2 = 30 2x1+3x2 = 24
z=0
As retas associadas à função objetivo têm declive -5/3, que é precisamente o declive da
reta 5x1 + 3x2 = 30
Slide 81

Quando, por maior (ou menor) que seja o valor considerado para a função
objetivo, for sempre possível encontrar uma solução admissível pertencente
à reta constituída pelos pontos que dão à função objetivo o valor
considerado dizemos que o problema é ilimitado.
Exemplo
Consideremos o seguinte problema de PL que resulta de modificar os sentidos das
desigualdades nas restrições do problema da refinaria.
max z = 800x1 + 600x2

s. a: 5x1 + 3x2 ≥ 30
2x1 + 3x2 ≥ 24
x1 + 3x2 ≥ 18
x1, x2 ≥ 0
Slide 82

Graficamente tem-se
x2 problema
x1  0
ilimitado
10
5x1+3x2  30
2x1+3x2  24
5 z = 10800
x1+3x2  18
z = 7200 x2  0
x1+3x2 = 18
-5 5 10 x1
z=0 z = 2400 5x1+3x2 = 30 2x1+3x2 = 24
Slide 83

Quando as restrições de um problema de PL são incompatíveis, o problema

diz-se impossível.
Exemplo
Consideremos o problema da refinaria mas invertendo o sentido da segunda
desigualdade.
max z = 800x1 + 600x2

s. a: 5x1 + 3x2 ≤ 30
2x1 + 3x2 ≥ 24
x1 + 3x2 ≤ 18
x1, x2 ≥ 0
Slide 84

Graficamente tem-se
x2
10 x1  0
2x1+3x2  24
x1+3x2  18 x1+3x2 = 18
x2  0
5x1+3x2  30
5 x1
10
5x1+3x2 = 30 2x1+3x2 = 24
Slide 85

Análise pós-otimização
Análise feita após se ter obtido

a solução ótima do problema
Para quem toma decisões é muitas vezes útil

perceber de que forma uma decisão, que é a melhor
para uma certa concretização dos parâmetros,
poderá variar com alterações nos mesmos.
Vamos ver como responder a questões do tipo:
➢ Será possível melhorar o valor ótimo do problema se modificarmos o termo

independente de alguma restrição?
➢ Qual será o impacto na solução ótima se alterarmos o coeficiente de uma

variável na função objetivo?
Slide 86

Exemplo (Problema da refinaria) Modelo Matemático

Petróleo Bruto
Max
(diariamente)
Médio Oriente (30 barris) z = 800x1+ 600x2

Norte da Europa (24 barris) s. a: 5x1 + 3x2 ≤ 30
América do Sul (18 barris) Questões 2x1 + 3x2 ≤ 24
x1 + 3x2 ≤ 18
x1, x2 ≥ 0
Se for alterado o lucro por unidade

Será possível aumentar o lucro
obtido com a produção de um dos
se dispusermos de maior
tipos de produtos será que o plano
quantidade de algum dos tipos
Gasolina Gasóleo de produção ótimo se mantém ?
de petróleo bruto? E de quanto
é que vai aumentar o lucro ?
Slide 87

Análise pós-otimização: termos independentes
Restrições de desigualdade num problema de PL com duas variáveis:
a1x1 + a2x2 ≥ b
Semiplanos limitados pela reta a1x1 + a2x2 = b
a1x1 + a2x2 ≤ b
Alteração do termo Alteração do semiplano em causa

independente Alteração da reta que define o semiplano
Se b variar D unidades a1x1 + a2x2 = b+D

Nova reta que define o semiplano
Pode ser vista como um ‘deslocamento’ da reta anterior
Slide 88

Consideremos um problema de PL e suponhamos que já tínhamos

determinado o ponto ótimo.
Restrição do
problema
É satisfeita com igualdade Não é satisfeita com igualdade
no ponto ótimo no ponto ótimo
Ativa Não ativa

no ponto ótimo no ponto ótimo
Uma alteração do termo independente Uma alteração ‘controlada’ do termo

pode alterar a solução ótima do independente não altera a solução
problema e o valor ótimo ótima do problema nem o valor ótimo
Slide 89

Alteração do termo independente de uma restrição ativa no ponto ótimo:
Restrição 1
a1x1 + a2x2 = b
Restrição 1
Solução ótima Restrição 3 a1x1 + a2x2 = b+D
Soluções a1x1 + a2x2 = b Nova solução ótima
admissíveis
Restrição 3
Soluções
Restrição 2 admissíveis
Restrição 2
Há alteração da solução ótima (e possivelmente do valor ótimo...)!
Slide 90

Alteração (ligeira) do termo independente de uma restrição não ativa no ponto

ótimo:
Restrição 1
Solução
ótima
Restrição 3
a1x1 + a2x2 = b Restrição 3
Soluções Restrição 1
admissíveis a1x1 + a2x2 = b+D
Solução
ótima
Restrição 3
Restrição 2 Soluções a1x1 + a2x2 = b
admissíveis
Restrição 2
Não há alteração da solução ótima (nem do valor ótimo)!
Slide 91

Definição
Designa-se por valor marginal (associado a uma restrição), a taxa de
variação (instantânea) do valor ótimo do problema se houver um aumento no
termo independente.
Observações
Frequentemente, o valor marginal pode determinar-se avaliando a variação
sofrida pelo valor ótimo se o termo independente em causa aumentar uma
unidade. Nesta disciplina vamos sempre estudar casos em que assim é.
Se uma restrição estabelecer uma limitação na disponibilidade de um

recurso, o valor marginal indica-nos o que ganhamos se conseguirmos uma
unidade adicional do recurso. Ficamos a saber o que se justifica ‘pagar’ por
tal unidade adicional. Neste caso, o valor marginal também se designa por
preço sombra do recurso.
Slide 92

Exemplo (Problema da refinaria)

x2
Max z = 800x1 + 600x2
10 Solução ótima:
s. a: 5x1 + 3x2 ≤ 30
5 x1 + 3x2 = 30 x = 3
2x1 + 3x2 ≤ 24    1
 x1 + 3x2 = 18  x2 = 5
x1 + 3x2 ≤ 18
z = 800  3 + 600  5 = 5400
x1, x2 ≥ 0 5
x1+3x2 = 18
-5 5 10
x1
z=0 5x1+3x2 = 30 2x1+3x2 = 24
Slide 93

Valor marginal da restrição 1 = ?
A primeira restrição estabelece uma limitação 5x1 + 3x2 ≤ 30

na disponibilidade diária de petróleo M. O.
Esta restrição é ativa no ponto ótimo (3,5) 5×3 + 3×5 = 30
Todo o petróleo M. O. disponível diariamente é utilizado!
Então um aumento na quantidade disponível de petróleo M. O. poderá permitir um

lucro ainda maior...
Suponhamos que em vez de 30 barris por dia tínhamos 31
Slide 94

x2
Lucro ótimo: 5400 5550
Um barril adicional de petróleo

10 Nova solução ótima:
M. O. Permitiu um aumento de 5 x1 + 3x2 = 31  x = 13 4

  1

€150 no lucro ótimo  x1 + 3x2 = 18  x2 = 59 12
z = 5550
Valor marginal da restrição 1 5
x1+3x2 = 18
150
-5 5 10
x1
Valor máximo que estaremos 5x1+3x2 = 31
dispostos a pagar por um barril z=0 5x1+3x2 = 30 2x1+3x2 = 24
adicional de petróleo M. O.
Slide 95

A primeira restrição estabelece uma limitação 2x1 + 3x2 ≤ 24

na disponibilidade diária de petróleo N. E.
Esta restrição não é ativa no ponto ótimo (3,5) 2×3 + 3×5 = 21 < 24
Diariamente sobram 3 barris de petróleo N. E.
Então um aumento na quantidade disponível de petróleo N. E. não trará qualquer

alteração no lucro ótimo...
Valor marginal da restrição 2 0 Valor máximo que estaremos
dispostos a pagar por um barril
adicional de petróleo N. E.
Slide 96

A primeira restrição estabelece uma limitação x1 + 3x2 ≤ 18

na disponibilidade diária de petróleo A. S.
Esta restrição é ativa no ponto ótimo (3,5) 3 + 3×5 = 18
Todo o petróleo A. S. disponível diariamente é utilizado!
Então um aumento na quantidade disponível de petróleo A. S. poderá permitir um lucro

ainda maior...
Suponhamos que em vez de 18 barris por dia tínhamos 19
Slide 97

x2
Lucro ótimo: 5400 5450
Um barril adicional de petróleo A.

10 Nova solução ótima:
S. Permitiu um aumento de €50 5 x1 + 3x2 = 30  x = 11 4

  1

no lucro ótimo  x1 + 3x2 = 19  x2 = 65 12
z = 5450
Valor marginal da restrição 3 5
x1+3x2 = 19
50 x1+3x2 = 18
-5 5 10
x1
Valor máximo que estaremos
dispostos a pagar por um barril z=0 5x1+3x2 = 30 2x1+3x2 = 24
adicional de petróleo A. S.
Slide 98

Uma questão que se coloca após se determinar o valor marginal de uma

restrição consiste em saber se essa valorização que é estabelecida para o
recurso ou fator associado à imposição que levou à restrição, se mantém,
independentemente da alteração sofrida pelo termo independente.
Limite de validade de um valor marginal

Vimos que um barril adicional de petróleo M. O. Permite aumentar o lucro ótimo
em € 150.
E se conseguirmos 2 barris adicionais?
Que quantidade adicional de petróleo M. O. Será vantajoso conseguir? Qualquer?
Slide 99

Resultado (Não vamos demonstrar)
➢ Os valores marginais das restrições de um problema de programação linear

mantêm-se enquanto o conjunto de restrições ativas no ponto ótimo não se
alterar.
➢ Poder-se-ão ainda manter (mas não necessariamente) se o conjunto de

restrições se alterar.
Slide 100

Determinação dos limites de

Determina-se o intervalo de valores para o
validade de um valor marginal
termo independente dessa restrição de
Sempre que analisarmos um termo forma que o conjunto de restrições ativas
independente vamos assumir que
os outros se mantêm inalterados
não se altere.
Quando se pretende avaliar a variação na função

objetivo associada a uma alteração no termo
independente da restrição, incluímos os extremos do.
Slide 101


x2
Restrições ativas no
ponto ótimo
10
Valor marginal da restrição 1 = 150 Restrição 1
Restrição 3
Alteração do termo independente
da reta associada à restrição 1 5
Ponto ótimo
x1+3x2=18
‘Deslocamento’ da reta 5x1 + 3x2 = 30
-5 5
x1
10
z=0 2x1+3x2=24
5x1+3x2=30
Slide 102

x2
+ -
Enquanto a reta não atingir P ou P 10
as restrições ativas no ponto ótimo
mantêm-se a 1ª e a 3ª
-
+ P
P Ponto de intersecção das retas
2x1 + 3x2 = 24 e x1 + 3x2 = 18 Ponto ótimo
(6,4) 5 +
P
x1+3x2=18
-
(0,6) x1 = 0 e x1 + 3x2 = 18
-5 5
x1
10
z=0 2x1+3x2=24
5x1+3x2=30
Slide 103

x2
-
5x1 + 3x2 = b -
-= b = 18 10
P (0,6)
+
5x1 + 3x2 = b + -
b = 42 P
+=
P (6,4)
5 +
P
Para 18 < b < 42 o valor marginal da x1+3x2=18
primeira restrição mantém-se 150
-5 5
x1
10
Justifica-se adquirir até 12
2x1+3x2=24
(=42-30) barris adicionais de z=0
petróleo MO.
(desde que o preço a pagar por cada
barril extra não exceda 150 €)
Slide 104

x2
ponto ótimo
10
Restrição 3

Ponto ótimo
x1+3x2=18
‘Deslocamento’ da reta 2x1 + 3x2 = 24

-5 5
x1
10
z=0 2x1+3x2=24
5x1+3x2=30
Slide 105

x2
Se a reta for ‘deslocada’ para 10

cima as restrições ativas no ponto
ótimo continuam a ser a 1ª e a 3ª
5 -
P
O valor marginal mantém-se 0 para
qualquer termo independente acima de 24 x1+3x2=18
Se a reta for ‘deslocada’ para x1

- -5 5 10
baixo, enquanto a não atingir P
as restrições ativas mantêm-se a z=0 5x1+3x2=30 2x1+3x2=24
1ª e a 3ª
Slide 106

-
(3,5) 5x1 + 3x2 = 30 e x1 + 3x2 = 18 10
-
2x1 + 3x2 = b -
-= b = 21
P (3,5) -
P
5
x1+3x2=18
O valor marginal mantém-se 0 para
qualquer termo independente acima de 21
x1
-5 5 10
z=0 5x1+3x2=30
Slide 107


x2
Restrição 3 x1 + 3x2 ≤ 18
ponto ótimo
10
Restrição 3
Ponto ótimo
x1+3x2=18
‘Deslocamento’ da reta x1 + 3x2 = 18
-5 5
x1
10
z=0 2x1+3x2=24
5x1+3x2=30
Slide 108

x2
+ -
Enquanto a reta não atingir P ou P 10
as restrições ativas no ponto ótimo
mantêm-se a 1ª e a 3ª +
P
+
(2,20/3) 5x1 + 3x2 = 30 e 2x1 + 3x2 = 24 5
-
P Ponto de intersecção das retas x1+3x2=18
(6,0) x2 = 0 e 5x1 + 3x2 = 30
-
P
-5 5
x1
10
z=0 2x1+3x2=24
5x1+3x2=30
Slide 109

Análise pós-otimização – termos independentes
x2
-
x1 + 3x2 = b -
-= b =6 10
P (6,0)
+ +
P
x1 + 3x2 = b +
+= b =22
P (2,20/3)
5
Para 6 < b < 22 o valor marginal da

terceira restrição mantém-se em 50
-
P
-5 5
x1
10
Justifica-se adquirir até 4
(=22-18) barris adicionais de z=0 5x1+3x2=30 2x1+3x2=24
petróleo AS.
(desde que o preço a pagar por
cada baril extra não exceda 50 €)
Slide 110

Análise pós-otimização: coeficientes na função objetivo
Função objetivo de problema de PL com duas variáveis:
z = c1x1 + c2x2 x2 = (-c1/c2)x1 + z/c2
Alteração de c1 ou c2 Alteração do declive das retas associadas à

função objetivo
Alteração de c2 Pode alterar-se o sentido da otimização
(‘deslocamento’ para cima ou para baixo da
reta associada à função objetivo)
Neste caso, em geral, o ponto ótimo vai mudar
? Para que valores de c1 (ou c2) a solução ótima não se altera ?

Neste tipo de análise, vamos estudar cada um dos
coeficientes assumindo que o outro se mantém inalterado
Slide 111

Mantendo-se o sentido da otimização
Declive das retas associadas Têm que ser Declives das retas que
à função objetivo comparados definem o ponto ótimo
➢ Quando há apenas duas restrições ativas no ponto ótimo, teremos que

considerar os dois declives das retas correspondentes a essas
restrições.
➢ Se houver mais do que duas restrições ativas no ponto ótimo teremos

que considerar os declives das duas retas que definem a região
admissível em torno do ponto ótimo.
Slide 112

A sistematização não é fácil Vejamos algumas situações
Situação 1: Intervalo de variação para c1 (supondo c2 inalterado)
Suponhamos que otimizar equivale a ‘deslocar’

‘restrição’
para ‘cima’ a reta associada à função objetivo.
m2 (Como c2 não se altera, o sentido da otimização vai manter-se)
‘restrição’
m1
Solução ótima
A solução ótima mantém-se
Soluções admissíveis
m2  -c1/c2  m1
A resolução desta dupla inequação em ordem a c1 dá-nos
o intervalo de variação para c1 de forma a que a solução
ótima não se altere
Slide 113


‘restrição’
Soluções Suponhamos que otimizar equivale a ‘deslocar’
admissíveis m2
para ‘baixo’ a reta associada à função objetivo.
(Como c2 não se altera, o sentido da otimização vai manter-se)
Solução ótima
m1 ‘restrição’
Soluções m2
‘restrição’ admissíveis
z
Solução ótima
m1
z
‘restrição’
m1  -c1/c2  +∞
A resolução desta dupla inequação em ordem a c1 dá-nos o intervalo de
variação para c1 de forma a que a solução ótima não se altere
Slide 114

Soluções ‘restrição’ Suponhamos que otimizar equivale a ‘deslocar’

admissíveis m2 z para ‘cima’ a reta associada à função objetivo.
(Como c2 não se altera, o sentido da otimização vai manter-se)
‘restrição’ m
1
Solução ótima
Soluções ‘restrição’
admissíveis z
m2
‘restrição’ m
1
Solução ótima
-∞  -c1/c2  m2
A resolução desta dupla inequação em ordem a c1 dá-nos o intervalo de
variação para c1 de forma a que a solução ótima não se altere
Slide 115


‘restrição’
‘restrição’ m2 Suponhamos que otimizar equivale a ‘deslocar’
m1 para ‘cima’ a reta associada à função objetivo.
Solução ótima
Se c2 mudar de sinal, o sentido da otimização pode
Soluções mudar – otimizar passa a equivaler a deslocar para
admissíveis
baixo a reta associada à função objetivo
‘restrição’
‘restrição’ m2
A solução ótima mantém-se m1
Solução ótima
m1  -c1/c2  m2 e c2 mantém o sinal Soluções

admissíveis
A resolução desta dupla inequação em ordem a c2
dá-nos o intervalo de variação para c2 de forma a que
a solução ótima não se altere
Slide 116

Soluções z Suponhamos que otimizar equivale a ‘deslocar’

admissíveis
m2 para ‘cima’ a reta associada à função objetivo.
m1 Solução ótima
Se c2 mudar de sinal, o sentido da otimização pode
‘restrição’ mudar – otimizar passa a equivaler a deslocar para
baixo a reta associada à função objetivo
‘restrição’
A solução ótima mantém-se m1  -c1/c2  +∞ e c2 troca de sinal
(Ilustração no próximo slide)

-∞  -c1/c2  m2 e c2 mantém o sinal
A resolução destas duplas inequações em ordem a c2 dá-nos o intervalo de variação para c2 de forma a
que a solução ótima não se altere
Slide 117

Situação 5: (Continuação)
c2 mantém o sinal. O sentido da c2 troca de sinal. O sentido da

otimização continua a ser ‘para cima’ otimização passas a ser ‘para baixo’
Soluções Soluções m2
m2
admissíveis admissíveis
z
m1
m1
Solução ótima Solução ótima
‘restrição’ ‘restrição’
z
‘restrição’ ‘restrição’
Slide 118

Observação
O facto de a solução ótima não se alterar quando se modifica um coeficiente de
uma variável na função objetivo, não significa que tudo se mantenha na mesma.
O valor da solução altera-se com uma alteração

no coeficiente de uma variável na função objetivo
A um intervalo de variação de um coeficiente na função objetivo estará

associado um intervalo de variação para o valor ótimo do problema.
Slide 119

Exemplo (Problema da refinaria) Função objetivo z = 800x1 + 600x2
Sentido da otimização
x2
A reta associada à função objetivo é

‘deslocada’ para cima 10
Questões:
▪ Que valores pode tomar o coeficiente
Ponto ótimo
de x1 (supondo inalterado o 5
coeficiente de x2) de forma que o

x1+3x2=18
ponto (3,5) continue a ser ótimo?
▪ Que valores pode tomar o coeficiente
de x2 (supondo inalterado o x1
-5 5
coeficiente de x1) de forma que o 10
ponto (3,5) continue a ser ótimo? z=0 5x1+3x2=30 2x1+3x2=24
Slide 120

❑ Intervalo de variação para o coeficiente de x1 de forma a que a solução ótima

se mantenha
Função objetivo z = c1x1 + 600x2 x2 = -(c1/600)x1 + z/600
Declive da reta Declive da reta

5x1 + 3x2 = 30 ≤ Declive da função objetivo ≤ x1 + 3x2 = 18
-5/3 ≤ -(c1/600) ≤ -1/3
200 ≤ c1 ≤ 1000
Se o lucro obtido com 1000 litros de gasolina estiver entre € 200,00 e € 1000,00 a solução
ótima consistirá em produzir (diariamente) 3000 litros de gasolina e 5000 litros de gasóleo.
c1 = 200  z = 2003 + 6005 = 3600

Lucro ótimo [3600;6000]
c1 = 1000  z = 10003 + 6005 = 6000
Slide 121

❑ Intervalo de variação para o coeficiente de x2 de forma a que a solução ótima
se mantenha
Função objetivo z = 800x1 + c2x2 x2 = -(800/c2)x1 + z/c2
Não faz sentido c2 ser negativo (mudar de sinal) O sentido da otimização

(c2 representa um lucro) mantém-se ‘para cima’
Declive da reta Declive da reta

5x1 + 3x2 = 30 ≤ Declive da função objetivo ≤ x1 + 3x2 = 18
-5/3 ≤ -(800/c2) ≤ -1/3

480 ≤ c2 ≤ 2400
Se o lucro obtido com 1000 litros de gasóleo estiver entre € 480 e € 2400 a solução ótima
consistirá em produzir (diariamente) 3000 litros de gasolina e 5000 litros de gasóleo.
c2= 480  z = 8003 + 4805 = 4800
Lucro ótimo [4800;14400]
c2 = 2400  z = 8003 + 24005 = 14400
Slide 122

Intervalo de variação para c1 e para c2 de forma que a solução ótima se mantenha
x2
10 Solução ótima:
x1=3, x2=5; z=5400. Possíveis declives para a reta
associada à função objetivo de forma
que o ponto (3,5) se mantenha ótimo
x1+3x2=18
z=5400
-5 5 10
x1
2x1+3x2=24
5x1+3x2=30
Slide 123
➢ Se um problema de PL tiver mais do que duas variáveis de decisão, o método

gráfico não pode ser utilizado (excetuando os casos em que, por eliminação
de variáveis de transforma o problema a resolver num problema com duas
variáveis).
Neste caso, é necessário recorrer a métodos algébricos, como por exemplo, o

Método do Simplex;
➢ Quando o número de variáveis de um problema de programação linear é

significativo, deixa de ser razoável aplicar ‘manualmente’ as técnicas de
resolução dos problemas de PL.
Nestes casos recorre-se a software de programação linear. Presentemente há

diverso software que disponibiliza técnicas para resolução de problemas de
programação linear, inclusive o MS Excel.
Slide 124
Problemas de PL – Caso geral
Forma geral de um problema de programação linear:
Max (min) z = c1 x1 + c2 x2 +  + c j x j +  + cn xn
s. a. a11 x1 + a12 x2 +  + a1 j x j +  + a1n xn  ()(=)b1
a21 x1 + a22 x2 +  + a2 j x j +  + a2 n xn  ()(=)b2

ai1 x1 + ai 2 x2 +  + aij x j +  + ain xn  ()(=)bi

am1 x1 + am 2 x2 +  + amj x j +  + amn xn  ()(=)bm
x1 , x2 , , x j , , xn  0
Slide 125
Forma standard de um problema de maximização:

n
Max z = c x
j =1
j j
s. a. a x
j =1
ij j  bi i = 1,..., m
xj  0 j = 1,..., n
Forma standard de um problema de minimização:

n
Min z = cjxj
j =1
n
s. a. a x
j =1
ij j  bi i = 1,..., m
xj  0 j = 1,..., n
Slide 126
Forma canónica de um problema de programação linear:  b1 

b 
Max (min) z = c1 x1 + c2 x2 +  + c j x j +  + cn xn b= 20

s. a. a11 x1 + a12 x2 +  + a1 j x j +  + a1n xn = b1  
bm 
a21 x1 + a22 x2 +  + a2 j x j +  + a2 n xn = b2

ai1 x1 + ai 2 x2 +  + aij x j +  + ain xn = bi

am1 x1 + am 2 x2 +  + amj x j +  + amn xn = bm
x1 , x2 ,, x j ,, xn  0
Max (min) z = cx
s. a. Ax = b
x0
Slide 127

Qualquer problema de programação linear pode ser transformado num
problema equivalente que esteja numa das seguintes formas:
➢ Canónica
➢ Standard de máximo
➢ Standard de mínimo
▪ Para qualquer função f tem-se max f ( x) = − min (− f ( x) )

xX xX
▪ Para qualquer função f e termo independente b tem-se
f ( x) = b  f ( x)  b  f ( x)  b
▪ Para qualquer função f e termo independente b tem-se
f ( x)  b  f ( x) + y = b  y  0
▪ Para qualquer problema são válidas as seguintes transformações
xi  0  xi '  0  xi = − xi ' xi livre  xi = xi '− xi ' ' xi '  0  xi ' '  0
Slide 128

Exemplo
Max z = 2x1 5 x1  −15  −5 x1  15

s. a: 3 x1  9 x1 livre  x1 = x1 '− x1 ' ' , x1 '  0, x1 ' '  0
5 x1  −15 Forma standard de maximização
x1 livre Max z = 2 x1 '−2 x1 ' '

s. a: 3 x1 '−3 x1 ' '  9
Forma canónica de maximização
− 5 x1 '+5 x1 ' '  15
Max z = 2 x1 '−2 x1 ' ' x1 ' , x1 ' '  0
s. a: 3 x1 '−3 x1 ' '+ y1 = 9
Variáveis auxiliares
− 5 x1 '+5 x1 ' '+ y2 = 15 y1 , y2
x1 ' , x1 ' ' , y1 , y2  0
Slide 129

Algumas propriedades
Problema da refinaria:
Max z = 800 x1 + 600 x2 Max z = 800 x1 + 600 x2

s. a: 5 x1 + 3 x2  30 Forma s. a: 5 x1 + 3 x2 + y1 = 30
canónica
2 x1 + 3 x2  24 2 x1 + 3 x2 + y2 = 24
x1 + 3 x2  18 x1 + 3 x2 + y3 = 18
Variáveis auxiliares
x1 , x2  0 y1 y2 y3 x1 , x2 , y1 , y2 , y3  0
As variáveis auxiliares representam a

quantidade não utilizada, diariamente,
de cada um dos recursos
Slide 130

Problema da refinaria (resolução gráfica):

Max z = 800 x1 + 600 x2
s. a: 5x1 + 3x2 + y1 = 30
x2
2 x1 + 3x2 + y2 = 24
10 Solução ótima: x1 + 3x2 + y3 = 18
5 x1 + 3x2 = 30 x = 3
x1 , x2 , y1 , y2 , y3  0
   1
 x1 + 3x2 = 18  x2 = 5
z = 800  3 + 600  5 = 5400
5
x1+3x2=18
-5 5 10 x1
z=0
5x1+3x2=30 2x1+3x2=24
Slide 131

Max z = 800 x1 + 600 x2
s. a: 5x1 + 3x2 + y1 = 30
x2 Cada reta no gráfico está 2 x1 + 3x2 + y2 = 24
x1 = 0 associada à anulação de uma x1 + 3x2 + y3 = 18
10
variável x1 , x2 , y1 , y2 , y3  0
y1 = 0
y2 = 0
5
y3 = 0
x1+3x2=18
x2 = 0
-5 5 10 x1
5x1+3x2=30 2x1+3x2=24
Slide 132

Max z = 800 x1 + 600 x2
s. a: 5x1 + 3x2 + y1 = 30
x2 Cada reta no gráfico está 2 x1 + 3x2 + y2 = 24
associada à anulação de uma x1 + 3x2 + y3 = 18
10
variável x1 , x2 , y1 , y2 , y3  0
x1+3x2 = 18
x1 = 0
x2 = 0
-5 5 10 x1
5x1+3x2 = 30 2x1+3x2 = 24
Slide 133

Max z = 800 x1 + 600 x2
s. a: 5x1 + 3x2 + y1 = 30
x2 Cada ponto extremo do conjunto 2 x1 + 3x2 + y2 = 24
das soluções admissíveis está na x1 + 3x2 + y3 = 18
10
interseção de duas retas x1 , x2 , y1 , y2 , y3  0
P1 x1 = 0  x2 = 0
5 P2
P3 P2 x1 + 3x2 = 18  x1 = 0
x1+3x2 = 18
P3 5 x1 + 3x2 = 30  x1 + 3x2 = 18
P1 P4 P4 5 x1 + 3x2 = 30  x2 = 0
-5 5 10 x1
5x1+3x2 = 30 2x1+3x2 = 24
Slide 134

Max z = 800 x1 + 600 x2
s. a: 5x1 + 3x2 + y1 = 30
Cada ponto extremo do conjunto
2 x1 + 3x2 + y2 = 24
x2 das soluções admissíveis está
associado à anulação simultânea x1 + 3x2 + y3 = 18
10
de duas variáveis x1 , x2 , y1 , y2 , y3  0
P2
P1 x1 = 0  x2 = 0
5 P3
P2 x1 = 0  y3 = 0
x1+3x2 = 18
x1 = 0
P3 y1 = 0  y3 = 0
x2 = 0 P4 P4 x2 = 0  y1 = 0
-5 P1 5 10 x1
5x1+3x2 = 30 2x1+3x2 = 24
Slide 135

Max z = 800 x1 + 600 x2
s. a: 5x1 + 3x2 + y1 = 30
A anulação simultânea de duas
2 x1 + 3x2 + y2 = 24
x2 variáveis permite obter um ponto
extremo (não necessariamente x1 + 3x2 + y3 = 18
P6
10
admissível). x1 , x2 , y1 , y2 , y3  0
P5
P7
P2
5 P3
P8
x1+3x2 = 18
P10
P1 P4 P9
-5 5 10 x1
5x1+3x2 = 30 2x1+3x2 = 24
Slide 136

 y1 = 30  x2 = 10  y1 = 6  y1 = 12
   
x1 = x2 = 0   y2 = 24 x1 = y1 = 0   y2 = −6 x1 = y2 = 0   x2 = 8 x1 = y3 = 0   y2 = 6
x2 P1  y3 = 18 P6  y3 = −12 P5  y3 = −6 P2  x2 = 6
10 P6
 x1 = 6  y1 = −30  y1 = −60
  
x2 = y1 = 0   y2 = 12 x2 = y2 = 0   x1 = 12 x2 = y3 = 0   y2 = −12
P5
P4  y3 = 12

P 9  y3 = 6

P10  x1 = 18
P7
P2  x1 = 2  x1 = 3
P3  
5 y1 = y2 = 0   x2 = 20 y1 = y3 = 0   x2 = 5
3
P8
x1+3x2 = 18 P7  y 3 = −4 
P3  y 2 = 3
P10  x1 = 6

y 2 = y3 = 0   x 2 = 4
P1 P4 P9 
P8  y1 = −12
-5 5 10 x1
5x1+3x2 = 30 2x1+3x2 = 24
Slide 137

 y1 = 30  x2 = 10  y1 = 6  y1 = 12
   
x1 = x2 = 0   y2 = 24 x1 = y1 = 0   y2 = −6 x1 = y2 = 0   x2 = 8 x1 = y3 = 0   y2 = 6
x2 P1  y3 = 18 P6  y3 = −12 P5  y3 = −6 P2  x2 = 6
10
 x1 = 6  y1 = −30  y1 = −60
  
x2 = y1 = 0   y2 = 12 x2 = y2 = 0   x1 = 12 x2 = y3 = 0   y2 = −12
P4  y3 = 12

P 9  y3 = 6

P10  x1 = 18
P2  x1 = 2  x1 = 3
P3  
5 y1 = y2 = 0   x2 = 20 y1 = y3 = 0   x2 = 5
3
x1+3x2 = 18 P7  y 3 = −4 
P3  y 2 = 3
 x1 = 6

y 2 = y3 = 0   x 2 = 4
P1 P4 
P8  y1 = −12
-5 5 10 x1
5x1+3x2 = 30 2x1+3x2 = 24
Slide 138

Max z = 800 x1 + 600 x2
s. a: 5x1 + 3x2 + y1 = 30
Pontos extremos adjacentes têm 2 x1 + 3x2 + y2 = 24
x2
uma aresta (variável nula) em x1 + 3x2 + y3 = 18
10
comum variando na outra x1 , x2 , y1 , y2 , y3  0
P1 x1 = 0  x2 = 0
P2
5 P3 P2 x1 = 0  y3 = 0
x1+3x2 = 18
P3 y1 = 0  y3 = 0
P1 P4 P4 x2 = 0  y1 = 0
-5 5 10 x1
5x1+3x2 = 30 2x1+3x2 = 24 P1 x1 = 0  x2 = 0
Slide 139

Max z = 800 x1 + 600 x2
s. a: 5x1 + 3x2 + y1 = 30
x2 Existe um ponto extremo do 2 x1 + 3x2 + y2 = 24
conjunto de soluções admissíveis x1 + 3x2 + y3 = 18
10
que é solução ótima x1 , x2 , y1 , y2 , y3  0
Solução ótima
5
P2
P3
x1+3x2 = 18
z = 2400
P1 P4
-5 5 10 x1
5x1+3x2 = 30 2x1+3x2 = 24
Slide 140

Dado um problema de PL existirá sempre um ponto extremo que é solução ótima?
Não !
Todos os problemas de PL com solução admissível têm pelo menos um ponto

extremo?
Não !
x2
max x2
x1 livre
0  x2  1
x1
Mas todos os problemas de PL com restrições de não negatividade

têm pelo menos um ponto extremo!
Slide 141

Se existir solução ótima e se existir pelo menos um ponto extremo, existe sempre
uma solução ótima que é ponto extremo?
SIM !
Mesmo que existam outras soluções ótimas
(segmentos, semirretas, toda a região
admissível)!
Determinação da solução ótima de um problema de programação linear

Uma possibilidade
Enumeração de todos os pontos extremos

admissíveis escolhendo-se o melhor
Mas cuidado!....
Slide 142

Tipos de Problemas de PL
Não existem soluções admissíveis (Problema Impossível) max x1

x1 + 2x 2  −1
x1  0, x2  0
Existe pelo menos uma solução admissível e uma solução max x1

ótima (Problema Admissível) x1 + 2x 2  1
x1  0, x2  0
Existe pelo menos uma solução admissível e o valor da max x1

função objetivo é ilimitado (Problema Ilimitado) x1 − 2x 2  1
x1  0, x2  0
Slide 143

Resolução algébrica
Uma possibilidade
Enumeração de todos os pontos extremos

admissíveis escolhendo-se o melhor
Podemos evitar uma enumeração completa!

(Em geral)
Identificada uma aresta ao longo da qual a função objetivo melhora,
deslocamo-nos o mais possível ao longo desse aresta passando
assim a um ponto extremo adjacente com melhor valor de z.
Slide 144

Propriedades dos pontos extremos do conjunto de soluções admissíveis:

1. Basta pesquisar os pontos extremos admissíveis
Se existe exatamente uma solução ótima então a mesma é um ponto extremo do
conjunto de soluções admissíveis
Se existem múltiplas soluções ótimas então pelo menos uma delas é ponto extremo do
conjunto de soluções admissíveis.
2. O processo de enumeração de todos os pontos extremos admissíveis é finito

O número de pontos extremos de um problema de programação linear é finito.
3. Teste de otimalidade
Se um ponto extremo do conjunto de soluções admissíveis é tal que o valor da função
objetivo não melhora ao longo de nenhuma aresta incidente nesse ponto extremo então
esse ponto é solução ótima.
Slide 145

- Esboço de um algoritmo -
Passo de
inicialização
Partir de um ponto extremo admissível
Condição de
terminação
Não existe um ponto extremo admissível Sim

adjacente com melhor valor para a Stop
função objetivo Ponto extremo corrente
é solução ótima !
Não
Passo iterativo
Passar para um ponto extremo

admissível adjacente com melhor valor
para a função objetivo
Slide 146

Problema da refinaria
Inicialização
P1  (0,0) z=0
x2
Condição de terminação
10
Extremos adjacentes a P1: P2 e P4
P2  (0,6) z = 3600
(P2 é melhor que P1)
P2
5
P3
P4  (6,0) z = 4800
x1+3x2 = 18 (P4 é melhor que P1)
Condição de terminação: Não
P1
P4 Passo iterativo
-5 x1
5 10 Vamos passar para o ponto extremo P4
5x1+3x2 = 30 2x1+3x2 = 24
Slide 147

Problema da refinaria Condição de terminação

x2
P1  (0,0) z=0
10 (P1 é pior que P4)
P3  (3,5) z = 5400
(P3 é melhor que P4)
P2
5
P3 Passo iterativo
x1+3x2 = 18
Vamos passar para o ponto extremo P3
P1 P4
-5 5 10 x1
5x1+3x2 = 30 2x1+3x2 = 24
Slide 148

Problema da refinaria Condição de terminação

x2
P2  (0,6) z = 3600
10 (P2 é pior que P3)
P4  (6,0) z = 4800
(P4 é pior que P3)
Condição de terminação: Sim
P2 P3
5
STOP
x1+3x2 = 18
O ponto extremo P3 é ótimo!
Valor ótimo=5400
P1 P4
-5 5 10 x1
5x1+3x2 = 30 2x1+3x2 = 24
Slide 149

Caso geral Como identificamos os pontos extremos do

conjunto de soluções admissíveis?
Quantos pontos extremos admissíveis existem?
Consideremos um problema de PL na forma canónica:
Max (min) z = cx Sejam

s. a: Ax = b n Número de variáveis
x0 m Número de restrições
Suponhamos que
r(A)=m e n≥m
Slide 150

Uma solução básica (SB) é uma solução que se obtém igualando a zero n-m
variáveis e resolvendo o sistema resultante em relação às restantes
variáveis, se este sistema for possível e determinado.
- A matriz do sistema é invertível

- As colunas da matriz formam uma base de Rm
Variáveis não fixadas a zero inicialmente Variáveis básicas (Base)
Variáveis fixadas a zero inicialmente Variáveis não básicas
Slide 151

Max z = 800 x1 + 600 x2

s. a: 5x1 + 3x2 + y1 = 30 n=5
2 x1 + 3x2 + y2 = 24 m=3
n−m = 2
x1 + 3x2 + y3 = 18
x1 , x2 , y1 , y2 , y3  0 Variáveis não
básicas
Obtenção de algumas soluções básicas:
5 x1 + 3 x2 = 30 x1 = 3 x2 = 5 y1 = 0 y2 = 3 y3 = 0
Sistema resultante 
y1 = y3 = 0 2 x1 + 3 x2 + y2 = 24
 x + 3 x = 18
 1 2
Variáveis
básicas
Slide 152

Exemplo (Problema da refinaria) Max z = 800 x1 + 600 x2

s. a: 5x1 + 3x2 + y1 = 30
3 x2 + y1 = 30
Sistema resultante  2 x1 + 3x2 + y2 = 24
x1 = y2 = 0 3 x2 = 24
3 x + y = 18 x1 + 3x2 + y3 = 18
 2 3
x1 , x2 , y1 , y2 , y3  0
Variáveis não
básicas
x1 = 0 x2 = 8 y1 = 6 y2 = 0 y3 = −6
Variáveis
básicas
Slide 153

Uma solução básica admissível (SBA) é uma solução básica cujas variáveis
têm todas valor maior ou igual a zero isto é, é uma solução básica que é
admissível para o problema.
Max z = 800 x1 + 600 x2 x1 = 0 x2 = 0 y1 = 30 y2 = 24 y3 = 18 SBA

s. a: 5x1 + 3x2 + y1 = 30
x1 = 3 x2 = 5 y1 = 0 y2 = 3 y3 = 0 SBA
2 x1 + 3x2 + y2 = 24
x1 = 0 x2 = 8 y1 = 6 y2 = 0 y3 = −6 SB
x1 + 3x2 + y3 = 18 não admissível
x1 , x2 , y1 , y2 , y3  0
Slide 154

Duas soluções básicas admissíveis dizem-se adjacentes se diferem numa

única variável não básica
Max z = 800 x1 + 600 x2

SBAs adjacentes:
s. a: 5 x1 + 3 x2 + y1 = 30
2 x1 + 3x2 + y2 = 24 x1 = 0 x2 = 0 y1 = 30 y2 = 24 y3 = 18
x1 + 3x2 + y3 = 18
x1 = 6 x2 = 0 y1 = 0 y2 = 12 y3 = 12
x1 , x2 , y1 , y2 , y3  0
Slide 155

Teorema fundamental:
Consideremos um problema de PL na forma canónica com n variáveis e m
restrições. Seja X (subconjunto de Rn) o conjunto de soluções admissíveis. Um
ponto (x1,x2,...,xn) é um ponto extremo de X se e só se é uma solução básica
admissível.
Demonstração: disciplina “Programação Matemática” (DEIO)
Número de pontos Número Número de n n

extremos = de SBA ≤ SB ≤ n−m = m
C C
Corolário:
O número de pontos extremos do conjunto das soluções admissíveis de um
problema de PL é finito
Slide 156

- Algoritmo do simplex (esboço) -
Passo de
inicialização Partir de um ponto extremo admissível
Teste de
otimalidade
Existe uma aresta incidente neste ponto Não

extremo e ao longo da qual a função Stop
objetivo melhora ? Ponto extremo corrente
é solução ótima !
Sim
Passo iterativo
Andar o mais possível ao longo da

aresta de melhoramento, ou seja
passar para um ponto extremo
admissível adjacente com melhor valor
para a função objetivo.
Slide 157

Inicialização
SBA inicial: (0,0,30,24,18) z=0
x2
10
SBAs adjacentes a (0,0,30,24,18):
(0,6,12,6,0) z = 3600
(6,0,0,12,12) z = 4800
P2
5
P3
x1+3x2 = 18
Passo iterativo
P1 P4 Vamos passar para a SBA (6,0,0,12,12)
-5 5 10 x1
5x1+3x2 = 30 2x1+3x2 = 24
Slide 158

x2
(0,0,30,24,18) z=0
10
(3,5,0,3,0) z = 5400
5
P2 Passo iterativo
P3
Vamos passar para a SBA (3,5,0,3,0)
x1+3x2 = 18
P1 P4
-5 5 10 x1
5x1+3x2 = 30 2x1+3x2 = 24
Slide 159

x2
(6,0,0,12,12) z = 4800
10
(0,6,12,6,0) z = 3600
Condição de terminação: Sim

P2
5
P3
x1+3x2 = 18 A SBA (3,5,0,3,0) é ótima!
Valor ótimo=5400
P1 P4
-5 5 10 x1
5x1+3x2 = 30 2x1+3x2 = 24
Slide 160

Considere-se um problema de PL na forma canónica com n variáveis e m restrições.

Suponhamos que estamos perante uma SBA. Sejam xj1,xj2,...,xjm as variáveis básicas e
sejam xjm+1,xjm+2,...xjn as variáveis não básicas. Diz-se que o problema está na forma
canónica associada a esta solução se o respetivo sistema de equações estiver escrito
na forma:
a11 x jm+1 + a12 x jm+2 +  + a1,n − m x jn + x j1 = b1

a21 x jm+1 + a22 x jm+2 +  + a2,n − m x jn + x j2 = b2
...
am1 x jm+1 + am 2 x jm+2 +  + am ,n − m x jn + x jm = bm
e a função objetivo estiver escrita apenas em função das variáveis não básicas
z = z + c jm+1 x jm+1 + c jm+2 x jm+2 + ... + c jn x jn
Slide 161


Max z = 800 x1 + 600 x2
SBA: (0,0,30,24,18) s. a: 5x1 + 3x2 + y1 = 30
2 x1 + 3x2 + y2 = 24
z=0+800x1+600x2
x1 + 3x2 + y3 = 18
5x1 +3x2 +y1 = 30
x1 , x2 , y1 , y2 , y3  0
2x1 +3x2 +y2 = 24
x1 +3x2 +y3 = 18
SBA: (6,0,0,12,12)
z=4800 +120x2 -160y1

x1 +(3/5)x2 +(1/5)y1 = 6
(9/5)x2 -(2/5)y1 +y2 = 12
(12/5)x2 -(1/5)y1 +y3 = 12
Slide 162

Max z = 800 x1 + 600 x2
s. a: 5x1 + 3x2 + y1 = 30
SBA: (0,6,12,6,0)
2 x1 + 3x2 + y2 = 24
z=3600+200x1 -200y3 x1 + 3x2 + y3 = 18
4x1 +y1 -y3 = 12 x1 , x2 , y1 , y2 , y3  0
x1 +y2 -y3 = 6
(1/3)x1 +x2 +(1/3)y3 = 6
SBA: (3,5,0,3,0)
z=5400 -150y1 -50y3

x1 +(1/4)y1 -(1/4)y3 = 3
-(1/4)y1 +y2 -(3/4)y3 = 3
x2 -(1/12)y1 +(5/12)y3 = 5
Slide 163

Se um problema de PL estiver na forma canónica associada à SBA corrente é fácil
verificar se esta é a solução ótima ou, em alternativa, identificar as variáveis não básicas
cujo incremento pode contribuir para uma melhoria da função objetivo.

SBA: (0,0,30,24,18) Variáveis não básicas: x1 e x2
z=800x1+600x2
Partindo desta SBA, quer um aumento em x1 quer um
aumento em x2 implicam um aumento de z
duas arestas de melhoramento
SBA: (6,0,0,12,12) Variáveis não básicas: y1 e x2
z=4800+120x2-160y1
Partindo desta SBA, um aumento em y1 implica o
decréscimo de z (o que não é desejável). Por outro lado, um
acréscimo em x2 implica um aumento de z
uma aresta de melhoramento
Slide 164

Se um problema de PL estiver na forma canónica associada à SBA corrente é fácil

determinar qual a variável básica que vai ser substituída pela variável não básica
selecionada para passar a ser básica.

SBA: (0,0,30,24,18) Variável não básica selecionada para entrar na base: x1
x2 é não básica e assim continuará, ou seja, manter-se-á
com valor 0
5x1 +3x2 +y1 = 30 5x1 +y1 = 30

x2 = 0
2x1 +3x2 +y2 = 24 2x1 +y2 = 24
x1 +3x2 +y3 = 18 x1 +y3 = 18
A subida de x1 implica alterações em y1, y2 e y3 que terão que se manter

não negativas
Slide 165


5x1 +y1 = 30 y1 = 30 - 5x1
2x1 +y2 = 24  y2 = 24- 2x1
x1 +y3 = 18 y3 = 18- x1
y1 ≥ 0 30 - 5x1 ≥ 0 x1 ≤ 6
y2 ≥ 0
 24- 2x1 ≥ 0  x1 ≤ 12  x1 ≤ 6
y3 ≥ 0 18- x1 ≥ 0 x1 ≤ 18
Maior valor que
x1 poderá tomar
Neste caso virá: y1 = 30 - 5x1 = 0 y1 passa a não-básica

y2 = 24 - 2x1 = 12
y3 = 18 - x1 = 12
Slide 166

Quando se passa para uma nova SBA (adjacente à corrente) é fácil escrever o problema
na forma canónica associada à nova SBA.
SBA corrente: (0,0,30,24,18)

Forma canónica associada a esta SBA:
z=0+800x1+600x2
5x1 +3x2 +y1 = 30
2x1 +3x2 +y2 = 24
x1 +3x2 +y3 = 18
Nova SBA: (6,0,0,12,12) (x1 substitui na base y1)
Slide 167

z=0+800x1+600x2
5x1 +3x2 +y1 = 30 x1 +(3/5)x2 +(1/5)y1 = 6
2x1 +3x2 +y2 = 24 A variável que entra na base é escrita em
função das (novas) variáveis não básicas
x1 +3x2 +y3 = 18
x1 = 6 -(3/5)x2 -(1/5)y1
z=4800 +120x2 -160y1

x1 +(3/5)x2 +(1/5)y1 = 6
(9/5)x2 -(2/5)y1 +y2 = 12
(12/5)x2 -(1/5)y1 +y3 = 12
Slide 168

Inicialização Determinar uma SBA inicial
Escrever o problema na forma canónica associada à SBA corrente

Teste de otimalidade
(prob de max)
Sim
Todos os coeficientes na função objetivo são ≤ 0 Stop
SBA é
Não solução ótima !
Escolher uma variável com coeficiente > 0 na função objetivo para Não
candidata a entrar na base. Existe restrição ao aumento do valor dessa Stop
variável? Problema é
ilimitado !
Sim
Obter uma nova SBA: A variável escolhida entra na base com o

maior valor possível e determina-se qual a variável que sai da base
Slide 169

Max z = 800 x1 + 600 x2

s. a: 5x1 + 3x2 + y1 = 30
2 x1 + 3x2 + y2 = 24
x1 + 3x2 + y3 = 18
x1 , x2 , y1 , y2 , y3  0
SBA inicial:
Variáveis não básicas (fixadas a zero): x1 e x2

Neste caso termos a SBA: (0,0,30,24,18)
Slide 170

Exemplo (Problema da refinaria) variáveis não-básicas variáveis básicas
z = 800 x1 + 600 x2 x1 , x2= 0 x1 x2 y1 y2 y3
5x1+ 3x2+ y1 = 30 30 24 18
x1 = min (30/5,24/2,18)
2x1+ 3x2 + y2 = 24 =6
x1+ 3x2 + y3 = 18
z = 120 x2 -160 y1 + 4800 x2 , y1= 0 y1 x2 x1 y2 y3

x1 + 3/5x2+ 1/5y1 = 6 x2 = min(6*5/3,12*5/9,12*5/12) 6 12 12
9/ x - 2/ y + y = 12 = min(10,20/3,5)
5 2 5 1 2
12/ x - 1/ y =5
5 2 5 1 + y3 = 12
z = -150 y1 -50 y3 + 5400 y1 y3 x1 y2 x2

3 3 5
x1 + 1/4 y1 - 1/4 y3 = 3 SBA é ótima !
-1/4 y1 + y2 - 3/4 y3 = 3
x2 -1/12y1 + 5/12 y3 = 5 x*= (3,5,0,3,0) Z*=5400
Slide 171
Programação Linear – Exemplos de aplicação

Um problema de gestão de tráfego
Em cada hora, cerca de 9000 carros entram na rede de ruas do centro de uma cidade,
representada na figura, viajando de 1 até 6 respeitando os sentidos obrigatórios.
1 2 4
3 5
Na tabela indica-se, para cada um dos troços da rede, o número máximo de carros que
pode transitar numa hora (NMC), em milhares de carros, bem como o tempo aproximado
de viagem de cada carro (TAV) em minutos.
troço 1,2 1,3 2,4 2,5 3,4 3,5 4,5 4,6 5,6
NMC 8 6 6 1 3 4 6 4 6
TAV 1 5 3 7 1 6 3 6 3
Slide 172

Os troços (2,5) e (3,4) atravessam a zona 1 2 4

histórica pelo que para diminuir a degradação
dos edifícios causada pela poluição restringe-se
a 2000 o número total de carros por hora no 6
total dos dois troços.

3 5
Pretende-se:
i) Determinar a forma de gerir o tráfego de forma a minimizar o tempo médio

de viagem entre 1 e 6.
ii) Determinar o impacto no tempo médio de viagem entre 1 e 6 se o limite

imposto conjuntamente aos troços (2,5) e (3,4) passar a ser de 2500 carros
por hora.
Slide 173

Formulação em PL troço 1,2 1,3 2,4 2,5 3,4 3,5 4,5 4,6 5,6
NMC 8 6 6 1 3 4 6 4 6
TAV 1 5 3 7 1 6 3 6 3
xij Número de carros (em milhares) que deverão circular por hora no troço (i,j)
(i, j)  (1,2), (1,3), (2,4), (2,5), (3,4), (3,5), (4,5), (4,6), (5,6)
Função objetivo:
Min Tempo _ médio =

1
(x12 + 5x13 + 3x24 + 7 x25 + x34 + 6 x35 + 3x45 + 6 x46 + 3x56 )
9
1 2 4
3 5
Slide 174

Formulação em PL troço 1,2 1,3 2,4 2,5 3,4 3,5 4,5 4,6 5,6
NMC 8 6 6 1 3 4 6 4 6
TAV 1 5 3 7 1 6 3 6 3
Restrições:
x12  8 x46  4 x46 + x56 = 9

x13  6 x56  6 x25 + x34  2
Vamos ignorar a
x24  6 x12 + x13 = 9 xij  0 (i, j )  TR indivisibilidade
das variáveis
x25  1 x12 = x25 + x24
1 2 4
x34  3 x13 = x34 + x35
6
x35  4 x24 + x34 = x45 + x46
x25 + x35 + x45 = x56
3
x45  6
5
Slide 175

Formulação em PL
Min Tempo _ médio =

1
(x12 + 5x13 + 3x24 + 7 x25 + x34 + 6 x35 + 3x45 + 6 x46 + 3x56 )
9
s. a: x35  4 x12 + x13 = 9 x25 + x34  2
x12  8
x13  6 x45  6 x12 = x25 + x24
x24  6 x46  4 x13 = x34 + x35
x25  1 x56  6 x24 + x34 = x45 + x46
x34  3 x25 + x35 + x45 = x56
x46 + x56 = 9
xij  0 (i, j )  TR
Slide 176

Resolução utilizando o Microsoft Excel
Problema de gestão de tráfego
Variáveis NMC Vértices Restrições

x12 <= 8 1 0 = 9
x13 <= 6 2 0 = 0
x24 <= 6 3 0 = 0
x25 <= 1 4 0 = 0
x34 <= 3 5 0 = 0
x35 <= 4 6 0 = 9
x45 <= 6
x46 <= 4 Troços (2,5) e (3,4) 0 <= 2
x56 <= 6
Tempo médio
de viagem 0
Variáveis TAV
x12 1
x13 5
x24 3
x25 7
x34 1
x35 6
x45 3
x46 6
x56 3
Slide 177

Problema de gestão de tráfego
Variáveis NMC Vértices Restrições

x12 7 <= 8 1 9 = 9
x13 2 <= 6 2 0 = 0
x24 6 <= 6 3 0 = 0
x25 1 <= 1 4 0 = 0
x34 1 <= 3 5 0 = 0
x35 1 <= 4 6 9 = 9
x45 3 <= 6
x46 4 <= 4 Troços (2,5) e (3,4) 2 <= 2
x56 5 <= 6
Tempo médio
de viagem 10,77778
Variáveis TAV
x12 1
x13 5 O tempo médio de viagem entre 1 e 6 é de 10.77 minutos.
x24
x25
3
7
O número de carros (em milhares) que passam em cada
x34 1 hora em cada troço é:
x35 6
x45 3 Troço (1,2) (1,3) (2,4) (2,5) (3,4) (3,5) (4,5) (4,6) (5,6)
x46 6
x56 3 Carros 7 2 6 1 1 1 3 4 5
Slide 178

Microsoft Excel 12.0 Sensitivity Report
Worksheet: [fluxo_carros.xls]Sheet1
Relatório de análise de sensibilidade
Report Created: 30-09-2009 14:58:22
Adjustable Cells
Final Reduced Objective Allowable Allowable
Cell Name Value Cost Coefficient Increase Decrease
$C$6 x12 7 0 0,111111111 0,111111111 1E+30
$C$7 x13 2 0 0,555555556 1E+30 0,111111111
$C$8 x24 6 -0,444444444 0,333333333 0,444444444 1E+30
$C$9 x25 1 -0,111111111 0,777777778 0,111111111 1E+30
$C$10 x34 1 0 0,111111111 0,222222222 0,111111111
$C$11 x35 1 0 0,666666667 1E+30 0,222222222
$C$12 x45 3 0 0,333333333 0,222222222 0
$C$13 x46 4 0 0,666666667 0 1E+30
$C$14 x56 5 0 0,333333333 1E+30 0
Constraints
Final Shadow Constraint Allowable Allowable
Cell Name Value Price R.H. Side Increase Decrease
$I$6 <= Restrições 9 0 9 0 1E+30
$I$7 <= Restrições 0 0,111111111 0 0 7
$I$8 <= Restrições 0 0,555555556 0 0 2
$I$9 <= Restrições 0 0,888888889 0 0 1
$I$10 <= Restrições 0 1,222222222 0 0 1
$I$11 <= Restrições 9 1,555555556 9 0 1
$I$13 Troços (2,5) e (3,4) Restrições 2 -0,222222222 2 1 1
Slide 179

Adjustable Cells
$C$6 x12 7 0 0,111111111 0,111111111 1E+30
$C$7 x13 2 0 0,555555556 1E+30 0,111111111
$C$8 x24 6 -0,444444444 0,333333333 0,444444444 1E+30
$C$9 x25 1 -0,111111111 0,777777778 0,111111111 1E+30
$C$10 x34 1 0 0,111111111 0,222222222 0,111111111
$C$11 x35 1 0 0,666666667 1E+30 0,222222222
$C$12 x45 3 0 0,333333333 0,222222222 0
$C$13 x46 4 0 0,666666667 0 1E+30
$C$14 x56 5 0 0,333333333 1E+30 0
Constraints
$I$6 <= Restrições 9 0 9 0 1E+30
$I$7 <= Restrições 0 0,111111111 0 0 7
$I$8 <= Restrições 0 0,555555556 0 0 2
$I$9 <= Restrições 0 0,888888889 0 0 1
$I$10 <= Restrições 0 1,222222222 0 0 1
$I$11 <= Restrições 9 1,555555556 9 0 1
$I$13 Troços (2,5) e (3,4) Restrições 2 -0,222222222 2 1 1
Slide 180

Impacto no tempo médio de viagem entre 1 e 6 se o limite imposto conjuntamente aos

troços (2,5) e (3,4) passar a ser de 2500 carros por hora:
Valor marginal da restrição : -0.2222
Logo, o impacto seria um decréscimo de 0.22 x 0.5 = 0.11 minutos no

tempo médio de viagem.
Podemos aumentar o número de carros no total dos 2 troços até 3000
Slide 181

Um problema de planeamento de produção
Uma empresa de Setúbal produz e comercializa para o mercado interno vários

derivados de peixe nomeadamente, conserva de atum, conserva de sardinha,
pasta de atum e pasta de sardinha.
Esta empresa possui 3 fábricas onde pode ser produzido qualquer um destes
produtos.
As encomendas para o próximo mês são de 400 lotes de conserva de atum, 350
lotes de conserva de sardinha, 750 kg de pasta de atum e 650 kg de pasta de
sardinha.
O tempo (em horas) necessário para obter 1 lote de conserva ou 1 kg de pasta
varia de acordo com a tabela seguinte:
Fábrica 1 Fábrica 2 Fábrica 3

Conserva atum 3 2.5 4
Conserva sardinha 2 2 2
Pasta atum 1.5 1 2
Pasta sardinha 1 1 1
Slide 182

Na fábrica 1 há 10 trabalhadores enquanto que nas fábricas 2 e 3 há 8
trabalhadores em cada.
Cada trabalhador tem um horário de 8 horas por dia. Para o próximo mês estão
previstos 20 dias úteis (de trabalho).
O empacotamento das conservas é feito em cada fábrica automaticamente
numa linha de empacotamento. O tempo (em horas) necessário para empacotar
um lote de conserva é dado de acordo com a tabela seguinte:

Conserva atum 0.5 0.75 0.4
Conserva sardinha 0.5 0.45 0.3
O número de horas diárias disponíveis na linha de empacotamento das fábricas

é de 7, 10 e 8 respetivamente, nas fábricas 1, 2 e 3.
A produção de pasta de atum e de sardinha na fábrica 1 está limitada a um total
de 350 kg no próximo mês.
Slide 183

Os custos de produção por lote de conserva e por quilograma de pasta são
dados, em euros, na tabela seguinte:

Conserva atum 5 5 4
Pasta atum 2 5 5
Slide 184

Questões:
1. Qual o plano ótimo de produção?
2. Surge a possibilidade de aumentar o tempo de funcionamento da linha de
empacotamento da fábrica 1. Esta medida a ser tomada incorre num custo
adicional de 4 euros por hora adicional. Será vantajoso para a empresa tomar
esta decisão? Justifique.
3. A empresa pode transferir um trabalhador de uma fábrica para outra durante um
período de 5 dias. Aconselharia esta transferência? Em caso afirmativo diga
como deveria esta transferência ser feita. Justifique.
4. Se o custo de produção de um lote de conserva de atum na fábrica 2 passar a ser
de 7 euros há alguma alteração no plano ótimo de produção inicialmente
determinado para o próximo mês?
Slide 185

Formulação
xij Quantidade (em lotes) de conserva de tipo i a produzir na fábrica j no

próximo mês
i  A, S  j  1,2,3
yij Quantidade (em kg) de pasta de tipo i a produzir na fábrica j no próximo
mês
i  A, S  j  1,2,3
Função objetivo:
Min 5x A1 + 5xA2 + 4 x A3 + 3xS1 + 7 xS 2 + 4 xS 3 + 2 y A1 + 5 y A2 + 5 y A3 + 3 yS1 + 2 yS 2 + 4 yS 3
Slide 186

Formulação
Restrições:
x A1 + x A2 + x A3 = 400
As encomendas de cada
xS1 + xS 2 + xS 3 = 350 produto para o próximo mês
y A1 + y A2 + y A3 = 750 tem que ser satisfeita
yS1 + yS 2 + yS 3 = 650
3xA1 + 2 xS1 + 1.5 y A1 + yS1  10  8  20 = 1600 A capacidade de proces-

samento em cada fábrica não
2.5x A2 + 2 xS 2 + y A2 + yS 2  8  8  20 = 1280 pode ser excedida
4 x A3 + 2 xS 3 + 2 y A3 + yS 3  8  8  20 = 1280
Slide 187

Formulação
Restrições:
0.5x A1 + 0.5xS1  7  20 = 140

A capacidade de empacotamento
0.75x A2 + 0.45xS 2  10  20 = 200 em cada fábrica não pode ser
excedida
0.4 x A3 + 0.3xS 3  8  20 = 160
A produção de pasta de atum e de
y A1 + yS1  350 sardinha na fábrica 1 está limitada
a 350 kg
xij  0
i  A, S  j  1,2,3
yij  0
Slide 188

Planeamento de produção para o próximo mês
Linha de empacotamento
Fab 1 Fab 2 Fab 3 Enc Fab 1 Fab 2 Fab 3

Conserva Atum 0 400 Conserva Atum 0,5 0,75 0,4
Conserva Sardinha 0 350 Conserva Sardinha 0,5 0,45 0,3
Pasta Atum 0 750
Pasta Sardinha 0 650 0 0 0
Horas diarias 7 10 8
Total de horas 140 200 160
Tempos processamento
Cap prod pasta F1 0 350
Fab 1 Fab 2 Fab 3
Conserva Atum 3 2,5 4 Custos
Conserva Sardinha 2 2 2 Fab 1 Fab 2 Fab 3
Pasta Atum 1,5 1 2 Conserva Atum 5 5 4
Pasta Sardinha 1 1 1 Conserva Sardinha 3 7 4
Pasta Atum 2 5 5
tempo proc 0 0 0 Pasta Sardinha 3 2 4
Fab 1 Fab 2 Fab 3 Custo total 0

Nº trabalhadores 10 8 8
Nº horas 8 8 8
Nº dias 20 20 20
Total 1600 1280 1280
Slide 189

Linha de empacotamento
Fab 1 Fab 2 Fab 3 Enc Fab 1 Fab 2 Fab 3

Conserva Atum 46 92 262 400 400 Conserva Atum 0,5 0,75 0,4
Conserva Sardinha 234 0 116 350 350 Conserva Sardinha 0,5 0,45 0,3
Pasta Atum 350 400 0 750 750
Pasta Sardinha 0 650 0 650 650 140 69 139,6
Horas diarias 7 10 8
Total de horas 140 200 160
Tempos processamento
Cap prod pasta F1 350 350
Fab 1 Fab 2 Fab 3
Conserva Atum 3 2,5 4 Custos
Conserva Sardinha 2 2 2 Fab 1 Fab 2 Fab 3
Pasta Atum 1,5 1 2 Conserva Atum 5 5 4
Pasta Sardinha 1 1 1 Conserva Sardinha 3 7 4
Pasta Atum 2 5 5
tempo proc 1131 1280 1280 Pasta Sardinha 3 2 4
Fab 1 Fab 2 Fab 3 Custo total 6904

Nº trabalhadores 10 8 8
Nº horas 8 8 8
Nº dias 20 20 20
Total 1600 1280 1280
Slide 190

Fab 1 Fab 2 Fab 3 Enc

Conserva Atum 46 92 262 400 400
Conserva Sardinha 234 0 116 350 350
Pasta Atum 350 400 0 750 750
Pasta Sardinha 0 650 0 650 650
1. Qual o plano ótimo de produção?

O custo total de produção para o próximo mês é 6904 euros.
A produção em lotes (conservas) e em quilogramas (pastas) para o
mês de Abril em cada fábrica e de cada um dos produtos é:

Conserva atum 46 92 262
Pasta atum 350 400 0
Slide 191

Target Cell (Min)
Cell Name Original Value Final Value
$C$48 Custo total Fab 1 0 6904
Adjustable Cells
Cell Name Original Value Final Value
$C$7 Conserva Atum Fab 1 0 46
$D$7 Conserva Atum Fab 2 0 92
$E$7 Conserva Atum Fab 3 0 262
$C$8 Conserva Sardinha Fab 1 0 234
$D$8 Conserva Sardinha Fab 2 0 0
$E$8 Conserva Sardinha Fab 3 0 116
$C$9 Pasta Atum Fab 1 0 350
$D$9 Pasta Atum Fab 2 0 400
$E$9 Pasta Atum Fab 3 0 0
$C$10 Pasta Sardinha Fab 1 0 0
$D$10 Pasta Sardinha Fab 2 0 650
$E$10 Pasta Sardinha Fab 3 0 0
Constraints
Cell Name Cell Value Formula Status Slack
$F$7 Conserva Atum 400 $F$7=$G$7 Not Binding 0
$F$8 Conserva Sardinha 350 $F$8=$G$8 Not Binding 0
$F$9 Pasta Atum 750 $F$9=$G$9 Not Binding 0
$F$10 Pasta Sardinha 650 $F$10=$G$10 Not Binding 0
$C$21 tempo proc Fab 1 1131 $C$21<=$C$27 Not Binding 469
$D$21 tempo proc Fab 2 1280 $D$21<=$D$27 Binding 0
$E$21 tempo proc Fab 3 1280 $E$21<=$E$27 Binding 0
$C$35 Fab 1 140 $C$35<=$C$37 Binding 0
$D$35 Fab 2 69 $D$35<=$D$37 Not Binding 131
$E$35 Fab 3 139,6 $E$35<=$E$37 Not Binding 20,4
$C$39 Cap prod pasta F1 Fab 1 350 $C$39<=$D$39 Binding 0
Slide 192

Relatório de Adjustable Cells
análise de Cell Name

Final Reduced Objective
Value Cost Coefficient
Allowable
Increase
Allowable
Decrease
sensibilidade $C$7 Conserva Atum Fab 1 46 0 5 6 1,5
$D$7 Conserva Atum Fab 2 92 0 5 3 2,000000001
$E$7 Conserva Atum Fab 3 262 0 4 1,333333334 17
$C$8 Conserva Sardinha Fab 1 234 0 3 1,5 6
$D$8 Conserva Sardinha Fab 2 0 3,4 7,000000001 1E+30 3,4
$E$8 Conserva Sardinha Fab 3 116 0 4 6 1,5
$C$9 Pasta Atum Fab 1 350 0 2 4 1E+30
$D$9 Pasta Atum Fab 2 400 0 5 0,8 4
$E$9 Pasta Atum Fab 3 0 0,8 5 1E+30 0,8
$C$10 Pasta Sardinha Fab 1 0 4 3 1E+30 4
$D$10 Pasta Sardinha Fab 2 650 0 2 1,8 1E+30
$E$10 Pasta Sardinha Fab 3 0 1,8 4 1E+30 1,8
Constraints
$F$7 Conserva Atum 400 8 400 102 23
$F$8 Conserva Sardinha 350 6 350 102 46
$F$9 Pasta Atum 750 6,2 750 230 57,5
$F$10 Pasta Sardinha 650 3,2 650 230 57,5
$C$21 tempo proc Fab 1 1131 0 1600 1E+30 469
$D$21 tempo proc Fab 2 1280 -1,2 1280 57,5 230
$E$21 tempo proc Fab 3 1280 -1 1280 92 468
$C$35 Fab 1 140 -6 140 23 51
$D$35 Fab 2 69 0 200 1E+30 131
$E$35 Fab 3 139,6 0 160 1E+30 20,4
$C$39 Cap prod pasta F1 Fab 1 350 -4,2 350 57,5 230
Slide 193

Constraints
$F$7 Conserva Atum 400 8 400 102 23
$F$9 Pasta Atum 750 6,2 750 230 57,5
$F$10 Pasta Sardinha 650 3,2 650 230 57,5
$C$21 tempo proc Fab 1 1131 0 1600 1E+30 469
$D$21 tempo proc Fab 2 1280 -1,2 1280 57,5 230
$E$21 tempo proc Fab 3 1280 -1 1280 92 468
$C$35 Fab 1 140 -6 140 23 51
$D$35 Fab 2 69 0 200 1E+30 131
$E$35 Fab 3 139,6 0 160 1E+30 20,4
$C$39 Cap prod pasta F1 Fab 1 350 -4,2 350 57,5 230
Restrição relativa ao
empacotamento na fábri-
ca 1.
Slide 194

Valor marginal da restrição relativa ao empacotamento na fábrica 1: -6
Isto significa que mais uma hora naquela linha na fábrica 1 conduz a um decréscimo de 6 euros
no custo total de produção. Como a tomada desta medida tem um custo adicional de 4 euros, na
realidade o decréscimo do custo total será de apenas 6 – 4 = 2 euros.
Os valores marginais mantêm-se inalterados desde que não se exceda um número adicional de
23 horas, isto é, desde que não se excedam nesta linha e nesta fábrica as 140 + 23 = 163 horas
no mês de Abril.
Assim, compensa tomar esta decisão porque representa um decréscimo de

2 x 23 = 46 euros no custo total de produção no mês de Abril.
Slide 195


Constraints
$F$7 Conserva Atum 400 8 400 102 23
$F$9 Pasta Atum 750 6,2 750 230 57,5
$F$10 Pasta Sardinha 650 3,2 650 230 57,5
$C$21 tempo proc Fab 1 1131 0 1600 1E+30 469
$D$21 tempo proc Fab 2 1280 -1,2 1280 57,5 230
$E$21 tempo proc Fab 3 1280 -1 1280 92 468
$C$35 Fab 1 140 -6 140 23 51
$D$35 Fab 2 69 0 200 1E+30 131
$E$35 Fab 3 139,6 0 160 1E+30 20,4 Restrições relativas
$C$39 Cap prod pasta F1 Fab 1 350 -4,2 350 57,5 230 ao número total de
horas de trabalho em
cada fábrica.
Slide 196


Enquanto que nas fábricas 2 e 3 todas as horas de trabalho são utilizadas, na fábrica 1,
sobram 1600-1131= 469 horas. Assim, só faz sentido transferir um trabalhador da fábrica 1.
Um trabalhador transferido durante 5 dias para uma outra fábrica representa um decréscimo de
5 x 8 =40 horas nessa fábrica e um acréscimo de 40 horas na fábrica para onde é transferido.
Valor marginal da restrição relativa à fábrica 2 : -1.2 é possível aumentar até 57,5 h > 40 h
Valor marginal da restrição relativa à fábrica 3: -1.0 é possível aumentar até 92 h > 40 h
Logo, deve fazer-se a transferência da fábrica 1 para a fábrica 2. Haverá um decréscimo no

custo total de 1.2 x 40 = 48 euros.
Slide 197


Adjustable Cells
$C$7 Conserva Atum Fab 1 46 0 5 6 1,5
$D$7 Conserva Atum Fab 2 92 0 5 3 2,000000001
$E$7 Conserva Atum Fab 3 262 0 4 1,333333334 17
$C$8 Conserva Sardinha Fab 1 234 0 3 1,5 6
$D$8 Conserva Sardinha Fab 2 0 3,4 7,000000001 1E+30 3,4
$E$8 Conserva Sardinha Fab 3 116 0 4 6 1,5
$C$9 Pasta Atum Fab 1 350 0 2 4 1E+30
$D$9 Pasta Atum Fab 2 400 0 5 0,8 4
$E$9 Pasta Atum Fab 3 0 0,8 5 1E+30 0,8
$C$10 Pasta Sardinha Fab 1 0 4 3 1E+30 4
$D$10 Pasta Sardinha Fab 2 650 0 2 1,8 1E+30
$E$10 Pasta Sardinha Fab 3 0 1,8 4 1E+30 1,8
Slide 198


O planeamento de produção obtido para o mês de Abril mantém-se ótimo para custos de
produção de cada lote de conserva de atum na fábrica 2 entre 5 - 2 = 3 euros e 5 + 3 = 8 euros.
Se o custo passar a ser de 7 euros ( < 8 euros ) em vez de 5 euros o plano de produção para o
mês de Abril mantem-se.
O custo total de produção passará a ser 6904 + 2 x 92 = 7088 euros

(7-5)
Slide 199
Programa
1. Introdução
DEPARTAMENTO DE ESTATÍSTICA E INVESTIGAÇÃO OPERACIONAL 3. Problemas em grafos
Em Investigação Operacional é frequente recorrer-se a uma rede para

modelar e/ou resolver um problema
▪ Problemas de planeamento de produção;

▪ Problemas de distribuição;
▪ Gestão de recursos humanos;
▪ Aplicações financeiras;
▪ …
Um pouco de história…
1736 As pontes de Königsberg (Leonard Euler)

1859 Uma volta ao mundo… (William Rowan Hamilton)
Slide 201
As pontes de Königsberg…
Königsberg é uma localidade alemã

banhada pelo rio Pregel.
Numa certa zona existem duas

pequenas ilhas (a e d) que estão
ligadas entre si e a terra através de
sete pontes.
As pessoas falavam frequentemente

sobre a possibilidade de um indivíduo
fazer um percurso que, partindo de um
determinado ponto, atravessasse cada
ponte uma e uma só vez regressando
ao ponto de partida…
Slide 202
Königsberg (Kaliningrado)
Slide 203
Königsberg em 1736...
Slide 204
Königsberg em 1736...
Slide 205
Kaliningrado reconstruída após a Segunda Guerra Mundial...
Slide 206
Ninguém conseguia demonstrar que tal não era possível

mas também ninguém encontrava uma forma de o fazer!
Euler Representa o problema numa rede…
Cada zona em terra Uma letra

a
Cada ponte Uma linha
c
a
b d
b c
d
b c
Slide 207
O problema de Hamilton (The icosian game)
Imaginem-se 20 cidades do nosso planeta

dispostas segundo os vértices de um dodecaedro
Pretende-se visitar cada cidade

exatamente uma vez e regressar à
cidade de partida.
As ligações possíveis são as que

correspondem às arestas do dodecaedro.
Será possível estabelecer um percurso

com estas características?...
*Poliedro regular com 20 vértices e doze faces pentagonais.

Slide 208
Definições e conceitos básicos…

Definição
➢ Chama-se grafo orientado a um par ordenado G = (X,A) em que X é um

conjunto finito e A é um subconjunto de X2 (ou seja, A  X2);
➢ Os elementos de X designam-se por vértices ou nodos do grafo;
➢ Os elementos de A designam-se por arcos do grafo.
➢ Para cada arco a=(i,j) A, i designa-se por vértice inicial de a e j por
vértice final ou terminal de a. Se i=j, a diz-se um lacete.
Slide 209

Exemplo
2
a2 a3 a5
4
a1
a6
X={1,2,3,4} 1 a4 3
A={a1,a2,a3,a4,a5,a6} ={(1,2),(2,1),(2,3),(3,1),(3,3),(3,4)}
3
a5 é um lacete a6
a3
a5
Um grafo admite múltiplas representações… 4
a2 2
a4
a1
Slide 210

Definição
Seja G = (X,A) um grafo orientado e seja (i,j)A
➢ O vértice j diz-se sucessor do vértice i;
➢ O vértice i diz-se antecessor do vértice j;
➢ G+(i)={j X:(i,j) A} é o conjunto dos sucessores de i;
➢ G-(i)={j X:(j,i) A} é o conjunto dos antecessores de i;
➢ O número de arcos cujo nodo inicial é o vértice i designa-se por grau

externo do vértice i e representa-se por d+(i);
➢ O número de arcos cujo nodo terminal é o vértice i designa-se por grau

interno do vértice i e representa-se por d-(i).
Slide 211

Exemplo
2 G+(1) = {2} d+(1) = 1

a2 a3 a5 G+(2) = {1,3} d+(2) = 2
4
a1
G+(3) = {1,3,4} d+(3) = 3
G+(4) =  d+(4) = 0
a6
1 3
a4 Sd+(i)=6=|A|
G-(1) = {2,3} d-(1) = 2

G-(2) = {1} d-(2) = 1
G-(3) = {2,3} d-(3) = 2
G-(4) = {3} -
d (4) = 1
Sd-(i)=6=|A|
Slide 212
Proposição
Seja G=(X,A) um grafo orientado. Tem-se d
i X
+
(i ) = d − (i ) = A
i X
Número de arcos de G
É preciso demonstrar?
d +
(i ) = (i, j ) : (i, j )  A, j  X  = A
iX iX
d −
(i ) = (i, j ) : ( j , i )  A, j  X  = A
iX iX
Slide 213

Um grafo G=(X,A) pode ser visto como
Exemplo
uma relação binária definida em X.
X={2,3,4,5,6,7,8,9,10}
Relação binária ij  i divide j e i  j
A = (i, j ) : ij e i, j  X 
A = (2,4), (2,6), (2,8), (2,10), (3,6), (3,9), (4,8), (5,10)
2 6 3 9
8 10 5 7
Slide 214
Definição
➢ Chama-se grafo não orientado a um par ordenado G = (X,A) em que X é
um conjunto finito e A  {{i,j}:i,jX e i≠j};
➢ Os elementos de X designam-se por vértices ou nodos do grafo;
➢ Os elementos de A designam-se por arestas dos grafo;
➢ Para cada aresta a={i,j}A, i e j designam-se por extremos de a.
4
Aresta {3,4}
3
3 e 4 são os extremos da aresta {3,4}
Slide 215

Exemplo
a3
1 6
a1
a2 2 a7
a5
3 a4 5 7
4 a6
X={1,2,3,4,5,6,7}
A={a1,a2,a3,a4,a5,a6,a7} ={{1,3},{1,4},{1,5},{2,4},{3,5},{4,5},{6,7}}
Slide 216
Definição
Seja G = (X,A) um grafo não orientado e seja {i,j}A
➢ i e j dizem-se adjacentes;
➢ G(i)={j X:{i,j} A} é o conjunto dos adjacentes de i;
➢ O número de adjacentes de i designa-se por grau do vértice i e

representa-se por d (i).
Slide 217

Exemplo
a3
1 6
a1
a2 2 a7
a5
3 a4 5 7
4 a6 G(1) = {3,4,5} d(1) = 3
G(2) = {4} d(2) = 1
G(3) = {1,5} d(3) = 2
G(4) = {1,2,5} d(4) = 3
G(5) = {1,3,4} d(5) = 3
G(6) = {7} d(6) = 1
G(7) = {6} d(7) = 1
Sd(i)=14=2|A|
Slide 218
Proposição
Seja G=(X,A) um grafo não orientado. Tem-se  d (i) =2 A
iX
É preciso demonstrar?
 d (i) =  G(i) = {i, j} : {i, j}  A, j  X  =2 A

iX iX i X
Cada aresta {i,j}A surge exatamente em dois

conjuntos: G(i) e G(j)
Slide 219

Exemplo Um grafo G=(X,A) pode ser visto como
X={2,3,4,5,6,7,8,9,10} uma relação binária definida em X.
Relação binária ij  i e j são primos entre si

A = (i, j ) : ij e i, j  X  4
3 5
6
2
10 8
9
Slide 220
Proposição
Seja G=(X,A) um grafo não orientado. Então G tem um número
par de vértices com grau ímpar
Exemplo
a3
1 d(1)=3 d(2)=1 d(3)=2
a1
a2 2
a5
d(4)=3 d(5)=3
3 a4 5
4 a6
Há 4 vértices com grau ímpar!
Slide 221

Prova
Sejam
I = i  X : d (i ) é ímpar I P =
P = i  X : d (i ) é par I P = X
Pela proposição 2 tem-se

2 A =  d (i ) = d (i ) +  d (i )
iX iP iI
  d (i) = 2 A −  d (i)
iI iP
Números pares
 d (i)
iI
é par!
Para que a soma de números ímpares seja par é necessário que o número
de parcelas seja par. Então,
I é par O número de vértices com grau
ímpar é par!
Slide 222
Fonte: Revista Pública (2002-09-23)

Uma charada…
Estávamos 8 pessoas na sala
O Gilberto cumprimentou toda a gente!
A Isabel cumprimentou 6 pessoas e a Beta 5;
A Gui cumprimentou 4 e o Manuel 3
O Rogério cumprimentou duas pessoas e a Alcina apenas uma.
Quem é que eu cumprimentei?
Slide 223

Definição
Seja G = (X,A) um grafo orientado
➢ Chama-se caminho no grafo a uma sequência de arcos em que o vértice

terminal de um coincide com o vértice inicial do seguinte;
➢ Chama-se circuito no grafo a um caminho em que o vértice terminal do

último arco coincide com o vértice inicial do primeiro arco.
Exemplo Caminhos (entre outros): a1, a3, a6

{(3,3);(3,1);(1,2);(2,3);(3,4)}
2
a5 (a3,a5,a4,a1,a2,a1,a3,a6)
a2 a3
4
a1 Circuitos (entre outros): a1, a3,a4
a6 {(3,3)}
1 a4 3
(a1,a2,a1,a3,a4)
Slide 224

Definição
Seja G = (X,A) um grafo não orientado
➢ Chama-se cadeia no grafo a uma sequência de arestas da forma

{{i1,i2}; {i2,i3};…;{ik-2,ik-1};{ik-1,ik}};
➢ Chama-se ciclo no grafo a uma sequência de arestas da forma

{{i1,i2}; {i2,i3};…;{ik-2,ik-1};{ik-1,ik}} em que i1=ik.
Exemplo Cadeias (entre outras): a1, a3, a6, a4
a3 {{3,5};{5,1};{1,4};{4,2}}
1
a1
a2 2
a4 a5 Ciclos (entre outros): a3, a6,a2
3 a6 5 {{3,5};{5,1};{1,3}}
4
(a1,a5,a6,a2)
Slide 225
Conexidade
Muitas vezes, é necessário verificar se a partir de um vértice de um grafo é

possível atingir outro vértice qualquer…
Definição
Seja G = (X,A) um grafo não orientado
G diz-se conexo se entre quaisquer dois vértices do grafo existe uma cadeia
que os une; Caso contrário diz-se desconexo.
Exemplo
Grafo conexo Grafo desconexo
Slide 226
Conexidade
Definição
Seja G = (X,A) um grafo orientado. Seja G’ o grafo não orientado que se
obtém de G pela remoção da orientação dos seus arcos (removendo
eventuais arestas duplicadas que surjam para algum par de vértices)
➢ G diz-se fortemente conexo se entre quaisquer dois vértices do grafo
existe pelo menos um caminho;
➢ G diz-se fracamente conexo se não for fortemente conexo mas G’ for
conexo;
➢ G diz-se desconexo se G’ for desconexo.
Exemplo
Grafo fortemente conexo Grafo fracamente conexo Grafo desconexo
Slide 227
Um quebra-cabeças…para descontrair?!
Será possível, com um traço contínuo,

desenhar a figura sem passar duas
vezes sobre o mesmo segmento?
E se for necessário regressar ao ponto

de partida?
Slide 228
Grafos eulerianos
Problema
O grafo não orientado da figura, representa 3
um bairro de uma cidade. Os vértices 2 1
correspondem a cruzamentos e as arestas 4
correspondem a ruas. 1 2 5
2
3
Os valores junto às arestas representam os 5 3
comprimentos das ruas correspondentes. 4
Todas as ruas têm casas apenas de um lado.
Um carteiro tem que percorrer as ruas do bairro para fazer a entrega do correio.
? Qual a distância mínima que o carteiro tem

que percorrer para garantir a entrega?
?
Slide 229
Grafos eulerianos
Limite inferior para essa distância: 20 3

2 1
O carteiro tem que percorrer 4
cada rua pelo menos uma vez 1 2 5
2
3
Soma dos valores associados a 5 3
4
todas as arestas
Em certos casos, este limite é coincide com a distância mínima a percorrer…
Slide 230

Definição
Seja G = (X,A) um grafo
➢ Um caminho (circuito, cadeia, ciclo) diz-se elementar se não passa mais

do que uma vez por cada vértice;
➢ Um caminho ou circuito (cadeia ou ciclo) diz-se simples se não passa

mais do que uma vez pelo mesmo arco (aresta).
Exemplo Caminhos (entre outros): a1, a3, a6

{(3,3);(3,1);(1,2);(2,3);(3,4)}
2
a5 (a3,a5,a4,a1,a2,a1,a3,a6)
a2 a3
4
a1 Circuitos (entre outros): a1, a3,a4
a6 {(3,3)}
1 a4 3
(a1,a2,a1,a3,a4)
Slide 231
Grafos eulerianos
Definição
Seja G = (X,A) um grafo não orientado.
➢ Uma cadeia em G diz-se euleriana se contiver todas as arestas de G uma

e uma só vez;
➢ Um ciclo em G diz-se euleriano se contiver todas as arestas de G uma e
uma só vez;
➢ G diz-se euleriano se contiver algum ciclo euleriano.
Exemplo 3
Ciclo euleriano:
1 2 5
{{3,2};{2,4};{4,3};{3,1};{1,4};{4,5};{5,3}}
O grafo é euleriano! 4
Slide 232
Grafos eulerianos
É possível caracterizar de forma simples um grafo euleriano
Seja G=(X,A) um grafo não orientado e seja C um ciclo euleriano em G.
C
Sempre que C atravessa um vértice qualquer, a sua
contribuição para o grau desse vértice é de duas unidades
C
O grau de cada vértice tem que ser par

Esta condição é, também, suficiente! (Prova que não faremos)
Proposição 4
Seja G=(X,A) um grafo não orientado conexo. G é euleriano se e
só se todos os vértices têm grau par (d(i) é par iX).
Slide 233
Grafos eulerianos
Exemplo (problema do carteiro)

3
d(1)=2 d(2)=2
1 2 5
d(3)=4 d(4)=4
d(5)=2
4
Todos os vértices têm grau par O grafo é euleriano
O carteiro pode percorrer todas as ruas sem repetir

nenhuma e saindo do bairro pelo ponto por onde entrou:
{{3,2};{2,4};{4,3};{3,1};{1,4};{4,5};{5,3}}
Slide 234
Grafos eulerianos
Exemplo O problema de Euler
a a
d d
b c b e f c
Há vértices com grau ímpar!
Problema das pontes de Königsberg:

Não existe qualquer percurso que utilize todas as pontes sem repetir nenhuma!
Slide 235
Mais um quebra-cabeças…
?
Será possível, com uma linha contínua, cruzar todos
os segmentos que compõem a figura, sem cruzar
duas vezes o mesmo segmento e fechando a linha?
?
Slide 236
Modelo adequado…
A linha fechada corresponde a um ciclo euleriano neste grafo…
… que não existe!

Slide 237
Grafos eulerianos
Proposição
Seja G=(X,A) um grafo não orientado conexo. Existe uma cadeia euleriana
em G se e só se o número de vértices com grau ímpar é no máximo 2.
Observação
Se o número de vértices com grau ímpar for 2 a cadeia tem que começar
num desses vértices para terminar no outro…
Exemplo
Será possível, com um traço contínuo, desenhar a figura
sem passar duas vezes sobre o mesmo segmento?
Resposta: Sim, mas temos que iniciar num dos vértices da base…
E se for necessário regressar ao ponto de partida?

Resposta: Não!
Slide 238
Grafos eulerianos
Definição
Seja G = (X,A) um grafo orientado.
➢ Um caminho em G diz-se euleriano se contiver todos os arcos de G uma
e uma só vez;
➢ Um circuito em G diz-se euleriano se contém todos os arcos de G uma e
uma só vez;
➢ G diz-se euleriano se contiver algum circuito euleriano.
Proposição
Seja G=(X,A) um grafo orientado. G é euleriano se e só se todos os
vértices têm grau interno igual ao grau externo (d+(i)=d-(i) iX).
Slide 239
Grafos eulerianos
Exemplo
3
d+(1)=1 d-(1)=1
d+(2)=1 d-(2)=1 1 2 5
d+(3)=2 d-(3)=2
+ -
4
d (4)=2 d (4)=2
Todos os vértices têm grau interno igual ao grau externo
O grafo é euleriano!
Slide 240
Grafos hamiltonianos
Definição
Seja G = (X,A) um grafo não orientado conexo.
➢ Um ciclo em G diz-se hamiltoniano se contém todos os vértices de G uma

e uma só vez;
➢ G diz-se hamiltoniano se contiver algum ciclo hamiltoniano.
Exemplo
3
Ciclo hamiltoniano:
1 2 5
{{1,4};{4,5};{5,2};{2,3};{3,1}}
O grafo é hamiltoniano!
4
Slide 241
Definição
Seja G = (X,A) um grafo orientado conexo.
➢ Um circuito em G diz-se hamiltoniano se contém todos os vértices de G

uma e uma só vez;
➢ G diz-se hamiltoniano se contiver algum circuito hamiltoniano.
Exemplo
3
Circuito hamiltoniano:
1 2 5
{(1,4);(4,5);(5,3);(3,2);(2,1)}
O grafo é hamiltoniano!
4
Slide 242
Ao contrário do que acontece no caso de grafos eulerianos, não são
conhecidas condições que sejam ao mesmo tempo necessárias e suficientes
para um grafo ser hamiltoniano...
... Mas conhecem-se condições necessárias ou suficientes.
Proposição (Condição necessária para um grafo ser hamiltoniano)

Seja G=(X,A) um grafo não orientado hamiltoniano. Então G é
conexo.
Prova Trivial!
Proposição (Condição necessária para um grafo ser hamiltoniano)

Seja G=(X,A) um grafo orientado hamiltoniano. Então G é fortemente
conexo.
Prova Trivial!
Slide 243
Caminhos ótimos
São muitas as aplicações na área da IO cuja resolução passa por determinar
o caminho de menor ou maior valor entre dois vértices de um grafo orientado
Problema de caminho ótimo
Definição
Seja G = (X,A) um grafo orientado tal que a cada arco (i,j) está associado um
valor cij, que designaremos por comprimento (custo, valor, peso) do arco.
Seja C, um caminho entre dois vértices s e t pertencentes a X.
➢ À soma dos comprimentos de todos os arcos de C chama-se

comprimento do caminho C;
Slide 244
Caminhos ótimos
Definição (continuação)
➢ De entre todos os caminhos entre s e t, o que tem menor comprimento

designa-se por caminho mais curto entre s e t.
➢ De entre todos os caminhos entre s e t, o que tem maior comprimento

designa-se por caminho mais longo entre s e t.
Slide 245
Caminhos ótimos
Exemplo 3
2 6
1
Sejam s = 1 e t = 5 1 2 4 5
3 1
Caminhos entre 1 e 5 e respetivos valores:
4
{(1,2); (2,3); (3,5)} comprimento = 9
{(1,2); (2,3); (3,4); (4,5)} comprimento = 8
{(1,2); (2,4); (4,5)} comprimento = 5
Caminho mais curto entre 1 e 5 {(1,2); (2,4); (4,5)}
Caminho mais longo entre 1 e 5 {(1,2); (2,3); (3,5)}
Slide 246
Caminhos ótimos
Existirá sempre caminho mais curto entre dois vértices de um grafo?
Exemplo
3
3 8
1
3 5
6
1 2 5
5
2 3
4
Não existe caminho mais curto entre 1 e 5

porque não existe nenhum caminho de 1 para 5!
Slide 247
Caminhos ótimos
Existirá sempre caminho mais curto entre dois vértices de um grafo?
Exemplo 3
3 8
1
3 -5
(1,2) (2,3) (3,5) 14 6
1 2 5
5
(1,2) (2,3) (3,4) (4,2) (2,3) (3,5) 12 (=14-2) 2 3
4
(1,2) (2,3) (3,4) (4,2) (2,3) (3,4) (4,2) (2,3) (3,5) 10 (=12-2)
(1,2) (2,3) … (3,4) (4,2) (2,3)… (3,5) 14-2n
−
n vezes
Não existe caminho porque o grafo tem um circuito de valor (custo) total negativo!
Slide 248
Caminhos ótimos
Existência de caminho mais curto entre dois vértices s e t num grafo orientado
➢ Tem que existir pelo menos um caminho entre s e t;

➢ Não pode existir qualquer circuito de valor negativo
em algum caminho entre s e t.
? Caminho mais curto entre dois vértices de um grafo orientado ?

Existem diversos algoritmos…
Slide 249
Caminhos ótimos
G=(X,A) Grafo orientado

cij Comprimento (custo, valor, peso) associado ao arco (i,j)X
Objetivo Determinar o caminho mais curto entre s e t (pertencentes a X)
Problema mais geral
Determinar o caminho mais curto entre o vértice s e todos os outros
Suposições (garantem que existe caminho mais curto entre o vértice s e todos os outros)
▪ Existe pelo menos um caminho entre o vértice s e todos os outros;

▪ O grafo não tem circuitos de valor negativo.
Slide 250
Caminhos ótimos
sX Vértice a partir do qual se pretende determinar os caminhos mais curtos
Notação
l(j) Comprimento do caminho mais curto entre o vértice s e o vértice j

j X
Exemplo l (2) = 5 l (4) = 7

2
2 4
l (1) = 0 5
6
(s=1) 1 3 3
3
5
3 5
8
l (3) = 3 l (5) = 10
Slide 251
Caminhos ótimos
Proposição
Seja G=(X,A) um grafo orientado e seja sX. Admita-se ainda que
existe pelo menos um caminho entre s e todos os outros vértices.
Sendo l(j) o comprimento do caminho mais curto entre s e j então,
➢ l(j)  l(i) + cij iX tal que (i,j)A;
➢ Se l(j) = l(i) + cij então o arco (i,j) é o último arco num

caminho mais curto entre s e j.
Observação l (i )
i cij
l ( j)
s j
Slide 252
Caminhos ótimos
Se conhecermos os valores l(j) podemos usar a parte 2 da proposição anterior
para ‘recuperar’ os caminhos mais curtos entre s e todos os outros vértices…
Exemplo l (2) = 5 l (4) = 7

l(5)=l(4)+c45 2
2 4
(4,5) é o último arco num caminho l (1) = 0 5
mais curto entre 1 e 5 6
1 3 3
l(4)=l(2)+c24 (s=1) 3
5
(2,4) é o último arco num caminho
mais curto entre 1 e 4
3 5
8
l (3) = 3 l (5) = 10
l(2)=l(1)+c12
mais curto entre 1 e 2
Caminho mais curto entre 1 e 5 {(1,2),(2,4),(4,5)}

Comprimento: l(5)=10.
Slide 253
Caminhos ótimos
Determinação dos valores l(j), jX – comprimentos dos caminhos mais curtos
entre s e todos os outros vértices
l (i)
Observação
i
cij
l (k ) l ( j)
ckj
s k j
l (l )
clj
l
Proposição
Seja G=(X,A) um grafo orientado e seja sX. Admita-se ainda que existe pelo
menos um caminho entre s e todos os outros vértices. l(j) é o comprimento do
caminho mais curto entre s e j se e só se,
l ( j) = min l (i) + c 
ij
i X : ( i , j ) A
Slide 254
Caminhos ótimos
Determinação dos valores l(j), jX – comprimentos dos caminhos mais curtos
ALGORITMO
1. l(s)  0;
2. Enquanto não se conhecer l(j) para todo o jX fazer
Considerar um qualquer vértice j tal que não se conhece l(j) mas tal que já
se conhecem os valores de l relativos a todos os seus antecessores. Fazer
l ( j)  min l (i) + c 
ij
i X : ( i , j ) A
Observação Caso se pretenda determinar apenas o comprimento do caminho

mais curto entre s e um determinado vértice tX, o algoritmo
termina quando se obtiver o valor de l(t)
Slide 255
Caminhos ótimos
Exemplo
2
2 4
l(1)=0 5
(s=1) 6
l(3)=min{l(1)+3}=3 1 3 3
3
5
l(2) = min{l(1)+5, l(3)+3 } =
3 5
min{ 0 + 5, 3+3}=5 8
l(4) = min{l(2)+2, l(3)+5 } =

min{ 5 + 2, 3 + 5 } = 7
l(5) = min{l(2)+6, l(3)+8, l(4)+3 } =

min{ 5 + 6, 3 + 8, 7 + 3 } = 10
Slide 256
Caminhos ótimos
Um problema de substituição de equipamento
➢ Uma empresa que faz entregas ao domicílio pretende ter uma viatura
automóvel disponível durante os próximos dois anos.
➢ A empresa tem como opções unicamente dois modelos de viatura: A e B.
➢ Os custos de aquisição e operação / manutenção são diferentes.
➢ No fim do primeiro ano é possível trocar de viatura (ou por outra do mesmo
modelo ou por uma do outro modelo), obtendo-se uma receita proveniente da
venda.
➢ No fim dos dois anos a empresa venderá a viatura que tiver na altura.
Slide 257
Caminhos ótimos
Custo de operação e
manutenção Valor de venda
Preço de No 1º ano de No 2º ano de 1 ano de 2 anos de
aquisição atividade atividade atividade atividade
Modelo A 600 300 400 350 210
Modelo B 300 500 600 170 130
Questões:
1. Que viatura adquirir de início;
2. Deve trocar-se de viatura no fim do primeiro ano? Se sim, para que modelo?
Slide 258
Caminhos ótimos
Agora Daqui a 1 ano Daqui a 2 anos
Usado A
400 com 2 anos
-210
Usado A
com 1 ano -350+600+300
600+300 Usado A
-350+300+500 -350
com 1 ano
t
s
-170
-170+600+300 Usado B
300+500 com 1 ano
-130
Usado B -170+300+500
com 1 ano
600 Usado B
com 2 anos
Slide 259
Caminhos ótimos
Agora Daqui a 1 ano Daqui a 2 anos
Usado A
400 com 2 anos
-210
Usado A
com 1 ano 550
900 Usado A
-350
com 1 ano
450
t
s
-170
730 Usado B
800
com 1 ano
-130
Usado B 630
com 1 ano
600 Usado B
com 2 anos
Slide 260
Caminhos ótimos
Um caminho entre s e t neste grafo corresponde a uma política de aquisição,

manutenção e venda das viaturas.
Usado A
Valor (custo) de um caminho 400 com 2 anos
-210
Usado A
com 1 ano 550
900 Usado A
-350
com 1 ano
450
t
s
-170
730 Usado B
800
com 1 ano
-130
Usado B 630
com 1 ano
600 Usado B
com 2 anos
Custo da política correspondente
Slide 261
Caminhos ótimos
l(1) = 0
4
l(2) = min{l(1)+900} = 900 400
-210
l(3) = min{l(1)+800} = 800 2 550
900 5 -350
l(4) = min{l(2)+400} = 1300 450
1 8
l(5) = min{l(2)+550, l(3)+730} = 730 -170
min {900+550, 800 +730} = 1450 800

6
3 630
-130
l(6) = min{l(2)+450, l(3)+630} =
600
min {900+450, 800 +630} = 1350 7
l(7) = min{l(3)+600} = 1400
l(8) = min{ l(4)-210, l(5)-350, l(6)-170, l(7)-130} =
min{1300-210, 1450-350, 1350-170, 1400-130} = 1090
Caminho mais curto: 1 2 4 8

Valor: 1090
Slide 262
Caminhos ótimos
Usado A
400
Política ótima com 2 anos
-210
Usado A
com 1 ano 550
900 Usado A
-350
com 1 ano
450
t
s
-170
730 Usado B
800
com 1 ano
-130
Usado B 630
com 1 ano
Comprar um carro de tipo A 600 Usado B
no início e mantê-lo durante com 2 anos
os dois anos
Custo desta política: 1090 unidades monetárias Menor custo possível!
Slide 263
Caminhos ótimos
E mais uma charada (com “barba”...ou não?!)
Na margem de um rio está um pastor com um lobo, uma ovelha e um
molho de couves...
Existe um barco disponível para fazer a travessia do rio mas que é tão
pequeno que, para além do pastor, apenas pode levar um ‘passageiro’.
O pastor pretende levar o lobo, a ovelha e o molho de couves para a outra

margem do rio mas sabe que, caso não esteja presente, o lobo não pode
ficar sozinho com a ovelha e esta não pode ficar sozinha com o molho de
couves...
Pretende-se saber de que forma o pastor deve fazer

a travessia minimizando o número de viagens
A novidade!
Slide 264
Caminhos ótimos
E mais uma charada (com “barba”...ou não?!)
Pastor P Ovelha O
Lobo L Couves C
Forma-se um grafo com os diferentes estados possíveis na margem de partida...
{L,O,C,P} {L,O, P} {O,C, P} {L,C, P} {O, P}
{L, C} {O} {L} {C} {}
Com a determinação de um caminho mais curto resolve-se o problema!...
Slide 265
Caminhos ótimos
Definição
Seja G = (X,A) um grafo orientado tal que a cada arco (i,j) está associado
um valor cij, que designaremos por comprimento (custo, valor, peso) do
arco.
➢ De entre todos os caminhos entre s e t, o que tem maior comprimento
designa-se por caminho mais longo entre s e t.
Existência de caminho mais longo entre dois vértices s e t num grafo orientado
➢ Tem que existir pelo menos um caminho entre s e t;

➢ Não pode existir qualquer circuito de valor positivo em algum caminho
entre s e t.
Slide 266
Caminhos ótimos
Exemplos
3
3 8
1
3 5
6
1 2 5 Não existe caminho entre 1 e 5
5
2 3
4
3
3 8
1
3 6
6
Existe um circuito de valor positivo 1 2 5
5
2 3
4
Slide 267
Caminhos ótimos
Determinação do caminho mais longo entre dois vértices de um grafo

orientado
➢ Algoritmo para determinação do caminho mais curto substituindo (cij)

por (–cij);
max f ( x)  min − f ( x)
➢ Adaptação de algoritmos para determinação do caminho mais curto…
Slide 268
Caminhos ótimos
2
2 4
Exemplo (Substituindo (cij) por (-cij)) (s=1)
5
6
1 3 3
l(1)=0 Caminho mais
3 5
3 5
l(3)=min{l(1)-3}=-3 longo entre 1 e 5? 8
l(2) = min{l(1)-5, l(3)-3 } = -2

2 4
min{ 0 - 5, -3 - 3 } = -6 -5
(s=1) -6
l(4) = min{l(2)-2, l(3)-5 } = 1 -3 -3
min{ -6 - 2, -3 - 5 } = -8 -3
-5
l(5) = min{l(2)-6, l(3)-8, l(4)-3 } = 3 5
-8
min{ -6 - 6, -3 - 8, -8 - 3 } = -12
Caminho mais curto entre 1 e 5 com custos (–cij): {(1,3),(3,2),(2,5)}
Comprimento: l(5)=-12
Caminho mais longo entre 1 e 5 com os custos originais: {(1,3),(3,2),(2,5)}
Comprimento: -l(5)=12
Slide 269
Caminhos ótimos
Mas queremos mais!
Podemos adaptar algoritmo apresentado antes para determinar caminhos mais

longos
Suposições (garantem que existe caminho mais curto entre o vértice s e todos os outros)
▪ Existe pelo menos um caminho entre o vértice s e todos os outros;

▪ O grafo não tem circuitos.
sX Vértice a partir do qual se pretende determinar os caminhos mais longos
Notação
m(j) Comprimento do caminho mais longo entre o vértice s e o vértice j

jX
Slide 270
Caminhos ótimos
Exemplo m (2) = 6 m (4) = 8

2
2 4
m (1) = 0 5
6
(s=1) 1 3 3
3
5
3 5
8
m (3) = 3 m (5) = 12
Slide 271
Caminhos ótimos
Proposição
Seja G=(X,A) um grafo orientado e seja sX. Admita-se ainda que
existe pelo menos um caminho entre s e todos os outros vértices.
Sendo m(j) o comprimento do caminho mais longo entre s e j então,
➢ m(j)  m(i) + cij iX tal que (i,j)A;
➢ Se m(j) = m(i) + cij então o arco (i,j) é o último arco num

caminho mais longo entre s e j.
Observação m (i)
i cij
m ( j)
s j
Slide 272
Caminhos ótimos
Se conhecermos os valores m(j) podemos usar a parte 2 da proposição anterior
para ‘recuperar’ os caminhos mais longos entre s e todos os outros vértices…
Exemplo m (2) = 6 m (4) = 8

m(5)=m(2)+c25 2
2 4
(2,5) é o último arco num caminho m (1) = 0 5
mais longo entre 1 e 5 6
1 3 3
m(2)=m(3)+c23 (s=1) 3
5
mais longo entre 1 e 2
3 5
8
m (3) = 3 m (5) = 12
m(3)=m(1)+c13
mais longo entre 1 e 3
Caminho mais longo entre 1 e 5 {(1,3),(3,2),(2,5)}

Comprimento: m(5)=12.
Slide 273
Caminhos ótimos
Determinação dos valores m(j), jX – comprimentos dos caminhos mais longos
m (i)
Observação
i
cij
m (k ) m ( j)
ckj
s k j
m (l )
clj
l
Proposição
Seja G=(X,A) um grafo orientado e seja sX. Admita-se ainda que existe pelo
menos um caminho entre s e todos os outros vértices. m(j) é o comprimento do
caminho mais longo entre s e j se e só se,
m ( j) = max m (i) + c 
ij
i X : ( i , j ) A
Slide 274
Caminhos ótimos
Determinação dos valores m(j), jX – comprimentos dos caminhos mais longos
ALGORITMO
1. m(s)  0;
2. Enquanto não se conhecer m(j) para todo o jX fazer
Considerar um qualquer vértice j tal que não se conhece m(j) mas tal que já
se conhecem os valores de m relativos a todos os seus antecessores. Fazer
m ( j)  max m (i) + c 
ij
i X : ( i , j ) A
Observação Caso se pretenda determinar apenas o comprimento do caminho

mais longo entre s e um determinado vértice tX, o algoritmo
termina quando se obtiver o valor de m(t)
Slide 275
Caminhos ótimos
Exemplo
2
2 4
m(1)=0 5
(s=1) 6
m(3)=max{m(1)+3}=3 3
1 3
m(2) = max{m(1)+5, m(3)+3 } = 3
5
max{ 0 + 5, 3+3}=6 3 5
8
m(4) = max{m(2)+2, m(3)+5 } =
max{ 6 + 2, 3 + 5 } = 8
m(5) = max{m(2)+6, m(3)+8, m(4)+3 } =
max{ 6 + 6, 3 + 8, 8 + 3 } = 12
Caminho mais longo entre 1 e 5 {(1,3),(3,2),(2,5)}

Comprimento: m(5) =12
Slide 276
Caminhos ótimos
O problema da mochila…
➢ Um campista tem uma mochila com uma capacidade máxima de 6 kg;
➢ O indivíduo tem um conjunto de objetos que gostaria de transportar na mochila;
➢ O valor que o indivíduo atribui a cada objeto e o respetivo peso são dados por:
Objeto Valor Peso (kg)

1 7.5 4
2 4 3
3 3 2
4 3.5 1
? Que objetos deve o campista por na mochila de forma a maximizar o

valor total dos objetos escolhidos não excedendo a capacidade? ?
Slide 277
Caminhos ótimos
O problema pode ser formulado como um problema de determinação do
caminho mais longo entre dois determinados vértices num grafo orientado…
▪ Vértices i,b Os objetos incluídos têm um peso total igual a b
Já foi tomada a decisão relativa à inclusão ou não dos objetos 1,…,i
▪ Arcos Estão associados às decisões de inclusão ou não dos objetos
Valor(i+1) 0
i,b i+1,b+peso(i+1) i,b i+1, b
• Corresponde à decisão de incluir o • Corresponde à decisão de não

objeto i+1; incluir o objeto i+1;
• O valor do arco será o valor do • O valor do arco será 0.
objeto.
Slide 278
Caminhos ótimos
Objeto
1
Valor
7.5
Peso (kg)
4
2 4 3
3 3 2
4 3.5 1 1,6 2,6 3,6 4,6 Fim
1,5 2,5 3,5 4,5
1,4 2,4 3,4 4,4
1,3 2,3 3,3 4,3
1,2 2,2 3,2 4,2
1,1 2,1 3,1 4,1
Início 1,0 2,0 3,0 4,0
Alguns vértices não são necessários por não serem alcançáveis…
Slide 279
Caminhos ótimos
Grafo com os vértices relevantes e com os pesos nos arcos
3,6 0 4,6 0 Fim

3 0
3.5
3,5 0 4,5
0
3
3.5
0 0 0
1,4 2,4 3,4 4,4 0
3.5 0
0 0
2,3 3,3 4,3
3.5 0
0 4,2
7.5 3,2
0
4
3 4,1
3.5
0 0 0 0
Início 1,0 2,0 3,0 4,0
Slide 280
Caminhos ótimos
Determinação do caminho mais longo
10.5 10.5 11
3,6 0 4,6 0 Fim
3 0
3.5
7
3,5 011 4,5
7.5 7.5 0
3
3.5
1,4
0
2,4 0 3,4 0 7.5 4,4 0
7.5
4 3.5 6.5 0
0 0
2,3 3,3 4,3
4
3.5 0
3 3,2 03 4,2
7.5
0
4 3.5
3 4,1
0 0 0 0 3.5 0
0 0 0 0
Início 1,0 2,0 3,0 4,0
Slide 281
Caminhos ótimos
➢ Qualquer caminho entre ‘Início’ e ‘Fim’, define uma solução admissível para o
campista e vice-versa;
➢ O valor de um caminho desses é igual ao valor da solução admissível

correspondente;
➢ Determinar a solução ótima para o problema da mochila equivale a

determinar o caminho de maior valor – mais longo – entre ‘Início’ e ‘Fim’ no
grafo construído.
Caminho mais longo:
7.5 0 0 3.5 0
Início 1,4 2,4 3,4 4,5 Fim
A solução ótima corresponde a incluir os

objetos 1 e 4, com um valor total de 11!
Slide 282
Programa
1. Introdução
DEPARTAMENTO DE ESTATÍSTICA E INVESTIGAÇÃO OPERACIONAL 4. Planeamento de projetos
Planeamento de projetos que envolvem um grande número de atividades
Problema complexo especialmente se há uma

ordem específica para a execução das atividades
PERT (Project Evaluation and Review Technique)
CPM (Critical Path Method)
Métodos mais ‘populares’ no tratamento deste tipo de problemas

➢ Foram desenvolvidos quase em simultâneo na década de 50
Slide 284
Conceitos iniciais
Os métodos PERT e CPM permitem
➢ Planear o projeto antecipadamente e prever quais as atividades

suscetíveis de atrasar a conclusão do projeto;
➢ Realizar as várias atividades de acordo com a sequência pré-estabelecida

e controlar a sua realização de modo a garantir a conclusão do projeto o
mais cedo possível, isto é, em caso de atrasos, prever se estes podem ou
não implicar um atraso na conclusão do projeto global e, em caso
afirmativo, de quanto tempo.
Método PERT Desenvolvido pela marinha Americana

(Programação do desenvolvimento dos mísseis Polaris)
Método CPM Conjunto de técnicas algo semelhantes às do método PERT
Slide 285
Conceitos iniciais
Aplicações dos métodos PERT e CPM
• Construção de edifícios, pontes, autoestradas, linhas de caminho de ferro,

etc...;
• Planeamento de operações de manutenção (plataformas petrolíferas,

navios, aviões, etc...);
• Desenvolvimento de armamento ou de outro tipo de produtos tais como

aviões, barcos, computadores, etc...;
• Projetos mais simples envolvendo um menor número de atividades tais

como a restauração de um edifício ou uma simples alteração de uma
casa.
Slide 286
Conceitos iniciais
Exemplo (Remodelação de uma cozinha)
Um pequeno projeto consiste na remodelação de uma cozinha. As atividades

que têm que ser desenvolvidas são as seguintes:
A: Mudança da canalização da água

B: Mudança da canalização do gás
C: Montagem de um novo pavimento
D: Rebocar e pintar a parede
E: Reforço da instalação elétrica
F: Colocação de iluminação
G: Instalação de equipamento
Naturalmente, estas atividades devem ser realizadas por uma determinada

ordem, uma vez que o início de algumas delas depende da conclusão de
outras. De facto,
Slide 287
Conceitos iniciais
Exemplo (continuação) B: Mudança da canalização do gás
C: Montagem de um novo pavimento
D: Rebocar e pintar a parede
A deve preceder C e D E: Reforço da instalação elétrica
B deve preceder D F: Colocação de iluminação
C deve preceder G
D deve preceder F e G
E deve preceder F
O tempo de duração de cada atividade é dado, em dias, por
A B C D E F G
3 2 1 4 1 1 3
O objetivo é determinar o prazo mínimo para a remodelação da cozinha.
Slide 288
Conceitos iniciais
Definição
Quando, num projeto envolvendo várias atividades, existem atividades cujo
início depende da conclusão de outra ou de outras atividades, diz-se que
existe uma relação de precedência orientada entre as atividades.
Os métodos PERT e CPM permitem tratar problemas como o anterior
Representação do problema através de um grafo
Vamos considerar uma representação dos problemas através de um

grafo orientado em que as atividades são representadas pelos arcos
Slide 289
Redes com atividades nos arcos – construção
1. Cada atividade do projeto é representada por um único arco;
2. Os vértices representam momentos específicos do tempo que se identificam

com o início ou fim de uma ou mais atividades;
3. A orientação dos arcos é utilizada para representar a sequência das

atividades a realizar: Se uma atividade precede outra, a segunda só pode ser
realizada depois da primeira estar terminada;
4. Sempre que necessário utilizam-se atividades fictícias – com duração nula –

de forma a evitar ambiguidades na rede;
5. Os vértices são numerados de forma que o vértice inicial de um arco tenha

sempre número inferior ao vértice final.
Slide 290
Existem diversas formas de representar um projeto através de uma rede.

Aquela que se descreveu designa-se por precedência-orientada.
G=(X,A) Projeto
Grafo orientado – rede de atividades
A Atividades ou tarefas
(Conjunto de arcos)
X Acontecimentos
(Conjunto de vértices) (Início ou conclusão de atividades)
Slide 291

‘Metodologia’ para construção de redes com atividades nos arcos
➢ Associar um arco a cada atividade;
➢ Utilizar atividades fictícias para estabelecer as precedências;
➢ Simplificar a rede;
➢ Numerar os vértices da rede.
Atividade T1 Atividade T2
… Atividade Tn
T1
Se T1 precede T2
Atividade fictícia – duração 0
T2
T1 T2
Slide 292

Simplificação / condensação da rede
➢ As atividades que não têm precedentes podem iniciar o projeto. Os

arcos correspondentes podem ter início no mesmo vértice, o qual
representará o início do projeto
T’
T’
T’’ T’’
T’’’ T’’’
Vértice que representa

Atividades sem
o início do projeto
precedentes
Slide 293

➢ As atividades que não precedem qualquer outra podem terminar o

projeto. Os arcos correspondentes podem convergir no mesmo
vértice, o qual representará o instante de conclusão do projeto
T’
T’
T’’ T’’
T’’’ T’’’
Atividades que não Vértice que representa

precedem qualquer outra a conclusão do projeto
Slide 294

➢ Se uma atividade fictícia é a única a convergir num vértice, pode ser

eliminada – juntam-se os vértices correspondentes
T’’’ T’’’
T’ T’
T’’ T’’
➢ Se uma atividade fictícia é a única a divergir de vértice, pode ser

eliminada – juntam-se os vértices correspondentes
T’ T’’’ T’ T’’’
T’’ T’’
Slide 295

Numeração dos vértices
➢ Ao vértice inicial de um arco vamos atribuir um número inferior

ao do vértice final
Só vamos atribuir número a um vértice tal que todos os seus

antecessores já tenham sido numerados
1 1 2 1 2
Slide 296
Exemplo (Planificação da remodelação da cozinha)

B: Mudança da canalização do gás A deve preceder C e D
C: Montagem de um novo pavimento B deve preceder D
D: Rebocar e pintar a parede C deve preceder G
E: Reforço da instalação elétrica D deve preceder F e G
F: Colocação de iluminação E deve preceder F
Equivalentemente
C tem como precedente A

D tem como precedentes A e B
F tem como precedentes D e E
G tem como precedentes C e D
Slide 297
Exemplo (Continuação)
Atividades com que o projeto se pode iniciar A, B, E
Atividades com que o projeto pode terminar F, G
C
A F
D
B G
Slide 298
Introdução das precedências
C
A G
D
B F
Slide 299
Exemplo (Continuação) Simplificação / condensação da rede

C
A G
D
B F
A G
D
B F
E
Slide 300
A G
D
B F
E
A G
D
B F
E
Slide 301
A G
D
B F
E
C
G
A
D
B
F
E
Slide 302
C
G
A
D
B
F
E
C
A G
B D
E F
Slide 303
Exemplo (Continuação) Numeração dos vértices
2
C 5
A G
B 3
D
1 4 7
E F
6
Slide 304
Generalidades
Definição
Num problema de planeamento de atividades designa-se por
acontecimento o momento que marca a conclusão de uma ou de
várias atividades ou, então, o início do projeto.
Observação
Quando se representa um projeto através de uma rede com as
atividades nos arcos tal como fizemos atrás, os acontecimentos
estão associados aos vértices.
Slide 305
Generalidades
Exemplo (continuação) 2
C 5
A G
B 3
D
1 4 7
O vértice 1 representa o início do projeto
E F
6
O vértice 2 representa a conclusão da atividade A;
Também representa o início da atividade C
O vértice 3 representa a conclusão da atividade B (e A…);

Também representa o início da atividade D
…
O vértice 7 representa a conclusão das atividades

G e F – Conclusão do projeto
Slide 306
Generalidades
Projeto
Rede de atividades Grafo orientado G=(X,A)
|X| n (número de vértices)
tij Tempo de duração da atividade (i,j)
? Prazo mínimo para a conclusão do projeto ?

O problema pode ser formulado em Programação Linear
Slide 307
Generalidades
yi Data de realização do acontecimento associado ao vértice i
i X
Tendo em conta a forma como numerámos os vértices tem-se:
y1 Data de início do projeto

yn Data de conclusão do projeto
yn − y1 Tempo utilizado na execução de todo o projeto
Slide 308
Generalidades
Problema que consiste em determinar o prazo mínimo para a execução

do projeto:
Min yn − y1 O tempo disponível para realizar a

atividade (i,j) tem que ser pelo
s. a: y j − yi  tij (i, j )  A menos igual ao tempo necessário
yi  0 i X para executar a atividade
As datas de realização dos

vértices são não negativas
Este problema pode ser resolvido:

• Utilizando uma técnica geral para problemas de Programação Linear
• Por inspeção
Slide 309
Generalidades
Resolução do problema anterior por inspeção
y1 = 0
y 2 , y3 ,  y n Escolhe-se o valor mais baixo possível

que garante a satisfação das restrições
Slide 310
Generalidades
Exemplo (Planificação da remodelação da cozinha)

Min y7 − y1
2
C 5 s. a: y2 − y1  3
A G y3 − y1  2
B D y5 − y 2  1 y3 − y 2  0
1 3 4 7
y 4 − y3  4 y5 − y 4  0
E F y6 − y1  1
y6 − y 4  0
6 y7 − y6  1
y 7 − y5  3
y3 − y 2  0
y5 − y 4  0
y6 − y 4  0
y1 , , y7  0
Slide 311
Generalidades
Min y7 − y1 y1 = 0
s. a: y2 − y1  3 y2 = ? y1 = 0  y2  3 y2 = 3
y3 − y1  2 y1 = 0  y3  2
y3 = ? y3 = 3
y5 − y2  1 y 2 = 3  y3  3
y4 − y3  4 y3 = 3  y 4  7 y4 = 7
y4 = ?
y6 − y1  1
y 2 = 3  y5  4 y5 = 7
y7 − y6  1 y5 = ?
y 4 = 7  y5  7
y7 − y5  3
y3 − y2  0 y6 = ? y1 = 0  y6  1 y6 = 7
y5 − y4  0 y 4 = 7  y6  7
y6 − y4  0 y7 = ? y5 = 7  y7  10 Prazo mínimo para a
y7 = 10
y6 = 7  y7  8 conclusão do projeto
y1 ,, y7  0
Slide 312
Generalidades
A análise anterior dá-nos alguma informação:

• Indica-nos o prazo mínimo para a conclusão do projeto.
Contudo, esta abordagem pouco (ou nada) nos diz acerca das atividades:
• Não sabemos se as atividades têm alguma margem de manobra

(dentro do prazo mínimo para a execução do projeto)
• Não temos uma identificação das atividades cuja execução deveremos

controlar com mais atenção por serem atividades em cujo um atraso
possa provocar um atraso em todo o projeto
O método CPM ajuda a colmatar estas lacunas!
Slide 313
Método CPM
Definição
Seja G=(X,A) uma rede de atividades. A data mais cedo em que é
possível ocorrer o acontecimento a que corresponde o vértice jX
designa-se por data mais cedo do vértice j e representa-se por Ej.
G=(X,A) Rede de atividades com n vértices

j X Acontecimento ‘conclusão de todas as tarefas cujos arcos
convergem em j’
tij Duração da atividade (i,j)A
El
l tlj
O acontecimento j só se dá
E j = max Ei + t ij 
Er trj Ej
quando todas as tarefas que
r j
( i , j )A convergem em j estiverem
Es terminadas
s tsj
Slide 314
Método CPM
En Data mais cedo de conclusão do projeto
(conclusão de todas as atividades)
j X
E j = max Ei + t ij  Equação recursiva Inicia-se fazendo E1 = 0
( i , j )A
3 7
2
C 5
E1 = 0 A 1
3 3 G 10
0
E2 = max{E1+t12} = 3 3
B 3
D
E3 = max{E1+t13,E2+t23} = 3 1 4 7
2 4 7
E4 = max{E3+t34} = 7 1
1 E F
E5 = max{E2+t25,E4+t45} = 7 6
E6 = max{E1+t16,E4+t46} = 7 7
E7 = max{E5+t57,E6+t67} = 10 10 dias é o prazo mínimo

para a conclusão de todo o projeto
Slide 315
Método CPM
Equações recursivas que permitem encontrar os valores Ej
Equações recursivas que permitem encontrar o valor do

caminho mais longo entre 1 e j
Ej = Comprimento do caminho mais longo entre 1 e j
En = Comprimento do caminho mais longo entre 1 e n

(Prazo mínimo para a
conclusão do projeto)
Slide 316
Método CPM
Definição
Seja G=(X,A) uma rede de atividades. A data mais tarde em que é
possível ocorrer o acontecimento a que corresponde o vértice jX de
forma a que todo o projeto fique concluído na data mais cedo (En)
designa-se por data mais tarde do vértice j e representa-se por Lj.

j X Acontecimento ‘início de todas as tarefas cujos arcos
divergem de j’
tij Duração da atividade (i,j)A
Ll
O acontecimento j tem que ocorrer
L j = min Li − t ji 
tjl l
num prazo tal que os acontecimen-
Lj tjr Lr tos que lhe sucedem possam estar
( j ,i )A
j r terminadas nos respetivos prazos
máximos
tjs Ls
s
Slide 317
Método CPM
j X
L j = min Li − t ji  Equação recursiva Inicia-se fazendo Ln = En

( j ,i )A
3 7
3 7
L7 = E7 = 10
2
C 5
L6 = min{L7-t67} = 9 0
A 1 10
3 3 3 G 10
0
L5 = min{L7-t57} = 7 3
B 3
D 7
1 4 7
L4 = min{L5-t45,L6-t46} = 7 2 4 7
L3 = min{L4-t34} = 3 E 1
1 F
L2 = min{L3-t23,L5-t25} = 3 6
L1 = min{L2-t12,L3-t13,L6-t16} = 0 9
7
Slide 318
Método CPM
Definição
Seja G=(X,A) uma rede de atividades.
➢ Define-se como folga de um acontecimento e representa-se por

F, a diferença entre as datas mais tarde e mais cedo do
acontecimento. Concretamente, se o acontecimento estiver
associado ao vértice j, a sua folga é dada por Fj = Lj-Ej;
➢ Um acontecimento com folga nula diz-se um acontecimento

crítico.
Observação
A folga de um acontecimento (vértice) indica o atraso máximo com que é
possível atingir esse sem que todo o projeto se atrase
Slide 319
Método CPM
Exemplo (Continuação) 3 7
3 7
2
C 5
0
A 1 10
Vértice Ej Lj Fj 3 3 3 G 10
0
1 0 0 0 B 3
D 7
1 3 4 7
2 3 3 0 2 4 7
3 3 3 0 E 1
4 7 7 0 1 F
6
5 7 7 0
6 7 9 2 9
7 10 10 0 7
Acontecimentos críticos 1 2 3 4 5 7
Slide 320
Método CPM
De forma a controlar melhor a execução de um projeto pode-se determinar,

para cada atividade, um conjunto de valores que permitem perceber quais as
atividades cuja execução deve ser mais controlada de forma a que o projeto
possa estar concluído o mais cedo possível.
➢ Data mais cedo de início;

Para cada atividade
➢ Data mais tarde de início;

➢ Data mais cedo de conclusão;
➢ Data mais tarde de conclusão;
➢ Folga.
Todos estes valores são determinados de forma que o projeto termine o mais
cedo possível
Slide 321
Método CPM
G=(X,A) Rede de atividades
Ei tij Lj
Atividade (i,j)
i j
❑ Data mais cedo de início da atividade (i,j) Ei

A atividade (i,j) só se pode iniciar depois de se dar o acontecimento a que
está associado o vértice i. A data mais cedo para isso acontecer é Ei.
❑ Data mais cedo de conclusão da atividade (i,j) Ei+tij

A atividade (i,j) terminará o mais cedo possível se se iniciar o mais cedo
possível ou seja se se iniciar no instante Ei. Nesse caso, terminará no instante
Ei+tij.
Slide 322
Método CPM
Ei tij Lj
i j
❑ Data mais tarde de conclusão da atividade (i,j) Lj

A data mais tarde de conclusão da atividade (i,j) - de forma a que o projeto
termine o mais cedo possível - será a data mais tarde em que se pode dar o
acontecimento associado ao vértice j, ou seja Lj.
❑ Data mais tarde de início da atividade (i,j) Lj-tij

A atividade (i,j) tem que estar terminada no máximo no instante Lj. Como ela
tem uma duração de tij, terá que se iniciar, no máximo, no instante Lj-tij.
Slide 323
Método CPM
Ei tij Lj
i j
❑ Folga da atividade (i,j) Lj-Ei-tij
Representa a margem de manobra da atividade (i,j). Obtém-se fazendo a
diferença entre as datas de início mais tarde e mais cedo ou entre datas de
conclusão mais tarde e mais cedo.
Ei+tij
Atividade (i,j)
Ei Lj-tij Lj
Atividade Duração Data mais Data mais cedo Data mais Data mais tarde Folga
cedo de início de conclusão tarde de início de conclusão
(i,j) tij Ei Ei+tij Lj-tij Lj Lj-Ei-tij
Slide 324
Método CPM
Definição
Seja G=(X,A) uma rede de atividades.
➢ Uma atividade com folga nula diz-se uma atividade crítica;
➢ Um caminho formado apenas por atividades críticas e que

tenha origem no vértice que representa o início do projeto e fim
no vértice que representa a conclusão do projeto diz-se um
caminho crítico.
Slide 325
Método CPM
3 7
3 7
C
2 5
1
Exemplo (Continuação) 0
0 A
3
3 G
10
10
B 2 3 D 7 3
1 3 4 4 7 7
1
E 1
F
6
9
7
Atividade Duração Data mais Data mais cedo Data mais Data mais tarde Folga
cedo de início de conclusão tarde de início de conclusão
(i,j) tij Ei Ei+tij Lj-tij Lj Lj-Ei-tij
A (1,2) 3 0 3 0 3 0
B (1,3) 2 0 2 1 3 1
C (2,5) 1 3 4 6 7 3
D (3,4) 4 3 7 3 7 0
E (1,6) 1 0 1 8 9 8
F (6,7) 1 7 8 9 10 2
G (5,7) 3 7 10 7 10 0
Slide 326
Método CPM
Exemplo (Continuação) 3 7
3 7
2
C 5
0
A 1 10
3 3 3 G 10
0
B 3
1 3
D 7
7
4
2 4 7
E 1
1 F
Atividades críticas A D G 6
9
Caminho crítico {(1,2),(2,3),(3,4),(4,5),(5,7)} 7
Slide 327
Método CPM
Proposição
Seja G = (X,A) uma rede de atividades com n vértices,
representando o vértice 1 o início do projeto e o vértice n a
conclusão.
➢ Qualquer caminho mais longo entre 1 e n é um caminho crítico;
➢ Se (i,j)A for uma atividade crítica então o arco (i,j) pertence a

um caminho mais longo entre 1 e n.
Proposição
Seja G = (X,A) uma rede de atividades. Qualquer vértice envolvido
num caminho crítico é um vértice crítico.
Slide 328
Método CPM
Observação
A determinação do(s) caminho(s) mais longo(s) entre os vértices inicial e

terminal de uma rede de atividades dá-nos:
➢ O prazo mínimo para a conclusão do projeto (comprimento do(s)

caminho(s) mais longo(s));
➢ Atividades críticas (todas as atividades cujo arco está num dos

caminhos mais longos encontrados);
➢ Vértices críticos (todos os vértices que estão em algum dos caminhos

mais longos encontrados).
Slide 329
Método CPM
Caminho mais longo entre 1 e 7

2
C 5
A 1
3 3 G
{{1,2},{2,3},{3,4},{4,5},{5,7}}
B 3
D
1 4 7
Comprimento = 10 2 4
E 1
1 F
Prazo mínimo para a 6
conclusão do projeto
Atividades críticas: A, D e G
Vértices críticos: 1, 2, 3, 4, 5 e 7
Slide 330
Cronogramas
Usando toda a informação relativa às atividades podemos construir um gráfico
Cronograma
Eixo das abcissas Tempo

Eixo das ordenadas Atividades
tij
Atividade (i,j) não crítica

Ei Lj-tij Ei+tij Lj
tij
Atividade (i,j) crítica

Ei Lj
tij
Slide 331
Cronogramas
Cronograma (atividades com início na data mais cedo)
Atividades
G (5,7)
F (6,7)
E (1,6)
D (3,4)
C (2,5)
B (1,3)
A (1,2)
1 2 3 4 5 6 7 8 9 10 Tempo
Slide 332
Cronogramas
Cronograma (datas mais cedo com pessoal especializado)
Atividades
Técnico de eletrodomésticos
G
Eletricista
F
Eletricista
E
Pedreiro 2
D
Pedreiro 1
C
Canalizador 2
B
Canalizador 1
A
1 2 3 4 5 6 7 8 9 10
Tempo
Slide 333
Análise Tempo/custo
Análise feita até aqui Predominância do fator tempo
Mas....
A execução de uma atividade acarreta custos
diretos indiretos
• Aquisição de material • Supervisão do projeto
• Aquisição de equipamento • Overheads
• Mão-de-obra • ...
• ...
Slide 334
Versão original do método CPM Igual importância é dada aos fatores
Tempo Custo
Considera-se uma função para cada atividade que relaciona

• Custos diretos associados à atividade
• Duração da atividade
Dois pontos servem de referência

• Atividade executada em tempo ‘normal’
Não se incorre em custos extraordinários (como por exemplo
trabalho extraordinário)
• Atividade executada no menor espaço de tempo possível
Nenhum custo é poupado para que se consiga acelerar a
execução da atividade
Slide 335
Custo direto
da atividade
Custo acelerado Acelerado

(no limite)
Custo normal Normal
Duração acelerada Duração Tempo de duração

(no limite) normal da atividade
Slide 336
Frequentemente assume-se que
Todos os pontos intermédios que relacionam o tempo e o custo direto

de execução de uma atividade
• são admissíveis
• pertencem ao segmento que une os dois pontos de referência -
‘Normal’ e ‘Acelerado’
Para cada atividade, as únicas estimativas que é necessário obter são

as que estão associadas aos dois pontos de referência
E a realidade?!
Slide 337
Custo direto
da atividade
Custo acelerado Acelerado

(no limite)
Custo normal Normal
Duração acelerada Duração Tempo de duração

(no limite) normal da atividade
Slide 338
Novo objetivo na análise de um projeto:
Determinação do nível tempo/custo a que deve ser executada cada

atividade de forma a que seja possível completar o projeto dentro de
um prazo previamente estabelecido, minimizando o custo total (direto)
envolvido
Slide 339
Vértice 1 Início do projeto

Vértice n Conclusão do projeto
Notação adicional:
Dij Duração normal da atividade (i,j)A;

Cij Custo de execução da atividade (i,j) )A se executada em tempo normal;
d ij Duração acelerada (no limite) da atividade (i,j)A;
cij Custo de execução da atividade (i,j)A se executada de forma acelerada

(no limite);
Slide 340
Custo direto
da atividade
cij Acelerado
Cij − cij
Declive Sij =
Custo direto da Dij − d ij
atividade (i,j) se a Cij Normal
sua duração for xij
d ij xij Dij Tempo de duração

da atividade
Assume-se que ao reduzir a duração da atividade (i,j) o custo

direto da atividade varia segundo uma taxa igual a –Sij
Cij + (-Sij) (Dij-xij)
Slide 341
Exemplo (Problema da remodelação da cozinha) C
2 5
A G
B 3
D
1 4 7
Consideremos a seguinte informação E F

adicional: 6
Atividade Duração normal Duração acelerada Custo normal Custo acelerado

(no limite) (no limite)
A (1,2) 3 1 20 28
B (1,3) 2 1 20 26
C (2,5) 1 - 15 -
D (3,4) 4 1 24 30
E (1,6) 1 - 30 -
F (6,7) 1 - 10 -
G (5,7) 3 2 25 35
Slide 342
Exemplo (Problema da remodelação da cozinha)
Atividade Duração normal Duração acelerada Custo normal Custo acelerado aumento unitário do custo
(no limite) (no limite) = -Sij
A (1,2) 3 1 20 28 4
B (1,3) 2 1 20 26 6
C (2,5) 1 - 15 - -
D (3,4) 4 1 24 30 2
E (1,6) 1 - 30 - -
F (6,7) 1 - 10 - -
G (5,7) 3 2 25 35 10
C12 − c12 20 − 28 C34 − c34 24 − 30

S12 = = = −4 S34 = = = −2
D12 − d12 3 −1 D34 − d 34 4 −1
C13 − c13 20 − 26 C57 − c57 25 − 35

S13 = = = −6 S57 = = = −10
D13 − d13 2 −1 D57 − d 57 3− 2
Slide 343
Atividade Duração normal Duração acelerada aumento unitário do custo

(no limite) = -Sij
A (1,2) 3 1 4
B (1,3) 2 1 6
C (2,5) 1 - -
D (3,4) 4 1 2
E (1,6) 1 - -
F (6,7) 1 - -
G (5,7) 3 2 10
duração duração
Caminhos de 1 a 7 duração reduzindo D 3 dias reduzindo A 1 dia
A-C-G 7 7 6
A-D-G 10 7 6
A-D-F 8 5 4
B-D-G 9 6 6
B-D-F 7 4 4
E-F 2 2 2
custo adicional=3x2=6 custo adicional=4
Custo total = 20+20+15+24+30+10+25 + 6 +4 = 154
Slide 344
Para problemas reais de grande dimensão…
Novo objetivo na análise de um projeto:

Determinação do nível tempo/custo a que deve ser executada cada
atividade de forma a que seja possível completar o projeto dentro de
um prazo previamente estabelecido, minimizando o custo total (direto)
envolvido
Formulação em Programação Linear
Slide 345
Vértice 1 Início do projeto

Notação: Vértice n Conclusão do projeto
Dij Duração normal da atividade (i,j)A;
Cij Custo de execução da atividade (i,j) )A se executada em tempo normal;
d ij Duração acelerada (no limite) da atividade (i,j)A;
cij Custo de execução da atividade (i,j)A se executada de forma acelerada

(no limite);
T Limite imposto para a duração total do projeto
Variáveis de decisão
xij Duração da atividade (i,j)A
yi Data de realização do vértice iX
Slide 346
Custo direto
da atividade
K ij Ordenada na origem Cij − Sij Dij
cij Acelerado
Cij − cij
Declive Sij =
Dij − d ij
Cij Normal
d ij Dij Tempo de duração

da atividade
Slide 347
Custo direto
da atividade
K ij
Acelerado
K ij + Sij xij Declive Sij

Normal
xij Tempo de duração

da atividade
Custo direto da atividade (i,j) se a sua duração for xij
Slide 348
Formulação em Programação Linear
Min  (K ij + Sij xij ) K ij + Min S

( i , j )A
x
ij ij
( i , j ) A ( i , j )A
(Custo direto total) s. a: y j − yi  xij (i, j )  A

d ij  xij  Dij (i, j )  A
y n − y1  T
xij  0 (i, j )  A
yi  0 i X
Slide 349
2
C 5
A G
Consideremos a seguinte informação
adicional: B D
1 3 4 7
T=6
Atividade Duração normal Duração acelerada Custo normal Custo acelerado
E F
(no limite) (no limite)
6
A (1,2) 3 1 20 28
B (1,3) 2 1 20 26
C (2,5) 1 - 15 -
D (3,4) 4 1 24 30
E (1,6) 1 - 30 -
F (6,7) 1 - 10 -
G (5,7) 3 2 25 35
C12 − c12 20 − 28 C −c 24 − 30 C57 − c57 25 − 35

S12 = = = −4 S34 = 34 34 = = −2 S57 = = = −10
D12 − d12 3 −1 D34 − d 34 4 −1 D57 − d 57 3− 2
C13 − c13 20 − 26
S13 = = = −6
D13 − d13 2 −1
Slide 350
Min − 4 x12 − 6 x13 − 2 x34 − 10 x57 2

C 5
A G
s. a: y2 − y1  x12 1  x12  3
y3 − y1  x13 B D
1  x13  2 1 3 4 7
y5 − y 2  1 1  x34  4 E F
y4 − y3  x34 2  x57  3 6
y6 − y1  1 y7  6
y7 − y6  1 x12 , x13 , x34 , x57  0
y7 − y5  x57 y1 ,  , y7  0
y3 − y 2  0
y5 − y 4  0
y6 − y 4  0
Slide 351
Exemplo (Problema da remodelação da cozinha) Input do Solver Excel
y1 y2 y3 y4 y5 y6 y7 x12 x13 x34 x57 RHS
0 0 0 0 0 0 0 0 0 0 0
OBJ -4 -6 -2 -10 0
REST1 -1 1 -1 0
REST2 -1 1 -1 0
REST3 -1 1 0 1
REST4 -1 1 -1 0
REST5 -1 1 0 1
REST6 -1 1 0 1
REST7 -1 1 -1 0
REST8 -1 1 0 0
REST9 -1 1 0
REST10 -1 1 0
REST11 1 0 1
REST12 1 0 1
REST13 1 0 1
REST14 1 0 2
REST15 1 0 3
REST16 1 0 2
REST17 1 0 4
REST18 1 0 3
REST19 1 0 6
Slide 352
Microsoft Excel 12.0 Relatório de respostas Output do
Folha de cálculo: [activida.xlsx]Folha1
Relatório gerado: 29-04-2009 15:25:13
Solver Excel
Célula de destino (Mín)

Célula Nome Valor original Valor final
$N$3 0 -52
Células ajustáveis
Célula Nome Valor original Valor final
$C$2 y1 0 0
$D$2 y2 0 2
$E$2 y3 0 2
$F$2 y4 0 3
$G$2 y5 0 3
$H$2 y6 0 3
$I$2 y7 0 6
$J$2 x12 0 2
$K$2 x13 0 2
$L$2 x34 0 1
$M$2 x57 0 3
Slide 353
2
C 5
A 1
[1,3] G
B D [2,3]
1 3 4 7
[1,2] [1,4]
E 1 y2 = 2 y5 = 3
1 F
6 2
C 5
A 1
G y7 = 6
y1 = 0 2 3
B 3
D
1 4 y4 = 3 7
2 1
y3 = 2
E 1
1 F
6
y6 = 5
Slide 354
y2 = 2 y5 = 3
2
C 5
A 1
G y7 = 6
y1 = 0 2 3
B 3
D
1 4 y4 = 3 7
2 1
y3 = 2
E 1
1 F
6
y6 = 5
K12 = C12 − S12D12 = 20 + 4x3 = 32 Custo direto total:

K13 = C13 − S13D13 = 20 − (−6)2 = 32 − 52 + 32 + 32 + 32 + 55 + 15 + 30 + 10 = 154
K 34 = C34 − S34D34 = 24 − (−2)4 = 32
K 57 = C57 − S57D57 = 25 − (−10)3 = 55 Custos das atividades C, E, F
Slide 355
Programa
1. Introdução
DEPARTAMENTO DE ESTATÍSTICA E INVESTIGAÇÃO OPERACIONAL 5. O problema de afetação
n indivíduos n tarefas
1 1
2 cij 2
... tempo ...
i desempenho j
... custo ...
...
n n
Objetivo: determinar a melhor forma de afetar os indivíduos às tarefas de

forma a que cada indivíduo execute exatamente uma tarefa e que cada
tarefa seja executada por exatamente um indivíduo.
Medida de performance a otimizar valor global associado

a todas as afetações
Slide 357
Introdução
Exemplo
Uma fábrica de brinquedos pretende montar uma linha de montagem para
4 bonecos diferentes. Cada um destes bonecos deverá ser produzido por
uma máquina diferente. Para cada uma das quatro máquinas disponíveis
conhecem-se os custos de produção de cada boneco.
Boneco
1 2 3 4
1 5 2 3 4
Máquina 2 7 8 4 5
3 6 3 5 6
4 2 2 3 5
Pretende-se determinar qual a máquina que deverá produzir cada boneco

de forma a minimizar o custo total de produção.
Slide 358
Introdução
Um problema de afetação fica completamente definido pela sua matriz

de valores de afetação
Formulação em Programação Matemática
1 se o indivíduo i é afeto à tarefa j

xij =  i, j = 1,...,n
0 caso contrário
cij Custo de afetar o indivíduo i à tarefa j i, j = 1,..., n
Slide 359
Introdução
n n
Min z =  cij xij Custo global
i =1 j =1
n
s. a: x
j =1
ij =1 i = 1,..., n Cada indivíduo realiza uma tarefa
x
i =1
ij =1 j = 1,..., n Cada tarefa é realizada por um indivíduo
xij  0,1 i, j = 1,..., n Domínio
Exatamente n variáveis são iguais a 1

Numa solução admissível
As restantes são iguais a 0
Slide 360
Introdução
Exemplo (continuação) Boneco
1 2 3 4
1 5 2 3 4
Uma solução admissível: Máquina 2 7 8 4 5
3 6 3 5 6
4 2 2 3 5
Afetar a máquina 1 ao boneco 1 x11 = 1 Custo 5 Custo desta solução

Afetar a máquina 2 ao boneco 2 x22 = 1 Custo 8
23
Restantes variáveis
Slide 361
Sem perdermos a generalidade, no que se segue, vamos assumir que

estamos perante um problema de afetação com um objetivo de
minimização.
Se cij  0 i, j = 1,..., n
Não existe qualquer solução com custo negativo.
Qualquer solução admissível com custo 0 é uma solução ótima.
Slide 362
Proposição 1: Seja C=[cij]i,j=1,...,n a matriz de custos de um problema de

afetação. Se adicionarmos uma constante a cada linha e/ou coluna da matriz,
o problema de afetação associado à nova matriz tem a mesma solução ótima
que o problema inicial.
Demonstração
Suponhamos que
A todos os elementos da linha i se adiciona um valor ai (i=1,...,n)
A todos os elementos da coluna j se adiciona um valor bj (j=1,...,n)
Nova matriz: Cˆ = cîj   i , j =1,..., n

cîj = cij + a i + b j
Designem
Z Função objetivo do problema original
Ẑ Função objetivo do problema transformado
Slide 363
Zˆ =  cîj xij =  (cij + a i + b j )xij

n n n n
i =1 j =1 i =1 j =1
n n n n n n
=   cij xij +  a i xij +  b j xij
i =1 j =1 i =1 j =1 i =1 j =1
 n
n  n  n 
= Z +  a i   xij  +  b j   xij 
i =1  j =1  j =1  i =1 
=1 =1
n n
= Z + ai +  b j
i =1 j =1
Z e Ẑ diferem numa constante independentemente dos valores das variáveis!
Qualquer solução ótima relativamente a uma delas sê-lo-á relativamente à

outra
Slide 364
Resultado anterior
É possível transformar um problema de afetação noutro em que cij0,

i,j=1,...,n e que tenha pelo menos uma solução admissível com custo zero
➢ Para que todos os custos venham não negativos, basta somar, a

todas as linhas e colunas, o valor absoluto do menor elemento
(negativo) da matriz.
➢ Obtenção de uma matriz em que seja possível encontrar uma solução

admissível de valor zero (admitindo cij0, i,j=1,...,n).
Subtraem-se às linhas e colunas, valores apropriados de forma a que

surjam zeros na matriz em quantidade suficiente para que tal solução
admissível seja alcançável.
Slide 365
Exemplo Boneco
1 2 3 4
5 2 3 4 − 3 1 5 2 3 4
7 8 4 5 − 4 Máquina 2 7 8 4 5
6 3 5 6 − 4 3 6 3 5 6
2 2 3 5 − 2
4 2 2 3 5
5 − 3 2−3 3−3 4 − 3 2 − 1 0 1
7 − 4 8−4 4−4 5 − 4 3 4 0 1
6 − 4 3−4 5−4 6 − 4 = 2 − 1 1 2
2 − 2 2−2 3−2 5 − 2 0 0 1 3
2 − 1 0 1 2 − 0 − 1 + 1 0 − 0 1 − 1  2 0 0 0
3 4 0 1 3 − 0 4 +1 0 − 0 1 − 1  3 5 0 0
2 − 1 1 2 2 − 0 − 1 + 1 1 − 0 2 − 1 = 2 0 1 1
0 0 1 3 0 − 0 0 +1 1 − 0 3 − 1 0 1 1 2
− 0 +1 − 0 −1
Slide 366
Exemplo (continuação) Boneco
1 2 3 4
 2 0 0 0 1 5 2 3 4
 3 5 0 0 Máquina 2 7 8 4 5
2 0 1 1 3 6 3 5 6
0 1 1 2
4 2 2 3 5
Nesta matriz de custo encontra-se uma afetação de valor zero
x41 = x32 = x23 = x14 = 1

Solução ótima do problema
Restantes xij iguais a 0
Custo (ótimo): 4+4+3+2=13
(Determinado na matriz original)
Slide 367
Algoritmo Húngaro
(O Algoritmo Húngaro foi desenvolvido por Kuhn, em 1955, tendo as suas raízes num trabalho de
um matemático húngaro – Egerváry – datado de 1931. Daí o nome do método)
Definição Considere-se um problema de afetação com n indivíduos e n tarefas,

sendo [cij] i,j=1,...,n a matriz de custos correspondente. Considere-se, ainda, uma
solução admissível para o problema
➢ Um par (i,j) diz-se afeto se xij=1.
➢ Chama-se afetação a um conjunto de pares afetos.
➢ Uma afetação de custo zero diz-se maximal se não existe outra afetação
de custo zero com mais pares afetos .
➢ Uma afetação diz-se completa se é uma afetação de custo zero com n

pares afetos (solução admissível de valor zero).
Slide 368
Algoritmo Húngaro
Início
A. Inicialização
B. Determinação de uma
afetação maximal
(de custo nulo)
sim
C. Afetação completa? Fim
não
D. Redução dos elementos

não nulos da matriz
Slide 369
Algoritmo Húngaro
A. Inicialização
Dada uma matriz de custos [cij] i,j=1,...,n, a mesma é transformada de forma a

que todos os elementos sejam não negativos e cada linha e coluna
contenham pelo menos um zero
✓ Calcula-se o valor mínimo de cada linha da matriz e subtrai-se esse

valor de cada um dos elementos dessa linha;
✓ Calcula-se o valor mínimo de cada coluna da matriz e subtrai-se esse

valor de cada um dos elementos dessa coluna;
Slide 370
Algoritmo Húngaro
B. Determinação de uma afetação de custo nulo maximal
Proposição 2 (Teorema - König): Seja C=[cij]i,j=1,...,n a matriz de custos de

um problema de afetação. O número de pares afetos numa afetação
maximal de custo nulo é igual ao número mínimo de riscos sobre linhas ou
colunas, necessário para cobrir todos os zeros da matriz.
Determinação de uma afetação de custo nulo maximal
Cobrem-se todos os elementos nulos da matriz, traçando o menor

número possível de riscos sobre as linhas ou colunas da matriz
Após se saber qual a dimensão de uma afetação maximal, tal afetação

encontrar-se-á (nesta disciplina) por observação da matriz. Os
correspondentes zeros assinalam-se de forma especial – por exemplo,
utilizando um ‘*’.
Slide 371
Algoritmo Húngaro
C. Teste de terminação
Seja k o número mínimo de riscos que cobrem todos os zeros da matriz
➢ Se k=n existe uma afetação completa de custo nulo na matriz
➢ Se k<n segue para D
Slide 372
Algoritmo Húngaro
D. Redução dos elementos não nulos da matriz
Proposição 3 (Teorema): Seja C=[cij]i,j=1,...,n a matriz de custos de um

problema de afetação com n indivíduos e n tarefas e tal que cij0, i,j=1,...,n.
Seja k o menor número de riscos necessário para cobrir todos os zeros da
matriz.
Seja m o mínimo dos elementos não cobertos por qualquer risco
(naturalmente, m>0).
Se subtrairmos m a cada linha não coberta e somarmos m a cada coluna

coberta obtém-se uma nova matriz, cuja soma de todos os elementos é
inferior em mn(n-k) à soma de todos os elementos de C.
Slide 373
Algoritmo Húngaro
Observações
➢ Subtrair m a cada linha não coberta e somar m a cada coluna coberta
equivale a subtrair m aos elementos não cobertos e somar m aos
elementos duplamente cobertos.
➢ Se o número mínimo de riscos que cobrem todos os zeros da matriz é
inferior a n então, nas condições do teorema, o decréscimo na soma de
todos os elementos de C é uma quantidade estritamente positiva.
Num número finito de passos é possível reduzir os elementos não nulos

da matriz de forma que seja possível encontrar uma afetação completa de
valor zero (assumindo todos os custos da matriz não negativos).
Slide 374
Algoritmo Húngaro
Boneco
Exemplo 1 2 3 4
1 5 2 3 4
5 2 3 4 Máquina 2 7 8 4 5
7 8 4 5 3 6 3 5 6
6 3 5 6 4 2 2 3 5
2 2 3 5
A. Inicialização
5 2 3 4 − 2 3 0 1 2 3 0 1 1
7 8 4 5 − 4 3 4 0 1 3 4 0 0
6 3 5 6 − 3 3 0 2 3 3 0 2 2
2 2 3 5 − 2 0 0 1 3 0 0 1 2
−1
Todos os elementos são não negativos
e existe pelo menos um zero em cada
linha e em cada coluna
Slide 375
Algoritmo Húngaro
3 0 1 1
3 4 0 0
3 0 2 2
0 0 1 2
O número mínimo de riscos necessário para cobrir todos os zeros da matriz é 3

Por exemplo
3 0 1 1
3 4 0 0
3 0 2 2
0 0 1 2
Slide 376
Algoritmo Húngaro
3 0 1 1
3 4 0 0
3 0 2 2
0 0 1 2
k =3<n
A afetação maximal não é completa
Segue para D
Slide 377
Algoritmo Húngaro
3 0 1 1
3 4 0 0
3 0 2 2
0 0 1 2
Determina-se o mínimo dos

elementos não cobertos m = min{3,1,1,3,2,2}=1
Subtrai-se m aos elementos não cobertos 2 0 0 0

3 5 0 0
Soma-se m aos elementos duplamente cobertos 2 0 1 1
0 1 1 2
Slide 378
Algoritmo Húngaro
2 0 0 0
3 5 0 0
2 0 1 1
0 1 1 2
O número mínimo de riscos necessário para cobrir todos os zeros da matriz é 4

Por exemplo
2 0 0 0
3 5 0 0
2 0 1 1
0 1 1 2
Slide 379
Algoritmo Húngaro
2 0 0 0
3 5 0 0
2 0 1 1
0 1 1 2
k =4=n
Uma afetação maximal é completa
Pode agora identificar-se uma afetação completa de valor zero que se sabe existir
Slide 380
Algoritmo Húngaro
2 0 0 0 *
3 5 0* 0 
2 0* 1 1 
0 * 1 1 2 
O algoritmo termina!
Pares afetos: (1,4), (2,3), (3,2) e (4,1) x14 = x23 = x32 = x41 = 1
Restantes xij iguais a 0
Slide 381
Algoritmo Húngaro
Máquina 1 Boneco 4 c14=4

Custo total: 13
Há uma solução ótima alternativa:
 2 0 0* 0 
3 5 0 0 *
 2 0* 1 1
0 * 1 1 2 
Slide 382
Algoritmo Húngaro
Observações
➢ Após a aplicação do algoritmo Húngaro, o custo da solução ótima pode ser
determinado somando todos os valores subtraídos às linhas e colunas em
todas as reduções feitas à matriz.
➢ A implementação do algoritmo Húngaro requer alguns cuidados,
nomeadamente na determinação de uma afetação maximal e no traçar
dos riscos que cobrirão todos os zeros da matriz.
➢ Um problema de afetação em que o número de indivíduos e de tarefas não
coincide pode transformar-se o problema num problema de afetação
‘equilibrado’:
▪ Caso haja menos indivíduos (tarefas) do que tarefas (indivíduos) pode-se
considerar tantos indivíduos (tarefas) ‘fictícios’ quantos os necessários para
equilibrar o problema.
▪ Todos os custos que envolvem um indivíduo (tarefa) fictício serão nulos.
Slide 383
Algoritmo Húngaro
Observações
➢ O algoritmo Húngaro pode ser utilizado para resolver um problema de

afetação em que o objetivo seja a maximização de uma medida de
performance. Para tal basta multiplicar por –1 todos os elementos da
matriz de custos aplicando o algoritmo à matriz obtida.
➢ O problema de afetação pode ser visto como um caso particular de outros

problemas de otimização estudados na área da Investigação Operacional.
Por este facto, encontram-se facilmente na literatura outros algoritmos
para resolver o problema.
Slide 384
Algoritmo Húngaro
Observações
➢ Até aqui considerámos problemas de afetação em que cada indivíduo tem
que executar exatamente uma tarefa e uma tarefa tem que ser executada
por exatamente um indivíduo. Há situações em que tal não acontece e
que, contudo, podem ser convertidas na situação referida.
▪ Quando um indivíduo pode executar mais do que uma tarefa consideram-se
‘réplicas’ do indivíduo (em número igual ao das tarefas que ele pode executar),
replicando ainda os custos associados a esse indivíduo. Cada uma das réplicas
poderá então executar uma única tarefa o que nos conduz ao caso que
estudámos.
▪ Quando uma tarefa requer mais do que um indivíduo consideram-se réplicas da

tarefa (tantas quanto o número de indivíduos que a têm que executar) replicando
ainda os custos associados a tal tarefa. Cada ‘réplica’ funcionará então como uma
tarefa que ser que ser executada por um único indivíduo.
Slide 385
Programa
1. Introdução
DEPARTAMENTO DE ESTATÍSTICA E INVESTIGAÇÃO OPERACIONAL 6. Gestão de stocks
Existência criada com o objetivo de ter um bem físico

Stock imediatamente disponível de acordo com um programa de
produção ou de vendas
A criação de stocks é fundamental para qualquer empresa que lide

com bens físicos:
➢ Fábricas
➢ Revendedores
➢ Lojas
➢ ...
Slide 387
Gestão de stocks - Generalidades

Stock Existências
Matéria-prima Consome-se na produção, integrando-se nela
Matéria-subsidiária Consome-se na produção mas não se integra no produto
Elemento que intervém no produto integrando-se nele,

normalmente numa fase de pré-montagem ou
Componente montagem, mas que não sofre transformação na
empresa
Produto que se encontra no final de uma fase do

Semi-produto processo de produção
Produto em curso de fabrico Produtos que estão no decurso do processo de produção
Produto que passou por todas as fases do processo de

Produto fabricado produção
Produto que se adquire para ser vendido sem qualquer

Mercadoria transformação
Slide 388

Porquê constituir stocks?
➢ Para anular, minimizar ou diminuir drasticamente o impacto de variações

imprevisíveis
▪ da procura de produtos fabricados e de mercadorias
▪ do consumo de materiais e componentes
▪ de prazos efetivos de entrega das encomendas colocadas nos fornecedores
▪ de qualidade dos materiais recebidos dos fornecedores, que impliquem a sua
devolução ou operações de recuperação
➢ Para evitar repercutir na produção os efeitos de variações sazonais

▪ na venda de produtos e mercadorias
▪ na compra de materiais e componentes
Maior autonomia entre os programas de produção e os de vendas e de compras
Slide 389

Porquê constituir stocks?
➢ Para possibilitar
▪ a aquisição de quantidades superiores às imediatamente necessárias,
conseguindo, desta forma
• Preços mais baixos
• Melhores condições de compra
• Redução dos custos unitários de transporte
▪ a produção de séries económicas conseguindo, desta forma
• Melhor distribuição dos custos de preparação e lançamento das encomendas
Slide 390

Porquê gerir stocks?
➢ Os montantes financeiros imobilizados em existências são normalmente

elevados
➢ É geralmente elevada a percentagem do montante dos stocks no ativo de

curto prazo da empresa
➢ As áreas ocupadas pelos armazéns são normalmente elevadas, o que eleva
diversos custos associados aos meios humanos e materiais, associados
nomeadamente
▪ à receção, movimentação e arrumação das encomendas
▪ à satisfação das requisições efetuadas pela produção e pelas vendas
▪ ao controlo dos movimentos
▪ ao controlo das existências
➢ Os custos inerentes a ruturas são normalmente elevados
Slide 391
Contribuição da IO para a Gestão de Stocks
➢ Formulação de modelos matemáticos capazes de descrever o

comportamento do sistema.
➢ Determinação de uma política ótima com base nos modelos
desenvolvidos.
➢ Utilização de um sistema informatizado de processamento de informação
de forma a manter um registo permanente dos níveis dos stocks.
➢ Utilização deste sistema e das políticas ótimas encontradas a partir dos

modelos matemáticos, de forma a determinar quando e em que
quantidade se deve repor o stock.
Slide 392
Modelos matemáticos para Gestão de Stocks
Natureza da procura
Determinísticos Estocásticos
Número de unidades de um bem físico que é necessário

Procura retirar de um stock para um determinado uso (por exemplo
venda) durante um determinado período de tempo
Procura É conhecida ou pode ser prevista com grande precisão
Determinística
Não é possível prever a procura mas é possível assumir
Procura que a mesma obedece a uma determinada lei de
Estocástica probabilidade
Slide 393
Gestão de stocks – Componentes de um modelo
Exemplo
Um hipermercado pretende gerir o seu stock de um determinado tipo de bicicleta
Relativamente a esta bicicleta, a informação disponível é a seguinte:
Custo no fabricante 40 € por bicicleta

15 € por cada encomenda de bicicletas
Custo de transporte 35 € por cada encomenda de bicicletas
Valor de venda 70 € por bicicleta
O custo que o hipermercado tem com cada bicicleta depende da quantidade

que encomendar!
Slide 394
Quantidade encomendada
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Custo variável 0 40 80 120 160 200 240 280 320 360 400 440 480 520 560 600
Custo fixo 0 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
Custo de transporte 0 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35
Custo total 0 90 130 170 210 250 290 330 370 410 450 490 530 570 610 650
Custo por unidade 0,00 90,00 65,00 56,67 52,50 50,00 48,33 47,14 46,25 45,56 45,00 44,55 44,17 43,85 43,57 43,33
100,00
90,00
80,00 O custo por bicicleta diminui com

70,00 a quantidade encomendada!
Custo
60,00
50,00
40,00
30,00
20,00
10,00
0,00 Qd encomendada
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Slide 395
Poderíamos então pensar que quantas mais bicicletas forem encomendadas

de cada vez melhor...
Consideremos a seguinte informação adicional:
Presentemente há 3 bicicletas em stock
Para os próximos 30 dias está prevista uma procura de 6 bicicletas
Custo por rutura do stock 15€ por bicicleta
5 € por cada bicicleta

Custo de armazenamento
(Que esteja em stock no fim do período de 30 dias)
Slide 396
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Bicicletas em falta 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12
Custo de ruptura 45 30 15 0 0 0 0 0 0 0 0 0 0 0 0 0
50
45
40
35
O custo de rutura do stock é não crescente
30
com a quantidade encomendada
Custo
25
20
15
10
0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Slide 397
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Nº de bicletas no fim de 30 dias 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12
Custo de armazenamento 0 0 0 0 5 10 15 20 25 30 35 40 45 50 55 60
70
60
50
40
Custo
30
O custo de armazenamento é não
20 decrescente com a quantidade
encomendada
10
0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Slide 398
A política de gestão de um stock pode influenciar de forma decisiva a sua

rentabilidade
Alguns custos que influenciam a rentabilidade

➢ Custos de aquisição ou produção
➢ Custos de armazenamento
➢ Custos de rutura
Outros fatores que podem influenciar a rentabilidade

➢ Backlogging
➢ Retorno com as vendas
➢ Salvados
Slide 399
➢ Custos de aquisição ou produção
Forma simples frequentemente assumida:
K + cQ
K Componente fixa - Custo fixo por encomenda ou por lote produzido
cQ Componente proporcional à quantidade encomendada/produzida
Custo de aquisição ou
produção de uma unidade
Slide 400
➢ Custos de armazenamento
Estes custos incluem entre outras possibilidades

✓ Custos associados ao capital imobilizado
✓ Custos associados ao espaço ocupado
✓ Seguros
✓ Proteção
✓ Taxas
Aferição dos custos

Periodicamente, por exemplo:
de armazenamento
▪ Função da quantidade máxima armazenada
durante o período
▪ Função da quantidade média em stock durante
Continuamente o período
▪ Função da quantidade em stock no final do
período
Slide 401
➢ Custos de rutura
Ocorrem quando a procura excede as existências
Backlogging permitido Backlogging não permitido
A procura não se perde A procura perde-se

(Fica pendente até que o stock
seja normalmente re-abastecido)
Custos de rutura Custos de rutura

• Degradação da imagem da empresa • Custos associados a uma encomenda
• Custo por atraso na obtenção do extraordinária urgente
valor de venda • Custos pela não realização das vendas
• Custos administrativos extraordinários
Slide 402
Tempo de entrega Tempo que decorre desde que uma encomenda

Componente de um modelo é feita até que o stock é reposto
de gestão de stocks Se o tempo de entrega for sempre o mesmo, pode-se
calendarizar um re-abastecimento do stock para o
momento exato que se pretende.
Um modelos de gestão de stocks pode ser classificado de acordo com a sua

política de revisão:
Uma encomenda é feita no exato momento em que o
Revisão contínua
nível do stock alcança um determinado valor
O nível do stock é verificado em momentos discretos
no tempo. Faz-se uma encomenda quando se verificar
Revisão periódica
que o nível do stock é inferior ou igual a um
(Por exemplo semanal)
determinado valor.
Nos slides seguintes vamos estudar um modelo determinístico de revisão
contínua e um modelo determinístico de revisão periódica.
Slide 403
Gestão de stocks – Modelo Determinístico Básico

(EOQ – Economic Order Quantity)
Uma situação frequente com muitos stocks é a diminuição progressiva e ao

longo do tempo do seu nível sendo o stock reposto de uma vez com um lote
de novas unidades
Um modelo simples que representa esta situação
Modelo Determinístico Básico
Suposições
➢ A procura ocorre de forma contínua e constante ao longo do tempo
➢ O stock é re-abastecido de forma instantânea no exato instante
pretendido e na quantidade desejada
➢ Não é permitida rutura.
Slide 404

Evolução do nível do stock ao longo do tempo
Nível do
stock
1 ciclo Tempo
Slide 405

Notação
d Procura/consumo por unidade de tempo

c Custo unitário de aquisição/produção Estes parâmetros assumem-se
determinísticos, conhecidos e
K Custo fixo de encomenda
constantes
h Custo de armazenamento por unidade
do artigo e por unidade de tempo
Q Número de unidades a encomendar de cada vez A determinar!
T Duração de um ciclo ou período

Tempo entre dois re-abastecimentos consecutivos
Deverá depender de Q e de d
Slide 406

Evolução do nível do stock ao longo do tempo

Nível do
stock
Q …
Tempo
T
Slide 407

S (t ) = Q − dt Q
Nível do stock no instante t S (t )
S (T ) = Q − dT = 0
t T
Q
T=
d
Slide 408

Exemplo Consumo de um determinado artigo

(contínuo ao longo do tempo) 200 unidades por mês
Quantidade a adquirir por encomenda 600 unidades

S (t )
Nível do stock Unidade de tempo
600
…
200
2 3 6 9 Tempo (meses)
Quantidade em stock 2 meses

S (2) = 600 − 200  2 = 200 depois de uma reposição
Slide 409

?
Quantidade ótima a encomendar Q*
Objetivo Minimizar o custo global por unidade de tempo
Custo global
por período =
Custos associados
a uma encomenda + Custos de armazenamento
por período
Slide 410

Custos associados
a uma encomenda
K + cQ
Q
Custo fixo de Custo unitário de

uma encomenda aquisição/produção
Custos de armazenamento Q Q Q2
por período h  = h
d 2 2d T
Quantidade média
por unidade do artigo e
por unidade de tempo em stock por período
Duração de
um período
por unidade do artigo e por
período
Slide 411

Custos associados K + cQ

a uma encomenda
Q2
+ Custos de
armazenamento
h
2d
= Custo total por

período K + cQ + h
Q2
2d
Slide 412

Custo total por período

Custo total por unidade de tempo =
Duração de um período
 Q2  Q
=  K + c  Q + h  
 2d  d
dK hQ
= + cd +
Q 2
= f (Q )
Slide 413

Custo total por

unidade de tempo
hQ
cd +
f (Q) 2
dK
cd Q
Q* Q
Lote económico!
Slide 414

Analiticamente tem-se
f (Q) dK h
=− 2 +
Q Q 2
f (Q) dK h h dK 2dK 2dK

= 0  − 2 + = 0  = 2  Q2 = Q=
Q Q 2 2 Q h h
 2 f (Q) 2dK
Confirmação de que se trata de um minimizante = 3 0
Q Q
Síntese 2dK
Q* = Lote económico
h
Q*
T* = Comprimento de um período
d
f (Q*) = cd + 2dKh Custo ótimo por unidade de tempo
Slide 415

Exemplo
Um revendedor de pneus pretende determinar a política económica ótima de
gestão do seu stock de pneus de forma a minimizar o custo global envolvido.
A procura anual é de cerca de 5000 pneus.
O custo de efetivação de uma encomenda é de €125,00, sendo o custo

unitário de cada pneu (já com transporte incluído) de €50,00.
Estima-se que o armazenamento de um pneu tenha um custo de €20,00.
Lote económico ?
Custo ótimo anual ?
Slide 416

Tem-se d=5000 K=125 c=50 h=20

Donde,
2dK 2  5000 125
Q* = = = 250 Lote económico
h 20
250
T* = = 0.05 anos = (aprox.) 18 dias Comprimento de um ciclo
5000
f (250) = 50  5000 + 2  5000 125  20 = €255000,00 Custo ótimo anual
Resposta: De cada vez, deverão ser encomendados 250 pneus. Deve-se lançar nova
encomenda de 18 em 18 dias.
Slide 417

Arredondamentos?....
Independentemente do valor de Q, os custos variáveis de encomenda por unidade de
tempo são sempre iguais: 𝑐 × 𝑑. A menos desta constante temos:
𝑑𝐾 ℎ𝑄
𝑓 𝑄 = + 𝑓 𝑄∗ = 2𝑑𝐾ℎ
𝑄 2
𝑑𝐾 ℎ𝑄 𝑑𝐾 ℎ𝑄
𝑓(𝑄) + 1 𝑑2𝐾2 𝑄 ℎ2 1 2𝑑𝐾 𝑄 ℎ
𝑄 2 𝑄 2
= = + = + = +
𝑓 𝑄∗ 2𝑑𝐾ℎ 2𝑑𝐾ℎ 2𝑑𝐾ℎ 𝑄 2𝑑𝐾ℎ 2 2𝑑𝐾ℎ 2𝑄 ℎ 2 2𝑑𝐾
1 ∗ 𝑄 1 1 𝑄∗ 𝑄
= 𝑄 + = +
2𝑄 2 𝑄∗ 2 𝑄 𝑄 ∗
𝑄 𝟏 𝟏 𝟏 𝟏
1 2 4 10 20
𝑄∗ 𝟐𝟎 𝟏𝟎 𝟒 𝟐
𝑓(𝑄)
10.025 5.05 2.125 1.25 1 1.25 2.125 5.05 10.025
𝑓 𝑄∗
Conclusão: 𝑓(𝑄) é bastante insensível a desvios de 𝑄 relativamente a 𝑄 ∗ .
Slide 418

Suposições consideradas para o Modelo Determinístico Básico:

➢ A procura ocorre de forma contínua e constante ao longo do tempo
➢ O stock é re-abastecido de forma instantânea no exato instante
pretendido e na quantidade desejada
O tempo de entrega/reposição do stock é nulo
Vamos considerar a variante em que o tempo de entrega não é nulo
l Tempo de entrega
Tempo que decorre desde o momento em que é feita uma encomenda

até que o stock seja reposto
Slide 419

l Tempo de entrega
Tempo que decorre desde o momento em que é feita uma encomenda

até que o stock seja reposto
Momento em que deve ser lançada a

encomenda para que não haja rutura do stock T -l
S (T − l ) = Q − d  (T − l ) = Q − dT + dl
= Q − Q + dl = dl Nível do stock no momento T-l
r: Ponto de encomenda
Slide 420

Exemplo
Retomemos o exemplo do revendedor de pneus.
Suponhamos, adicionalmente, que o prazo normal de re-aprovisionamento de

uma encomenda de pneus é de 4 dias
Ponto de encomenda ?
4
r = d  l = 5000  = 54.79  55 Ponto de encomenda
365
Deve-se lançar nova encomenda quando o nível do stock atinge os 55 pneus.
Slide 421

Descontos de quantidade
Frequentemente, o custo unitário de aquisição/produção, depende da
quantidade encomendada/produzida.
QUANTIDADE A ENCOMENDAR PREÇO UNITÁRIO
1  Q  q1 c1
q1  Q  q2 c2 c1  c2  ...  cn
… …
qn −1  Q cn
Incentivam-se encomendas/lotes de produção de maiores dimensão
Slide 422

dK hQ
f i (Q) = + ci d +
Q 2
Custo total por
unidade de tempo f1 (Q)
f 2 (Q )
f n (Q )
Slide 423

Custo total por

unidade de tempo f1 (Q)
f 2 (Q )
f n (Q )
q1 q2 qn −1 Q
Slide 424

Custo total por

unidade de tempo
f1 (Q)
f 2 (Q ) f n (Q )
q1 q2 qn −1 Q
Slide 425

Determinação da quantidade ótima a encomendar
2dK
Q* =
h
Solução ótima ou
Um dos qj maiores ou iguais a Q*
Slide 426

Metodologia para determinar a quantidade ótima a encomendar
2dK
1. Determinar Q* = e f (Q*) Utiliza-se o custo unitário
h apropriado para a quantidade Q*
2. Seja q s = min q j : q j  Q *
3. i=s
Enquanto i  n −1
Se f ( qi )  f (Q*) fazer Q* = qi
i = i +1
Slide 427

Exemplo
Retomemos o exemplo do revendedor de pneus.
Suponhamos, agora, que o custo unitário de cada pneu depende da

quantidade encomendada da seguinte forma:
QUANTIDADE A ENCOMENDAR PREÇO UNITÁRIO
1  Q  200 55
q1 = 200
200  Q  275 50
q2 = 275
275  Q  300 48
q3 = 300
300  Q 46
Slide 428

2dK 2  5000 125

Q* = = = 250
h 20
125  5000 20  250
f (250) = + 50  5000 + = €255000,00
250 2
Primeiro qj≥Q* q2 = 275

125  5000 20  275
f (q2 ) = f (275) = + 48  5000 + = €245023,00
275 2
125  5000 20  300
f (q3 ) = f (300) = + 46  5000 + = €235083,00
300 2
donde
300
Q * = 300 T* = = 0.06 anos = (aprox.) 22 dias Comprimento de um ciclo
5000
Slide 429
Gestão de stocks – Um modelo de revisão periódica
O stock é re-abastecido periodicamente em

Modelo de revisão periódica
momentos pré-determinados no tempo
Objetivo
Determinar o nível de reabastecimento do stock no início de cada
período de forma a minimizar o custo global para o horizonte
temporal considerado
Slide 430
Suponhamos que temos que fazer um planeamento para n períodos.
Notação
c Custo unitário de aquisição/produção
K Custo fixo de encomenda Estes parâmetros assumem-se

determinísticos, conhecidos e
h Custo de armazenamento por unidade constantes
do artigo e por período
di Procura/consumo no período i
i = 1,..., n
Slide 431
Suposições
➢ Não há nenhuma unidade em stock no início
➢ No momento em que é feito o planeamento ainda há tempo para fazer

uma encomenda que chegue no início do primeiro período
➢ Toda a procura tem que ser satisfeita em todos os períodos (ou seja,
não é permitida rutura do stock
Slide 432
A chave para se encontrar um algoritmo eficiente que nos permita determinar

a política ótima de gestão do stock assenta na seguinte constatação acerca
da solução ótima do problema
Numa política ótima o stock é re-abastecido apenas quando

o seu nível atinge o valor zero
Não há vantagem em fazer encomendas que satisfaçam

parcialmente a procura de algum período posterior
Slide 433
Exemplo (Retomemos o exemplo das bicicletas já apresentado antes)

Um hipermercado pretende gerir o seu stock de um determinado tipo de
bicicleta. Relativamente a esta bicicleta, a previsão de vendas para os
próximos 3 meses é a seguinte:
Mês 1 2 3
Nº de bicicletas 6 7 4
Presentemente não existe nenhuma bicicleta em stock.

Os custos relevantes são os seguintes:
Custo no fabricante 40 € por bicicleta
15 € por encomenda de bicicletas
Custo de armazenamento 5 € por cada bicicleta

(que seja armazenada de uma mês para o seguinte)
Slide 434

Consideremos a seguinte política de re-abastecimento do stock de bicicletas:
Início do mês 1 O stock é re-abastecido com 10 bicicletas

Repare-se que no início do período 1 chegam bicicletas que satisfazem apenas

parcialmente (4 bicicletas) a procura do período 2.
No início do período 2 será necessário re-abastecer com o que falta para este período.
Então, se as 4 bicicletas que chegam no período 1 e que se destinam ao período 2
vierem apenas no início do período 2, os custos de armazenamento descem sem que se
suba qualquer outro custo. Assim, a seguinte política é preferível:

Slide 435
Política ótima no caso geral
Re-abastecimento do stock no (início do) período i  1,..., n
0 Não há re-abastecimento
di É feito o re-abastecimento para o período i
d i + d i +1 É feito o re-abastecimento para os períodos i e i+1

di +  + dn É feito o re-abastecimento para os períodos i, i+1,...,n
Slide 436
O problema pode ser formulado como um problema de caminho mais curto

entre dois vértices de um grafo
G = ( X , A)
Início do período i
X = 1,..., i ,...n + 1 i
Fim do período i −1
A = (i , j ) : 1  i  j  n + 1 i j
Re-abastecimento do stock no início do

período i com a quantidade necessária
para os meses i , i + 1,..., j − 1
Slide 437
i j
Re-abastecimento do stock no início do

período i com a quantidade necessária
para os meses i , i + 1,..., j − 1
➢ A encomenda terá dimensão d i + d i +1 + ... + d j −1

➢ O stock no final do mês k (i≤k≤j-1) d k +1 + d k + 2 + ... + d j −1
➢ O custo da encomenda é K + c  (d i + d i +1 + ... + d j −1 )

j −2
➢ O custo de armazenamento é  h  (d
k =i
k +1 + d k + 2 + ... + d j −1 )
Slide 438

j −2
Cij = K + c  (d i + d i +1 + ... + d j −1 ) +  h  (d k +1 + d k + 2 + ... + d j −1 )
k =i
i j
l ( n + 1) Custo da política ótima

l (1) = 0
l ( j ) = min l (i ) + C ij , i = 1,..., j − 1 j = 2 ,..., n + 1
Custo da política ótima para os períodos 1,..., j − 1

Observação Se o stock inicial não for 0, tudo se mantém. Apenas é
necessário subtrair o stock inicial à procura no primeiro
período
Slide 439

Um hipermercado pretende gerir o seu stock de um determinado tipo de
bicicleta. Relativamente a esta bicicleta, a previsão de vendas para os
próximos 3 meses é a seguinte:
Mês 1 2 3
Nº de bicicletas 6 7 4
Existe um stock inicial de 3 bicicletas d1 = 6 − 3 = 3 d 2 = 7 d3 = 4
Os custos relevantes são os seguintes:

Custo no fabricante 40 € por bicicleta c = 40
15 € por encomenda de bicicletas
K = 50
Custo de armazenamento 5 € por cada bicicleta h=5

(que seja armazenada de uma mês para o seguinte)
Slide 440

Vértices
1 – início do 1º mês
2 – fim do 1º mês / início do 2º mês
3 – fim do 2º mês / início do 3º mês
4 – fim do 3º mês
Arcos
(1,2) – encomenda no início do 1º mês para satisfazer a procura no mês 1.
(1,3) – encomenda no início do 1º mês para satisfazer a procura nos meses 1 e 2.
(1,4) – encomenda no início do 1º mês para satisfazer a procura nos meses 1, 2 e 3.
(2,4) – encomenda no início do 2º mês para satisfazer a procura nos meses 2 e 3.
Slide 441

Exemplo (Continuação) Um caminho entre os vértices
1 e 4 neste grafo corresponde
a uma política de gestão do
stock para os 3 meses.
1 2 3 4
1→2 →3 →4 Encomendar no início de cada mês a quantidade necessária para

satisfazer a procura nesse mês.
1→4 Encomendar a quantidade total no início do mês 1.
1→3 →4 Encomendar no início do mês 1 para satisfazer a procura nos meses 1 e 2;
encomendar no início do mês 3 para satisfazer a procura no mês 3.
1→2 →4 Encomendar no início do mês 1 para satisfazer a procura no mês 1;

encomendar no início do mês 2 para satisfazer a procura nos meses 2 e 3.
Slide 442

Exemplo (Continuação) c = 40
K = 50
Valores dos arcos h=5
1 2 3 4
d1 = 3 d2 = 7 d3 = 4
(1,2) 50 + 40  3 + 5  0 = 170
(1,3) 50 + 40  (3 + 7 ) + 5  7 + 5  0 = 485
(1,4) 50 + 40  (3 + 7 + 6) + 5 11 + 5  4 + 5  0 = 685
(2,3) 50 + 40  (7 ) + 5  0 = 330
(2,4) 50 + 40  (7 + 4) + 5  4 + 5  0 = 510
(3,4) 50 + 40  (4) + 5  0 = 210
Slide 443

485 510
170 210
1 2 330 3 4
685
l (1) = 0
l ( 2) = l (1) + C12 = 170
l (3) = min l (1) + C13 , l ( 2 ) + C 23  = 485
l ( 4 ) = min l (1) + C14 , l ( 2 ) + C 24 , l (3) + C 34  = 680
Slide 444

485 510
0 170 485 680

170 210
1 2 330 3 4
685
l (1) = 0
l ( 2) = l (1) + C12 = 170
l (3) = min l (1) + C13 , l ( 2 ) + C 23  = 485
l ( 4 ) = min l (1) + C14 , l ( 2 ) + C 24 , l (3) + C 34  = 680
Slide 445

485 510
0 170 485 680

170 210
1 2 330 3 4
685
Política ótima de gestão deste stock

Re-abastecer o stock logo de início com 3 unidades (o necessário para o mês 1)
Re-abastecer o stock no início do mês 2 com 11 unidades (o necessário para os
meses 2 e 3)
Custo ótimo: 680 €
Slide 446
Técnicas de Investigação Operacional
Ano letivo 2020/2021
Francisco Saldanha da Gama

(Gabinete: 4.6.37A | E-mail: fsgama@ciencias.ulisboa.pt)

Slides

Enviado por

Direitos autorais:

Formatos disponíveis

Slides

Enviado por

Dados do documento

Descrição original:

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Slides

Enviado por

Direitos autorais:

Formatos disponíveis

Investigação Operacional

Técnicas de Investigação Operacional

Ano letivo 2020/2021

Francisco Saldanha da Gama

H. A. Taha, “Operations Research: An Introduction”, Prentice Hall,

W. L. Winston, “Operations Research: Applications and Algorithms”,

➢ 2ª Guerra Mundial (Operações militares)

▪ Controle de fogo antiaéreo

➢ Anos 1950 a 1970 (Operações de caráter económico)

▪ Planeamento da produção industrial

➢ Anos 1980 e 1990 (Novos tipos de aplicações)

▪ Aplicações financeiras (‘real options’)

Matemática Investigação Gestão

IO consiste na representação de sistemas reais através da utilização de

Operational Research Society (UK)

“A IO consiste na aplicação do método científico a problemas complexos que

APDIO – Associação Portuguesa de Investigação Operacional

“Trata-se de uma ciência aplicada voltada para a resolução de problemas

Alguns sites sobre IO

The Association of European Operational Research Societies

Institute for the Operations Research and Management Sciences

The Operational Research Society

Diversos links na área de IO

Alguns sites sobre IO

Decision Support Puzzles for Applied Mathematicians

As distâncias entre os diferentes pontos são as seguintes:

Pretende-se determinar a ordem pela qual se devem visitar os clientes de

Um processo para obter ✓ Partindo do Lumiar vai-se para o ponto mais

Distâncias (km) Lumiar P. Nações Benfica Algés Docas

Distância total percorrida: 37 km.

A solução anterior constitui uma solução admissível para o problema

Gerar todas as soluções admissíveis, calcular os respetivos custos e

Se o problema tiver n pontos

𝑛−1 ! Se a matriz de distâncias for simétrica

Lumiar Lumiar Lumiar

EXPO EXPO EXPO

Lumiar Lumiar Lumiar

EXPO EXPO EXPO

Lumiar Lumiar Lumiar

EXPO EXPO EXPO

Lumiar Lumiar Lumiar

EXPO EXPO EXPO

Neste exemplo pequeno podemos gerar todas as rotas admissíveis:

Rota 1: cliente 1 com uma carga de 22 unidades, custo 20 u.m.

Custo: 88 u.m. Custo: 84 u.m. Custo: 81 u.m.

A constituição dos diversos talhões tem a ver com múltiplos fatores:

Problemas que surgem na gestão de uma floresta

▪ Corte de madeira com fins lucrativos mas tendo em conta:

Um problemas de corte de talhões numa floresta e

Um problemas de corte de talhões numa floresta Talhão Lucro (u.m.)

Um problemas de corte de talhões numa floresta

Cortar os talhões a lucro 20 u.m.

Cortar os talhões a lucro 20 u.m.

➢ A empresa tem como opções unicamente dois modelos de viatura: A e B.

➢ Os custos de aquisição e operação / manutenção são diferentes.

Trocar por novo modelo A

Trocar por novo modelo A

900 450 -350