next up previous
Next: About this document ...

Deux problèmes avec la méthode du simplexe

Trouver une solution de base pour commencer

Un petit exemple

Les contraintes: $x_1+x_2\leq 10,\\ x_1-3x_2\leq -5,~ -5x_1+x_2\leq -3$ deviennent $x_1+x_2\leq 10+y,~ x_1-3x_2\leq -5+y,\\ -5x_1+x_2\leq -3+y$

et le problème avec ces contraintes et la fonction objective z = -y a la solution réalisable de base x1=x2=0, x1-3x2= -5+y

Une solution optimale est $x_1=1,~x_2=2,\\ y=0,~x_1-3x_2= -5+y,
~ -5x_1+x_2= -3+y$

Donc x1=1, x2=2,, x1-3x2= -5,
5x1+x2= -3 est une solution réalisable de base du vrai problème.

Et les équations vérifiées à cette solution du vrai problème se trouve en supprimant le y= 0 dans les équations de la solution optimale du problème auxiliaire!

Amélioration nulle
Comment? Si le nombre d'équations des contraintes vérifiées à une solution est supérieure à n.
Une itération jette une contrainte et en ajoute une autre; ça peut donner la même solution.
Et l'algorithme pourrait boucler (même point; ensembles différents d'équations).

Mais il existe au moins un bon ensemble d'équations qui permet à l'algorithme de continuer (vraie amélioration de z s'il y en a). Donc,

1.
choisir les équations à supprimer et à rajouter comme normale avec un choix aléatoire quand plus d'un candidat
marche de façon acceptable quand il existe une meilleur solution mais ne peut pas trouver qu'il n'y en a pas.
2.
ajouter (virtuellement) une petite quantité $\epsilon_i$ à la constante bi de la contrainte i;
Agir comme si $1 >> \epsilon_1 >> \epsilon_2 >> \epsilon_3\cdots$;
Impossibilité d'avoir plus de n équations vérifiées!!
Et on résout un programme indistinguable de l'initial!

Pourquoi ne pas jeter les contraintes inutiles?
Trop difficile de les trouver!

Le ``vrai'' algorithme du simplexe de Dantzig
1
Calcul beaucoup plus vite de la première itération dans le cas où $(0,0,\cdots,0)$ est une solution de base réalisable:

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

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

Chaque contrainte avec un coefficient ai,j>0 donne une borne supérieure sur la nouvelle valeur de xi;

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



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