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.
Conclusão da aula anterior: 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) em clpfd.
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.
Interpretação geométrica do método Simplex no plano e no espaço. 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).
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. Referência à complexidade exponencial do método Simplex, no pior dos casos, e à existência de métodos polinomiais. Introdução ao Problema de Transporte.
Problema de transporte 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. Resolução do problema de transporte: método stepping stone. Propriedades da matriz de coeficientes.
Resolução do problema de transporte: método uv (método de Dantzig). Justificação da sua correcção.
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.
Análise de problemas em redes sobre caminhos e árvores de suporte: revisão de alguns algoritmos para sua resolução.
Determinação do caminho máximo em grafos dirigidos acíclicos.
Introdução às redes de actividades.
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.
Modelo de optimização linear para o problema e sua tradução por programa usando clpfd.
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 crítico).
Modelo linear para problemas com custos. Custo da redução da duração das actividades. Soluções com custo mínimo.
Conclusão da aula anterior. 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.
Modelo matemático do problema de maximização do fluxo numa dada rede.
Programação inteira: Definição e exemplos; Definição de relaxação linear. Modelação de situações especiais: Problemas com custos fixos; Problemas de cobertura; Restrições de OU (não exclusivo); Restrições SE ... ENTÃO.
Método da procura em árvore (branch-and-bound) para programação inteira.
Análise de dois exercícios propostos ( folha 6). 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. Análise de dois programas para resolução dum problema de escalonamento numa rede arco-actividade, com marcação duma mesma data de início para as actividades que começam no mesmo nó (concretamente, a mais próxima). 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. Reified Constraints em clpfd: uso de variáveis booleanas para detectar (forçar ou impor) a satisfação ou não duma restrição.
Restrições proposicionais em clpfd.
Problema do emparelhamento máximo como problema de fluxo máximo.
Problemas de afectação: problema de emparelhamento máximo com custo mínimo; método húngaro.
Formulação de modelos matemáticos para problemas de optimização combinatória. Exemplo de aplicação a um problema de optimização de postos de contagem de tráfego em intersecções urbanas: exploração das propriedades matemáticas da matriz do problema de transporte na análise e definição dum modelo para instâncias do problema; modelos aproximados (enfraquecimento de restrições complexas e de difícil tradução, necessidade de testar "soluções" encontradas).
Conclusão da aula anterior. Continuação de formulação de modelos matemáticos para problemas de optimização combinatória: exemplo duma aplicação à optimização do armazenamento de produtos em silos com a restrição de não poderem ser misturados.
Modelos para 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.
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.
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 de ilustração (reforma de agricultor; venda de casa; jogo (revista J.Público)).
Introdução à análise de filas de espera: modelos markovianos M/M/1, M/M/S, M/M/S/L (concl); condição de estabilidade; exemplos; dedução das expressões dos pârametros para o sistema M/M/1.
Introdução à análise de stocks. Custos de manutenção de stock, reaprovisionamento, e de ruptura 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 ruptura. Minimização do custo por unidade de tempo. Modelo com ruptura e sem custos de inicialização. Modelos de stocks com ruptura e custos de inicialização.
Análise de stocks (concl). Exemplo de problema com consumo probabilístico: minimização do custo esperado.
Introdução aos problemas de substituição de equipamento. Obsolescência de equipamento: custos de manutenção a preços constantes.
Substituição de equipamento: análise de problemas com juros; taxas de juro e de desconto; custos reportados ao mesmo instante; comparação de custos com base na determinação de rendas anuais equivalentes.
Breve referência ao Problema de Colocação de Professores e sua relação com o problema de determinação de emparelhamentos estáveis. Algoritmos de Gale-Shapley para resolução de problemas com listas de preferências estritamente ordenadas (completas ou incompletas).
Análise de resoluções do trabalho prático: apresentação do trabalho realizado por um grupo de alunos e pelos docentes; codificação dos modelos em CLP(FD); vantagens da definição duma estratégia de enumeração que explore o conhecimento específico do problema para dinamicamente definir a ordem de enumeração; análise da abordagem MIP (modelação usando AMPL) e resolução do problema por branch-and-bound.