Teoria da Optimização
Mestrado em Matemática
1º semestre - 2003/04
Faculdade de
Ciências e Tecnologia
Universidade de Coimbra
Teoria da Optimização Mestrado em Matemática
|
|
Docente:
| João Soares | Email:jsoares@mat.uc.pt |
| Gabinete 6.4 do Dep. Matemática | Tel. 239 791 154 |
Um dos elementos de avaliação da disciplina de Teoria da Optimização consiste na elaboração de um relatório/trabalho de síntese sobre um trabalho científico proposto pelo professor na lista abaixo. O aluno deve calendarizar reuniões periódicas com o professor. O aluno deverá entregar uma versão preliminar até 14 de Novembro de 2003 e deverá entregar uma versão definitiva até 15 de Janeiro de 2004.
O relatório deverá ser preparado em LaTeX que é um compilador para processamento de texto vocacionado para a escrita de texto matemático. Para produzir um texto em LaTeX necessita de um processador de texto ascii como o Emacs ou WinEdit onde o ficheiro .tex contendo as instruções é manipulado. Eis um exemplo de um ficheiro .tex. A compilação desse ficheiro produz um ficheiro .dvi ou .pdf ou .ps. O documento preparado por Michel Goemans do MIT descreve um conjunto de instruções elementares que te podem ajudar a escrever em LaTeX. O documento refere-se a um ficheiro preamble.tex que deve estar presente na directoria onde compilares o teu ficheiro .tex.
O Professor Pedro Quaresma do Departamento de Matemática mantém uma página web dedicada ao LaTeX e é autor do livro Introdução ao LaTeX editado pela Escolar Editora.
| Tema | Aluno |
| Tópicos em Programação
Linear Contínua Bibliografia: Linear programming in infinite-dimensional spaces : theory and applications. - Chichester : John Wiley, 1987. - XI, 172 p. - (Wiley-Interscience series in discrete mathematics and optimization). Cota: 90C/AND. Comentário: "The authors discuss linear optimization problems where there are infinitely many constraints and variables including the case of "semi-infinite programing" where just one of these is infinite. They extend concepts underlying linear programming, such as basic feasible solution, dual problem, and zero duality gap to infinite-dimensional spaces, under restrictions that depend on the topology and the ordering of the spaces. They also discuss certain extensions of the simplex algorithm and analyse its various applications including the mass-transfer (or continuous transportation) problem, maximal flow in a dynamic network, continuous linear programming, and some others." Existem PLs cuja função objectivo e restrições são funcionais lineares. O que é o dual? Existe Dualidade Forte? O que são os vértices? Que aplicações existem? |
Artur |
| Obter a
Desigualdade Escova mais violada em Grafos Planares Bibliografia: Fleischer, L.; Tardos, É. Separating maximally violated comb inequalities in planar graphs. Math. Oper. Res. 24 (1999), no. 1, 130--148. Comentário: "The traveling salesman problem (TSP) is a benchmark problem in combinatorial optimization. It was one of the very first problems used for developing and testing approaches to solving large integer programs, including cutting plane algorithms and branch-and-cut algorithms. Much of the research in this area has been focused on finding new classes of facets for the TSP polytope, and much less attention has been paid to algorithms for separating from these classes of facets. In this paper, we consider the problem of finding violated comb inequalities. If there are no violated subtour constraints in a fractional solution of the TSP, a comb inequality may not be violated by more than 1. Given a fractional solution in the subtour elimination polytope whose graph is planar, we either find a violated comb inequality or determine that there are no comb inequalities violated by 1." |
Miguel |
| Algoritmos para minimizar
uma função submodular em tempo fortemente polinomial Bibliografia: Iwata, Satoru; Fleischer, Lisa; Fujishige, Satoru A strongly polynomial-time algorithm for minimizing submodular functions, preprint (1999); e, Schrijver, Alexander A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80 (2000), no. 2, 346--355. Comentário: "A submodular function on a finite set $V$ is a function $f$ defined on a family of subsets of $V$ such that $f(X)+f(Y)\geq\break f(X\cap Y)+f(X\cup Y)$ for all $X,Y\subseteq V$. The author presents a strongly polynomial-time algorithm for minimization of a submodular function $f$ using a value-giving oracle (i.e., an oracle that returns $f(X)$ for any given $X\subseteq V$). The algorithm does not use any linear programming method. No bound on the complexity of the values of $f$ needs to be known a priori. The number of oracle calls is bounded by a polynomial in the size of the underlying set." |
Nuno |
última actualização em 18 de Setembro de 2003