\include{header}

\begin{slide}{}
\heading{
l'algorithme du simplexe
}

Algorithme efficace  pour r\'esoudre des probl\`emes de programmation lin\'eaire

(ou de trouver qu'il n'y a pas de solution)

Beaucoup utilis\'e et r\'eussit sur les probl\`emes ``r\'eels''

Th\'eoriquement trop lent pour des probl\`emes tr\`es bizarres
\end{slide}


\begin{slide}{}
\heading{
L'id\'ee de base  (g\'eom\'etrique)
}

\begin{itemize}
\item Choisir une solution r\'ealisable de base (sommet du polytope)
%\item Choisir une ar\^ete du polytope partant de ce sommet sur laquelle la
%fonction objective monte
%\item Parcourir cette ar\^ete jusqu'\`a un autre sommet
\item Si la fonction objective a une valeur sup\'erieure \`a un sommet
voisin, aller \`a ce sommet
\item R\'ep\'eter (tant que possible...)
\end{itemize}
\end{slide}

\begin{slide}{}
\heading{
Pourquoi \c{c}a marche?
}

Chaque ar\^ete 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'\`a une solution optimale (s'il y en a)

Comment est-ce que \c{c}a s'arr\^ete?

%Aucune ar\^ete sur laquelle la  fonction objective monte (optimum trouv\'e)

%ou aucun sommet plus loin sur l'ar\^ete (aucune borne sur \colmath{z})

Aucun sommet voisin avec une valeur sup\'erieure de \colmath{z}

On a trouv\'e la valeur optimale (si elle existe)

\end{slide}

\begin{slide}{}
\heading{
C'est quoi, un sommet voisin?
}
\begin{itemize}
\item Le sommet actuel est d\'etermin\'e par \colmath{n} \'equations
\item Une ar\^ete du polytope qui
passe par ce sommet est d\'etermin\'ee par \colmath{n-1} parmi elles
\item Un voisin est donn\'ee par les \colmath{n-1} et une nouvelle \'equation
\item Un ensemble de \colmath{n-1} des \'equations actuelles et une nouvelle
peut \'echouer (aucune solution ou plusieurs solutions
ou pas r\'ealisable ou valeur pas am\'elior\'ee)
\item Sur une ar\^ete il n'y a que deux solutions de base r\'ealisables
\end{itemize}
\end{slide}


\begin{slide}{}
\heading{
Un tr\`es petit exemple de parcours it\'eratif calcul\'e de fa\c{c}on na\"{\i}ve
}
Deux variables \colmath{x_1} et \colmath{x_2}\\
Deux contraintes explicites: \colmath{3x_1+2x_2~\leq~30}\\
\colmath{-2x_1+x_2~\leq~8}\\
les \colmath{2} contraintes implicites: \colmath{x_1,~x_2~\geq~0}\\
\colmath{z~=~-3x_1+2x_2} \`a maximiser.

La solution de base \colmath{x_1=x_2=0} est r\'ealisable avec \colmath{z=0}.
Les solutions voisines sont obtenues en supprimant une des \'equations
\colmath{x_1=0} ou \colmath{x_2=0} et en ajoutant une des \'equations\\\colmath{3x_1+2x_2~=~30}
ou \colmath{-2x_1+x_2~=~8}

\end{slide}

\begin{slide}{}

Donc quatre possibilit\'es:

\begin{itemize}
\item \colmath{x_1=0,~3x_1+2x_2~=~30}: \colmath{x_2=15} n'est pas r\'ealisable.
\item \colmath{x_1=0,~-2x_1+x_2~=~8}: \colmath{x_2=8} r\'ealisable avec \colmath{z=16}.
\item \colmath{x_2=0,~3x_1+2x~=~30}: \colmath{x_1=10} r\'ealisable avec \colmath{z=-30}.
\item \colmath{x_2=0,~-2x_1+x_2~=~8}: \colmath{x_1=-4} n'est pas r\'ealisable.
\end{itemize}
\end{slide}

\begin{slide}{}
On continue de la solution:\\\colmath{x_1=0,~-2x_1+x_2~=~8,~~~z=16}.

Supprimer une des \'equations:\\\colmath{x_1=0,~-2x_1+x_2~=~8}\\
Ajouter une \'equation choisie parmi\\\colmath{x_2=0,~~3x_1+2x~=~30}

En fait on ne trouve qu'une nouvelle solution:\\
\colmath{3x_1+2x_2~=~30,~-2x_1+x_2~=~8}:\\\colmath{x_1=2,~x_2=12}
r\'ealisable avec \colmath{z=18}, donc une am\'elioration.

Et ainsi de suite (mais pour ce petit exemple il n'y a
plus de possibilit\'es d'am\'elioration).
\end{slide}

\begin{slide}{
Impressionnant?
}
Non !
On a fait 3 it\'erations et pour chaque it\'eration
on calcule 4 voisins; donc 12 sommets calcul\'es\\
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\'erations (un peu pessimiste),
on n'en calcule que \colmath{40 \times 10 \times 10 ~=~ 4000}.\\
(Et on va voir que le vrai algorithme fait encore moins de calcul)

Plus la taille du probl\`eme est \'elev\'ee, plus cette m\'ethode
gagne par rapport \`a la m\'ethode tr\`es na\"{\i}ve de calculer toutes
les solutions de base.
\end{slide}

\begin{slide}{
Le ``vrai'' algorithme du simplexe de Dantzig
}
Calcul beaucoup plus vite d'un bon voisin

On consid\`ere d'abord le cas o\`u \colmath{(0,0, ... ,0)} est une
solution de base r\'ealisable
et l'algorithme part de l\`a:

On va supprimer une seule des \'equations \colmath{x_j=0}; donc cette
variable \colmath{x_j} va devenir positive et les autres resteront nulles.
Donc, il faut choisir une variable \`a coefficient positif en \colmath{z}.

En choisir une (peut-\^etre mais pas forc\'ement celle au coefficient le plus \'elev\'e?)

Chaque contrainte avec un coefficient \colmath{a_{i,j}>0} donne une borne
sup\'erieure sur la nouvelle valeur de \colmath{x_i};

Choisir la plus petite de ces bornes; c'est la contrainte qu'il
faut rajouter.
\end{slide}

\begin{slide}{Efficacité améliorée}

Une manipulation simple algébrique (le pivotage) remet le programme dans une forme où la nouvelle
solution de base est \colmath{(0,0, ... ,0)} pour un choix différent
de variables, ce qui permet de continuer de la même façon.
\end{slide}

\begin{slide}{
Deux Problèmes avec l'algorithme du simplexe}
\heading{
(1) Am\'elioration nulle
}
Comment? Si le nombre d'\'equations des contraintes v\'erifi\'ees \`a
une solution est sup\'erieure \`a \colmath{n}.\\
Une it\'eration jette une contrainte et en ajoute une autre ;
\c{c}a peut donner la m\^eme solution.\\
Et l'algorithme pourrait boucler (m\^eme point ; ensembles diff\'erents
d'\'equations).

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

Un programme robuste doit \^etre capable de traiter ce cas.

Et une règle simple suffit: à chaque choix (colonne ou ligne du pivot),
choisir la première variable possible pour sortir ou entrer.

\end{slide}

\begin{slide}{}
\heading{
Trouver une solution de base pour commencer
}

\begin{itemize}
\item Modifier le probl\`eme de sorte que le nouveau probl\`eme
\colmath{auxiliaire} aie une solution
de base triviale et une solution optimale du nouveau
probl\`eme  soit forc\'ement une solution
r\'ealisable (de base) de l'ancien ;
\item R\'esoudre ce nouveau probl\`eme par\\l'algorithme du simplexe !
\item Enfin commencer a r\'esoudre le vrai probl\`eme.
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{itemize}
\item Pour construire le nouveau probl\`eme:
\begin{itemize}
\item Ajouter une nouvelle variable, disons \colmath{y} (avec \colmath{y\ge 0})
\item Remplacer toute contrainte \colmath{lin~\leq ~const} par \colmath{lin-y \leq ~const}
(et transformer dans la forme canonique)
\item Il existe une solution r\'ealisable  de base avec \colmath{n+1}
\'equations v\'erifi\'ees
\item Minimiser \colmath{y} (maximiser \colmath{-y}) ; si le r\'esultat est nul,
on a trouv\'e une solution
r\'ealisable  de base
de l'ancien probl\`eme ; sinon il n'y en a pas.
\end{itemize}
\end{itemize}
\end{slide}


\end{document}
