Outils Mathé- Matière: Optimisation

matiques

Pr [Link] Kyal

Outils Mathématiques

Pr [Link] Kyal

ENSA d’Agadir

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques

Pr [Link] Kyal

Chapitre I : Formulation d’un Programme linéaire et résolution

graphique

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Introduction

Outils Mathé-
matiques

Pr [Link] Kyal
→ La programmation linéaire traite de manière générale des
problèmes d’allocation de ressources limitées d’une façon
optimale.
→ La programmation linéaire emploie des modèles
mathématiques pour décrire des problèmes réels.
→ L’adjectif "linéaire" indique que toutes les fonctions
mathématiques de ce modèle sont linéaires tandis que le
terme "programmation" ă signifie essentiellement
planification.
→ Les applications pratiques sont partout,dans les domaines
de transport, Energie, Administration,
Télécommunications, Informatique, Gestion de projet,
Production, Comptabilité, etc...
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Comment écrire le modèle mathématique

Outils Mathé-
matiques

Pr [Link] Kyal Généralement il y a trois étapes à suivre pour pouvoir

construire le modèle d’un programme linéaire :
1 Identifier les variables du problème à valeur non connues
(variable de décision) et les représenter sous forme
symbolique (exp. x1 , x2 , · · · ).
2 Identifier l’objectif ou le critère de sélection et le
représenter sous une forme linéaire en fonction des
variables de décision. Spécifier si le critère de sélection est
à maximiser ou à minimiser.
3 Identifier les restrictions (les contraintes) du problème et
les exprimer par un système d’équations et d’inéquations
linéaires.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé- La tâche de formulation demande généralement une certaine
matiques
expertise et connaissance du problème pour pouvoir relever
Pr [Link] Kyal
facilement les différentes composantes du problème et ainsi
donner un programme qui modélise au mieux la situation rélle.
Dans ce qui suit, on présentera quelques exemples de
formulation en programme linéaire liés à différents problèmes
de décision.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Problème de l’agriculteur

Outils Mathé-
matiques

Pr [Link] Kyal

Un agriculteur veut allouer 150 hectares de surface irrigable

entre culture de tomates et celles de piments. Il dispose de
440m3 d’eau. Un hectare de tomates demande 4m3 d’eau et
donne un bénéfice net de 100 Euros. Un hectare de piments
demande 2m3 d’eau et donne un bénéfice net de 200 Euros.
Quelle est la meilleure allocation de ses ressources ?

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques Formulation du problème en un programme linéaire :
Pr [Link] Kyal Etape 1 Identification des variables de décision.
Les deux activités que l’agriculteur doit
déterminer sont les surfaces à allouer pour la
culture de tomates et de piments :
i) x1 : la surface alloué à la culture des
tomates
ii) x2 : la surface alloué à la culture des
piments.

On vérifie bien que les variables de décision x1 et

x2 sont positives

x1 ≥ 0 et x2 ≥ 0
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques

Pr [Link] Kyal

Etape 2 Identification de la fonction objectif.

La fonction objectif consiste à maximiser le profit
apporté par la culture des tomates et de piments.
Les contributions respectives 100 et 200, des deux
variables de décision x1 et x2 sont proportionnelles
à leur valeur. La fonction objectif est donc

max z = 100x1 + 200x2

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques

Pr [Link] Kyal

Etape 3 Identification des contraintes.

Dans ce problème les contraintes représentent la
disponibilité des facteurs de production :
i) Terrain : l’agriculteur dispose de
150 hectares de terrain, ainsi la
contrainte lié à la limitation de la
surface de terrain est

x1 + x2 ≤ 150

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques

Pr [Link] Kyal

ii) Eau : la culture d’un hectare de tomates demande

4m3 d’eau et celle d’un hectare de piments
demande 2m3 mais l’agriculteur ne dispose que
de 440m3 . La contrainte qui exprime les
limitations des ressources en eau est

4x1 + 2x2 ≤ 440.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques

Pr [Link] Kyal

Le programme linéaire qui modélise le problème de l’agriculteur

est :
max z = 100x1 + 200x2
sous les contraintes


 x1 + x2 ≤ 150
4x1 + 2x2 ≤ 440

 x
1 ≥ 0, x2 ≥ 0

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Présentation Théorique

Outils Mathé-
matiques
Un programme linéaire consiste à trouver le maximum ou le
Pr [Link] Kyal
minimum d’une fonction objectif en satisfaisant un certain
nombre de contraintes. En suivant les étapes de formulation, la
forme générale d’un modèle de programmation linéaire est
max ( ou min)z = c1 x1 + · · · + cn xn
sous les contraintes


 a11 x1 + a12 x2 + ··· + a1r xn {≤, =, ≥} b1

 .. ..



 . .



 + ··· {≤, =, ≥}
 ai1 x1 + ai2 x2 + air xn bi
..
 .



 am1 x1 + am2 x2 + ··· + amr xn {≤, =, ≥} bm



 ..

 .


x1 ≥ 0 , x2 ≥ 0 , ··· , xn ≥ 0
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Exercice sur la formulation d’un programme linéaire

Outils Mathé-
matiques

Pr [Link] Kyal
Un spécialiste en médecine a fabriqué un médicament (des
pilules) pour guérir les sujets atteints d’un rhume. Ces pilules
sont fabriqués selon deux formats :
- Petite taille : elle contient 2 grains d’aspirine, 5
grains de bicarbonate et 1 grain de codéine.
- Grande taille : elle contient 1 grain d’aspirine, 8
grains de bicarbonate et 6 grains de codéine.
Pour guérir la maladie, le sujet a besoin de 12 grains d’aspirine,
74 grains de bicarbonate et 24 grains de codéine.
Déterminer le nombre de pilules minimales à prescrire au sujet
pour qu’il soit guérit.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Les étapes de la résolution graphique d’un
programme linéaire
Outils Mathé-
matiques

Pr [Link] Kyal
Dans le cas de deux variables de décision, un problème linéaire
peut être résolu de manière purement graphique, on suit le
processus en trois étapes.
Prenons l’exemple du programme linéaire suivant :

max z= x1 + 3x2


 x1 + x2 ≤ 14

 − 2x + 3x
1 2 ≤ 12
s.c

 2x − x ≤ 12


1 2
x1 , x2 ≥ 0

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Première étape

Outils Mathé-
matiques

Pr [Link] Kyal

Elle consiste à représenter graphiquement la région réalisable.

Définition
On appelle région réalisable ou région admissible,
l’ensemble des valeurs de variables de décision qui satisfont
toute les contraintes.
Les solutions qui, en plus, optimisent la fonction objectif sont
dénommées solutions optimales.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé- Prenons, par exemple, la première de ces contraintes
matiques

Pr [Link] Kyal
x1 + x2 ≤ 14

l’équation
x1 + x2 = 14
correspond à une droite dans le plan et l’équation

x1 + x2 ≤ 14

représente un demi plan (ou demi-espaces appelé hyperplans)

fermé délimité par la droite d’équation

x1 + x2 = 14

donc il s’agit du demi-plan fermé contenant l’origine puisque

l’origine (0, 0) satisfait la contrainte d’inégalité.
.
.
.
.
.
. . . . .
. . . .
. . . .
. . . .
. . . .
. . . . .
.
.
.
.
.
.
.
.
.
Outils Mathé-
matiques

Pr [Link] Kyal

De même, le demi-plan fermé délimité par la droite d’équation

−2x1 + 3x2 = 12

et contenant l’origine correspont à la deuxième contrainte

−2x1 + 3x2 ≤ 12

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques

Pr [Link] Kyal

Les contraintes de non négativité réduisent la région de

solutions admissibles (ou région admissible) au premier quart
positif du plan.
L’ensemble de ces contraintes forme un ensemble fermé
convexe appelé polytope.
En conclusion, la région grise représente la région admissible du
problème, autrement dit, cette région correspond a l’ensemble
des points dans le plan qui satisfont toute les contraintes du
problème.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques

Pr [Link] Kyal
x2

10
8
6
4
2
0 x1
−2 0 2 4 6 8 10
−2

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Deuxième étape : Les droites d’isovaleur

Outils Mathé-
matiques
La deuxième étape de la résolution graphique consiste à
Pr [Link] Kyal
représenter graphiquement les lignes d’isovaleur ou lignes
d’isoprofit de la fonction objectif. Considérons des valeurs
successives de l’objectif :
z = c1 x1 + c2 x2
ce qui correspond graphiquement à des droites parallèles, en
effet, toutes les droites d’équation c1 x1 + c2 x2 sont
perpendiculaire au vecteur de composantes (c1 , c2 ) et la valeur
de z Croît dans le sens de ce vecteur. Notons que Les points de
toute droite z = c1 x1 + c2 x2 sont les points qui donnent la
même valeur du profit, d’où le nom de droite d’isovaleur ou
d’isoprofit de la fonction objectif. dans notre cas, la fonction
objectif est d’équation
z = x1 + 3x2 .
. . . . . . . . . . . . . . . . . . . .
et le vecteur perpendiculaire aux droites z est (1, 3)t .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques

Pr [Link] Kyal
x2
z = 30
10
8
z = 18
6
z = 12
4
2
0 x1
−2 0 2 4 6 8 10
−2

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Troisième étape de la résolution graphique : La
solution optimale
Outils Mathé-
matiques
Puisque, dans notre cas, on cherche à maximiser la fonction
Pr [Link] Kyal
objectif, il faut prendre la droite d’isoprofit qui donne la valeur
la plus élevée de la fonction objectif et qui touche encore la
région réalisable.

x2
z = 30
10 A(6, 8)
8 b

z = 18
6
z = 12
4
2
0 .
.
.
.
.
. . . . .
. . . .
x1
. . . .
. . . .
. . . .
. . . . .
.
.
.
.
.
.
.
.
.
Outils Mathé- ( )
matiques
6
Pr [Link] Kyal Ici, le point A est le seul point qui appartient à la plus
8
haute droite z passant par la région admissible. De plus, ce
point est à l’intersection des deux droites

x1 + x2 = 14

et
−2x1 + 3x2 = 12.
La solution du système, formé par ces deux équations linéaires,
corréspond alors aux coordonnées du point A dont les valeurs
sont x1 = 6 et x2 = 8. Par conséquent la valeur optimale de la
fonction objectif est zmax = 30 pour la solution optimale
(x1∗ , x2∗ ) = (6; 8).
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Exemple d’un domaine borné avec une infinité de
solutions
Outils Mathé-
matiques

Pr [Link] Kyal

Considérons le problème de PL suivant :

max z= 3x1 + 2x2


 x1 ≤ 4



 2x2 ≤ 12
s.c 3x1 + 2x2 ≤ 18



 x1 ≥ 0


x2 ≥ 0

dont la résolution graphique est la suivante :

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques

Pr [Link] Kyal
x2

(2, 6)
(0, 6) b b

b (4, 3)

b b x1
(0, 0) (4, 0)

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques

Pr [Link] Kyal

Ce problème admet une infinité de solutions optimales. En effet

la dernière droite d’isovaleur coïncide avec la droite d’équation
3x1 + 2x2 = 18, donc la valeur optimale est zmax = 18, en plus,
les solutions optimales sont tous les points
( appartenant
) au
2
segment [A, B] avec A de coordonnées et B de
6
( )
4
coordonnées
3

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques

Pr [Link] Kyal

Remarque
On remarque que dans ces deux exemples, la région admissible
est bornée, c’est un polygone dont les côtés sont les segments
des droites représentant les contraintes linéaires. La solution de
ces problèmes est toujours un sommet du polygone lorsqu’elle
est unique, ou un côté du polygone lorqu’il existe une infinité
de solutions optimales.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Exemples de domaines non bornés

Outils Mathé-
matiques

Pr [Link] Kyal

Considérons maintenant le problème de PL suivant :

max z= −4x1 + x2


 −2x1 + x2 ≤ 2
s.c x1 − 2x2 ≤ 2

 x1 , x2 ≥ 0

dont la résolution graphique est la suivante :

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques
x2
Pr [Link] Kyal

(0, 2) b

b b x1
(0, 0) (2, 0)

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques

Pr [Link] Kyal

La région admissible n’est pas bornée mais le sommet A est

une solution optimale de ce problème.
Si on change la fonction objectif, pour les mêmes contraintes,
par la fonction
max z = −2x1 + x2 ,
Tous les points de la demi droite [A, +∞[ sont solutions du
problème .

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques

Pr [Link] Kyal
x2

(0, 2) b

b b x1
(0, 0) (2, 0)

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé- Par contre, avec les mêmes contraintes, si on a la fonction
matiques

Pr [Link] Kyal max z = x1 + x2 ,

il n’y a pas de solution optimale finie pour ce nouveau
problème.

x2

(0, 2) b

b b
.
.
.
.
.
. x1
. . . .
. . . .
. . . .
. . . .
. . . .
. . . . .
.
.
.
.
.
.
.
.
.
 Exemple d’un domaine vide

Outils Mathé-
matiques

Pr [Link] Kyal
lorsque toutes les contraintes sont incompatibles, il n y a pas
de solution admissible et donc la région admissible est est vide,
prenons l’exemple suivant :

maxz = x1 + 3x2

s.c
x1 − x2 ≤ −1
−x1 − x2 ≤ −3
2x1 + x2 ≤ 2
x1 , x2 ≥ 0
dont la résolution graphique est la suivante :

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques x2
Pr [Link] Kyal

0 x1
0 1 2 3

On peut alors conclure que pour un problème de

.
.
.
.
.
. . . . .
. . . .
. . . .
. . . .
. . . .
. . . . .
.
.
.
.
.
.
.
.
.
Outils Mathé-
matiques
1 La région réalisable est bornée, dans ce cas :
Pr [Link] Kyal 1 soit il y a une solution optimale unique qui correspond à
un sommet de la région admissible.
2 soit il y a une infinité de solutions optimales qui
correspondent à une frontière de la région admissible c’est
à dire un segment.
2 La région réalisable est non bornée, dans ce cas :
1 soit il n’y a pas de solution optimale finie, on dit alors que
le problème est non borné.
2 soit il y a une solution optimale unique qui correspond à
un sommet de la région admissible.
3 soit il y a une infinité de solutions optimales qui
correspondent à une frontière de la région admissible, dans
ce cas, il s’agit d’un segment ou d’une demi droite.
3 La région admissible est vide, dans ce cas, il n’y a pas de
solutions optimales.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Résolution graphique d’un problème linéaire en
nombres entiers
Outils Mathé-
matiques

Pr [Link] Kyal Etant donné le problème suivant :

max z = x1 + x2 ,


 2x1 + 2x2 ≥ 3,



 2x
1 − 2x2 ≤ 3,
s.c.

 2x1 + 4x2 ≤ 19,



 x1 , x2 ≥ 0 et entiers.

(x1 , x2 )∗ = (3, 3)
z∗ = 6

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques

Pr [Link] Kyal x2
bc bc bc bc bc bc

bc b b bc bc bc

bc b b b b bc

bc b b b b bc

bc bc b b bc bc

bc bc bc bc bc bc x1

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Exemple 2

Outils Mathé-
matiques

Pr [Link] Kyal max z = x1 + x2 ,



 x1 + x2 ≥ 2,



 x2 ≥ 1,





 x1 − x2 ≤ 1,


 x1 ≤ 3,
s.c.

 x1 + 2x2 ≤ 9,



 x2 ≤ 4,





 x1 ≥ 0,


 x1 , x2 entiers.
(x1 , x2 )∗ = (3, 3)
z∗ = 6
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Outils Mathé-
matiques

Pr [Link] Kyal x2
bc bc bc bc bc bc

bc b b bc bc bc

bc b b b b bc

bc b b b b bc

bc bc b b bc bc

bc bc bc bc bc bc x1

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .