Mathématiques · Écoles d'ingénieurs — ENSA — cycle ingénieur

Recherche opérationnelle : Programmation linéaire

Le cours expliqué simplement, les questions que tous les élèves se posent et des exercices type examen national. Programme marocain, gratuit.

📘 Fiche de cours

L'essentiel du cours

La programmation linéaire consiste à maximiser ou minimiser une fonction objectif $Z = ax + by$ sous un ensemble de contraintes linéaires de la forme $a_i x + b_i y \leq c_i$ ou $\geq c_i$ , avec $x, y \geq 0$ . Le théorème fondamental stipule que si une solution optimale existe, elle se trouve sur l'un des sommets du polygone convexe formé par les contraintes.

Méthodes à maîtriser

Représentation graphique : Tracer les droites d'équation $a_i x + b_i y = c_i$ et hachurer les zones exclues.
Identification des sommets : Résoudre les systèmes d'équations linéaires aux intersections des droites frontières.
Évaluation de la fonction objectif : Calculer $Z$ pour chaque sommet $(x_i, y_i)$ et comparer les résultats.
Algorithme du Simplexe (pour $n > 2$ variables) : Utilisation du tableau de Simplexe avec variables d'écart.

Exemples corrigés

Soit $Z = 3x + 2y$ sous $x+y \leq 4$ , $x \leq 3$ , $y \leq 2$ , $x,y \geq 0$ .

Sommets : $(0,0), (3,0), (3,1), (2,2), (0,2)$ .
Valeurs : $Z(0,0)=0, Z(3,0)=9, Z(3,1)=11, Z(2,2)=10, Z(0,2)=4$ .
Max : $Z=11$ au point $(3,1)$ .

Erreurs fréquentes

Oublier la contrainte de non-négativité ( $x,y \geq 0$ ).
Mal orienter les inégalités lors du hachurage.
Se tromper dans la résolution des systèmes d'équations aux sommets.

L'essentiel du cours

La programmation linéaire consiste à maximiser ou minimiser une fonction objectif $Z = ax + by$ sous un ensemble de contraintes linéaires de la forme $a_i x + b_i y \leq c_i$ ou $\geq c_i$, avec $x, y \geq 0$. Le théorème fondamental stipule que si une solution optimale existe, elle se trouve sur l'un des sommets du polygone convexe formé par les contraintes.

Méthodes à maîtriser

Représentation graphique : Tracer les droites d'équation $a_i x + b_i y = c_i$ et hachurer les zones exclues.
Identification des sommets : Résoudre les systèmes d'équations linéaires aux intersections des droites frontières.
Évaluation de la fonction objectif : Calculer $Z$ pour chaque sommet $(x_i, y_i)$ et comparer les résultats.
Algorithme du Simplexe (pour $n > 2$ variables) : Utilisation du tableau de Simplexe avec variables d'écart.

Exemples corrigés

Soit $Z = 3x + 2y$ sous $x+y \leq 4$, $x \leq 3$, $y \leq 2$, $x,y \geq 0$.

Sommets : $(0,0), (3,0), (3,1), (2,2), (0,2)$.
Valeurs : $Z(0,0)=0, Z(3,0)=9, Z(3,1)=11, Z(2,2)=10, Z(0,2)=4$.
Max : $Z=11$ au point $(3,1)$.

Erreurs fréquentes

Oublier la contrainte de non-négativité ($x,y \geq 0$).
Mal orienter les inégalités lors du hachurage.
Se tromper dans la résolution des systèmes d'équations aux sommets.

🌉 Jisr : les mots du chapitre FR ⇄ AR

Tu as appris les sciences en arabe ? Touche un mot pour voir sa traduction et une explication en darija.

La question que tu n'oses pas poser en classe ? Pose-la à UstadZéro jugement, même en darija, même à minuit. Il t'explique pas à pas et corrige ta démarche. Gratuit.Commencer gratuitement

Défi flash : 4 questions

Sans compte

🎯 Recherche opérationnelle : Programmation linéaire

1/4

Le domaine admissible d'un programme linéaire est toujours :

❓ Questions fréquentes

Wach momkin nle9aw 7al ssalb (négatif) ?

Non, à cause de la contrainte de non-négativité ( $x, y \geq 0$ ) qui est standard dans les problèmes de gestion.

💡 À retenir : Si $x$ ou $y$ sort négatif, vérifie tes calculs.

Non, à cause de la contrainte de non-négativité ($x, y \geq 0$) qui est standard dans les problèmes de gestion.

💡 À retenir : Si $x$ ou $y$ sort négatif, vérifie tes calculs.

Comment savoir si on cherche un max ou un min ?

C'est écrit dans l'énoncé. "Maximiser le profit" ou "Minimiser le coût". La méthode reste la même, seule la comparaison finale change.

💡 À retenir : Lisez bien la question avant de conclure.

Est-ce que les variables d'écart ont un impact sur Z ?

Non, dans la fonction objectif initiale, elles ont un coefficient de 0. Elles servent uniquement à la manipulation algébrique dans le tableau.

💡 À retenir : $Z = ax + by + 0e_1 + 0e_2$ .

Non, dans la fonction objectif initiale, elles ont un coefficient de 0. Elles servent uniquement à la manipulation algébrique dans le tableau.

💡 À retenir : $Z = ax + by + 0e_1 + 0e_2$.

Est-ce qu'on peut avoir une solution optimale en dehors des sommets ?

Non, dans un problème de programmation linéaire classique, si le domaine est borné, le maximum ou le minimum est toujours atteint en un sommet. Si la fonction objectif est parallèle à une contrainte, il peut y avoir une infinité de solutions sur un segment, mais les sommets restent des solutions optimales.

💡 À retenir : Testez toujours tous les sommets du domaine admissible.

Kifach n7seb les sommets ila kan 3ndi bezzaf dial l9oyoud ?

7eddi ga3 les droites li kaykono l'espace (les frontières).
7elli ga3 les systèmes $2 \times 2$ dial les droites li kaytla9aw.
Verifier wach had no9ta li l9iti kat7e9e9 ga3 les autres contraintes.

💡 À retenir : Une intersection n'est un sommet que si elle respecte toutes les contraintes du système.

7eddi ga3 les droites li kaykono l'espace (les frontières).
7elli ga3 les systèmes $2 \times 2$ dial les droites li kaytla9aw.
Verifier wach had no9ta li l9iti kat7e9e9 ga3 les autres contraintes.

💡 À retenir : Une intersection n'est un sommet que si elle respecte toutes les contraintes du système.

C'est quoi une variable d'écart ?

C'est une variable qu'on ajoute pour transformer une inéquation en équation. Par exemple, $x + y \leq 4$ devient $x + y + e = 4$ avec $e \geq 0$ . Elle mesure "l'écart" entre la valeur actuelle et la limite.

💡 À retenir : Indispensable pour la méthode du Simplexe.

C'est une variable qu'on ajoute pour transformer une inéquation en équation. Par exemple, $x + y \leq 4$ devient $x + y + e = 4$ avec $e \geq 0$. Elle mesure "l'écart" entre la valeur actuelle et la limite.

💡 À retenir : Indispensable pour la méthode du Simplexe.

Chno hiya l'utilité dial programmation linéaire f l'ingénierie ?

Elle sert à optimiser les ressources limitées : minimiser les coûts de production, maximiser le rendement d'une usine ou optimiser le transport de marchandises. C'est la base de la gestion de projet.

💡 À retenir : Optimiser = faire mieux avec moins.

Est-ce que le domaine peut être vide ?

Oui, si les contraintes sont contradictoires (ex: $x+y \geq 10$ et $x+y \leq 2$ ). Dans ce cas, le problème n'a pas de solution.

💡 À retenir : Vérifiez toujours la compatibilité des contraintes avant de calculer.

Oui, si les contraintes sont contradictoires (ex: $x+y \geq 10$ et $x+y \leq 2$). Dans ce cas, le problème n'a pas de solution.

💡 À retenir : Vérifiez toujours la compatibilité des contraintes avant de calculer.

Kifach n3ref wach l'espace li hachert s7i7 ?

Khodi no9ta sahla (b7al $(0,0)$ ila makantch f l'axe) w chofi wach kat7e9e9 l'inéquation. Ila kanet kat7e9e9ha, l'espace li fih $(0,0)$ howa s7i7.

💡 À retenir : La méthode du point test est la plus fiable.

Khodi no9ta sahla (b7al $(0,0)$ ila makantch f l'axe) w chofi wach kat7e9e9 l'inéquation. Ila kanet kat7e9e9ha, l'espace li fih $(0,0)$ howa s7i7.

💡 À retenir : La méthode du point test est la plus fiable.

Peut-on avoir un domaine non borné ?

Oui, si les contraintes permettent à $x$ ou $y$ de tendre vers $+\infty$ . Dans ce cas, la fonction objectif peut ne pas avoir de maximum fini.

💡 À retenir : Un domaine non borné implique souvent l'absence de solution optimale.

Oui, si les contraintes permettent à $x$ ou $y$ de tendre vers $+\infty$. Dans ce cas, la fonction objectif peut ne pas avoir de maximum fini.

💡 À retenir : Un domaine non borné implique souvent l'absence de solution optimale.

Est-ce que le Simplexe est toujours nécessaire ?

Non, seulement quand tu as plus de 2 variables de décision. Pour 2 variables, le graphique est beaucoup plus rapide et visuel.

💡 À retenir : Graphique pour 2D, Simplexe pour $n$ dimensions.

Non, seulement quand tu as plus de 2 variables de décision. Pour 2 variables, le graphique est beaucoup plus rapide et visuel.

💡 À retenir : Graphique pour 2D, Simplexe pour $n$ dimensions.

Chno lfar9 bin l'optimisation linéaire et non-linéaire ?

Linéaire = tout est sous forme $ax+by$ . Non-linéaire = présence de $x^2, \sin(x), e^x$ , etc. La résolution est beaucoup plus complexe.

💡 À retenir : Le programme de BAC se limite strictement au linéaire.

Linéaire = tout est sous forme $ax+by$. Non-linéaire = présence de $x^2, \sin(x), e^x$, etc. La résolution est beaucoup plus complexe.

💡 À retenir : Le programme de BAC se limite strictement au linéaire.

✍️ Exercices type examen national

Exercice 1

Une entreprise fabrique deux types de produits A et B. Le profit est de 200 DH pour A et 300 DH pour B. Contraintes :

$x + 2y \leq 10$
$3x + y \leq 15$
$x, y \geq 0$ Déterminer le nombre d'unités de A ( $x$ ) et B ( $y$ ) pour maximiser le profit $P = 200x + 300y$ .

Exercice 1

Une entreprise fabrique deux types de produits A et B. Le profit est de 200 DH pour A et 300 DH pour B. Contraintes :

$x + 2y \leq 10$
$3x + y \leq 15$
$x, y \geq 0$ Déterminer le nombre d'unités de A ($x$) et B ($y$) pour maximiser le profit $P = 200x + 300y$.

Voir la correction détaillée : inscription gratuite

Exercice 2

Soit le problème : Minimiser $C = 2x + 5y$ sous : $x + y \geq 4$ $x + 3y \geq 6$ $x, y \geq 0$

Exercice 2

Soit le problème : Minimiser $C = 2x + 5y$ sous : $x + y \geq 4$ $x + 3y \geq 6$ $x, y \geq 0$

Voir la correction détaillée : inscription gratuite

Exercice 3

Soit un système avec 3 contraintes : $x \leq 4$ , $y \leq 3$ , $x+y \leq 5$ . Maximiser $Z = x+y$ .

Exercice 3

Soit un système avec 3 contraintes : $x \leq 4$, $y \leq 3$, $x+y \leq 5$. Maximiser $Z = x+y$.

Voir la correction détaillée : inscription gratuite

Un prof de Mathématiques pour aller plus loin

Les cours du soir avec des profs vérifiés arrivent : inscris-toi pour être prévenu(e) en premier.

Être prévenu(e) gratuitement

Autres chapitres de Mathématiques

Analyse numérique : Résolution d'équations non linéaires Analyse numérique : Interpolation et approximation polynomiale Analyse numérique : Intégration numérique Analyse numérique : Résolution des systèmes d'équations linéaires Calcul différentiel : Fonctions de plusieurs variables Calcul intégral : Intégrales multiples et curvilignes Équations différentielles ordinaires Transformées de Fourier et de Laplace Probabilités et statistiques appliquées à l'ingénierie Algèbre linéaire avancée et calcul matriciel Analyse complexe