Présentation du logiciel G2DS

Un programme linéaire est défini par un ensemble de contraintes linéaires et une fonction objectif linéaire. Nous nous intéresserons exclusivement ici aux programmes linéaires contenant 2 variables, x et y, ce qui signifie que toute contrainte s'écrira « ax + by op c » (avec op valant « ≥ », « = » ou « ≤ ») et que la fonction objectif s'écrira « min/max (dx + ey) » (min pour « minimiser » et max pour « maximiser »), où a, b, c, d et e sont des constantes.

En résumé, résoudre un programme linéaire consiste à optimiser (minimiser ou maximiser) une fonction linéaire sur un ensemble convexe (polyèdre) correspondant, en dimension 2, à un polygone (éventuellement vide ou non borné). Dans la suite, ce polygone sera appelé polygone admissible ou polygone des contraintes. Les « côtés » du polygone sont appelés facettes. Le point commun à deux facettes adjacentes est appelé sommet, point de base ou (avec un léger abus de langage) solution de base admissible. Si la valeur optimale d'un programme linéaire donné (i.e., la meilleure valeur qu'une de ses solutions de base admissibles puisse prendre) est finie et est notée z^*, et que sa fonction objectif est « [opt] (dx + ey) » (où [opt] vaut min ou max), alors la droite d'équation « dx + ey = z^* » est appelée droite optimale.

Si on impose en outre que les variables x et y ne prennent que des valeurs entières, alors le problème obtenu est appelé programme linéaire en nombres entiers.

Ce logiciel est implémenté, dans sa version actuelle, sous la forme d'un programme Java (et plus précisément distribué sous la forme d'une archive JAR). Comme tout programme Java, cela signifie que, pour l'exécuter, vous aurez besoin qu'une machine virtuelle Java (appelée Java Virtual Machine -ou JVM- en anglais) soit présente sur votre ordinateur.

La commande de base à écrire dans une console ou un terminal pour exécuter un programme Java nommé G2DS et fourni sous forme d'archive JAR (et dont le nom complet est par conséquent « G2DS.jar ») est la suivante (où « java » est précisément le nom du programme correspondant à la JVM, et où « > » est le symbole de l'invite de commande) :

• La première ligne du fichier contient la fonction objectif, au format « OPT sep coefficient de x sep coefficient de y ». Ici, « OPT » vaut soit « MIN » (si on veut minimiser la fonction objectif), soit « MAX » (si on veut maximiser la fonction objectif), soit n'importe quoi d'autre sauf « . » (si on ne souhaite pas définir de fonction objectif). L'information « coefficient de x » (respectivement « coefficient de y ») est évidemment le coefficient de x (respectivement celui de y) dans la fonction objectif ainsi définie.


• Chacune des autres lignes du fichier (sauf la dernière) représente une contrainte, au format « coefficient de x sep coefficient de y sep sens inégalité sep second membre ». Ici, les informations « coefficient de x » et « coefficient de y » sont évidemment les coefficients de x et de y, respectivement, dans cette contrainte, « second membre » est la valeur du second membre (ou membre de droite) de la contrainte, et « sens inégalité » est le couple de symboles représentant le sens de la contrainte (« <= » pour « ≤ », et « >= » pour « ≥ »).


• Enfin, la dernière ligne du fichier ne contient que le seul caractère « . », qui indique la fin du fichier.

Une fonction objectif se définit quasiment de la même manière qu'une contrainte. Les 2 champs de texte de la 1^ère ligne correspondent respectivement au coefficient de x et au coefficient de y dans la fonction objectif (les 3 remarques de la section précédente portant sur la procédure de saisie des données s'appliquent également dans ce cas). Sélectionnez ensuite « min » (pour minimiser), « max » (pour maximiser) ou « aucune » (pour ne définir aucun objectif), puis appuyez sur le bouton « Définir ». La résolution du programme linéaire se lance alors automatiquement. Notez que, à chaque fois qu'une nouvelle fonction objectif est redéfinie (en appuyant sur « Définir »), l'ancienne est effacée.

La zone de statut est située sous les 3 lignes de saisie du logiciel, juste au-dessus de la zone où s'affiche la représentation graphique du problème. Cette zone de statut, qui s'affiche en rouge, est utilisée par le logiciel pour vous avertir du statut courant de la résolution (nombre de solutions de base admissibles, valeur optimale, affichage ou non des solutions entières, etc.). Lors d'une utilisation du logiciel, vous pouvez bien sûr ajouter autant de contraintes que vous le voulez (la limite étant celle du temps de calcul !) et redéfinir la fonction objectif autant de fois que vous le souhaitez. À chaque fois qu'une contrainte est ajoutée ou retirée, le polygone des contraintes se met à jour automatiquement (les facettes du polygone sont les traits noirs), ainsi que la zone de statut. De même, lorsque l'objectif est défini/redéfini, la droite optimale s'affiche à l'écran et le statut se met à jour, sauf si le programme linéaire n'admet pas de solution optimale (auquel cas, cela vous sera de toute façon notifié dans le statut).

Pour dessiner correctement le polygone admissible, le logiciel calcule automatiquement le facteur de zoom le plus « adapté ». Il vous informe de l'échelle utilisée à travers les valeurs « Xmax » et « Ymax ». Sur chaque axe (celui des abscisses et celui des ordonnées) se trouvent représentés 10 points à intervalle régulier. Le 10^e point sur l'axe des x correspond au point d'abscisse Xmax, et le 10^e sur l'axe des y à celui d'ordonnée Ymax. Les autres points sur l'axe des x ont donc pour coordonnées respectives Xmax/10, 2*Xmax/10, etc.

Cette section détaille les fonctionnalités supplémentaires offertes par le logiciel qui ne sont pas indispensables pour une utilisation basique. Nous allons commencer par les fonctionnalités liées à des boutons :

• Les boutons « Rappeler » et « Effacer » de la première ligne servent respectivement à afficher les coefficients de la fonction objectif courante (c'est-à-dire la dernière à avoir été validée à l'aide du bouton « Définir ») et à remettre à zéro les 2 champs de texte de cette ligne. Par ailleurs, ils servent également à afficher et à masquer, respectivement, la droite optimale sur la zone d'affichage.


• Le bouton « Éditer » de la 2^e ligne sert à éditer, dans les 3 champs de texte de la 3^e ligne, la contrainte actuellement sélectionnée dans la liste déroulante des contraintes.


• Le bouton « Réduire » de la 3^e ligne sert à signaler au logiciel que vous avez saisi une ou des fraction(s) et désirez ne pas perdre de précision. Lorsque vous appuyez sur ce bouton, le logiciel convertit la contrainte que vous avez saisie en une contrainte absolument équivalente dans laquelle tous les coefficients sont entiers. La contrainte ainsi obtenue est la plus réduite possible (au sens où il n'existe pas de contrainte équivalente dans laquelle les coefficients sont entiers et strictement inférieurs). Vous pourrez ensuite ajouter cette contrainte en appuyant sur le bouton « Ajouter », comme si vous l'aviez vous-même saisie. Notez que, si vous saisissez des quotients de nombres réels, le bouton « Réduire » n'aura aucun effet. Par exemple, l'entrée « 3/2 x + 1 y ≥ 4/5 » donnera « 15 x + 10 y ≥ 8 », alors que l'entrée « 3,5/2 x + 1 y ≥ 4/5 » est incorrecte (du point de vue du bouton « Réduire » !).

• Vous pouvez redéfinir les couleurs affichées par le logiciel en double-cliquant sur certaines zones. Il existe 5 couleurs qui peuvent être redéfinies : celle de fond (1), celle du polygone admissible (2), celle des facettes et points sélectionnés (voir plus bas, (3)), celle de la droite et des points optimaux (4) et celle des nouvelles contraintes (5). Pour redéfinir la couleur (1), double-cliquez simplement sur une zone vierge quelconque de la zone d'affichage. Pour redéfinir la couleur (2), double-cliquez n'importe où à l'intérieur du polygone admissible. Pour redéfinir la couleur (3), double-cliquez sur le texte souligné « Statut du problème : ». Pour redéfinir la couleur (4), double-cliquez sur le texte « Fonction objectif : ». Enfin, pour redéfinir la couleur (5), double-cliquez sur le texte souligné « Nouvelle contrainte : ».


• Si vous placez le curseur de la souris sur l'axe des x, vous verrez apparaître l'abscisse du point où vous vous trouvez (« x = ... »), son ordonnée étant nulle. Vous pouvez faire la même chose sur l'axe des y.


• Si vous sélectionnez une contrainte dans la liste déroulante des contraintes (2^e ligne), la facette correspondante (si elle est définie !) sera sélectionnée et prendra (si elle ne correspond ni à « x = 0 », ni à « y = 0 ») la couleur (3).


• Si vous cliquez (un seul clic) sur le texte souligné « Nouvelle contrainte : », il changera de couleur (il prendra la couleur (5)), vous informant que vous pouvez désormais ajouter une contrainte graphiquement. Cliquez n'importe où hors du domaine admissible une première fois, cela constituera le point de départ de la droite représentant votre nouvelle contrainte. Cliquez ensuite une 2^e fois sur un autre endroit de la zone d'affichage, et la droite représentant la contrainte se tracera. Notez que votre nouvelle contrainte doit nécessairement couper en deux le domaine admissible affiché (sinon, elle ne se tracera pas). Aussitôt que la droite est tracée, son équation apparaît dans les 3 champs de texte de la 3^e ligne. Sélectionnez ensuite le symbole d'inégalité souhaité (« ≥ » ou « ≤ »), modifiez éventuellement certains des coefficients, et vous pouvez alors ajouter normalement la nouvelle contrainte en appuyant sur le bouton « Ajouter ». Vous pouvez recliquer autant de fois que vous le souhaitez pour sélectionner un nouveau point d'arrivée pour la droite (le point de départ, quant à lui, ne pouvant être modifié qu'en sortant puis en réentrant dans ce mode) ; à chaque fois l'équation de la (nouvelle) droite se met à jour. Pour sortir de ce mode à tout moment, appuyez à nouveau sur le texte souligné « Nouvelle contrainte : » (si le texte est déjà en noir et non plus de la couleur (5), c'est que d'autres actions, comme par exemple la suppression d'une contrainte, vous en ont fait sortir).


• Si vous passez avec le curseur de la souris au-dessus de la zone de texte « G2DS 3.0 », vous verrez apparaître le copyright du logiciel. Dès que vous éloignez le curseur, le texte « G2DS 3.0 » s'affiche de nouveau.


• Si vous passez avec le curseur de la souris au-dessus de la zone de texte soulignée « Sous contraintes : », vous verrez apparaître le nombre de contraintes du problème (également souligné). Dès que vous éloignez le curseur, le texte souligné « Sous contraintes : » s'affiche de nouveau.


• De façon similaire, depuis la version 3.0, si vous passez avec le curseur de la souris au-dessus de la zone de texte soulignée « Statut du problème : », vous verrez apparaître le nombre de facettes du problème (également souligné). Dès que vous éloignez le curseur, le texte souligné « Statut du problème : » s'affiche de nouveau.

Cette section détaille les nouvelles fonctionnalités offertes par le logiciel depuis sa version 2.0. Elles concernent la possibilité de résoudre le programme linéaire saisi par l'utilisateur comme un programme linéaire en nombres entiers. Plus précisément, il sera d'abord résolu comme un programme linéaire, puis comme un programme linéaire en nombres entiers. Pour activer ce mode, il suffit de cliquer (un seul clic) sur la zone de texte soulignée « Sous contraintes : » (qui affiche en fait, dès le moment où le curseur de la souris passe dessus, le nombre de contraintes du problème, également souligné) : alors, le suffixe « (e) » est ajouté à cette zone de texte (pour indiquer le fait qu'on est entré en mode d'affichage des solutions entières), et les informations sur les solutions entières du programme linéaire (nombre de solutions entières, polyèdre des contraintes non borné, existence ou non d'une solution entière optimale, etc.) apparaissent dans la zone de statut. En outre, les solutions entières contenues dans la zone d'affichage sont affichées sous la forme de petits carrés noirs, et, si une fonction objectif a été définie et si la valeur optimale entière est finie (et la solution optimale entière contenue dans la zone d'affichage !), alors cette solution optimale entière est affichée sous la forme d'un petit carré de couleur (4).

Pour quitter ce mode (et revenir au mode normal), il suffit de recliquer (un seul clic) sur la zone de texte soulignée « Sous contraintes : ». Il convient de remarquer que la raison pour laquelle la zone d'affichage est définie en fonction des solutions de base admissibles et non en fonction des solutions entières (et, en particulier, de la solution entière optimale) est que cette dernière peut être très éloignée de toutes les solutions de base admissibles (et donc de la solution de base optimale). Par exemple, si l'on considère le programme linéaire suivant : « maximiser -3x+y, sous contraintes y ≥ 3/2, -x+20y ≤ 30, x ≥ 0 et y ≥ 0 », la solution de base optimale est (x = 0, y = 3/2), alors que la solution entière optimale est (x = 10, y = 2) !

Cette section détaille les nouvelles (nouvelles) fonctionnalités offertes par le logiciel depuis sa version 3.0.

En premier lieu, si vous cliquez (un seul clic) sur la zone de texte soulignée « Statut du problème : » (qui affiche en fait, dès le moment où le curseur de la souris passe dessus, le nombre de facettes du problème, également souligné), alors une première facette du problème (parmi celles qui ne sont ni « x = 0 », ni « y = 0 », s'il en existe au moins une !) est sélectionnée (et prend donc la couleur (3)), et la contrainte correspondante est également sélectionnée dans la liste déroulante des contraintes (2^e ligne). Si vous recliquez (toujours un seul clic) sur cette même zone de texte, une autre facette est sélectionnée (ainsi que la contrainte correspondante), puis une autre, et ainsi de suite. Si vous cliquez suffisamment de fois pour que toutes les facettes aient été sélectionnées successivement, alors le processus recommencera à nouveau à partir de la première facette. Notez que l'ajout ou la suppression d'une contrainte (et d'autres événements, comme le fait de faire résoudre le problème comme un programme linéaire en nombres entiers) vous fait sortir de ce mode (et il faut alors recommencer tout le processus depuis le début, le cas échéant).

En second lieu, si vous cliquez (un seul clic) sur la zone de texte soulignée qui indique le nombre de solutions de base admissibles du problème (1^ère ligne de statut, en rouge), alors une première solution de base admissible du problème est sélectionnée (et prend donc la couleur (3)), et ses coordonnées s'affichent dans la zone de texte « Solution de base affichée : » (qui, tant que ce n'est pas le cas, affiche simplement « Solution de base affichée : aucune »). Si vous recliquez (toujours un seul clic) sur cette même zone de texte, une autre solution de base admissible est sélectionnée (et, à nouveau, ses coordonnées s'affichent dans la zone de texte « Solution de base affichée : »), puis une autre, et ainsi de suite. Si vous cliquez suffisamment de fois pour que toutes les solutions de base admissibles aient été sélectionnées successivement, alors le processus recommencera à nouveau à partir de la première solution de base admissible. Notez, ici aussi, que l'ajout ou la suppression d'une contrainte (et d'autres événements, comme le fait de faire résoudre le problème comme un programme linéaire en nombres entiers) vous fait sortir de ce mode (et il faut alors recommencer tout le processus depuis le début, le cas échéant).