Testes io

Disponível somente no TrabalhosFeitos
  • Páginas : 45 (11241 palavras )
  • Download(s) : 0
  • Publicado : 25 de abril de 2011
Ler documento completo
Amostra do texto
FREQUÊNCIAS E EXAMES RESOLVIDOS DE INVESTIGAÇÃO OPERACIONAL

LICENCIATURA EM CONTABILIDADE E ADMINISTRAÇÃO

Jorge P. J. Santos Ano lectivo 2004/2005

ÍNDICE
1ª Frequência – 21/05/2005 ................................................................................................................................................ 1 2ª Frequência − 01/07/2005................................................................................................................................................ 9 Exame Época Normal − 19/07/2005................................................................................................................................. 16 Exame Época de Recurso − 13/09/2005........................................................................................................................... 28

1ª Frequência de Investigação Operacional – Contabilidade e Administração (21/05/2005)

Jorge P. J. Santos

INSTITUTO SUPERIOR POLITÉCNICO DE VISEU 1ª Frequência de Investigação Operacional – Contabilidade e Administração Duração: 1h30m 21/05/2005 ____________________________________________________________

____________________________________ 1.Um empregado de segurança pretende transportar valores para algumas agências bancárias durante o dia. O Empregado trabalha numa empresa localizada em Coimbra e as agências a visitar estão localizadas em Mira, Figueira da Foz, Montemor, Tocha e Cantanhede, sendo os custos de deslocação (em u.m.) dados pela seguinte tabela: j i Coimbra Mira Fig. Foz Montemor Tocha Cantanhede Coimbra − 60 60 40 5530 Mira 60 − 50 55 20 25 Fig. Foz 60 50 − 25 30 55 Montemor 40 55 25 − 30 35 Tocha 55 20 30 30 − 25 Cantanhede 30 25 55 35 25 −

O empregado tem por objectivo visitar cada localidade uma só vez e regressar a Coimbra no final. Formule o problema em termos de programação matemática de modo a minimizar a distância percorrida. Resolução: Para começarmos a formular o problema vamos representar aslocalidades Coimbra, Mira, Fig. Foz, Montemor, Tocha e Cantanhede pelos números 1, 2, 3, 4, 5 e 6, respectivamente. É de notar que os percursos para este tipo de problema podem ser representados por grafos da forma 2 1 6 5 3 4

Assim, neste problema as variáveis de decisão podem ser definidas por
⎧1 se a localidade j for visitada imediatamente a seguir à localidade i , xij = ⎨ ⎩0 caso contrárioi,j=1,2,...,6

O problema obriga que imediatamente a seguir a uma localidade i (i=1,2,...,6) o empregado só pode visitar uma outra localidade

1

1ª Frequência de Investigação Operacional – Contabilidade e Administração (21/05/2005)

Jorge P. J. Santos

x12 + x13 + x14 + x15 + x16 = 1 x21 x31 + x32 x41 + x42 + x43 x51 + x52 + x53 + x54 x61 + x62 + x63 + x64 + x65 + x23 + x24 + x25 + x26= 1 + x34 + x35 + x36 = 1 + x45 + x46 = 1 + x56 = 1 =1 ⇔

∑ xij = 1 ,
j =1 j ≠i

6

i = 1,2,...,6

Por outro lado, imediatamente antes de uma localidade j (j=1,2,...,6) o empregado visitou apenas uma outra localidade x21 + x31 + x41 + x51 + x61 = 1 x12 x13 + x23 x14 + x24 + x34 x15 + x25 + x35 + x45 x16 + x26 + x36 + x46 + x56 + x32 + x42 + x52 + x62 = 1 + x43 + x53 + x63 = 1 + x54 + x64= 1 + x65 = 1 =1 ⇔

i =1 i≠ j

∑ xij = 1 ,

6

j = 1,2,...,6

Os dois conjuntos de restrições que acabamos de descrever não são suficientes, pois não evitam subpercursos da forma 2 1 6 5 3 4

Esta solução satisfaz as restrições que acabamos de introduzir e não é claramente um percurso válido para o empregado de segurança. Portanto há que introduzir novas restrições que evitem aexistência de subpercursos entre p localidades, com p < 6. Uma forma de evitar subpercursos é obrigar que o número de ligações entre quaisquer p localidades, com p < 6, seja inferior ou igual a (p−1). Se S é um subconjunto de {1,2,...,6} com |S| elementos, as restrições podem ser escritas da seguinte forma

i∈S j∈S j ≠i

∑ ∑ xij ≤ |S| − 1

para todo o conjunto S ⊂ {1,2,...,6} tal que 2 ≤ |S| ≤ 6...
tracking img