Planeamento
Aulas Teóricas
AT01 Formulação de probemas de optimização linear - 18/02 quarta
Apresentação, bibliografia e avaliação. Formulação do problema de optimização linear. Formas canónica e padrão. Conjuntos admissível e padrão.
AT02 Transformações entre formulações - 19/02 quinta
Transformação de problema formulado na forma padrão para problema formulado na forma canónica e vice-versa. Relacionamento entre os conjuntos admissíveis e solução.
AT03 Existência de solução - 23/02 segunda
Problemas de optimização linear na forma canónica. Interpretação analítica do problema. Interior e fronteira do conjunto admissível. Condição suficiente para a existência de solução. Função objectivo e função de restrição como funções contínuas.
AT04 Existência de solução - 26/02 quinta
Condição suficiente para a existência de solução de problema de optimização linear na forma canónica (conclusão).
AT05 Cálculo de soluções - 02/03
Problema de optimização linear na forma padrão reduzida. Vector admissível básico. Base e base admissível. Relacionamento entre bases e vectores admissíveis.
AT06 Cálculo de soluções - 05/03 quinta
Condição suficiente para que todo o vector admissível tenha uma testemunha básica. condição suficiente para que um problema de optimização linear na forma padrão reduzida tenha solução.
AT07 Interpretação Geométrica - 09/02 segunda
Conjunto admissível como conjunto convexo. Subespaço afim e suas caracterizações. Conjunto fechado para combinações afins.
AT08 Interpretação Geométrica - 12 /03 quinta
Hiperplanos e semi-espaços. O conjunto admissível do problema de optimização linear na forma padrão restrita como poliedro convexo.
AT09 Interpretação geométrica - 16/03 segunda
O conjunto admissível do problema de optimização linear na forma padrão restrita como poliedro convexo. Faces, arestas e vértices.
AT10 Interpretação Geométrica - 19/03 quinta
Vérttices e vectores admissíveis básicos. Envólucro convexo de conjunto de vectores.
AT11 Interpretação Geométrica - 23/03 segunda
Cones convexos. Cones convexos primitivos.
AT12 Interpretação geométrica - 26/03 quinta
Conclusão da aula anterior. Teorema da distância mínima.
AT13 Interpretação geométrica - 30/03 segunda
Lema de Farkas e suas variantes.
AT14 Interpretação geométrica - 09/04 quinta
Conclusão da aula anterior. Linhas activas para vector admissível. Teorema do máximo local e do máximo.
AT15 Interpretação geométrica - 13/04 segunda
Conclusão da aula anterior. Dualidade. Teorema da dualidade fraca. Condição suficiente para que vector admissível seja solução de problema de optimização linear na forma canónica.
AT16 Dualidade - 16/04 quinta
Lema da existência do dual. Teorema forte da dualidade.
Teste A - 16/04 quinta
18h00-20h00
AT17 Dualidade - 20/04 segunda
Folgas. Teorema das folgas. Condição de equilíbrio e sua caracterização.
AT18 Interpretação lógica do problema de opetimização - 23/04 quinta
Cálculo de inequações. Inequação incoerente e satisfazível e seu relacionamento.
AT19 Interpretação lógica do problema de optimização - 27/04 segunda
Conclusão da aula anterior. Problemas não degenerados (formulação padrão). Caracterização dos vectores admissíveis básicos em problemas não degenerados.
AT20 Problemas de computação e de decisão - 30/04 quinta
Apresentação do problema de computação e do problema de decisão ligados à optimização linear. Tempo de execução e tempo de execução na pior situação. Notação de Landau. Algoritmo polinomial.
AT21 Algoritmo do simplexo - 04/05 segunda
Apresentação do algoritmo do simplexo e início da demonstração da sua correcção.
AT22 Algoritmo do simplexo - 07/05 quinta
Demonstração da correcção e completude do algoritmo do simplexo.
AT23 Problema de verificação em optimização - 11/05 segunda
Problema NP. Demonstração que o problema de verificação em optimização é NP.
AT24 Complexidade computacional - 14/05 quinta
Complexidade computacional do algoritmo básico para o problema de optimização linear na forma padrão.
AT25 Optimização linear inteira - 18/05 segunda
Problema de optimização linear inteira. Técnica do "branch and bound".
AT26 Optimização linear inteira - 21/05 quinta
Problema da mochila. Problemas totalmente unimodulares. Problema da afectação de recursos.