UNIVERSITÉ : ENIS
École Nationale d'Ingénieurs de Sfax
Titre du Projet :
Programmation Linéaire
Presented By
Ammous Mahdi
Année Universitaire : : 2024/2025]
Sommaire
Introduction ............................................................................................................................2
Chapitre 1 : Programmation linière .........................................................................................4
1. Etude bibliographie sur l’algorithme de simplexe ............................................................5
1.1. Définition de la Programmation Linéaire (PL).............................................................5
1.2. Éléments principaux de la programmation linéaire ......................................................5
2. Formulation d'un problème de programmation linéaire ...................................................6
3. Histoire de la programmation linéaire .............................................................................7
4. Domaines de travail de la programmation linéaire ...........................................................7
Chapitre 2 : Concepts fondamentaux de la programmation linéaire ....................................... 10
1. Problématique ............................................................................................................... 11
1.1. Formulation mathématique du problème ................................................................... 11
1.2. Résolution graphique (si x1 et x2 sont les seules variables) ....................................... 12
1.3. Résolution ce problème de programmation linéaire avec l'algorithme du simplexe ... 14
2. Réalisation sur matlab ................................................................................................... 18
Conclusion ........................................................................................................................... 20
2024/2025
Optimisation de la production d'une entreprise via la
méthode du simplexe
Introduction
La programmation linéaire est une technique d'optimisation mathématique qui permet de
trouver la meilleure solution à un problème en maximisant ou en minimisant une fonction
objective, sous des contraintes linéaires. Elle est largement utilisée dans divers domaines, tels
que la gestion des ressources, la production industrielle, et la logistique, pour résoudre des
problèmes complexes où les relations entre les variables sont linéaires. En optimisant les
processus, la programmation linéaire aide les entreprises à améliorer leur efficacité et à prendre
des décisions stratégiques.
Dans ce projet, l'objectif est d'appliquer la méthode du simplexe pour résoudre un problème
d'optimisation spécifique. Le simplexe est une méthode algorithmique efficace pour trouver la
solution optimale dans les problèmes de programmation linéaire. Cette méthode permet de
naviguer entre les sommets d'un polytope (représentant les solutions possibles) afin de
maximiser ou minimiser la fonction objective, tout en respectant les contraintes du problème.
L'utilisation de la méthode du simplexe dans ce projet vise à optimiser un processus de
production ou de gestion des ressources, en fonction des spécificités du problème choisi. Par
exemple, dans un contexte de production, la méthode permettra de maximiser les profits ou de
minimiser les coûts tout en respectant les contraintes liées aux ressources disponibles.
2
2024/2025
Problématique
Ce projet porte sur l'optimisation de la production d'une entreprise qui fabrique deux produits,
appelés P1et P2. Chaque produit nécessite des ressources spécifiques, et l'objectif est de
maximiser le profit total en déterminant le nombre optimal d'unités à produire pour chaque
produit, tout en respectant les contraintes liées aux ressources disponibles.
Contexte
L'entreprise dispose de ressources limitées dans deux départements de production : Production
et Assemblage. Chaque produit requiert un nombre d'heures de travail différent dans chaque
département. De plus, chaque produit génère un profit spécifique à chaque unité produite.
Données
Produits : P1et P2
Ressources disponibles :
o Nombre d'heures de travail disponibles dans le département de production : 120
heures.
o Nombre d'heures de travail disponibles dans le département d'assemblage : 80
heures.
Coûts/Profits associés :
o Profit par unité de P1 : 40 TND.
o Profit par unité de P2: 30 TND.
Temps de travail requis pour chaque produit :
o P1 nécessite 2 heures dans le département de production et 3 heures dans le
département d'assemblage.
o P2 nécessite 4 heures dans le département de production et 2 heures dans le
département d'assemblage.
3
2024/2025
Chapitre 1 :
Programmation
linière
4
2024/2025
1. Etude bibliographie sur l’algorithme de simplexe
1.1. Définition de la Programmation Linéaire (PL)
La programmation linéaire est une méthode mathématique utilisée pour optimiser (maximiser
ou minimiser) une fonction objective, soumise à un ensemble de contraintes exprimées par des
équations ou des inégalités linéaires. Elle est utilisée pour résoudre des problèmes où les
relations entre les variables sont linéaires.
1.2. Éléments principaux de la programmation linéaire
Les éléments principaux de la programmation linéaire sont :
Variables de décision :
Ce sont les variables dont la valeur est déterminée par le problème. Elles représentent les
choix ou les actions à optimiser. Par exemple, dans un problème de maximisation de profit,
les variables de décision peuvent être la quantité de chaque produit à produire.
Fonction objectif :
C'est une fonction linéaire qui doit être maximisée ou minimisée. Elle représente l'objectif
du problème, comme maximiser le profit ou minimiser les coûts. La fonction objectif est
généralement exprimée sous la forme c1x1+c2 x2+⋯+cn xn où x1,x2,…,xn sont les variables
de décision et c1,c2,…,cn sont des coefficients constants.
Contraintes :
Ce sont des équations ou inégalités linéaires qui limitent les valeurs possibles des variables
de décision. Les contraintes peuvent représenter des limitations sur les ressources, comme
la disponibilité des matériaux ou des horaires de travail. Par exemple, une contrainte
pourrait être a1 x1+a2 x2+⋯+an xn ≤ b , où b est une constante et les a1 , a2 ,…,an sont des
coefficients.
Domaines des variables :
5
2024/2025
Les variables de décision sont souvent soumises à des restrictions supplémentaires, telles
que des bornes sur leurs valeurs ou des conditions de non-négativité. Par exemple, xi ≥ 0
pour tous les i.
Formulation mathématique :
La formulation complète d'un problème de programmation linéaire est un ensemble de la
fonction objectif, des contraintes et des domaines des variables. Elle peut être écrite sous la
forme :
Maximiser ou Minimiser c1 x1 +c2 x2+⋯+cn xn
sous les contraintes
a1 x1 + a2x2 +⋯+ an xn ≤ b
et les conditions sur les variables
xi ≥ 0 (ou autres restrictions).
Ces éléments sont la base de tout modèle de programmation linéaire et permettent de structurer
et de résoudre des problèmes d'optimisation dans des domaines variés, tels que la gestion des
ressources, la planification de la production, le transport, etc.
2. Formulation d'un problème de programmation linéaire
Un problème de PL peut être formulé sous la forme générale suivante :
𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 𝑜𝑢 𝑀𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 𝑍 = 𝑐1𝑥1 + 𝑐2𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
sous les contraintes :
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 𝑏2
x1,x2,…,xn≥0
6
2024/2025
où Z est la fonction objective et x1,x2,…,xn sont les variables de décision.
3. Histoire de la programmation linéaire
La programmation linéaire (PL) a émergé dans les années 1940, principalement en réponse aux
défis posés par la Seconde Guerre mondiale. Elle a été conçue pour résoudre des problèmes
complexes liés à la gestion des ressources, la planification logistique et l'optimisation des
approvisionnements militaires. Les armées avaient besoin de méthodes efficaces pour allouer
des ressources limitées (nourriture, carburant, matériel) tout en maximisant l'efficacité.
C’est George Dantzig, un mathématicien américain, qui a joué un rôle clé dans le
développement de la programmation linéaire. En 1947, il a proposé l’algorithme du simplexe,
une méthode itérative permettant de résoudre des problèmes d’optimisation linéaire de manière
efficace. Cet algorithme est devenu l’un des piliers de la PL et reste largement utilisé à ce jour.
Le terme "programmation linéaire" a été utilisé pour la première fois par Dantzig lui-même,
bien que le mot "programmation" fasse référence ici à la planification (et non à l'écriture de
code informatique). Après la guerre, la PL s'est rapidement répandue dans des domaines civils,
notamment :
Économie : pour analyser les marchés et optimiser les coûts.
Industrie : pour planifier la production et la distribution.
Transport : pour optimiser les itinéraires et les horaires.
Énergie : pour gérer les réseaux électriques et les ressources énergétiques.
Depuis son invention, la programmation linéaire a évolué avec des avancées technologiques et
mathématiques. Elle constitue aujourd’hui un outil fondamental dans la recherche
opérationnelle, permettant de résoudre des problèmes d’optimisation dans des secteurs aussi
variés que l’ingénierie, la finance et l’agriculture.
4. Domaines de travail de la programmation linéaire
La programmation linéaire (PL) est un outil d'optimisation puissant qui trouve des applications
dans une grande variété de domaines. Elle est utilisée chaque fois qu'il s'agit de résoudre des
problèmes impliquant des ressources limitées et des objectifs à maximiser ou minimiser. Voici
les principaux domaines où la PL est couramment appliquée :
7
2024/2025
o Logistique et transport
Optimisation des itinéraires pour minimiser les coûts de transport (ex. : livraison,
déplacements).
Planification des horaires pour les systèmes de transport public ou la gestion des flottes.
Répartition optimale des marchandises entre entrepôts et points de distribution.
o Gestion de la production industrielle
Planification de la production pour minimiser les coûts ou maximiser les profits tout en
respectant les contraintes de capacité.
Gestion des stocks pour équilibrer la demande et l'offre tout en minimisant les coûts de
stockage.
Allocation optimale des machines, des ressources humaines et des matières premières.
o Économie et finance
Optimisation des portefeuilles d'investissement pour maximiser le rendement attendu
en minimisant les risques.
Planification macroéconomique pour l'allocation optimale des ressources dans une
économie nationale.
Analyse des marchés pour déterminer les prix et les volumes optimaux dans des
conditions de concurrence.
o Énergie et environnement
Gestion optimale des réseaux électriques pour équilibrer la production et la
consommation d'énergie.
Planification des ressources énergétiques pour maximiser l'efficacité énergétique tout
en réduisant les coûts.
Optimisation des solutions respectueuses de l’environnement, comme la gestion des
déchets et la réduction des émissions.
o Agriculture et gestion des ressources naturelles
8
2024/2025
Optimisation des cultures et des terres agricoles pour maximiser les rendements tout en
minimisant l'utilisation des ressources (eau, engrais, etc.).
Gestion des ressources forestières ou hydriques pour maximiser leur exploitation
durable.
Planification de l'irrigation et gestion des ressources en eau.
o Santé et services publics
Optimisation des plannings dans les hôpitaux (personnel médical, salles d'opération,
etc.).
Planification des campagnes de vaccination ou de gestion de crise (ex. : pandémie).
Optimisation de la distribution des ressources médicales, comme les ambulances ou les
médicaments.
o Communication et télécommunications
Optimisation des réseaux pour assurer une couverture maximale tout en minimisant les
coûts.
Allocation optimale des canaux de communication et des fréquences radio.
Planification de l'infrastructure pour les réseaux sans fil et les satellites.
La polyvalence de la programmation linéaire permet son intégration dans divers systèmes
complexes, où elle apporte des solutions optimales à des problèmes réels tout en prenant en
compte les contraintes pratiques.
9
2024/2025
Chapitre 2 : Concepts
fondamentaux de la
programmation
linéaire
10
2024/2025
1. Problématique
Problème d'optimisation de production :
Imaginons qu'une entreprise fabrique deux produits P1 et P2, avec les paramètres suivants :
Profit unitaire :
o P1 rapporte un profit de 30 TND par unité.
o P2 rapporte un profit de 40 TND par unité.
Ressources disponibles :
o Le département de production a 100 heures de travail disponibles.
o Le département d'assemblage a 80 heures de travail disponibles.
Temps requis pour chaque produit :
o Pour produire une unité de P1, il faut 1 heure de production et 2 heures
d'assemblage.
o Pour produire une unité de P2, il faut 2 heures de production et 1 heure
d'assemblage
1.1. Formulation mathématique du problème
Variables de décision
x1 : Nombre d'unités de P1 à produire.
x2 : Nombre d'unités de P2 à produire.
Fonction objectif
Maximiser le profit total :
Z = 30 x1+40 x2
Contraintes
11
2024/2025
Temps disponible pour la production :
1x1+2x2 ≤ 100
Temps disponible pour l'assemblage :
2x1+1x2 ≤ 80
Non-négativité des variables :
x1 ≥ 0 , x2 ≥ 0
1.2. Résolution graphique (si x1 et x2 sont les seules variables)
Convertir les contraintes en équations d'égalité
Première contrainte :
x1+2x2 = 100
Cette droite peut être tracée en trouvant deux points :
Si x1=0 , alors 2x2=100 donc x2=50.
Si x2=0 , alors x1=100 .
Ainsi, la droite passe par les points (0,50) et (100,0) .
Deuxième contrainte :
2x1+x2=80
Cette droite peut aussi être tracée en trouvant deux points :
Si x1=0 , alors x2=80 .
Si x2=0 , alors 2x1=80 donc x1=40 .
Ainsi, la droite passe par les points (0,80) et (40,0) .
Contraintes de non-négativité :
x1 ≥ 0 et x2 ≥ 0 signifient que nous ne travaillons que dans le premier quadrant du
graphique.
12
2024/2025
Tracer les droites sur un graphique
Sur un plan x1 (axe horizontal) et x2 (axe vertical), tracez :
o La droite x1+2x2=100.
o La droite 2x1+x2=80.
On va Trouve les sommets de la région faisable
La région faisable sera un polygone. Trouvez les sommets (points d’intersection des droites et
des axes) :
1. Intersection entre x1+2x2=100 et 2x1+x2=80 :
o Résolve ce système d'équations :
x1 + 2x2 = 100
2x1 + x2 = 80
Après substitution : x1 = 20, x2 = 40 .
Donc, le sommet est ( 20,40).
o Intersection avec les axes :
13
2024/2025
o Avec x1+2x2=100, les sommets sont (0,50) et (100,0).
o Avec 2x1+x2=802, les sommets sont (0,80) et (40,0).
Les sommets à vérifier sont donc :
(0,50) , (40,20) , (40,0) .
4. Calcul de la fonction objectif à chaque sommet
On a Z=20x1+40x2 pour chaque sommet :
(0,50) : Z=30(0)+40(50) = 2000 .
(20,40) : Z=30(20)+40(40) = 800+1200=2200 .
(40,0) : Z=30(40)+40(0)=800 .
Solution optimale
La valeur maximale de Z est atteinte au sommet (20,40), donc :
x1=20 , x2=40.
Profit total maximal : 2200 TND.
1.3. Résolution ce problème de programmation linéaire
avec l'algorithme du simplexe
Variables de décision :
x1 : Nombre d'unités de P1 à produire.
x2 : Nombre d'unités de P2 à produire.
Fonction objectif (à maximiser) :
Z = max 30x1+40x2
Contraintes :
14
2024/2025
Temps disponible pour la production :
x1+ 2x2 ≤ 100
Temps disponible pour l'assemblage :
2x1+ x2 ≤ 80
Non-négativité des variables :
x1 ≥ 0 , x2 ≥ 0
Étape 1 : Conversion en forme standard
Nous devons transformer les inégalités en égalités en introduisant des variables d'écart (pour
≤) :
x1+2x2+x3 = 100 (où x3 est la variable d'écart pour la première contrainte)
2x1+x2+ x4 = 80 (où x4 est la variable d'écart pour la deuxième contrainte)
x1 ≥ 0 , x2 ≥ 0 x3 ≥ 0 , x 4 ≥ 0
Étape 2 : Construction du tableau de simplexe initial avec x3 et x4
Le tableau de simplexe initial devient :
Les variables de base est : x3 et x4
Les variables de hors base est : x1 et x2
Donc le base : ( 10 01)
XB = B-1. b = (100
80
)≥0 donc c’est un sommet
X3 X4 X1 X2 b
1 0 1 2 100
0 1 2 1 80
0 0 -30 -40 0
15
2024/2025
Alors on peut rentrer l’une du variable x1 et x2 pour chacune de ses variable on va calcule Oj et
l’indice de la variable qu’il faut sortie de la base .
Variable x1 :
𝑥𝑖 100 80
Oj = min 𝑦𝑖 = { | }=1
1 2
𝑦𝑖≥0
J= arg ( O1 ) = 1
La variable entrent est x1 et la variable sortante est x3
Variable x2 :
𝑥𝑖 100 80
Oj = min 𝑦𝑖 = { | }=2
1 1
𝑦𝑖≥0
J= arg ( O2 ) = 2
La variable entrent est x2 et la variable sortante est x4
X1 X2 X3 X4 b
1 2 1 0 100
2 1 0 1 80
-30 -40 0 0 0
On pivot autour de l’élément 2 dans la colonne x2 et la ligne x3 1. Divisons toute la première
ligne par 2 pour que l’élément pivot devienne 1 :
X1 X2 X3 X4 b
𝟏 1 𝟏 0 50
𝟐 𝟐
2 1 0 1 80
-30 -40 0 0 0
16
2024/2025
X1 X2 X3 X4 b
𝟏 1 𝟏 0 50
𝟐 𝟐
𝟑 0 −𝟏 1 30
𝟐 𝟐
-30 -40 0 0 0
Variable entrante :
x1 entre dans la base (car −10 est le plus négatif).
Variable sortante :
On calcule le rapport pour déterminer quelle variable sort :
50
Pour x2 : 0.5= 100
30
Pour x4 : 1.5 = 20
La plus petite valeur est 20, donc x4 sort de la bas
On pivote autour de l’élément 1.5 dans la colonne x1 et la ligne x4 . Après mise à jour, le
tableau devient :
X1 X2 X3 X4 b
0 1 1 −1 40
3
1 0 −1 2 20
3 3
0 0 50 20 2200
3 3
Solution optimale :
x1 = 20 , x2= 40 , Z = 2200
50 20
Variables hors base : x3 = , x4 =
3 3
La solution optimale maximise la fonction objectif Z à 2200.
17
2024/2025
Profit total maximal : 2200 TND.
2. Réalisation sur matlab
% Script MATLAB pour résoudre le problème de programmation linéaire
% Comme MATLAB minimise par défaut, on utilise les valeurs négatives.
f = [-30; -40]; % Les coefficients de x1 et x2
% Matrice des contraintes (Ax <= b)
A = [1, 2; % Contraintes de production
2, 1]; % Contraintes d'assemblage
% Vecteur des bornes supérieures des contraintes
b = [100; 80];
% Bornes sur les variables (x1, x2 >= 0)
lb = [0; 0]; % x1 >= 0, x2 >= 0
% Résolution du problème avec linprog
[x, Z] = linprog(f, A, b, [], [], lb);
% Affichage des résultats
disp('Solution optimale :');
fprintf('x1 = %.2f\n', x(1));
fprintf('x2 = %.2f\n', x(2));
disp('Valeur maximale de la fonction objectif :');
fprintf('Z = %.2f\n', -Z); % La fonction objectif initiale était maximisée
Résultat attendu :
Solution optimale :
x1 = 20.00
x2 = 40.00
Valeur maximale de la fonction objectif :
Z = 2200.00
18
2024/2025
19
2024/2025
Conclusion
Dans le contexte de ce mini-projet, l’étude a permis de mettre en œuvre un modèle
d’optimisation simple mais efficace, répondant directement aux besoins d’une entreprise fictive
dans la gestion de ressources limitées. Grâce à la programmation linéaire, nous avons maximisé
le profit tout en respectant les contraintes de production et d’assemblage, illustrant ainsi
l’applicabilité pratique de ces outils dans des situations réelles. Ce projet constitue une base
solide pour l’apprentissage et l’application des techniques d’optimisation, offrant une
opportunité idéale pour développer des compétences analytiques et renforcer la compréhension
des enjeux industriels dans un cadre académique.
20
