Sejam
e
, tais que posto
e
. Defina
. Considere o PL
1
Mostre que se o valor ótimo do PL acima é nulo então
possui uma solução básica viável. O quê podemos concluir se o valor ótimo for não-nulo? Justifique sua resposta.
Mostre que se o valor ótimo do PL acima é nulo então
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.