L'algèbre (max,+) (se prononce max-plus) redéfinit les opérateurs addition et multiplication de l'algèbre classique par respectivement les opérateurs maximum noté $\oplus$ et addition noté $\otimes$ dans le domaine des nombres réels $\mathbb{R}$ augmenté du nombre moins l'infini ($\varepsilon = -\infty$) que l'on nomme $\mathbb{R}_{\varepsilon} = \mathbb{R} \cup \{ -\infty \}$. Sa structure algébrique est celle d'un dioïde selectif-inversible selon la classification de Gondran-Minoux (cette structure est appelée plus fréquemment semi-corps idempotent) $(\mathbb{R}_{\varepsilon}, \oplus, \otimes)$.
$$\forall a,b \in \mathbb{R}_{\varepsilon}: a \oplus b \triangleq \max(a,b)$$$$\forall a,b \in \mathbb{R}_{\varepsilon}: a \otimes b \triangleq a + b$$L'algèbre (min,+) (se prononce min-plus) redéfinit les opérateurs addition et multiplication de l'algèbre classique par respectivement les opérateurs minimum noté $\oplus$ et addition noté $\otimes$ dans le domaine des nombres réels $\mathbb{R}$ augmenté du nombre plus l'infini ($\varepsilon = +\infty$) que l'on nomme $\mathbb{R}_{\varepsilon} = \mathbb{R} \cup \{ +\infty \}$. Sa structure algébrique est celle d'un dioïde selectif-inversible selon la classification de Gondran-Minoux (cette structure est appelée plus fréquemment semi-corps idempotent) $(\mathbb{R}_{\varepsilon}, \oplus, \otimes)$.
$$\forall a,b \in \mathbb{R}_{\varepsilon}: a \oplus b \triangleq \min(a,b)$$$$\forall a,b \in \mathbb{R}_{\varepsilon}: a \otimes b \triangleq a + b$$Les algèbres Max-Plus ou Min-Plus sont parfois qualifiées de tropicales.
L'intérêt du calcul matriciel dans cette algèbre est enseigné dès les années 60 par J. Kuntzman dans sa théorie des réseaux. Elle est utilisée dans de nombreux domaines Recherche opérationnelle (théorie des réseaux), Physique (Quantification), Probabilité (transformée de Cramer), Automatique (systèmes à événements discrets), Informatique (théorie des automates, Réseaux de Pétri), Mathématiques (géométrie algébrique). On pourra consulter la bibliographie pour plus d'informations.
L'une des premières boîtes à outils Max-Plus disponibles a été fournie par l'INRIA avec le logiciel Scilab qui est devenu ScicosLab (fork) puis par son remplacement NSP (fork du fork). Le but essentiel de cette boîte à outil est de faciliter les calculs matriciels dans cette algèbre et tire parti du livre SYNCHRONIZATION AND LINEARITY: An Algebra for Discrete Event Systems.
Scilab n'étant plus maintenu par les auteurs originaux, un portage de la boîte à outils Max-Plus pour le langage Julia vous est proposé ici et dont le code est téléchargeable soit sur le dépôt GitHub https://github.com/Lecrapouille/MaxPlus.jl soit depuis le système de paquets de Julia avec la commande ] add MaxPlus. Notons qu'initiallement, cette boîte devait uniquement se focaliser sur l'algèbre (max,+) (vu que Scilab ne gère que le max+ et que ce projet était un portage) mais de fil en aiguille, des fonctions pour l'algèbre (min,+) ont été introduites (version >= 0.3.0) mais le nom du package MaxPlus.jl n'a pas changé.
Pour information, il existe autre paquet Julia TropicalNumbers dont le développement est actif. Il existe une boîte à outils pour Matlab http://www.stanczyk.pro/mpa/ mais dont le développement semble être abandonné. Mais aucune de ces boîtes à outils n'est un portage de Scilab.
Ce présent document va uniquement présenter comment installer la boîte à outils MaxPlus.jl et la démarer depuis un document Jupyter notebook. Les tutoriels suivants montreront les différentes fonctions qu'offre cette boîte à outils tout en introduisant les bases des algèbres (max,+) et (min,+) ainsi que des applications en relation avec ces algèbres.
Cette boîte à outils Max-Plus devrait fonctionner avec toutes les versions de Julia même celles obsolètes (versions 0.4 et 0.7). Certaines versions de Julia ont apporté des correctifs (sur les matrices creuses: version 1.3), d'autres ont apporté des régressions (version 1.0: matrice identité; version 1.4: produit matriciel matrice creuse avec matrice pleine; version 1.5: affichage des matrices creuses comme des matrices denses). D'autres bugs sont vieux (> 3 ans) et n'ont pas encore totallement corrigés (version 1.8) mais des correctifs sont automatiquement appliqués avec ce paquet Max-Plus mais peuvent impacter vos autres packages. Pour plus d'information, confère le fichier fallbacks.jl. Norallement la version de Julia >= 1.9 devrait contenir tous les correctifs des bugs détectés par l'auteur de cette boîte à outils.
Par conséquent, vérifions d'abord votre version de Julia :
VERSION
v"1.8.1"
Pour installer la boîte à outils Max-Plus Julia on a plusieurs options. Les codes suivants ne fonctionnent pas directement depuis ce document Jupyter, pensez donc à les décommenter et à les exécuter depuis le mode interactif Julia (REPL) :
# using Pkg; Pkg.add("MaxPlus")
# using Pkg; Pkg.add(PackageSpec(url="https://github.com/Lecrapouille/MaxPlus.jl"))
git clone https://github.com/Lecrapouille/MaxPlus.jl
cd MaxPlus.jl
julia
Il est important d'être correctement placé dans le dossier racine MaxPlus.jl !
Puis lancez le système de package Julia ] et tapez la ligne suivante :
# (@v1.8) pkg> add .
Maintenant que le paquet Julia Max-Plus vient d'être installé dans le système de Julia, on peut l'utiliser depuis le REPL de Julia via using MaxPlus. Il est beaucoup plus agréable d'utiliser Julia depuis un document Jupyter. Pour ce faire, il suffit de lancer un notebook Jupyter depuis le REPL avant le chargement de la boîte à outils. Voici les commandes à taper depuis votre REPL depuis le dossier racine MaxPlus.jl:
# using IJulia
# notebook()
Créer un nouveau document Jupyter, pensez à vérifier que votre document est connecté à Julia. Puis dans ce document Jupyter créé, chargez la boîte à outil Max-Plus depuis le dossier MaxPlus.jl:
push!(LOAD_PATH, pwd())
using MaxPlus
Tapons notre premier nombre Max-Plus :
MP(5)
(max,+) 5
Tapons notre premier nombre Min-Plus :
MI(5)
(min,+) 5
Cette boîte à outils permet de générer du code $\LaTeX$ via la fonction Base.show. Dans Jupyter ce mode semble être celui utilisé par défault, mais ici, on préfère garder l'affichage en texte plein. Pour cela on doit d'abord taper:
Base.show(io::IO, ::MIME"text/latex", x::MP) = show(io, MIME"text/plain", x)
Base.show(io::IO, ::MIME"text/latex", A::MPAbstractVecOrMat) = show(io, MIME"text/plain", A)
Si vous voyez le bon résultat, vous pouvez continuer les autres tutoriels qui vous présenteront l'API de cette boîte à outils ainsi qu'une introduction aux algèbres tropicales.