next up previous
Next: About this document ...

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

Basé sur deux idées importantes:

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 $\color {blue}z$

On a trouvé la valeur optimale (si elle existe)

C'est quoi, un sommet voisin?

Un très petit exemple de parcours itératif calculé de façon naïve
Deux variables $\color {blue}x_1$ et $\color {blue}x_2$
Deux contraintes explicites: $\color {blue}3x_1+2x_2~\leq~30$
$\color {blue}-2x_1+x_2~\leq~8$
les $\color {blue}2$ contraintes implicites: $\color {blue}x_1,~x_2~\geq~0$
$\color {blue}z~=~-3x_1+2x_2$ à maximiser.

La solution de base $\color {blue}x_1=x_2=0$ est réalisable avec $\color {blue}z=0$. Les solutions voisines sont obtenues en supprimant une des équations $\color {blue}x_1=0$ ou $\color {blue}x_2=0$ et en ajoutant une des équations
$\color {blue}3x_1+2x_2~=~30$ ou $\color {blue}-2x_1+x_2~=~8$

Donc quatre possibilités:

On continue de la solution:
$\color {blue}x_1=0,~-2x_1+x_2~=~8,~~~z=16$.

Supprimer une des équations:
$\color {blue}x_1=0,~-2x_1+x_2~=~8$
Ajouter une équation choisie parmi
$\color {blue}x_2=0,~~3x_1+2x~=~30$

En fait on ne trouve qu'une nouvelle solution:
$\color {blue}3x_1+2x_2~=~30,~-2x_1+x_2~=~8$:
$\color {blue}x_1=2,~x_2=12$ réalisable avec $\color {blue}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 $\color {blue}40 \times 10 \times 10 ~=~ 4000$.
(Et on va voir que le vrai algorithme fait encore moins de calcul)

Plus la taille du problème est élevée, plus cette méthode gagne par rapport à la méthode très naïve de calculer toutes les solutions de base.

Le ``vrai'' algorithme du simplexe de Dantzig
Calcul beaucoup plus vite d'un bon voisin

On considère d'abord le cas où $\color {blue}(0,0,\cdots,0)$ est une solution de base réalisable et l'algorithme part de là:

On va supprimer une seule des équations $\color {blue}x_i=0$; donc cette variable $\color {blue}x_i$ va devenir positive et les autres resteront nulles. Donc, il faut choisir une variable à coefficient positif en $\color {blue}z$.

En choisir une (peut-être mais pas forcément celle au coefficient le plus élevé?)

Chaque contrainte avec un coefficient $\color {blue}a_{i,j}>0$ donne une borne supérieure sur la nouvelle valeur de $\color {blue}x_i$;

Choisir la plus petite de ces bornes; c'est la contrainte qu'il faut rajouter.

Comment continuer?

Une astuce algébrique permet de continuer à faire les calculs de la même façon efficace

Transformer le problème en ``forme standard''.

C'est la forme où les seules contraintes sont que chaque variable est positive ou nulle et des contraintes dans la forme d'équations. La transformation s'effectue en ajoutant une nouvelle variable ``variable d'écart'' pour chaque contrainte d'inéquation:

Par exemple $\color {blue}3x_1+2x_2~\leq~30$ devient $\color {blue}3x_1+2x_2+x_3~=~30$ $\color {blue}x_3$ est la variable d'écart, contrainte d'être positive ou nulle.

Le même exemple
$\color {blue}\begin{array}{rrrrl}
3x_1&+2x_2&+x_3&&=30\\
-2x_1&{\color {red}+x...
...=2\\
&+x_2&+2x_3/7&+3x_4/7&=12\\
&&-x_3/7&-12x_4/7&=(z)-18\\
\\
\end{array}$

En pratique on garde les coefficients dans un tableau et supprime les colonnes connues ne contenir qu'un élément non nul etc. mais ce ne sont que des détails de programmation.



next up previous
Next: About this document ...
Mike ROBSON
2001-10-12