Trabalho G3
Curso
Gestão
Unidade Curricular
Investigação Operacional II
Trabalho G3
Docente:
Mestre Irene Guia Arraiano
Discentes:
Bruna Ribeiro nº 20120903
Márcia Monteiro nº 2011844
Turma:
TGN62
Lisboa, 19 de Maio de 2014
ENUNCIADO
Um jovem português pretende ir de férias para a Austrália, pelo que necessita de adquirir uma viagem de avião de Lisboa para Sydney. No entanto, nenhuma companhia aérea realiza voos diretos entre as duas cidades sendo, por isso, necessário fazer escala numa ou em várias cidades. Após uma pesquisa on-line, o jovem conseguiu elaborar a tabela seguinte, na qual um traço significa uma ligação inexistente e um número o custo do bilhete de avião entre as duas respetivas cidades. Pretende-se saber quais os bilhetes de avião que deverão ser adquiridos pelo jovem de modo a obter a viagem de férias mais barata.
a) Formalize o problema apresentado.
b) Usando o software adequado determine e interprete a solução ótima do problema.
2
RESOLUÇÃO
a) Formalize o problema apresentado.
i DE origem, de Lisboa (1) a Hong Long (6) j PARA destinos de Madrid (1) a Sydney (6)
Lisboa = 1
Madrid = 2
Londres = 3
Paris = 4
Frankfurt = 5
Hong Kong = 6
Sydney = 7
Min Z = 90X11 + 110X12 + 100X13 + 60X22 + 120X24 + 70X33 + 105X34 + 150X35 +
120X45 + 140X55 + 110X56 + 130X66
xij
1, se xij estiver no caminho ótimo
0, se caso contrário
s.a.
X11 + X12 + X13 = 1
(Lisboa)
X22 + X24 = X12
(Madrid)
X33 + X34 + X35 = X12 + X22
(Londres)y
X45 = X13 + X33
(Paris)
X55 + X56 = X24 + X34
(Frankfurt)
X66 = X35 + X45 + X55
(Hong Kong)
X56 + X66 = 1
(Sydney)
xij ∈ { 0,1}
(i,j) ∈ 𝐴
A = {(X12, X13, X14, X25, X23, X34, X35, X36, X46, X56, X57)}
i, j ∈ 𝑉
V = {(1, 2, 3, 4, 5, 6, 7)
3
Interpretação económica
O jovem português, para poder realizar a viagem de férias de Lisboa com destino a
Sydney, de forma mais barata, deverá adquirir o bilhete de avião de Lisboa para Madrid, de seguida para Frankfurt