Une optimisation évidente de l'algorithme du simplexe consiste à confier le soin des additions et multiplications à un ordinateur. On sera néanmoins attentif à ne pas sous-traiter la réflexion, qui constitue le coeur du métier d'ingénieur.
Le programme mk_simplex (LISTING 1) a pour
objectif de créer toutes les variables auxiliaires nécessaires à la
transformation des inéquations en équations et à la transformation
des contraintes non satisfaites par l'origine du problème initial
en contraintes satisfaites par l'origine d'un problème de plus grande
taille. Pour des raisons de commodité, les trois sortes de variables
s'appellent toutes 
, l'indice variant de 
à 
pour les
variables naturelles, de 
à 
pour les variables "
"
et de 
à la fin pour les variables "
".
En sortie, 
contient les équations récrites, 
est l'ensemble
de toutes les variables, 
est l'ensemble des variables ""
et 
est la liste des coordonnées dont l'égalité à 0 caractérise
le point où l'on se trouve.
Le programme pt_vue (LISTING 2) est un programme
"cosmétique" destiné à récrire l'ensemble des équations
du point de vue du sommet où l'on se trouve. L'écriture effective
de ce programme est tout à fait simple (on utilise 
pour résoudre),
mais est loin d'être optimale. En effet, une étape est caractérisée
par l'échange de rôles entre une variable "actuellement principale"
et une variable "actuellement auxiliaire" : une
résolution de proche en proche serait plus rapide.
Le programme avance (LISTING 5) exécute le déplacement
consistant en l'échange des rôles entre la variable principale 
,
choisie par l'utilisateur, et la variable auxiliaire exerçant la contrainte
la plus forte. Le cas exceptionnel où l'on trouve un mouvement 
ne se produit qu'en présence de contraintes redondantes.
Enfin, le programme randavance (LISTING 6) détermine quels sont les pivots possibles (variables ayant une influence positive sur la fonction de bénéfice) et en choisit un aléatoirement.
est considérée
comme une fonction de coût...
)
![$ \left[400. ; 500.\right]$](img158.png){kind=small}
, lagr=
![$ \left[0. ; 4. ; 1.333\right]$](img159.png){kind=small}
,
ff=
au
point 4 ci-dessus
![\begin{algorithm}
% latex2html id marker 1014
[!h]
\begin{algorithmic}[1]
\par
\...
...\par
\end{algorithmic}\par
\caption{Incantations initiales}
\par
\end{algorithm}](img161.png)
Les sorties se font à l'écran et dans un fichier. La fonction mymprint gère cela. Avec funcprot(0), on évite le message "fonction redéfinie". Avec ieee(2), une division par 0 engendre le nombre %inf et non une erreur. Avec myseed, on initialise le générateur aléatoire (utile pour debug).
![\begin{algorithm}
% latex2html id marker 1035
[!h]
\begin{algorithmic}[1]
\par
\...
...) }
\par
\end{algorithmic}\par
\caption{Entrée des données}
\par
\end{algorithm}](img162.png)
La matrice 
regroupe toutes les données du système. Les contraintes
supérieures sont entrées comme des contraintes ordinaires. Les formats
d'affichage (fff pour la matrice et fvu pour la vue) sont construits
d'après les données.
![\begin{algorithm}
% latex2html id marker 886
[htbp]
\begin{algorithmic}[1]
\par
...
...t des inégalités, création des variables supplémentaires.
}
\par
\end{algorithm}](img135.png)
![\begin{algorithm}
% latex2html id marker 930
[htbp]
\begin{algorithmic}[1]
\par
...
...fichage du système (du point de vue du sommet en cours).
}
\par
\end{algorithm}](img148.png)
![\begin{algorithm}
% latex2html id marker 941
[htbp]
\begin{algorithmic}[1]
\par
...
... de l'algorithme (avec choix du pivot par l'utilisateur).
}
\par
\end{algorithm}](img151.png)
![\begin{algorithm}
% latex2html id marker 951
[htbp]
\begin{algorithmic}[1]
\par
...
...right)$\ ;
\par
\end{algorithmic}
\par
\caption{randavan}
\par
\end{algorithm}](img152.png)
![\begin{algorithm}
% latex2html id marker 961
[htbp]
\begin{algorithmic}[1]
\par
...
... de l'algorithme (avec choix du pivot par l'utilisateur).
}
\par
\end{algorithm}](img153.png)
![\begin{algorithm}
% latex2html id marker 970
[htbp]
\begin{algorithmic}[1]
\par
...
...e étape de l'algorithme (avec choix aléatoire du pivot).
}
\par
\end{algorithm}](img154.png)