|
Nesta página serão disponibilizados os roteiros de aulas já realizadas e os
roteiros pretendidos para aulas ainda não realizadas.Atenção, o cronograma
é apresentado por semanas, sendo que podem existir pequenas diferenças de datas entre as
três turmas devido aos feriados e dinâmicas de aulas diferentes.
|
Aulas |
Tópicos/comentários |
| |
|
| SEMANA 1
06/08-14/08 |
- Introdução à disciplina
- Otimização
- problemas gerais
- problemas com estrutura
- O que é Programação Linear (PL):
- idéias
- conceitos
- exemplos
- Algumas convenções
- Conceitos Matemáticos: teoremas, demonstrações,...
|
|
| SEMANA 2
13/08-15/08 |
- Conceitos básicos:
- x>y, x>=y, xy, A=[a¹|a²|...|an]=[...]
- dependência linear: A=[a¹|a²|...|an], então x=0>
- base do IRn
- hiperplano (afim): Hc,a := {x em IRn: c'x=a}
- Semi-espaço: Sc,a := {x em IRn: c'x<=a}
- Curvas de nível: Hc,a , Hlc,la ,
Hlc,? = Hc,a , ...
|
|
| SEMANA 3
19/08-21/08 |
- Conceitos básicos: ponto aderente, fecho, aberto/fechado, norma, bola,...
- Poliedros e convexos
- definições, exemplos e propriedades
|
|
| SEMANA 4
26/08-28/08 |
- Convexidade: algumas propriedades
- A inter B
- l1*A + l2*B
- ...
- Cones
- definições, exemplos e propriedades
|
|
| SEMANA 5
09/09-11/09 |
- Cone: algumas propriedades (princ. A conv => C(A) conv.)
- Cone gerado:
- Versão geométrica: C(A) := { l*c : l>=0 e c em A }
- Versão algébrica: C(A) é o menor cone que contém A
- Propriedades e exercícios (princ. Prop. 10: B cone => <B é conv <=> B=B+B>)
- Cone poliedral
- Invariantes:
A subespaço => l1*a1 + l2*a2 em A, l1 e l2 qq escalares
A convexo => l1*a1 + l2*a2 em A, l1 e l2, escalares tq l1>=0, l2>=0 e l1+l2=1
A cone convexo => l1*a1 + l2*a2 em A, l1 e l2, escalares tq l1>=0, l2>=0
(o último invariante segue da propriedade 10 indicada acima)
|
|
| SEMANA 6
16/09-18/09 |
- Casco convexo de A = [A]
- A em [A]; A em B => [A] em [B]; [A] interseção de todos conv. contendo A
- [A] = menor convexo contendo A
- Ponto extremo
- Equivalência entre problemas lineares: variáveis artificiais e de folga
|
|
| SEMANA 7
23/09- |
- Casco convexo:
- A := [{a^i}_{i=1,k}] limitado
- max { c'a, a em A} < +oo
|
|
| SEMANA 8
30/09-02/10 |
- Pontos extremos: exercícios
- Equivalencias
- y não extremo de Y <=> existe h<>0: y+h e y-h em Y;
- Conjuntos I(y) e H_x: x +/- l h em X <=> Ah=0, I(h) em I(x) e x em X
- Vértices: x não em V(X) <=> existe h<>0: x +/- h em X; ...
|
|
| SEMANA 9
07/10-09/10 |
- Vértices
- H_x subespaço linear
- Teorema: x em V(X) <=> x em X e {a^i}_{i em I(x)} l.i.
- Corolários: 0 em X <=> 0 em V(X) <=> {0} = V(X);
X <> vazio <=> V(X) <> vazio
- p := argmin{ q: Xq <> vazio} => Xp em V(X)
|
|
| SEMANA 10
14/10-16/10 |
- Avaliação 1
- Revisão avaliação 1
- Lema: x não em V(X) => existe h<>0 e l>0 tq x':=x+/-lh em X, #I(x') < #I(x)
|
|
| SEMANA 11
21/10-23/10 |
- Teorema: X = [V(X)] + C
- Corolário: X limitado <=> X = [V(X)]
- Consequências
- subconjunto limitado do cone C (C¹)
- C <> {0} <=> C¹ <> vazio
- raios extremais
|
|
| SEMANA 12
28/10-30/10 |
- Poliedro canônico C¹
- Capítulo 4: Simplex
- Condição de parada: base ótima (gama <= 0)
|
|
| SEMANA 13
04/11-06/11 |
- Capítulo 4: Simplex
- Condição de parada: base ótima (gama <= 0)
- Condição de parada: direção de ilimitação (pi <= 0)
- B base viável (b.v.) e gama não <= 0 NÃO implica que vértice associado não é ótimo
|
|
| SEMANA 14
11/11-13/11 |
- Exercícios de sala: se B b.v. e x em X, então: x_B = ?; c'x = ?
- Algoritmo: "atualização" de base
- Exercício: se B b.v., x vért. assoc. não degenerado, então "próximo" vért. é estritamente melhor
|
|
| SEMANA 15
18/11-20/11 |
- Simplex
- Forma tabular
- "Inicialização"
|
|