Re: dúvidas

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

Ola'

On Sat, 12 Aug 2000, acarro wrote:

> Prof. ,verifique se esta correto.
> 
> Demonstre o Teorema de alternativas de Gale.
> s1: Ax=b           s2:A'y=0
>                       b'y=1
> Sol.
> s1^s2=falso
> suponha que há um par(x,y) pertencente aos  R^m X R^n
> solução de S1 e S2 respectivamente
> 
> 1=b'y=(Ax)'y=A'yx'=0.x'=0 (absurdo)

Detalhe:       ^ (A'y)'x, como esta' tem erro de dimensoes

> não S1=>S2
> Associando-se a um par primal dual conveniente teriamos
> 
> max      (p)                           min b'y   (d)
     ^ 0'x, a fc obj. de um PL e' "lado direito" 
            de seu correspondente par, sempre!!!!
> Ax=b                                   A'y=0
> x-> R^m                                y->R^n
> 
> Supondo que S1 não tenha sol. então (p)é inviavel
> VOp=-infinito.Como d é viável(y=0)=>Vop=Vod ,Vod=-
> infinito.Assim (d) é ilimitado,dai S2 tem solução.

A conclusao pulou um passo GRANDE:
"Sendo (d) ilimitado, existe um semi-reta e como o poliedro de (d) e' um
 cone, qualquer elemento nao nulo e' uma semi-reta. 
 [Basta agora apresentar uma semi-reta que seja de ilimitacao (alem de 
  <ly -> poliedro (d)>, b'(ly) -> infinito, qdo l->inf. ]
 Ou seja, existe um y no poliedro de (d), tal que,

   A'y = 0 e b'y<0.

 Agora tomando z=(1/||y||) y, teremos

   A'z = A'(1/||y||) y = (1/||y||) A'y = (1/||y||) 0 = 0,  e
   b' (1/||y||) y = (1/||y||) b'y < 0, pois 1/||y||>0 e b'y<0.

 [Finalmente podemos concluir a tese:]
 Deste modo, S2 tem solucao, ao menos z definido acima. c.q.d.

> Outra dúvida que tenho nesse problema,é que como c'y=0,
> b'y=1...então b'y>c'y. Posso dizer que o primal é de
> maximização?

Opsss... Esta' cometendo um deslize estranho (que voce^, Antonio, nao
cometeu em sua prova): o T.Fraco diz que, no caso de MAXIMIZACAO,
quaisquer pares viaveis (x,y),

          c'x <= b'y

o que esta' perfeitamente coerente com o para primal/dual acima.

Certo ? E' o contrario do que escreveu acima.

> Outro exercício era considerando 1=(1,1,1...1)'
> mostre que o sistema S1 e S2 constituem um teorema de
> alternativas.
> 
> 
> S1:Ax=0                        S2:A'y>=1
> X>0
> 
> Sol.
> S1^S2=falso
> suponha que haja um par (x,y) solucão de S1 e S2
> respectivamente.
> 0=b'y=(A'x).y=x.(A'y)>=x(absurdo)

??? onde aparece b no par ?

Nao seria: 1 < x'(A'y) = y'Ax = 0 ???!!!

> não S1=>S2
> associando-se um par primal dual conveniente
> 
> max x                   min 0.y
      ^ NAO: se o lado direito em S2 que deseja associar `a (p) e'
             (1,...1) entao a fc obj de (d) tem que ser
  max 1'x = max x_1+x_2+...+x_n

> Ax=0  (d)             (p)   A'y>=1
> x>0                         y pert. R^n
  ^ nao costumamos trabalhar com desigualdades estritas, certo?

> eu inverti a ordem,pois acho que (p) não é viável????
> Por que não é viavel??? devido ao (min 0.y)?
> Bom passado isso,teria que ver se (d) é viavel.
> Pelo visto eu acho que A é ld.e deve haver x<>0,x>0
> que a torne viavel...esta certo????
> O resto eu sei terminar.

Este e' o galho. Modelou errado. Deveria trabalhar com x>=0 e acertar o
resto na solucao, fazer com x nao seja nulo: como (d) e' o que vai 
usar para viabilidade e ilimitacao, quando tiver ilimitacao vai
implicar que 1'x > 0 e isso implica, como x>=0, que  x>0 c.q.d.

> A questão da sub que pedia uma c.suficiente para que o
> sistema não tenha sol,(Ah1=0 h1>=0,c'h1<0 ,b'h2>0,Ah2=0)
> 
> seria associar um (P)=> max 0'h1
>                             Ah1=0
>                             h1>=0
> e um D=>min 0'h2
>            Ah2>=0
>            h2 livre de sinal
> prof. (P) é viável para h1=0?
> 
> Como eu concluiria esse problema da prova Sub.

A ideia e' associar um par primal/dual. Sabemos que se um e' viavel entao
VOP=VOD, logo se um e' viavel nao podemos ter cones de ilimitacao em
ambos!! E cone de ilimitacao e' o que e' o sistema S (basta decompo-lo em
dois sistemas).

Deve escrever estes comentario no arquivo da Sub. Mando aviso.

> antecipadamente muito obrigado pela atenção.
> Antonio Marcos l. carro

Ate'

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] 
 Interessado em Matemática?  Visite o "iMatica":  http://www.matematica.br