Come risolvere un sistema di disuguaglianze?

Question

Ho ridotto il mio problema (algoritmo di layout di tabella) al seguente problema:

Immagina di avere N variabili X ₁ , X ₂ , ..., X _N . Ho anche un certo numero (indeterminato) di disuguaglianze, come:

X ₁ > = 2
x ₂ + X ₃ > = 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?

Answer 1

Ridurre al minimo x1 + x2 + ... dove xi soddisfa i vincoli lineari è chiamato Programmazione lineare. È trattato in dettaglio in Wikipedia

Answer 2

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

Answer 3

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.

Answer 4

Programmazione lineare