O que sai nos Exames de Investigação Operacional

Por frequência

O que aparece nos exames

Quase sempre em licenciatura

Método gráfico

Traçar restrições, identificar região de solução e encontrar o ponto óptimo graficamente.

Formulação de PL

Ler enunciado empresarial, escrever a função objectivo e as restrições correctamente.

Método Simplex

Construir tabelas, iterar, identificar a solução óptima e interpretar os resultados.

Problema dual

Converter primal em dual, identificar as variáveis duais e as respectivas condições.

Frequente em licenciatura

Problemas de rede

Caminho mais curto — algoritmo de Dijkstra passo a passo.

Caixeiro viajante

Circuito de menor distância — método do vizinho mais próximo (heurística).

Gestão de projectos (PERT-CPM)

Caminho crítico, duração mínima do projecto e folgas de cada actividade.

Ocasional em mestrado

Cortes de Gomory

Programação linear inteira — adicionar cortes e resolver até solução inteira.

Programação dinâmica

Decomposição em etapas e princípio da optimalidade.

Simulação

Simular sistemas com distribuições de probabilidade e interpretar resultados.

Heurística

Algoritmos genéticos e simulated annealing — descrever ou aplicar.

Método Electra

Análise multicritério — matrizes de concordância e discordância.

Exercícios

Exercícios originais resolvidos

Exercícios originais com resolução completa passo a passo. Clica em "Ver resolução" para expandir.

Ex. 1

Método Gráfico

Quase sempre

Uma empresa produz dois tipos de mobiliário: cadeiras (x₁) e mesas (x₂). Cada cadeira requer 2 h de carpintaria e 1 h de acabamento; cada mesa requer 3 h de carpintaria e 2 h de acabamento. A empresa dispõe de 12 h semanais de carpintaria e 8 h de acabamento. O lucro por cadeira é 50 € e por mesa 80 €. Resolva pelo método gráfico.

Ver resolução completa

Formulação

Max Z = 50x₁ + 80x₂

s.a.  2x₁ + 3x₂ ≤ 12   (carpintaria)
       x₁ + 2x₂ ≤  8   (acabamento)
      x₁, x₂ ≥ 0

1.º Pontos para traçar as restrições

2x₁ + 3x₂ = 12 → A(0 ; 4) e B(6 ; 0)
x₁ + 2x₂ = 8 → C(0 ; 4) e D(8 ; 0)

2.º Vértices da região admissível e valor de Z

Ponto	x₁	x₂	Z = 50x₁ + 80x₂
O	0	0	0
B	6	0	300
E	0	4	320 ← máximo

O ponto E(0 ; 4) resulta da intersecção das duas restrições: resolvendo 2x₁+3x₂=12 e x₁+2x₂=8 obtém-se x₂=4, x₁=0.

Solução óptima

X* = (0 ; 4) e Z* = 320 € — Produzir 0 cadeiras e 4 mesas por semana.

Ex. 2

Formulação de PL

Quase sempre

Uma fábrica de calçado produz três modelos: sapato clássico (x₁), bota (x₂) e sandália (x₃). Disponibilidade: 16 h de corte, 18 h de costura, 12 h de acabamento. Horas por unidade — sapato: 2/3/1; bota: 4/2/3; sandália: 1/2/2. Lucros: 120 €, 200 €, 80 €. Procura máxima de botas: 3 unidades. Produção de sandálias não pode exceder a de sapatos clássicos. Formule matematicamente o problema.

Ver resolução completa

Dados em tabela

	Corte (h)	Costura (h)	Acabamento (h)	Lucro (€)
Sapato (x₁)	2	3	1	120
Bota (x₂)	4	2	3	200
Sandália (x₃)	1	2	2	80
Disponível	16	18	12

Formulação completa

Max Z = 120x₁ + 200x₂ + 80x₃

s.a.  2x₁ + 4x₂ +  x₃ ≤ 16   (corte)
      3x₁ + 2x₂ + 2x₃ ≤ 18   (costura)
       x₁ + 3x₂ + 2x₃ ≤ 12   (acabamento)
                    x₂ ≤  3   (procura máx. de botas)
               x₃ − x₁ ≤  0   (sandálias ≤ sapatos)
      x₁, x₂, x₃ ≥ 0

A restrição x₃ ≤ x₁ é reescrita como x₃ − x₁ ≤ 0 para manter a forma standard.

5 restrições + não negatividade

Função objectivo: Max Z = 120x₁ + 200x₂ + 80x₃. A restrição de proporção x₃ ≤ x₁ é equivalente a x₃ − x₁ ≤ 0.

Ex. 3

Método Simplex

Quase sempre

Uma empresa produz dois produtos A (x₁) e B (x₂). A requer 1 h de máquina e 2 h de mão-de-obra; B requer 2 h de máquina e 1 h de mão-de-obra. Disponível: 6 h de máquina e 8 h de mão-de-obra. Lucro: A = 5 €/unid., B = 4 €/unid. Resolva pelo método Simplex.

Ver resolução completa

Forma padrão (adicionar variáveis de folga x₃, x₄)

Max Z = 5x₁ + 4x₂ + 0x₃ + 0x₄

s.a.   x₁ + 2x₂ + x₃      = 6
      2x₁ +  x₂      + x₄ = 8
      xᵢ ≥ 0

Quadro 1 — base inicial {x₃=6, x₄=8}

Cᴮ	Base	x₁ (5)	x₂ (4)	x₃ (0)	x₄ (0)	b	θ = b/col.
0	x₃	1	2	1	0	6	6/1 = 6
0	x₄	2 ←	1	0	1	8	4 ↑ (mín)
	Cⱼ−Zⱼ	5 ↑	4	0	0	Z = 0

Entrante: x₁ (maior Cⱼ−Zⱼ = 5). Sainte: x₄ (menor θ = 4). Pivot: 2.

Quadro 2 — base {x₃, x₁}

Cᴮ	Base	x₁ (5)	x₂ (4)	x₃ (0)	x₄ (0)	b	θ
0	x₃	0	1,5 ←	1	−0,5	2	1,33 ↑ (mín)
5	x₁	1	0,5	0	0,5	4	8
	Cⱼ−Zⱼ	0	1,5 ↑	0	−2,5	Z = 20

Entrante: x₂ (Cⱼ−Zⱼ = 1,5). Sainte: x₃ (θ = 1,33). Pivot: 1,5.

Quadro 3 — solução óptima

Cᴮ	Base	x₁ (5)	x₂ (4)	x₃ (0)	x₄ (0)	b
4	x₂	0	1	0,67	−0,33	1,33
5	x₁	1	0	−0,33	0,67	3,33
	Cⱼ−Zⱼ	0	0	−1,33	−1,33	Z = 23,33

Todos os Cⱼ−Zⱼ ≤ 0 → solução óptima encontrada. Todas as restrições estão activas — sem folga em máquina nem em mão-de-obra.

Solução óptima

X* = (3,33 ; 1,33) e Z* = 23,33 € — Produzir 3,33 unidades de A e 1,33 de B por semana.

Ex. 4

Problema Dual

Quase sempre

Considera o problema primal: Min Z = 6x₁ + 4x₂ + 8x₃, sujeito a: 3x₁ + x₂ + 2x₃ ≥ 9; x₁ + 2x₂ + x₃ ≥ 6; x₁, x₂, x₃ ≥ 0. Encontre o problema dual.

Ver resolução completa

Regras de conversão Primal → Dual

Primal (Min)	Dual (Max)
Função Min	Função Max
Coeficientes objectivo (6, 4, 8)	Termos independentes do dual
Termos independentes (9, 6)	Coeficientes objectivo do dual
Restrição ≥	Variável dual ≥ 0
2 restrições	2 variáveis duais (y₁, y₂)
3 variáveis	3 restrições duais

Problema dual resultante

Max W = 9y₁ + 6y₂

s.a.  3y₁ +  y₂ ≤ 6   (coluna x₁ do primal)
       y₁ + 2y₂ ≤ 4   (coluna x₂ do primal)
      2y₁ +  y₂ ≤ 8   (coluna x₃ do primal)
      y₁, y₂ ≥ 0

Verificação da simetria

Primal	Dual
Min Z = 6x₁ + 4x₂ + 8x₃	Max W = 9y₁ + 6y₂
2 restrições	2 variáveis duais
3 variáveis	3 restrições
Restrições ≥ → variáveis ≥ 0	Restrições ≤

Pelo teorema da dualidade forte, no óptimo: Z* = W*.

Dual: Max W = 9y₁ + 6y₂

Sujeito a: 3y₁+y₂≤6, y₁+2y₂≤4, 2y₁+y₂≤8, y₁,y₂≥0. No óptimo Z*=W*.

Ex. 5

Caminho Mais Curto — Dijkstra

Frequente

Uma empresa envia mercadoria do nó 1 (armazém) ao nó 6 (cliente). Distâncias em km: 1→2: 4, 1→3: 7, 2→3: 2, 2→4: 5, 3→4: 3, 3→5: 6, 4→6: 4, 5→6: 3. Determine o caminho mais curto pelo algoritmo de Dijkstra.

Ver resolução completa

Iteração 1 — partir do nó 1 (d=0)

Nó	d acumulada	Nó anterior	Estado
1	0	—	✓ visitado
2	4	1
3	7	1
4	∞	—
5	∞	—
6	∞	—

Próximo: nó 2 (d = 4, mínimo).

Iteração 2 — a partir do nó 2

Nó 3: min(7, 4+2) = 6 — actualiza, nó anterior = 2
Nó 4: min(∞, 4+5) = 9, nó anterior = 2

Nó	d acumulada	Nó anterior	Estado
2	4	1	✓ visitado
3	6	2
4	9	2
5	∞	—
6	∞	—

Próximo: nó 3 (d = 6).

Iteração 3 — a partir do nó 3

Nó 4: min(9, 6+3) = 9 — empate, actualiza nó anterior para 3
Nó 5: min(∞, 6+6) = 12, nó anterior = 3

Nó	d acumulada	Nó anterior	Estado
3	6	2	✓ visitado
4	9	3
5	12	3
6	∞	—

Próximo: nó 4 (d = 9).

Iteração 4 — a partir do nó 4

Nó 6: min(∞, 9+4) = 13, nó anterior = 4

Próximo: nó 5 (d = 12).

Iteração 5 — a partir do nó 5

Nó 6: min(13, 12+3=15) = 13 — sem actualização (15 > 13)

Nó 6 visitado — algoritmo termina. Reconstituição do caminho: 6 ← 4 ← 3 ← 2 ← 1.

Caminho: 1 → 2 → 3 → 4 → 6 · Distância: 13 km

O caminho mais curto entre o armazém e o cliente percorre 13 km, passando pelos nós 2, 3 e 4.

Ex. 6

Caixeiro Viajante — Vizinho Mais Próximo

Frequente

Um representante parte de A e visita as cidades B, C, D e E, regressando a A. Distâncias (km): A-B 8, A-C 12, A-D 5, A-E 10, B-C 6, B-D 9, B-E 7, C-D 4, C-E 11, D-E 6. Determine o circuito de menor distância usando o método do vizinho mais próximo.

Ver resolução completa

Matriz de distâncias

	A	B	C	D	E
A	—	8	12	5	10
B	8	—	6	9	7
C	12	6	—	4	11
D	5	9	4	—	6
E	10	7	11	6	—

Aplicação da heurística

Passo	Em	Escolha	Distância	Acumulado
1	A	→ D (5 km, mínimo de A)	5	5
2	D	→ C (4 km, mínimo de D)	4	9
3	C	→ B (6 km, mínimo de C)	6	15
4	B	→ E (7 km, único restante)	7	22
5	E	→ A (regresso)	10	32

Nota: neste caso a heurística encontra o circuito óptimo (mínimo absoluto por enumeração = 32 km). Em geral, o método do vizinho mais próximo não garante a solução óptima global — fornece uma boa solução de forma rápida.

Circuito: A → D → C → B → E → A · Distância: 32 km

Solução heurística (vizinho mais próximo). Circuito alternativo A→D→E→B→C→A = 36 km — pior.

Ex. 7

PERT-CPM — Caminho Crítico

Frequente

Uma empresa planeia a construção de um armazém com 8 actividades. Durações (semanas) e precedências: A(3,—), B(4,A), C(6,B), D(3,C), E(4,C), F(3,C), G(5,D+E+F), H(2,G). Determine: a) o caminho crítico; b) a duração mínima do projecto; c) as folgas de cada actividade.

Ver resolução completa

1.º Forward pass — datas mais cedo (ES / EF)

Actividade	ES	Duração	EF = ES + Dur.
A	0	3	3
B	3	4	7
C	7	6	13
D	13	3	16
E	13	4	17
F	13	3	16
G	max(16,17,16) = 17	5	22
H	22	2	24

Duração mínima do projecto: 24 semanas.

2.º Backward pass — datas mais tarde (LS / LF)

Actividade	LF	Duração	LS = LF − Dur.
H	24	2	22
G	22	5	17
D	17	3	14
E	17	4	13
F	17	3	14
C	min(14,13,14) = 13	6	7
B	7	4	3
A	3	3	0

3.º Folgas (Folga = LS − ES)

Actividade	ES	LS	Folga	Crítica?
A	0	0	0	✓
B	3	3	0	✓
C	7	7	0	✓
D	13	14	1
E	13	13	0	✓
F	13	14	1
G	17	17	0	✓
H	22	22	0	✓

D e F têm folga de 1 semana — podem atrasar até 1 semana sem prejudicar o projecto.

Caminho crítico: A → B → C → E → G → H · Duração: 24 semanas

D e F têm folga de 1 semana. Todas as restantes actividades têm folga zero.

Estrutura típica

Como está estruturado um teste típico

Pergunta	Tópico	Valor típico
1	Método gráfico	5,0 valores
2	Formulação de PL	3,0 valores
3	Método Simplex com tabelas	5,0 valores
4	Problema dual ou redes	4,0 valores
—	Interpretação da solução	3,0 valores

Em mestrado surgem adicionalmente Programação Dinâmica, Heurística e Método Electra.

Universidades apoiadas

Onde já foram dados apoios

IST – Técnico de Lisboa Universidade do Minho Universidade de Aveiro ISCTE ISEG Católica ISUTE — Moçambique Outras instituições

Apoio presencial em Lisboa e Porto. Explicações online para todo o país e internacionalmente.

Queres preparar o exame com apoio personalizado?

30€/hora · Online e presencial · Resposta em menos de 24h

Marcar explicação

Actividade	ES	LS	Folga	Crítica?
A	0	0	0	✓
B	3	3	0	✓
C	7	7	0	✓
D	13	14	1
E	13	13	0	✓
F	13	14	1
G	17	17	0	✓
H	22	22	0	✓

Actividade	ES	LS	Folga	Crítica?
A	0	0	0	✓
B	3	3	0	✓
C	7	7	0	✓
D	13	14	1
E	13	13	0	✓
F	13	14	1
G	17	17	0	✓
H	22	22	0	✓

O que sai nos exames de Investigação Operacional

O que aparece nos exames

Método gráfico

Formulação de PL

Método Simplex

Problema dual

Problemas de rede

Caixeiro viajante

Gestão de projectos (PERT-CPM)

Cortes de Gomory

Programação dinâmica

Simulação

Heurística

Método Electra

Exercícios originais resolvidos

Método Gráfico

Formulação

1.º Pontos para traçar as restrições

2.º Vértices da região admissível e valor de Z

Formulação de PL

Dados em tabela

Formulação completa

Método Simplex

Forma padrão (adicionar variáveis de folga x₃, x₄)

Quadro 1 — base inicial {x₃=6, x₄=8}

Quadro 2 — base {x₃, x₁}

Quadro 3 — solução óptima

Problema Dual

Regras de conversão Primal → Dual

Problema dual resultante

Verificação da simetria

Caminho Mais Curto — Dijkstra

Iteração 1 — partir do nó 1 (d=0)

Iteração 2 — a partir do nó 2

Iteração 3 — a partir do nó 3

Iteração 4 — a partir do nó 4

Iteração 5 — a partir do nó 5

Caixeiro Viajante — Vizinho Mais Próximo

Matriz de distâncias

Aplicação da heurística

PERT-CPM — Caminho Crítico

1.º Forward pass — datas mais cedo (ES / EF)

2.º Backward pass — datas mais tarde (LS / LF)

3.º Folgas (Folga = LS − ES)

Como está estruturado um teste típico

Onde já foram dados apoios

Queres preparar o exame com apoio personalizado?

Actividade	ES	LS	Folga	Crítica?
A	0	0	0	✓
B	3	3	0	✓
C	7	7	0	✓
D	13	14	1
E	13	13	0	✓
F	13	14	1
G	17	17	0	✓
H	22	22	0	✓