Come risolvere un sistema di disuguaglianze?
-
07-07-2019 - |
Domanda
Ho ridotto il mio problema (algoritmo di layout di tabella) al seguente problema:
Immagina di avere N variabili X 1 , X 2 , ..., X N . Ho anche un certo numero (indeterminato) di disuguaglianze, come:
X 1 > = 2
x 2 + X 3 > = 13
ecc.
Ogni disuguaglianza è una somma di una o più variabili, ed è sempre confrontata con una costante usando l'operatore > =. Non posso dire in anticipo quante disuguaglianze avrò ogni volta, ma tutte le variabili devono essere non negative, quindi è già una per ogni variabile.
Come risolvere questo sistema in modo tale che i valori delle variabili siano il più piccoli possibile?
Aggiunta: leggi l'articolo di Wikipedia e mi sono reso conto che ho dimenticato di menzionare che le variabili devono essere numeri interi. Immagino che questo renda NP-difficile, eh?
Soluzione
Ridurre al minimo x1 + x2 + ... dove xi soddisfa i vincoli lineari è chiamato Programmazione lineare. È trattato in dettaglio in Wikipedia
Altri suggerimenti
Quello che hai è un problema di programmazione lineare piuttosto semplice. Vuoi massimizzare l'equazione X_1 + ... + X_n
soggetta a
X_1 >= 2
X_2 + X_3 >= 13
etc.
Esistono numerosi algoritmi per risolvere questo tipo di problema. Il più noto è algoritmo simplex che risolverà la tua equazione (con alcuni avvertimenti) in modo abbastanza efficiente in il caso medio, sebbene esistano problemi di LP per i quali l'algoritmo Simplex richiederà esponenzialmente molti passaggi da risolvere (nella dimensione del problema).
Esistono varie implementazioni di solutori LP. Ad esempio LP_Solve dovrebbe soddisfare la maggior parte delle tue esigenze
Puoi anche pubblicare direttamente il tuo modello lineare sulla piattaforma NEOS ( http: / /neos.mcs.anl.gov/neos/solvers/index.html ). Quello che devi semplicemente fare per primo è scrivere il tuo modello in un linguaggio algebrico come AMPL. Quindi NEOS risolverà il modello e restituirà i risultati via e-mail.