Aulas Práticas IO_2018_2019

Prévia do material em texto

2018/2019 
 
 
Investigação 
Operacional 
Documento de apoio das 
aulas Teórico-Práticas 
Cecília Silva;Emília Malcata 
SPTA - FEUP 
 
INVESTIGAÇÃO OPERACIONAL 
 
 
 3º Ano 
(1º semestre) 
 
Departamento de 
Engenharia Civil 
DEC 
 
Secção de Planeamento 
do Território e Ambiente 
 
Index 
Index .................................................................................................................................. 1 
Prefácio .............................................................................................................................. 3 
Funcionamento da Disciplina ...................................................................................................... 4 
Regras de Avaliação e Calendário das Aulas .................................................................................. 4 
Objetivos da disciplina .......................................................................................................... 6 
Bibliografia ........................................................................................................................ 6 
Investigação Operacional .......................................................................................................... 7 
1 Introdução à Programação Linear ........................................................................................... 8 
1.1 Formulação de Problemas de Programação Linear ................................................................... 8 
1.2 Propriedades da Programação Linear .................................................................................. 10 
1.3 Exercício Exemplo – Formulação e Resolução Gráfica ............................................................... 11 
Exercícios de Resolução Gráfica ............................................................................................... 14 
Exercícios de Formulação ...................................................................................................... 14 
2 Método de Simplex – Resolução de problemas de Programação Linear ............................................... 18 
2.1 Conceitos .................................................................................................................. 18 
2.2 Metodologia do algoritmo Simplex ..................................................................................... 19 
2.3 Resolução Gráfica, Algébrica e pelo Método de Simplex ........................................................... 19 
2.4 Casos Particulares ........................................................................................................ 25 
2.5 Problemas não standard ................................................................................................. 29 
Exercícios de Método de Simplex ............................................................................................. 33 
Exercícios de Exame – Parte I .................................................................................................... 35 
3 Teorema da Dualidade ....................................................................................................... 38 
Exercícios de Dualidade ........................................................................................................ 41 
4 Problema de Transportes .................................................................................................... 43 
4.1 Formulação em problema de programação linear ................................................................... 44 
4.2 Formulação em Problema de Transportes (Tabular) ................................................................ 45 
4.3 Resolução do Problema de Transportes ............................................................................... 45 
4.4 Problema de Afetação ................................................................................................... 51 
4.5 Problemas convertíveis em Problemas de Transportes / Afetação ................................................ 52 
4.6 Exercícios de Resolução do Problema de Transportes .............................................................. 54 
4.7 Exercícios de Resolução de Problemas de Afetação ................................................................. 55 
4.8 Exercícios de Formulação de Problemas de Transportes ........................................................... 57 
IO - Aulas TP 
Página | 2 
 
5 Problema de Redes ........................................................................................................... 60 
5.1 Árvore de Ligações Mínimas ............................................................................................. 61 
5.2 Caminho Mais Curto ...................................................................................................... 63 
5.3 Fluxo máximo ............................................................................................................. 64 
5.4 CPM ......................................................................................................................... 66 
5.5 PERT ........................................................................................................................ 69 
5.6 Exercícios de Redes ...................................................................................................... 72 
Exercícios de Exame – Parte II .................................................................................................... 77 
Soluções dos Exercícios............................................................................................................ 84 
 
 
 
 
IO - Aulas TP 
Página | 3 
 
Prefácio 
 
Este documento serve de apoio às aulas teórico-práticas da disciplina de Investigação Operacional do curso de 
Mestrado Integrado de Engenharia Civil da Faculdade de Engenharia da Universidade do Porto. Não deve ser encarado 
como um manual extensivo de todos os conteúdos abordados na disciplina, sendo apenas um complemento da 
bibliografia de apoio da disciplina. Este documento sumariza alguns dos principais conteúdos abordados nas aulas 
teórico-práticas da disciplina, servindo de apoio a essas mesmas aulas como elemento de estudo não acompanhado 
de preparação e revisão. Adicionalmente, o manual inclui os enunciados dos exercícios de aplicação propostos para 
as aulas e para estudo individual. 
 
 
 
 
INVESTIGAÇÃO OPERACIONAL 
 
 
 3º Ano 
(1º semestre) 
 
Departamento de 
Engenharia Civil 
DEC 
 
Secção de Planeamento 
do Território e Ambiente 
 
Funcionamento da Disciplina 
 
Regras de Avaliação e Calendário das Aulas 
As indicadas nas Normas Gerais de Avaliação [NGA] da FEUP. 
a) Modo de avaliação. 
− IO insere-se no formato de uma disciplina de avaliação distribuída com exame final 
 b) Componentes da avaliação 
− Realização de um exame final 
− Elaboração de Trabalho Semestral 
- Apresentação do enunciado do Trabalho até dia 8 de Novembro 
- O trabalho será desenvolvido em grupos de 3 cuja constituição será revelada até dia 8 de Novembro 
- Entrega do Relatório e da Apresentação do Trabalho (8 deDezembro) 
▪ A entrega será obrigatoriamente feita pelo Moodle 
▪ Só será permitida a submissão de dois documentos: o relatório em PDF e a apresentação 
no formato desejado 
▪ Os documentos submetidos tem de ter como nome a identificação do grupo no formato: 
“T?G??.pdf” e “T?G??.pptx” em que ‘?’ identifica o numero de turma e ‘??’ o número do 
grupo. 
- Defesa Oral do Trabalho (17 a 20 de Dezembro, as apresentações serão realizadas na respetiva turma 
das aulas teórico-práticas à exceção da Turma 6 que apresentará na aula teórica de quarta-feira da 
mesma semana). É obrigatória a presença de todos os elementos do grupo na apresentação. 
− Aulas virtuais e questionários 
- A Unidade Curricular conta com 3 aulas virtuais que deverão ser visualizadas antes da aula teórico-
prática respetiva. Cada aula virtual éacompanhada de um questionário que deve ser preenchido antes 
do início da aula teórico-prática da turma a que está inscrito. 
▪ Calendário das aulas virtuais 
• Aula 3: Programação Linear: Método de Simplex. Resolução Matricial. 
• Aula 4: Programação Linear: Método de Simplex de duas fases. 
• Aula 7: Problema de Transportes: Resolução do Problema de Transportes. 
- As aulas virtuais estarão disponíveis no moodle desde a semana anterior à aula, bem como o 
questionário que o acompanha. 
c) Condições para obtenção de frequência. 
− Não faltar a mais do que 25% das aulas teóricas e das aulas teórico-práticas. 
d) Fórmula de cálculo da classificação final. 
- Aulas virtuais e questionários 1 valores (esta classificação é válida para o ano letivo seguinte ao da elaboração) 
- Trabalho Semestral 5 valores (esta classificação é válida para o ano letivo seguinte ao da elaboração) 
- Exame Final 14 valores (classificação mínima para aprovação de 6 valores) 
− Alunos que não estão abrangidos pelas regras da frequência obrigatória (TE, TI, DA, ...): 
- Realização de exame cobrindo a totalidade da matéria lecionada nas aulas teóricas e teórico-práticas. 
IO - Aulas TP 
Página | 5 
 
 A
u
la
S
e
g
u
n
d
a
T
e
rç
a
Q
u
a
rt
a
Q
u
in
ta
S
e
x
ta
S
u
m
á
ri
o
1
1
7
/
se
t
1
8
/
se
t
1
9
/
se
t
2
0
/
se
t
2
1
/
se
t
In
tr
o
d
u
ç
ã
o
 a
o
 P
ro
b
le
m
a
 d
e
 I
O
; 
P
ro
g
ra
m
a
ç
ã
o
 L
in
e
a
r;
 F
o
rm
u
la
ç
ã
o
; 
P
ro
p
ri
e
d
a
d
e
s;
 D
o
m
ín
io
; 
R
e
so
lu
ç
ã
o
 G
rá
fi
c
a
.
E
x
e
rc
íc
io
s
2
2
4
/
se
t
2
5
/
se
t
2
6
/
se
t
2
7
/
se
t
2
8
/
se
t
P
ro
g
ra
m
a
ç
ã
o
 L
in
e
a
r;
 F
o
rm
u
la
ç
ã
o
 d
e
 P
ro
b
le
m
a
s.
E
x
e
rc
íc
io
s.
3
0
1
/
o
u
t
0
2
/
o
u
t
0
3
/
o
u
t
0
4
/
o
u
t
0
5
/
o
u
t
P
ro
g
ra
m
a
ç
ã
o
 L
in
e
a
r;
 M
é
to
d
o
 S
im
p
le
x
; 
R
e
so
lu
ç
ã
o
 M
a
tr
ic
ia
l.
E
x
e
rc
íc
io
s.
4
0
8
/
o
u
t
0
9
/
o
u
t
1
0
/
o
u
t
1
1
/
o
u
t
1
2
/
o
u
t
P
ro
g
ra
m
a
ç
ã
o
 L
in
e
a
r;
 M
é
to
d
o
 S
im
p
le
x
 d
e
 d
u
a
s 
fa
se
s.
E
x
e
rc
íc
io
s.
5
1
5
/
o
u
t
1
6
/
o
u
t
1
7
/
o
u
t
1
8
/
o
u
t
1
9
/
o
u
t
E
x
e
rc
íc
io
 d
e
 R
e
v
is
ã
o
 -
 P
a
rt
e
 I
6
2
2
/
o
u
t
2
3
/
o
u
t
2
4
/
o
u
t
2
5
/
o
u
t
2
6
/
o
u
t
T
e
o
re
m
a
 d
a
 D
u
a
li
d
a
d
e
.
E
x
e
rc
íc
io
s
2
9
/
o
u
t
3
0
/
o
u
t
3
1
/
o
u
t
0
1
/
n
o
v
0
2
/
n
o
v
S
e
m
a
n
a
 d
e
 E
n
g
e
n
h
a
ri
a
7
0
5
/
n
o
v
0
6
/
n
o
v
0
7
/
n
o
v
0
8
/
n
o
v
0
9
/
n
o
v
P
ro
b
le
m
a
 d
e
 T
ra
n
sp
o
rt
e
s;
 R
e
so
lu
ç
ã
o
 d
o
 P
ro
b
le
m
a
 d
e
 T
ra
n
sp
o
rt
e
s.
E
x
e
rc
íc
io
s
8
1
2
/
n
o
v
1
3
/
n
o
v
1
4
/
n
o
v
1
5
/
n
o
v
1
6
/
n
o
v
P
ro
b
le
m
a
 d
e
 T
ra
n
sp
o
rt
e
s;
 C
a
so
 d
o
 P
ro
b
le
m
a
 d
e
 A
fe
c
ta
ç
ã
o
. 
O
 M
é
to
d
o
 H
u
n
g
a
ro
.
E
x
e
rc
íc
io
s
9
1
9
/
n
o
v
2
0
/
n
o
v
2
1
/
n
o
v
2
2
/
n
o
v
2
3
/
n
o
v
P
ro
b
le
m
a
 d
e
 T
ra
n
sp
o
rt
e
s;
 F
o
rm
u
la
ç
ã
o
 m
a
te
m
á
ti
c
a
 e
 t
a
b
u
la
r;
 P
ro
p
ri
e
d
a
d
e
s.
E
x
e
rc
íc
io
s.
1
0
2
6
/
n
o
v
2
7
/
n
o
v
2
8
/
n
o
v
2
9
/
n
o
v
3
0
/
n
o
v
P
ro
b
le
m
a
 d
e
 R
e
d
e
s;
 T
e
rm
in
o
lo
g
ia
; 
C
a
m
in
h
o
 M
a
is
 C
u
rt
o
; 
Á
rv
o
re
 d
e
 L
ig
a
ç
õ
e
s 
M
ín
im
a
s;
 F
lu
x
o
 M
á
x
im
o
.
E
x
e
rc
íc
io
s
1
1
0
3
/
d
e
z
0
4
/
d
e
z
0
5
/
d
e
z
0
6
/
d
e
z
0
7
/
d
e
z
P
ro
b
le
m
a
s 
d
e
 R
e
d
e
s;
 C
P
M
 &
 P
E
R
T
E
x
e
rc
íc
io
s
1
2
1
0
/
d
e
z
1
1
/
d
e
z
1
2
/
d
e
z
1
3
/
d
e
z
1
4
/
d
e
z
E
x
e
rc
íc
io
 d
e
 R
e
v
is
ã
o
 -
 P
a
rt
e
 I
I
1
3
1
7
/
d
e
z
1
8
/
d
e
z
1
9
/
d
e
z
2
0
/
d
e
z
2
1
/
d
e
z
A
p
e
se
n
ta
ç
ã
o
 d
o
s 
tr
a
b
a
lh
o
s
P
ro
g
ra
m
a
 d
o
 S
e
m
e
st
re
 
IO - Aulas TP 
Página | 6 
 
 
Objetivos da disciplina 
− Contribuir para que os alunos desenvolvam capacidades (métodos) para resolverem problemas concretos 
(processo de tomada de decisões). 
− Dotar os alunos com competências para: 
− Identificar e abordar de forma hábil e estruturada problemas de decisão 
− Construir modelos de problemas de decisão 
− Usar métodos quantitativos na obtenção de soluções para os problemas construídos, como suporte para 
decisões fundamentadas 
− Usar a informação extraída dos modelos para induzir e motivar mudanças organizacionais 
 
 
Bibliografia 
− Hillier, F.S. e G. J. Lieberman, Introduction to Operations Research, McGraw-Hill 
− Taha, H., Operations Research - An Introduction, Prentice-Hall International, Inc. 
− Tavares, L. V.; Oliveira, R. C.; Themido, I. H.; Correia, F. N. , Investigação Operacional, McGraw-Hill 
 
INVESTIGAÇÃO OPERACIONAL 
 
 
 3º Ano 
 (1º semestre) 
 
Departamento de 
Engenharia Civil 
DEC 
 
Secção de Planeamento 
do Território e Ambiente 
 
Investigação Operacional 
A investigação operacional consiste na utilização de métodos científicos para fazer investigação sobre as atividades 
ou operações de uma organização, tendo como objetivo a determinação da melhor alternativa num problema de 
decisão, sujeito a restrições relativas à limitação de recursos. 
Normalmente o termo investigação operacional está associado quase exclusivamente ao uso de técnicas matemáticas 
para modelar e analisar problemas de decisão. No entanto, a componente matemática da investigação operacional 
deve ser encarada no contexto mais vasto do processo de tomada de decisões, cujos elementos não podem ser 
totalmente representados através de um modelo matemático. 
Caraterísticas da Investigação Operacional: 
• A investigação operacional adota uma atitude de pesquisa, procurando compreender a realidade sem 
admitir como ponto de partida conceitos pré-definidos (investigação) 
• a investigação operacional utiliza a compreensão da realidade com o objetivo de apoiar os processos 
decisórios dos responsáveis pelos sistemas analisados, e adota uma atitude sempre orientada para a 
melhoria da sua operacionalidade (operacional) 
• a investigação operacional adota uma metodologia interdisciplinar estruturada recorrendo, com frequência, 
à teoria dos sistemas, às ciências organizacionais, à estatística, a métodos matemáticos de otimização, a 
metodologias de experimentação (geralmente designadas por simulação) e a instrumentos computacionais 
• a investigação operacional considera que a realidade deve ser modelada em cada caso, numa perspectiva 
construtivista, sendo importante o processo de aprendizagem que se desenvolve durante a construção de 
um modelo. 
Evolução da Investigação Operacional: 
• progressos na informática 
o disponibilização de meios e de sistemas de informação, com velocidades e capacidades crescentes 
de concretização algorítmica, adaptando-se cada vez melhor às exigências resultantes da 
complexidade dos problemas em estudo. 
o desenvolvimento de uma relação direta entre os sistemas de informação e os decisores, criando 
condições inéditas de interação entre o conhecimento e a deliberação. 
• progresso nas metodologias de investigação operacional, em especial no campo da modelação estatística e 
estocástica, da experimentação, da construção de heurísticas e da teorização dos processos de decisão. 
Metodologia da Investigação Operacional – Fases: 
1. Formulação do problema 
2. Construção de um modelo 
3. Obtenção da solução 
4. Validação do modelo e teste da solução 
5. Implementação da solução 
 
 
INVESTIGAÇÃO OPERACIONAL 
 
 
 3º Ano 
 (1º 
semestre) 
 
Departamento de 
Engenharia Civil 
DEC 
 
Secção de Planeamento 
do Território e Ambiente 
 
1 Introdução à Programação Linear 
A programação linear (p.l.) é uma técnica de modelação matemática que visa a otimização da utilização de recursos 
limitados. É aplicada em áreas tão diversas como a indústria, a agricultura, os transportes, a economia, os sistemas 
de saúde, e mesmo as ciências sociais e comportamentais. Devidoà sua elevada eficiência computacional é a base 
do desenvolvimento de algoritmos de solução de outros tipos de problemas de investigação operacional (mais 
complexos). 
 
A programação linear envolve o planeamento das atividades de modo a obter um resultado ótimo, isto é, um 
resultado que permita atingir melhor o objetivo pretendido (de acordo com o modelo matemático e dentro das 
alternativas possíveis). O tipo mais comum de aplicação da programação linear envolve a alocação de recursos 
limitados a diversas atividades, embora a programação linear tenha também outras importantes aplicações. Esta 
alocação traduz-se na escolha dos níveis das atividades que permitem atingir o melhor possível determinados 
patamares de desempenho. 
 
1.1 Formulação de Problemas de Programação Linear 
A formulação matemática de um problema de programação linear implica a definição de 3 elementos: 
• VARIÁVEIS DE DECISÃO . Determinar, no problema concreto, aquilo que é fixo e não pode ser alterado, e 
aquilo que se pode decidir (variáveis de decisão). Representar estas variáveis de decisão de uma forma 
algébrica. 
• FUNÇÃO OBJETIVO . Identificar o(s) objetivo(s) do problema e representá-lo(s) como uma função das 
variáveis de decisão, que deve ser maximizada ou minimizada. 
• RESTRIÇÕES . Identificar as restrições do problema, isto é, aquilo que limita as decisões a tomar, e 
representá-las como igualdades ou desigualdades que sejam funções das variáveis de decisão. 
 
Num problema geral de programação linear os termos-chave são os recursos e atividades, em que m denota os 
diferentes tipos de recursos que podem ser utilizados, e n denota o número de atividades que estão a ser 
consideradas. 
Exemplos de recursos: dinheiro, certos tipos de máquinas ou equipamentos, veículos, pessoal... 
Exemplos de atividades: investimento em determinados projetos, publicidade em certos meios de comunicação 
social, transporte de bens de uma dada origem para um dado destino... 
 
 
 
 
 
 
 
IO - Aulas TP 
Página | 9 
 
Informação necessária para um modelo de programação linear envolvendo a alocação de recursos às atividades 
 
 
O modelo coloca o problema da tomada de decisões relativas aos níveis das atividades, razão pela qual x1, x2, …., xn 
se designam por variáveis de decisão. 
xj - nível da atividade j (para j = 1, 2, …., n) 
z - medida geral de “performance” (desempenho) 
cj - aumento de z que resulta de uma unidade de aumento do nível da atividade j 
aij - quantidade do recurso i consumido por cada unidade da atividade j 
* os valores de cj, bi, e aij (para i= 1, 2, …, m e j= 1, 2, …, n) são inputs constantes para o modelo, razão pela qual 
também se designam por parâmetros do modelo 
 
O modelo consiste em selecionar os valores de x1, x2,....., xn de modo a maximizar (ou minimizar) a função objetivo 
(z). 
 
1.1.1 O Modelo em formulação matemática 
Max (Min) z = c1x1+c2x2+.....+cnxn 
sujeito às restrições: 
a11x1+a12x2+.............+a1nxn ≤ (ou ≥ ou =...) b1 
a21x1+a22x2+.............+a2nxn ≤ (ou ≥ ou =...) b2 
am1x1+am2x2+...........+amnxn ≤ (ou ≥ ou =...) bm 
e 
x1 ≥ 0; x2 ≥ 0;......... xn ≥ 0 (ou variáveis xj sem restrição de sinal para alguns valores de j) 
 
qualquer situação cuja formulação matemática se ajuste a este modelo é um problema de programação linear. 
 
 
IO - Aulas TP 
Página | 10 
 
1.1.2 Terminologia para as Soluções do Modelo 
 
Termos mais utilizados 
Região Admissível – RA 
conjunto de todas as soluções admissíveis 
Solução Admissível – SA 
todas as restrições são satisfeitas 
Solução Não Admissível – SNA 
pelo menos uma restrição não é satisfeita 
Solução Básica Admissível – SBA 
solução num vértice da região admissível (resulta da 
interseção de restrições do problema) 
Solução Ótima – SO 
é a solução admissível que conduz ao maior valor 
possível da função objetivo, no caso da 
maximização, e ao menor valor possível da função 
objetivo, para a minimização . 
 
Relação: Soluções Ótimas/Soluções Básicas Admissíveis 
• Problema de programação linear com soluções admissíveis e região admissível limitada, então, o problema 
tem soluções básicas admissíveis e uma delas será a solução ótima. 
• Se o problema tem uma solução ótima ela será um vértice 
• Se o problema tem soluções múltiplas pelo menos duas serão vértices 
 
1.2 Propriedades da Programação Linear 
1.2.1 Proporcionalidade: 
A contribuição de cada atividade para o valor da função objetivo é proporcional ao nível de atividade xj (representado 
pelo termo cjxj) 
A contribuição de cada atividade, no lado esquerdo da equação das restrições, é proporcional ao nível de atividade 
xj (representada pelo termo aixj) 
Não pode haver expoentes superiores a um. 
 
x 2 
x 1 
SNA 
RA 
SA 
SBA 
SO 
FO 
IO - Aulas TP 
Página | 11 
 
 
1.2.2 Aditividade: 
Todas as funções, num modelo de programação linear (seja a função objetivo ou qualquer das restrições), são a 
soma das contribuições individuais das respetivas atividades. 
Exemplos de violação da propriedade da Aditividade: 
 
1.2.3 Divisibilidade: 
As variáveis de decisão, num modelo de programação linear, podem tomar qualquer valor maior ou igual a zero, 
incluindo valores não inteiros. Estas variáveis não se restringem a valores inteiros. Como cada variável de decisão 
representa um nível de atividade, assume-se que as atividades possam decorrer em níveis parciais. 
 
1.2.4 Certeza: 
O valor atribuído a cada parâmetro de um modelo de programação linear é uma constante conhecida. 
Na realidade, esta propriedade raramente é satisfeita. Os valores dos parâmetros utilizados baseiam-se em projeções 
para situações futuras, o que induz algum grau de incerteza. Por esta razão, é muito importante a realização de 
uma análise de sensibilidade após a implementação do novo sistema para avaliar a qualidade dos resultados. 
 
1.3 Exercício Exemplo – Formulação e Resolução Gráfica 
A empresa PAINT, S.A. produz tinta para interior e tinta para exterior a partir de duas matérias-primas, M1 e M2, 
conforme a informação sistematizada na tabela seguinte: 
 Matéria-Prima usada (Ton.) por Ton. de tinta produzida Máxima 
Disponibilidade 
Diária (Ton.) 
Tinta Exterior Tinta Interior 
Matéria-Prima M1 6 4 24 
Matéria-Prima M2 1 2 6 
Lucro por Ton. (Milhares de Euros) 5 4 
 
Uma pesquisa de mercado mostra que a procura máxima diária de tinta para interior não excede as 2 toneladas. 
Além disso, a procura diária de tinta para interior não pode exceder a procura de tinta para exterior mais do que 1 
tonelada. 
A empresa PAINT, S.A. pretende determinar qual a combinação ótima de tinta para interior e para exterior que 
maximiza o lucro diário total. 
 
 
IO - Aulas TP 
Página | 12 
 
1.3.1 Resolução 
VARIÁVEIS DE DECISÃO 
x1 – Produção diária de tinta para exterior (toneladas) 
x2 – Produção diária de tinta para interior (toneladas) 
 
FUNÇÃO OBJECTIVO 
Maximizar z = 5x1 + 4x2 
 
RESTRIÇÕES 
6x1 + 4x2 ≤ 24 (Matéria-prima M1) (1) 
1x1 + 2x2 ≤ 6 (Matéria-prima M2) (2) 
x2 - x1 ≤ 1 (3) 
x2 ≤ 2 (4) 
x1 ≥ 0 (5) 
x2 ≥ 0 (6) 
 
1. Determinar a Região de Admissibilidade 
1 
 
2 
 
3 
 
4 
 
IO - Aulas TP 
Página | 13 
 
5 
 
6 
 
7 
 
8 
 
2. Identificar a Solução ótima 
2.1 Marcar a interceção da função objetivo com o plano x1x2 (portanto para z=0) (linha a traço ponto) 
2.2 Marcar o vetor de crescimento da função objetivo (por definição, perpendicular à reta de interceção da função 
objetivo com o plano x1x2) 
 
∇
→= (5; 4) 
2.3 Identificar o máximo (mínimo) valor de z, identificando a reta paralela à reta de interceção do plano da função 
objetivo e do plano x1x2 de valor de z=0 
 
IO - Aulas TP 
Página | 14 
 
 
Exercícios de Resolução Gráfica 
Exercício 1 
Minimizar 𝒛 = 𝟏𝟎 𝒙𝟏 + 𝟓 𝒙𝟐 
Sujeito às seguintes restrições: 
20𝑥1 + 50𝑥2 ≥ 200 
50𝑥1 + 10𝑥2 ≥ 150 
30𝑥1 + 30𝑥2 ≥ 210 
𝑥1 ≥0 ; 𝑥2 ≥ 0 
 
Exercício 2 
Maximizar 𝒛 = 𝟐 𝒙𝟏 + 𝟑 𝒙𝟐 
Sujeito às seguintes restrições: 
2𝑥1 + 2𝑥2 ≥ 6 
−𝑥1 + 𝑥2 ≤ 1 
𝑥2 ≤ 3 
𝑥1 ≥ 0 ; 𝑥2 ≥ 0 
 
Exercício 3 
Maximizar 𝒛 = 𝒙𝟏 + 𝟕 𝒙𝟐 
Sujeito às seguintes restrições: 
𝑥1 − 2𝑥2 ≤ −5 
𝑥1 + 2𝑥2 ≤ 8 
𝑥1 ≥ 0 ; 𝑥2 ≥ 0 
 
 
Exercícios de Formulação 
Exercício 4 – Construção no Porto 
O Eng.º Manuel, diretor da empresa MCM - Promoção Imobiliária, Lda., possui 2 terrenos para construção na cidade 
do Porto, um deles na Baixa e o outro em Paranhos. Entusiasmado com a perspetiva de aumento da procura de 
habitação na Baixa do Porto, potenciado pelo novo Plano de Revitalização, o Eng.º Manuel decidiu estudar a 
possibilidade de aí construir um edifício de luxo. 
O Eng.º Manuel soube também que, segundo o PDM do Porto e sob indicação da SRU, quem construir ou reabilitar 
edifícios na Baixa poderá beneficiar de um determinado aumento de potencial construtivo em terrenos noutras zonas 
da cidade. Este facto tornou ainda mais aliciante a construção no seu terreno de Paranhos. 
Sabendo que: 
IO - Aulas TP 
Página | 15 
 
− A área máxima de construção permitida pelo PDM no terreno da Baixa é de 2700 m2 
− A área máxima total de construção nos dois terrenos em conjunto, tendo em conta as vantagens oferecidas pelo 
PDM, é de 5000 m2 
− O financiamento máximo que o Eng.º Manuel espera conseguir angariar, tendo em conta a situação da empresa 
e a sua prestação financeira no passado, é de € 4.050.000 
− O custo de construção é aproximadamente € 750/m2 em Paranhos e € 1.050/m2 na Baixa 
− O preço de venda estimado pelo Eng.º Manuel é de cerca de € 900/m2 em Paranhos e € 1.350/m2 na Baixa 
Como é que o Eng.º Manuel deverá repartir a área de construção disponível pelos dois terrenos, de forma a 
maximizar o seu lucro, no conjunto das duas empreitadas? 
 
Exercício 5 - Problema da Refinaria de Petróleo 
Uma refinaria de petróleo pode misturar 3 tipos de crude para produzir gasolina normal e super. 
Existem disponíveis duas unidades de mistura. 
Para cada ciclo de produção, a unidade mais antiga usa 5 barris de crude A, 7 barris de crude B e 2 barris de crude 
C para produzir 9 tanques de gasolina normal e 7 de gasolina super. 
A unidade de mistura mais recente usa 3 barris de crude A, 9 de B e 4 de C para produzir, num ciclo de produção, 5 
tanques de gasolina normal e 9 de super. Devido a contratos já assinados, a refinaria tem que produzir, pelo menos, 
500 tanques de gasolina normal e 300 tanques de gasolina super. 
Existem disponíveis 1500 barris de crude A, 1900 de crude B e 1000 de crude C. 
Por cada tanque de gasolina normal produzida a refinaria ganha 6 unidades monetárias e, por tanque de gasolina 
super, ganha 9 unidades monetárias. 
O problema consiste em saber como utilizar as reservas de crude e as duas unidades de mistura de forma a, 
respeitando os compromissos assumidos, maximizar o lucro da refinaria. 
 
Exercício 6 - Problema do corte de ferro para armaduras 
O ferro Ø16 necessário para as armaduras das sapatas, pilares e vigas de um pavilhão industrial chega à obra em 
atados de 200 varões de 12 metros de comprimento. Estudos efetuados pelo gabinete de preparação de obra 
permitiram identificar as necessidades de ferros com cada um dos comprimentos identificados, conforme indicado 
na tabela seguinte: 
Comprimento de Varões (m) Quantidades Necessárias (nº) 
4 60 
5 20 
6 50 
 
Formule o problema de programação linear que lhe permita minimizar os desperdícios de ferro. 
 
 
IO - Aulas TP 
Página | 16 
 
Exercício 7 - Formulação - Problema do Gabinete de Engenharia 
O gabinete de projetos GAPROBE tem 6 engenheiros. O número total de horas disponível por especialidade por ano 
é mostrado no quadro abaixo. 
Especialidade Horas por ano 
Engenheiros de estruturas 5 000 
Engenheiros de hidráulica 1 500 
Engenheiros de vias 3 500 
 
O GAPROBE trabalha com três principais tipos de obra: pontes, ETARs e urbanizações. O número de horas de trabalho 
de cada especialidade que cada tipo de obra exige em média é o seguinte: 
 Pontes ETARs Urbanizações 
Engenheiros de estruturas 100 60 180 
Engenheiros de hidráulica 0 80 100 
Engenheiros de vias 40 0 60 
 
A procura máxima esperada para projetos de pontes é de 20 por ano, atendendo ao abrandamento recente nesse 
mercado. Nas duas outras áreas não se prevê falta de trabalho. 
Sabendo que o lucro médio por projeto de pontes, ETARs e Urbanizações é, respetivamente, € 12 500, € 10 
000 e € 25 000, formule o problema linear que permite determinar o número de projetos de cada tipo que o 
gabinete deve fazer de forma a maximizar o lucro. 
 
Exercício 8 - Formulação - Problema do Promotor Imobiliário 
A empresa MCM Promoção Imobiliária adquiriu 800 hectares de terreno não-urbanizado no concelho de Gondomar 
numa zona de terraços junto ao Douro. Segundo o PDM, qualquer urbanização a ser construída no local deve obedecer 
aos seguintes critérios: 
− Só podem ser construídas edifícios habitacionais uni, bi e tri-familiares, devendo as habitações unifamiliares 
perfazer, pelo menos, 50% do total dos efifícios. 
− A dimensão de cada lote é de 2, 3 e 4 hectares, respetivamente, para edifícios uni, bi e tri-familiares 
− Devem ser construídas áreas de lazer com um hectare por cada 200 famílias 
 
A MCM estima que exatamente 15% do terreno seja consumido por arruamentos e outros equipamentos básicos, 
sendo o lucro esperado por tipo de habitação apresentado no quadro seguinte: 
 
Tipo de unidade Uni-familiar Bi-familiar Tri-familiar 
Lucro por unidade 10 000 € 12 000 € 15 000 € 
 
O custo da ligação ao sistema de abastecimento de água é proporcional ao número de edifícios construídos. No 
entanto, para que a empresa de abastecimento de água esteja disposta a construir uma conduta até à urbanização, 
as taxas de ligação a pagar pelos habitantes da urbanização a essa empresa devem perfazer, no mínimo, € 100 000 
(para que o projeto seja economicamente viável). 
Para além disso, a expansão do sistema de abastecimento de água para além da sua capacidade atual está limitado 
a 50 000 litros de água por dia durante os períodos de ponta. O quadro seguinte apresenta o custo da ligação ao 
sistema de abastecimento de água por habitação bem como o consumo de água por tipo de habitação/equipamento: 
IO - Aulas TP 
Página | 17 
 
 
Unidade Uni-familiar Bi-familiar Trifamiliar Lazer Unidade 
Ligação 
(€/habitação) 
1 000 1 200 1 400 800 Ligação (€/ha) 
Consumo 
(l/dia/habitação) 
100 120 210 115 
Consumo 
(l/dia/ha) 
 
Formule o modelo de programação linear que permite decidir qual o número de habitações de cada tipo a 
construir bem como o número de áreas de lazer necessárias, de modo a maximizar o lucro da empresa MCM 
Promoção Imobiliária. 
 
Exercício 9 - Formulação - Problema de Afetação de Autocarros 
A CM de Vila Real está a estudar a viabilidade de introduzir um serviço de autocarros na cidade de forma a reduzir 
o acesso de automóveis ao centro e melhorar a acessibilidade da população. 
Nesta fase prévia, a CM pretende determinar o número mínimo de autocarros capaz de suportar a procura existente. 
Como se sabe, a procura de transportes varia ao longo do dia. Depois de um estudo aturado, a CM decidiu que o 
gráfico abaixo é uma boa aproximação dessa procura. 
Sabendo que cada autocarro só pode trabalhar durante 8 horas seguidas por dia por razões de manutenção e 
desgaste, qual é o mínimo número de veículos capaz de satisfazer a procura na cidade? 
 
 
 
12 12 
 Nº de 
 Autocarros 10 
 
8 
 8 
 7 
 
 
 
4 4 4 
 
 
 
 
0 4:00 8:00 12:00 16:00 20:00 24:00 
 
 
INVESTIGAÇÃO OPERACIONAL 
 
 
 3º Ano 
 (1º 
semestre) 
 
 
Departamento de 
Engenharia Civil 
DECSecção de Planeamento 
do Território e Ambiente 
 
2 Método de Simplex – Resolução de problemas de 
Programação Linear 
2.1 Conceitos 
O Método de Simplex (de George Dantzig, 1947) apesar de ser essencialmente um método de resolução algébrica, 
tem todo o seu processo de resolução apoiado em conceitos geométricos. Assim para entender o seu significado é 
fundamental entender os conceitos geométricos em que se baseia. 
Qualquer que seja o problema de programação linear com solução sabe-se que a solução ótima se encontra no limite 
da sua região de admissibilidade, mais especificamente num vértice desse limite denominada Solução Básica 
Admissível (SBA). Como estamos em programação linear sabe-se também que se uma SBA não tem SBAs adjacentes 
com solução (da função objetivo) melhor que essa SBA então essa SBA é solução ótima. Assim, o método simplex 
segue um método iterativo de verificação das soluções básicas admissíveis do problema, iniciando (quando possível) 
pela origem do sistema de eixos (solução básica admissível inicial – em problemas standard) e terminando na SBA 
que não apresente SBAs adjacentes com melhor solução. 
 
ASSIM: 
Conceito 1. O Método Simplex estuda apenas as soluções básicas. Para qualquer problema com, pelo menos, uma 
solução ótima, encontrar essa solução apenas requer encontrar a melhor solução básica (desde que o problema 
possua uma Região de Admissibilidade - RA). 
 
Conceito 2. O Método Simplex é um algoritmo iterativo, isto é, é um procedimento de resolução sistematizado que 
consiste na repetição de uma série de passos, que se designam por iterações, até que se obtenha um determinado 
resultado. 
 
Conceito 3. Sempre que possível, o processo de inicialização do Método Simplex escolhe a origem como solução 
básica admissível inicial (ponto em que todas as variáveis são iguais a zero). 
 
Conceito 4. Dada uma solução básica, é muito mais rápido recolher informação sobre as soluções adjacentes do que 
sobre outras soluções. Por isso, cada vez que o Método Simplex faz uma iteração a partir da solução básica corrente 
para uma solução básica melhor, escolhe sempre uma solução básica adjacente. 
 
Conceito 5. Após a solução básica corrente ser identificada, o Método Simplex examina cada uma das fronteiras da 
região de admissibilidade que emana dessa solução básica. 
 
Conceito 6. Num problema de maximização (minimização) se existir uma taxa de variação positiva (negativa) da 
função objetivo, então existe pelo menos uma solução básica melhor que a atual. 
 
IO - Aulas TP 
Página | 19 
 
 
2.2 Metodologia do algoritmo Simplex 
Início: identificar uma solução básica admissível inicial (origem das coordenadas) 
Iteração: passar a uma solução básica admissível melhor 
• Qual é a variável que entra na base? 
• É a variável não básica (nula) que ao passar a positiva provoca um acréscimo mais rápido de z (num 
problema de maximização) e um decréscimo mais rápido de z (num problema de minimização). Para 
ser fácil fazer essa análise é necessário que a função objetivo seja escrita exclusivamente em função 
das variáveis não básicas. 
• Como se identifica a variável a sair da base? 
• É a correspondente à restrição que primeiro limita a variação da variável que entra na base. 
o Como se identifica a nova solução básica? 
▪ Convertendo as equações para que mantenham a forma canónica: 
• cada variável básica só deverá ter coeficiente 1 numa das equações e coeficiente 
0 em todas as outras. 
• em cada equação só uma variável básica deverá ter coeficiente 1. 
Paragem: parar quando não existe nenhuma solução básica admissível adjacente melhor que a solução atual. 
 
2.3 Resolução Gráfica, Algébrica e pelo Método de Simplex 
Min z = 0.8x1 – 2x2 
S:A: -x1 + x2  8 
x1 - x2  8 
x1 + x2  15 
x2  9; 
x1  0; x2  0 
 
2.3.1 Resolução Gráfica 
 
X1 
X2 
-X1+X2 = 8 
X1-X2 = 8 
X1+X2 = 15 
X2 = 9 
Solução Ótima 
X1=1; X2=9 
Z=0 
Z= -17.2 
IO - Aulas TP 
Página | 20 
 
 
2.3.2 Resolução Algébrica 
Forma aumentada 
(0) z - 0.8x1 + 2x2 + 0x3 + 0x4 + 0x5 + 0x6 = 0 
(1) -x1 + x2 + x3 = 8 
(2) x1 - x2 + x4 = 8 
(3) x1 + x2 + x5 = 15 
(4) x2 + x6 = 9 
 
 
 
 
Condições base no funcionamento: 
• xi≥0 ∀ i (Implícito na resolução) 
• A solução básica inicial é a origem do sistema de coordenadas 
 
Solução Básica Inicial 
x1 = 0; x2 = 0; x3 = 8; x4 = 8; x5 = 15; x6 = 9 
 
Teste do Ótimo 
Tx Crescimento (x1) = 0.8 
Tx Crescimento (x2) = -2  Máximo decrescimento  VBE 
 
2º ITERAÇÃO 
VBE - x2 
VBS=? 
 
 
X1 
X2 
-X1+X2 = 8 
X1-X2 = 8 
X1+X2 = 15 
X2 = 9 
Variáveis de folga 
Variáveis Básicas (VB) na primeira iteração 
Variáveis de decisão 
Variáveis não Básicas (VNB) na primeira iteração 
IO - Aulas TP 
Página | 21 
 
 
Resolver restrições em ordem a x2 
0 + x2 + x3 = 8 
0 - x2 + x4 = 8 
0 + x2 + x5 = 15 
 x2 + x6 = 9 
 
x3 = 8 - x2  0  x2  8 min  x3 - VBS 
x4 = 8 + x2  0  x2 qualquer 
x5 = 15 - x2  0  x2  15 
x6 = 9 - x2  0  x2  9 
 
 
VNB – x1; x3 
VB – x2; x4; x5; x6 
 
(0)-2(1)  (z-0.8x1 + 2x2) -2(-x1 + x2 + x3) = 0-2*8 
(1)/1  -x1 + x2 + x3 = 8 
(2)+(1)  (x1 - x2 + x4) +(-x1 + x2 + x3) = 8+8 
(3)-(1)  (x1 + x2 +x5) – (-x1 + x2 + x3) = 15-8 
(4)-(1)  x2 +x6 – (-x1 + x2 + x3) = 9-8 
 
(0)-2(1) 1.2x1 + 0x2 - 2x3 + 0x4 + 0x5 + 0x6 = -16 
(1)/1 - x1 + x2 + x3 = 8 
(2)+(1) x3 + x4 = 16 
(3)-(1) 2x1 - x3 + x5 = 7 
(4)-(1) x1 - x3 + x6 = 1 
 
Nova solução básica 
x1 = 0; x2 = 8; x3 = 0; x4 = 16; x5 = 7; x6 = 1 
 
Teste do Ótimo 
Tx Crescimento (x1) = -1.2  Máximo decrescimento  VBE 
Tx Crescimento (x3) = 2 
IO - Aulas TP 
Página | 22 
 
 
 
 
3ª Iteração 
VBE – x1 
VBS=? 
Resolver restrições em ordem a x1 
- x1 + x2 + 0 = 8 
 0 + x4 = 16 
2x1 - 0 + x5 = 7 
x1 - 0 + x6 = 1 
 
x2 = 8 + x1  x1 qualquer 
x4 = 16 
x5 = 7 - 2x1  x1  3.5 
x6 = 1 - x1  x1  1 min  x6 - VBS 
 
VNB – x3; x6 
VB – x1; x2; x4; x5 
 
(0)-1.2(4) 0x1 + 0x2 - 0.8x3 + 0x4 + 0x5 - 1.2x6 = -17.2 
(1)+(4) x2 + x6 = 9 
(2)+0 x3 + x4 = 16 
(3)-2(4) x3 + x5 - 2x6 = 5 
(1)/1 x1 - x3 + x6 = 1 
Teste do Ótimo 
Tx Crescimento (x3) = 0.8 
Tx Crescimento (x6) = 1.2 
 
X1 
X2 
-X1+X2 = 8 
X1-X2 = 8 
X1+X2 = 15 
X2 = 9 
IO - Aulas TP 
Página | 23 
 
 
ATINGIU-SE O ÓTIMO 
 
Solução Ótima 
x1 = 1; x2 = 9; x3 = 0; x4 = 16; x5 = 5; x6 = 0 
Valor ótimo da função z = -17.2 
 
2.3.3 Resolução pelo Método Simplex 
 X1 X2 X3 X4 X5 X6 L.D. rácio 
X3 -1 1 1 0 0 0 8 8/1 min 
X4 1 -1 0 1 0 0 8 - 
X5 1 1 0 0 1 0 15 15/1 
X6 0 1 0 0 0 1 9 9/1 
z 0.8 -2 0 0 0 0 0 
X2 -1 1 1 0 0 0 8 - 
X4 0 0 1 1 0 0 16 - 
X5 2 0 -1 0 1 0 7 3.5 
X6 1 0 -1 0 0 1 1 1 min 
z -1.2 0 2 0 0 0 16 
X2 0 1 0 0 0 1 9 
X4 0 0 1 1 0 0 16 
X5 0 0 1 0 1 -2 5 
X1 1 0 -1 0 0 1 1 
z 0 0 0.8 0 0 1.2 17.2 
X1 
X2 
-X1+X2 = 8 
X1-X2 = 8 
X1+X2 = 15 
X2 = 9 
Solução Ótima 
X1=1; X2=9 
IO - Aulas TP 
Página | 24 
 
 
 
x1 = 1; x2 = 9; x3 = 0; x4 = 16; x5 = 5; x6 = 0 
Valor ótimo da função z = -17.2 
 
2.3.4 Método Simplex - Passos Elementares de Resolução 
1. Formular o problema de programação linear na forma normal ou estandardizada ou aumentada: 
• passar as inequações a equações através da utilização de variáveis de folga. 
2. Identificar uma solução básica admissível inicial. Uma solução básica contém um número de variáveis igual ao 
número de restrições funcionais do problema. 
3. Passar todos os coeficientes e constantes do problema para um quadro simplex 
4. Verificar se esta solução é ótima, isto é, verificar se não há nenhum coeficiente positivo na linha da função 
objetivo em problemas de maximização, ou se não há nenhum coeficiente negativo na linha da função objetivo em 
problemas de minimização. 
• caso isto se verifique, a soluçãoótima está encontrada. Não há nenhuma solução alternativa que melhore 
o valor da função objetivo. 
• caso isto não se verifique, escolher como coluna pivot a que corresponde ao coeficiente mais elevado da 
função objetivo em problemas de maximização, e a que corresponde ao coeficiente mais negativo da função 
objetivo em problemas de minimização. A variável associada a essa coluna deve entrar na solução básica, 
já que é a que garante a mais rápida variação da função objetivo no sentido da otimização pretendida. 
5. A variável que vai sair da solução básica (VBS) é a que está associada à restrição que primeiro limita a variação 
da nova variável básica. A forma de determinar o valor dessa variável é escolhendo a linha com o menor valor não 
negativo do quociente entre o termo independente de cada equação e o valor do coeficiente da nova variável básica 
de entrada nessa restrição. A linha associada a essa variável é a linha pivot. 
6. O elemento pivot é o coeficiente que se encontra na interseção da coluna pivot com a linha pivot. 
7. Através de operações sobre linhas, transformar em 1 o elemento pivot e em 0 todos os restantes elementos da 
coluna pivot. 
8. Uma vez encontrada a solução ótima (ponto 4.), o valor ótimo de cada variável básica obtém-se na última coluna 
do quadro simplex, na linha referente a essa variável. O valor ótimo da função objetivo é o simétrico do valor que 
aparece no canto inferior direito do quadro simplex. 
 
 
IO - Aulas TP 
Página | 25 
 
 
2.4 Casos Particulares 
2.4.1 Empate na Variável Básica de Entrada (VBE) 
Quando existe empate na Taxa de Crescimento que leva à escolha da VBE: 
Escolher a VBE arbitrariamente 
 
Exemplo 
Minimizar 𝐳 = −𝐱𝟏 − 𝐱𝟐 
S.A: 
𝒙𝟏 + 2 𝒙𝟐 ≤ 𝟒 (1) 
𝒙𝟏 ≤ 2 (2) 
𝒙𝟏 ≥ 𝟎 ; 𝒙𝟐 ≥ 𝟎 
 
Solução: 
x1=2, x2=1, x3=0, x4=0, z=-3 
 
 X1 X2 X3 X4 L.D. rácio 
X3 1 2 1 0 4 2 
X4 1 0 0 1 2 - 
z -1 -1 0 0 0 
X2 0.5 1 0.5 0 2 4 
X4 1 0 0 1 2 2 
z -0.5 0 0.5 0 2 
X2 0 1 0.5 -0.5 1 
X1 1 0 0 1 2 
z 0 0 0.5 0.5 3 
 
 
 
 
(2) 
(1) 
Z=0 
Z=-3 
X2 
X1 
SO 
IO - Aulas TP 
Página | 26 
 
 
2.4.2 Empate na Variável Básica de Saída (VBS) 
Quando existem várias Variáveis Básicas (VB) com rácio igual ao rácio mínimo: 
Escolher a VBS arbitrariamente 
Resultado: Pelo menos uma das VB’s anula-se na iteração seguinte (a que tendo rácio mínimo não foi escolhida para 
VBS) 
Solução Degenerada 
 
Exemplo 
Maximizar 𝐳 = 𝐱𝟏 + 𝟐 𝐱𝟐 
S.A: 
𝒙𝟏 + 2 𝒙𝟐 ≤ 𝟏𝟐 (1) 
𝟐𝒙𝟏 + 𝒙𝟐 ≤ 6 (2) 
𝒙𝟏 ≥ 𝟎 ; 𝒙𝟐 ≥ 𝟎 
 
Solução degenerada 
x1=0, x2=6, x3=0, x4=0, z=12 
 
 X1 X2 X3 X4 L.D. rácio 
X3 1 2 1 0 12 6 
X4 2 1 0 1 6 6 
z 1 2 0 0 0 
X2 0.5 1 0.5 0 6 
X4 1.5 0 -0.5 1 0 
z 0 0 -1 0 -12 
 
 
 
(2) 
(1) 
Z=0 
Z=12 
X2 
X1 
SO 
IO - Aulas TP 
Página | 27 
 
 
2.4.3 Função Objetivo não é limitada 
Não existem VB em condições de serem VBS (por exemplo quando todos os rácios mínimos são negativos) 
Solução Ilimitada 
 
Exemplo 
Maximizar 𝐳 = 𝐱𝟏 + 𝟐 𝐱𝟐 
Sujeito às seguintes restrições: 
−𝟒𝒙𝟏 + 𝒙𝟐 ≤ 𝟒 (1) 
𝟐𝒙𝟏 − 𝟑𝒙𝟐 ≤ 6 (2) 
𝒙𝟏 ≥ 𝟎 ; 𝒙𝟐 ≥ 𝟎 
 
 
Solução não limitada (não é possível identificar 
VBS) 
 
 X1 X2 X3 X4 L.D. rácio 
X3 -4 1 1 0 4 4 
X4 2 -3 0 1 6 - 
z 1 2 0 0 0 
X2 -4 1 4 - 
X4 -10 0 3 1 18 - 
z 9 0 -2 0 -8 
 
 
 
(1) 
(2) 
X2 
X1 
Z=0 
IO - Aulas TP 
Página | 28 
 
 
2.4.4 Múltiplas Soluções Ótimas 
A solução do problema já atingiu o ótimo e na função objetivo há pelo menos uma VNB com coeficiente zero. 
Para determinar a Solução Ótima Alternativa fazer mais uma iteração (dependendo do numero de soluções 
alternativas) em que a VBE é a que apresenta a Taxa de Crescimento Nula 
 
Exemplo 
 
Maximizar 𝐳 = 𝐱𝟏 + 𝟐𝐱𝟐 
Sujeito às seguintes restrições: 
𝒙𝟏 ≤ 𝟐 (1) 
𝒙𝟐 ≤ 𝟐 (2) 
𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟑 (3) 
𝒙𝟏 ≥ 𝟎 ; 𝒙𝟐 ≥ 𝟎; 𝒙𝟑 ≥ 𝟎 
 
 
Soluções Alternativas 
x1=0, x2=1.5, x3=2, x4=0.5, x5=0, z=3 
ou 
x1=2, x2=0.5, x3=0, x4=1.5, x5=0, z=3 
 X1 X2 X3 X4 X5 L.D. rácio 
X3 1 0 1 0 0 2 - 
X4 0 1 0 1 0 2 2 
X5 1 2 0 0 1 3 1.5 
z 1 2 0 0 0 0 
X3 1 0 1 0 0 2 2 
X4 -0.5 0 0 1 -0.5 0.5 -1 
X2 0.5 1 0 0 0.5 1.5 3 
z 0 0 0 0 -1 -3 S.O. 
X1 1 0 1 0 0 2 
X4 0 0 0.5 1 -0.5 1.5 
X2 0 1 -0.5 0 0.5 0.5 
z 0 0 0 0 -1 -3 S.O 
 
 
SO2 
(3) 
(1) 
(2) 
Z=0 
Z=3 
SO1 
X1 
X2 
IO - Aulas TP 
Página | 29 
 
 
2.5 Problemas não standard 
Definição: Um problema não-standard é um problema que não admite a origem do sistema de coordenadas como 
solução básica admissível e assim não permite ao método simplex iniciar a sua resolução iterativa por esse ponto. 
 
Existe uma variedade de problemas de programação linear que se enquadram nesta definição. Apenas iremos abordar 
3 casos específicos de problemas não-standard: 
• Problemas com restrições de igualdade (=) e que não passam na origem do sistema de coordenadas 
• Problemas com restrições de maior ou igual (≥) 
• Problemas com restrições com Lado Direito negativo 
 
Procedimentos a adotar 
Para que se possa resolver estes problemas pelo método simplex (começando pela origem do sistema de coordenadas 
e admitindo que todas as variáveis são positivas ou nulas) terá que recorrer á introdução de Variáveis Artificias nas 
restrições que a isso obriguem, criando um problema artificial. 
A escrita da forma aumentada implica: 
• Para as restrições de Lado Direito negativo 
o multiplicar a restrição por –1 
o sinal ≥ (>) passará a ≤ (<) e vice-versa 
o NOTA: esta situações devem ser sempre resolvidas antes da escrita da forma aumentada!!! 
• Para as Restrições com a forma ≥ e = 
o Introduzir uma Variável de Excesso (para transformar o sinal ≥ em =) apenas nas restrições de > ou 
≥; 
o Introduzir uma Variável Artificial (para se poder começar na origem com todas as variáveis básicas 
a cumprir a restrição de não negatividade). 
A resolução do problema implica o uso do método de simplex em duas fases. A primeira fase tem como finalidade 
percorrer as soluções básicas não admissíveis, partindo da origem do sistema de coordenadas, à procura da região 
de admissibilidade. A segunda fase tem como finalidade encontrar a solução ótima uma vez dentro da região de 
admissibilidade. A segunda fase é assim em tudo igual ao método simplex para problemas standard. 
 
2.5.1 Resolução de problemas não-standard pelo método de simplex (de 2 fases) 
Minimizar 𝐳 = −𝐱𝟏 − 𝐱𝟐 
Sujeito às seguintes restrições: 
−𝒙𝟏 − 𝒙𝟐 ≥ −5 (𝒙𝟏 + 𝒙𝟐 ≤ 5) 
𝒙𝟏 + 𝒙𝟐 ≥ 3 
𝒙𝟏 − 𝒙𝟐 = 𝟏 
𝒙𝟏 ≥ 𝟎 ; 𝒙𝟐 ≥ 𝟎 
 
 
 
 
 
 
IO - Aulas TP 
Página | 30 
 
 
Resolução Gráfica 
 
 
Escrita da forma aumentada: 
Min z= -x1 -x2 
 x1 +x2 +x3 =5 
 x1 +x2 -x4 +𝑥5̅̅ ̅ =3 
 x1 -x2 +𝑥6̅̅ ̅ =1 
Min g= -2x1 +x4 =4 
(Min g = ∑ 𝑣𝑎𝑟𝑖á𝑣𝑒𝑖𝑠 𝑎𝑟𝑡𝑖𝑓𝑖𝑐𝑖𝑎𝑖𝑠 ) 
 
SO 
X2 
X1 
Z=0 
x3 – variável de folga 
x4 – variável de excesso 
𝑋5̅̅ ̅e 𝑋6̅̅ ̅ – variáveis artificial 
IO - Aulas TP 
Página | 31 
 
 
 
 X1 X2 X3 X4 𝑋5̅̅ ̅ 𝑋6̅̅ ̅ L.D. rácio 
X3 1 1 1 0 0 0 5 5 
𝑋5̅̅ ̅ 1 1 0 -1 1 0 3 3 
𝑋6̅̅ ̅ 1 -1 0 0 0 1 1 1 
z -1 -1 0 0 0 0 0 
g -2 0 0 1 0 0 -4 
X3 0 2 1 0 0 -1 4 2 
𝑋5̅̅ ̅ 0 2 0 -1 1 -1 2 1 
X1 1 -1 0 0 0 1 1 -1 
z 0 -2 0 0 0 1 1 
g 0 -2 0 1 0 2 -2 
X3 0 0 1 1 -1 0 2 2 
X2 0 1 0 -0,5 0,5 -0,5 1 -2 
X1 1 0 0 -0,5 0,5 0,5 2 -4 
z 0 0 0 -1 1 0 3 
g 0 0 0 0 1 1 0 
X4 0 0 1 1 2 
 
X2 0 1 0,5 0 2 
 
X1 1 0 0,5 0 3 
 
z 0 0 1 0 5 
 
Solução 
x1=3, x2=2, x3=0, x4=2, x5=0, x6=0, z=-5 
 
2.5.2 Método Simplex de 2 fases - Passos Elementares de Resolução 
1. Formular o problema de programação linear na forma normal ou estandardizada ou aumentada: 
• passar as inequações a equações através da utilização de variáveis de folga ou de variáveis de excesso ou 
afastamento. 
• às restrições do tipo ou = devem ainda ser adicionadas variáveisartificiais. 
2. Criar uma função auxiliar g igual à variável artificial ou à soma das variáveis artificiais. A primeira fase do método 
consiste em minimizar a função g, atendendo às restrições do problema. 
3. Passar todos os coeficientes e constantes do problema para um quadro simplex. Nas duas últimas linhas do quadro 
figuram, respetivamente, os coeficientes da função z e os coeficientes da função g. 
4. Minimizar o valor da função auxiliar g. No final da primeira fase do método todos os coeficientes de custo reduzido 
da função g devem ser nulos à exceção do coeficiente da variável artificial ou das variáveis artificiais que é (são) 1. 
O valor de g deverá ser nulo, caso contrário o problema é impossível. 
1ª fase do método simplex de 2 fases 
• Otimizar a função auxiliar (g) 
• Encontrar a região de admissibilidade 
2ª fase do método simplex de 2 fases 
• Otimizar a função objetivo (z) 
• Encontrar a solução ótima 
IO - Aulas TP 
Página | 32 
 
 
5. Caso se verifique a condição anterior, cortar a última linha do quadro simplex, bem como a(s) coluna(s) 
referente(s) à(s) variável(eis) artificial(ais). A segunda fase do método simplex consiste em otimizar a função 
objetivo (cujos coeficientes figuram agora na última linha do quadro simplex). 
 
2.5.3 Caso Particular (mais um): Problema impossível 
Quando se atinge o ótimo da função auxiliar mas não se anulou as variáveis artificiais. 
Significado gráfico: Problema sem região de admissibilidade. 
Apenas possível para problemas não-standard. 
 
Exemplo 
Mazimixar 𝐳 = 𝐱𝟏 + 𝐱𝟐 
S.A: 
𝒙𝟏 + 𝒙𝟐 ≥ 𝟑 (1) 
𝒙𝟏 ≤ 1 (2) 
𝒙𝟐 ≤ 1 (3) 
𝒙𝟏 ≥ 𝟎 ; 𝒙𝟐 ≥ 𝟎 
 
Problema impossível 
 
 X1 X2 X3 𝑋4̅̅̅̅ X5 X6 L.D. rácio 
𝑋4̅̅̅̅ 1 1 -1 1 0 0 3 3 
X5 1 0 0 0 1 0 1 1 
X6 0 1 0 0 0 1 1 - 
z 1 1 0 0 0 0 0 
g -1 -1 1 0 0 0 -3 
𝑋4̅̅̅̅ 0 1 -1 1 -1 0 2 2 
X1 1 0 0 0 1 0 1 - 
X6 0 1 0 0 0 1 1 1 
z 0 1 0 0 -1 0 -1 
g 0 -1 1 0 1 0 -2 
𝑋4̅̅̅̅ 0 0 -1 1 -1 -1 1 
X1 1 0 0 0 1 0 1 
X2 0 1 0 0 0 1 1 
z 0 0 0 0 -1 -1 -2 
g 0 0 1 0 1 1 -1 
 
 
 
(2) 
(1) 
Z=0 
X2 
X1 
(3) 
RA = Ø 
IO - Aulas TP 
Página | 33 
 
 
Exercícios de Método de Simplex 
Exercício 10 – Método de Simplex (Problemas Standard) 
10.1: 
Minimizar 𝐳 = −𝟓 𝐱𝟏 + 𝟐 𝐱𝟐 
Sujeito às seguintes restrições: 
𝟐𝒙𝟏 + 𝒙𝟐 ≤ 𝟗 
𝒙𝟏 − 𝟐𝒙𝟐 ≤ 2 
−𝟑𝒙𝟏 + 𝟐. 𝟓𝒙𝟐 ≤ 𝟑 
𝒙𝟏 ≥ 𝟎 ; 𝒙𝟐 ≥ 𝟎 
10.2: 
Maximizar 𝐳 = 𝟐𝐱𝟏 − 𝐱𝟐 + 𝐱𝟑 
Sujeito às seguintes restrições: 
𝟑𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 ≤ 𝟔 
𝒙𝟏 − 𝒙𝟐 + 𝟐𝒙𝟑 ≤ 𝟏 
𝒙𝟏 + 𝒙𝟐 − 𝒙𝟑 ≤ 𝟐 
𝒙𝟏 ≥ 𝟎 ; 𝒙𝟐 ≥ 𝟎; 𝒙𝟑 ≥ 𝟎 
10.3: 
Maximizar 𝐳 = 𝟑𝐱𝟏 + 𝟓𝐱𝟐 + 𝟔𝐱𝟑 
Sujeito às seguintes restrições: 
𝟐𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 ≤ 𝟒 
𝒙𝟏 + 𝟐𝒙𝟐 + 𝒙𝟑 ≤ 𝟒 
𝒙𝟏 + 𝒙𝟐 + 𝟐𝒙𝟑 ≤ 𝟒 
𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 ≤ 𝟑 
𝒙𝟏 ≥ 𝟎 ; 𝒙𝟐 ≥ 𝟎; 𝒙𝟑 ≥ 𝟎 
10.4: 
Maximizar 𝐳 = 𝐱𝟏 + 𝐱𝟐 + 𝐱𝟑 + 𝐱𝟒 
Sujeito às seguintes restrições: 
𝒙𝟏 + 𝒙𝟐 ≤ 3 
𝒙𝟑 + 𝒙𝟒 ≤ 𝟐 
𝒙𝟏 ≥ 𝟎 ; 𝒙𝟐 ≥ 𝟎; 𝒙𝟑 ≥ 𝟎; 𝒙𝟒 ≥ 𝟎 
10.5: 
Maximizar 𝐳 = 𝟓𝐱𝟏 + 𝐱𝟐 + 𝟑𝐱𝟑 + 𝟒𝐱𝟒 
Sujeito às seguintes restrições: 
𝒙𝟏 − 𝟐𝒙𝟐 + 𝟒𝒙𝟑 + 𝟑𝒙𝟒 ≤ 20 
−𝟒𝒙𝟏 + 𝟔𝒙𝟐 + 𝟓𝒙𝟑 − 𝟒𝒙𝟒 ≤ 40 
𝟐𝒙𝟏 − 𝟑𝒙𝟐 + 𝟑𝒙𝟑 + 𝟖𝒙𝟒 ≤ 50 
𝒙𝟏 ≥ 𝟎 ; 𝒙𝟐 ≥ 𝟎; 𝒙𝟑 ≥ 𝟎; 𝒙𝟒 ≥ 𝟎 
10.6: 
Maximizar 𝒛 = 𝟐𝒙𝟏 + 𝟐 𝒙𝟐 − 𝒙𝟑 − 𝒙𝟒 
Sujeito às seguintes restrições: 
𝟐𝒙𝟏 + 𝒙𝟑 – 𝟐𝒙𝟒 ≤ 𝟔 
−𝟐𝒙𝟏 + 𝟐𝒙𝟐 + 𝒙𝟑 − 𝒙𝟒 ≥ −8 
𝒙𝟏 + 𝒙𝟐 + 𝟐𝒙𝟒 ≤ 𝟓 
𝒙𝟏 ≥ 𝟎 ; 𝒙𝟐 ≥ 𝟎 ; 𝒙𝟑 ≥ 𝟎 ; 𝒙𝟒 ≥ 𝟎 
 
Exercício 11 – Método de Simplex (Problemas não Standard) 
11.1 
Minimizar 𝐳 = 𝐱𝟏 + 𝟑𝐱𝟐 
Sujeito às seguintes restrições: 
2𝑥1 + 𝑥2 ≤ 9 
𝑥1 + 2𝑥2 ≥ 2 
−3𝑥1 + 2.5𝑥2 ≤ 3 
𝑥1 ≥ 0 ; 𝑥2 ≥ 0 
11.2 
Maximizar 𝐳 = −𝟐𝐱𝟏 + 𝟑𝐱𝟐 
Sujeito às seguintes restrições: 
−2𝑥1 − 𝑥2 ≤ −10 
4𝑥1 − 𝑥2 ≤ 4 
𝑥2 = 6 
𝑥1 ≥ 0 ; 𝑥2 ≥ 0 
 
IO - Aulas TP 
Página | 34 
 
 
11.3 
Minimizar 𝐳 = −𝐱𝟏 + 𝟐𝐱𝟐 
Sujeito às seguintes restrições: 
2𝑥1 + 𝑥2 ≤ 9 
𝑥1 + 𝑥2 ≥ 80 
𝑥1 ≤ 50 
𝑥1 ≥ 0 ; 𝑥2 ≥ 0 
 
11.4 
Minimizar 𝐳 = 𝟑𝐱𝟏 + 𝟐𝐱𝟐 
Sujeito às seguintes restrições: 
2𝑥1 + 𝑥2 ≥ 10 
−3𝑥1 + 2𝑥2 ≤ 6 
𝑥1 + 𝑥2 ≥ 6 
𝑥1 ≥ 0 ; 𝑥2 ≥ 0 
 
INVESTIGAÇÃO OPERACIONAL 
 
 
 3º Ano 
 (1º 
semestre) 
 
 
Departamento de 
Engenharia Civil 
DEC 
 
Secção de Planeamento 
do Território e Ambiente 
 
Exercícios de Exame – Parte I 
Exercício 12 (05.11.2008) 
Uma empresa de fabrico de brinquedos procedeu a uma recolha de dados referentes à sua capacidade de produção 
e às condições de mercado, no sentido de programar a sua produção para o período de 23 de Outubro a 23 de 
Dezembro. Durante este período regista-se um acréscimo significativo de encomendas o que, regra geral, leva à 
inexistência de limites superiores para as vendas dos produtos da empresa. A empresa trabalha 22 dias úteis por 
mês, e 8 horas por dia. 
A empresa produz 2 tipos de brinquedos a partir da utilização de dois tipos de componentes (em plástico, em 
madeira) e 2 máquinas. Supõe-se que existem componentes em plástico e madeira suficientes para satisfazer as 
necessidades produtivas. 
O brinquedo 1BFX é um conjunto de construção, sendo constituído por 14 peças. O outro brinquedo (2CAR) é 
constituído por uma só peça. 
As capacidades das duas máquinas (expressas em nº de peças/hora) e as necessidades de componentes (expressas 
em componentes por peça) são as seguintes: 
 
 (peças/hora) (componentes/peça) 
 Máq. A Máq. B Plástico Madeira 
1BFX 100 80 5 4 
2CAR 40 40 70 - 
 
Um acordo com as lojas estabeleceu um limite mínimo de produção de 150 brinquedos 1BFX para o período indicado. 
Durante os 2 meses do programa, as máquinas A e B têm capacidades de trabalho de 100 e 225 horas, com custos 
horários de 3 e 3,5 euros, respetivamente. Os componentes têm custos de 0,7 e 0,3 euros, respetivamente, por 
componente de plástico e de madeira. 
Os preços de venda dos brinquedos são de 70 euros para 1BFX, 50 euros para cada 2CAR. 
Formule o problema de modo a maximizar o lucro da empresa. 
 
Exercício 13 (04.11.2009) 
Uma empresa de pré-fabricados tem capacidade para a produção de vigotas de 5m, por turnos diários. Cada turno 
de produção incorre num custo diferente. 
A procura esperada, bem como os custos de produção e a capacidade de produção total, por turno de produção, são 
indicados no quadro seguinte. 
 
 
 
IO - Aulas TP 
Página | 36 
 
 
Turno diário Procura mínima Custo de produção Capacidade de produção total 
 (n.º vigotas) (€/vigota) (nº vigotas) 
T1: 04 – 10 125 8 150 
T2: 10 – 16 150 4 160 
T3: 16 – 22 200 6 150 
T4: 22 - 04 75 9 170 
 
É possível armazenar um máximo de 100 vigotas num armazém próximo ao custo de 1,5 € por vigota e por turno de 
produção. 
Pretende-se determinar o regime de produção e/ou armazenagem mais conveniente, minimizando o custo total, 
de modo a que a empresa possa dar resposta à procura existente, sabendo que existe um stock inicial de 15 vigotas 
e que as vigotas são vendidas por ordem de produção (ou seja, a quantidade de vigotas existente em armazém é a 
primeira a ser vendida). 
 
Exercício 14 (23.01.2013) 
Considere o problema de programação linear com a seguinte formulação matemática: 
Max z = -x1 + x2 
s.a.: 
-x1 + x2 ≤ 1 
 x1 - x2 ≤ 1 
 x1 + x2 ≤ 1 
-x1 - x2 ≤ 1 
x1 ≥ 0; x2 ≥ 0 
 
a) Resolva o problema geometricamente. Caracteriza a(s) solução(ões) ótima(s) obtida(s) (valor da função 
objetivo e das variáveis). 
b) Escreva o quadro inicial de resolução deste problema pelo método de simplex. Indique o nome das variáveis 
que acrescentou na escrita da forma normal (ou estandardizada ou aumentada). 
c) Identifique a variável básica de entrada na primeira iteração. Justifique. 
d) De acordo com a informação de que dispõe até este momento, de quantas iterações precisa para chegar àsolução ótima? Justifique. 
e) Faça uma iteração. Caracterize a solução encontrada (valor da função objetivo e das variáveis). Explique o 
significado gráfico da iteração efetuada. Esta solução é ótima? Justifique. 
 
 
IO - Aulas TP 
Página | 37 
 
 
Exercício 15 (27.01.2012) 
Considere o problema de programação linear com a seguinte formulação matemática: 
Max Z = X1 - X2 
s.a. : 
X1 ≤ 3 
X2 = 3 
-X1 - X2 ≤ -7 
X1 ≥ 0; X2 ≥ 0 
 
a) Indique a solução básica inicial (valor da função objetivo e das variáveis de decisão). 
i. Esta solução básica é admissível? Justifique. 
b) Escreva o quadro inicial do método de simplex 
i. Indique o nome das variáveis que acrescentou na escrita da forma aumentada. 
c) Identifique as Variáveis não básicas (VNB) iniciais. 
d) Identifique a Variável básica de entrada (VBE) da primeira iteração. Justifique. 
e) Considere o quadro simplex seguinte: 
 
i. Calcule uma iteração a partir do quadro dado. 
ii. Caracterize a solução encontrada (valor da função objetivo e das variáveis). 
iii. A solução é ótima? Justifique, indicando o significado gráfico da solução encontrada. 
f) Indique o valor das letras “A” a “I” (sombreadas a cinzento) do quadro seguinte sabendo que representa o 
quadro ótimo de um problema simplex com solução degenerada de valor 6. 
 
 
x1 x2 x3 x4 x5 x6
x3 1 0 1 0 0 0 3
x2 0 1 0 1 0 0 3
x6 1 0 0 -1 -1 1 4
z 1 0 0 1 0 0 3
g -1 0 0 2 1 0 -5
x1 x2 x3 x4 x5 x6
A 0 C 2 1 3 4 H
x2 0 D 0 0 2 7 2
B 1 E 0 0 2 1 4
z 0 F 4 G 3 1 I
 
INVESTIGAÇÃO OPERACIONAL 
 
 
 3º Ano 
 (1º 
semestre) 
 
 
Departamento de 
Engenharia Civil 
DEC 
 
Secção de Planeamento 
do Território e Ambiente 
 
3 Teorema da Dualidade 
 
A todo o problema de programação linear nas variáveis x1, x2, ...., xn (designado por primal) está associado um outro 
problema linear nas variáveis y1, y2, ...., ym (designado por dual). A definição matemática do problema dual está 
estritamente relacionada, e pode ser obtida diretamente, a partir do problema primal. 
 
PROBLEMA PRIMAL PROBLEMA DUAL 
𝑀𝑎𝑥 𝑧 = ∑ 𝑐𝑗𝑥𝑗
𝑛
𝑗=1
 
s.a.: 
∑ 𝑎𝑖𝑗𝑥𝑗 ≤ 𝑏𝑖 , 𝑖 = 1,2, … , 𝑚
𝑛
𝑗=1
 
𝑥𝑗 ≥ 0, 𝑗 = 1,2, … , 𝑛 
n VARIÁVEIS 
m RESTRIÇÕES 
𝑀𝑖𝑛 𝑤 = ∑ 𝑏𝑖𝑦𝑖
𝑚
𝑖=1
 
s.a.: 
∑ 𝑎𝑖𝑗𝑦𝑖 ≥ 𝑐𝑗 , 𝑗 = 1,2, … , 𝑛
𝑚
𝑖=1
 
𝑦𝑖 ≥ 0, 𝑖 = 1,2, … , 𝑚 
m VARIÁVEIS 
n RESTRIÇÕES 
 
Correspondências de formulação entre os problemas Primal e Dual 
As variáveis e as restrições do problema dual podem ser construídas a partir do problema primal da seguinte forma: 
• se o primal está a maximizar, o dual está a minimizar, e se o primal está a minimizar, o dual está a 
maximizar. 
• a cada uma das m restrições do problema primal está associada uma variável do dual, e a cada uma das n 
restrições do problema dual está associada uma variável do primal. 
• a cada uma das n variáveis do problema primal está associada uma restrição do dual, e a cada uma das m 
variáveis do problema dual está associada uma restrição do primal. 
• os coeficientes das variáveis do membro esquerdo de cada restrição do problema primal (linha) igualam os 
coeficientes da variável dual associada nas restrições (coluna) do dual, e os coeficientes das variáveis do 
membro esquerdo de cada restrição do problema dual (linha) igualam os coeficientes da variável primal 
associada nas restrições (coluna) do primal. 
• os coeficientes da função objetivo do problema primal igualam os termos independentes das restrições do 
dual, e os coeficientes da função objetivo do problema dual igualam os termos independentes das restrições 
do primal. 
 
 
 
IO - Aulas TP 
Página | 39 
 
 
Correspondência entre problema primal e dual: 
Problema Primal 
(ou Problema Dual) 
Problema Dual 
(ou Problema Primal) 
Maximizar Z (ou W) Minimizar W (ou Z) 
Restrição i: 
Na forma ≤ 
Na forma = 
Na forma ≥ 
Variável yi (ou xi): 
Yi ≥ 0 
Yi sem restrição de sinal 
Yi ≤ 0 
Variável xj (ou yj): 
xj ≥ 0 
xj sem restrição de sinal 
xj ≤ 0 
Restrição j: 
Na forma ≥ 
Na forma = 
Na forma ≤ 
 
Exemplo 
Primal (Dual) Dual (Primal) 
Maximizar z = 5x1 + 4x2 
6x1 + 4x2 ≤ 24 
x1 + 2x2 ≤ 6 
- x1 + x2 ≤ 1 
x2 ≤ 2 
 
x1 ≥ 0 
x2 ≥ 0 
Minimizar w = 24y1 + 6y2 + y3 + 2y4 
y1 ≥ 0 
y2 ≥ 0 
y3 ≥ 0 
y4 ≥ 0 
 
6y1 + y2 – y3 ≥ 5 
4y1 + 2y2 + y3 + y4 ≥ 4 
 
 
Leitura das equações do problema primal e dual 
 Problema Primal 
Coeficientes L.D 
x1 x2 W 
P
ro
b
le
m
a
 D
u
a
l 
C
o
e
fi
c
ie
n
te
s 
y1 6 4 (≤) 24 
C
o
e
fi
c
ie
n
te
s 
d
a
 
F
.O
. 
W
 
y2 1 2 (≤) 6 
y3 -1 1 (≤) 1 
y4 0 1 (≤) 2 
L.D Z (≥) 5 (≥) 4 0 
 Coeficientes da F.O. 
Z 
 
IO - Aulas TP 
Página | 40 
 
 
Leitura da solução básica admissível no quadro simplex 
Primal (Dual) Dual (Primal) 
Maximizar z = 5x1 + 4x2 
6x1 + 4x2 +x3 = 24 
x1 + 2x2 +x4 = 6 
- x1 + x2 +x5 = 1 
 x2 +x6 = 2 
 x1 x2 x3 x4 x5 x6 
x3 6 4 1 0 0 0 24 
x4 1 2 0 1 0 0 6 
x5 -1 1 0 0 1 0 1 
x6 0 1 0 0 0 1 2 
Z 5 4 0 0 0 0 0 
Solução Ótima 
 x1 x2 x3 x4 x5 x6 
x1 1 0 1/4 - 1/2 0 0 3 
x2 0 1 - 1/8 3/4 0 0 3/2 
x5 0 0 3/8 -5/4 1 0 5/2 
x6 0 0 1/8 - 3/4 0 1 1/2 
Z 0 0 - 3/4 - 1/2 0 0 -21 
 
Variáveis de Decisão 
 Valor Coef na F.O. 
Variáveis de Decisão 
x1 3 0 
x2 3/2 0 
Variáveis de Folga 
x3 0 -3/4 
x4 0 -1/2 
x5 5/2 0 
x6 1/2 0 
 
Minimizar w = 24y1 + 6y2 + y3 + 2y4 
6y1 + y2 – y3 -y5 + y6 = 5 
4y1 + 2y2 + y3 + y4 -y7 +y8 = 4 
 
 
 y1 y2 y3 y4 y5 y6 y7 y8 
y6 6 1 -1 0 -1 1 0 0 5 
y8 4 2 1 1 0 0 -1 1 4 
W 24 6 1 2 0 0 0 0 0 
 
 
 
 y1 y2 y3 y4 y5 y7 
y1 1 0 - 1/3 - 1/9 - 1/4 1/9 3/4 
y2 0 1 5/4 3/4 1/2 - 3/4 1/2 
W 0 0 5/2 1/2 3 3/2 -21 
 
 
 
 
Variáveis de Excesso 
 Valor Coef na F.O. 
Variáveis de Excesso 
y5 0 3 
y7 0 3/2 
Variáveis de Decisão 
y1 3/4 0 
y2 1/2 0 
y3 0 5/2 
y4 0 1/2 
 
 
 
 
 
 
*(-1) 
IO - Aulas TP 
Página | 41 
 
 
Associação entre variáveis do primal e dual: 
Problema Primal 
(ou Problema Dual) 
Problema Dual 
(ou Problema Primal) 
Maximizar Z (ou W) Minimizar W (ou Z) 
Variáveis de Decisão 
Variáveis de Folga 
Variáveis de excesso 
Variáveis de Decisão 
 
Assim: 
Valor das variáveis duais = Coeficiente da função objetivo das variáveis primais (cij) 
Valor das variáveis de folga ou excesso = Coeficiente das variáveis de decisão 
Valor das variáveis de decisão = Coeficiente das variáveis de folga ou excesso 
 
Teorema Fundamental da Dualidade 
Num par de problemas primal-dual, se um deles tem solução ótima, então o outro também tem, e o valor ótimo da 
função objetivo é o mesmo para os dois problemas. 
 
Teorema da Complementaridade da Folga 
Se as variáveis de folga ou de excesso ou afastamento correspondentes a uma dada restrição no problema primal 
(dual) forem positivas na solução ótima, a variável dual (primal) correspondente a essa restrição é nula na solução 
ótima 
 
 
Exercícios de Dualidade 
Exercício 16 
Escreva o problema dual dos problemas seguintes: 
16.1 
Maximizar 𝐳 = 𝟐𝐱𝟏 + 𝐱𝟐 
Sujeito às seguintes restrições: 
𝑥1 + 𝑥2 ≥ 2 
𝑥1 + 𝑥2 ≤ 4 
𝑥1 ≥ 0 ; 𝑥2 ≥ 0 
16.2 
Minimizar 𝐳 = 𝟒𝐱𝟏 + 𝟖𝐱𝟐 + 𝟑𝒙𝟑 
Sujeito às seguintes restrições: 
𝑥1 + 𝑥2 ≥ 2 
2𝑥1 + 𝑥3 ≥ 5 
𝑥1 + 𝑥2 + 𝑥3 = 3 
𝑥1 ≥ 0 ; 𝑥2 ≥ 0; 𝑥3 ≥ 0; 
 
 
 
 
IO - Aulas TP 
Página | 42 
 
 
16.3 
Minimizar 𝐳 = 𝐱𝟏 + 𝟑𝐱𝟐 
Sujeito às seguintes restrições: 
2𝑥1 + 𝑥2 ≤ 9 
𝑥1 + 2𝑥2 ≥ 2 
−3𝑥1 + 2.5𝑥2 = 3 
𝑥2 ≤ 0 
16.4 
Maximizar 𝐳 = −𝐱𝟏 − 𝐱𝟐 
Sujeito às seguintes restrições: 
−𝑥1 + 3𝑥2 ≤ 10 
𝑥1 + 𝑥2 ≤ 6 
𝑥1 − 𝑥2 ≤ 2 
𝑥1 + 3𝑥2 ≥ 6 
2𝑥1 + 𝑥2 ≥ 4 
𝑥1 ≥ 0 ; 𝑥2 ≥ 0 
 
Exercício 17 
Escreva a função objetivo do problema dual sabendo que o problemaprimal: 
• é de maximização 
• tem 5 variáveis das quais 2 são variáveis de decisão e 3 são variáveis de folga 
• na solução básica inicial as variáveis de folga têm o valor de x3=3; x4=1; x5=5. 
 
Exercício 18 
Classifique a solução ótima do problema primal e dual para cada um dos quadros ótimo de problemas de 
programação linear apresentados de seguida: 
 
18.1 Max z 
 x1 x2 x3 x4 x5 x6 LD 
x4 0 0 1 1 -1 -2 1 
x1 1 0 0,5 0 0,5 0,5 1,5 
x2 0 1 -1,5 0 -0,5 0,5 0,5 
z 0 0 -1,5 0 -1,5 -0,5 -2,5 
 
18.2 Max z 
 x1 x2 X3 x4 x5 x6 x7 LD 
x1 1 0 0 13,55 -3 0,55 3,09 116,4 
x3 0 0 1 1,09 0 0,09 0,18 12,7 
x2 0 1 0 7,45 -2 0,45 1,91 73,6 
z 0 0 0 -74,45 17 -3,45 -17,91 -693,6 
 
18.3 Min z 
Nota: A variável x5 é artificial e foi adicionada numa restrição de ≥ 
 x1 x2 x3 x4 x5 x6 L.D. 
x3 0 -3 1 2 - 0 5 
x1 1 2 0 -1 - 0 2 
x6 0 8,5 0 -3 - 1 9 
z 0 1 0 1 - 0 -2 
g - - - - - - - 
 
 
INVESTIGAÇÃO OPERACIONAL 
 
 
 3º Ano 
 (1º 
semestre) 
 
 
Departamento de 
Engenharia Civil 
DEC 
 
Secção de Planeamento 
do Território e Ambiente 
 
4 Problema de Transportes 
Genericamente, o Problema de Transportes refere-se à distribuição de qualquer tipo de bem proveniente de um 
conjunto de fornecedores (denominados origens) para um conjunto de clientes (denominados destinos). 
 
Assim, uma origem i (i = 1, 2, …, m) pode fornecer ai unidades de um dado bem aos vários destinos, e um determinado 
destino j (j = 1, 2, …, n) procura bj unidades a partir das várias origens. 
 
Um pressuposto dos problemas de transportes é o de que o custo de transporte entre a origem i e o destino j é 
proporcional ao número de unidades transportadas, designando cij o custo unitário de transporte. 
 
Como deve o produtor enviar o seu produto das várias origens para os vários destinos de modo a minimizar o custo 
total de transporte? 
 
 
 
 
 
Origens i Destinos j 
IO - Aulas TP 
Página | 44 
 
 
4.1 Formulação em problema de programação linear 
Variáveis de Decisão: xij - quantidade a enviar da origem i para o destino j 
𝑀𝑖𝑛 𝑧 = ∑ ∑ 𝑐𝑖𝑗 ∗ 𝑥𝑖𝑗
𝑛
𝑗
𝑚
𝑖
 
Sujeito a: 
Para todas as origens i 
∑ 𝑥𝑖𝑗 = 𝑎𝑖
𝑛
𝑗=1
 
a – oferta de cada origem i 
Para todos os destinos j 
∑ 𝑥𝑖𝑗 = 𝑏𝑗
𝑚
𝑖=1
 
b – procura de cada destino j 
Restrições de não negatividade para todas as variáveis. 
 
 
É condição necessária e suficiente para que um problema de transportes tenha solução admissível que 
∑ 𝑎𝑖
𝑛
𝑗
= ∑ 𝑏𝑗
𝑚
𝑖
 
 
 
IO - Aulas TP 
Página | 45 
 
 
4.2 Formulação em Problema de Transportes (Tabular) 
Com, 
cij – coeficientes da função objetivo 
cij – custos reduzidos; coeficientes da função objetivo em cada iteração uma vez reduzido o sistema de eixos em 
cada iteração (à semelhança do método simplex) 
 
 Destinos j (procura) 
 D1 D2 … Dn 
O
ri
g
e
n
s 
i 
(o
fe
rt
a
) 
O1 
cij 
 𝑐𝑖𝑗̅̅̅̅ Xij a1 
O2 
 
 a2 
… 
 
 … 
Om 
 
 am 
 b1 b2 … bn 
 
4.3 Resolução do Problema de Transportes 
Exercício exemplo 
A empresa Constrói-Razoavelmente (CR) tem neste momento obras em 
Lisboa, no Porto e em Coimbra. A procura diária de inertes em cada obra 
está de acordo com o quadro seguinte: 
 
 Porto Coimbra Lisboa 
Procura de 
inertes 
(m3/dia) 
100 50 200 
A empresa CR tem pedreiras em Pinhel, Arouca e Portalegre, com a 
seguinte produção diária de inertes. 
 Portalegre Arouca Pinhel 
Produção 
de inertes 
(m3/dia) 
140 110 100 
 
O custo dos próprios inertes e o custo de transporte entre a pedreira e 
a obra estão representados no quadro seguinte: 
 
IO - Aulas TP 
Página | 46 
 
 
 
Custo de transporte (€/m3) (incluindo os custos de 
aquisição do inerte) 
 Porto Coimbra Lisboa 
Portalegre 4 3 3.2 
Arouca 2.2 2.4 3.4 
Pinhel 2.2 2.5 3.6 
 
Formule este problema como um problema de programação linear e como um problema de transporte. Resolva 
o problema de transporte. 
 
Formulação como problema de Programação Linear 
Variáveis de Decisão: 
Xij – quantidade de inerte transportado de i para j (m3) 
i – 1. Portalegre, 2. Arouca. 3. Pinhel 
j – 1. Porto, 2. Coimbra, 3. Lisboa 
 
Minimizar 𝒛 = 𝟒𝒙𝟏𝟏 + 𝟑𝒙𝟏𝟐 + 𝟑. 𝟐𝒙𝟏𝟑 + 𝟐. 𝟐𝒙𝟐𝟏 + 𝟐. 𝟒𝒙𝟐𝟐 + 𝟑. 𝟒𝒙𝟐𝟑 + 𝟐. 𝟐𝒙𝟑𝟏 + 𝟐. 𝟓𝒙𝟑𝟐 + 𝟑. 𝟔𝒙𝟑𝟑 
Sujeito às seguintes restrições: 
𝑥11 + 𝑥12 + 𝑥13 = 140 
 𝑥21 + 𝑥22 + 𝑥23 = 110 
 𝑥31 + 𝑥32 + 𝑥33 = 100 
𝑥11 + 𝑥21 + 𝑥31 = 100 
 𝑥12 + 𝑥22 + 𝑥32 = 50 
 𝑥13 + 𝑥23 + 𝑥33 = 200 
𝑥𝑖𝑗 ≥ 0 
 
Formulação como problema de Transportes 
 Porto Coimbra Lisboa 
Portalegre 
4 3 3.2 
140 
Arouca 
2.2 2.4 3.4 
110 
 
Pinhel 
2.2 2.5 3.6 
100 
 
 100 50 200 350 
 
 
 
O
fe
rt
a
 
P
ro
c
u
ra
IO - Aulas TP 
Página | 47 
 
 
Resolução como problema de Transportes 
1º Encontrar a solução básica inicial 
Ao contrário da resolução pelo método simplex, a resolução pelo algoritmo de transportes não começa na origem do 
sistema de eixos (se assim fosse todas as variáveis seriam nulas, já que o problema de transportes não usa variáveis 
adicionais para além das variáveis de decisão). Em alternativa, escolhe-se uma qualquer solução básica admissível 
(SBA) do problema para iniciar a sua resolução. Uma solução é básica e admissível se cumprir todas as restrições do 
problema e se tiver o número correto de variáveis básicas (VB). Um problema de Transportes tem tantas VBs como 
o número de restrições menos uma. Na resolução pelo método simplex um problema tem tantas VBs como restrições 
mas no problema de transportes uma das restrições é redundante, sendo, portanto, o número de variáveis básicas 
igual ao número de restrições menos 1 (condição necessária e suficiente para que um problema de transportes tenha 
solução admissível). 
Regra do Custo Mínimo 
(um de entre os diversos métodos que existem para encontrar uma SBAinicial) 
 
 Porto Coimbra Lisboa 
Portalegre 
4 3 3.2 
 
140 0 
 140 
Arouca 
2.2 
 
2.4 
 
3.4 
110 10 0 
 100 10 
Pinhel 
2.2 2.5 
 
3.6 
 
100 60 0 
 40 60 
 100 
0 
50 
40 
0 
200 
60 
0 
 
SBAinicial (0,0,140,100,10,0,0,40,60); Z=3.2*140+2.2*100+2.4*10+2.5*40+3.6*60=1008 
 
OU 
 
 Porto Coimbra Lisboa 
Portalegre 
4 3 3.2 
 
140 0 
 140 
Arouca 
2.2 2.4 
 
3.4 
 
110 60 0 
 50 60 
Pinhel 
2.2 2.5 3.6 
 
100 0 
 100 0 
 100 
0 
50 
0 
200 
60 
0 
 
Solução Degenerada (VBs com valor nulo) 
SBAinicial (0,0,140,0,50,60,100,0,0); Z=3.2*140+2.4*50+3.4*60+2.2*100+3.6*0=992 
 
 
1º 
 
 
 
 
2º 
3º 
4º 
5º 
 
1º 
 
 
 
2º 
 4º 
3º 
5º 
IO - Aulas TP 
Página | 48 
 
 
2º Verificar se a SBA é ótima 
Aqui não podemos usar os coeficientes da função objetivo pois os coeficientes presentes na tabela são apenas válidos 
para o sistema de equações quando se começa a resolver o problema na origem do sistema de eixos. Assim, no 
problema de transportes recorre-se ao problema Dual e aos Teoremas da Dualidade para encontrar os coeficientes 
da função objetivo em cada iteração – os chamados custos reduzidos (𝑐𝑖𝑗̅̅ ̅). Para mais detalhes sobre a Dualidade ver 
secção 3 - Teoremas da Dualidade) 
 
 
Para as VB: 𝑢𝑖 + 𝑣𝑗 = 𝑐𝑖𝑗 
VB 
(arbitrando v3=0) 
x13 𝑢1 + 𝑣3 = 𝑐13 = 3,2 => u1=3,2 
x22 𝑢2 + 𝑣2 = 𝑐22 = 2,4 => v2=-1 
x23 𝑢2 + 𝑣3 = 𝑐23 = 3,4 => u2=3,4 
x31 𝑢3 + 𝑣1 = 𝑐31 = 2,2 => v1=-1,4 
x33 𝑢3 + 𝑣3 = 𝑐33 = 3,6 => u3=3,64 3 3.2 
u1=… 140 
2.2 2.4 3.4 
u2=… 
 50 60 
2.2 2.5 3.6 
u3=… 
 100 0 
v1=… v2=… v3=… 
Dualidade no Problema de Transportes 
Usamos a dualidade para calcular o valor dos coeficientes da função objetivo em cada iteração (𝑐𝑖𝑗̅̅ ̅). 
Com, cij – coeficiente na função objetivo original 
 
Formulação do Problema Dual do Problema de Transportes: 
Max z = ∑ ai ∗ ui
m
i
+ ∑ bj ∗ vj
n
j
 
Sujeito a: 
ui + vj ≤ cij para todos os i= 1,…,m e j=1,…,n 
 
Escrevendo a restrição na forma normal ou estandardizada ou aumentada fica: 
 ui + vj + sij = cij com sij sendo a variável de folga do problema dual 
 
Pelos Teoremas da Dualidade sabemos que: 
sij = cij 
Por isso, 
• Para as VB’s (𝒙𝒊𝒋 ≥ 𝒐): como os seus coeficientes na função objetivo em cada iteração do problema 
primal são nulos (𝑐𝑖𝑗=0), então as variáveis de folga das restrições correspondentes do problema dual 
são nulas (sij=0), logo: 
o 𝑢𝑖 + 𝑣𝑗 = 𝑐𝑖𝑗 
o conhecendo o cij (coeficiente na função objetivo original) de cada VB podemos construir um 
sistema de equações para o cálculo do valor de ui e vj 
• Para as VNB (𝒙𝒊𝒋 = 𝒐): sabendo o valor de ui e vj podemos agora calcular o valor 𝑐𝑖𝑗 de todas as VNB 
o 𝑐𝑖𝑗 = 𝑠𝑖𝑗 = 𝑐𝑖𝑗 − ( 𝑢𝑖 + 𝑣𝑗) 
IO - Aulas TP 
Página | 49 
 
 
OU (calculo direto sem construir o sistema de equações) 
 
Para as VNB: 𝑐𝑖𝑗 = 𝑠𝑖𝑗 = 𝑐𝑖𝑗 − ( 𝑢𝑖 + 𝑣𝑗) 
 
 
 
 
 
 
 
 
Solução não é ótima. 
VBE – x32 
VBS - ? 
 
3º Calcular o quadro da iteração seguinte 
VBS será a primeira VB a anular-se com a entrada da VBE. 
Método para encontrar a VBS – “ciclo do ” 
 
4 3 3.2 
u1=3.2 
2.2 0.8 0 140 
2.2 2.4 3.4 
u2=3.4 
0.2 0 50- 0 60+ 
2.2 2.5 VBE 3.6 VBS 
u3=3.6 
0 100 -0.1 + 0 0- 
v1=-1,4 v2=-1 v3=0 
 = min - = {50,0}=0 => VBS x33 
 
Quadro da 2ª iteração 
 
4 3 3.2 
u1=3.2 
2.1 0.8 0 140 
2.2 2.4 3.4 
u2=3.4 
0.1 0 50 0 60 
2.2 2.5 3.6 
u3=3.5 
0 100 0 0 0.1 
v1=-1,3 v2=-1 v3=0 
Solução ótima 
Solução: x13=140, x22=50, x23=60, x31=100, restantes xij=0; Z=992 
4 3 3.2 
u1=3.2 
2.2 0.8 0 140 
2.2 2.4 3.4 
u2=3.4 
0.2 0 50 0 60 
2.2 2.5 3.6 
u3=3.6 
0 100 -0.1 0 0 
v1=-1,4 
 
v2=-1 
 
v3=0 
(arbitrado) 
 
IO - Aulas TP 
Página | 50 
 
 
 
Resolução da SBA inicial alternativa 
 
1ª Quadro
ui
4 3 3,2 0
2,1 0,9 0 140
2,2 2,4 − 3,4 + 0,3
0 100 0 10 -0,1
2,2 2,5 + 3,6 − 0,4
-0,1 0 40 0 60
vi 1,9 2,1 3,2
Solução: x13=140; x21=100; x22=10; x32=40; x33=60
Solução não é optima (há taxas de crescimento negativas
VBE - x23
VBS - ? min - =10 VBS - x22  = 10
2º Quadro
ui
4 3 3,2 0
2 0,9 0 140
2,2 − 2,4 3,4 + 0,2
0 100 0,1 0 10
2,2 + 2,5 3,6 − 0,4
-0,2 0 50 0 50
vi 2 2,1 3,2
Solução: x13=140; x21=100; x23=10; x32=50; x33=50
Solução não é optima (há taxas de crescimento negativas)
VBE - x31
VBS - ? min - =50 VBS - x33  = 50
3º Quadro
ui
4 3 3,2 0
2 0,7 0 140
2,2 − 2,4 + 3,4 0,2
0 50 -0,1 0 60
2,2 + 2,5 − 3,6 0,2
0 50 0 50 0,2
vi 2 2,3 3,2
Solução: x13=140; x21=50; x23=60; x31=50; x32=50
Solução não é optima (há taxas de crescimento negativas)
VBE - x22
VBS - ? min - =50 VBS - x21  = 50
3º Quadro
ui
4 3 3,2 0
2,1 0,8 0 140
2,2 2,4 3,4 0,2
0,1 0 50 0 60
2,2 2,5 3,6 0,3
0 100 0 0 0,1
vi 1,9 2,2 3,2
Solução: x13=140; x22=50; x23=60; x31=100; x32=0
Solução optima
Há uma solulção alternativa
SoluçãoAlternativa: x13=140; x21=0; x22=50; x23=60; x31=100
IO - Aulas TP 
Página | 51 
 
 
 
4.4 Problema de Afetação 
“The best person for the job” (TAHA, 1997) 
O Problema de Afetação é um caso particular do Problema de Transportes, em que a oferta em cada origem (ai) e a 
procura em cada destino (bj) assumem valor unitário e o custo de afetação de uma origem/indivíduo a um 
determinado destino/tarefa é dado por cij. A afetação de um indivíduo a uma tarefa é dada por xij tal que xij é nula 
quando o indivíduo i não é afetado à tarefa j e unitária quando o indivíduo i é afetado à tarefa j. 
 
 
Modelo Matemático 
Min z = ∑ ∑ cij ∗ xij
n
j
m
i
 
Sujeito a: 
Para todas as origens m 
∑ xmj = 1
n
j
 
Para todos os destinos n 
∑ xin = 1
m
i
 
Restrições de não negatividade para todas as variáveis (todas as variáveis são não negativas e inteiras) 
xij ∈ {0,1} 
 
Estes problemas de programação linear são ideais, por exemplo, para formular situações em que existe um certo 
número de operários a afetar ao desempenho do mesmo número de tarefas (um operário por cada tarefa). 
Assim, se xij=1, o operário i efetua a tarefa j, e se xij=0 o operário i não efetua a tarefa j. 
Se representarmos por cij o tempo que o operário i demora a desempenhar a tarefa j, o objetivo consiste em 
distribuir as tarefas pelos operários, de forma a que a soma dos tempos por eles despendidos seja mínima. Os 
problemas de afetação podem, como é evidente, ser tratados como problemas de transportes. 
No entanto, é mais eficiente usar o algoritmo designado por “método húngaro”. 
 
A ideia fundamental que serve de base ao método húngaro é a seguinte: 
não se modificam a ou as soluções ótimas de um problema de afetação diminuindo ou aumentando de um mesmo 
valor todos os elementos de uma dada linha ou de uma dada coluna da matriz de custos (embora o valor ótimo da 
função objetivo seja alterado). 
 
Sejam, então, pi e qj as constantes subtraídas da linha i e da coluna j, respetivamente. Então o elemento de custos 
cij muda para: 
cij’ = cij – pi - qj 
Usando os coeficientes cij’ na função objetivo obtêm-se os mesmos valores ótimos para xij do que quando se usa cij: 
 
IO - Aulas TP 
Página | 52 
 
 
 
 
Assim torna-se possível usar o Método Húngaro apresentado de seguida. 
Método Húngaro para a resolução de Problemas de Afetação 
(passos elementares) 
1. Formular o problema através de um quadro de afetação. As linhas correspondem a origens e as colunas 
correspondem a destinos. 
2. Num problema de minimização (maximização), identificar o valor mínimo (máximo) de cada linha. Subtrair esse 
valor a todos os elementos da linha respetiva. 
3. Para o quadro resultante do ponto 2, identificar o valor mínimo (máximo) de cada coluna e subtraí-lo a todos 
os elementos da coluna respetiva. 
4. A afetação ótima está associada aos elementos nulos do quadro calculado no ponto 3. 
5. Se o quadro calculado no ponto 3 não produzir uma solução ótima admissível (i.e., não é possível preencher 
todas as tarefas tendo em conta apenas as células nulas), realizar os seguintes passos adicionais: 
a. Desenhar o mínimo número de linha verticais e horizontais (de lés a lés) no quadro obtido em 3 de forma 
a cobrir todas as células com valores nulos. 
b. Identificar o menor (maior) elemento não coberto por essas linhas verticais e horizontais e subtraí-lo a 
todos os elementos não cobertos. A seguir adicioná-lo aos elementos na intersecção de linhas e das 
colunas. 
c. Repetir estes passos até encontrar uma solução ótima admissível (ver definição no ponto 5). 
 
4.5 Problemas convertíveis em Problemas de Transportes / Afetação 
Os problemas convertíveis em problemas de transportes/afetação correspondem a situações que podem ser 
convertidas em Problema de Transportes apesar de na sua génese não cumprirem todas as condições deste problema: 
• Situações em que a procura total excede a oferta total 
o Num problema de afetação a procura excede a oferta quando existem mais origens que destinos 
• Situações em que a oferta total excede a procura total 
o Num problema de afetação a oferta excede a procura quando existem mais destinos que origens 
• Situações em que é impossível abastecer um (ou mais) destino(s) a partir de uma (ou mais) origens 
 
Como fazer a conversão: 
• Procura total excede a oferta total 
o Cria-se uma linha artificial (origem fictícia) com custos nulos ou iguais às penalidades pelos pedidos 
não satisfeitos. 
o Na resolução pelo Método Húngaro tem que se