MOD 4.

4: Recherche opérationnelle

Nicolas Bousquet

Ecole Centrale de Lyon

1/32
 Recherche opérationnelle

Définition (wikipedia)
La Recherche Opérationnelle peut être définie comme l’ensemble des
méthodes et techniques rationnelles orientées vers la recherche du
meilleur choix dans la façon d’opérer en vue d’aboutir au résultat visé
ou au meilleur résultat possible.

Dans la vraie vie:

• Modélisation d’un problème sous forme mathématique.
• Développer des algorithmes de résolution efficace pour ce type de
problèmes (ou utiliser des méthodes existantes).
• Evaluer (empiriquement ou théoriquement) la qualité de la solution
comparée à la solution optimale.
• Evaluer la solution dans l’environnement réel.
Toutes les contraintes ont-elles été prises en compte?

2/32
 Recherche Opérationnelle (cont.)

Le but d’une solution d’un problème en Recher Opérationnelle est que la

solution trouvée soit à la fois:
• Efficace. Solution rapide au problème.
• Robuste. Si les données du problème change légèrement (ou que les
données obtenus sont bruitées), on doit pouvoir garantir que la
solution reste proche d’une solution optimale.
• Garantie théorique ou expérimentale. La solution obtenue doit être
la meilleure possible. Si possible optimale, sinon proche de l’être.

3/32
Exemples:
• Ordonnancement.
• Routage.
• Optimisation industrielle.
• Aide à la décision.
• Logistique

4/32
Exemples: Différentes approches:
• Ordonnancement. • Solutions exactes. (Algo.
• Routage. polynomiaux...)
• Optimisation industrielle. • Solutions approchées.
• Aide à la décision. • Heuristiques (local search,
• Logistique deep learning...).

4/32
Exemples: Différentes approches:
• Ordonnancement. • Solutions exactes. (Algo.
• Routage. polynomiaux...)
• Optimisation industrielle. • Solutions approchées.
• Aide à la décision. • Heuristiques (local search,
• Logistique deep learning...).

Différents types de contraintes:

• Discrètes.
• Continues.
• Mixtes.

4/32
 Organisation des deux prochains cours

• Partie 1 - Modélisation.
• Partie 2 - Programmation Linéaire.
• Partie 3 - Dualité et toutes ses conséquences.
• Partie 4 - Programmation Linéaire en nombre entiers.

5/32
 Modélisation

Définition
La modélisation consiste à représenter mathématiquement un problème
réel via des objectifs et des contraintes définis comme des problèmes
mathématiques.

6/32
 Modélisation

Définition
La modélisation consiste à représenter mathématiquement un problème
réel via des objectifs et des contraintes définis comme des problèmes
mathématiques.

Un procédé qui nécessite souvent plusieurs allers-retours:

• Problèmes mal posés.
• Quelles sont les “vraies” contraintes.
• Contraintes inconnues.

6/32
 Modélisation 1 - Ordonnancement

• Un ensemble de tâches X = {x1 , . . . , xn } qui peuvent être effectués

par une machine.
• Pour chaque tâche xi , il existe un intervalle (ai , bi ) durant lequel la
tâche doit être nécessairement être effectuée intégralement.
• Objectif: Maximiser le nombre de tâches effectuées complètement?

7/32
 Modélisation 1 - Ordonnancement

• Un ensemble de tâches X = {x1 , . . . , xn } qui peuvent être effectués

par une machine.
• Pour chaque tâche xi , il existe un intervalle (ai , bi ) durant lequel la
tâche doit être nécessairement être effectuée intégralement.
• Objectif: Maximiser le nombre de tâches effectuées complètement?
Kit clé en main pour la modélisation:
• Sur quoi on optimise? → Variables.

7/32
 Modélisation 1 - Ordonnancement

• Un ensemble de tâches X = {x1 , . . . , xn } qui peuvent être effectués

par une machine.
• Pour chaque tâche xi , il existe un intervalle (ai , bi ) durant lequel la
tâche doit être nécessairement être effectuée intégralement.
• Objectif: Maximiser le nombre de tâches effectuées complètement?
Kit clé en main pour la modélisation:
• Sur quoi on optimise? → Variables.

• Exprimer l’objectif en fonction des variables.

7/32
 Modélisation 1 - Ordonnancement

• Un ensemble de tâches X = {x1 , . . . , xn } qui peuvent être effectués

par une machine.
• Pour chaque tâche xi , il existe un intervalle (ai , bi ) durant lequel la
tâche doit être nécessairement être effectuée intégralement.
• Objectif: Maximiser le nombre de tâches effectuées complètement?
Kit clé en main pour la modélisation:
• Sur quoi on optimise? → Variables.

• Exprimer l’objectif en fonction des variables.

• Exprimer les contraintes en fonction des variables.

7/32
 Modélisation 1 - Ordonnancement

• Un ensemble de tâches X = {x1 , . . . , xn } qui peuvent être effectués

par une machine.
• Pour chaque tâche xi , il existe un intervalle (ai , bi ) durant lequel la
tâche doit être nécessairement être effectuée intégralement.
• Objectif: Maximiser le nombre de tâches effectuées complètement?
Kit clé en main pour la modélisation:
• Sur quoi on optimise? → Variables.
→ Ici on crée, une variable par tâche xi ∈ {0, 1}.
• Exprimer l’objectif en fonction des variables.

• Exprimer les contraintes en fonction des variables.

7/32
 Modélisation 1 - Ordonnancement

• Un ensemble de tâches X = {x1 , . . . , xn } qui peuvent être effectués

par une machine.
• Pour chaque tâche xi , il existe un intervalle (ai , bi ) durant lequel la
tâche doit être nécessairement être effectuée intégralement.
• Objectif: Maximiser le nombre de tâches effectuées complètement?
Kit clé en main pour la modélisation:
• Sur quoi on optimise? → Variables.
→ Ici on crée, une variable par tâche xi ∈ {0, 1}.
• Exprimer l’objectif en fonction des variables.
P
→ Maximize i≤n xi .
• Exprimer les contraintes en fonction des variables.

7/32
 Modélisation 1 - Ordonnancement

• Un ensemble de tâches X = {x1 , . . . , xn } qui peuvent être effectués

par une machine.
• Pour chaque tâche xi , il existe un intervalle (ai , bi ) durant lequel la
tâche doit être nécessairement être effectuée intégralement.
• Objectif: Maximiser le nombre de tâches effectuées complètement?
Kit clé en main pour la modélisation:
• Sur quoi on optimise? → Variables.
→ Ici on crée, une variable par tâche xi ∈ {0, 1}.
• Exprimer l’objectif en fonction des variables.
P
→ Maximize i≤n xi .
• Exprimer les contraintes en fonction des variables.
P
→ Quelque soit l’instant t, [ai ,bi ] contiennent t xi ≤ 1.

7/32
 Ordonnancement (cont.)

Bilan:
X
max xi
i≤n

soumis à: X
xi ≤ 1 ∀t
[ai ,bi ] contiennent t

xi ∈ {0, 1} ∀i ∈ X

8/32
Modélisation 2 - Problème de transport
• n entrepôts X = {x1 , . . . , xn } t.q. chaque entrepôt
xi a une quantité ci de ressource.
• m clients Y = {y1 , . . . , ym } t.q. chaque yj a un
besoin dj en la ressource.
• Pour chaque paire i, j, il y a un coût de transport
cij ∈ R de xi à yj par unité.
• Objectif: Satisfaire chaque client à un coût
minimum.

9/32
 Modélisation 2 - Problème de transport
• n entrepôts X = {x1 , . . . , xn } t.q. chaque entrepôt
xi a une quantité ci de ressource.
• m clients Y = {y1 , . . . , ym } t.q. chaque yj a un
besoin dj en la ressource.
• Pour chaque paire i, j, il y a un coût de transport
cij ∈ R de xi à yj par unité.
• Objectif: Satisfaire chaque client à un coût
minimum.
Variables: Quantité zij de ressources qui vont de l’entrepôt xi au client
yi .
Contraintes: X
zij ≤ ci ∀i
j≤m
X
zij = dj ∀j
i≤n
P
Objectif: min i,j cij zij .
9/32
 Bilan

Bilan:
X
min cij zij
i,j

soumis à: X
zij ≤ ci ∀i
j≤m
X
zij = dj ∀j
i≤n

zij ∈ N ∀i, j

10/32
 Modélisation 3 - Clustering
Un entreprise souhaite ouvrir k entrepôts Y pour
servir ses n clients X = { x1 , . . . , xn } situés sur les
points yi = (ai , bi ) du plan.
Le but est de minimiser la distance L2 entre chaque
client et son entrepôt le plus proche.

11/32
 Modélisation 3 - Clustering
Un entreprise souhaite ouvrir k entrepôts Y pour
servir ses n clients X = { x1 , . . . , xn } situés sur les
points yi = (ai , bi ) du plan.
Le but est de minimiser la distance L2 entre chaque
client et son entrepôt le plus proche.

Variables: xj , yj pour j ≤ k.
Pn
Objectif: min i=1 minj≤k d2 (xi , yj )

Contraintes: Aucune
11/32
Modélisation 4 - Emploi du temps
• Un ensemble de cours C et une fonction de
contrainte f qui dit si deux cours peuvent être
données simultanement.
• Un ensemble de k créneaux de cours.
• Trouver une assignation des cours aux différents
créneaux qui satisfait toutes les contraintes.

12/32
 Modélisation 4 - Emploi du temps
• Un ensemble de cours C et une fonction de
contrainte f qui dit si deux cours peuvent être
données simultanement.
• Un ensemble de k créneaux de cours.
• Trouver une assignation des cours aux différents
créneaux qui satisfait toutes les contraintes.
Modélisation via un graphe de conflit:
• Sommets: Cours.
• Arêtes entre deux cours si les deux cours sont incompatibles.
• Objectif: Colorer le graphe avec k couleurs en évitant les arêtes
monochromatiques.

12/32
 Modélisation 4 - Emploi du temps
• Un ensemble de cours C et une fonction de
contrainte f qui dit si deux cours peuvent être
données simultanement.
• Un ensemble de k créneaux de cours.
• Trouver une assignation des cours aux différents
créneaux qui satisfait toutes les contraintes.
Modélisation via un graphe de conflit:
• Sommets: Cours.
• Arêtes entre deux cours si les deux cours sont incompatibles.
• Objectif: Colorer le graphe avec k couleurs en évitant les arêtes
monochromatiques.

Exercice (difficile): Modéliser ce problème avec variables et contraintes 12/32

 Programmation Linéaire (PL)
Définition (programme linéaire)
Minimisation/ maximisation d’une fonction linéaire sous des con-
traintes elles-même linéaires.

13/32
 Programmation Linéaire (PL)
Définition (programme linéaire)
Minimisation/ maximisation d’une fonction linéaire sous des con-
traintes elles-même linéaires.

Classiquement:
n = nombre de variables.
x1 , . . . , xn = ensemble des variables.
m = nombre de contraintes.

13/32
 Programmation Linéaire (PL)
Définition (programme linéaire)
Minimisation/ maximisation d’une fonction linéaire sous des con-
traintes elles-même linéaires.

Classiquement:
n = nombre de variables.
x1 , . . . , xn = ensemble des variables.
m = nombre de contraintes.
n
Exemple: X
ai xi ≤ b
i=1

13/32
 Programmation Linéaire (PL)
Définition (programme linéaire)
Minimisation/ maximisation d’une fonction linéaire sous des con-
traintes elles-même linéaires.

Classiquement:
n = nombre de variables.
x1 , . . . , xn = ensemble des variables.
m = nombre de contraintes.
n
Exemple: X
ai xi ≤ b
n i=1 n
X X
ai xi ≥ b ⇔ −ai xi ≤ −b
i=1 i=1

13/32
 Programmation Linéaire (PL)
Définition (programme linéaire)
Minimisation/ maximisation d’une fonction linéaire sous des con-
traintes elles-même linéaires.

Classiquement:
n = nombre de variables.
x1 , . . . , xn = ensemble des variables.
m = nombre de contraintes.
n
Exemple: X
ai xi ≤ b
n i=1 n
X X
ai xi ≥ b ⇔ −ai xi ≤ −b
n i=1 n i=1 n
X X X 
ai xi = bi ⇔ ( ai xi ≤ b) AND ai xi ≥ b
i=1 i=1 i=1

13/32
 Programmation Linéaire (PL)
Définition (programme linéaire)
Minimisation/ maximisation d’une fonction linéaire sous des con-
traintes elles-même linéaires.

Classiquement:
n = nombre de variables.
x1 , . . . , xn = ensemble des variables.
m = nombre de contraintes.
n
Exemple: X
ai xi ≤ b
n i=1 n
X X
ai xi ≥ b ⇔ −ai xi ≤ −b
n i=1 n i=1 n
X X X 
ai xi = bi ⇔ ( ai xi ≤ b) AND ai xi ≥ b
i=1 i=1 i=1
xi ≥ 0

13/32
 Programmation Linéaire (PL)
Définition (programme linéaire)
Minimisation/ maximisation d’une fonction linéaire sous des con-
traintes elles-même linéaires.

Classiquement:
n = nombre de variables.
x1 , . . . , xn = ensemble des variables.
m = nombre de contraintes.
n
Exemple: X
ai xi ≤ b
n i=1 n
X X
ai xi ≥ b ⇔ −ai xi ≤ −b
n i=1 n i=1 n
X X X 
ai xi = bi ⇔ ( ai xi ≤ b) AND ai xi ≥ b
i=1 i=1 i=1
xi ≥ 0

Questions: Quels exemples sont exprimés comme des PL?

13/32
 Forme normale d’un PL
X
max c i xi
n
X
soumis à ∀j, ai xi ≤ bj
i=1
∀i, xi ≥ 0

14/32
 Forme normale d’un PL
X
max c i xi
n
X
soumis à ∀j, ai xi ≤ bj
i=1
∀i, xi ≥ 0
A = Matrice des ai,j .
c = vecteur des ci .
b = vecteur des bi .
Un programme linéaire est sous forme normale s’il s’écrit:

max c t x
soumis à Ax ≤ b
x ≥0

La contrainte x ≥ 0 s’appelle contrainte de positivité.

14/32
 Exemple

Une usine fabrique des chaises et des tables. Chaque semaine l’usine
commande la même quantité de bois, connaı̂t le temps de travail de ses
employés et la durée de fonctionnement de ses machines.
Sachant qu’une table rapporte 6 euros et une chaise 4, quel est le mix
chaises-tables qui maximise le revenu de l’usine?

15/32
 Exemple

Une usine fabrique des chaises et des tables. Chaque semaine l’usine
commande la même quantité de bois, connaı̂t le temps de travail de ses
employés et la durée de fonctionnement de ses machines.
Sachant qu’une table rapporte 6 euros et une chaise 4, quel est le mix
chaises-tables qui maximise le revenu de l’usine?
Table Chaise Quantité disponible
Equipement 3 9 81
Main d’oeuvre 4 5 55
Bois 2 1 20

15/32
 Mise en équation
Table Chaise Quantité disponible
Equipement 3 9 81
Main d’oeuvre 4 5 55
Bois 2 1 20

16/32
 Mise en équation
Table Chaise Quantité disponible
Equipement 3 9 81
Main d’oeuvre 4 5 55
Bois 2 1 20

• Création de deux variables: xt et xc .

16/32
 Mise en équation
Table Chaise Quantité disponible
Equipement 3 9 81
Main d’oeuvre 4 5 55
Bois 2 1 20

• Création de deux variables: xt et xc .

• Création de trois contraintes: équipement, main d’oeuvre, bois:

3xt + 9xc ≤ 81
4xt + 5xc ≤ 55
2xt + xc ≤ 20
xt , xc ≥ 0

16/32
 Mise en équation
Table Chaise Quantité disponible
Equipement 3 9 81
Main d’oeuvre 4 5 55
Bois 2 1 20

• Création de deux variables: xt et xc .

• Création de trois contraintes: équipement, main d’oeuvre, bois:

3xt + 9xc ≤ 81
4xt + 5xc ≤ 55
2xt + xc ≤ 20
xt , xc ≥ 0

• Création de la fonction objectif.

z = max(6xt + 4xc )

16/32
 Résolution du système
Quand on résout le système, on obtient la solution optimale suivante:

(xt , xc ) = (15/2, 5).

Cette solution peut être obtenue de plusieurs façons:

• En dimension 2: graphiquement.

xc Bois

5
Equipement
Main d’oeuvre
15/2 xt

17/32
 Résolution du système
Quand on résout le système, on obtient la solution optimale suivante:

(xt , xc ) = (15/2, 5).

Cette solution peut être obtenue de plusieurs façons:

• En dimension 2: graphiquement.
• En toute dimension: comment faire?
xc Bois

5
Equipement
Main d’oeuvre
15/2 xt

17/32
 Points extrêmes et recherche de solution
optimale
xc Bois

5
Equipement
Main d’oeuvre
15/2 xt

P
Une contrainteP ai xi ≤ b définit un demi-espace. P
La contrainte ai xi ≤ b est serrée pour un point z si ai zi = b.

18/32
 Points extrêmes et recherche de solution
optimale
xc Bois

5
Equipement
Main d’oeuvre
15/2 xt

P
Une contrainteP ai xi ≤ b définit un demi-espace. P
La contrainte ai xi ≤ b est serrée pour un point z si ai zi = b.
Un point extrême z est un point tel que:
• z soit une solution,
• z est l’unique point à l’intersection d’un ensemble C de contraintes
serrées.

18/32
 A quoi ressemble une solution optimale?

Remarque:
L’ensemble des solutions est une intersection de demi-espaces fermés.
En particulier c’est un espace convexe et fermé.

19/32
 A quoi ressemble une solution optimale?

Remarque:
L’ensemble des solutions est une intersection de demi-espaces fermés.
En particulier c’est un espace convexe et fermé.
Théorème 1:
On optimise une fonction linéaire (donc convexe et concave) dans un
convexe
⇒ Un maximum (resp. minimum) local est un maximum (resp.
minimum) global.

19/32
 A quoi ressemble une solution optimale?

Remarque:
L’ensemble des solutions est une intersection de demi-espaces fermés.
En particulier c’est un espace convexe et fermé.
Théorème 1:
On optimise une fonction linéaire (donc convexe et concave) dans un
convexe
⇒ Un maximum (resp. minimum) local est un maximum (resp.
minimum) global.
Théorème 2:
Si la valeur optimale est finie alors il existe un point extrême qui atteint
le maximum.

19/32
 A quoi ressemble une solution optimale?

Remarque:
L’ensemble des solutions est une intersection de demi-espaces fermés.
En particulier c’est un espace convexe et fermé.
Théorème 1:
On optimise une fonction linéaire (donc convexe et concave) dans un
convexe
⇒ Un maximum (resp. minimum) local est un maximum (resp.
minimum) global.
Théorème 2:
Si la valeur optimale est finie alors il existe un point extrême qui atteint
le maximum.
Principe de l’algorithme du simplexe: Se promener de points extrêmes
en points extrêmes.

19/32
 Etape 1: Mettre le PL sous forme standard
Forme standard:
max c t x
soumis à Ax = b
x ≥0

20/32
 Etape 1: Mettre le PL sous forme standard
Forme standard:
max c t x
soumis à Ax = b
x ≥0

Idée: rajouter des variables d’écart.

n
X
ai xi ≤ b
i=1

Créer une variable y et poser:

n
X
y =b− ai xi
i=1
Pn
Notez que y ≥ 0 et i=1 ai xi + y = b.
Remarque: La forme générale des solutions ne change pas. La projection
d’une solution est toujours une solution.
20/32
 Sur notre exemple
• On a les inégalités.

3xt + 9xc ≤ 81
4xt + 5xc ≤ 55
2xt + xc ≤ 20
xt , xc ≥ 0

21/32
 Sur notre exemple
• On a les inégalités.

3xt + 9xc ≤ 81
4xt + 5xc ≤ 55
2xt + xc ≤ 20
xt , xc ≥ 0

• On rajoute les variables d’écart pour créer des égalités.

z = max 6xt + 4xc
sous les contraintes
 
3xt + 9xc + y1 = 81     xt
81 3 9 1 0 0  x
 c

4xt + 5xc + y2 = 55
⇔ 55 = 4 5 0 1 0  y1 
 
2xt + xc + y3 = 20

20 2 1 0 0 1  y2 
xt , xc , y1 , y2 , y3 ≥ 0 y3

21/32
 Etape 2: Transformer la solution courante
• On cherche une solution réalisable pour commencer:
 
  xt  
3 9 1 0 0  xc 
 81
⇔  4 5 0 1 0   y 1
 = 55
2 1 0 0 1  y2  20
y3

Autrement dit “Quand xt et xc valent 0 alors

(y1 , y2 , y3 ) = (81, 55, 20) est une solution”.

22/32
 Etape 2: Transformer la solution courante
• On cherche une solution réalisable pour commencer:
 
  xt  
3 9 1 0 0  xc 
 81
⇔  4 5 0 1 0   y 1
 = 55
2 1 0 0 1  y2  20
y3

Autrement dit “Quand xt et xc valent 0 alors

(y1 , y2 , y3 ) = (81, 55, 20) est une solution”.
• Notre solution est-elle améliorable?

max 6xt + 4xc

Pour l’instant xt et xc valent 0... Donc si on les rend positif, ça

améliorera la valeur de la solution !

22/32
 Etape 2: Transformer la solution courante
• On cherche une solution réalisable pour commencer:
 
  xt  
3 9 1 0 0  xc 
 81
⇔  4 5 0 1 0   y 1
 = 55
2 1 0 0 1  y2  20
y3

Autrement dit “Quand xt et xc valent 0 alors

(y1 , y2 , y3 ) = (81, 55, 20) est une solution”.
• Notre solution est-elle améliorable?

max 6xt + 4xc

Pour l’instant xt et xc valent 0... Donc si on les rend positif, ça

améliorera la valeur de la solution !
• On choisit une variable avec un coefficient positif dans l’objectif et
on l’augmente “autant qu’on peut” (en maintenant les contraintes).
→ Choisissons arbitrairement xt .
22/32
   Test d’entrée
  xt  
3 9 1 0 0  x
 c
 81
4 5 0 1 0  y 1
 = 55
 
2 1 0 0 1  y2  20
y3
• Si xt est modifié (et xc reste égal à 0) alors on doit toujours avoir:
3xt + y1 = 81
4xt + y2 = 55
2xt + y3 = 20

23/32
   Test d’entrée
  xt  
3 9 1 0 0  x
 c
 81
4 5 0 1 0  y 1
 = 55
 
2 1 0 0 1  y2  20
y3
• Si xt est modifié (et xc reste égal à 0) alors on doit toujours avoir:
3xt + y1 = 81
4xt + y2 = 55
2xt + y3 = 20
• Comme on doit toujours avoir y1 , y2 , y3 positifs ou nuls on a:
xt ≤ 17 contrainte 1
55
xt ≤ contrainte 2
4
xt ≤ 10 contrainte 3

23/32
   Test d’entrée
  xt  
3 9 1 0 0  x
 c
 81
4 5 0 1 0  y 1
 = 55
 
2 1 0 0 1  y2  20
y3
• Si xt est modifié (et xc reste égal à 0) alors on doit toujours avoir:
3xt + y1 = 81
4xt + y2 = 55
2xt + y3 = 20
• Comme on doit toujours avoir y1 , y2 , y3 positifs ou nuls on a:
xt ≤ 17 contrainte 1
55
xt ≤ contrainte 2
4
xt ≤ 10 contrainte 3

• Plus on augmente xt mieux c’est (pour l’objectif) →, on augmente

xt jusqu’à 10. A ce moment là, y3 devient égal à 0.
On dit alors que y3 sort de la base et que xt y rentre. 23/32
 Variables basiques et hors base
 
  xt  
3 9 1 0 0  x
 c
 81
4 5 0 1 0  y 1
 = 55
 
2 1 0 0 1  y2  20
y3
• On remarque la matrice restreinte aux yi était l’identité.
On supposera dorénavant que la matrice restreinte aux variables
dans la base (ici les yi ) est l’identité.
Les variables dans la base sont les seules qui pourront être non
nulles dans la solution courante (ici (0, 0, 81, 55, 20)).

24/32
 Variables basiques et hors base
 
  xt  
3 9 1 0 0  x
 c
 81
4 5 0 1 0  y 1
 = 55
 
2 1 0 0 1  y2  20
y3
• On remarque la matrice restreinte aux yi était l’identité.
On supposera dorénavant que la matrice restreinte aux variables
dans la base (ici les yi ) est l’identité.
Les variables dans la base sont les seules qui pourront être non
nulles dans la solution courante (ici (0, 0, 81, 55, 20)).
• Maintenant on ajouter xt dans la base et en supprimer y3 .
→ Elimination de Jordan Gauss pour que la matrice restreinte aux
colomnes de xt , y1 , y2 soit l’identité.

24/32
 Variables basiques et hors base
 
  xt  
3 9 1 0 0  x
 c
 81
4 5 0 1 0  y 1
 = 55
 
2 1 0 0 1  y2  20
y3
• On remarque la matrice restreinte aux yi était l’identité.
On supposera dorénavant que la matrice restreinte aux variables
dans la base (ici les yi ) est l’identité.
Les variables dans la base sont les seules qui pourront être non
nulles dans la solution courante (ici (0, 0, 81, 55, 20)).
• Maintenant on ajouter xt dans la base et en supprimer y3 .
→ Elimination de Jordan Gauss pour que la matrice restreinte aux
colomnes de xt , y1 , y2 soit l’identité.
 
xt
0 15 3
   
2 1 0 − 2
xc 
  51
0 3 0 1 −2  y1  = 15
 
1 21 0 0 1
2
 y2  10
y3 24/32
 Variables basiques et hors base
 
  xt  
3 9 1 0 0  x
 c
 81
4 5 0 1 0  y 1
 = 55
 
2 1 0 0 1  y2  20
y3
• On remarque la matrice restreinte aux yi était l’identité.
On supposera dorénavant que la matrice restreinte aux variables
dans la base (ici les yi ) est l’identité.
Les variables dans la base sont les seules qui pourront être non
nulles dans la solution courante (ici (0, 0, 81, 55, 20)).
• Maintenant on ajouter xt dans la base et en supprimer y3 .
→ Elimination de Jordan Gauss pour que la matrice restreinte aux
colomnes de xt , y1 , y2 soit l’identité.
 
xt
0 15 3
   
2 1 0 − 2
xc 
  51
0 3 0 1 −2  y1  = 15
 
1 21 0 0 1
2
 y2  10
y3 24/32
 Nouvelle solution et objectifs
 
xt
15 3
   
0 2 1 0 −2  x
 c
 51
0 3 0 1 −2   y
  1
 = 15
1 1  y2 
1 2 0 0 2
10
y3

• Nouvelle solution courante: (10, 0, 51, 15, 0).

• On re-exprime la fonction objectif en fonction des variables hors
base: 6xt + 4xc = (60 − 3xc − 3y3 ) + 4xc = 60 + xc − 3y3 .

25/32
 Nouvelle solution et objectifs
 
xt
15 3
   
0 2 1 0 −2  x
 c
 51
0 3 0 1 −2   y
  1
 = 15
1 1  y2 
1 2 0 0 2
10
y3

• Nouvelle solution courante: (10, 0, 51, 15, 0).

• On re-exprime la fonction objectif en fonction des variables hors
base: 6xt + 4xc = (60 − 3xc − 3y3 ) + 4xc = 60 + xc − 3y3 .
Remarques:
• On a simplement ré-écrit la matrice de contraintes !
⇒ Les solutions du système sont toujours les mêmes. (Autrement
dit, si vous pluggez (0, 0, 81, 55, 20) dans ce système, ça vous
donnera toujours une solution et sa valeur sera toujours 0).

• Similairement on a simplement ré-écrit la fonction objectif !

25/32
 Nouvelle solution et objectifs
 
xt
15 3
   
0 2 1 0 −2  x
 c
 51
0 3 0 1 −2   y
  1
 = 15
1 1  y2 
1 2 0 0 2
10
y3

• Nouvelle solution courante: (10, 0, 51, 15, 0).

• On re-exprime la fonction objectif en fonction des variables hors
base: 6xt + 4xc = (60 − 3xc − 3y3 ) + 4xc = 60 + xc − 3y3 .
Remarques:
• On a simplement ré-écrit la matrice de contraintes !
⇒ Les solutions du système sont toujours les mêmes. (Autrement
dit, si vous pluggez (0, 0, 81, 55, 20) dans ce système, ça vous
donnera toujours une solution et sa valeur sera toujours 0).
• Mais à chaque matrice on associe une solution appelée basic feasible
solution qui correspond à “variables de la base” potentiellement non
nulle et les autres sont nulles.
• Similairement on a simplement ré-écrit la fonction objectif !
25/32
 Nouvelle solution et objectifs

max 60 + xc − 3y3
soumis à  
xt
15 3
   
0 2 1 0 −2  x
 c
 51
0 3 0 1 −2   y
  1
 = 15
1 1  y2 
1 2 0 0 2
10
y3
Exercice:
1 Qui peut rentrer dans la base?
2 Qui doit en sortir?
3 Calculer la nouvelle matrice de contrainte et la nouvelle fonction
objectif.

26/32
 Solution optimale !
1 7
z = 65 − y2 − y3
3 3
sous les contraintes:
 
  xt  
0 0 1 −5/2 7/2  x
 c
 27/2
0 1 0 1/3 −2/3 
 y1  =
  5 
1 0 0 −1/6 5/6  y2  15/2
y3
Pour répondre à vos questions:

27/32
 Solution optimale !
1 7
z = 65 − y2 − y3
3 3
sous les contraintes:
 
  xt  
0 0 1 −5/2 7/2  x
 c
 27/2
0 1 0 1/3 −2/3 
 y1  =
  5 
1 0 0 −1/6 5/6  y2  15/2
y3
Pour répondre à vos questions:
• Quelle est la solution? Il s’agit du point (15/2, 5, 25/2, 0, 0).

27/32
 Solution optimale !
1 7
z = 65 − y2 − y3
3 3
sous les contraintes:
 
  xt  
0 0 1 −5/2 7/2  x
 c
 27/2
0 1 0 1/3 −2/3 
 y1  =
  5 
1 0 0 −1/6 5/6  y2  15/2
y3
Pour répondre à vos questions:
• Quelle est la solution? Il s’agit du point (15/2, 5, 25/2, 0, 0).
• Quelle est sa valeur? 65.

27/32
 Solution optimale !
1 7
z = 65 − y2 − y3
3 3
sous les contraintes:
 
  xt  
0 0 1 −5/2 7/2  x
 c
 27/2
0 1 0 1/3 −2/3 
 y1  =
  5 
1 0 0 −1/6 5/6  y2  15/2
y3
Pour répondre à vos questions:
• Quelle est la solution? Il s’agit du point (15/2, 5, 25/2, 0, 0).
• Quelle est sa valeur? 65.
• Pourquoi la solution est optimale? Le mieux que l’on puisse faire
c’est d’avoir y2 et y3 équaux à 0... Et c’est justement le cas dans la
solution courante !

27/32
 Solution optimale !
1 7
z = 65 − y2 − y3
3 3
sous les contraintes:
 
  xt  
0 0 1 −5/2 7/2  x
 c
 27/2
0 1 0 1/3 −2/3 
 y1  =
  5 
1 0 0 −1/6 5/6  y2  15/2
y3
Pour répondre à vos questions:
• Quelle est la solution? Il s’agit du point (15/2, 5, 25/2, 0, 0).
• Quelle est sa valeur? 65.
• Pourquoi la solution est optimale? Le mieux que l’on puisse faire
c’est d’avoir y2 et y3 équaux à 0... Et c’est justement le cas dans la
solution courante !
• Mais pourquoi ça termine? Et pourquoi ça marcherait à chaque
fois? Et comment interpréter ce qu’on vient de faire? Et comment
on fait pour commencer?
27/32
 Interprétation géométrique
xc Bois

5
Equipement
Main d’oeuvre
15/2 xt

Au départ:
max 6xt + 4xc
soumis à  
  xt  
3 9 1 0 0  x
 c
 81
4 5 0 1 0  y 1
 = 55
 
2 1 0 0 1  y2  20
y3

28/32
 Interprétation géométrique
xc Bois

5
Equipement
Main d’oeuvre
15/2 xt

A l’étape intermédiaire:
max 60 + xc − 3y3
soumis à  
xt
15 3
   
0 2 1 0 −2  x
 c
 51
0 3 0 1 −2   y
 1
 =  15
1 1  y2 
1 2 0 0 2
10
y3

28/32
 Interprétation géométrique
xc Bois

5
Equipement
Main d’oeuvre
15/2 xt

A la fin:
1 7
z = 65 − y2 − y3
3 3
soumis à:
 
 xt  
0 0 1 −5/2 7/2  x
 c
 27/2
0 1 0 1/3 −2/3 
 y1  =
  5 
1 0 0 −1/6 5/6 y2  15/2
y3

28/32
 Interprétation géométrique
xc Bois

5
Equipement
Main d’oeuvre
15/2 xt

A la fin:
1 7
z = 65 − y2 − y3
3 3
soumis à:
 
 xt  
0 0 1 −5/2 7/2  x
 c
 27/2
0 1 0 1/3 −2/3 
 y1  =
  5 
1 0 0 −1/6 5/6 y2  15/2
y3
Théorème: Le Simplexe consiste à se “promener” de points extrêmes en
points extrêmes en améliorant localement la solution ! 28/32
 Et pourquoi ça termine?

Remarque: L’algorithme du simplexe est en fait une classe d’algorithme

qui dépend de la règle de pivot choisie (choix de la variable qui rentre et
qui sort).

29/32
 Et pourquoi ça termine?

Remarque: L’algorithme du simplexe est en fait une classe d’algorithme

qui dépend de la règle de pivot choisie (choix de la variable qui rentre et
qui sort).
Théorème 1: Si il n’existe pas (n + 1) droites qui s’intersectent en un
même point (système non dégénéré), alors on améliore strictement la
solution à chaque étape et l’algorithme termine.

29/32
 Et pourquoi ça termine?

Remarque: L’algorithme du simplexe est en fait une classe d’algorithme

qui dépend de la règle de pivot choisie (choix de la variable qui rentre et
qui sort).
Théorème 1: Si il n’existe pas (n + 1) droites qui s’intersectent en un
même point (système non dégénéré), alors on améliore strictement la
solution à chaque étape et l’algorithme termine.
Dans les autre cas ce n’est pas clair... Ca dépend de quelle variable on
choisit pour rentrer et sortir...
Algorithme du Simplexe proposé en 1947 par Dantzig.
Première règle de terminaison: Bland en 1977 !

29/32
 Et pourquoi ça termine?

Remarque: L’algorithme du simplexe est en fait une classe d’algorithme

qui dépend de la règle de pivot choisie (choix de la variable qui rentre et
qui sort).
Théorème 1: Si il n’existe pas (n + 1) droites qui s’intersectent en un
même point (système non dégénéré), alors on améliore strictement la
solution à chaque étape et l’algorithme termine.
Dans les autre cas ce n’est pas clair... Ca dépend de quelle variable on
choisit pour rentrer et sortir...
Algorithme du Simplexe proposé en 1947 par Dantzig.
Première règle de terminaison: Bland en 1977 !
Théorème 2: (Bland) Il existe une règle (déterministe) qui garantit que
le Simplexe termine en temps fini.

29/32
 Complexité

Problème ouvert: Existe-t-il une règle (déterministe) qui garantit que le

Simplexe termine en temps polynomial?

30/32
 Complexité

Problème ouvert: Existe-t-il une règle (déterministe) qui garantit que le

Simplexe termine en temps polynomial?
Conjecture (Hirsch): Il existe toujours une suite d’étapes de longueur
n + m pour aller de n’importe quel point extrême à la solution
[Link] réfutée... Mais toujours ouvert pour n + m + 1.

30/32
 Complexité

Problème ouvert: Existe-t-il une règle (déterministe) qui garantit que le

Simplexe termine en temps polynomial?
Conjecture (Hirsch): Il existe toujours une suite d’étapes de longueur
n + m pour aller de n’importe quel point extrême à la solution
[Link] réfutée... Mais toujours ouvert pour n + m + 1.
Mais il y a quand même deux bonnes nouvelles:
• En pratique, l’algorithme du Simplexe fonctionne bien (3/2(n + m)
itérations en moyenne).

30/32
 Complexité

Problème ouvert: Existe-t-il une règle (déterministe) qui garantit que le

Simplexe termine en temps polynomial?
Conjecture (Hirsch): Il existe toujours une suite d’étapes de longueur
n + m pour aller de n’importe quel point extrême à la solution
[Link] réfutée... Mais toujours ouvert pour n + m + 1.
Mais il y a quand même deux bonnes nouvelles:
• En pratique, l’algorithme du Simplexe fonctionne bien (3/2(n + m)
itérations en moyenne).
• En théorie. L’algorithme dit “de l’ellipsoı̈de” peut résoudre tous les
programmes linéaires en temps polynomial dans le pire des cas?
Mais il est difficile à comprendre, à implémenter et (beaucoup)
moins efficace en pratique.

30/32
 Petite remarque d’importance

Notons que la solution optimale n’est pas entière. Et fabriquer 7.5 tables
n’a pas de sens.
Pour “résoudre” le problème il suffit d’arrondir la solution optimale à
l’entier inférieur, ce qui ne modifie (en général) pas sensiblement la
valeur obtenue (surtout quand elle la production est de plusieurs
centaines / milliers).

31/32
 Petite remarque d’importance

Notons que la solution optimale n’est pas entière. Et fabriquer 7.5 tables
n’a pas de sens.
Pour “résoudre” le problème il suffit d’arrondir la solution optimale à
l’entier inférieur, ce qui ne modifie (en général) pas sensiblement la
valeur obtenue (surtout quand elle la production est de plusieurs
centaines / milliers).
Faire un tel arrondi peut néanmoins se révéler
problématique si:
• L’industriel veut réellement une solution
optimale (c’est rare).
• Les entiers sont “petits” et arrondir modifie
sensiblement la valeur de la solution optimale
(ça peut arriver).

31/32
 Programme Linéaire en nombre entiers
(PLNE)

On peut modéliser de nombreux problèmes avec des PL ayant comme

variables {0, 1}. Par exemple:
• Selection de tâches en ordonnancement (Exemple 1).
• Modélisation de formules booléennes.
• Ensemble dans un graphe ayant une “bonne” propriété (voir BE).

32/32
 Programme Linéaire en nombre entiers
(PLNE)

On peut modéliser de nombreux problèmes avec des PL ayant comme

variables {0, 1}. Par exemple:
• Selection de tâches en ordonnancement (Exemple 1).
• Modélisation de formules booléennes.
• Ensemble dans un graphe ayant une “bonne” propriété (voir BE).
→ De nombreux problèmes sont NP-complets et non approximables.

32/32
 Programme Linéaire en nombre entiers
(PLNE)

On peut modéliser de nombreux problèmes avec des PL ayant comme

variables {0, 1}. Par exemple:
• Selection de tâches en ordonnancement (Exemple 1).
• Modélisation de formules booléennes.
• Ensemble dans un graphe ayant une “bonne” propriété (voir BE).
→ De nombreux problèmes sont NP-complets et non approximables.

Bilan: Les programmes linéaires en nombre entiers sont beaucoup plus

compliqués que ceux continus...

32/32