Pessoal,
Ontem na monitoria com alguns alunos, duas questões ficaram pendentes de resposta. O prof. Marcelo indicou como resolvê-las e achamos melhor postar aqui, assim todos têm acesso à resolução.
P3 de 07/12/2010, questão 4
Naquela questão 4, acho que houve um mal-entendido em relação ao que significa "a solução associada a B no problema acima". Não é o mesmo x de antes, mas o x que seria construído *no problema acima* fixando x_N=0 e fazendo x_B=B^{-1}(b+beta). Uma solução básica de um PLC sempre obedecerá o sistema de equações, por construção, mas ela pode violar as restrições de sinal, então a questão da viabilidade é respondida pela condição B^{-1}(b+beta)>=0 ou B^{-1}beta>=-B^{-1}b. Realmente o gama não tem nada a ver com a viabilidade.
No (b), realmente a condição de viabilidade dual (equivalente a cbarranovo>=0) só depende do gama, e poderia valer mesmo para um beta que tornasse a base inviável. A condição é simplesmente cbarranovo=(c+gama)'-(c+gama)_B'B^{-1}A>=0, ou ainda, cbarravelho'+gama'-gama_B'B^{-1}A>=0.
O (c) depende de uma propriedade bem bonita, que é re-escrever um (PL) como um sistema de equações lineares equivalente, usando dualidade e folgas complementares, e aí parametrizar o valor ótimo do problema em função de beta e gama. Note que um par ótimo primal-dual (x,p) tem que satisfazer Ax=b+beta,x>=0,A'p<=c+gama e (c+gama)'x=(b+beta)'p (viabilidade primal e dual e ausência de gap de dualidade). Como estamos interessados apenas nas soluções xbarra e pbarra associadas à base B (ou seja, xbarra_N=0, xbarra_B=B^{-1}(b+beta), pbarra'=(c+gama)_B'B^{-1}), o valor ótimo a ser minimizado é simplesmente (c+gama)'x=(c_B+gama_B)'B^{-1}(b+beta) sujeito a B^{-1}(b+beta)>=0 e (c+gama)_B'B^{-1}A<=c', que são restrições lineares nas variáveis beta e gama (com A, b, c e B fixados), porém com uma função objetivo quadrática (pois abrindo a expressão aparecerão todos os produtos de gama_{B_i} por beta_j).
P3 A - questão 3 (a)
A P3A-Q3-(a) tem a ver com a caracterização de direções de ilimitação em (PLCs): uma direção y será de ilimitação se x+alfa*y for viável para todo alfa>=0, e c'y<0 (assim c'(x+alfa*y) tende a -infinito quando alfa tende a infinito). x+alfa*y ser sempre viável depende apenas de A, e não do lado direito, pois se x é viável em (Plambda), ou seja, se Ax=b+lambda*d, então A(x+alfa*y)=b+lambda*d é o mesmo que alfa*(Ay)=0. Se existisse uma direção assim no (Plambda), com c'y<0, ela seria também direção de ilimitação no (PL) original com lambda=0, e não poderia existir uma base ótima.
Intuitivamente (o que não serve como prova...), podemos pensar que as variações do lado direito conseguem jogar os hiperplanos que definem o subespaço-afim {x| Ax=b} mais para cima ou para baixo, mas não afetam as inclinações destes hiperplanos (inclinações dadas pelas linhas de A), e por isso esse tipo de manipulação não pode introduzir novas direções tangentes ao subespaço-afim, já que essas direções são exatamente o espaço-nulo de A. As mudanças podem sim reconfigurar radicalmente o conjunto por determinarem a viabilidade e inviabilidade das diversas soluções básicas, que são associadas tanto ao espaço-afim resultante quanto às restrições de sinal ativas ou inativas em cada solução.
Abraços,
Brielen