Une solution où n des équations correspondant aux contraintes sont
satisfaites
(c'est-à-dire les équations obtenues en remplacant
par =)
Un sommet du polytope
théorème : si la fonction objective est bornée, elle prend sa valeur optimale à une solution de base
Donc un algorithme possible:
calculer chaque solution de base;
vérifier qu'elle est réalisable;
si oui calculer la fonction objective;
prendre le maximum des valeurs calculées.
Mais ca serait très très lent ...
Des contraintes réelles qu'on ne peut pas exprimer (directement) par des contraintes linéaires.
]
ou
,
..., coûts régressifs)
Algorithme efficace (...) pour résoudre des problèmes de programmation linéaire
(ou de trouver qu'il n'y a pas de solution)
Beaucoup utilisé et réussit sur les problèmes ``réels''
Théoriquement trop lent pour des problèmes très bizarres
Chaque arête parcourue augmente la fonction objective: donc pas de boucles
Le nombre de sommets est fini: donc terminaison garantie
Pas de maximaux locaux qui ne sont pas de maximaux globaux: donc l'algorithme ne peut se terminer qu'à une solution optimale (s'il y en a)
Comment est-ce que ça s'arrête?
Aucun sommet voisin avec une valeur supérieure de z
On a trouvé la valeur optimale (si elle existe)
La solution de base x1=x2=0 est réalisable avec z=0.
Les solutions voisines sont obtenues en supprimant une des équations
x1=0 ou x2=0 et en ajoutant une des équations
3x1+2x2 = 30
ou -2x1+x2 = 8
Donc 4 possibilités:
On continue de la solution:
x1=0, -2x1+x2 = 8, z=16.
Supprimer une des équations:
x1=0, -2x1+x2 = 8
Ajouter une équation choisie parmi
x2=0, 3x1+2x = 30
En fait on ne trouve qu'une nouvelle solution:
3x1+2x2 = 30, -2x1+x2 = 8:
x1=2, x2=12
réalisable avec z=18, donc une amélioration.
Et ainsi de suite (mais pour ce petit exemple il n'y a plus de possibilités d'amélioration).
On a fait 3 itérations et pour chaque itération
on calcule 4 voisins; donc 12 sommets calculés
sur les 6 qui existent!
Mais pour un exemple de taille raisonnable c'est mieux:
10 variables et 10 contraintes explicites: 184756 sommets
Si l'algorithme prend 40 itérations (un peu pessimiste),
on n'en calcule que
40 x 10 x 10 = 4000.
Plus la taille du problème est élevée, plus ce méthode gagne par rapport à la méthode naïve de calculer toutes les solutions de base.