MCTA017 -- Programação Matemática -- 2021.Q3

Expediente

• Professor: Aritanan Gruber
• Moodle: PM21.3
  (detalhes de andamento do curso, notas de aulas, links para artigos e vídeos das aulas, avaliações, notas, etc.)
• Atendimento: Sex 10–12h via Google Meet <= novo link provido pelo google
  (você deve estar logado no Classroom (código: wnau22o) com sua conta da UFABC)
• Aulas assíncronas: vídeos em Aritanan Gruber’s YouTube

Ementa

Introdução: revisões de álgebra linear e conjuntos convexos. Programação linear: modelagem; resolução gráfica; teoremas básicos; o método simplex; simplex revisado; dualidade; algoritmos primal-dual e dual-simplex; análise de sensibilidade. Programação Dinâmica.

Avaliações e critérios

• 4 listas de exercícios: $L_1, L_2, L_3, L_4\in[0,10]$
  média aritmética das 3 melhores

Nota nominal: $$ N = \frac{1}{4}\max\left\{\sum_{j\in S}L_j\,:\,S\in\binom{[4]}{3}\right\} $$

Conceito nominal ($C_N$): reflete o seu desempenho frente ao material apresentado e às avaliações realizadas; obtido pelo encaixe de $N$ em um dos intervalos: $$-\infty < \mathbf{F} < 5.0 \leq \mathbf{D} \leq 6.0 < \mathbf{C} \leq 7.0 < \mathbf{B} \leq 8.5 < \mathbf{A} < \infty.$$

Normalização

Sejam $\mu$ e $\sigma$ a média e o desvio padrão das notas $N$ atribuídas a todos os alunos. Cada aluno obterá uma nota normalizada: $$M = (N-\mu)/\sigma.$$

Conceito normalizado ($C_M$): reflete o seu desempenho perante os seus colegas; obtido pelo encaixe de $M$ em um dos intervalos: $$-\infty < \mathbf{F} < 0 \leq \mathbf{D} < \frac{1}{4} \leq \mathbf{C} < \frac{1}{2}\sigma \leq \mathbf{B} < \sigma \leq \mathbf{A} < \infty.$$

Considerando-se a ordenação $\mathbf{A} > \mathbf{B} > \mathbf{C} > \mathbf{D} > \mathbf{F}$, seu conceito efetivo (final / pré-recuperação) será maior ou igual ao seu conceito nominal: $$C_F = \max\{C_N,C_M\}.$$

Recuperação

Caso seu conceito $C_F$ seja $\mathbf{D}$ ou $\mathbf{F}$, você tem direito a uma avaliação online de recuperação $P_R$. Esta será única e contemplará toda a matéria do quadrimestre. Uma nova nota nominal $\overline{N}=(N+P_R)/2$ será utilizada para gerar um novo conceito (nominal) final pós-recuperação $\overline{C}_N$. Não haverá normalização na recuperação. Seu conceito final pós-recuperação pode ser menor que o pré-recuperação: uma vez feita, a recuperação é parte integrante da sua avaliação.

Bibliografia

Usaremos Bertsimas-Tsitsiklis [A] e Gärtner-Matousek [C]. Ambos são muito didáticos.

Para material mais avançado em teoria e algoritmos, consulte Nemhauser-Wolsey [D] e, principalmente, Schrijver [E]. Para modelagem, recomendamos Chen-Batson-Dand [B], Fourer-Gay-Kerninghan [I] e Williams [J]. Conceitos de álgebra linear são cobertos em nível introdutório em Axler [K] e Strang [N] e, em forma mais avançada, em Hoffman-Kunze [O]. A referência clássica para análise convexa é Rockafellar [M]; Bertsekas-Nedic-Ozdaglar [L] é uma boa alternativa – ambos contêm muito mais material do que vamos precisar. Para otimização além de linear, consulte Bertsekas [F], Boyd-Vendenberghe [G] e Ruszczynski [H].

Otimização Linear e Linear Inteira

• [A] D. Bertsimas e J. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific (1997)
• [B] D. Chen, R. Batson e Y. Dand, Applied Integer Programming: Modeling and Solution, Wiley (2010)
• [C] B. Gärtner e J. Matousek, Understanding and Using Linear Programming, Springer (2007)
• [D] G. Nemhauser e L. Wolsey, Integer and Combinatorial Optimization, Willey (1988)
• [E] A. Schrijver, Theory of Linear and Integer Programming, Wiley (1986)

Otimização Convexa e Não-Linear

• [F] D. Bertsekas, Nonlinear Programming, 3rd ed., Athena Scientific (2016)
• [G] S. Boyd e L. Vendenberghe, Convex Optimization, Cambridge University Press (2004)
• [H] A. Ruszczynski, Nonlinear Optimization, Princeton University Press (2006)
• [P] N.K. Vishnoi, Algorithms for Convex Optimization (2020)

Modelagem e Ferramentas

• [I] R. Fourer, D. Gay e B. Kerninghan, AMPL: A Modeling Language for Mathematical Programming, 2nd ed., Thompson (2003)
• [J] H. Williams, Model Building in Mathematical Programming, 5th ed., Willey (2013)

Álgebra Linear e Análise Convexa

• [K] S. Axler, Linear Algebra Done Right, 3rd ed., Springer (2015)
• [L] D. Bertsekas, A. Nedic e E. Ozdaglar, Convex Analysis and Optimization, Athena Scientific (2003)
• [M] T. Rockafellar, Convex Analysis, Princeton University Press (1970)
• [N] G. Strang, Introduction to Linear Algebra, 5th ed., Wellesley Publishers (2016)
• [O] K. Hoffman e R. Kunze, Linear Algebra, 2nd ed., Prentice Hall (1971)

Lista de tópicos por semana (tentativa)

• S01 – Introdução à Otimização e Dualidade Lineares
  (BT[A] 1.1 – 1.4, 1.6, 1.8, 4.1, 4.2; GM[C] 1.1 – 1.4, 2.1 – 2.5, 3.1, 4.1, 6.1, 6.2)
• S02 – Elementos de Álgebra Linear e Convexidade
  (BT[A] 1.5, 2.1; GM[C] Apêndice, 4.3; A[N] 1.B, 1.C, 2.A – 2.C, 3.A – 3.C, 6.A – 6.C)
• S03 – Geometria e Estrutura de Poliedros I
  (BT[A] 2.2 – 2.8, 4.2 – 4.4, 4.6, 4.7; GM[C] 4.1 – 4.4, 6.1, 6.2, 6.4, 6.7)
• S04 – Geometria e Estrutura de Poliedros II
  (BT[A] 2.2 – 2.8, 4.2 – 4.4, 4.6, 4.7; GM[C] 4.1 – 4.4, 6.1, 6.2, 6.4, 6.7)
• S05 – Geometria e Estrutura de Poliedros III
  (BT[A] 2.2 – 2.8, 4.2 – 4.4, 4.6, 4.7; GM[C] 4.1 – 4.4, 6.1, 6.2, 6.4, 6.7)
• S06 – Método Simplex I
  (BT[A] 3.1 – 3.5, 3.7, 4.5; GM[C] 5.1 – 5.10)
• S07 – Método Simplex II
  (BT[A] 3.1 – 3.5, 3.7, 4.5; GM[C] 5.1 – 5.10)
• S08 – Análises Paramétrica e de Sensibilidade
  (BT[A] 5.1 – 5.4, 6.1, 6.2, 12.1)
• S09 – Métodos de Pontos Interiores I
  (BT[A] 9.1 – 9.3; Vis[P] 10)
• S10 – Métodos de Pontos Interiores II
  (BT[A] 9.4 – 9.6; Vis[P] 10)
• S11 – Método de Elipsoides
  (BT[A] 8.1 – 8.5; Vis[P] 12)
• S12 – Matrizes Totalmente Unimodulares e Poliedros Inteiros
  (BT[A] 10.1 – 10.3, 11.1, 11.2; GM[C] 3.1 – 3.4)

Estudando para esta disciplina

Pela natureza do tópico (métodos de otimização) e pelo posicionamento na grade (Q10-Q12), este é um curso avançado de graduação e será tratado como tal. Espera-se que você, após a primeira semana, leia o conteúdo programado para as demais aulas antes de ocorrerem e se dedique à listas e projeto.

De qualquer forma, é normal fazer confusões e sentir-se perdido no início. O motivo é, em geral, a falta de familiaridade com formalismo matemático e raciocínio algorítmico.

• Refaça os exemplos fornecidos nas aulas e re-prove os principais resultados.
• Preste atenção ao processo de solução e não foque somente no resultado final.
• Assista às aulas (vídeos) e resolva os exercícios propostos durante as mesmas e os contidos nas listas.
• Estude a bibliografia indicada (monte grupos de estudo online) e faça um bom uso dos horários de atendimento.
• Tenha sempre em mente que aprendizado é uma tarefa ativa; não fique somente assistindo.
• Se ainda estiver se sentindo perdido, repita os passos acima. Mais cedo ou mais tarde, eles convergirão à compreensão.

Integridade acadêmica e transgressões

O Artigo 25 do Código de Ética da UFABC estabelece, à página 23: “Quanto aos trabalhos acadêmicos, é eticamente inaceitável que os discentes:

• I - fraudem avaliações;
• II - fabriquem ou falsifiquem dados;
• III - plageiem ou não creditem devidamente autoria;
• IV - aceitem autoria de material acadêmico sem participação na produção;
• V - vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.”

Trabalhos (listas, provas, programas) suspeitos de cópia ou de outra representação fraudulenta acarretarão aos envolvidos conceitos $\mathbf{F}$ (falha) no curso. A atividade será reportada à Comissão Disciplinar Discente da universidade para que sejam tomadas todas as providências disciplinares cabíveis.