Come verificare se la soluzione di un programma lineare è ottimale

Il certificato per provare l'ottimalità di una soluzione LP richiede una soluzione del LP duale che sia fattibile e complementare alla vostra soluzione - cioè, ovunque la vostra soluzione abbia una variabile con un valore lontano dal suo limite, il corrispondente vincolo duale è attivo, e viceversa. Così, quando il vostro algoritmo termina, dovrete

• generare una soluzione duale complementare che potete provare che è fattibile (per verificare l'ottimalità) o provare che non esiste una tale soluzione (per verificare la non ottimalità), o
• generare una soluzione all'LP duale che pensate sia ottimale e provare che essa e la vostra soluzione originale sono complementari.

Nota che ci sono già algoritmi che producono soluzioni dimostrabilmente ottimali in modo efficiente per LP molto grandi. Quale sarebbe il vantaggio del tuo algoritmo, specialmente se non puoi garantire l'ottimalità?

Se vuoi dimostrare che il tuo algoritmo è garantito per trovare una soluzione ottimale (se ne esiste una), allora dovrai dimostrare che puoi sempre eseguire la prima opzione sopra.