Sejam A in R^m times n e b in R^m, tais que posto (A)=m e b >= 0. Defina V=x in R^n mid A x=b, x >= 0. Considere o PL
ll minimizar & sumi=1^n yi sujeito & A x+y=b & xj >= 0, yi >= 0 ; i=1, cdots, m, j=1, cdots, n
1
Mostre que se o valor ótimo do PL acima é nulo então V possui uma solução básica viável. O quê podemos concluir se o valor ótimo for não-nulo? Justifique sua resposta.

Passo 1

Beleza, vamos lá! O enunciado fala sobre programação linear. Temos uma matriz de dimensões com posto (isso significa que as linhas de são linearmente independentes) e um vetor que é não-negativo. Estamos definindo o conjunto que contém todos os vetores que satisfazem e . O problema de programação linear (PL) que precisamos analisar é minimizar a soma dos componentes de sujeito a , com e também sendo não negativos.

Passo 2

Primeiro, vamos entender o que significa ter um valor ótimo nulo para esse PL. Se o mínimo da soma das componentes de é zero, isso quer dizer que todas as componentes de são iguais a zero no ponto ótimo. Então, a restrição simplifica para . Além disso, como , ter não viola nenhuma restrição. Portanto, nesse caso, é uma solução viável para .

Passo 3

Agora, vamos falar sobre soluções básicas viáveis. Em programação linear, uma solução básica viável é uma solução que satisfaz as restrições do problema e que está em um “vértice” do conjunto de soluções possíveis. Como tem posto , e estamos considerando com , podemos aplicar o teorema da existência de soluções básicas viáveis. Ou seja, se o PL tem uma solução viável (no caso, que satisfaz e ), então existe pelo menos uma solução básica viável.

Passo 4

Então, se o valor ótimo do PL é zero, isso implica que existe um vetor que satisfaz e , ou seja, não está vazio. Além disso, como tem posto completo e estamos em um espaço onde deve ser não negativo, essa solução pode ser escolhida para ser uma solução básica viável.

Resposta

Se o valor ótimo do problema de programação linear é zero, então o conjunto possui uma solução básica viável. Por outro lado, se o valor ótimo for diferente de zero, isso indica que não existe nenhuma solução no conjunto que satisfaça todas as restrições e , ou seja, não possui solução viável.

Exercícios relacionados