Investigação Operacional I

IDENTIFICAÇÃO

Disciplina: Métodos Determinísticos de Investigação Operacional
Cursos: Engª Informática
Ano Lectivo: 2007/08
Escolaridade: 2T+2TP
Docentes: J. M. Valério de Carvalho - (T – 5ªf, 11-13)
Pedro Chaves (TP1 – 2ªf., 09-11 h)

Pedro Chaves (TP2 – 2ªf., 11-13 h)

Pedro Chaves (TP3 – 2ªf., 14-16 h)

Pedro Chaves (TP4 – 6ªf., 14-16 h)
Departamento: Produção e Sistemas
Escola: Engenharia

ANÚNCIOS

-Classificações do ExameMeioSemestre (mesma password que a dos apontamentos)

Sessão de dúvidas para exame de recurso: dia 11 de Fevereiro (segunda-feira), das 10:00-11:00, sala da aula teórica

(Aviso afixado em 31 jan 08)

-Classificações do ExameFimSemestre e Finais (mesma password que a dos apontamentos)

Classificações do ExameRecurso e Finais (mesma password que a dos apontamentos)

ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ

Classificações do Exame de recurso de Investigação Operacional I (LESI)

42060 - Luis Ricardo Gonçalves Teixeira – R

38202 - Hugo Filipe Nascimento Pereira - 10

19751 - Renato Isaias Rodrigues Portela - 10

1480 - Maria Paula Cardoso Maia - 10

42235 - José Miguel Carvalho Magalhães - D

35286 - Bruno Simão Dias – D

- JOSÉ CARLOS CARVALHO DOS SANTOS - R

ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ

OBJECTIVOS

- apresentar a Metodologia da Investigação Operacional

- apresentar um conjunto das técnicas mais utilizadas, seleccionadas tendo em consideração:

- a relevância para a formação

- o tempo e esforço dispendido pelos alunos na sua apreensão,

- o desenvolvimento da capacidade para a sua aplicação na solução de problemas reais.

- transmitir o 'conceito-filosofia' de modelação e optimização, através do estudo das técnicas seleccionadas.

RESULTADOS DE APRENDIZAGEM

- Desenvolver a capacidade de resolução de problemas (modelos determinísticos), com ênfase em problemas de engenharia de sistemas.

- Conhecer as técnicas e os métodos de Investigação Operacional apresentados na disciplina, e ser capaz de os aplicar na resolução de instâncias de problemas de pequena dimensão.

- Desenvolver a capacidade de analisar sistemas complexos, de criar modelos para os descrever, de obter soluções para esses modelos utilizando programas computacionais adequados, de validar os modelos obtidos, de interpretar as soluções obtidas, e de elaborar recomendações para o sistema em análise.

- Compreender a importância da avaliação das soluções, e ser capaz de realizar análises de sensibilidade.

PROGRAMA
DETALHADO

1. Programação Matemática
Modelos e sua estrutura. Disponibilidade de dados. Óptimo e Função Objectivo. Simplificação de Modelos. Programação Linear, Aspectos geométricos, Método Simplex, Método do M, Técnica das Duas Fases, Revisão do Método Simplex. Modelos de Transporte, Análise de Optimabilidade, Regra do Canto NW, Regra do Custo Mínimo, Método da 'Steping Stone', Método dos Multiplicadores. Programação Linear Avançada, Combinação Convexa, Conjunto Convexo, Solução óptima para o problema de programação linear. Teoremas da Programação Linear. Análise de Sensibilidade, Variações nos coeficientes da função objectivo, e das restrições, Preço Sombra. Teoria da Dualidade, Definição de Primal e de Dual. Método Simplex-Dual. Justificação do Método dos Multiplicadores do Modelo de Transportes. Modelos Particulares de Transportes, Transbordo, Depósitos intermédios, Selecção de Meios de Transporte, Transporte com Limites Superiores às quantidades, Modelo 'Aircraft Routing' (Problema de Transportes Generalizado), Programação Paramétrica, Custo variável, Disponibilidade variável. Programação Inteira, Método "Branch & Bound", Corte Fraccional, Cortes Mistos. Modelos de Programação Inteira, Custo Fixo, Planeamento da Produção, Dicotomias, Dimensão de Lote. Tipos especiais de Função Objectivo, Minimax, Função tipo Razão. Programação Quadrática, Condições de Kuhn Tucker, Convexidade e Concavidade. Construção e aplicação de um quadro simplex modificado.

2. Programação Dinâmica - Modelos Determinísticos
Definições e terminologia. Rêde de Políticas, Estágio, Estado, Contribuição de Estágio, Acção, Política. Formulação admissível e formulação impossível. Relação de Recorrência. Condições de Validade em Programação Dinâmica (separabilidade e optimabilidade). Verificação das Condições de Validade para problemas com Contribuições Aditivas, Multiplicativas e Descontadas. Problemas MAXIMIN. Redução da Carga Computacional em Programação Dinâmica.

MATÉRIA TEÓRICO-PRÁTICA

As aulas Teórico-Práticas centram-se no apoio/acompanhamento de exercícios propostos. Os exercícios propostos cobrem os assuntos apresentados nas aulas teóricas, e procuram constituir uma preparação dos alunos para a interpretação dos enunciados, definição dos modelo e sua execução.

BIBLIOGRAFIA

- Apontamentos de Investigação Operacional, Modelos Determinísticos, António Guimarães Rodrigues, Reprografia da UMinho
- Jorge Guerreiro, Alípio Magalhães, Manuel Ramalhete, Programação Linear (Volumes I e II), Mc Graw-Hill Portuguesa
- Harvey M. Wagner, Principles of Operations Research, Prentice Hall
- Hamdy Taha, Operations Research - An Introduction, Collier MacMillan International Editions
- N.A.J.Hastings, Dynamic Programming with Management Applications, Butterworths

- Slides:

- método simplex,

- degenerescencia + método grande m,

- método das 2 fases,

- modelos de programação linear,

- transportes,

- transportes com limites superiores,

- sensibilidade e dualidade,

- introdução de programação inteira,

- aplicações de io,

- Exercícios: 1

AVALIAÇÃO

Os elementos de avaliação da disciplina são os seguintes:

- Três Trabalhos Práticos de modelação de um problema, e sua resolução com um package de software (com guia de utilização):
   1. Problema de corte (data de entrega - 25 out.*)
   2. Problema de produção-inventário (data de entrega - 29 nov.*)
   3. Puzzles (data de entrega - 10 jan.*)

- Um Exame Meio Semestre

- Um Exame Final

* A entrega deverá ser feita no início da aula teórica do dia indicado.

A classificação final da disciplina é obtida por arredondamento do valor de Cf, calculado do seguinte modo:

Cf = 0.3 Ce1 + 0.4 Ce2 + 0.1 Ct1 + 0.1 Ct2 + 0.1 Ct3,

sujeitos às seguintes restrições:

Ce1 >= 40%,
Ce2 >= 40%,
Ct1 >= 50%, Ct2 >= 50%, Ct3 >= 50%,

sendo

Ce1 – a classificação do exame meio-semestre,
Ce2 - a classificação do exame final,
Cti – a classificação do trabalho i, i=1,2,3

Exame:

O exame inclui a resolução de três ou quatro problemas propostos, num período de 2 horas; é realizado com consulta apenas dos Apontamentos da disciplina.
A admissão a exame está condicionada à presença em, pelo menos, 2/3 das actividades lectivas efectivamente realizadas (T e TPs).
A frequência obtida num ano lectivo anterior não dispensa um aluno reprovado da frequência das aulas no ano lectivo corrente.

Trabalhos:

Os trabalhos devem ser realizados em grupos de 4 alunos, excepcionalmente 3.
O relatório de cada trabalho prático deve traduzir a experiência de modelização e resolução dos casos propostos, conter as peças requeridas na lista dos trabalhos, estar bem estruturado, e apresentar toda a informação necessária à sua avaliação.
No entanto, não é desejável que o aluno perca muito tempo com aspectos como a “qualidade de apresentação gráfica” do relatório, que não são valorizados. Ele pode ser elaborado com processador de texto ou manuscrito, ou uma combinação dos dois formatos.
O relatório deve ser feito em folhas formato A4, ter uma folha de capa com a identificação do(s) aluno(s), do trabalho e da data, devendo o conjunto ser agrafado no canto superior esquerdo.
A classificação obtida nos trabalhos num ano lectivo anterior não dispensa um aluno reprovado da realização dos trabalhos no ano lectivo corrente.
Será atribuída a classificação de 0 valores a todos os trabalhos realizados de uma forma fraudulenta. De acordo com o definido na nº 4 do Artº 6 do RIAPA, a classificação final dos alunos envolvidos nessas situações será “não admitido”. Essa classificação final será atribuída quer a fraude seja detectada antes ou depois da realização do exame da disciplina.

Calendário:

Semana	Data Teórica	teóricas	teórico-práticas
1	20-Set
2	27-Set
3	04-Out
4	11-Out
5	18-Out
6	25-Out	t1
7	feriado
8	08-Nov
9	15-Nov	exame 1	(a realizar no dia 17 de Novembro (sábado), conforme calendário da Direcção de Curso
10	22-Nov
11	29-Nov	t2
12	06-Dez
13	13-Dez
14	20-Dez
15	ferias
16	ferias
17	10-Jan	t3
18	17-Jan
19	24-Jan	exame 2	aval trab
20	31-Jan	aval. Ensino	aval trab

LINKS

Utilidades:
- Associação Portuguesa de Investigação Operacional
- Institute for Operations Research and the Management Sciences
- EstudIO (Estudantes de Investigação Operacional) - tem tutoriais em português
- Casos de aplicação de Investigação Operacional

Links:
- http://opsresearch.com/
- http://mat.gsia.cmu.edu/
- http://www2.informs.org/Resources/
- http://dir.yahoo.com/Science/Mathematics/Operations_Research