www.cmathematique.com

Liste des grands dossiers

Grille horaire

Consultez l'horaire de diffusion

Diffuseurs de l'émission :

Consultez le kiosque des mathématiques de l'Agence Science-Presse.Vous y découvrirez une foule de références utiles sur le grand univers des mathématiques.

Participez au concours de Cmathematique.com
Relevez le défi et résolvez le problème du mois. Les meilleures solutions seront publiées sur le site. Concours du mois : les polygones "arithmétiques".

Aidez-nous à mieux cerner vos besoins en répondant à ce sondage.

Les capsules mathématiques proposent des approfondissements sur des concepts en math dont il est question dans les grands dossiers.

Le but de cette section est de vous donner des occasions ou des outils pour que vous puissiez trouver des réponses à vos interrogations au niveau de l'enseignement collégial des sciences.

Les séries 1 et 2 de l'émission "C'est mathématique" sont maintenanten vente sur vidéocassettes.

programmation linéaire

La programmation linéaire est une des très nombreuses théories mathématiques qui ont été élaborées pour résoudre des problèmes d'optimisation. Les problèmes d'optimisation se posent constamment dans les organisations, dans les entreprises et dans la société en général. Mais la nature de ces problèmes est souvent si différente qu'aucune théorie mathématique ne peut les englober tous.

Dans cette capsule, nous vous présentons la Programmation Linéaire qui s'applique à de très nombreux problèmes. Pour introduire ce domaine de la mathématique nous partirons d'un exemple : l'optimisation des revenus dans une cabane à sucre qui produit du sirop, de la tire et du sucre d'érable. Dans cet exemple le petit nombre de variables permets une visualisation graphique du problème. Cela ne sera pas le cas dans une autre capsule mathématique qui traitera de la construction d'un horaire optimal pour les infirmières d'un hôpital. Nous vous inviterons aussi, dans cette capsule, à visiter un site web où vous pourrez expérimenter la résolution automatique de problèmes de programmation linéaire.

Napoléon Cliche : sucrier

Napoléon Cliche possède une cabane à sucre et il compte sur ses ventes de sirop et de sucre comme revenu d'appoint important. Pour Napoléon, il est important de découvrir la façon d'optimiser les revenus qu'il tire de sa cabane. Nous allons tenter de l'aider à résoudre ce problème. Mais, en premier lieu, il doit nous fournir quelques informations.

1. Combien récoltez-vous d'eau d'érable chaque année? Pour une bonne année, j'en récolte environ 10000 gallons.
2. Combien gagnez-vous net pour le sirop et pour le sucre? Je me fais à peu près 9 $ net par gallon de sirop et 2 $ net par livre de sucre. Mais le sucre je ne peux en fabriquer trop car je n'arriverais pas à le vendre.
3. Quel est le nombre maximum de livres de sucre que vous arrivez à vendre? 700 livres.
4. Pour un gallon de sirop cela prend combien d'eau d'érable? Pour un gallon de sirop ça prend 30 gallons d'eau et pour une livre de sucre c'est environ 4 gallons.
5. Combien pouvez-vous faire de sirop en une journée de travail? Environ 50 gallons et 100 livres de sucre si je ne fais que du sucre.
6. Compte tenu de vos autres obligations, combien de jours au maximum pouvez-vous consacrer à faire du sucre et du sirop? Pas plus de deux semaines soit 11 jours si j'inclus un petit samedi.
7. Faites-vous aussi de la tire? S'il reste de l'eau après mes 11 jours, ma femme fait de la tire avec l'eau qui reste. Mais la tire on ne la vend pas; c'est pour la famille.

Nous allons maintenant traduire mathématiquement ces différentes données. Posons que Napoléon produit x gallons de sirop et y livres de sucre. Notons R le revenu net. On a alors : R = 9x + 2y.

Tous les points du premier cadran dans ce graphique pourraient, en principe, correspondre à des productions de sirop et de sucre. Mais, bien entendu, il y a des contraintes à satisfaire. Ci-dessus, nous avons tracé le graphique du segment, dans le premier cadran, de la droite d'équation 9x + 2y = 2000. Les coordonnées de chaque point du segment correspondent à une production de sirop et de sucre fournissant un revenu net de 2000 $. Dans le graphique suivant, nous avons tracé les points correspondant à un revenu de 1000 $ net : 9x + 2y = 1000. Pour chaque revenu que l'on fixerait, on obtiendrait un segment parallèle aux autres.

Exprimons mathématiquement les contraintes :

La quantité d'eau d'érable ne peut dépasser 10000 gallons. Ainsi 30x + 4y <= 10000. Cette inéquation se lit comme suit : la quantité d'eau utilisée pour le sirop (30x) plus la quantité d'eau utilisée pour le sucre (4y) devra être plus petite ou égale à 10000 gallons. En voici la représentation graphique :

Napoléon Cliche ne peut travailler plus de 11 jours. Si Napoléon produit x gallons de sirop cela lui prendra x/50 jours. S'il produit y livres de sucre, cela lui prendra y/100 jours. Ainsi x/50 + y /100 <= 11, inéquation équivalente à 2x + y <= 1100. En voici la représentation graphique :

La quantité de sucre produit par Napoléon ne devra pas dépasser 700 livres. L'inéquation y <= 700 représente cette contrainte. En voici la représentation graphique :

Dans le graphique ci-dessous nous avons représenté l'ensemble des points représentant des productions possibles : ce sont les points qui satisfont toutes les contraintes à la fois. La région ainsi déterminée correspond à la mise en commun des 3 graphiques donnés précédemment.

Les points à l'intérieur et sur la frontière du polygone OABCD sont les seuls points satisfaisant toutes les contraintes. Parmi ces points, il nous faut découvrir celui pour lequel le revenu est le plus grand. Mathématiquement, le problème se résume à ceci : Déterminer x et y afin que R = 9x + 2y soit maximum tout en satisfaisant les contraintes suivantes :

30x + 4y <= 10000
2x + y <= 1100
y <= 700

Tout problème de programmation linéaire se présente de la même façon : il s'agit de trouver le maximum (parfois c'est le minimum) d'une fonction linéaire qui satisfait un ensemble de contraintes s'exprimant au moyen d'inéquations linéaires.

Dans des problèmes réels, le nombre de variables est le plus souvent très grand et il en est de même pour le nombre de contraintes. Ainsi, avant l'arrivée des ordinateurs, il était le plus souvent impossible de résoudre de tels problèmes même si on connaissait déjà des méthodes de résolution telle la méthode du Simplexe.

Comment découvrir le point qui maximisera les revenus de Napoléon? À première vue le problème apparaît difficile car il y a énormément de points satisfaisant les contraintes. Mais, on peut montrer que le maximum est nécessairement atteint à un des sommets du polygone satisfaisant les contraintes. Dans le cas qui nous intéresse ici, où il n'y a que deux variables, il est facile de se convaincre de ce fait. Voici comment.

Reprenons le segment que nous avions tracé et dont chaque point fournissait un revenu de 2000 $. Imaginons maintenant que l'on déplace ce segment vers le haut en le maintenant parallèle à lui-même. Alors, lorsque le segment sortira du polygone, ce sera en passant par un sommet et ce sommet fournira le point de revenu maximum car plus le segment monte et plus les revenus de Napoléon augmentent! Pour trouver le point optimal il suffit donc de trouver les coordonnées des sommets puis d'évaluer le revenu de Napoléon pour chacun d'eux. Nous vous invitons à faire les calculs requis pour trouver les coordonnées des sommets puis de découvrir la production qui optimiserait les revenus de Napoléon. En négligeant les fractions de gallons et de livres vous devriez trouver que la production qui optimiserait les revenus nets de Napoléon serait 255 gallons de sirop et 590 livres de sucre. Le peu qui restera d'eau d'érable pourra servir à faire de la tire. Dans ces conditions le revenu net de Napoléon sera de 3475 $.

Maximize R = 9x + 2y subject to
30x + 4y <= 10000
2x + 1y <= 1100
1y <= 700

Lorsque vous aurez accédé au site http://qmc.yi.org/mrtutor/math/SimplexScript.html vous collerez ce texte dans l'espace approprié (sans laisser d'espace superflu avant et/ou après le bloc texte copié). Puis vous sélectionnerez DECIMAL. En cliquant sur SOLVE, le logiciel solutionnera le problème à l'aide de la méthode du Simplexe. Si vous déroulez la page, vous verrez apparaître une série de tableaux : la méthode du Simplexe demande justement que l'on construise de tels tableaux jusqu'à ce que l'on arrive à la solution. Bien entendu, pour un problème aussi simple que celui que nous avons considéré, l'utilisation de cette méthode est un peu ridicule. Mais, pour des problèmes réels qui impliquent souvent des milliers de contraintes, il n'existe pas d'autres méthodes de résolution.

Ce site est la propriété de

Collaboration

Réalisation et hébergement Net Communications Inc.

Production

Avec l'aide financière du