Université de

Nouakchott
Al Aasriya

Institut
Universitaire
Professionnel

Recherche Opérationnelle

1439 H
Enseignant-chercheurs :
Pr. Mohamed-Aly LOULY
Février 2018
Dr. Elkhomeini MOULAYE ELY
Dr. Mohamed SIDI
 2
LE COURS

 Volume d’enseignement : 52 heures

 Evaluation : Devoir + Projet + Examen

 Reference :
C. Prins et M. Sevaux. Programmation Linéaire avec
Excel. Editions Eyrolles, 2011.
 3
PLAN

1. Introduction a l’Optimisation Combinatoire

 Voyageur du Commerce
 Bin packing
2. La Programmation Linéaire
 Modélisation linéaire
 Programme Linéaire
 Résolution graphique
 Résolution algébrique
 Algorithme du Simplexe forme tableau
 Cas spéciaux pour l’algorithme du Simplexe
 Dualité
 Sensibilité
3. Le Solveur d’Excel
4. Modélisation linéaire des problèmes d’optimisation dans les graphes
5. Applications de la modélisation linéaire
 4 1. O PTIMISATION C OMBINATOIRE

C’est la recherche de la meilleure décision parmi un ensemble fini

d’alternative.

Bien que fini, cet ensemble est généralement de cardinal

exponentiel, ce qui rend impossible l’énumération complète.

Exemples :
1. Le problème du voyageur de commerce
2. Le problème de bin packing
 5 LE BIN PACKING

Ranger un ensemble de n objets en utilisant le nombre minimum

de conteneurs.
Même s’il n’y a que 2 conteneurs, on aura a travailler sur les
sous-ensembles d’objets, dont le nombre est 2n sous-ensembles!
 6 LE BIN PACKING

Exemples d’applications du bin packing :

1. Rangement d'objets dans des conteneurs

(camions, boîtes, palettes, etc.).
2. découpe de câbles et de matières premières.
3. Placement dans un entrepôt.
 7 LE BIN PACKING

Temps approximatif d’énumération des sous-ensembles avec une vitesse 1GHz

n 2n Secondes Jours Années Milliards

d’années

10 1024 10-6 10-11 3 x 10-14 3 x 10-23

30 109 1 10-5 3 x 10-8 3 x 10-17

50 1015 106 13 0,03 3 x 10-11

70 1021 1012 107 37436 3,7 x 10-5

90 1027 1018 1013 3,9 x 1010 39,3

L'âge de l’univers : 13,7 milliards d’années !!!

8 V OYAGEUR DE COMMERCE

Trouver la meilleure tournée ➔ n! alternatives

Attention, pour n > 3 : n! > 2n
 9 V OYAGEUR DE COMMERCE

Exemples d’applications du TSP et ses extensions :

1. Optimisation du transport des camions, bus,

bateaux et avions.
2. Ordonnancement des activités d’un poste de
travail.
3. Fabrication des cartes perforées. (Ordre de
fonctionnement de la perceuse)
 10 2. P ROGRAMMATION LINÉAIRE

La modélisation linéaire
Ciment 1 Ciment 2 Temps disponible
par jour

Profit par tonne 50 $ 70 $

Durée de calcination par 20 min 30 min 6h

tonne dans le four
Durée de broyage par 40 min 30 min 8h
tonne dans l’atelier

Planification de la production quotidienne de la cimenterie :

Combien produire de chaque ciment chaque jour ?
11 P ROGRAMME LINÉAIRE

x1 : quantité du ciment 1
x2 : quantité du ciment 2

Une fonction-objectif linéaire

Des contraintes linéaires

12 S OLUTIONS D ’ UN PL

(x1, x2) = (10, 10) : solution non réalisable de ce PL.

(x1, x2) = (1, 1) : solution réalisable, mais non optimale.
(x1, x2) = (6, 8) : solution optimale.
13 F ORME G ÉNÉRALE D ’ UN PL
14 F ORME CANONIQUE D ’ UN PL
15 C ANONIQUE VERS STANDARD

Ajout des variables d’écart

16 F ORME STANDARD D ’ UN PL
17 S TANDARD VERS CANONIQUE

Dédoublement des contraintes

18 I NTERPRÉTATION ÉCONOMIQUE

• Un acteur économique exerce n activités avec des

intensités xj a déterminer. Ces activités utilisent m
ressources.
• On connait la quantité aij de la ressource i nécessaire pour
exercer l’activité j avec l’intensité 1.
• On connait le profit ou le cout cj pour une intensité 1 de
l’activité j.
• On veut trouver les intensités des activités, compatibles
avec les ressources, pour maximiser le profit ou minimiser
le cout.
19 R ÉSOLUTION GRAPHIQUE

• Un polyèdre est l’ensemble des solutions d’un

système fini d’inégalités linéaires, c’est-à-dire :

où A est une matrice m x n

• Un polyèdre borné est appelé polytope.

• Un polyèdre P ainsi défini est convexe, c.-à-d. que chaque

fois qu'on y prend deux points A et B, le segment [A, B] qui
les joint y est entièrement contenu.
 20 R ÉSOLUTION GRAPHIQUE

Exemple de polyèdres bornés dans R3 : les 5 solides de Platon. Ce sont

des polyèdres convexes réguliers avec 4, 6, 8, 12 et 20 faces identiques.

Attention
Le nombre de sommets d’un polyèdre de Rn peut être exponentiel !
 21 R ÉSOLUTION GRAPHIQUE

Le polygone le plus simple : triangle (Simplexe a 2 dimensions)

A (0, 6)
Domaine des
solutions réalisables
Direction
du max
Si le PL admet une
solution optimale, alors
elle est atteinte sur un
B (6, 0)
sommet. O (0, 0)
 22 R ÉSOLUTION GRAPHIQUE

Le cas général à deux variables : un polygone convexe

A (0, 6)

Direction
C (3, 3) du max
D (0, 3)

B (6, 0)
O (0, 0)

Le cas général à n variables : un polyèdre convexe

 23 R ÉSOLUTION GRAPHIQUE

Le cas général à deux variables : un polygone convexe

A (0, 6)

Direction
C (3, 3) du max
D (0, 3)

B (6, 0)
O (0, 0)

Le cas général à n variables : un polyèdre convexe

 24 R ÉSOLUTION GRAPHIQUE

Cas spécial : un domaine non borné et pas de maximum

Direction
On peut indéfiniment augmenter du max
la fonction-objectif sans violer
les contraintes. Il n’y a donc pas
de solution optimale. En effet,
peut toujours augmenter x1.
 25 R ÉSOLUTION GRAPHIQUE

Cas spécial : existence d’un maximum sur un domaine non borné

Direction
du max
La direction de la maximisation
est bornée.
26 R ÉSOLUTION GRAPHIQUE

Cas spécial : le domaine des solutions réalisables est vide.

Il n’y a pas de solution qui satisfait toutes les contraintes.

27 R ÉSOLUTION GRAPHIQUE

Cas spécial : plusieurs solutions optimales

Solutions
(3, 3) optimales

(6, 0)

Il existe toujours un sommet optimal dans ce cas

28 R ÉSOLUTION GRAPHIQUE

L’exemple de la cimenterie

(6, 8)
29 R ÉSOLUTION GRAPHIQUE

Résoudre les PLs suivants avec la méthode graphique

PL 1 PL 2 PL 3
 30 R ÉSOLUTION A LGÉBRIQUE

• Pour résoudre des problèmes de programmation

linéaire ayant un nombre de variables supérieur à trois
nous devons obligatoirement faire appel à une autre
méthode de résolution que celle graphique.

• Vous découvrirez dans cette section la méthode

algébrique qui permettra d’étudier les différentes
étapes à franchir pour arriver à une solution optimale.
 31 R ÉSOLUTION A LGÉBRIQUE

• Cette résolution utilise la forme standard Ax = b

• La matrice A est une matrice de taille m x n avec
rang(A)=m ≤ n
• Rappel
• rang (A) = nombre maximal de lignes de A
linéairement indépendantes (nombre
maximal de colonnes linéairement
indépendantes)
 32 R ANG ET S OLUTION

Sous l’hypothèse de rang plein

• Le système Ax = b admet toujours des

solutions
• Si m < n, le système Ax = b admet une
infinité de solutions
• Si m = n, alors il n’ y a rien à maximiser car
la solution x est unique et vaut A‫־‬¹ b.
 33 R ANG ET S OLUTION

• Si rang(A) < m, on peut toujours éliminer les équations

redondantes et réécrire le problème sous la forme A’x=b’ avec A’
de rang plein inferieur a m. On peut donc toujours supposer A de
rang plein.
• On appelle solution réalisable de P tout vecteur x ≥ 0 qui satisfait
les contraintes Ax=b.
• Il y a au plus solutions réalisables. C’est le nombre des choix
possibles de m variables de base parmi les n possibles. Pour 400
variables et 100 contraintes cela est de l’ordre d’un google 10100.
C’est plus que le nombre des atomes de l’univers 1080.
 34 B ASE ET S OLUTIONS DE BASE

• On appelle base de A , ou matrice de base, toute sous

matrice carrée inversible B, m x m de A
• Les variables xB =(xj; i élément de B) sont appelées variables de
base.
• Les variables xN =(xj; j n’est pas un élément de B) sont appelées
variables hors-base
• Soit B une base de A
• On partitionne A sous la forme suivante : A = [B N]
• Pour simplifier la présentation, les m premières colonnes constituent
la base
• On partitionne de la même manière les vecteurs x et c
• X = (xB, ,xN ) T et c = (cB, ,cN )T
 35 B ASE ET S OLUTIONS DE BASE

• Supposons qu’on a:

• Comme:

• Et:

• Alors on note par :

•
• et
 36 B ASE ET S OLUTIONS DE BASE

• Le programme linéaire (P) s’écrit alors sous la forme

• C’est la forme standard par rapport à la base B

• On dit que est solution associée à la base B si

• Si est une solution de base réalisable alors

et
 37 S OLUTION O PTIMALE

• Théorème
• L’ensemble des points extrêmes du polytope,
correspond à l’ensemble des solutions de base
réalisables

• Théorème
• Si CN ≤ 0 alors la solution de base réalisable
correspondante est une solution optimale du
programme linéaire.
 38 E XEMPLE D ’ APPLICATION

• Considérons le programme linéaire (PL) ci-dessous :

• Déterminer toutes les solutions de base réalisables SBR

• Donner la solution de base optimale
 39 E XEMPLE D ’ APPLICATION

• La matrice A est définie par :

• Les bases réalisables sont
• La première base réalisable
B1
•

B2
•

• n’est pas une base car les colonnes ne sont pas linéairement
indépendantes (det = 0)
• La deuxième base réalisable
O (0, 0)
•

•
40 E XEMPLE D ’ APPLICATION

• La troisième base réalisable

•

• B4

• La quatrième base n’est pas réalisable

B3 B1
•

•
B5 B2
• La cinquième base réalisable

•
 41 E XEMPLE D ’ APPLICATION

• Vu que et donc, on a
pour (x =(0,0)) :
N

• La première base : et La base optimale

• La deuxième base : et

• La troisième base : et

• La cinquième base : et
 42 L A MÉTHODE DU S IMPLEXE

• Publié par Dantzig en 1949.

• Fonctionne sur la forme standard du PL.
• Un algorithme itératif qui améliore la fonction-objectif à
chaque itération en passant d’un sommet à un meilleur
sommet voisin.
• L’algorithme du simplexe est très efficace en pratique et son
temps de calcul empirique est linéaire avec un nombre
d’itérations généralement entre 2m et 3m.
• Il est cependant théoriquement exponentiel dans le pire
cas, alors que le PL est d’une complexité polynomial.
 43 LA MÉTHODE DU S IMPLEXE

A (0, 6, 0, -3)

C (3, 3, 0, 0)

D (0, 3, 3, 0)
B (6, 0, 0, 3)
O (0, 0, 6, 3)

• Chaque sommet est une solution basique SB qui contient au

moins (n-m) zéros, représentant les variables non-basiques.
• Une SB est réalisable (SBR) si toutes ses valeurs sont positives.
• La SB initiale la plus évidente est celle pour laquelle les variables
initiales sont nulles, mais cette SB n’est pas toujours une SBR.
 44 LA MÉTHODE DU S IMPLEXE

C (3, 3, 0, 0)

D (0, 3, 3, 0)

O (0, 0, 6, 3)
B (6, 0, 0, 3)

• On commence par la base évidente formée par les variables

d’écart x3 et x4.
• La fonction z et les variables de base sont réécrites en
fonctions des variables hors base x1 et x2.
• La SBR initiale est obtenue en mettant les variables hors base
a zéro : SBR0 = (0, 0, 6, 3) et z = 0.
 45 LA MÉTHODE DU S IMPLEXE

• Pour aller d’une SBR0 à une nouvelle SBR1, une

variable entre dans la base et une variable en sort.
• La variable entrante augmente sa valeur et la
variable sortante devient égale a zéro. Cette
opération de pivotage peut se voir comme un zéro
qui se déplace dans la solution.
• Géométriquement, on de déplace d’un sommet du
polyèdre vers un sommet adjacent.
 46 LA MÉTHODE DU S IMPLEXE

• La variable entrante est celle qui donne le profit unitaire

maximal dans l’expression de la fonction-objectif z, ici x2.
• La variable sortante est le première qui s’annule en
augmentant la valeur de la variable entrante, ici x4.
• La fonction z et les nouvelles variables de base x2 et x3 sont
alors réécrites en fonctions des variables hors base x1 et x4.

• La nouvelle SBR est obtenue en mettant les nouvelles

variables hors base a zéro : SBR1 = (0, 3, 3, 0) et z = 6.
 47 LA MÉTHODE DU S IMPLEXE

• A la nouvelle itération, la variable entrante est x1 car c’est la

seule qui a un profit unitaire strictement positif.
• La variable sortante est x3 qui s’annule quand x1 devient 3.

• La nouvelle SBR est : SBR2 = (3, 3, 0, 0) et z = 9.

• C’est la solution optimale car toutes la variables hors bases
ont un profit unitaire négatif.
 48 LE TABLEAU DU S IMPLEXE

Tableau correspondant a la SBR0

Base X1 X2 X3 X4 b

X3 1 1 1 0 6

Variable sortante X4 0 1 0 1 3

Profit C 1 2 0 0 Z=0

Variable
entrante
49 LE TABLEAU DU S IMPLEXE

Base X1 X2 X3 X4 b

X3 1 1 1 0 6

X4 0 1 0 1 3

Profit C 1 2 0 0 Z=0

Base X1 X2 X3 X4 b

X3 1 0 1 -1 3

X2 0 1 0 1 3

Profit C 1 0 0 -2 Z=6
50 LE TABLEAU DU S IMPLEXE

Base X1 X2 X3 X4 b

X3 1 0 1 -1 3

X2 0 1 0 1 3

Profit C 1 0 0 -2 Z=6

Base X1 X2 X3 X4 b

X1 1 0 1 -1 3

X2 0 1 0 1 3

Profit C 0 0 -1 -1 Z=9
51 R ÉSOLUTION GRAPHIQUE

Résoudre le PL de la cimenterie et les PLs suivants avec

l’algorithme du Simplexe sous forme de tableau.

PL 1 PL 2 PL 3
 52
S IMPLEXE DEUX PHASES

Solution initiale artificielle

▪ Une solution de base admissible n’est pas toujours connue a priori.

▪ Certains problèmes n’admettent pas de solution admissible, donc

il est impossible de trouver une base de départ.

▪ La méthode des deux phases va permettre de déterminer une

base admissible ou prouver que le problème est impossible.
 53
S IMPLEXE DEUX PHASES

Soit le PL suivant :

Introduction des variables d’écarts :

 54
S IMPLEXE DEUX PHASES

➢ Pas de base admissible "triviale".

➢ On voudrait voir apparaître une matrice identité.
➢ Introduction de variables artificielles.
Introduction des variables artificielles:

❖ R1, R2 et x4 peuvent être utilisées comme base de départ admissible.

❖ Base pour le système de départ si R1 = R2 = 0 (hors base).
❖ Réécrire l’objectif en fonction des variables hors base !
 55 S IMPLEXE DEUX PHASES

Problème d’origine après introduction des variables d’écart

 56 S IMPLEXE DEUX PHASES

Introduction des variables artificielles :

 57
S IMPLEXE DEUX PHASES
Exemple d’application :
Problème de Départ

Introduction des variables d’écarts

Base évidente X3 et X4 non réalisable !

 58
S IMPLEXE DEUX PHASES
Exemple d’application :
Problème avec variables artificielles

Une nouvelle base réalisable évidente : x4; x5

On utilise Simplexe et si x5 = 0 alors optimum du problème de
départ.
 59
S IMPLEXE DEUX PHASES
Exemple d’application :
Assurer que X5 =0 !
 60
S IMPLEXE DEUX PHASES
Exemple d’application :
Expression en fonction de variables hors bases

Résolution : faire entrer x2 et sortir x5

Variables en base : x2; x4
=) x5 = 0 (x1 = 0; x2 = 19/3 ; x3 = 0; x4 = 20/3 )
C’est une solution réalisable du problème d’origine
 61
S IMPLEXE DEUX PHASES
Exemple d’application :
Dernière itération du Simplexe

X5=0 Retour au Problème

d’origine.
 62
D UALITÉ

A tout programme linéaire appelé PRIMAL correspond un programme

linéaire appelé DUAL obtenu de la manière suivante:
PRIMAL DUAL
m contraintes d'infériorité n contraintes de supériorité
n variables d'activité n variables d'écart
m variables d'écart m variables d'activité
écriture en ligne écriture en colonne

Exemple
PRIMAL DUAL
3 x1 + 4 x2 ≤ 160 3 y1 + 6 y2 ≥ 1200
6 x1 + 3 x2 ≤ 180 4 y1 + 3 y2 ≥ 1000
Max z = 1200 x1 + 1000 x2 Min w = 160 y1 + 180 y2
x1 ≥ 0 ; x2 ≥ 0 y1 ≥ 0 ; y2 ≥ 0
 63
D UALITÉ

Exemple

Utilité : Un PL avec dix variables et deux contraintes ne peut pas être résolu
graphiquement, tendis que cela n’est pas de problème pour son dual à deux
variables et dix contraintes.
64 FABRICATION D ’ UN ACIER

Une entreprise reçoit une demande de 5 tonnes d’acier

avec les caractéristiques suivantes :

Elément Pourcentage Pourcentage

chimique minimal maximal

Carbone 2 3
Cuivre 0,4 0,6
Manganèse 1,2 1,65
65 FABRICATION D ’ UN ACIER

Matière première %C % Cu % Mn Stock Cout

(kg) (Euro/Kg)
Fer 1 2.5 0 1,3 4 000 1,20
Fer 2 3 0 0,8 3 000 1,50
Fer 3 0 0,3 0 6 000 0,90
Cuivre 1 0 90 0 5 000 1,30
Cuivre 2 0 96 4 2 000 1,45
Aluminium 1 0 0,4 1,2 3 000 1,20
Aluminium 2 0 0,6 0 2 500 1

Déterminer la composition de l’acier a fabriquer.

 66 FABRICATION D ’ UN ACIER

xi : la quantité utilisée de la matière première i

Fonction-objectif :

Satisfaction de la demande :
 67 FABRICATION D ’ UN ACIER

Pourcentage de carbone :

Pourcentage de cuivre :

Pourcentage de Manganèse :
 68 FABRICATION D ’ UN ACIER

Disponibilité des stocks :

Positivité des variables :

69
P RODUCTION D ’ ALIMENTS
POUR BÉTAIL

Une entreprise fabrique 2 aliments pour bétail (granulés et Farine) a partir

de 3 matières premières (avoine, maïs et mélasse). L’avoine et le maïs sont
broyés avant d’être mélangés avec la mélasse. Les granulés sont ensuite
obtenus par granulation et la farine est obtenu par tamisage.

Nutriment Avoine Maïs Mélasse Teneur

souhaitée
Protéines 13,6 4,1 5 ≥ 9,5
Lipides 7,1 2,4 0,3 ≥2
Glucides 7 3,7 25 ≤6
70
P RODUCTION D ’ ALIMENTS
POUR BÉTAIL

La demande est de 9 tonnes de granulées et 12 tonnes de farine.

Matières premières Avoine Maïs Mélasse

Quantité disponible en kg 11 900 23 500 750

Prix d’achat en euros/kg 0,8 1 0,75

Opération Broyage Mélange Granulation Tamisage

Coût en euros/kg 1,5 0,3 2,5 1

 71
P RODUCTION D ’ ALIMENTS
POUR BÉTAIL

Xi,j : la quantité de la matière première j utilisée pour fabriquer l’aliment i.

Fonction-objectif :

Satisfaction de la demande :
 72
P RODUCTION D ’ ALIMENTS
POUR BÉTAIL

Pourcentage de protéines :

Pourcentage de lipides :

Pourcentage de glucides :
 73
P RODUCTION D ’ ALIMENTS
POUR BÉTAIL

Disponibilité des stocks :

Positivité des variables :

74
P LANIFICATION DE
PRODUCTION DE BICYCLETTES

La capacité de production durant les heures normales est de

30 milles bicyclettes par mois. On peut produire plus durant
les heures supplémentaires, mais le cout de production d’une
bicyclette passe de 130 euros a 160 euros. Le stock initial est
de 2 milles bicyclettes. Le cout de stockage d’une bicyclette
est de 20 euros par mois. Les prévisions de ventes de l’année
prochaine sont :

Mois 1 2 3 4 5 6 7 8 9 10 11 12

Demande 30 15 15 25 33 40 45 45 26 14 25 30
 75
P LANIFICATION DE
PRODUCTION DE BICYCLETTES

xni : la quantité produite durant les heures normales du mois i.

xsi : la quantité produite durant les heures supplémentaires du mois i.
si : la quantité stockée a la fin du mois i.

Fonction-objectif :
 76
P LANIFICATION DE
PRODUCTION DE BICYCLETTES

Contraintes d’équilibre des stocks

 77
P LANIFICATION DE
PRODUCTION DE BICYCLETTES

Capacité de production :

Positivité des variables :

78
P LANIFICATION DE
PRODUCTION DES VERRES

Une entreprise produit 6 types de verres de table par lot de

1000. Les demandes en nombre de lots pour les 12 semaines
a venir est la suivante :
1 2 3 4 5 6 7 8 9 10 11 12

V1 20 22 18 35 17 19 23 20 29 30 28 32
V2 17 19 23 20 11 10 12 34 21 23 30 12
V3 18 35 17 10 9 21 23 15 10 0 13 17
V4 31 45 24 38 41 20 19 37 28 12 30 37
V5 23 20 23 16 10 22 18 30 28 7 15 10
V6 22 18 20 19 18 35 0 28 12 30 21 23
79
P LANIFICATION DE
PRODUCTION DES VERRES

Une entreprise produit 6 types de verres de table par lot de

1000. Les demandes en nombre de lots pour les 12 semaines
a venir est la suivante :
Cout de Cout de Stock Stock Temps Temps Casiers
production stockage initial final min travail machine stockage
V1 100 25 50 10 3 2 4
V2 80 28 20 10 3 1 5
V3 110 25 0 10 3 4 5
V4 90 27 15 10 2 8 6
V5 200 10 0 10 4 11 4
V6 140 20 10 10 4 9 9
 80
P LANIFICATION DE
PRODUCTION DES VERRES

Qi,j : la quantité du produit i fabriquée durant la période j.

Si,j : la quantité du produit i stockée a la fin de la période j.
Fonction-objectif :
 81
P LANIFICATION DE
PRODUCTION DES VERRES

Contraintes d’équilibre des stocks du produit i

82
P LANIFICATION DE
PRODUCTION DES VERRES

Capacité de production et de stockage durant la période j :