Recherche opértionnelle .pdf



Nom original: Recherche opértionnelle.pdf
Titre: Recherche Opérationnelle
Auteur: Anas RACHID

Ce document au format PDF 1.5 a été généré par LaTeX with Beamer class version 3.24 / pdfTeX-1.40.13, et a été envoyé sur fichier-pdf.fr le 05/12/2013 à 13:29, depuis l'adresse IP 197.153.x.x. La présente page de téléchargement du fichier a été vue 2088 fois.
Taille du document: 532 Ko (93 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)










Aperçu du document


Recherche Op´erationnelle
Anas RACHID
Universit´
e Hassan II,Mohammedia-Casablanca
´
Ecole
Nationale Sup´
erieure d’Arts et M´
etiers
ENSAM-Casablanca

Octobre 2013

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

1 / 49

Recherche op´
erationnelle ?

D´efinition
Ensemble de m´ethodes :
I algorithmiques
I math´ematiques
I mod´elisation
afin de prendre des d´ecisions optimales ou proches de l’optimum dans des
probl`emes complexes, qui traitent de la maximisation d’un profit ou la
minimisation d’un coˆ
ut.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

2 / 49

Recherche op´
erationnelle ?

D´efinition
Ensemble de m´ethodes :
I algorithmiques
I math´ematiques
I mod´elisation
afin de prendre des d´ecisions optimales ou proches de l’optimum dans des
probl`emes complexes, qui traitent de la maximisation d’un profit ou la
minimisation d’un coˆ
ut.
Donc nous allons faire de l’optimisation. (avec et sans contraintes)

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

2 / 49

Recherche op´
erationnelle :Optimisation

Optimisation
L’optimisation est une m´ethode qui cherche la meilleure utilisation, des ressources
rares ou des activit´es, dans une situation r´eelle mais d´ecrite par un mod`ele
math´ematique

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

3 / 49

Recherche op´
erationnelle :Optimisation

Optimisation
L’optimisation est une m´ethode qui cherche la meilleure utilisation, des ressources
rares ou des activit´es, dans une situation r´eelle mais d´ecrite par un mod`ele
math´ematique
Mod`ele
Un mod`ele est une transformation formelle d’une r´ealit´e dans laquelle des d´ecisions
doivent ˆetre prises en vue d’un objectif et/ou des contraintes sur ces d´ecisions.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

3 / 49

Recherche op´
erationnelle :Optimisation

Il existe une infinit´e d’applications o`
u des mod`eles d’optimisation peuvent ˆetre
utiles.
Domaines d’applications
I Finance : Il faut maximiser le profit esp´er´e d’un ensemble d’investissements
en respectant des limites budg´etaires et des limites impos´ees sur le niveau de
risque.
I Logistique : Il faut visiter tous les clients une fois (sans r´ep´etition) d’une
mani`ere qui minimise la distance parcourue.
I Production/ordonnancement : Affecter des tˆaches aux machines d’une
mani`ere que le temps n´ecessaire pour qu’une machine termine ses tˆaches soit
minimis´e.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

3 / 49

Optimisation

Sans contrainte
• Un peu de calcul diff´
erentiel

Avec contrainte
Programmation lin´eaire : Simplexe

• Un peu de calcul matriciel

1

un peu de calcul matriciel

• un logiciel

2

un logiciel

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

4 / 49

Optimisation

Sans contrainte
• Un peu de calcul diff´
erentiel

Avec contrainte
Programmation lin´eaire : Simplexe

• Un peu de calcul matriciel

1

un peu de calcul matriciel

• un logiciel

2

un logiciel

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

4 / 49

Optimisation

Sans contrainte
• Un peu de calcul diff´
erentiel
• Un peu de calcul matriciel
• un logiciel

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

5 / 49

Optimisation

Rappel : Calcul diff. et matriciel

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

5 / 49

Programmation lin´eaire

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

6 / 49

Objectif

Objectif
r´esoudre un probl`eme d’optimisation avec maximisation ou minimisation d’une
fonction lin´eaire (ou fonction objectif) sous `a un certain nombre de contraintes.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

7 / 49

Objectif

Objectif
r´esoudre un probl`eme d’optimisation avec maximisation ou minimisation d’une
fonction lin´eaire (ou fonction objectif) sous `a un certain nombre de contraintes.
M´ethodologie
(
´
Ecriture
du probl`eme sous la forme
C’est ce qu’on appelle

Anas RACHID (ENSAM)

:

I d’in´equations
I d’un objectif `a optimiser

programme lin´
eaire.

Recherche Op´
erationnelle

Octobre 2013

7 / 49

M´ethodologie
´
Etapes
de formulation
(
´
Ecriture
du probl`eme sous la forme

:

I d’in´equations
I d’un objectif `a optimiser

G´en´eralement il y a trois ´etapes `a suivre pour pouvoir construire le mod`ele d’un
programme lin´eaire (PL) :
1

Identifier les variables du probl`eme `a valeur non connues (variable de
d´ecision) et les repr´esenter sous forme symbolique (exp. x1 , y1 ).

2

Identifier les restrictions (les contraintes) du probl`eme et les exprimer par un
syst`eme d’´equations lin´eaires.

3

Identifier l’objectif ou le crit`ere de s´election et le repr´esenter sous une forme
lin´eaire en fonction des variables de d´ecision. Sp´ecifier si le crit`ere de
s´election est `a maximiser ou `a minimiser.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

8 / 49

M´ethodologie
´
Etapes
de formulation
(
´
Ecriture
du probl`eme sous la forme

:

I d’in´equations
I d’un objectif `a optimiser

G´en´eralement il y a trois ´etapes `a suivre pour pouvoir construire le mod`ele d’un
programme lin´eaire (PL) :
1

Identifier les variables du probl`eme `a valeur non connues (variable de
d´ecision) et les repr´esenter sous forme symbolique (exp. x1 , y1 ).

2

Identifier les restrictions (les contraintes) du probl`eme et les exprimer par un
syst`eme d’´equations lin´eaires.

3

Identifier l’objectif ou le crit`ere de s´election et le repr´esenter sous une forme
lin´eaire en fonction des variables de d´ecision. Sp´ecifier si le crit`ere de
s´election est `a maximiser ou `a minimiser.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

8 / 49

M´ethodologie
´
Etapes
de formulation
(
´
Ecriture
du probl`eme sous la forme

:

I d’in´equations
I d’un objectif `a optimiser

G´en´eralement il y a trois ´etapes `a suivre pour pouvoir construire le mod`ele d’un
programme lin´eaire (PL) :
1

Identifier les variables du probl`eme `a valeur non connues (variable de
d´ecision) et les repr´esenter sous forme symbolique (exp. x1 , y1 ).

2

Identifier les restrictions (les contraintes) du probl`eme et les exprimer par un
syst`eme d’´equations lin´eaires.

3

Identifier l’objectif ou le crit`ere de s´election et le repr´esenter sous une forme
lin´eaire en fonction des variables de d´ecision. Sp´ecifier si le crit`ere de
s´election est `a maximiser ou `a minimiser.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

8 / 49

M´ethodologie : exemples

Exemple 1
Un agriculteur veut allouer 150 hectares de surface irrigable entre culture de
tomates et celles de piments.
Il dispose de 480 heures de main d’œuvre et de 440 m3 d’eau.
Un hectare de tomates demande 1 heure de main d’œuvre, 4 m3 d’eau et donne
un b´en´efice net de 100 dirhams. Un hectare de piments demande 4 heures de main
d’œuvre, 2 m3 d’eau et donne un b´en´efice net de 200 dirhams.
Le bureau du p´erim`etre irrigu´e veut prot´eger le prix des tomates et ne lui permet
pas de cultiver plus de 90 hectares de tomates. Quelle est la meilleure allocation
de ses ressources ?

Question : Mod´eliser le probl`eme et ´ecrire le programme lin´eaire.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

9 / 49

M´ethodologie : exemples

´
Etape
1 :Identification des variables de d´ecision.
Les deux inconnues que l’agriculteur doit d´eterminer sont les surfaces `a allouer
pour la culture de tomates et de piments :
• x1 : la surface allou´
ee `a la culture des tomates
• x2 : la surface allou´
ee `a la culture des piments

Nous avons : les variables de d´ecision x1 et x2 sont positives : x1 ≥ 0, x2 ≥ 0.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

9 / 49

M´ethodologie : exemples
´
Etape
2 : Identification des contraintes
Dans ce probl`eme les contraintes repr´esentent la disponibilit´e des facteurs de
production :
• Terrain : l’agriculteur dispose de 150 hectares de terrain, ainsi la contrainte li´ee `
a la
limitation de la surface de terrain est x1 + x2 ≥ 150
• Eau : la culture d’un hectare de tomates demande 4 m3 d’eau et celle d’un hectare
de piments demande 2 m3 mais l’agriculteur ne dispose que de 440 m3 . La
contrainte qui exprime les limitations des ressources en eau est 4x1 + 2x2 ≥ 440
• Main d’oeuvre : Les 480 heures de main d’œuvre seront d´epartager (pas
n´ecessairement en totalit´e) entre la culture des tomates et celles des piments.
Sachant qu’un hectare de tomates demande une heure de main d’œuvre et un
hectare de piments demande 4 heures de main d’œuvre alors la contrainte
repr´esentant les limitations des ressources humaines est x1 + 4x2 ≥ 480
• Les limitations du bureau du p´
erim`
etre irrigu´
e : Ces limitations exigent que
l’agriculteur ne cultive pas plus de 90 hectares de tomates. La contrainte qui
repr´esente cette restriction est x1 ≥ 90
Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

10 / 49

M´ethodologie : exemples
´
Etape
2 : Identification des contraintes
Dans ce probl`eme les contraintes repr´esentent la disponibilit´e des facteurs de
production :
• Terrain : l’agriculteur dispose de 150 hectares de terrain, ainsi la contrainte li´ee `
a la
limitation de la surface de terrain est x1 + x2 ≥ 150
• Eau : la culture d’un hectare de tomates demande 4 m3 d’eau et celle d’un hectare
de piments demande 2 m3 mais l’agriculteur ne dispose que de 440 m3 . La
contrainte qui exprime les limitations des ressources en eau est 4x1 + 2x2 ≥ 440
• Main d’oeuvre : Les 480 heures de main d’œuvre seront d´epartager (pas
n´ecessairement en totalit´e) entre la culture des tomates et celles des piments.
Sachant qu’un hectare de tomates demande une heure de main d’œuvre et un
hectare de piments demande 4 heures de main d’œuvre alors la contrainte
repr´esentant les limitations des ressources humaines est x1 + 4x2 ≥ 480
• Les limitations du bureau du p´
erim`
etre irrigu´
e : Ces limitations exigent que
l’agriculteur ne cultive pas plus de 90 hectares de tomates. La contrainte qui
repr´esente cette restriction est x1 ≥ 90
Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

10 / 49

M´ethodologie : exemples
´
Etape
2 : Identification des contraintes
Dans ce probl`eme les contraintes repr´esentent la disponibilit´e des facteurs de
production :
• Terrain : l’agriculteur dispose de 150 hectares de terrain, ainsi la contrainte li´ee `
a la
limitation de la surface de terrain est x1 + x2 ≥ 150
• Eau : la culture d’un hectare de tomates demande 4 m3 d’eau et celle d’un hectare
de piments demande 2 m3 mais l’agriculteur ne dispose que de 440 m3 . La
contrainte qui exprime les limitations des ressources en eau est 4x1 + 2x2 ≥ 440
• Main d’oeuvre : Les 480 heures de main d’œuvre seront d´epartager (pas
n´ecessairement en totalit´e) entre la culture des tomates et celles des piments.
Sachant qu’un hectare de tomates demande une heure de main d’œuvre et un
hectare de piments demande 4 heures de main d’œuvre alors la contrainte
repr´esentant les limitations des ressources humaines est x1 + 4x2 ≥ 480
• Les limitations du bureau du p´
erim`
etre irrigu´
e : Ces limitations exigent que
l’agriculteur ne cultive pas plus de 90 hectares de tomates. La contrainte qui
repr´esente cette restriction est x1 ≥ 90
Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

10 / 49

M´ethodologie : exemples
´
Etape
2 : Identification des contraintes
Dans ce probl`eme les contraintes repr´esentent la disponibilit´e des facteurs de
production :
• Terrain : l’agriculteur dispose de 150 hectares de terrain, ainsi la contrainte li´ee `
a la
limitation de la surface de terrain est x1 + x2 ≥ 150
• Eau : la culture d’un hectare de tomates demande 4 m3 d’eau et celle d’un hectare
de piments demande 2 m3 mais l’agriculteur ne dispose que de 440 m3 . La
contrainte qui exprime les limitations des ressources en eau est 4x1 + 2x2 ≥ 440
• Main d’oeuvre : Les 480 heures de main d’œuvre seront d´epartager (pas
n´ecessairement en totalit´e) entre la culture des tomates et celles des piments.
Sachant qu’un hectare de tomates demande une heure de main d’œuvre et un
hectare de piments demande 4 heures de main d’œuvre alors la contrainte
repr´esentant les limitations des ressources humaines est x1 + 4x2 ≥ 480
• Les limitations du bureau du p´
erim`
etre irrigu´
e : Ces limitations exigent que
l’agriculteur ne cultive pas plus de 90 hectares de tomates. La contrainte qui
repr´esente cette restriction est x1 ≥ 90
Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

10 / 49

M´ethodologie : exemples

´
Etape
3 : Identification de la fonction objectif.
La fonction objectif consiste `a maximiser le profit apport´e par la culture de
tomates et de piments.
Les contributions respectives 100 et 200, des deux variables de d´ecision x1 et x2
sont proportionnelles `a leur valeur. La fonction objectif est donc
z = 100x1 + 200x2 .

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

11 / 49

M´ethodologie : exemples

Exemple 1
Un agriculteur veut allouer 150 hectares de surface irrigable entre culture de tomates et celles de
piments.
Il dispose de 480 heures de main d’œuvre et de 440 m3 d’eau.
Un hectare de tomates demande 1 heure de main d’œuvre, 4 m3 d’eau et donne un b´
en´
efice net
de 100 dirhams. Un hectare de piments demande 4 heures de main d’œuvre, 2 m3 d’eau et
donne un b´
en´
efice net de 200 dirhams.
Le bureau du p´
erim`
etre irrigu´
e veut prot´
eger le prix des tomates et ne lui permet pas de cultiver
plus de 90 hectares de tomates. Quelle est la meilleure allocation de ses ressources ?

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

12 / 49

M´ethodologie : exemples
Exemple 1
Un agriculteur veut allouer 150 hectares de surface irrigable entre culture de tomates et celles de
piments.
Il dispose de 480 heures de main d’œuvre et de 440 m3 d’eau.
Un hectare de tomates demande 1 heure de main d’œuvre, 4 m3 d’eau et donne un b´
en´
efice net
de 100 dirhams. Un hectare de piments demande 4 heures de main d’œuvre, 2 m3 d’eau et
donne un b´
en´
efice net de 200 dirhams.
Le bureau du p´
erim`
etre irrigu´
e veut prot´
eger le prix des tomates et ne lui permet pas de cultiver
plus de 90 hectares de tomates. Quelle est la meilleure allocation de ses ressources ?

PL

M ax z = 100x1 + 200x2






x1 + x2 ≥ 150

 s.c
4x1 + 2x2 ≥ 440
(P L) =

x1 + 4x2 ≥ 480




x1 ≥ 90



x1 ≥ 0, x2 ≥ 0
Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

12 / 49

M´ethodologie : Exemples

Exemple 2
Un sp´ecialiste en m´edecine a fabriqu´e un m´edicament (des pilules) pour gu´erir les
sujets atteints d’un rhume. Ces pilules sont fabriqu´ees selon deux formats :
• Petite taille : elle contient 2 grains d’aspirine, 5 grains de bicarbonate et 1

grain de cod´eine.
• Grande taille : elle contient 1 grain d’aspirine, 8 grains de bicarbonate et 6

grains de cod´eine.
Pour gu´erir la maladie, le sujet a besoin de 12 grains d’aspirine, 74 grains de
bicarbonate et 24 grains de cod´eine. D´eterminer le nombre de pilules minimales `a
prescrire au sujet pour qu’il soit gu´erit.

Question : Mod´eliser le probl`eme et ´ecrire le programme lin´eaire.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

13 / 49

M´ethodologie : Exemples

´
Etape
1 :Identification des variables de d´ecision.
Les variables de d´ecision qui repr´esentent des valeurs inconnues par le d´ecideur qui
est dans ce cas le sp´ecialiste en m´edecine sont :
• x1 : le nombre de pilules de petite taille `
a prescrire.
• x2 : le nombre de pilules de grande taille `
a prescrire.

On v´erifie bien que les variables de d´ecision x1 et x2 sont positives : x1 ≥ 0,
x2 ≥ 0.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

13 / 49

M´ethodologie : exemples

´
Etape
2 : Identification des contraintes
Les contraintes impos´ees par le probl`eme sur les valeurs possibles de x1 et x2
sont :
• La prescription doit contenir des pilules avec au moins 12 grains d’aspirine.

Sachant qu’une petite pilule contient 2 grains d’aspirine et qu’une grande
pilule contient un seul grain d’aspirine, on obtient la contrainte suivante :
2x1 + x2 ≥ 12
• De la mˆ
eme fa¸con que pour l’aspirine, la prescription du sp´ecialiste en

m´edecine doit contenir au moins 74 grains de bicarbonate. Ainsi la contrainte
suivante doit ˆetre satisfaite : 5x1 + 8x2 ≥ 74
• Finalement la contrainte impos´
ee par le fait que la prescription doit contenir

au moins 24 grains de cod´eine est x1 + 46x2 ≥ 24

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

14 / 49

M´ethodologie : exemples

´
Etape
2 : Identification des contraintes
Les contraintes impos´ees par le probl`eme sur les valeurs possibles de x1 et x2
sont :
• La prescription doit contenir des pilules avec au moins 12 grains d’aspirine.

Sachant qu’une petite pilule contient 2 grains d’aspirine et qu’une grande
pilule contient un seul grain d’aspirine, on obtient la contrainte suivante :
2x1 + x2 ≥ 12
• De la mˆ
eme fa¸con que pour l’aspirine, la prescription du sp´ecialiste en

m´edecine doit contenir au moins 74 grains de bicarbonate. Ainsi la contrainte
suivante doit ˆetre satisfaite : 5x1 + 8x2 ≥ 74
• Finalement la contrainte impos´
ee par le fait que la prescription doit contenir

au moins 24 grains de cod´eine est x1 + 46x2 ≥ 24

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

14 / 49

M´ethodologie : exemples

´
Etape
2 : Identification des contraintes
Les contraintes impos´ees par le probl`eme sur les valeurs possibles de x1 et x2
sont :
• La prescription doit contenir des pilules avec au moins 12 grains d’aspirine.

Sachant qu’une petite pilule contient 2 grains d’aspirine et qu’une grande
pilule contient un seul grain d’aspirine, on obtient la contrainte suivante :
2x1 + x2 ≥ 12
• De la mˆ
eme fa¸con que pour l’aspirine, la prescription du sp´ecialiste en

m´edecine doit contenir au moins 74 grains de bicarbonate. Ainsi la contrainte
suivante doit ˆetre satisfaite : 5x1 + 8x2 ≥ 74
• Finalement la contrainte impos´
ee par le fait que la prescription doit contenir

au moins 24 grains de cod´eine est x1 + 46x2 ≥ 24

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

14 / 49

M´ethodologie : exemples

´
Etape
3 : Identification de la fonction objectif.
On remarque qu’il y a plusieurs couples de solutions qui peuvent satisfaire les
contraintes sp´ecifi´ees `a l’´etape 2. La prescription doit contenir le minimum
possible de pilules. Donc le crit`ere de s´election de la quantit´e de pilules `a prescrire
est celle qui minimise le nombre total des pilules z = x1 + x2

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

15 / 49

M´ethodologie : exemples

Exemple 2
Un sp´
ecialiste en m´
edecine a fabriqu´
e un m´
edicament (des pilules) pour gu´
erir les sujets atteints
d’un rhume. Ces pilules sont fabriqu´
ees selon deux formats :

• Petite taille : elle contient 2 grains d’aspirine, 5 grains de bicarbonate et 1 grain de cod´eine.
• Grande taille : elle contient 1 grain d’aspirine, 8 grains de bicarbonate et 6 grains de
cod´
eine.
Pour gu´
erir la maladie, le sujet a besoin de 12 grains d’aspirine, 74 grains de bicarbonate et 24
grains de cod´
eine. D´
eterminer le nombre de pilules minimales `
a prescrire au sujet pour qu’il soit
gu´
erit.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

16 / 49

M´ethodologie : exemples
Exemple 2
Un sp´
ecialiste en m´
edecine a fabriqu´
e un m´
edicament (des pilules) pour gu´
erir les sujets atteints
d’un rhume. Ces pilules sont fabriqu´
ees selon deux formats :

• Petite taille : elle contient 2 grains d’aspirine, 5 grains de bicarbonate et 1 grain de cod´eine.
• Grande taille : elle contient 1 grain d’aspirine, 8 grains de bicarbonate et 6 grains de
cod´
eine.
Pour gu´
erir la maladie, le sujet a besoin de 12 grains d’aspirine, 74 grains de bicarbonate et 24
grains de cod´
eine. D´
eterminer le nombre de pilules minimales `
a prescrire au sujet pour qu’il soit
gu´
erit.

PL
Le programme lin´eaire qui mod´elise ce probl`eme m´edical est donc le suivant :

M in z = x1 + x2





 s.c
2x1 + x2 ≥ 12
(P L) =
5x1 + 8x2 ≥ 74



x1 + 46x2 ≥ 24 ≥ 90



x1 ≥ 0, x2 ≥ 0
Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

16 / 49

Forme canonique d’un PL

• Probl`
eme canonique de maximisation

Pour un probl`eme de maximisation, on peut l’´ecrire sous la forme canonique suivante :

n
X



M ax z =
cj xj




j=1
n
X
(P L1) =

s.c
aij xj ≤ bi
i = 1, . . . , m




j=1


xj ≥ 0
j = 1, . . . , n.
Le programme (P L1) est un probl`eme de maximisation dont les variables xj sont
toutes non n´egatives et les contraintes sont du type inf´erieure ou ´egale : ” ≤ ”.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

17 / 49

Forme canonique d’un PL

• Probl`
eme canonique de minimisation

Pour un probl`eme de minimisation, on peut l’´ecrire sous la forme canonique suivante :

n
X



M in z =
cj xj




j=1
n
X
(P L2) =

s.c
aij xj ≥ bi
i = 1, . . . , m




j=1


xj ≥ 0
j = 1, . . . , n.
Le programme (P L2) est un probl`eme de maximisation dont les variables xj sont
toutes non n´egatives et les contraintes sont du type inf´erieure ou ´egale : ” ≥ ”.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

17 / 49

Notation matricielle

Cette notation est aussi une r´ef´erence non n´egligeable pour les probl`emes de
programmation lin´eaire.


 M ax z = Cx
(P L4) =
s.c Ax ≤ b


x ≥ 0.
Avec
C =
(c1 . . . cn ) : Vecteur des coefficients de l’objectif.
x1
 .. 
x =  .  : Les variables de d´ecisions du probl`eme donn´e.
xn

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

18 / 49

M´ethodes de r´esolution : exemple
Exemple d’application
Une entreprise fabrique et vend deux mod`eles de buffets de cuisine en bois
massif : le mod`ele A et le mod`ele B.
Pour le prochain exercice comptable une ´etude de march´e a montr´e qu’il ´etait
possible de vendre 200 unit´es de A et 300 unit´es de B.
Le mod`ele A n´ecessite deux fois plus de bois que le mod`ele B, pour le nouvel
exercice, l’approvisionnement pr´evu permettrait de fabriquer 450 buffets A.
Le mod`ele A est beaucoup plus travaill´e et mieux fini que le mod`ele B, il n´ecessite
3 fois plus de temps de fabrication que le buffet B . Le temps de travail pr´evisible,
pour le futur exercice, permettrai de fabriquer au maximum 660 mod`eles B.
La marge sur coˆ
ut variable unitaire procur´ee par la vente d’un buffet A est de 6,
celle produite par un buffet B est de 4.
L’entreprise cherche un programme de production qui lui permettrai de maximiser
sa marge sur coˆ
ut variable globale compte tenu des contraintes qui lui sont
impos´ees.
Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

19 / 49

M´ethodes de r´esolution

Travail `a faire :
1 Mod´
eliser le probl`eme moyennant un programme lin´eaire.
2

Donner une solution graphique.

3

Donner une solution par le simplexe.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

20 / 49

M´ethodes de r´esolution : exemple
1- Mod´
eliser le probl`
eme moyennant un programme lin´
eaire

Variables de decision
L’un des objectifs est de d´eterminer le nombre de buffets de chaque type `a
fabriquer et `a vendre au cours du prochain exercice. Appelons :
• x le nombre de buffets A `
a fabriquer et `a vendre ;
• y le nombre de buffets B `
a fabriquer et `a vendre ;

x et y sont des inconnues qui peuvent prendre de nombreuses valeurs, on les
appelle variables d’activit´es. Le couple (x, y) est appel´e programme.
Si on donne `a x et `a y les valeurs x1 et y1 le couple (x1 , y1 ) sera un programme
de fabrication. Si on donne `a x et `a y les valeurs x2 et y2 le couple (x2 , y2 ) sera
un autre programme de fabrication.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

21 / 49

M´ethodes de r´esolution : exemple
1- Mod´
eliser le probl`
eme moyennant un programme lin´
eaire

Variables de decision
L’un des objectifs est de d´eterminer le nombre de buffets de chaque type `a
fabriquer et `a vendre au cours du prochain exercice. Appelons :
• x le nombre de buffets A `
a fabriquer et `a vendre ;
• y le nombre de buffets B `
a fabriquer et `a vendre ;

x et y sont des inconnues qui peuvent prendre de nombreuses valeurs, on les
appelle variables d’activit´es. Le couple (x, y) est appel´e programme.
Si on donne `a x et `a y les valeurs x1 et y1 le couple (x1 , y1 ) sera un programme
de fabrication. Si on donne `a x et `a y les valeurs x2 et y2 le couple (x2 , y2 ) sera
un autre programme de fabrication.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

21 / 49

M´ethodes de r´esolution
1- Mod´
eliser le probl`
eme moyennant un programme lin´
eaire

Les variables x et y prennent des valeurs r´eelles soumises `a des contraintes :
de signe
de march´e :

x ≥ 0 et y ≥ 0

Contraintes de march´e :
x ≤ 200 et y ≤ 300

Un nombre de buffets est forc´ement
positif.

de fabrication :
Contraintes de fabrications :
M contraintes d’approvisionnement :
x + 2y ≤ 450 ;
M contraintes de temps de travail :
3x + y ≤ 660.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

22 / 49

M´ethodes de r´esolution
1- Mod´
eliser le probl`
eme moyennant un programme lin´
eaire

Les variables x et y prennent des valeurs r´eelles soumises `a des contraintes :
de signe
de march´e :

x ≥ 0 et y ≥ 0

Contraintes de march´e :
x ≤ 200 et y ≤ 300

Un nombre de buffets est forc´ement
positif.

de fabrication :
Contraintes de fabrications :
M contraintes d’approvisionnement :
x + 2y ≤ 450 ;
M contraintes de temps de travail :
3x + y ≤ 660.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

22 / 49

M´ethodes de r´esolution : exemple
1- Mod´
eliser le probl`
eme moyennant un programme lin´
eaire

La fonction objectif (´economique) :
La marge sur coˆ
ut variable globale r´esultant du programme (x, y) sera ´egale `a :
M = 6x + 4y.
Le but du traitement que nous allons pratiquer est de d´eterminer l’ensemble des
programmes (x, y) donnant `a M une valeur positive et de choisir parmi ces
programmes celui qui donne `a M sa valeur maximale.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

23 / 49

M´ethodes de r´esolution : exemple
1- Mod´
eliser le probl`
eme moyennant un programme lin´
eaire

La fonction objectif (´economique) :
La marge sur coˆ
ut variable globale r´esultant du programme (x, y) sera ´egale `a :
M = 6x + 4y.
Le but du traitement que nous allons pratiquer est de d´eterminer l’ensemble des
programmes (x, y) donnant `a M une valeur positive et de choisir parmi ces
programmes celui qui donne `a M sa valeur maximale.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

23 / 49

M´ethodes de r´esolution : exemple
1- Mod´
eliser le probl`
eme moyennant un programme lin´
eaire

Programme lin´eaire sous forme canonique :
Le programme lin´eaire qui mod´elise le probl`eme est donc le suivant :

M ax M = 6x + 4y






x ≤ 200

 s.c
y ≤ 300
(P L) =

x
+ 2y ≤ 450




3x
+ y ≤ 660



x ≥ 0, y ≥ 0
Ce programme lin´eaire permet la recherche du maximum d’une fonction
´
economique lin´
eaire sous des contrainte lin´
eaires.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

24 / 49

M´ethodes de r´esolution
3- R´
esolution par l’algorithme du simplexe

Programme lin´eaire sous forme standard :
Pour traiter alg´ebriquement un programme lin´eaire il est n´ecessaire de transformer
les in´equations du programme canonique en ´equations.
Pour cela des variables d’´
ecart sont introduites dans ces derni`eres
Soient t1 , t2 , t3 et t4 les variables d’´ecart correspondant `a notre exemple. L’´ecriture
du programme lin´eaire sous forme d’´equations le met sous forme standard.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

25 / 49

M´ethodes de r´esolution
3- R´
esolution par l’algorithme du simplexe

Programme lin´eaire sous forme standard :
Pour traiter alg´ebriquement un programme lin´eaire il est n´ecessaire de transformer
les in´equations du programme canonique en ´equations.
Pour cela des variables d’´
ecart sont introduites dans ces derni`eres
Soient t1 , t2 , t3 et t4 les variables d’´ecart correspondant `a notre exemple. L’´ecriture
du programme lin´eaire sous forme d’´equations le met sous forme standard.

M ax M = 6x + 4y






x + t1 = 200

 s.c
y + t2 = 300
(S0 ) =

x + 2y + t3 = 450




3x
+ y + t4 = 660



x ≥ 0, y ≥ 0, t1 ≥ 0, t2 ≥ 0, t3 ≥ 0, t4 ≥ 0.

Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

25 / 49

M´ethodes de r´esolution
3- R´
esolution par l’algorithme du simplexe


M ax M = 6x + 4y






x + t1 = 200

 s.c
y + t2 = 300
(S0 ) =

x + 2y + t3 = 450




3x
+ y + t4 = 660



x ≥ 0, y ≥ 0, t1 ≥ 0, t2 ≥ 0, t3 ≥ 0, t4 ≥ 0.
Chaque contrainte ´economique est transform´ee en ´equation par l’adjonction d’une
variable d’´ecart positive. La saturation d’une contrainte entraˆıne l’annulation de la
variable d’´ecart correspondante.
Le programme lin´eaire sous sa forme standard comporte 4 ´equations et 6 inconnues :
2 variables d’activit´e et 4 variables d’´ecart. Il constitue le syst`eme S0 .
A noter
• Les variables d’´
ecart : les variables de base ;
• Les autres : les variables hors base.
Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

26 / 49

M´ethodes de r´esolution
3- R´
esolution par l’algorithme du simplexe


M ax M = 6x + 4y






x + t1 = 200

 s.c
y + t2 = 300
(S0 ) =

x + 2y + t3 = 450




3x
+ y + t4 = 660



x ≥ 0, y ≥ 0, t1 ≥ 0, t2 ≥ 0, t3 ≥ 0, t4 ≥ 0.
Chaque contrainte ´economique est transform´ee en ´equation par l’adjonction d’une
variable d’´ecart positive. La saturation d’une contrainte entraˆıne l’annulation de la
variable d’´ecart correspondante.
Le programme lin´eaire sous sa forme standard comporte 4 ´equations et 6 inconnues :
2 variables d’activit´e et 4 variables d’´ecart. Il constitue le syst`eme S0 .
A noter
• Les variables d’´
ecart : les variables de base ;
• Les autres : les variables hors base.
Anas RACHID (ENSAM)

Recherche Op´
erationnelle

Octobre 2013

26 / 49



Documents similaires


recherche opertionnelle
methodes d identification approchee
ro
tp n7
ortrans appeloffresdpostdoc
cours programmation lineaire 4 1


Sur le même sujet..