Présentation de l'applet 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)".

En résumé, résoudre un programme linéaire consiste à optimiser une fonction linéaire sur un ensemble convexe (polyèdre) représenté, en dimension 2, par 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é point de base. Si la valeur optimale d'un programme linéaire est z* et que sa fonction objectif est [opt] dx + ey, 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, le problème obtenu est appelé programme linéaire en nombres entiers.

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 d'entrée des données s'appliquent également). Sélectionner ensuite "min" (pour minimiser), "max" (pour maximiser) ou "aucune" (pour ne définir aucun objectif), puis appuyer 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 de l'applet, 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 l'applet 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 de l'applet, 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 notifié de toute façon dans le statut).

Pour dessiner correctement le polygone admissible, l'applet 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, 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 l'applet 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 sélectionnée dans la liste déroulante.



• Le bouton "Réduire" de la 3^e ligne sert à signaler à l'applet que vous avez entré des fractions et désirez ne pas perdre de précision. Lorsque vous appuyez sur ce bouton, l'applet convertit la contrainte que vous lui avez entrée en une contrainte absolument équivalente dans laquelle tous les coefficients sont entiers. La contrainte ainsi obtenue est la plus réduite possible (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 entrée. Notez que si vous entrez 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 + 1y ≥ 4/5" est incorrecte (du point de vue du bouton "Réduire" !).

• Vous pouvez redéfinir les couleurs de l'applet 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 l'applet. 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 une facette (attention, il faut être précis !) ou sur le texte "Sous contraintes :". Pour redéfinir la couleur (4), double-cliquez sur la droite optimale (précision obligatoire !) ou sur le texte "Fonction objectif :". Enfin, pour redéfinir la couleur (5), double-cliquez sur le texte "Nouvelle contrainte :".



• Si vous placez le curseur de la souris sur l'axe des x, vous verrez apparaitre 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 cliquez (un seul clic) sur une facette (il faut être précis), vous la sélectionnez. Elle prend la couleur (3), sauf s'il s'agit de "x = 0" ou "y = 0", et la contrainte correspondante est sélectionnée dans la liste déroulante des contraintes (2^e ligne). À l'inverse, vous pouvez aussi sélectionner une contrainte dans la liste déroulante, et 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 un point de base (il faut être précis), vous le sélectionnez. Il prend la couleur (3) et ses coordonnées s'affichent à côté de lui.



• Si vous cliquez (un seul clic) sur le texte "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 apparait 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 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 "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 la souris au-dessus de la zone de texte "G2DS 2.0", vous verrez apparaitre le copyright de l'applet. Dès que vous éloignez la souris, le texte "G2DS 2.0" s'affiche de nouveau.



• Si vous passez avec la souris au-dessus de la zone de texte "Sous contraintes :", vous verrez apparaitre le nombre de contraintes du problème. Dès que vous éloignez la souris, le texte "Sous contraintes :" s'affiche de nouveau.

Cette section détaille les nouvelles fonctionnalités offertes par l'applet depuis sa version 2.0. Elles concernent la possibilité de résoudre le programme linéaire entré 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 "Sous contraintes :" (qui affiche, dès le moment où la souris passe dessus, le nombre de contraintes) : 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 "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) !