Mathématiques · Écoles d'ingénieurs — INSEA

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 à optimiser une fonction linéaire $Z = c_1x_1 + c_2x_2 + \dots + c_nx_n$ sous des contraintes linéaires de type $\sum a_{ij}x_j \leq b_i$ ou $\geq b_i$ et $x_j \geq 0$ . Le théorème fondamental stipule que si une solution optimale existe, elle se trouve sur l'un des sommets du polyèdre convexe défini par les contraintes.

Méthodes à maîtriser

Méthode graphique : Utilisable uniquement pour 2 variables. Tracer les droites frontières, hachurer les zones exclues et identifier les sommets.
Méthode du Simplexe :
- Transformer le modèle en forme standard (ajouter des variables d'écart).
- Construire le tableau initial.
- Identifier la colonne pivot (valeur la plus négative dans la ligne $Z$ ).
- Identifier la ligne pivot (ratio $b_i / a_{ij}$ minimal positif).
- Effectuer le pivotage (opération de Gauss) jusqu'à ce que tous les coefficients de $Z$ soient positifs.

Exemples corrigés

Pour maximiser $Z = 3x_1 + 2x_2$ sous $x_1 + x_2 \leq 4$ et $2x_1 + x_2 \leq 5$ :

Sommets : $(0,0), (0,4), (2.5,0), (1,3)$ .
Calcul de $Z$ en chaque point : $Z(1,3) = 3(1)+2(3) = 9$ . C'est le maximum.

Erreurs fréquentes

Oublier la contrainte de non-négativité ( $x_i \geq 0$ ).
Se tromper dans le choix de la ligne pivot (choisir un ratio négatif ou nul).
Ne pas convertir correctement les inégalités $\geq$ en utilisant des variables d'écart et des variables artificielles (méthode du Grand M).

L'essentiel du cours

La programmation linéaire consiste à optimiser une fonction linéaire $Z = c_1x_1 + c_2x_2 + \dots + c_nx_n$ sous des contraintes linéaires de type $\sum a_{ij}x_j \leq b_i$ ou $\geq b_i$ et $x_j \geq 0$. Le théorème fondamental stipule que si une solution optimale existe, elle se trouve sur l'un des sommets du polyèdre convexe défini par les contraintes.

Méthodes à maîtriser

Méthode graphique : Utilisable uniquement pour 2 variables. Tracer les droites frontières, hachurer les zones exclues et identifier les sommets.
Méthode du Simplexe :
- Transformer le modèle en forme standard (ajouter des variables d'écart).
- Construire le tableau initial.
- Identifier la colonne pivot (valeur la plus négative dans la ligne $Z$).
- Identifier la ligne pivot (ratio $b_i / a_{ij}$ minimal positif).
- Effectuer le pivotage (opération de Gauss) jusqu'à ce que tous les coefficients de $Z$ soient positifs.

Exemples corrigés

Pour maximiser $Z = 3x_1 + 2x_2$ sous $x_1 + x_2 \leq 4$ et $2x_1 + x_2 \leq 5$ :

Sommets : $(0,0), (0,4), (2.5,0), (1,3)$.
Calcul de $Z$ en chaque point : $Z(1,3) = 3(1)+2(3) = 9$. C'est le maximum.

Erreurs fréquentes

Oublier la contrainte de non-négativité ($x_i \geq 0$).
Se tromper dans le choix de la ligne pivot (choisir un ratio négatif ou nul).
Ne pas convertir correctement les inégalités $\geq$ en utilisant des variables d'écart et des variables artificielles (méthode du Grand M).

🌉 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

Dans un tableau simplexe, la colonne pivot est choisie selon :

❓ Questions fréquentes

Qu'est-ce qu'une variable d'écart ?

Une variable d'écart est une variable ajoutée à une inégalité pour la transformer en égalité. Par exemple, pour $x_1 + x_2 \leq 10$ , on ajoute $e_1 \geq 0$ pour obtenir $x_1 + x_2 + e_1 = 10$ . Elle représente la "marge" non utilisée de la ressource.

💡 À retenir : Elle transforme une inéquation en équation pour permettre le calcul matriciel.

Une variable d'écart est une variable ajoutée à une inégalité pour la transformer en égalité. Par exemple, pour $x_1 + x_2 \leq 10$, on ajoute $e_1 \geq 0$ pour obtenir $x_1 + x_2 + e_1 = 10$. Elle représente la "marge" non utilisée de la ressource.

💡 À retenir : Elle transforme une inéquation en équation pour permettre le calcul matriciel.

Kifach n-3ref l-point optimal f-la méthode graphique ?

Ktrsem l-minta9a admissible (l-blasa li fihom l-contraintes kamlin).
Ktrsem l-moustakim dyal la fonction objectif $Z = k$ .
Ktb9a t-déplacer had l-moustakim f-l-itijah li kay-zeyed $Z$ (ila knti k-maximiser).
Aakhir point f-l-minta9a li kay-mousso had l-moustakim howa l-point optimal.

💡 À retenir : L'optimum se trouve toujours sur un sommet du polygone.

Ktrsem l-minta9a admissible (l-blasa li fihom l-contraintes kamlin).
Ktrsem l-moustakim dyal la fonction objectif $Z = k$.
Ktb9a t-déplacer had l-moustakim f-l-itijah li kay-zeyed $Z$ (ila knti k-maximiser).
Aakhir point f-l-minta9a li kay-mousso had l-moustakim howa l-point optimal.

💡 À retenir : L'optimum se trouve toujours sur un sommet du polygone.

Est-ce que la méthode du simplexe fonctionne toujours ?

Oui, pour tout problème de programmation linéaire dont le domaine est borné et non vide. Si le domaine est vide, il n'y a pas de solution. S'il n'est pas borné, la solution peut être infinie.

💡 À retenir : Le simplexe est l'algorithme standard pour résoudre les problèmes complexes.

Chno hiya l-far9 bin la forme canonique et la forme standard ?

La forme canonique est celle de l'énoncé (inégalités). La forme standard est celle utilisée pour le calcul (équations avec variables d'écart).

💡 À retenir : Le passage à la forme standard est l'étape obligatoire avant le tableau simplexe.

Comment choisir la colonne pivot ?

Dans le tableau simplexe, on choisit la colonne correspondant au coefficient le plus négatif dans la ligne de la fonction objectif $Z$ (pour une maximisation).

💡 À retenir : Le coefficient le plus négatif indique la variable qui augmente le plus rapidement la valeur de $Z$ .

Dans le tableau simplexe, on choisit la colonne correspondant au coefficient le plus négatif dans la ligne de la fonction objectif $Z$ (pour une maximisation).

💡 À retenir : Le coefficient le plus négatif indique la variable qui augmente le plus rapidement la valeur de $Z$.

Kifach n-7seb l-ratio bach n-l9aw l-ligne pivot ?

Kta-khod l-valeur li kayna f-la colonne "b" (l-constantes) w-k-t-qsemha 3la l-valeur li kayna f-la colonne pivot (l-moujaba ghir).

💡 À retenir : Le ratio minimal positif détermine la contrainte la plus restrictive.

Que faire si tous les coefficients de Z sont positifs dans le simplexe ?

Si vous maximisez et que tous les coefficients de la ligne $Z$ sont positifs (ou nuls), cela signifie que vous avez atteint la solution optimale.

💡 À retenir : L'optimalité est atteinte quand aucune variable ne peut plus augmenter $Z$ .

Si vous maximisez et que tous les coefficients de la ligne $Z$ sont positifs (ou nuls), cela signifie que vous avez atteint la solution optimale.

💡 À retenir : L'optimalité est atteinte quand aucune variable ne peut plus augmenter $Z$.

Est-ce qu'on peut avoir plusieurs solutions optimales ?

Oui, si le coefficient d'une variable hors-base est nul dans la ligne $Z$ finale, cela signifie qu'on peut augmenter cette variable sans changer la valeur de $Z$ .

💡 À retenir : Cela indique une infinité de solutions sur un segment.

Oui, si le coefficient d'une variable hors-base est nul dans la ligne $Z$ finale, cela signifie qu'on peut augmenter cette variable sans changer la valeur de $Z$.

💡 À retenir : Cela indique une infinité de solutions sur un segment.

Est-ce que la programmation linéaire est utilisée en finance ?

Absolument, pour l'optimisation de portefeuille, la gestion des risques et l'allocation d'actifs sous contraintes budgétaires.

💡 À retenir : C'est un outil fondamental pour la prise de décision.

Chno hiya l-méthode du Grand M ?

C'est une variante du simplexe utilisée quand on a des contraintes de type $\geq$ . On ajoute une variable artificielle avec un coût très grand $M$ dans la fonction objectif pour forcer sa valeur à zéro.

💡 À retenir : $M$ est un nombre arbitrairement grand.

C'est une variante du simplexe utilisée quand on a des contraintes de type $\geq$. On ajoute une variable artificielle avec un coût très grand $M$ dans la fonction objectif pour forcer sa valeur à zéro.

💡 À retenir : $M$ est un nombre arbitrairement grand.

Pourquoi le domaine est-il toujours un polyèdre convexe ?

Parce que chaque contrainte définit un demi-plan (convexe). L'intersection de plusieurs demi-plans est toujours un ensemble convexe.

💡 À retenir : La convexité garantit que tout optimum local est un optimum global.

Comment savoir si le problème n'a pas de solution ?

Si, lors du simplexe, vous ne pouvez pas choisir de ligne pivot (tous les dénominateurs sont négatifs ou nuls), le problème est non borné ou impossible.

💡 À retenir : Vérifiez toujours la cohérence des contraintes au départ.

✍️ Exercices type examen national

Exercice 1

Une usine produit deux modèles de composants A et B.

Le modèle A nécessite 2h de montage et 1h de finition.
Le modèle B nécessite 1h de montage et 3h de finition.
Les capacités maximales sont de 100h pour le montage et 90h pour la finition.
Le profit est de 500 DH pour A et 400 DH pour B. Déterminer le nombre de composants à produire pour maximiser le profit.

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

Espaces vectoriels et applications linéaires Réduction des endomorphismes Espaces préhilbertiens réels Analyse réelle : Suites et séries numériques Fonctions d'une variable réelle : Continuité, dérivabilité et développements limités Calcul intégral et équations différentielles Fonctions de plusieurs variables : Calcul différentiel Intégrales multiples et curvilignes Probabilités et variables aléatoires Statistique descriptive et inférentielle Processus stochastiques Analyse numérique