[MAC 315] Lista 3 e caract. de vertices

[Leonidas O Brandao <leo@ime.usp.br>]

Ola' para todos,

 Dois assuntos importantes antes da prova...

 1) O Emerson me mostrou que errei na digitacao de mais um exercicio, o
    numero 1.4: a forma correta dos itens e'

    i) C={0}              => X limitado  (NAO vale o <=)
   ii) X lim. e nao vazio => C={0}       (NAO vale o =>)

    Lembre o que 1.5 tb tem erro (que ja' apontei).

 2) Hoje na monitoria apareceu um duvida num exercicio de tranformacao de
    poliedro nao canonico para canonico.

    A confusao foi que pensavam valer o seguinte resuntado: Y <-> X

      y vertice de Y <=> x vertice de X 

    o que e' falso na direcao <=!!! Ja' vimos isso em sala, o exemplo do
    poliedro sem vertices que no canonico resultava em 2 vertices.

    Estou enviando anexo um TXT explicando um pouco melhor isso.

  ----------------------------------------------------------------------

    Outro ponto teorico importante, que em funcao da duvida acima, acho
    melhor explicitar: tambem NAO e' verdade que

          x vertice de X <=> {A^i}_{i em I(x)} l.i.

    A parte => e' sempre verdade, mas <= SO' vale quando x em X, ou seja o
    teorema (2.2) que vale e'

          x \in V(X)     <=> x \in X e {A^i}_{i em I(x)} l.i.

 Espero ter dirimido todas a duvidas a este respeito. Mas todos entenderem
perfeitamente, aconselho criarem exemplos (pequenos) e fazem as contas (e
desenhos).

 Bons estudos,
 Leonidas

 --------------------------------------------------------------------------
 Leônidas de Oliveira Brandão - Computer Science Dep. of IME-USP  (Brazil)
 leo@ime.usp.br - http://www.ime.usp.br/~leo - +55 (011) 818 [6298 | 6135] 
Atenção: Cuidado com o raciocínios sobre poliedros transformado em canônicos
-------

Seja Y:={y: By<=b} e X:={x: Ax=b, x>=0}, tal que
     para todo y em Y existe um unico x em X
     e dado um x em X existe um y em Y correspondente

Algumas observações importantes:

1) Vimos um exercício onde o poliedro original não tinha vértices
   e o conônico transformado tinha! Logo, 

     <x em V(X)> NÃO implica que <y em V(Y)>

2) Não é fácil provar, mas

      <y em V(Y)> => <x em V(X)>

   Idéia é:
   Lema 1: y em V(Y) <=> By=b
   Dem:    (<=) É direto.
           (=>) Dá trabalho 
                Tem que usar Álgebra Linear: I={i: B^i y = b_i},
                posto de B para B_m,n com m<n,...
   Lema 2: Dado y em Y, então
           y em V(Y) <=> não existe h dif. de 0 tq Bh=0
   (use y não vértice <=> existe h tq y-h e y+h pertence a Y)

Note que o teorema 2.2 de caracterização de vértice para poliedros
conônicos era: Dado x em X, então
                    x vértice <=> {A^j}_{j em I(x)} é l.i.
Assim, 

Exercício: {A^j}_{j em I(x)} é l.i. NÃO implica que x vértice !!

Por que? Ache um contra-exemplo

Para finalizar: o exercício da monitoria

 Seja Y:={y: y_1+y_2 <= 1, y_1>=0}
 Então o X correspondente é 

      X:={x: x_1+x_2+x_3-x_4 = 1, x>=0 }, 

 com a associação
      
      x_1 := y_1
      x_2 := 1 - y_1 - y_2 (=> x_1 + x_2 = 1 - y_2 )
      x_3 := mais(x_2)
      x_4 := menos(x_2)

 onde mais(a):=max{a,0} e menos(a):=-min{a,0}.

 Assim, usando o fato que bases geram vetores (se 
 contidos em X!!!),

        V(X) = { e^1,  e^2,  e^3 }
                  ^     ^     ^
                  |     |     |
                 \/    \/    \/
                (1,0) (0,0) (0,1) correspondentes em X

 Note que: 
 - a base {A^4} resulta -e^4
 - todos os pontos resultam originais viáveis, não
   necessariamente vértices