Méthode des plans sécants
Cet article est une ébauche concernant les mathématiques et l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En mathématiques, et spécialement en optimisation linéaire en nombres entiers, la méthode des plans sécants, ou cutting plane method, est une méthode utilisée pour trouver une solution entière d'un problème d'optimisation linéaire. Elle fut introduite par Ralph E. Gomory puis étudiée par Gomory et Václav Chvátal.
Principe
Le principe de la méthode est d'ajouter des contraintes au programme linéaire pour le raffiner, et le rapprocher des solutions intégrales[1]. Plus précisément, étant donné un ensemble de contraintes, et une solution optimale x* au problème d'optimisation linéaire, la méthode consiste à créer de nouvelles contraintes, telle que la solution entière optimale est conservée, mais x* viole l'une des nouvelles contraintes[2].
Notes et références
Voir aussi
Articles connexes
- Séparation et évaluation
- Branch and cut
v · m Optimisation mathématiques et algorithmiques | |||||||
---|---|---|---|---|---|---|---|
Non linéaire |
| ||||||
Convexe |
| ||||||
Combinatoire | |||||||
Métaheuristique | |||||||
Liste |
- Portail des mathématiques
- Portail de l'informatique théorique