Como verificar se a solução de um programa linear é ótima

O certificado para provar a otimização de uma solução LP requer uma solução para o LP duplo que seja viável e complementar à sua solução - ou seja, onde quer que a sua solução tenha uma variável com um valor longe do limite, a restrição dupla correspondente está ativa, e vice-versa. Assim, quando o seu algoritmo terminar, você precisará ou

>ul>li>gerar uma solução dupla complementar que você possa provar ser viável (para verificar a otimização) ou provar que nenhuma tal solução sai (para verificar a não otimização), ougerar uma solução para a dupla LP que você considere ótima e provar que ela e sua solução original são complementares.p>Note que já existem algoritmos que produzem soluções comprovadamente ótimas de forma eficiente para LPs muito grandes. Qual seria a vantagem do seu algoritmo, especialmente se não puder garantir a optimização?

Se quiser provar que o seu algoritmo tem a garantia de encontrar uma solução óptima (se existir), então terá de provar que pode sempre realizar a primeira opção acima.