Olá,
Eu estava tentando fazer a prova 2 (BMAC 20/10/2011) e na questão 2 temos de classificar as direções encontradas em inviavel, viavel limitada/ilimitada, eu imagino que uma direção inviavel é aquela que te faz sair do cojunto viavél mas eu queria uma definição melhor do que seja cada uma delas.
Obrigado
Em resposta à Bruno S Reis
Re: Duvida sobre direção inviavel, viavel limitada/ilimitada
por Marcelo Queiroz -
Oi, Bruno!
A definição geral de direção viável a partir de um vértice x (e consequentemente também a definição do que significa direção inviável a partir deste ponto) está na página 36, definição 3.1, e vale para poliedros com qualquer formulação. Note que a definição se refere explicitamente à existência de um θ>0 para o qual x+θd pertence ao poliedro; no caso de uma direção básica d(j) em um poliedro na forma canônica a partir de um vértice associado a uma base B, então o mecanismo de cálculo do θ* do simplex associa a inviabilidade da direção ao critério θ*=0 (θ*>=0 é a condição que caracteriza direções viáveis).
A noção de direção ilimitada/limitada (em relação ao poliedro) é um conceito geométrico que está colocado no início da seção 3.2, página 39. A direção d é ilimitada a partir de x se a semi-reta {x+θd|d>=0} estiver contida no poliedro; ela será limitada no caso contrário (note que essa é uma caracterização geral, e não apenas para a forma canônica). Observe que se ela já é viável, então existe algum θ>0 tal que x+θd pertence a P, e se a semi-reta não está contida no poliedro, o fato do poliedro ser fechado garante a existência de um θ máximo para o qual x+θd ainda pertence ao poliedro. No caso canônico, em uma direção básica d(j) a partir de x, então a ilimitação da direção está caracterizada pela inexistência de uma componente dBi<0, e portanto pelo cálculo do θ* envolver um conjunto vazio (θ*=min Ø=∞ por convenção, ou seja, não existe limitação para o θ e todos os x+θd pertencem ao poliedro).
Existe um terceiro conceito relacionado, que é o de direção de ilimitação em relação ao (PL), ou seja, uma direção d a partir de um ponto viável x tal que (1) d é ilimitada a partir de x, ou seja, x+θd pertence ao poliedro para qualquer θ>=0 e (2) a função objetivo decresce estritamente neste caminho, ou seja c'(x+θd)<c'x para θ>0 (isso é equivalente a c'd<0). No teorema 2.8 esse conceito aparece, para provarmos que se um problema viável não tem um vértice ótimo, então ele precisa ser ilimitado.
Marcelo