Comment résoudre un système d'inégalités?
https://stackoverflow.com/questions/1432580
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai réduit mon problème (algorithme de présentation de table) au problème suivant:
Imaginez que j'ai N variables X 1 , X 2 , ..., X N . J'ai aussi un nombre (non déterminé) d'inégalités, comme:
X 1 > = 2
x 2 + X 3 > = 13
etc.
Chaque inégalité est la somme d'une ou de plusieurs variables et est toujours comparée à une constante à l'aide de l'opérateur > =. Je ne peux pas dire à l'avance combien d'inégalités j'aurai à chaque fois, mais toutes les variables doivent être non négatives, donc c'est déjà une pour chaque variable.
Comment résoudre ce système de telle sorte que les valeurs des variables soient aussi petites que possible?
Ajouté: Lisez l'article de Wikipédia et réalisez que j'ai oublié de mentionner que les variables doivent être des entiers. Je suppose que ça rend NP-difficile, hein?
La solution
Minimiser x1 + x2 + ... où xi vérifie les contraintes linéaires est appelé programmation linéaire. Il est couvert en détail dans Wikipedia
.Autres conseils
Vous avez un problème assez fondamental de Programmation linéaire . Vous souhaitez maximiser l'équation X_1 + ... + X_n en fonction de
X_1 >= 2
X_2 + X_3 >= 13
etc.
Il existe de nombreux algorithmes pour résoudre ce type de problème. Le plus connu est l’ ?? algorithme simplex qui résoudra votre équation (avec certaines mises en garde) de manière très efficace dans le cas moyen, bien qu'il existe des problèmes LP pour lesquels l'algorithme Simplex nécessitera de manière exponentielle beaucoup d'étapes à résoudre (dans la taille du problème).
Il existe différentes implémentations de solveurs LP. Par exemple, LP_Solve devrait répondre à la plupart de vos besoins
Vous pouvez également publier directement votre modèle linéaire sur la plate-forme NEOS ( http: / /neos.mcs.anl.gov/neos/solvers/index.html ). Ce que vous devez simplement faire en premier lieu, c'est écrire votre modèle dans un langage algébrique tel que AMPL. Ensuite, NEOS résoudra le modèle et renverra les résultats par courrier électronique.
