RECHERCHE OPERATIONNELLE -

PROGRAMMATION LINEAIRE -

1
INTRODUCTION
 Exemple 1:
Une entreprise de construction d’automobiles possède trois usines situées
respectivement à Paris, Strasbourg et Lyon.
Le métal nécessaire à la construction des véhicules est disponible au port
du Havre et de Marseille.
Les coûts de transport sont supposés varier proportionnellement aux
quantités transportées, les coûts unitaires sont donnés par le tableau
suivant :
Paris Strasbourg Lyon

Marseille 5 6 3

Le Havre 3 5 4

Les quantités de ce métal nécessaires chaque semaine sont 400, 300 et

200 tonnes respectivement pour les usines de Paris, Strasbourg et Lyon.
Tandis que les quantités disponibles sont de 550 et 350 tonnes par
semaine respectivement à Marseille et au Havre.
2
Quel est le meilleur plan d’approvisionnement possible ?
INTRODUCTION
 Exemple 2 :
Pour relier une mine à un terminal de chargement de minerai, on doit
construire une voie ferrée pour descendre le minerai avec des wagonnets.
On donne dans le tableau suivant les coûts de construction des tronçon qui
relient les différents nœuds du réseau. La mine est au nœud 1 et le
terminal au nœud 8. Le coût de construction du tronçon qui va, par
exemple du 1er nœud au nœud n° 2 est de 12 Millions de Dinars.

2 3 4 5 6 7 8
1 12 4 2
2 3
3 7 15
4 18 29
5 8
6 4 9
7 4

Quelle est la voie ferrée la plus économique ?

3
INTRODUCTION
 Exemple 3 :
La table ci-dessous donne la composition et le coût unitaire de 9 alliages
standards de plomb, zinc et étain.

On voudrait fabriquer un nouvel alliage contenant au moins 30 % de

plomb, 30 % de zinc et 40 % d’´etain.

Quelle quantité doit-on utiliser de chaque type d’alliage

de façon à avoir le plus faible coût possible ?
4
DÉFINITIONS
 Problème d’optimisation

➢ atteindre un (ou plusieurs) objectif(s) t.q :

• maximisation : gains, chiffre d’affaires, volume
d’activité, débit, capacité, ….
• minimisation : dépenses, coûts, distances, pertes,
temps, ….
➢ en respectant les contraintes du pb t.q :
• disponibilité de ressources (MP, MO, heures machines,
…)
• demande clients,
• capacité réseau,
• etc …

5
DÉFINITIONS
 Recherche Opérationnelle
Méthode scientifique d’aide à la prise de décision au sein
d’organisations complexes quelque soit leur domaine d’application
(transport, télécommunication, industrie, services, santé, ….).

1. Modélisation : traduction du pb sous forme de :

• Problème mathématique : Programmation mathématique
• Graphe : Théorie des graphes

2. Résolution du pb : recherche de la (ou les) solution(s) optimale(s)

en utilisant des outils mathématiques

6
DÉFINITIONS
 Programmation Mathématique / Linéaire

Traduire le pb d’optimisation sous forme d’un pb mathématique :

• identifier les variables de décision : variables qui traduisent
les décisions qu’on cherche à prendre,
• définir la fonction objectif : fonction mathématique qui traduit
l’objectif du pb,
• définir les contraintes : équations et inéquations qui traduisent
les contraintes du pb.

PL ≡ Fonction objectif + contraintes : linéaires

7
FORMULATION D’UN PL
Exemple de formulation de PL :

L’entreprise VITRE SAR SA. Fabrique des vitres de haute qualité pour portes
et fenêtres. L’entreprise souhaite lancer deux nouveaux produits :
-Le produit 1 requiert des ressources dans l’atelier 1 et 3
-Le produit 2 requiert des ressources dans l’atelier 2 et 3.

Cadre aluminium Cadre en bois Assemblage

pour porte pour fenêtre Vitre & cadre

Atelier 1 Atelier 2 Atelier 3

Quel est le mix de produits 1 et 2
le plus profitable à réaliser dans
l’atelier 3 ?
Ressource
partagée
8
FORMULATION D’UN PL
Les données
Atelier Temps de Temps de
production production
(heures/lot) disponible
Produit 1 Produit 2 (heures/semaine)
Atelier 1 1 0 4
Atelier 2 0 2 12
Atelier 3 3 2 18
Profit 3000 5000
(TND/lot)
Un lot = 20 Pièces
L’entreprise cherche à déterminer le nombre de lots à réaliser par semaine pour
les deux produits 1 et 2 dans l’objectif de maximiser le profit total, en respectant
les restrictions imposées par les capacités limitées des machines des 3 ateliers.
9
FORMULATION D’UN PL
 Variables de décision
elles doivent décrire les décisions à prendre.

L’entreprise doit déterminer le nombre de lots de produits 1 et de

produits 2 à produire par semaine.

On définit alors :
x1 : le nombre de lots de produits 1 à produire par semaine,
x2 : le nombre de lots de produits 2 à produire par semaine.

10
FORMULATION D’UN PL
 Fonction Objectif

Elle traduit l’objectif du pb.

L’objectif est exprimé sous forme d’une fonction des variables de décision,
appelée fonction objectif.

Profit hebdomadaire = Revenu hebdomadaire – Coût hebdomadaire

= 3000 x1 + 5000 x2 (en TND)
= 3 x1 + 5 x2 (en Milles TND)

11
FORMULATION D’UN PL
 Les contraintes
Si l’entreprise est libre de choisir n’importe quelles valeurs pour x1 et x2,
elle peut avoir un profit très large en produisant de très grandes
quantités de produits 1 et de produits 2.
Malheureusement, ces valeurs sont limitées à causes des restrictions
imposées par l’environnement de l’entreprise d’une part et par les
ressources à capacité finie, d’autre part. Ces restrictions sont exprimées
par le biais des contraintes.

 Contraintes sur les ressources

 Contraintes de signe

12
FORMULATION D’UN PL

 Les contraintes sur les ressources

Chaque semaine la capacité de production de l’atelier 1 est limitée à 4 heures

1 x1 + 0 x2  4
Chaque semaine la capacité de production de l’atelier 2 est limitée à 12 heures
0 x1 + 2 x2 12
Chaque semaine la capacité de production de l’atelier 3 est limitée à 18 heures
3 x1 + 2 x2  18

13
FORMULATION D’UN PL
 Les contraintes de signes

On doit préciser l’ensemble des valeurs auquel appartiennent les variables de

décision.
Est-ce que les variables x1 et x2 peuvent prendre n’importe quelles valeurs réelles,
ou seulement des valeurs non négatives ou encore des valeurs entières ou
binaires ?

Dans cet exemple, le nombre de lots ne peut pas être négatif.

x1  0, x2  0

Remarque : Ici, nous supposons qu’on accepte les lots non entiers. Autrement, x1
et x2 doivent être entiers et il s’agit d’un programme linéaire en nombres entiers.

14
FORMULATION D’UN PL
En résumé le modèle mathématique qui correspond à l’exemple s’écrit
comme suit :

Max Z(x)=3 x1 + 5 x2 (1.1)

s.c (Sous les contraintes) :
x1 4 (1.2)
2 x2 12 (1.3)
3 x1 + 2 x2  18 (1.4)
x1  0, x2  0 (1.5)

15
 RÉSOLUTION
D’une manière générale, un PL est un problème mathématique qui s’écrit sous la
forme :

Max (ou min) Z(x) = Ct x

S.c. Ax b
x0
Où :
n : nbre de variables du PL et m : nbre de contraintes,
x IRn : vecteur des variables de décision,
C IRn : vecteur coût,
b IRm : vecteur seconds membres,
A est une matrice (m,n) : matrice des contraintes.
La fonction à optimiser (Ct x) est appelée fonction objectif.
Les inégalités définies par le système linéaire (AX  b) sont les contraintes du
problème et les composantes du vecteur x sont les variables de décision.

Résolution ≡ recherche de solutions optimales (vecteur x), si elles existent

16
RÉSOLUTION
 Un vecteur x est une solution réalisable s’il vérifie toutes
les contraintes du problème (i.e. Ax b et x  0).

 L’ensemble de tous les vecteurs, solutions réalisables, est

appelé domaine réalisable, noté (DR).

 Donner des exemples de solutions réalisables et de solutions

non réalisables relatives à l’exemple.

 Une solution réalisable x* est optimale si la valeur de Ctx*

est la meilleure des valeurs de Ctx pour tout x, solution
réalisable.

17
RÉSOLUTION
Méthode graphique

 Applicable pour programmes linéaires ayant au plus deux variables de décision.

 Etapes :

 Dans le plan défini par les deux variables de décision, on trace les différentes droites
représentant les contraintes du problème et en déduire le domaine réalisable du pb
considéré.

 On trace ensuite la ligne isoprofit (ou isocoût) représentant la fonction objectif.

 Pour trouver une solution optimale, on déplace la ligne isoprofit dans la direction qui
permet d’optimiser (maximiser ou minimiser) la valeur de la fonction objectif. Le ou les
deriniers points du DR touché(s) par cette ligne donne(nt) la (ou les) solution(s) optimale(s)
du PL considéré.

18
RÉSOLUTION
Exemple :

Max Z(x)=3 x1 + 5 x2
s.c (Sous les contraintes) :
x1 4
2 x2 12
3 x1 + 2 x2  18
x1  0, x2  0

19
 RÉSOLUTION
Exemple :
Détermination du DR
x2
6

Max Z(x)=3 x1 + 5 x2
s.c (Sous les contraintes) :
4
x1 4
2 x2 12
3 x1 + 2 x2  18
2
x1  0, x2  0

-2 2 4 6 8 x1
-2

20
 RÉSOLUTION
Exemple :
Détermination du DR
x2 1ère contrainte : x1  4
6

Max Z(x)=3 x1 + 5 x2
s.c (Sous les contraintes) :
4
x1 4
2 x2 12
3 x1 + 2 x2  18
2
x1  0, x2  0

-2 2 4 6 8 x1
-2

D1: x1 = 4 21
 RÉSOLUTION
Exemple :
Détermination du DR 2ème contrainte : x2  6
x2
6 D2: x2 = 6
Max Z(x)=3 x1 + 5 x2
s.c (Sous les contraintes) :
4
x1 4
2 x2 12
3 x1 + 2 x2  18
2
x1  0, x2  0

-2 2 4 6 8 x1
-2

D1: x1 = 4 22
 RÉSOLUTION
Exemple :
Détermination du DR 3ème contrainte : 3 x1 + 2 x2  18
x2
6 D2: x2 = 6
(2,6)
Max Z(x)=3 x1 + 5 x2
s.c (Sous les contraintes) :
4
x1 4
2 x2 12
3 x1 + 2 x2  18
2
x1  0, x2  0

(6,0)
-2 2 4 6 8 x1
-2

D1: x1 = 4 23
 RÉSOLUTION
Exemple :
Détermination du DR Contraintes de signe
x2
6 D2: x2 = 6
Max Z(x)=3 x1 + 5 x2
s.c (Sous les contraintes) :
4
x1 4
2 x2 12
3 x1 + 2 x2  18
2
x1  0, x2  0

-2 2 4 6 8 x1
-2

D1: x1 = 4 24
 RÉSOLUTION
Exemple :
Détermination du DR
x2
6 D2: x2 = 6
Max Z(x)=3 x1 + 5 x2
s.c (Sous les contraintes) :
4
x1 4
2 x2 12 DR
3 x1 + 2 x2  18
2
x1  0, x2  0

-2 2 4 6 8 x1
-2

D1: x1 = 4 25
 RÉSOLUTION
Exemple :
Détermination des solutions optimales
x2
Droite d’isoprofit (Z(x)=cte)
6 D2: x2 = 6
Max Z(x)=3 x1 + 5 x2
s.c (Sous les contraintes) :
4
x1 4
2 x2 12 DR
3 x1 + 2 x2  18
2
x1  0, x2  0

-2 (0,0) 2 4 6 8 x1
-2

D1: x1 = 4 (5,-3) 26

Δ : Z(x)=3 x1 + 5 x2 = 0
 RÉSOLUTION
Exemple :
Détermination des solutions optimales
x2 X* = (2,6) Droite d’isoprofit (Z(x)=cte)
6 D2: x2 = 6
Max Z(x)=3 x1 + 5 x2
s.c (Sous les contraintes) :
4
x1 4 Max Z(x)
2 x2 12 DR
3 x1 + 2 x2  18
2
x1  0, x2  0

-2 (0,0) 2 4 6 8 x1
-2

D1: x1 = 4 (5,-3) 27

Δ : Z(x)=3 x1 + 5 x2 = 0
RÉSOLUTION
Cas particuliers

1er cas:

Min Z(x) = 3x1 + 2x2

S.C 3x1 + 2x2 ≤ 120
x1 + x2 ≤ 50
x1 ≥ 30
x2 ≥ 20
x1 ≥ 0, x2 ≥ 0

28
RÉSOLUTION
Cas particuliers

1er cas:

Min Z(x) = 3x1 + 2x2

S.C 3x1 + 2x2 ≤ 120
x1 + x2 ≤ 50
x1 ≥ 30 DR =Ø => PL non réalisable
x2 ≥ 20
x1 ≥ 0, x2 ≥ 0

29
RÉSOLUTION
Cas particuliers
x2

2ème cas:
15
PL non borné
Max Z(x) = x1 + 2x2
S.C 7x1 + 2x2 ≥ 28
10
x1 + 6x2 ≥ 12
x1 ≥ 0, x2 ≥ 0 DR
5

x1
4 8 12 14
D2 : x1 + 6 x2 = 12

30
D1 : 7 x1 + 2 x2 = 28
RÉSOLUTION
Cas particuliers
x2
3ème cas:
60
Max Z(x) = 3x1 + 2x2
S.C 3x1 + 2x2 ≤ 120
40
x1 + x2 ≤ 50
x1 ≥ 0, x2 ≥ 0
20
DR

-20 20 40 60 80 x1
Sol. Opt. = [A,B] -20 D2 : x1 + x2 = 50

A (20,30) et B (40,0)
D1 : 3 x1 + 2 x2 = 120 31
Δ : 3 x 1 + 2 x2 = 0
RÉSOLUTION
Différents cas possibles :
➢ DR =Ø => PL non réalisable
➢ DR ≠ Ø :
➢ PL non borné (∋ sol. réal. mais pas de solutions optimales),
➢ PL admettant une seule solution optimale,
➢ PL admettant une infinité de solutions optimales.

32