Comptes rendus des Travaux

Pratiques de Recherche
Opérationnelle

Réalisé par :

ARIF Mariem
MANNAI Yasmine

IIA 3/2
 TP n°1 : Programmation linéaire

Exercice 1:
On est demandé de résoudre le problème suivant :

Donc on a utilisé le solveur d’excel pour le résoudre et on a trouvé les solutions

suivantes :

La solution trouvée est optimale et réalisable, et toutes les contraintes sont

respectées.
Résolution graphique avec Python:

Dans le cadre de l’analyse de ce programme linéaire, une approche graphique a

été utilisée à l’aide du langage Python afin de visualiser l’ensemble des
contraintes et identifier la zone de faisabilité. À cet effet, les inégalités
représentant les contraintes du problème ont été tracées dans un repère

1
(x1,x2), et la zone réalisable a été déterminée comme l’intersection de
l’ensemble des demi-plans admissibles.

Le code réalisé :

2
3
Résultat graphique :

Cette représentation graphique permet non seulement de vérifier visuellement la

validité des contraintes, mais aussi d’identifier les points d’intersection clés, qui
représentent les solutions candidates.

Grâce à cette méthode, il a été possible de déterminer la solution optimale du

problème, qui est x1=3 , x2=4.5 , pour une valeur optimale de la fonction objectif égale
à Z=19,5 , en cohérence avec les résultats obtenus via Excel et le Solveur. Ce type de
visualisation renforce l’interprétation intuitive du problème et permet une meilleure
compréhension de l’impact de chaque contrainte sur la solution optimale.

4
Exercice 2 :
On veut maximiser le profit z, sous des contraintes de capacité horaire des trois
machines :

Analyse détaillée de la solution obtenue:

●​ Utilisation des machines :

Les machines 1 et 2 sont pleinement utilisées, ce qui indique qu’elles sont les
contraintes actives dans ce problème.

La machine 3 est sous-utilisée, elle n’est pas contraignante dans cette solution (elle a
encore 88.3 heures libres).

●​ x₁ = 0 :

Cela signifie que produire de la laine n'apporte pas une contribution optimale au
profit par rapport à son coût en heures machine et c’est à cause de :

Heures totales Profit rendement

utilisées

Laine 11.7 7 ≃0.598

coton 9.6 10 ≃ 1.042

soie 8.3 12 ≃1.446

La laine a le pire rendement, donc elle est éliminée naturellement par l’algorithme .

Cependant, dans la réalité, une entreprise peut ne pas avoir la liberté d’éliminer un
produit, même si son rendement est faible.​
Par exemple, si la laine est fortement demandée par les clients ou essentielle pour

5
la réputation de l’entreprise, sa fabrication peut devenir obligatoire,
indépendamment de sa rentabilité immédiate.

Ainsi, la solution optimale théorique dépend du modèle mathématique, mais la

décision réelle dépend du contexte de l’entreprise. Ce type de situation met en
lumière l’importance de l’analyse de sensibilité et la nécessité de réajuster les
modèles en fonction des contraintes et des priorités du monde réel.

Résolution graphique avec Matlab:

Remarque : La méthode graphique ne peut représenter que deux variables à la fois.

Pour visualiser ce problème, on fixe une variable à 0 (ici x₁ = 0 déjà, ce qui facilite les
choses).
Le code réalisé :

6
7
Résultat graphique :

Zone réalisable (en bleu foncé) :

●​ Représente l’ensemble des solutions admissibles (qui satisfont toutes les

contraintes).
●​ Déterminée par l’intersection des demi-plans définis par les contraintes.
●​ La zone polygonale est convexe, comme toujours en programmation linéaire.
●​ Les lignes pointillées représentent des niveaux de profit constants (ex. : Z =
100, 200, …).
●​ Le profit augmente vers le coin supérieur gauche jusqu’à toucher la frontière
de la zone réalisable.

8
Solution optimale (interprétation):

À partir du graphique :

●​ La ligne de profit maximale tangente à la zone réalisable passe par

l’intersection des contraintes Machine 1 et Machine 2.​
Ce point correspond à : x2 = 6, x3 = 27.
●​ le Profit optimale : Z= 10*6+12*27=384

⇒Ce résultat confirme celui obtenu via le Solver Excel.

Conclusion :

L’utilisation combinée d’Excel, MATLAB et Python a permis d’aborder le problème

sous différents angles : pratique , graphique et algorithmique. Ces approches ont
confirmé que l’optimisation de la production, dans un cadre industriel contraint,
repose sur une gestion rigoureuse des ressources et une prise de décision basée sur
des modèles mathématiques solides. Cette démarche illustre l’intérêt de la
programmation linéaire comme outil d’aide à la décision dans les entreprises de
production.

9
TP n°2 : Modélisation sous forme de
programme linéaire

L’objectif de ce tp est de formuler deux problèmes industriels (problème de

production d’articles et problème de fabrication de pièces mécaniques) en
modèles de programmation linéaire (PL) et d’obtenir leurs solutions
optimales à l’aide du solveur d’Excel .

Problème 1 : Production de poteries et d’émaux sur cuivre:

1. Énoncé et variables de décision :

On note :

●​ x : nombre d’articles de poterie

●​ y : nombre d’articles d’émail sur cuivre

Les données sont les suivantes :

1.​ Temps de fabrication :

○​ 1 h pour une poterie ⇒ x poteries ⇒ x heures
○​ 4 h pour un émail ⇒y émaux ⇒ 4y heures​

2.​ Contrainte sur la charge de travail :​

La charge de travail pour les émaux ne doit pas dépasser celle de la
poterie de plus de 160 heures.​
Mathématiquement :​
4y−x ≤ 160

10
 3.​ Contrainte de production relative :​
La production d’articles de poterie ne doit pas excéder de plus de 30
unités la production d’émaux.​
x−y ≤ 30x

4.​ Capacité journalière :​

Le nombre total d’articles (poteries + émaux) ne doit pas excéder 80
unités par jour.​
x+y ≤ 80

5.​ Non-négativité :​
x ≥ 0,y ≥ 0

6.​ Fonction objectif :​

​
Maximiser le bénéfice total, avec​
​
bénéfice=20 x + 60 y​
En notation PL (maximisation), on pose​
Z = 20 x + 60 y⟶max

2. Formulation en programme linéaire :

On peut écrire le PL dans sa forme standard (inégalités ≤ et non-négativité) :

Max(Z) = 20 x + 60 y

11
sous les contraintes:
− x + 4 y ≤ 160,
x − y ≤ 30,
x + y ≤ 80,
x ≥ 0, y ≥ 0

3. Résolution en utilisant le solveur d’Excel:

Ces résultats indiquent que, pour maximiser le bénéfice, il faut fabriquer :

●​ 32 poteries par jour

●​ 48 articles émaillés par jour
●​ ce qui permet d’atteindre un bénéfice maximal de 3520 D.

Dans la programmation linéaire, la solution optimale se situe généralement à

l'intersection de deux ou plusieurs contraintes saturées. Ces contraintes
actives déterminent les coordonnées exactes de la solution optimale.

➢​ Deux contraintes sont saturées à la limite maximale — ce qui signifie

que la solution est optimale

12
2.Résolution graphique avec Python :

13
Résultat graphique :

Interprétation géométrique

●​ La zone faisable est un polygone convexe, comme toujours en

programmation linéaire.
●​ Le maximum se situe toujours sur un sommet (coin) de cette région.
●​ Grâce à Python, on peut confirmer visuellement :​

○​ Que la solution est faisable (dans la zone),

○​ Qu’elle maximise bien le profit.

14
Problème 2 : Fabrication de coussinets (A) et paliers (B)

1. Énoncé et variables de décision :

On note :

●​ x : nombre de coussinets (A) à fabriquer​

●​ y : nombre de paliers (B) à fabriquer​

Les données chiffrées sont les suivantes :

1.​ Quantités minimales à produire :​

x ≥ 4 000, y ≥ 5 000
2.​ Matière première :​

○​ 2 kg pour un coussinet ⇒ 2 x kg pour x coussinets​

○​ 3 kg pour un palier ⇒ 3 y kg pour y paliers​

3.​ L’unité de production doit traiter au moins 36 000 kg de matière

première.​
2 x + 3 y ≥ 36 000

4.​ Main d’œuvre :​

○​ 1 h pour un coussinet ⇒ x h
○​ 0,5 h pour un palier ⇒ 0.5 y h​

15
 5.​ Le maximum d’heures de main d’œuvre est fixé à 10 000
heures.​
x + 0,5 y ≤ 10 000

6.​ Non-négativité :​
x ≥0,y ≥0

7.​ Fonction objectif :​

​
Minimiser le coût de transport total, composé de :
○​ coût d’acheminement des matières premières : 4x+6y
○​ coût du retour des produits finis : 3x+4y

8.​ Cout total=(4x+6y) + (3x+4y)=7x+10y⟶min

2. Formulation en programme linéaire :

​MinimiserZ=7x+10y,
sous les contraintes​​:
x≥4000,
y≥5000,
2x+3y≥36000,
x+0,5y≤10000,
x≥0,y≥0.​

16
3. Résolution avec le solveur d’Excel:

4. Résolution sur Matlab:

Solution obtenue:

La résolution sur Matlab aboutit au même résultat.

17
Remarque sur la solution obtenue:
La quantité de paliers à fabriquer est un nombre décimal, alors qu’il doit être
entier .

Deux cas sont alors considérés :

➢​ Cas 1 : y = 9333

✅ La fonction objectif est minimisée (valeur plus faible)

❌ La contrainte de matière première est violée : 35999<36000
➢​ Cas 2 : y = 9334

✅ Toutes les contraintes sont respectées

❌ Mais la fonction objectif augmente légèrement​

18
❓ Quel cas choisir ?
La réponse est : « ça dépend ».​
En effet, chaque solution doit être analysée dans son contexte. Une
entreprise réelle possède un cahier des charges spécifique qui fixe des
limites acceptables sur les contraintes.

●​ Si la violation légère de la contrainte de matière première est

acceptable en pratique, on peut choisir le Cas 1, car il minimise le coût.​

●​ Sinon, le Cas 2 est préféré, car toutes les contraintes sont respectées,
même si le coût augmente légèrement.​

❖​ En recherche opérationnelle, modifier les variables de décision pour

observer comment le modèle réagit fait partie de ce qu’on appelle
l’analyse de sensibilité. Cette approche permet d’évaluer l’impact des
changements sur la solution optimale. Toutefois, ces ajustements
doivent être réalisés dans le respect des intervalles de tolérance (± △
x1, ± △ x2 ...) , afin de garantir que les solutions restent valides et
exploitables.

19
 ❖​ Une autre stratégie consiste à agir sur l’autre variable de décision,
comme ici, la quantité de coussinets à produire. Cela peut permettre
d’équilibrer les contraintes sans trop compromettre l’objectif.

D’après le principe de Pareto, on est en présence d’un problème multicritère,

ce qui signifie qu’on ne peut pas optimiser tous les objectifs en même temps
sans en sacrifier un autre. Autrement dit :

"Améliorer un critère entraîne souvent la détérioration d’un autre."

C’est pourquoi le but de la recherche opérationnelle est de trouver un

compromis équilibré, qui permette de satisfaire l’ensemble des critères de
manière acceptable, sans nécessairement atteindre l’optimum absolu pour
chacun.

❖​ Enfin, on peut envisager d’agir non seulement sur les variables, mais
aussi sur les contraintes elles-mêmes. C’est ce qu’on appelle une
relaxation de contrainte. Cette approche permet d’assouplir certaines
conditions du modèle, mais elle doit être justifiée et maîtrisée : il est
crucial d’évaluer jusqu’à quel point on peut relâcher une contrainte
sans compromettre la faisabilité ou la qualité de la solution.

20
 TP N°3: Utilisation d’un Logiciel
d’Optimisation LINDO/LINGO

Ce TP introduit l’utilisation de LINDO/LINGO, un nouveau logiciel dédié à la

résolution des programmes linéaires. Il permet de formuler facilement des
modèles mathématiques et d’obtenir rapidement des solutions optimales,
tout en respectant les contraintes du problème. L’objectif est de se familiariser
avec cet outil à travers deux applications concrètes d’optimisation.

Problème 1: Optimisation de production (Entreprise CARCO)

L’entreprise CARCO fabrique des voitures et des camions. Elle cherche à

maximiser son profit en tenant compte des ressources limitées :

●​ Machines (type 1 à louer et type 2 disponibles),

●​ Quantité d’acier,
●​ Contraintes de production minimale.​

Variables de décision :

●​ Voitures : nombre de voitures produites/jour

●​ Camions : nombre de camions produits/jour
●​ Machines 1 : nombre de machines de type 1 louées/jour​

Modèle sur LINDO :

Sur LINDO, la déclaration des variables de décision se fait au niveau de la
fonction objectif.

21
Objectif :

Maximiser le profit net, tout en respectant les contraintes de

production et de ressources.

Modèle initial :

22
Solution obtenue:

Remarques sur la solution obtenue:

Lors de la première exécution, le nombre de camions obtenu était une valeur

décimale, ce qui n’est pas réaliste dans le contexte (on ne peut pas produire
26.4 camions).

Correction : Ajout de contraintes d'intégralité:

LINDO permet d’imposer l’intégralité à une variable avec la fonction

@GIN(variable) .

Donc on impose que les valeurs de nos variables de décision soient de type
entier .

23
Le modèle devient:

24
On remarque qu'en ajoutant cette contrainte le profit a diminué.

25
Programme Matlab équivalent:

On fait ce programme Matlab qui modélise et résout le même problème:

26
Les résultats trouvés avec Matlab coïncident parfaitement avec ceux de LINDO,

27
Problème 2:

Toutes les contraintes sont modélisées sous forme d’égalités.

Des contraintes de signe ont également été ajoutées.

Modèle sur LINDO:

28
Solution Obtenue:

Résolution avec Python:

Une résolution graphique n'est pas possible pour ce problème car il comporte
12 variables. Les méthodes graphiques ne sont applicables que pour des
problèmes à 2 variables (ou éventuellement 3 avec des visualisations 3D
complexes .

Le problème a été modélisé et résolu en Python à l’aide de la bibliothèque

PuLP, spécialisée en optimisation linéaire. Voici le code :

29
30
Les résultats obtenus avec la ligne : [Link]()

Les résultats Python coïncident parfaitement avec ceux de LINDO, confirmant

la cohérence des solutions.

31
Remarques sur la solution obtenue:

On remarque que, même si nous avons imposé que toutes les variables de
décision soient strictement supérieures à zéro, certaines d’entre elles ont
tout de même une valeur nulle dans la solution optimale.

Cela s’explique par le fait que toutes les contraintes du modèle sont des
égalités strictes. Ce type de formulation réduit fortement l’espace des
solutions réalisables. Ainsi, pour trouver une solution optimale, le
programme peut ignorer la contrainte de signe, même si nous avions
souhaité que toutes les variables de décision soient strictement positives.

Réflexion dans un contexte réel:

En entreprise, lors de la planification de la production ou de la logistique, on

cherche souvent à établir un calendrier d’activités tenant compte de
nombreuses contraintes : disponibilité des ressources, délais, coûts, etc.

❖​ Notions de jalonnement et de relaxation des contraintes :

Dans la pratique, il est fréquent de devoir relâcher certaines contraintes pour

permettre la faisabilité d’un plan :

●​ On appelle cela le jalonnement : on commence par ignorer ou assouplir

certaines contraintes pour obtenir un premier plan réalisable.​

●​ Ensuite, on ajuste progressivement le modèle en réintégrant certaines

conditions (disponibilité des équipements, délai, coût de
sous-traitance…).​

❖​ Exemple : variables nulles dans la réalité

32
Si une variable ayant une valeur nulle dans le modèle correspond, par
exemple, à l’achat d’un composant ou à un sous-produit nécessaire à la
production :

●​ Le responsable de la planification devra se poser des questions :​

○​ Cette ressource est-elle vraiment inutile ?​

○​ Peut-on la remplacer, la sous-traiter, ou l' acheter ailleurs à un

coût plus compétitif ?​

●​ Des décisions concrètes peuvent en découler : recours à une autre

entreprise, adaptation de la production, négociation de tarifs.

33