Métodos de Apoio à Decisão
Investigação Operacional I
e
Métodos Quantitativos e Restrições

Ana Paula Tomás
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto


19/09/2006
Objectivos da disciplina. Critérios de avaliação. Formulação de modelos matemáticos para problemas de decisão: exemplos. Sistemas de unidades e dimensões; análise dimensional de equações.

21/09/2006
Formulação de modelos matemáticos para problemas de decisão (cont).

3/10/2006
Formulação de modelos matemáticos para problemas de decisão (cont).

10/10/2006
Introdução à Programação (Lógica) por Restrições: variáveis, domínios e restrições. Conjunto de restrições: consistência, simplificação, resolução. CLP(R): comparação com Prolog, interpretação de termos, domínios de variáveis, restrições em suspenso, execução eventualmente bem sucedida. Projecção de restrições lineares segundo variáveis da query.
Módulos de programação por restrições clp(q), clp(r) e clp(fd) nos sistemas Yap Prolog, GNU Prolog e SICStus Prolog
Exemplos de programas.

12/10/2006
Continuação da aula anterior. Formulação de modelos para problemas de decisão e sua resolução usando módulos de programação por restrições no sistema SICStus Prolog. Introdução à propagação de restrições nos sistemas de CLP(FD): consistência do domínio (domain-consistency), consistência por arcos (arc-consistency) e consistência dos limites dos intervalos que definem os domínios da variáveis (bounds-consistency). Restrição de indexação (element) em clpfd.

17/10/2006
Conclusão da aula anterior.
Introdução à Programação Linear: solução admissível, valor óptimo, solução óptima e soluções óptimas alternativas; redução de problemas à forma padrão por introdução de variáveis de desvio; resolução de problemas no plano e espaço por análise geométrica.

19/10/2006
Resolução de problemas de optimização linear pelo Método Simplex. Soluções básicas e vértices do espaço de solução: possibilidade de várias bases determinarem o mesmo vértice (se corresponder a solução básica degenerada). Método Simplex (supondo dada solução básica admissível inicial). Análise dos indicadores de variação da função objectivo. Verificação de optimalidade. Melhoramento de solução por pivotagem.

24/10/2006
Método Simplex (cont).

26/10/2006
Método Simplex: determinação duma solução básica admissível inicial; introdução de variáveis artificiais e ideia do método das duas fases; verificação da inconsistência dum sistema usando o método Simplex. Referência à complexidade exponencial do método Simplex, no pior dos casos, e à existência de métodos polinomiais.

31/10/2006
Problema de Transporte. Introdução de destinos e origens fictícias para equilibrar problemas. Regras para determinação duma solução inicial: canto noroeste; mínimo por linha ou por coluna. Resolução do problema de transporte: método stepping stone. Propriedades da matriz de coeficientes.

2/11/2006
Problema de Transporte. Método uv para determinação dos indicadores. Justificação da correcção.

7/11/2006
Análise de problemas em redes. Determinação de caminhos de comprimento mínimo (i.e., cuja soma dos valores nos arcos do caminho é mínima). Determinação de caminhos de capacidade máxima (i.e., com maior valor mínimo nos arcos do caminho). Determinação do caminho de comprimento máximo em grafos dirigidos acíclicos. Introdução às redes de actividades.

9/11/2006
Redes de actividades: actividades e dependências, planeamento sem partilha de recursos, duração do projecto, caminho crítico. Modelos "nó-actividade" e "arco-actividade". Actividades fictícias. Acontecimentos (acontecimento inicial e final). Determinação da caminhos críticos (CPM). Datas mais próximas e mais afastadas para acontecimentos. Datas de início mais próximas e mais afastadas (ou mais tardias) para cada tarefa. Folgas totais e folgas livres. Breve referência a casos com durações não exactas.
Modelo de optimização linear para o problema e sua tradução por programa usando clpfd. Propagação de restrições do tipo X <= Y+const : efeitos da imposição de consistência (local) nos extremos dos domínios das variáveis X e Y.

14/11/2006
Introdução aos problemas de fluxo. Caminhos de capacidade máxima e de capacidade miníma. Determinação de fluxo máximo: ideia do método de Ford-Fulkerson (grafo residual associado a fluxo, caminho para aumento, novo fluxo, optimalidade da solução). Corte. Capacidade dum corte. Teorema de Ford-Fulkerson. Prova do Teorema de Ford-Fulkerson. Identificação do corte de capacidade mínima por análise da rede residual depois de determinado um fluxo máximo.

16/11/2006
Problemas de fluxo. Modelo matemático do problema de maximização do fluxo numa dada rede.
Problema do emparelhamento máximo em grafos bipartidos como problema de fluxo máximo.
Problemas de emparelhamento em grafos bipartidos com preferências e prioridades.

21/11/2006
Problemas de emparelhamento em grafos bipartidos com preferências mútuas estritamente ordenadas: algoritmo de Gale-Shapley para determinação de emparelhamentos estáveis.
Atribuição de candidatos a postos de trabalho: determinação de emparelhamentos estáveis quando os candidatos estão estritamente ordenados, podem manisfestar igual preferências por alguns postos e há candidatos que têm direito a certos lugares (caso não consigam nenhum outro). Relação deste problema com o Problema de Colocação de Professores em Portugal.

23/11/2006
Problemas de afectação com pesos (custos): minimização do peso global; método húngaro (de Kuhn-Munkres); redução dum problema de maximização do peso global (lucro global) a um problema de minimização.

28/11/2006
Programação inteira e mista. Relaxação linear. Introdução de variáveis 0/1 para modelação de disjunções. Método da procura em árvore (branch-and-bound) para programação inteira.

30/11/2006
Problemas de satisfação de restrições que apresentam simetria: eliminação de soluções simétricas (equivalentes) por inserção de restrições adicionais e por reformulação do modelo. Exemplos.

5/12/2006
Programação Dinâmica. Obtenção de soluções partindo da situação inicial (análise para a frente). Exemplos: reforma de agricultor; jogo .

7/12/2006
Programação Dinâmica: obtenção de soluções por análise para trás. Exemplo: valor esperado para venda de casa.
Exemplos de modelos para problemas de optimização combinatória. Definição de restrições simbólicas (globais) no módulo clpfd: exemplo lex_leq (lexicograficamente menor ou igual). Problemas com simetrias inerentes (ex., geração de polígonos): interesse e vantagens da sua exploração.

12/12/2006
Introdução às Cadeias de Markov. Transições entre estados de um sistema e probabilidades a elas associadas. Probabilidades estacionárias. Cadeias de Markov regulares e pontos fixos. Análise a longo prazo.
Introdução à análise de filas de espera: modelos markovianos.

14/12/2006
Introdução à análise de filas de espera: modelos markovianos M/M/1, M/M/S, M/M/S/L; condições de estabilidade; exemplos.