Recherche Opérationnelle: Cours: 3 A IGE

Recherche Opérationnelle
Cours : 3 A IGE
Dr. Soufia BENHIDA

[email protected]
Casablanca
Recherche Opérationnelle
1) INTRODUCTION À LA RECHERCHE
OPÉRATIONNELLE ( PL).
2) RÉSOLUTION DE PROGRAMMES LINÉAIRES
3) CAS PARTICULIERS
4) DUALITÉ
5) SOLVEURS ET LANGAGES DE
MODÉLISATION
6) ANALYSE DE LA SENSIBILITÉ
7) PLANIFICATION ET ORDONNANCEMENT
Introduction à la PL
Exemple
Une compagnie est spécialisée dans la production de deux
types de produits : des climatiseurs et des ventilateurs. Les
deux produits nécessitent un certain nombre d’heures de
main d’œuvre. Le tableau suivant donne les informations
nécessaires sur les deux produits, c’est-à-dire les nombres
d’heures machine et d’heures main d’œuvre nécessaires à
la fabrication d’une unité de chacun de ces produits, ainsi
que le profit généré par la production d’une unité de ce
produit. Le tableau nous donne aussi le nombre total
d’heures machines et d’heures main d’œuvre disponibles.
Exemple ( Suite)
Heures machine Main d’œuvre Profit
Climatiseur 2 h/unité 3 h/unité 25 DT/unité

Ventilateur 2 h/unité 1 h/unité 15 DT/unité
Total disponible 240 h 140 h
I. Formulation du programme linéaire
a) Variables de décision : doivent complètement décrire les

décisions à prendre.
La compagnie veut décider du nombre de climatiseurs et du

nombre de ventilateurs à produire pour maximiser le profit.
Ceci nous amène à choisir les deux variables de décision
suivantes :
x1 = nombre de climatiseurs
x2 = nombre de ventilateurs
b) Fonction objectif : dans n’importe quel programme linéaire, le
responsable de décision veut maximiser (en général, le revenu
ou profit) ou minimiser (en général le coût) une fonction des
variables de décisions. Cette fonction est appelée “ fonction
objectif ”.
L’objectif de l’entreprise est de déterminer le programme de

production qui maximisera son profit (Z=profit). La fonction
objectif s’écrit alors:
Max Z = 25x1 + 15x2

c) Contraintes du modèle : La limitation des ressources contraint
l’entreprise de la manière suivante :
1) Contraintes heure machine 2x1 + 2x2 ≤ 240
2) Contrainte main d’œuvre 3x1 + x2 ≤ 140
3) Contraintes de non-négativité (exprimant que les niveaux
d’activité ne peuvent être négatifs) x1 ≥ 0, x2 ≥ 0
Modèle complet : x1 = nbre de climatiseurs, x2 = nbre de

ventilateurs
Max Z = 25 x1 + 15 x2
s.c. 2x1 + 2x2 ≤ 240
3x1 + x2 ≤ 140
x1 ≥ 0, x2 ≥ 0
s.c = sous contraintes
 Domaine réalisable et solutions optimales : Ce sont deux
concepts fondamentaux associés avec un PL. Pour les définir, on va
utiliser le terme point (x1,x2), qui désigne une spécification de la
valeur de chaque variable de décision.
 Le domaine réalisable (DR) est l’ensemble de tous les points

satisfaisant toutes les contraintes du PL. Dans notre exemple, le
point (20,40) (Z= 280) appartient au DR. Ce point est dit réalisable.
 Pour un problème de maximisation (min), une solution optimale est

un point du DR qui donne la valeur la plus large (faible) de la
fonction objective.
(20, 40) ≠ solution optimale car (10, 110) est réalisable et donne Z =
1900
meilleur profit que Z= 280
RÉSOLUTION DE PROGRAMMES LINÉAIRES
Méthode Graphique
Résolution graphique
Méthode de résolution d’un PL ne comportant que 2 variables de décision
Etapes à suivre
 Représenter les lignes des contraintes et l’ensemble du domaine

réalisable
 Localiser la solution optimale
 Calculer la solution optimale
Méthode Graphique
1ère étape : domaine réalisable
(PL) Max Z = 25 x1 + 15 x2
s.c. 2x1 + 2x2 ≤ 240
3x1 + x2 ≤ 140
x1 ≥ 0, x2 ≥ 0
Domaine réalisable
Méthode Graphique
2ème étape : Recherche de la solution optimale
(PL) Max Z = 25 x1 + 15 x2
La fonction objectif Z = 25x1 + 15x2 représente pour Z fixé (25x1 +

15x2 = cte) l’équation des courbes de niveau qu’on appelle aussi ligne
d’isoprofit ou isocoût.
Maximiser Z revient à déplacer la ligne d’isoprofit dans la direction qui

augmente la valeur de Z (pour un pb de maximisation). La dernière ligne
qui touche le DR définit la plus large valeur de toutes les solutions
réalisables, et contient la solution optimale.
Méthode Graphique
2ème étape : Recherche de la solution optimale (suite)
Solution optimale
D’
D
Méthode Graphique
3ème étape : Calcul de la solution optimale
Solution optimale
2x1 + 2x2 = 240
3x1 + x2 = 140
Donc x1=10, x2=110 et Z*=1900
D’

Recherche Opérationnelle: Cours: 3 A IGE

Transféré par

Droits d'auteur :

Formats disponibles

Recherche Opérationnelle: Cours: 3 A IGE

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Recherche Opérationnelle: Cours: 3 A IGE

Transféré par

Droits d'auteur :

Formats disponibles

Recherche Opérationnelle

Dr. Soufia BENHIDA

Heures machine Main d’œuvre Profit

Climatiseur 2 h/unité 3 h/unité 25 DT/unité

a) Variables de décision : doivent complètement décrire les

La compagnie veut décider du nombre de climatiseurs et du

L’objectif de l’entreprise est de déterminer le programme de

Max Z = 25x1 + 15x2

Modèle complet : x1 = nbre de climatiseurs, x2 = nbre de

 Le domaine réalisable (DR) est l’ensemble de tous les points

 Pour un problème de maximisation (min), une solution optimale est

Méthode de résolution d’un PL ne comportant que 2 variables de décision

 Représenter les lignes des contraintes et l’ensemble du domaine

La fonction objectif Z = 25x1 + 15x2 représente pour Z fixé (25x1 +

Maximiser Z revient à déplacer la ligne d’isoprofit dans la direction qui

2ème étape : Recherche de la solution optimale (suite)

Vous aimerez peut-être aussi