Métodos de Apoio à Decisão

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


19/9/2002
Objectivos da disciplina. Critérios de avaliação.
Formulação de Modelos Matemáticos para problemas de optimização: exemplos.
Sistemas de unidades e dimensões; análise dimensional de equações.

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

26/9/2002
Formulação de modelos matemáticos para problemas de optimização (cont).
Problemas de optimização linear. Resolução no plano e espaço por análise geométrica: espaço convexo constituído pelas soluções; localização das soluções óptimas em vértices ou faces.

1/10/2002
Revisão do método de Gauss-Jordan para resolução de sistemas de equações lineares. Caracterização das soluções básicas de sistemas de equações lineares.
Formulação matemática de problemas de optimização linear. Variáveis de decisão. Introdução de variáveis de desvio (folga) para transformar sistemas de inequações em sistemas de equações: relação entre as soluções de Ax <= b e as de Ax+Is = b, com s >= 0, e I identidade.
Método simplex para resolução de problemas de optimização lineares: variáveis básicas, mudança de base; expressão da função a optimizar como função das variáveis não básicas; caracterização da solução óptima; indicadores.

3/10/2002
Continuação da aula anterior.

8/10/2002
Método simplex revisto: determinação da inversa da matriz constituída pelas colunas na base; actualização da inversa em cada troca de base.

10/10/2002
Optimização Linear (cont). Introdução de variáveis artificiais para determinar uma solução básica admissível. Método das duas fases: Fase I - minimização da soma das variáveis artificiais introduzidas; Fase II - resolução do problema dado, partindo da solução obtida na Fase I.
Informação que se obter por análise da solução óptima da Fase I: inconsistência do problema dado e/ou existência de equações redundantes.

15/10/2002
Casos particulares de Programação Linear: Problema de transporte. Análise de possíveis melhoramentos duma solução básica admissível por troca de base. Aplicação do método stepping stone para resolução de problemas bem equilibrados.

17/10/2002
Não houve aula: DCC-ao-rubro.

22/10/2002
Problemas de transporte (cont).
Problema bem equilibrado (balanceado): 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 .
Propriedades matemáticas da matriz de coeficientes do Problema de Transporte.

24/10/2002
Problema de transporte linear (concl.): Método uv para determinação dos indicadores; propriedades matemáticas da matriz de coeficientes do Problema de Transporte.
Breve referência à análise de sensibilidade da solução óptima de problemas de programação linear e à dualidade.

29/10/2002
Revisão de alguns algoritmos em grafos: determinação do caminho minímo (algoritmo de Dijkstra), determinação da árvore de suporte mínima (algoritmos de Prim e Kruskal).
Introdução às redes de actividades: actividades e acontecimentos, modelos ``arco''-actividade e ``nó''-actividade. Actividades Fictícias, dependências, duração do projecto, caminho crítico.

31/10/2002
Ordenação topólogica dos vértices dum DAG (grafo dirigido acíclico). Algoritmo (de Ford) para determinação do caminho máximo em DAGs. Determinação de caminhos critícos (CPM) em redes de actividades: actividades critícas e folgas. Diagramas de Gantt.
Introdução aos problemas de fluxo. Capacidades máximas dos arcos e fluxo na rede. Modelo matemático do problema de maximização do fluxo numa dada rede. Algoritmo de Ford-Fulkerson para determinação do fluxo máximo: grafo residual; caminhos para aumento de fluxo.

5/11/2002
Problemas de maximização de fluxo (cont.): cortes; capacidade dum dado corte; igualdade do fluxo máximo à capacidade do corte com capacidade miníma; Teorema de Ford-Fulkerson.
Revisão de alguns algoritmos em grafos: determinação do caminho minímo para todos os pares de nós.

7/11/2002
Problemas de afectação. Método Húngaro (de Kuhn). Condições de aplicabilidade. Transformação dum dado problema de afectação noutro equivalente, e que satisfaça as condições de aplicabilidade do método.
Teorema de König.

12/11/2002
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). Resolutores incompletos. Teste de consistência e propagação de restrições: arc-consistency.

14/11/2002
Exemplificação do funcionamento dos módulos de programação por restrições clpr e clpfd no SICStus Prolog.
Alguns aspectos do módulo de clpfd . Definição do domínio das variáveis (restrições in e domain). Definição de restrições aritméticas: operadores relacionais, e restrições sum e scalar_product. Predicados de enumeração: indomain e labeling. Estratégias para enumeração: por defeito, max, bisect, ff (first-fail), down. Predicados para optimização: maximize e minimize. Formas diferentes de consistência (parcial): consistência por arcos (arc-consistency) e consistência dos limites dos intervalos que definem os domínios da variáveis. Restrição element.
Estratégias de procura: "geração e teste" versus "restringir e gerar".
Necessidade de restrições mais complexas: por exemplo, all_diferent. Algoritmos especiais para teste de consistência e propagação dessas restrições.
Problema da mochila (``knapsack'') linear, 0/1, inteiro: solução obtida por estratégia ambiciosa/gulosa (``greedy'') e solução óptima.

19/11/2002
Diferentes modelos matemáticos para um mesmo problema de optimização combinatória: comparação (em termos de eficiência) de implementações desses modelos. Análise de implementações para um problema de corte (eliminação de soluções simétricas).

21/11/2002
Exemplos de problemas de optimização combinatória (cont.)

26/11/2002
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). Exemplos. Exemplo em que não é aplicável: cálculo de x^n com número mínimo de multiplicações.

28/11/2002
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. Exemplos: partilha de mercados.

3/12/2002
Cadeias de Markov: campanhas publicitárias; filas de espera (com entrada limitada).
Introdução às filas de espera. Noções de fila, serviço, distribuições de entradas e de serviços. Disciplinas de fila e prioridades, impaciência, possibilidade de mudança de fila. Estabilidade. Parâmetros a calcular. Notação de Kendall. Distribuições de Poisson e exponencial negativa. Sistemas M/M/1: parâmetros, condição de estabilidade. Exemplos. Dedução das expressões dos pârametros para o sistema M/M/1.

5/12/2002
Outros modelos de sistemas de espera: sistemas M/M/S, sistemas M/M/1 e M/M/S/L (com entrada limitada, L unidades no sistema).
Expressões para outros sistemas: com várias fases de serviço -- um só serviço por fase (distribuição de Erlang com k fases); com tempo de serviço dependente do número de unidades no sistema.
Introdução à análise de stocks. Custos de manutenção de stock, reaprovisionamento, e de rotura de stock. Nível de stock e de reaprovisionamento, leis de consumo e de reaprovisionamento. Exemplo de aplicação. Modelos com velocidades de consumo constantes e sem rotura. Minimização do custo por unidade de tempo.

10/12/2002
Análise de stocks (cont). Modelo com rotura e sem custos de inicialização. Modelos de stocks com rotura e custos de inicialização. Exemplo de problema com consumo probabilístico: minimização do custo esperado.

12/12/2002
Análise duma resolução do trabalho prático: modelo matemático; análise de algumas características das soluções do problema; implementação directa do modelo matemático em CLP(FD); comparação com a utilização de programação dinâmica para diminuir a árvore procura.
Introdução aos problemas de substituição de equipamento.

17/12/2002
Introdução aos problemas de substituição de equipamento (cont). Obsolescência de equipamento: custos de manutenção a preços constantes. Taxas de juro e de desconto, custos reportados a um certo instante. Comparação de custos de projectos com base na determinação de rendas anuais constantes equivalentes.