La valeur optimale des programmes entiers - 04/04/08
pages | 4 |
Iconographies | 0 |
Vidéos | 0 |
Autres | 0 |
Note présentée par Michèle Vergne
Résumé |
On donne une expression de la valeur optimale fc(y) du programme entier max{c′xxΩ(y)Nn} où Ω(y) est le polyèdre convexe {xRnAx=y,x⩾0}. Elle est une conséquence de la formule de Brion et Vergne qui évalue la somme ∑xΩ(y)Nnec′x. On montre que comme en programmation linéaire, fc(y) peut être obtenue par inspection des coûts réduits aux sommets du polyèdre. On donne aussi un résultat explicite qui relie fc(ty) à la valeur optimale du programme linéaire associé, pour des valeurs de tN suffisamment grandes. Pour citer cet article : J.B. Lasserre, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 863-866.
Le texte complet de cet article est disponible en PDF.Abstract |
We present a formula for the optimal value fc(y) of the integer program max{c′xxΩ(y)Nn} where Ω(y) is the convex polyhedron {xRnAx=y,x⩾0}. It is a consequence of Brion and Vergne's formula which evaluates the sum ∑xΩ(y)Nnec′x. As in linear programming, fc(y) can be obtained by inspection of the reduced-costs at the vertices of the polyhedron. We also provide an explicit result that relates fc(ty) and the optimal value of the associated continous linear program, for large values of tN. To cite this article: J.B. Lasserre, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 863-866.
Le texte complet de cet article est disponible en PDF.Plan
Vol 335 - N° 11
P. 863-866 - décembre 2002 Retour au numéroBienvenue sur EM-consulte, la référence des professionnels de santé.
L’accès au texte intégral de cet article nécessite un abonnement.
Bienvenue sur EM-consulte, la référence des professionnels de santé.
L’achat d’article à l’unité est indisponible à l’heure actuelle.
Déjà abonné à cette revue ?