next up previous
Next: About this document ...

Solutions de base

Une solution où n des équations correspondant aux contraintes sont satisfaites
(c'est-à-dire les équations obtenues en remplacant $\le$ 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 ...

Limitations:

Des contraintes réelles qu'on ne peut pas exprimer (directement) par des contraintes linéaires.

l'algorithme du simplexe

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

L'idée de base (géométrique)

Pourquoi ça marche?

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)

C'est quoi, un sommet voisin?

Un très petit exemple
2 variables x1 et x2
2 contraintes explicites: $3x_1+2x_2~\leq~30$
$-2x_1+x_2~\leq~8$
les 2 contraintes implicites: $x_1,~x_2~\geq~0$
z = -3x1+2x2 à maximiser.

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).

Impressionnant?
Non.

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.




next up previous
Next: About this document ...
Mike ROBSON
2000-10-04