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: $\color {blue}x_1+x_2\leq 10,\\ x_1-3x_2\leq -5,~ -5x_1+x_2\leq -3$ deviennent $\color {blue}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 $\color {blue}z = -y$ a la solution réalisable de base $\color {blue}x_1=x_2=0$, $\color {blue}x_1-3x_2= -5+y$

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

Donc $\color {blue}x_1=1,~x_2=2,,~x_1-3x_2= -5,$
$\color {blue}5x_1+x_2= -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 $\color {blue}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 à $\color {blue}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 $\color {blue}z$ s'il y en a). Donc deux possibilités,

  1. choisir les équations à supprimer et à rajouter comme normale avec un choix aléatoire quand plus d'un candidat
    peut marcher de façon acceptable quand il existe une meilleur solution mais risque de ne peut pas trouver qu'il n'y en a pas.
  2. ajouter (virtuellement) une petite quantité $\color {blue}\epsilon_i$ à la constante $\color {blue}b_i$ de la contrainte $\color {blue}i$;
    Agir comme si $\color {blue}1 >> \epsilon_1 >> \epsilon_2 >> \epsilon_3\cdots$;
    Impossibilité d'avoir plus de $\color {blue}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 dual d'un programme linéaire
Motivation
Une solution réalisable d'un programme (de minimisation) donne un $\color {blue}z$ possible, donc un majorant du $\color {blue}z$ optimal.

Je peux aussi déduire des minorants de $\color {blue}z$ par manipulation directe des inéquations:

$\color {blue}\begin{array}{rrrrrrrcr}
10&10&20&50&0&40&25& ~~x~\geq~~ &100 \\
...
...15& &100 \\
30&50&40&5&5&20&10& &100 \\
0&0&0&0&50&30&0& &100 \\
\end{array}$

Si je calcule $\color {blue}2/5\times$ (1) + $\color {blue}2/3\times$ (2), j'obtiens
$\color {blue}37.33x_1+44x_2+34.67x_3+20x_4+16x_6+20x_7$
$\color {blue}\geq 106.67$
Donc $\color {blue}z=40x_1+50x_2+50x_3+60x_4+30x_5+20x_6+20x_7\geq 106.67$

Quel est le meilleur minorant que je peux trouver de cette façon?

Le problème de base: maximiser $\color {blue}\displaystyle \sum_{j=1}^n c_jx_j$
avec $\color {blue}\displaystyle m$ contraintes $\color {blue}\displaystyle \sum_{j=1}^n a_{i,j}x_j \leq b_i$
et $\color {blue}\displaystyle x_j \geq 0$

En essayant de trouver un majorant de la solution, j'ai cherché des multiplicateurs $\color {blue}\displaystyle y_i$ pour les contraintes avec les propriétés:
$\color {blue}\displaystyle y_i \geq 0$
$\color {blue}\displaystyle \sum_{i=1}^m a_{i,j}y_i \geq c_j$
Et je veux trouver un ensemble de tels multiplicateurs qui me donne la valeur la plus petite possible de $\color {blue}\displaystyle \sum_{i=1}^m b_i y_i$.

Un nouveau programme linéaire!
appelé le dual.

Propriété évidente: chaque solution réalisable du dual est supérieure ou égale à chaque solution réalisable du problème de base.

Le dual du dual

Le dual, à savoir minimiser $\color {blue}\displaystyle \sum_{i=1}^m b_i y_i$ avec les contraintes $\color {blue}\displaystyle \sum_{i=1}^m a_{i,j}y_i \geq c_j$ équivaut à maximiser $\color {blue}\displaystyle \sum_{i=1}^m -b_i y_i$ avec les contraintes $\color {blue}\displaystyle \sum_{i=1}^m -a_{i,j}y_i \leq -c_j$.
(pour l'exprimer en forme canonique)

On a multiplié les deux vecteurs $\color {blue}\displaystyle \bf b$ et $\color {blue}\bf c$ et la matrice $\color {blue}\bf a$ par $\color {blue}\displaystyle -1$, échangé les 2 vecteurs et transposé la matrice.

Donc, si on le fait une deuxième fois pour obtenir le dual du dual, on trouve le problème de base.

Les deux problèmes ont la même solution!
(c'est-à-dire la même valeur optimale de la fonction objective)

Le théorème le plus important de la programmation linéaire.

Démonstration compliquée.

Mais, il n'est pas difficile de voir que l'algorithme du simplexe calcule (dans le cas d'un programme faisable et borné) une valeur qui est une solution réalisable des deux problèmes;
donc, forcément la solution optimale des deux.

L'interprétation économique de la solution du dual
La solution du problème dual (c'est-à-dire les $\color {blue}\displaystyle y_i$) nous dit par combien la solution optimale ( $\color {blue}\displaystyle z$) va changer si la contrainte (numéro $\color {blue}\displaystyle i$) est modifiée.
(parce que la valeur trouvée pour $\color {blue}z$ est $\color {blue}\sum_i b_iy_i$)

Si $\color {blue}\displaystyle z$ est mon profit, $\color {blue}y_i$ est le maximum que je devrait payer (par unité) pour lâcher la contrainte (acheter plus d'une matière de base ...)

Les méthodes plus récentes
Depuis une vingtaine d'années de nouveaux algorithmes existent avec des différences importantes par rapport à celui du simplexe:


next up previous
Next: About this document ...
Mike ROBSON
2001-11-21