ProgLin 2013: Questão 3 da P3

Olá professor,

estou com dificuldades para demonstrar no item b) que o conjunto viável dual é um segmento de reta. Eu não precisaria admitir/ter um p que já é solução viável, e depois construir algo da forma p + alfa*d, alfa>=0 e mostrar que isso também está no conjunto viável? Eu posso supor que o problema é viável assim de cara?

Outra dúvida, mas não relacionada a este exercício: se eu tenho uma matriz A quadrada que já me dizem que tem colunas L.D. (do enunciado ou afim) eu consigo criar um vetor d tal que A*d = 0, d >= 0, somatória de todos os componentes de d = 1? Eu sei que por ser L.D., esse d existe e é diferente de 0, mas e as outras duas condições? (este exercício é de alguma outra prova, mas não consigo localizá-lo por enquanto)

Obrigado.

Re: Questão 3 da P3

por Marcelo Queiroz - terça-feira, 16 jul. 2013, 09:25

Olá, Edênis!

No exercício 3 da P3, você deve ter escrito o dual de forma explícita no item (a), com suas restrições da forma a_ip≤c_i, i=1,...n. Considerando os casos a_i<0 e a_i>0 separadamente, a restrição acima se tornaria p≥c_i/a_i e p≤c_i/a_{_i} respectivamente; no caso a_i=0 a restrição se torna 0p≤c_i, o que não restringe o valor de p mas fornece condições de viabilidade para este dual, relativas ao vetor c (de fato a condição c_i≥0 se a_i=0 deveria fazer parte do enunciado, pois se existisse c_i<0 com a_i=0 o primal seria ilimitado e o dual inviável). Juntando todas as restrições da forma p≥c_i/a_i como p≥max{c_i/a_i|a_i<0} e todas as restrições da forma p≤c_i/a_i como p≤min{c_i/a_i|a_i>0} temos não apenas a representação explícita do segmento de reta como também uma maneira de obter o ponto ótimo dual (já que b>0 o problema é equivalente a maximizar p).

Quanto à outra dúvida, a única coisa que você consegue garantir *sem hipóteses adicionais* é que existe d≠0 tal que Ad=0, que é equivalente a dizer que as colunas de A são LD. Daria até pra normalizar este d (fazendo d*=d/||d||) e preservar a propriedade Ad=0, mas pra ver que as outras duas condições não valem em geral, basta tomar um exemplo como A=[1 1], que tem duas colunas LD (em R¹). Para satisfazer Ad=0 esse d≠0 teria que ser da forma d=(α,-α)', e portanto ele nunca seria ≥0, e nunca poderia satisfazer α-α=1.

Localize o enunciado exato do exercício que gerou essa segunda dúvida e eu tento ajudar.

Abraço,

Marcelo

Re: Questão 3 da P3

por Edênis Freindorfer Azevedo - terça-feira, 16 jul. 2013, 15:58

Consegui localizar!

É o item 2 da questão 4 da prova P1 desse ano. No caminho de ida (=>) consegui chegar até a parte que mostro que Ad = 0, d>=0, mas não consigo a condição da somatória! O caminho da volta achei simples, mas não usei a condição da somatória.
Olhando com um pouco mais de atenção, acho que devo ter que aproveitar alguma coisa da matriz A (supor coisa sobre as colunas dela) que ainda não sei exatamente o que é. É esse o caminho?

Obrigado.

Re: Questão 3 da P3

por Marcelo Queiroz - terça-feira, 16 jul. 2013, 21:58

Olá!

Você está tentando mostrar que o C é não-vazio em geral, mas isso não é verdade (e não é o que a questão pede). Naquele exercício, o ponto importante é a existência da semi-reta dentro do poliedro canônico, ou seja a existência de um xbarra e um d!=0 tais que xbarra+alfa*d pertence ao poliedro, para qualquer alfa>=0. Trabalhando com as condições de viabilidade destes pontos (ou seja, A(xbarra+alfa*d)=b para qualquer alfa>=0 e (xbarra+alfa*d)>=0 para qualquer alfa>=0) você conseguirá provar que Ad=0 (usando alfa=1 e A*xbarra=b) e que d>=0 (trabalhando por contradição: se existisse d_i<0 então aumentando alfa>0 alguma hora xbarra_i+alfa*d_i ficaria negativo). Depois disso, basta "normalizar" d dividindo-o pela expressão sum_i(d_i), que é necessariamente >0.

Isso é o argumento da ida (ou somente se). A volta (ou se) é mais simples, ou seja, tomar um xbarra viável em P e um d viável naquele cone C, e mostrar que xbarra+alfa*d será viável em P para qualquer alfa>=0. Escreva se tiver dúvidas.

Marcelo