CH1 Introd Model Resol Graphique 2019

Introduction et principaux concepts Modélisation Résolution graphique d’un PL
Recherche Opérationnelle: Introduction, modélisation et

résolution graphique
Prof: A. El maliki, abdelmaliki@gmail.com
ENCG Casablanca
A. El maliki (ENCG Casablanca) Recherche Opérationnelle: Introduction, modélisation et résolution graphique 1 / 31

1 Introduction et principaux concepts
2 Modélisation
3 Résolution graphique d’un PL

Aide à la décision
Aide à la décision
L’aide à la décision est l’activité de celui qui, par des voies dites
scientifiques, aide à obtenir des éléments de réponse à des questions que se
posent des acteurs impliqués dans un processus de décision, éléments
concourant à éclairer la décision en vue de favoriser un comportement des
acteurs qui soit de nature à accroı̂tre la cohérence entre l’évolution du
processus d’une part, les objectifs et/ou les systèmes de valeurs au service
desquels ces acteurs se trouvent placés d’autre part.
(B. Roy : Cahiers du Lamsade n˚97, Univ. Paris-Dauphine, 1992)

Qu’est ce que la Recherche Opérationnelle ( en abrégé RO)
La Recherche Opérationnelle(RO) est l’ensemble des méthodes

rationnelles d’analyse (algorithmiques, mathématiques, modélisation) et
des synthèses de phénomènes d’organisation (qui traite de la maximisation
d’un profit, d’une performance, d’un rendement ou bien de la minimisation
d’un coût, d’une dépense...) utilisable pour élaborer de meilleures décisions
(solutions).
RO est indispensable pour les futurs gestionnaires décideurs, responsables

de projets :
Modéliser des problèmes issus des organisations du monde réel
Identifier les méthodes de résolution et les outils les plus adaptés face
à un problème pratique
L’optimisation joue un rôle essentiel dans la recherche opérationnelle

car, outre son aspect important, elle est utilisée comme outil par la plupart
des autres techniques.
La Recherche Opérationnelle
La Recherche Opérationnelle :
n’est pas une science pour des chercheurs purs, car elle est axée sur la
pratique
est purement quantitative et utilisera donc des techniques
quantitatives
repose sur la construction de modèles
n’est pas une science exigeant des qualités de leadership
est une aide pour la préparation de décisions
se situe dans un environnement complexe
est multidisciplinaire et repose sur un travail d’équipe
est performante lorsque la situation est complexe.

Recherche Opérationnelle :
Méthodes utilisées en RO
Optimisation avec/sans contraintes :
- Programmation mathématique, optimistaion combinatoire...
Statistiques
Data Mining
Séries chronologiques ....
Logiciels
Il existe de nombreux logiciels de résolution : Excel Solver, LINDO, MPSX,
CPLEX, MathPro, Matlab, Mathematica ...
Domaines d’application
La RO avait été appliquée considérablement dans plusieurs domaines tels
que :
• affaires (business) • industries •agricole • gouvernement
• économique, • agences • hôpitaux • institutions d’éducation ....
Applications of operations research : Annuel savings

Optimisation
L’Optimisation est un outil d’aide à la décision, permet d’optimiser une

fonction économiques (maximisation d’un profit ou la minimisation d’un
coût) en présence de contraintes.
Programmation mathématique
La programmation mathématique(PM) est un problème d’optimisation
consiste à trouver l’optimum (maximum ou minimum) d’une fonction f (x)
de n variables x = (x1 , · · · , xn ) soumise ou non à un ensemble de m
contraintes gi (x) = 0 ou gi (x) ≥ 0 ; i = 1, · · · , m
La typologie des problèmes de programmation mathématique est basée sur
1 la nature de la fonction : linéaire ou non linéaire
2 la présence ou l’absence de contraintes
3 la nature des contraintes : linéaires ou non linéaires
4 la nature des variables xi : réelles, entières ou binaires

Programmation linéaire
Les problèmes de programmation linéaire (en abrégé PL) sont des

problèmes d’optimisation où la fonction objectif et les contraintes sont
toutes linéaires.
max z = 5x1 + 4x2 ← fonction objectif


x + x2 ≤ 20 ← contrainte 1
 1


Exemple de PL :

s.c 2x1 + x2 ≤ 35 ← contrainte 2



 x , x ≥ 0 ← contraintes de non-négativité
1 2
On appelle variable de décision toute quantité utile à la résolution du

problème et on doit déterminer sa valeur.
On appelle contraintes du problème toutes les relations limitant le
choix de valeurs possibles pour les variables.
On appelle fonction objectif l’expression qui modélise la quantité à
optimiser en fonction des variables du problème.
Définitions
Domaine réalisable : Ensemble de tous les jeux de valeurs des variables de

décision satisfaisant toutes les contraintes et restrictions de signe du PL
(ensemble des solutions réalisables ou solutions admissibles).
Solution réalisable : On appelle solution réalisable toute solution vérifie les

contraintes du PL (y compris les contraintes de positivité).
Solution optimale : Solution réalisable qui optimise (max ou min) la

fonction économique. Elle peut être
Unique → sommet du domaine realisable,
Multiple → côté du domaine realisable,
Infinie (contraintes manquantes ?),
Impossible (contraintes incompatibles !).

Programmation linéaire (PL) : Formulation
La Modélisation consiste à utiliser un ensemble de relations

mathématiques pour refléter le plus adéquatement possible une situation
réelle
Tout modèle est une simplification de la réalité, mais il doit capturer les
caractéristiques essentielles du problème.
Il conviendra donc de tester le modèle, et de le modifier au besoin.
On peut faire aussi de l’analyse de sensibilité pour vérifier la sensibilité du
modèle à des changements de valeurs des paramètres.
Pour modéliser un PL il faut bien lire et comprendre l’énoncé du problème

et Identifier clairement les données.
1 Attention aux unités de mesure !

Les étapes de formulation d’un PL

Généralement il y a trois étapes à suivre pour pouvoir construire le modèle
d’un programme linéaire :
1 Identifier les variables du problème (variables de décision x1 , x2 , · · · ,
les inconnues ).
2 Identifier les contraintes (restrictions) du problème et les exprimer par
un système d’équations et/ou d’inéquations linéaires.
3 Identifier l’objectif ou le critère de sélection et le représenter sous une
forme linéaire en fonction des variables de décision. Spécifier si cette
fonction objectif est à maximiser ou à minimiser.
Rappelons que dans un (PL) les contraintes et l’objectif sont des fonctions
linéaires des variables.

Hypothèses d’un modèle de programmation linéaire

1 Proportionnalité : Les contributions de chaque variable à la fonction
économique et aux contraintes sont proportionnelles à la valeur prise
par cette variable.
2 Additivité : l’effet total des actions prises est égal à la somme des
effets particuliers de chaque variable.
3 Divisibilité : chaque variable de décision peut prendre des valeurs non
entières
4 Certitude : les valeurs affectées à chaque paramètre sont des
constantes connues avec certitude

Exemples de formulation : production de ciment
Exemple 1
Une usine produit deux types de ciments C1 et C2 , rapportant
respectivement 500Dh et 700Dh par tonne. Une tonne du ciment C1
nécessite 40 min de calcination dans un four à chaux et 20 min de
broyage. Une tonne du ciment C2 nécessite 30 min de calcination dans un
four à chaux et 30 min de broyage. Le four et l’atelier de broyage sont
disponibles 6h et 8h par jour.
Combien de ciment de chaque type peut-on produire par jour pour
maximiser le bénéfice ?
Modélisation du problème
Etape 1 : Identification des variables de décision.
Etape 2 : Identification des contraintes
Etape 3 : Identification de la fonction objectif.

Exemple de formulation : production de ciment
Identification des variables de décision :

Le profit total est fonction des quantités vendues des deux produits
C1 et C2 . Appelons :
◦ x1 : la quantité de C1 à produire
◦ x2 : la quantité de C2 à produire
Identification de la fonction objectif :
Le profit z s’obtient à partir de l’expression, Z = 500x1 + 700x2 .
L’objectif poursuivi consiste à trouver la combinaison des quantités x1
et x2 qui maximise le profit total Z : max Z = 500x1 + 700x2
Identification des contraintes : Les valeurs prises par x1 et x2 sont
limitées par les quantités disponibles des ressources (four et broyeur) :
40x1 + 30x2 ≤ 360 (la disponibilité du four )
20x1 + 30x2 ≤ 480 (la disponibilité du broyeur).

Exemples de formulation : production de ciment
Contraintes de non-négativité :
Elles assurent que les quantités achetées ne peuvent être que positives
ou nulles :
x1 ≥ 0, x2 ≥ 0
Le programme linéaire résultant s’écrit :
max z = 500x1 + 700x2




 40x1 + 30x2 ≤ 360

s.c 20x1 + 30x2 ≤ 480



 x ,x ≥ 0 1 2

Exemple de formulation : A production mix problem
The production manager has the responsibility of specifying production

levels for each product for the coming month.
Exemple de formulation : Problème de transport
Une entreprise dispose de 2 entrepôts A1 et A2 pour des unités destinées à

satisfaire la demande de 3 clients B1 , B2 et B3 . Le nombre d’unités
disponibles à chaque entrepôt et les demandes des clients sont spécifiés
dans le tableau suivant qui contient égalemnt le coût du transport d’un
item de chaque entrepôt à chaque client
Entrepôts\ clients B1 B2 B3 disponibilité

A1 1 4 9 200
A2 6 8 4 500
demande 200 400 100
Le problème est de déterminer quelle quantité chaque client reçoit de

chaque entrepôt pour minimiser le coût total de transport tout en
satisfaisant les contraintes.

Exemple de formulation : Problème de mélange
Un industriel veut fabriquer deux sortes d’alliages A1 et A2 dont les

caractéristiques sont les suivantes :
type spécifications prix de vente (euros/tonnes)
A1 pas moins de 30% de zinc 680
pas plus de 40% de fer
A2 pas moins de 15% de cuivre 570
pas plus de 60% de fer
Il trouve disponibles sur le marché trois sorte d’alliages C1, C2 et C3 dont
les compositions(en %), les disponibilités (en tonnes) et les prix d’achat
(en euro/tonnes) sont les suivants :
alliage fer zinc cuivre disponibilité prix d’achat
C1 10 50 40 200 300
C2 30 40 30 250 200
C3 80 10 10 120 100
On cherche dans quelles proportion mélanger les alliages Ci , i = 1, ..., 3
pour fabriquer les alliages Aj , j = 1, ..., 2.
Formuler le problème de mélange d’alliage par un PL pour maximiser le
profit net ?
Exemple de formulation : Problème d’entroposage
Considérons le problème d’entroposer une commodité pour vente future.

Le problème s’échelonne sur 3 périodes successives. A chaque période nous
pouvons acheter et/ou vendre cette commodité et supposons que le prix
unitaire de vente est égal au prix unitaire d’achat tel que spécifié dans
le tableau suivant. De plus le coût unitaire d’entroposage est de $1,00 par
période et la capacité de l’entrepôt est de 60 unités. L’entreprise réalise
donc le plus grand profit en achetant aux périodes où les prix sont bas
pour revendre durant celles où les prix sont plus élevés
Période(t) Prix d’achat unitaire($)
1 4
2 9
3 6
Le problème consiste à déterminer pour chaque période les quantités à
acheter, entreposer et vendre pour maximiser les profits au cours des 3
périodes en supposant que 30 unités sont disponibles initialement.

Programmation linéaire : Résolution du modèle
Utiliser une procédure (algorithme, méthode) pour déterminer :

les valeurs des variables représentant l’amplitude de l’utilisation des
diverses actions pour optimiser la fonction économique (atteindre
l’objectif) en respectant les contraintes imposées.
Résolution graphique.(problème de PL à deux variables).
Résolution par l’algorithme du simplexe.
Résolution graphique :
Première étape : Représenter le domaine réalisable des valeurs des
variables de décision. Graphiquement c’est l’intersection des
demi-plans limités par les droites obtenues en prenant les inégalités
des contraintes à des simples égalités.
Deuxième étape : On représente la fonction objectif dans le plan,
c’est-à-dire Z = C , qui correspond à des droites parallèles d’indice C .
Troisième étape : On détermine l’optimum en choisissant la droite
d’indice C le plus élevé qui touche l’ensemble réalisable.
Résolution graphique d’un PL à deux variables : Exemple de production
Une usine fabrique deux produits P1 et P2 en utilisant des matières

premières M1 , M2 et M3 .
Une unité de P1 nécessite 1 unité de M1 , 2 unités de M2 et 4 unités de M3 .
Une unité de P2 nécessite 6 unités de M1 , 2 unités de M2 et 1 unité de M3 .
Les stocks disponibles sont de 30 unités de M1 , 15 unités de M2 et 24
unités de M3 .
La vente du produit P1 rapporte un bénéfice de 2$. La vente du produit
P2 rapporte un bénéfice de 1$.
La question qui se pose est comment produire ? C-à-d quelles sont les
quantités des produits P1 et P2 à produire pour que le bénéfice total de
l’entreprise soit maximal ?

Formulation de l’exemple de production
Les variables : Designons par x1 et x2 respectivement les quantités

de P1 et P2 à produire.
La fonction objectif à maximiser : La fonction objectif Z
correspond au bénéfice total : max Z = 2x1 + x2 .
Les contraintes :
Disponibilité de chacune des ressources :
x1 + 6x2 ≤ 30 (Matière M1)

2x1 + 2x2 ≤ 15 (Matière M2)
4x1 + x2 ≤ 24 (Matière M3)
Positivité des variables : x1 ≥ 0, x2 ≥ 0

Résolution graphique
Figure: Résolution graphique par IOR Tutorial
L’ensemble admissible(=polyèdre OABCD) est la partie colorée.

Les contraintes où apparaissent des inégalités (y compris celles de

positivité) correspondent géométriquement à des demi-plans .
L’intersection de ces demi-plans forme l’ensemble des variables satisfaisant
à toutes les contraintes= ensemble réalisable (polygône convexe).
A la fonction objectif Z correspond une droite 2x1 + x2 = cste, de

coefficient
vecteur 1,-2/1
directeur (−1, 2/1) (ou de pente (−2/1)).
Isoprofit (Courbe de niveaux de l’objectif) est L’ensemble de solution ayant
un profit donné (= cste).
Recherche d’une direction dans laquelle le profit Z augmente

Pour déterminer max Z , on translate la droite de bas en haut jusqu’à
rencontrer l’ensemble des variables satisfaisant les contraintes (constatez
que le bénéfice Z (x) augmente).
On obtient ainsi la solution optimale (x1 = 11/2, x2 = 2) et ce qui donne
le profit maximal max(Z ) = 2 × 11/2 + 2 = 13.
Remarques
L’ensemble des points réalisables est l’ensemble des solutions vérifiant
toutes les contraintes (y compris celles de positivité)
La solution optimale de notre problème est un sommet du polyèdre
OABCD=simplexe.
Quelle sera la solution optimale si la fonction objective Z devienne :

Z = x1 + x2
Z = x1 + 2x2

Formulation et résolution graphique : production de la peinture
Une société produit de la peinture d’intérieur et d’extérieur à partir de

deux produits de base M1 et M2. Données :
Quantité utilisée/ t Quantité disponible/j

Extérieure Intérieure
M1 6 4 24
M2 1 2 6
Profit par tonne 5 4
Contraintes supplémentaires :
- Demande maximum en peinture d’intérieur : 2 tonnes / jour.
- La production en peinture d’intérieur ne dépasse que d’une tonne celle
d’extérieur.
Écrire le problème de maximisation du profit de cette entreprise sous la
forme d’un programme linéaire.

Exemple : production de peinture
Identification des variables de décision :

Le profit total est fonction des quantités de la peinture d’intérieur et
d’extérieur vendues . Appelons :
◦ x1 : quantités de peinture d’extérieur produites par jour
◦ x2 : quantités de peinture d’intérieur produites par jour
Identification de la fonction objectif à optimiser :
Le profit Z s’obtient à partir de l’expression, Z = 5x1 + 4x2 . L’objectif
poursuivi consiste à trouver la combinaison des quantités x1 et x2 qui
maximise le profit total z : max Z = 5x1 + 4x2
Identification des contraintes : Les valeurs prises par x1 et x2 sont
limitées par des restrictions :
6x1 + 4x2 ≤ 24 (disponibilté de M1) ;
x1 + 2x2 ≤ 6 (disponibilté de M2) ;
x2 ≤ 2 (demande maximale) ;
x2 − x1 ≤ 1 (limite exigée par le marché)

Exemples de formulation : production de peinture
Contraintes de non-négativité :
Elles assurent que les quantités achetées ne peuvent être que positives
ou nulles :
x1 ≥ 0, x2 ≥ 0
Le programme linéaire résultant s’écrit :
max z = 5x1 + 4x2


 6x1 + 4x2 ≤ 24




x + 2x2 ≤ 6

 1



s.c x2 ≤ 2



 x2 − x1 ≤ 1





 x1 , x2 ≥ 0

Exemples de formulation : production de peinture
Figure: Résolution graphique par IOR Tutorial
L’ensemble admissible(=polyèdre OABCDE) est la partie colorée.

Programmation linéaire
Ce qu’il faut absolument savoir

Poser et résoudre graphiquement un problème d’optimisation linéaire :
Modélisation
PL = optimisation linéaire
Résolution graphique de PL à 2 variables

CH1 Introd Model Resol Graphique 2019

Transféré par

Droits d'auteur :

Formats disponibles

CH1 Introd Model Resol Graphique 2019

Transféré par

Informations du document

Description originale:

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

CH1 Introd Model Resol Graphique 2019

Transféré par

Droits d'auteur :

Formats disponibles

Introduction et principaux concepts Modélisation Résolution graphique d’un PL

Recherche Opérationnelle: Introduction, modélisation et

Prof: A. El maliki, abdelmaliki@gmail.com

A. El maliki (ENCG Casablanca) Recherche Opérationnelle: Introduction, modélisation et résolution graphique 1 / 31

1 Introduction et principaux concepts

3 Résolution graphique d’un PL

A. El maliki (ENCG Casablanca) Recherche Opérationnelle: Introduction, modélisation et résolution graphique 2 / 31

A. El maliki (ENCG Casablanca) Recherche Opérationnelle: Introduction, modélisation et résolution graphique 3 / 31

Qu’est ce que la Recherche Opérationnelle ( en abrégé RO)

La Recherche Opérationnelle(RO) est l’ensemble des méthodes

RO est indispensable pour les futurs gestionnaires décideurs, responsables

L’optimisation joue un rôle essentiel dans la recherche opérationnelle

A. El maliki (ENCG Casablanca) Recherche Opérationnelle: Introduction, modélisation et résolution graphique 5 / 31

Applications of operations research : Annuel savings

A. El maliki (ENCG Casablanca) Recherche Opérationnelle: Introduction, modélisation et résolution graphique 7 / 31

L’Optimisation est un outil d’aide à la décision, permet d’optimiser une

A. El maliki (ENCG Casablanca) Recherche Opérationnelle: Introduction, modélisation et résolution graphique 8 / 31

Les problèmes de programmation linéaire (en abrégé PL) sont des

max z = 5x1 + 4x2 ← fonction objectif

On appelle variable de décision toute quantité utile à la résolution du

Domaine réalisable : Ensemble de tous les jeux de valeurs des variables de

Solution réalisable : On appelle solution réalisable toute solution vérifie les

Solution optimale : Solution réalisable qui optimise (max ou min) la

A. El maliki (ENCG Casablanca) Recherche Opérationnelle: Introduction, modélisation et résolution graphique 10 / 31

Programmation linéaire (PL) : Formulation

La Modélisation consiste à utiliser un ensemble de relations

Pour modéliser un PL il faut bien lire et comprendre l’énoncé du problème

A. El maliki (ENCG Casablanca) Recherche Opérationnelle: Introduction, modélisation et résolution graphique 11 / 31

Programmation linéaire (PL) : Formulation

Les étapes de formulation d’un PL

A. El maliki (ENCG Casablanca) Recherche Opérationnelle: Introduction, modélisation et résolution graphique 12 / 31

Programmation linéaire (PL) : Formulation

Hypothèses d’un modèle de programmation linéaire

A. El maliki (ENCG Casablanca) Recherche Opérationnelle: Introduction, modélisation et résolution graphique 13 / 31

Exemples de formulation : production de ciment

A. El maliki (ENCG Casablanca) Recherche Opérationnelle: Introduction, modélisation et résolution graphique 14 / 31

Exemple de formulation : production de ciment

Identification des variables de décision :

A. El maliki (ENCG Casablanca) Recherche Opérationnelle: Introduction, modélisation et résolution graphique 15 / 31

Exemples de formulation : production de ciment

Le programme linéaire résultant s’écrit :

max z = 500x1 + 700x2

A. El maliki (ENCG Casablanca) Recherche Opérationnelle: Introduction, modélisation et résolution graphique 16 / 31

Exemple de formulation : A production mix problem

The production manager has the responsibility of specifying production

Exemple de formulation : Problème de transport

Une entreprise dispose de 2 entrepôts A1 et A2 pour des unités destinées à

Entrepôts\ clients B1 B2 B3 disponibilité

Le problème est de déterminer quelle quantité chaque client reçoit de

A. El maliki (ENCG Casablanca) Recherche Opérationnelle: Introduction, modélisation et résolution graphique 18 / 31

Exemple de formulation : Problème de mélange

Un industriel veut fabriquer deux sortes d’alliages A1 et A2 dont les

Exemple de formulation : Problème d’entroposage

Considérons le problème d’entroposer une commodité pour vente future.

A. El maliki (ENCG Casablanca) Recherche Opérationnelle: Introduction, modélisation et résolution graphique 20 / 31

Programmation linéaire : Résolution du modèle

Utiliser une procédure (algorithme, méthode) pour déterminer :

Résolution graphique d’un PL à deux variables : Exemple de production