Objetivos

Investigação Operacional

 

Os principais objetivos desta Unidade Curricular são:

- familiarizar os estudantes com o método de resolução de problemas utilizado pela Investigação Operacional;

- apresentar as técnicas mais relevantes da Investigação Operacional usadas para resolver problemas de engenharia.

No final da Unidade Curricular o estudante de ser capaz de 

- identificar de forma estruturada problemas de decisão/optimização;

- construir modelos de problemas de optimização, e 

- usar algoritmos que produzam soluções óptimas para esses modelos, como suporte para decisões fundamentadas.

 

Programa

Investigação Operacional

 

Capítulo 1 - Introdução à Investigação Operacional

1. Investigação Operacional

2. Modelos de IO

Capítulo 2 - Programação Linear

1. Introdução

1.1. Definição do problema de PL

1.2. Representação gráfica de problemas de PL

1.3. Formalização matemática do PL

1.4. Forma padrão ou "standard" de um problema de PL

1.5. Análise convexa

2. Método SIMPLEX

2.1. Algoritmo de Simplex (problema de maximização)

2.2. Técnica da base artificial

2.2.1. Método do M-Grande (ou das Penalidades)

2.2.2. Método das Duas-Fases

2.3. Problemas de minimização

2.4. Interpretação económica das variáveis "slack" e "surplus"

2.5. Degenerescência e entrada em ciclo (Técnica da Perturbação)

3. Teoria da dualidade

3.1. Definição e formalização do problema Dual

3.2. Algoritmo Dual-Simplex

4. Análise de Pós-optimização

4.1. Alteração dos coeficientes da função objectivo, cij

4.2. Alteração dos termos independentes das restrições, bij

4.3. Alterações dos coeficientes da matriz das restrições, Aij

4.4. Introdução de uma variável

4.5. Introdução de uma restrição

5. Análise de sensibilidade

5.1. Em relação aos coeficientes da função objectivo, c

5.2. Em relação aos termos independentes, b

6. Problema de Transportes

6.1. Definição e formalização do problema

6.2. Obtenção de uma Solução Básica Admissível

6.2.1. Método do Canto Noroeste

6.2.2. Método do Custo Mínimo

6.2.3. Método das Penalidades

6.3. Obtenção da solução óptima

6.4. Degenerescência

6.5. Caso em que a Oferta Total é diferente da Procura Total

7. Problema de Afectação

7.1. Definição e formalização do problema

7.2. Obtenção da solução óptima (algoritmo Húngaro)

7.3. Caso em que o número de Origens é diferente do número de Destinos

Capítulo 3 - Problemas de Fluxo em Redes

1. Conceitos fundamentais de grafos e de redes

2. Problema do caminho mais curto

2.1. Definição

2.2. Determinação da solução óptima utilizando os algoritmos de Dijkstra e de Floyd

3. Árvore abrangente mínima

3.1. Definição

3.2. Determinação da solução óptima utilizando duas versões do algoritmo de PRIM : rotulação e tabela das distâncias/custos

4. Problema de Fluxo Máximo

4.1. Definição

4.2. Determinação da solução óptima utilizando o algoritmo de Ford-Fulkerson

4.3. Definição e determinação do curto mínimo da rede

Capítulo 4 - Programação Linear Multiobjectivo

1. O problema multiobjectivo

2. Métodos de resolução de problemas multiobjectivo

3. Formalização do problema de Programação Linear Multiobjectivo

4. Resolução do problema graficamente

 

Bibliografia

Investigação Operacional

 

"Introduction to Operations Research", 1990

Frederick S. Hillier e Gerald J. Liberman

McGraw-Hill

 

"Programação Linear", Vol. I e II, 1985

Jorge Guerreiro, Alípio Magalhães e Manuel Ramalhete

McGraw-Hill de Portugal

 

"NETWORK FLOWS. Theory, Algorithms and Applications", 1993

Ravindra K. Ahuja, Thomas L. Magnanti e James B. Orlin

Prentice-Hall

 

"Uma Abordagem ao Problema de Caminho Mais Curto Multiobjectivo - Aplicação ao Problema de Encaminhamento em Redes Integradas de Comunicações", 1999

Carlos Manuel Chorro Simões Barrico

Dissertação de Mestrado, Universidade de Coimbra

 

Avaliação

Investigação Operacional

 

Ensino-Aprendizagem

A avaliação é composta por 4 mini-testes escritos, de 45 minutos cada, a serem efectuados nas aulas práticas ou teórico-práticas.

Cada mini-teste vale 5 valores e a matéria para cada um deles é a seguinte :

Mini-teste 1 : Formulação matemática de problemas de PL e Método Simplex

Mini-teste 2 : Análise de pós-optimização e de sensibilidade

Mini-teste 3 : Problemas de Transporte e de Afectação

Mini-teste 4 : Problemas de Fluxo em Redes

Os alunos que obtenham classificação final superior a 16, terão que realizar uma prova suplementar. Caso não o façam, apenas lhes será atribuída a classificação de 16.

Época Normal

A avaliação é composto por uma prova escrita que vale 20 valores.

Época de Recurso

A avaliação é composto por uma prova escrita que vale 20 valores.

 

Datas dos testes

Investigação Operacional

 

Ensino-Aprendizagem

Mini-teste

1470

1605

1968

1808

1

25/10/00

25/10/00

23/10/00

23/10/00

2

15/11/00

15/11/00

20/11/00

20/11/00

3

07/12/00

07/12/00

07/12/00

07/12/00

4

14/12/00

14/12/00

14/12/00

14/12/00

Exames

Exame

Data

Hora

Salas

Normal

25/01/2001

14.30 horas

6.5 - 6.16

Recurso

17/02/2001

14.30 horas

6.5 - 6.9

 

Resultados obtidos nos vários tipos de avaliação

Investigação Operacional

 

Ano letivo 2000/2001 (necessita de senha de acesso)

Matemática/Informática

Trabalhos

Frequência

Aprendizagem

Exame

 

Apontamentos

Investigação Operacional

 

Capítulo 1 - Introdução à Investigação Operacional

Capítulo 2 - Introdução à Programação Linear

Capítulo 3 - Método SIMPLEX

Capítulo 4 - Teoria da dualidade

Capítulo 5 - Análise de Pós-optimização e de Sensibilidade

Capítulo 6 - Problemas de Transportes e de Afectação

Capítulo 7 - Problemas de Fluxo em Redes

Capítulo 8 - Programação Linear Multiobjectivo

Bibliografia

 

Folhas práticas

Investigação Operacional

 

Folha 1 - Resolução gráfica de problemas de Programação Linear

Folha 2 - Modelação matemática de problemas de Programação Linear

Folha 3 - Método Simplex. Teoria da dualidade

Folha 4 - Análise de Pós-Optimização e de Sensibilidade

Folha 5 - Problemas de Transportes e de Afectação

Folha 6 - Problemas de Fluxo em Redes

Folha 7 - Programação Linear Multiobjectivo

Testes (enunciados e correcções)

Ano lectivo

Tipo

Enunciado

Resolução

1997-1998

Frequência

Download

Download

1997-1998

Exame Normal

Download

Download

1997-1998

Exame Recurso

Download

Download

 

 

 

 

1998-1999

Frequência (A)

Download

Download

1998-1999

Frequência (B)

Download

Download

1998-1999

Exame Normal

Download

Download

1998-1999

Exame Antecipação

Download

Download

1998-1999

Exame Recurso

Download

Download

 

 

 

 

1999-2000

Frequência

Download

Download

1999-2000

Exame Normal

Download

Download

1999-2000

Exame Antecipação

Download

Download

1999-2000

Exame Recurso

Download

Download

 

 

 

 

2000-2001

Exame Normal

Download

Download

2000-2001

Exame Recurso

Download

Download

 

Projetos realizados

Investigação Operacional

 

Identificação

Aplicação

Ajuda

Relatório

Algoritmos de Simplex (Primal e Dual)

Download

Download

Download

Análise de pós-optimização e de sensibilidade

Download

Download

Download

Problema de Transportes e de Afectação

Download

Download

Download

Problema de Caminho Mais Curto (Dijkstra)

Download

Download

Download

Problema de Fluxo Máximo (Ford- Fulkerson)

Download

Download

Download