Dans cette fiche explicative, nous allons apprendre comment trouver la solution optimale d’un système linéaire qui a une fonction objectif et plusieurs contraintes.
La programmation linéaire est une technique utilisée pour déterminer le maximum ou le minimum d’une quantité donnée avec des restrictions. Ici, la quantité à optimiser est appelée la fonction objectif, et les restrictions sont appelées les contraintes.
En programmation linéaire, la fonction objectif est une fonction affine de plusieurs variables à laquelle on peut ajouter une constante. En d’autres termes, pour un problème de programmation linéaire à deux variables, une fonction objectif doit prendre la forme pour des constantes , et .
Les contraintes de la programmation linéaire sont données comme un ensemble d’inéquations linéaires, ce qui signifie que ce sont des inégalités de la forme pour des constantes a, b et . Les inégalités des contraintes ne sont généralement pas strictes, et la solution optimale d’un problème de programmation linéaire, si elle existe, se situe à la frontière. Il peut y avoir un nombre quelconque d’inéquations données comme contraintes pour un problème de programmation linéaire.
Chaque contrainte de la forme définit une région de demi-plan sur le plan où la frontière de la région est donnée par la droite . Savoir tracer la région donnée par une contrainte est une compétence importante pour la programmation linéaire.
On trace la région donnée par la contrainte . On doit d’abord tracer la frontière . On peut réarranger cette équation pour écrire , ce qui donne l’équation réduite de la droite. Cette droite a une ordonnée à l’origine de 1 et une pente positive de 4. On trace d’abord cette droite sur le plan .
Cette droite divise le plan en deux régions. Pour déterminer quelle région satisfait la contrainte donnée, on peut sélectionner n’importe quel point en dehors de la droite pour tester si le point satisfait la contrainte donnée. Il est conseillé de sélectionner le point le plus simple possible pour cela. Si l’origine n'est pas sur la frontière, alors c’est toujours le choix le plus simple. On peut vérifier si l’origine se situe sur une droite ou non en substituant dans l’inégalité. Si l’égalité est vérifiée, alors l’origine se situe sur la droite. Pour cet exemple, en substituant dans l’inégalité , on remarque que le membre gauche est . Comme l’égalité n’est pas vérifiée, , l’origine ne se situe pas sur la droite.
Maintenant, on peut vérifier si l’origine se situe à l’intérieur de la région définie par la contrainte en testant l’inégalité stricte . Substituer dans l’expression conduit à
Mais comme , ce qui est contraire à l’inégalité donnée, le point ne satisfait pas l’inégalité . En d’autres termes, l’origine ne se situe pas dans la région décrite par cette inégalité. Cela implique que la région définie par la contrainte est celle qui n’inclut pas l’origine. Cette région est colorée dans le graphique ci-dessous.
En programmation linéaire, plusieurs contraintes sont fournies donc la région résultante est la région de chevauchement entre chaque région. Par exemple, on considère les trois contraintes ci-dessous.
Lorsque l’on combine les trois contraintes, on obtient la région de chevauchement triangulaire illustrée ci-dessous.
En programmation linéaire, plusieurs contraintes linéaires se chevauchent pour produire une région de forme polygonale. Ce chevauchement défini par toutes les contraintes fournies est appelé l’ensemble réalisable, et les sommets du polygone sont appelés les points extrémaux.
On dit qu’une région sur le plan est bornée si elle est contenue dans un disque. Sinon, on dit que la région est non bornée. L’ensemble réalisable défini par un ensemble de contraintes peut être borné ou non. Un exemple d’ensemble réalisable non borné est illustré sur le graphique ci-dessous.
On remarque qu’aussi grand que soit le rayon d’un disque cette région ne peut pas être contenue dans le disque. Donc, la région colorée sur le diagramme ci-dessus est non bornée.
Théorème : Théorème fondamental de la programmation linéaire
Si un problème de programmation linéaire a une solution optimale, alors la solution se situe sur la frontière (c’est-à-dire sur les arrêtes et les sommets). De plus, si une frontière contenant une solution optimale a un sommet (ou des sommets), alors la solution se situe sur l’un des sommets.
Pour mieux comprendre ce principe, on va étudier un exemple. On cherche à déterminer la valeur maximale de avec les contraintes
D’après les éléments précédents, l’ensemble réalisable triangulaire est illustré ci-dessous.
On désigne la fonction objectif par . On souhaite trouver la plus grande valeur possible pour , tout en restreignant les valeurs de et telles que est à l’intérieur de l’ensemble réalisable triangulaire. On peut réarranger l’équation de la fonction objectif pour déterminer en écrivant
Pour différentes valeurs de , il s’agit de l’équation d’une droite de pente 3 et d’ordonnée à l’origine . Par exemple, on représente graphiquement cette droite pour , , et sur le graphique contenant l’ensemble réalisable. Notez que
Les ordonnées à l’origine des droites sont donc pour , pour , pour et pour .
Chacune des droites rouges illustrées ci-dessus représente différentes valeurs de la fonction objectif comme indiqué. On remarque que toutes les droites rouges ont la même pente. Les valeurs différentes de n’affectent que les ordonnées à l’origine. La famille des droites représentant la fonction objectif sont donc toutes parallèles.
Si une droite chevauche l’ensemble réalisable, même en un seul point, alors il existe un couple dans l’ensemble réalisable qui peut produire la valeur de la fonction objectif associée à la droite. Si une droite ne chevauche pas l’ensemble réalisable, même en un seul point, alors la valeur de n’est pas réalisable dans l’ensemble réalisable. Par exemple, ne chevauche pas la région colorée ci-dessus donc cette valeur ne peut pas être réalisée.
Donc, la tâche de déterminer la valeur maximale de dans l’ensemble réalisable est réduite à la tâche de trouver la droite rouge associée à la plus haute valeur de . On peut faire glisser une droite de pente 3 vers le haut et le bas dans l’ensemble réalisable jusqu’à ce qu’elle n’intersectionne plus la région. Comme le glissement vers le haut est associé à des valeurs croissantes de dans cet exemple, on cherche la droite la plus haute d’intersection non vide avec la région colorée.
On voit que cette droite est celle de et elle chevauche l’ensemble réalisable en un seul point . Toute droite avec ne chevauche pas du tout l’ensemble réalisable, donc n’est pas réalisable. Cela amène à la conclusion que est la valeur maximale de la fonction objectif dans l’ensemble réalisable.
Dans cet exemple, on recherchait la « dernière droite » d’intersection non vide avec l’ensemble réalisable. Si une telle droite existe, alors elle doit toucher une frontière de l’ensemble réalisable. En outre, si la frontière contient un sommet (ou des sommets), alors la « dernière droite » doit chevaucher l’ensemble réalisable sur un sommet. Cela fournit une justification intuitive du théorème fondamental de la programmation linéaire.
Bien qu’il soit utile de garder cette intuition géométrique à l’esprit lors de la résolution de problèmes de programmation linéaire, il existe une méthode algorithmique plus simple lorsque l’ensemble réalisable est borné. On rappelle qu’un ensemble borné signifie qu’il peut être contenu dans un disque. L’ensemble réalisable de l’exemple précédent est un ensemble borné comme illustré ci-dessous.
Si l’ensemble réalisable est borné, alors le maximum et le minimum d’une fonction objectif linéaire doivent exister. En outre, on remarque que la frontière de tout ensemble polygonal borné doit passer par deux sommets. Cela est dû au fait qu’une droite qui ne passe pas par deux sommets s’étend vers l’infini et ne peut être contenue donc dans aucun disque. Cela conduit à l’affirmation suivante.
Théorème : Programmation linéaire pour un ensemble réalisable borné
Un problème de programmation linéaire avec un ensemble réalisable non vide et borné doit avoir une solution à l’un des sommets de l’ensemble.
En d’autres termes, on peut résoudre tout problème de programmation linéaire avec un ensemble réalisable borné en cherchant la valeur optimale parmi les sommets. Cela conduit à la méthode suivante pour résoudre un problème de programmation linéaire avec un ensemble réalisable borné.
Comment utiliser la programmation linéaire pour un ensemble réalisable borné
On considère une fonction objectif avec une série de contraintes linéaires. On suppose que l’ensemble réalisable est borné. Pour déterminer la valeur maximale ou minimale de sous les contraintes données, on suit les étapes ci-dessous.
- Représenter graphiquement l’ensemble réalisable d’après les contraintes ;
- Déterminer tous ses sommets ;
- Substituer les coordonnées de chaque sommet dans la fonction objectif ;
- La plus grande valeur de l’étape précédente est la valeur maximale, et la plus petite est la valeur minimale.
On utilise cette méthode pour l’exemple précédent. D’après la représentation de l’ensemble réalisable, on remarque que les sommets sont
On substitue ces points dans la fonction objectif pour obtenir
La plus grande valeur de la fonction objectif de la liste ci-dessus est 3, donc c’est la solution à cet exemple. En d’autres termes, la valeur maximale de limitée à la région colorée est 3, ce qui se produit lorsque et . Cela confirme la réponse trouvée en utilisant la méthode précédente.
Considérons quelques exemples de programmation linéaire avec des ensembles réalisables bornés en utilisant cette méthode.
Exemple 1: Déterminer le point qui maximise la fonction objectif à partir du graphique des contraintes
En utilisant la programmation linéaire, déterminez les valeurs minimale et maximale de la fonction sachant que , , et .
Réponse
Dans cet exemple, on a le graphique de l’ensemble réalisable. On remarque que l’ensemble réalisable est borné (c’est-à-dire qu’il ne peut être contenu dans aucun disque). On rappelle que si l’ensemble réalisable est borné, alors la fonction objectif a ses valeurs maximale et minimale en l’un des sommets. Les étapes pour identifier les valeurs maximale et minimale sont les suivantes.
- Représenter graphiquement l’ensemble réalisable d’après les contraintes ;
- Déterminer tous ses sommets ;
- Substituer les coordonnées de chaque sommet dans la fonction objectif ;
- Identifier la solution.
Comme le graphique de l’ensemble réalisable est fourni, on procède à la recherche des sommets. À partir du graphique, on remarque que les sommets de l’ensemble réalisable triangulaire sont
Ensuite, on substitue ces valeurs dans la fonction objectif :
Dans la liste ci-dessus, la plus grande valeur de est 1, et la plus petite valeur de est .
Donc est la valeur minimale de (quand et ), et 1 est la valeur maximale de (quand et ).
Exemple 2: Déterminer la valeur maximale de la fonction objectif à partir des contraintes et de leur graphique
Déterminez la valeur maximale de la fonction objectif compte tenu des contraintes , , , et .
Réponse
On a le graphique de trois régions colorées correspondant aux contraintes. La région de chevauchement est le quadrilatère marron avec un sommet à l’origine. Il s’agit de l’ensemble réalisable pour ce problème de programmation linéaire.
D’après le graphique donné, on peut dire que les sommets sont
On rappelle que si l’ensemble réalisable est borné (c.à.d. qu’il est contenu dans un disque), alors les valeurs maximale et minimale doivent se produire en l’un de ces sommets. On substitue les coordonnées de chaque sommet dans la fonction objectif :
La plus grande valeur de la liste ci-dessus est 24.
Donc, la valeur maximale de la fonction objectif est égale à 24, ce qui se produit lorsque et .
La programmation linéaire peut être utilisée dans des problèmes réels pour trouver des solutions optimales. Dans les prochains exemples, nous allons examiner des problèmes impliquant des situations de la vie courante.
Exemple 3: Former l’ensemble des inégalités et la fonction objectif d’un problème de programmation linéaire de la vie courante
Dans un atelier, deux ouvriers produisent deux types de bureaux en fer : le type A et le type B. Un ouvrier construit les bureaux et l’autre les peint. Le premier ouvrier met 4 heures pour construire un bureau de type A et 3 heures pour construire un bureau de type B. Le second ouvrier met 3 heures pour peindre un bureau de type A et 4 heures pour peindre un bureau de type B. Le premier ouvrier travaille au moins 5 heures par jour, et le second travaille un maximum de 7 heures par jour. Si l’atelier réalise un profit de 60 LE sur chaque bureau (de chaque type), déterminez la fonction objectif et les inégalités requises pour calculer le nombre de bureaux de chaque type à produire chaque jour pour maximiser le profit .
Réponse
On définit les variables clés de ce problème. Soient le nombre de bureaux de type A produits et le nombre de bureaux de type B produits. L’atelier gagne 60 LE pour chaque bureau de chaque type, donc le profit est donné par . Il s’agit de la fonction objectif à maximiser pour cet exemple.
On examine ensuite le temps de travail du premier ouvrier. Le premier ouvrier met 4 heures pour construire un bureau de type A et 3 heures pour construire un bureau de type B. Donc, le nombre total d’ heures travaillées par le premier ouvrier est donné par . Le premier ouvrier travaille au moins 5 heures par jour, donc on obtient la contrainte
On examine maintenant le temps de travail du second ouvrier. Le second ouvrier met 3 heures pour peindre un bureau de type A et 4 heures pour peindre un bureau de type B. Donc, le nombre total d’ heures travaillées par le second ouvrier est donné par . Le second ouvrier travaille un maximum de 7 heures par jour, donc on obtient la contrainte
Enfin, on doit s’assurer que et car il est impossible de produire un nombre négatif de bureaux. On a donc les contraintes et la fonction objectif :
Exemple 4: Utiliser la programmation linéaire pour maximiser le profit
Une petite entreprise teint ses chemises de couleur unie ou à la teinture nouée, et elle souhaite décider du nombre de chemises de chaque type à produire pour une vente à venir. Ils ont un budget de 240 $. L’achat de chaque chemise coûte 2 $. Cela coûte 0,50 $ pour teindre une chemise de couleur unie et 1,50 $ pour teindre une chemise à la teinture nouée. Ils n’ont que 8 heures pour produire toutes les chemises, et il faut 2 minutes pour teindre une chemise de couleur unie et 10 minutes pour teindre une chemise à la teinture nouée.
Ils souhaitent maximiser leur profit, sachant qu’ils font un profit de 8 $ pour chaque chemise de couleur unie et de 10 $ pour chaque chemise à la teinture nouée.
Soit le nombre de chemises de couleur unie et le nombre de chemises à la teinture nouée.
Lequel des graphiques suivants représente l’ensemble réalisable ?
Définissez la fonction objectif.
Combien de chemises de chaque type l’entreprise doit-elle produire pour maximiser son profit ?
Réponse
Partie 1
On doit d’abord identifier les contraintes de ce problème. Soient le nombre de chemises de couleur unie et le nombre de chemises à la teinture nouée. Comme on ne peut pas avoir un nombre négatif de chemises, on doit avoir et .
On examine ensuite le coût total. Chaque chemise coûte 2 $ à l’achat, mais il y a un coût supplémentaire pour la teinture. Une chemise de couleur unie coûte 0,50 $ à teindre, donc le coût global est 2,50 $ par chemise de couleur unie. Une chemise à la teinture nouée coûte 1,50 $ à teindre, donc le coût global est 3,50 $ par chemise à la teinture nouée. Donc, le coût total (en dollars) est donné par . Comme le coût total ne peut pas dépasser 240 $, on obtient la contrainte
On remarque que l’origine satisfait à la stricte inégalité comme , donc cette inégalité correspond à la région contenant l’origine. En la chevauchant avec les contraintes et , on obtient la région colorée suivante.
On examine maintenant le temps de travail total. Il faut 2 minutes pour teindre une chemise de couleur unie et 10 minutes pour teindre une chemise à la teinture nouée. Donc, le temps de travail total (en minutes) est donné par . Comme le temps total ne peut pas dépasser 8 heures (c’est-à-dire, ), on obtient la contrainte
On note que l’origine satisfait à l’inégalité stricte comme ; donc cette inégalité correspond à la région contenant l’origine. En la chevauchant avec les contraintes et , on obtient la région colorée suivante.
En chevauchant ces deux régions, on obtient l’ensemble réalisable ci-dessous.
Partie 2
On souhaite maximiser le profit. On sait qu’ils réalisent un profit de 8 $ pour chaque chemise de couleur unie et de 10 $ pour chaque chemise à la teinture nouée. Le profit est donc donné par
C’est la fonction objectif à maximiser.
Partie 3
On rappelle qu’un problème de programmation linéaire avec un ensemble réalisable borné doit avoir une solution optimale en un sommet. L’ensemble réalisable représenté dans la partie 1 a quatre sommets. L’origine en est un évident. Un autre est l’ordonnée à l’origine de . On peut le calculer en définissant :
Donc, ce sommet est . L’intersection avec l’axe des abscisses de est un autre sommet. On peut le calculer en définissant :
Donc, ce sommet est . Le dernier sommet est le point d’intersection des deux droites dont les équations sont fournies. On doit donc résoudre le système d’équations linéaires
On peut réarranger la première équation pour isoler et obtenir . En le substituant dans la deuxième équation, on obtient
En le substituant dans . On obtient donc le sommet . Donc, les quatre sommets sont
Enfin, on substitue ces sommets dans la fonction objectif pour trouver le point optimal.
Donc, le profit maximum est 768 $, qui est atteint lorsque et .
L’entreprise doit fabriquer 96 chemises de couleur unie et 0 chemise à la teinture nouée pour maximiser son profit.
Jusqu’à présent, on a examiné des exemples où l’ensemble réalisable était borné. Dans ce cas, la solution au problème de programmation linéaire existe, on peut donc suivre l’algorithme pour identifier la solution.
Cependant, dans le cas d’ensembles réalisables non bornés, la solution n’existe pas toujours. Dans de tels cas, on doit représenter graphiquement la famille de droites associée à différentes valeurs de la fonctions objectif pour vérifier si une solution existe ou non.
Par exemple, on souhaite maximiser la fonction objectif avec les contraintes
Son ensemble réalisable est représenté graphiquement ci-dessous.
On remarque que la région colorée est non bornée car elle ne peut être contenue dans aucun disque. Comme précédemment, on peut résoudre la fonction objectif pour obtenir par . On représente ensuite graphiquement la famille de droites
En représentant graphiquement ces droites dans la partie supérieure de l’ensemble réalisable, on obtient
On remarque que pour toutes grandes valeurs de , la droite associée chevauche toujours l’ensemble réalisable. Cela implique que peut être aussi grand qu’on le souhaite, même sous les contraintes. Dans ce cas, on dit qu’il n’y a pas de valeur maximale de la fonction objectif. En d’autres termes, il n’existe pas de solution à cette programmation linéaire.
Dans certains cas, la solution d’un problème de programmation linéaire peut exister malgré un ensemble réalisable illimité. Il existe plusieurs méthodes pour vérifier si le problème a la solution optimale.
Comment rechercher des solutions à une programmation linéaire avec un ensemble réalisable non borné
Soit la fonction objectif sur un ensemble réalisable non borné. Alors,
- si a une valeur minimale (c.à.d. pour une constante ), alors a la valeur minimale sur l’ensemble réalisable ;
- si a une valeur maximale (c.à.d. pour une constante ), alors a la valeur maximale sur l’ensemble réalisable ;
- si les conditions ci-dessus ne sont pas claires, on doit représenter graphiquement une famille de droites correspondant à la fonction objectif pour vérifier si la valeur optimale est réalisable ou non.
Si on peut déterminer que la valeur optimale existe, alors on peut suivre l’algorithme précédent pour les ensembles réalisables bornés afin d’identifier la valeur optimale.
Dans le dernier exemple, nous allons considérer un exemple de programmation linéaire avec un ensemble réalisable non borné.
Exemple 5: Former des fonctions objectifs pour minimiser les coûts à partir d’un graphique représentant les contraintes
Un fermier peut améliorer la qualité de sa production s’il utilise au moins 18 unités de composé à base d’azote et au moins 6 unités de composé de phosphate. Il peut utiliser deux types d’engrais : A et B. Le coût et le contenu de chaque engrais sont indiqués dans le tableau.
Engrais | Nombre d’unités de composé à base d’azote par kilogramme | Nombre d’unités de composé de phosphate par kilogramme | Coût de chaque kilogramme (LE) |
---|---|---|---|
A | 3 | 2 | 170 |
B | 6 | 1 | 120 |
Sachant que le graphique représente les contraintes dans cette situation, déterminez le coût le plus bas que l’agriculteur peut payer pour l’engrais tout en utilisant des quantités suffisantes des deux composés.
Réponse
On commence par identifier les contraintes représentées sur la figure. Soit le montant (en kilogrammes) d’engrais A utilisé, et le montant (en kilogrammes) d’engrais B utilisé. Alors, sur la base du tableau ci-dessous, la quantité de composé à base d’azote est donnée par . Comme l’agriculteur a besoin d’au moins 18 unités de composé à base d’azote, on obtient
La quantité de composé de phosphate est donnée par . Comme l’agriculteur a besoin d’au moins 6 unités de composé de phosphate, on obtient
Comme on ne peut pas utiliser une quantité négative d’engrais, on a également les contraintes et .
Les contraintes sont donc
Il s’agit de la région colorée en violet sur le graphique ci-dessus.
On détermine ensuite la fonction objectif. L’agriculteur veut minimiser le coût utilisé pour les engrais. D’après le tableau, le coût total en engrais est donné par . La fonction objectif est donc
Il y a deux façons différentes de résoudre ce problème. Comme l’ensemble réalisable est non borné (c.à.d. qu’il ne peut être contenu dans aucun disque), on doit d’abord vérifier si le problème a une solution.
Méthode 1
On commence par noter que la fonction objectif représente le coût, qui ne peut pas être négatif. Donc , ce qui signifie que a une valeur minimale. On rappelle que si une fonction objectif a une valeur minimale, alors elle a la valeur minimale sur l’ensemble réalisable. La solution existe donc.
On rappelle que si une solution à un problème de programmation linéaire existe, alors elle doit se produire sur une frontière. En outre, si chaque frontière contient un sommet, alors la solution doit se produire à l’un des sommets. Sur le graphique ci-dessus, on observe que les sommets sont
En substituant ces points dans la fonction objectif .
Comme la plus petite valeur ci-dessus est 580, il s’agit de la valeur minimale de la fonction objectif . En outre, on remarque que cette valeur se produit en , que l’on a prédit à l’aide du graphique.
Méthode 2
Alternativement, on peut vérifier que la solution existe en représentant graphiquement une famille de droites de la fonction objectif. Pour cette méthode, on commence par réarranger la fonction objectif pour isoler et on obtient
La pente de cette droite est , qui se situe entre les pentes des deux droites frontières ( et ). On peut tracer quelques droites correspondant à
On remarque que plus est petit, plus la droite est basse. La droite associée à ne chevauche pas du tout l’ensemble réalisable, donc cette valeur de n’est pas réalisable. En revanche, les droites associées à et chevauchent toutes deux l’ensemble réalisable donc elles peuvent être réalisées. On peut dire en observant cette figure que la plus petite valeur donnant la « dernière droite » avant que la droite ne sorte complètement de l’ensemble réalisable existe.
En fait, en faisant glisser des droites parallèles vers le haut et le bas de l’ensemble réalisable, on peut dire que cette « dernière droite » doit chevaucher l’ensemble réalisable au sommet . Ainsi, en remplaçant dans la fonction objectif, on obtient la valeur minimale
On note que cela correspond à la réponse obtenue avec la méthode 1.
Donc, le coût le plus bas que l’agriculteur peut payer en engrais tout en utilisant des quantités suffisantes des deux composés est 580 LE en utilisant 2 kg d’engrais A et 2 kg de d’engrais B.
Points clés
- La programmation linéaire est une technique utilisée pour déterminer la valeur optimale (min/max) d’une fonction objectif linéaire avec un ensemble de contraintes linéaires.
- Pour les variables physiques qui ne peuvent pas être négatives, on doit penser aux contraintes et .
- On peut vérifier si un problème de programmation linéaire donné a une solution de la manière suivante.
- Si l’ensemble réalisable est borné, alors le maximum et le minimum existent.
- Si la fonction objectif a une valeur minimale, alors le minimum existe.
- Si la fonction objectif a une valeur maximale, alors le maximum existe.
- Si aucune des situations ci-dessus ne s’applique, on doit représenter graphiquement une famille de droites de la fonction objectif pour vérifier si la valeur optimale est réalisable.
- Si la programmation linéaire a une solution, la solution se situe sur la frontière. Si, en plus, chaque frontière contient un sommet (ou des sommets), alors la solution doit se produire en un sommet.
- Si une solution de programmation linéaire existe, alors on peut trouver la solution en utilisant les étapes suivantes.
- Représenter graphiquement l’ensemble réalisable à partir des contraintes.
- Déterminer tous les sommets.
- Substituer les coordonnées de chaque sommet dans la fonction objectif.
- Identifier la solution.