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


17/9/2004
Objectivos da disciplina. Critérios de avaliação. Alguns exemplos de programas simples em Prolog.

22/9/2004
Formulação de modelos matemáticos para problemas de decisão: exemplos.
Sistemas de unidades e dimensões; análise dimensional de equações.

24/9/2004
Formulação de modelos matemáticos para problemas de decisão (cont).

29/9/2004
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.

1/10/2004
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.

6/10/2004
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. Ideia do 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.

8/10/2004
Resolução de sistemas de equações lineares: método de eliminação de Gauss-Jordan, caracterização das soluções do sistema, soluções básicas e mudanças de base de representação do conjunto solução (revisão).
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.
Soluções degeneradas: existência de técnicas para garantir terminação. Referência à complexidade exponencial do método Simplex, no pior dos casos, e à existência de métodos polinomiais.
Interpretação geométrica do método no plano.

13/10/2004
Interpretação geométrica do método Simplex no plano (concl.).
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).
Quadro do simplex: representação matricial do problema, análise das transformações do quadro.
Introdução à pós-optimização: análise de sensibilidade a variações de recursos.

15/10/2004
Breve introdução à dualidade e pós-optimização: pares primal-dual, estimativa do valor óptimo do primal por análise de soluções admissíveis do dual e interpretação económica da dualidade, análise de sensibilidade a variações de custos e de recursos.

20/10/2004
Casos particulares de Programação Linear: Problema de transporte. Problema bem equilibrado: 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. Métodos de resolução do problema de transporte: método stepping stone e método uv .

22/10/2004
Propriedades matemáticas da matriz de coeficientes do Problema de Transporte.

27/10/2004
Propriedades matemáticas da matriz de coeficientes do Problema de Transporte (concl.)
Problema de transporte como problema de optimização em grafos/redes. Outros problemas em grafos e redes.
Revisão de alguns algoritmos em grafos: determinação do caminho minímo (algoritmo de Dijkstra, algoritmo de Floyd); determinação da árvore de suporte mínima (algoritmos de Prim e Kruskal).

29/10/2004
Análise de problemas em redes sobre caminhos e árvores de suporte.
Introdução às redes de actividades: actividades e dependências, planeamento sem partilha de recursos, duração do projecto, caminho crítico. Modelo nó-actividade. Determinação de caminhos máximos em DAGs (grafos dirigidos acíclicos).

3/11/2004
Redes de actividades (sem partilha de recursos). Modelo "arco-actividade". Actividades fictícias. Acontecimentos (acontecimento inicial e final). Determinação da caminhos critícos (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.
Modelo de optimização linear para o problema e sua tradução por programa usando clpfd.

5/11/2004
Redes de actividades (concl): breve referência a casos com durações não exactas (durações optimista, pessimista e mais frequente; valor esperado e variância para a duração de cada tarefa; durações independentes para as tarefas e distribuição normal para duração dum caminho critíco).
Modelo linear para problemas com custos. Custo da redução da duração das actividades. Soluções com custo mínimo.
Exemplos de problemas em redes. 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).

10/11/2004
Determinação do fluxo máximo numa rede (concl): método de Ford-Fulkerson; prova da correcção (cortes, capacidade dum dado corte, fluxo na rede e fluxo num corte, teorema de Ford-Fulkerson).
Modelo matemático do problema de maximização do fluxo numa dada rede.
Problema do emparelhamento máximo como problema de fluxo máximo.

12/11/2004
Problemas de afectação: problema de emparelhamento máximo com custo mínimo; método húngaro.

17/11/2004
Programação inteira: modelos de problemas (MIP, IP, BIP); relaxação linear; ramificar-limitar (branch-and-bound); inserção de novas restrições (cortes de Gomory).

19/11/2004
Continuação da aula anterior. Formulação de modelos para problemas de cortes.

24/11/2004
Problema da mochila (``knapsack'') linear, 0/1, inteiro: solução obtida por estratégia ambiciosa/gulosa (``greedy'') e solução óptima. Estratégias para enumeração no módulo clpfd (ex, down ).
Programação Dinâmica. Problemas determinísticos e probabilísticos. Obtenção de soluções partindo da situação inicial (análise para a frente) ou das situações finais (análise para trás).

26/11/2004
Programação por restrições: formas diferentes de consistência (parcial): 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).
Eliminação de soluções simétricas (equivalentes). 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.
Formulação de modelos matemáticos para problemas de satisfação de restrições e optimização.

3/12/2004
Formulação de modelos matemáticos para problemas de optimização combinatória: exploração das propriedades matemáticas da matriz do problema de transporte na análise e definição dum modelo para um problema de optimização de postos de contagem de tráfego em intersecções urbanas. Modelos aproximados (enfraquecimento de restrições complexas, necessidade de testar "soluções" encontradas).

10/12/2004
Análise de problemas de substituição de equipamento.

15/12/2004
Introdução à análise de filas de espera: modelos markovianos.

17/12/2004
Relação de variantes do problema dos "casamentos estáveis" (stable marriage problem ) com o problema da colocação de professores: solução única obtida em tempo polinomial quando as preferências definem relação de ordem total; preferências com indiferença --- complexidade NP.