Fiche explicative de la leçon: Programmation linéaire | Nagwa Fiche explicative de la leçon: Programmation linéaire | Nagwa

Fiche explicative de la leçon: Programmation linéaire Mathématiques • Première année secondaire

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 𝑎𝑥+𝑏𝑦+𝑐0 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 𝑎𝑥+𝑏𝑦+𝑐0 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 𝑎𝑥+𝑏𝑦+𝑐=0. 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 4𝑥𝑦+10. On doit d’abord tracer la frontière 4𝑥𝑦+1=0. On peut réarranger cette équation pour écrire 𝑦=4𝑥+1, 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 (0;0) 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 (𝑥;𝑦)=(0;0) dans l’inégalité. Si l’égalité est vérifiée, alors l’origine se situe sur la droite. Pour cet exemple, en substituant (0;0) dans l’inégalité 4𝑥𝑦+10, on remarque que le membre gauche est 40+1=1. Comme l’égalité n’est pas vérifiée, 40+10, 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 4𝑥𝑦+1<0. Substituer (0;0) dans l’expression 4𝑥𝑦+1 conduit à 4(0)0+1=1.

Mais comme 1>0, ce qui est contraire à l’inégalité donnée, le point (0;0) ne satisfait pas l’inégalité 4𝑥𝑦+1<0. En d’autres termes, l’origine (0;0) 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 4𝑥𝑦+10 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 3𝑥+𝑦+2 avec les contraintes 𝑥+𝑦10,𝑦0,𝑥0.

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 𝑝=3𝑥+𝑦+2. 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 𝑦=3𝑥+𝑝2.

Pour différentes valeurs de 𝑝, il s’agit de l’équation d’une droite de pente 3 et d’ordonnée 𝑦 à l’origine (0;𝑝2). Par exemple, on représente graphiquement cette droite pour 𝑝=1, 𝑝=2, 𝑝=3 et 𝑝=4 sur le graphique contenant l’ensemble réalisable. Notez que 𝑝=1𝑦=3𝑥1,𝑝=2𝑦=3𝑥,𝑝=3𝑦=3𝑥+1,𝑝=4𝑦=3𝑥+2.

Les ordonnées 𝑦 à l’origine des droites sont donc (0;1) pour 𝑝=1, (0;0) pour 𝑝=2, (0;1) pour 𝑝=3 et (0;2) pour 𝑝=4.

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, 𝑝=4 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 𝑝=3 et elle chevauche l’ensemble réalisable en un seul point (0;1). Toute droite avec 𝑝>3 ne chevauche pas du tout l’ensemble réalisable, donc 𝑝>3 n’est pas réalisable. Cela amène à la conclusion que 𝑝=3 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.

  1. Représenter graphiquement l’ensemble réalisable d’après les contraintes;
  2. Déterminer tous ses sommets;
  3. Substituer les coordonnées de chaque sommet dans la fonction objectif;
  4. 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 (1,0),(0,1),(0,0).

On substitue ces points dans la fonction objectif 𝑓(𝑥;𝑦)=𝑥+4𝑦+2 pour obtenir 𝑓(1,0)=31+0+2=1,𝑓(0,1)=30+1+2=3,𝑓(0,0)=30+0+2=2.

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 𝑥+4𝑦+2 limitée à la région colorée est 3, ce qui se produit lorsque 𝑥=0 et 𝑦=1. 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 𝑝=4𝑥3𝑦 sachant que 𝑥0, 𝑦0, 𝑥+𝑦9 et 𝑦5.

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.

  1. Représenter graphiquement l’ensemble réalisable d’après les contraintes;
  2. Déterminer tous ses sommets;
  3. Substituer les coordonnées de chaque sommet dans la fonction objectif;
  4. 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 (0,5),(0,9),(4,5).

Ensuite, on substitue ces valeurs dans la fonction objectif 𝑝=𝑝(𝑥;𝑦)=4𝑥3𝑦:𝑝(0,5)=4035=15,𝑝(0,9)=4039=27,𝑝(4,5)=4435=1.

Dans la liste ci-dessus, la plus grande valeur de 𝑝 est 1, et la plus petite valeur de 𝑝 est 27.

Donc 27 est la valeur minimale de 𝑝 (quand 𝑥=0 et 𝑦=9), et 1 est la valeur maximale de 𝑝 (quand 𝑥=4 et 𝑦=5).

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 𝑝=2𝑥+6𝑦 compte tenu des contraintes 𝑥0, 𝑦0, 𝑥+𝑦6, 3𝑥+𝑦9 et 𝑥+2𝑦8.

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 (0,0),(0,4),(2,3),(3,0).

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 𝑝=𝑝(𝑥;𝑦)=2𝑥+6𝑦:𝑝(0,0)=20+60=0,𝑝(0,4)=20+64=24,𝑝(2,3)=22+63=22,𝑝(3,0)=23+60=6.

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 𝑥=0 et 𝑦=4.

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 𝑝=60𝑥+60𝑦. 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 4𝑥+3𝑦. Le premier ouvrier travaille au moins 5 heures par jour, donc on obtient la contrainte 4𝑥+3𝑦5.

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 3𝑥+4𝑦. Le second ouvrier travaille un maximum de 7 heures par jour, donc on obtient la contrainte 3𝑥+4𝑦7.

Enfin, on doit s’assurer que 𝑥0 et 𝑦0 car il est impossible de produire un nombre négatif de bureaux. On a donc les contraintes et la fonction objectif:𝑥0,𝑦0,4𝑥+3𝑦5,3𝑥+4𝑦7,𝑝=60𝑥+60𝑦.

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 𝑥0 et 𝑦0.

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 2,5𝑥+3,5𝑦. Comme le coût total ne peut pas dépasser 240 $, on obtient la contrainte 2,5𝑥+3,5𝑦240.

On remarque que l’origine (0;0) satisfait à la stricte inégalité 2,5𝑥+3,5𝑦<240 comme 2,50+3,50<240, donc cette inégalité correspond à la région contenant l’origine. En la chevauchant avec les contraintes 𝑥0 et 𝑦0, 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 2𝑥+10𝑦. Comme le temps total ne peut pas dépasser 8 heures (c’est-à-dire, 8×60=480minutes), on obtient la contrainte 2𝑥+10𝑦480.

On note que l’origine (0;0) satisfait à l’inégalité stricte 2𝑥+10𝑦<480 comme 20+100<480;donc cette inégalité correspond à la région contenant l’origine. En la chevauchant avec les contraintes 𝑥0 et 𝑦0, 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 𝑝(𝑥,𝑦)=8𝑥+10𝑦.

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 (0;0) en est un évident. Un autre est l’ordonnée 𝑦 à l’origine de 2𝑥+10𝑦=480. On peut le calculer en définissant 𝑥=0:20+10𝑦=48010𝑦=480𝑦=48.

Donc, ce sommet est (0;48). L’intersection avec l’axe des abscisses 𝑥 de 2,5𝑥+3,5𝑦=240 est un autre sommet. On peut le calculer en définissant 𝑦=0:2,5𝑥+3,50=2402,5𝑥=240𝑥=96.

Donc, ce sommet est (96;0). 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 2𝑥+10𝑦=480,2,5𝑥+3,5𝑦=240.

On peut réarranger la première équation pour isoler 𝑥 et obtenir 𝑥=2405𝑦. En le substituant dans la deuxième équation, on obtient 2,5(2405𝑦)+3,5𝑦=24060012,5𝑦+3,5𝑦=2409𝑦=360𝑦=40.

En le substituant dans 𝑥=2405𝑦=240540=40. On obtient donc le sommet (40;40). Donc, les quatre sommets sont (0,0),(0,48),(96,0),(40,40).

Enfin, on substitue ces sommets dans la fonction objectif 8𝑥+10𝑦 pour trouver le point optimal. 𝑝(0,0)=80+100=0,𝑝(0,48)=80+1048=480,𝑝(96,0)=896+100=768,𝑝(40,40)=840+1040=720.

Donc, le profit maximum est 768 $, qui est atteint lorsque 𝑥=96 et 𝑦=0.

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 𝑝=3𝑥+𝑦+2 avec les contraintes 𝑥+𝑦10,𝑦0,𝑥0.

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 𝑦=3𝑥2+𝑝. On représente ensuite graphiquement la famille de droites 𝑝=1𝑦=3𝑥1,𝑝=2𝑦=3𝑥,𝑝=3𝑦=3𝑥+1,𝑝=4𝑦=3𝑥+2.

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.

EngraisNombre d’unités de composé à base d’azote par kilogrammeNombre d’unités de composé de phosphate par kilogrammeCoût de chaque kilogramme (LE)
A3 2170
B61120

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 3𝑥+6𝑦. Comme l’agriculteur a besoin d’au moins 18 unités de composé à base d’azote, on obtient 3𝑥+6𝑦18.

La quantité de composé de phosphate est donnée par 2𝑥+𝑦. Comme l’agriculteur a besoin d’au moins 6 unités de composé de phosphate, on obtient 2𝑥+𝑦6.

Comme on ne peut pas utiliser une quantité négative d’engrais, on a également les contraintes 𝑥0 et 𝑦0.

Les contraintes sont donc 3𝑥+6𝑦18,2𝑥+𝑦6,𝑥0,𝑦0.

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 170𝑥+120𝑦. La fonction objectif est donc 𝑐=170𝑥+120𝑦.

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 𝑐0, 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 (0,6),(2,2),(6,0).

En substituant ces points dans la fonction objectif 𝑐(𝑥;𝑦)=170𝑥+120𝑦. 𝑐(0,6)=1700+1206=720,𝑐(2,2)=1702+1202=580,𝑐(6,0)=1706+1200=1020.

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 (𝑥;𝑦)=(2;2), 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 𝑦=1712𝑥+𝑐120.

La pente de cette droite est 1712, qui se situe entre les pentes des deux droites frontières (12 et 2). On peut tracer quelques droites correspondant à 𝑐=120𝑦=1712𝑥+1,𝑐=720𝑦=1712𝑥+5,𝑐=1200𝑦=1712𝑥+10.

On remarque que plus 𝑐 est petit, plus la droite est basse. La droite associée à 𝑐=120 ne chevauche pas du tout l’ensemble réalisable, donc cette valeur de 𝑐 n’est pas réalisable. En revanche, les droites associées à 𝑐=720 et 𝑐=1200 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 (2;2). Ainsi, en remplaçant (2;2) dans la fonction objectif, on obtient la valeur minimale 𝑐(2,2)=1702+1202=580.

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 𝑥0 et 𝑦0.
  • 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.

Rejoindre Nagwa Classes

Assistez à des séances en direct sur Nagwa Classes pour stimuler votre apprentissage avec l’aide et les conseils d’un enseignant expert !

  • Séances interactives
  • Chat et messagerie électronique
  • Questions d’examen réalistes

Nagwa utilise des cookies pour vous garantir la meilleure expérience sur notre site web. Apprenez-en plus à propos de notre Politique de confidentialité