CC330: Métodos de Apoio à Decisão

Sumários - Aulas Teóricas (2007/08)

Miguel Filgueiras e Ana Paula Tomás

Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto


25/02/2008
Objectivos da disciplina.
Formulação de modelos matemáticos para problemas de decisão: exemplos. Sistemas de unidades e dimensões; análise dimensional de equações.

27/02/2008
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.

03/03/2008
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.

05/03/2008
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.

10/03/2008
Programação inteira e mista. Relaxação linear. Método da procura em árvore (branch-and-bound) para programação inteira.

12/03/2008
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) em sistemas de Prolog. Exemplos de programas: puzzle: send+more=money.

(Férias de Páscoa: 17/04/2008 a 24/04/2008)

26/03/2008
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, ff (first-fail), down. Predicados para optimização: maximize e minimize. 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). Restrição de indexação element. Estratégias de procura: "geração e teste" versus "restringir e gerar". Necessidade de restrições mais complexas (restrições globais/especializadas): por exemplo, all_distinct (comparação com all_different).

31/03/2008
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. Exemplos: formação de equipa para prova de natação.

02/04/2008
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: problema de corte (andares).


07/04/2008 a 24/04/2008 Consultar sumários e informações complementares das aulas leccionadas por Prof. Miguel Filgueiras sobre problemas em grafos e redes (caminhos mínimos/máximos, árvores de suporte, escalonamento de tarefas, fluxo máximo).


28/04/2008
Problema do emparelhamento máximo em grafos bipartidos como problema de fluxo máximo. Problemas de afectação com pesos (custos): minimização do peso global; breve referência ao método húngaro (de Kuhn-Munkres). Problemas de emparelhamento em grafos bipartidos com preferências e prioridades: algoritmo de Gale-Shapley para determinação de emparelhamentos estáveis.

30/04/2008
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.

(Semana da Queima das Fitas: 05/05/2008 e 07/05/2008)

12/05/2008
Programação Dinâmica. Obtenção de soluções partindo da situação inicial (análise para a frente). Exemplos: reforma de agricultor; caminho mínimo; problemas de mochila. Obtenção de soluções por análise para trás. Exemplo: problema da venda de casa (optimização do valor esperado).

14/05/2008
Uso de programação dinâmica para redução do espaço de procura num problema ( jogo ) de optimização discreta: tabelação de informação relevante sobre soluções de subproblemas de dimensão inferior e utilização dessa informação para corte da árvore de pesquisa; implementação de retrocesso cronológico; re-inicialização do método.


19/04/2008 a 28/04/2008 Consultar sumários e informações complementares das aulas leccionadas por Prof. Miguel Filgueiras de introdução à simulação, filas de espera e substituição de equipamento.