Recherche opérationnelle

GC-SIE
 Plan du cours
 Optimisation linéaire
– Introduction et exemples
– Géométrie
– Algo. du simplexe (phase II)
– Algo. du simplexe (phase I)
– Dualité

Introduction Michel Bierlaire 2

 Plan du cours (suite)
 Optimisation non-linéaire
– Introduction et exemples
– Conditions d’optimalité
– Plus forte pente et Newton
– Variations sur Newton
– Moindres carrés

Introduction Michel Bierlaire 3

 Plan du cours (suite)
 Problèmes de réseaux
– Introduction et exemples
– Problème du plus court chemin
– Problème de flot maximal
– Problème de transbordement

Introduction Michel Bierlaire 4

 Plan du cours (suite)
 Problèmes en nombres entiers
– Introduction et exemples
– Algorithmes exacts
– Algorithmes d’approximation
– Heuristiques
 Recuit simulé
 Algorithmes génétiques
 Introduction à la simulation

Introduction Michel Bierlaire 5

 Introduction

Recherche opérationnelle
Génie Civil
 Chapitre 1
 Introduction à l’optimisation
– Démarche générale
– Exemples
– Formulation
– Approche intuitive
– Types de problèmes
– Algorithmes

Introduction Michel Bierlaire 7

 Historique
Théorie des Programmation Combinatorique,
décisions mathématique Théorie des graphes

Pascal (1654) Fourier (1824) Sainte-Laguë (1926)

Fermat (1654) D. König (1936)
Bernouilli (1713)
RO 2e guerre mondiale:
1ère application: militaire

Simplexe Premier “grand” algorithme (1947)

1er ordinateur 1ère application commerciale (1956)

 Mots clés
 Modélisation
– Simplification de la réalité pour pouvoir en
appréhender certains aspects
 Optimisation
– Identification d’une configuration qui soit meilleure
que toute autre suivant un critère spécifique
 Simulation
– Représentation artificielle d’un fonctionnement réel

Introduction Michel Bierlaire 9

 Recherche
Statistiques opérationnelle
Réalité Modèle

Observateur Description Prédiction

Optimisation

Données
Décision

Estimation

Modèle
 Exemple : Geppetto
Geppetto, Inc., jouets en bois.
Soldats : vendus 27F et coûtant 10F de matériel brut.
Coûts généraux : 14F par soldat.
Qté. de travail : 1 h de menuiserie 2 h de finissage
Trains : vendus 21F et coûtant 9F de matériel brut.
Coûts généraux : 10F par train.
Qté. de travail : 1 h de menuiserie et 1 h de finissage
Au maximum, on dispose de
80 h de menuiserie et
100 h de finissage par semaine.
Demande : illimitée pour les trains,
maximum 40 soldats par semaine.

Introduction Michel Bierlaire 11

 Exemple : Geppetto
Comment maximiser les bénéfices de Geppetto ?
Modélisation :
1.         Variables de décision :
x1 = nombre de soldats produits par semaine
x2 = nombre de trains produits par semaine
2.         Fonction objectif :
Bénéfice = revenu – coût du matériel – coûts généraux
Revenu = revenu pour les soldats +
revenu pour les trains
= (francs/soldat)(soldats/semaine) +
(francs/train)(trains/semaine)
= 27 x1 + 21 x2
Coût du matériel = 10 x1 + 9 x2
Coûts généraux = 14 x1 + 10 x2

Introduction Michel Bierlaire 12

 Exemple : Geppetto
Bénéfice = (27 x1 + 21 x2)-(10 x1 + 9 x2)-(14 x1 + 10 x2)
= 3 x1 + 2 x 2
On notera Maximiser z = 3 x1 + 2 x2
3.         Contraintes :
a) Pas plus de 100 h de finissage par semaine
b) Pas plus de 80 heures de menuiserie par semaine
c) Pas plus de 40 soldats par semaine
Finissage/semaine =
(finissage/soldat)(soldats/semaine) +
(finissage/train)(trains/semaine) =
2 x1 + x2
Contrainte a : 2 x1 + x2  100
Contrainte b : x1 + x2  80
Contrainte c : x1  40
x1  0, x2  0

Introduction Michel Bierlaire 13

 Formulation
 Sous quelles formes présenter le problème
d’optimisation ?
 Formes standard ou canonique
 Exigences des algorithmes
 Nécessité de transformer le problème

Introduction Michel Bierlaire 14

 Formulation
 Fonction objectif
min f(x) max f(x)
 Contraintes

g(x)  cte g(x)  cte g(x) = cte

 Contraintes de bornes

lxu
 Contraintes de signe

x0

Introduction Michel Bierlaire 15

 Formulation : transformations

Introduction Michel Bierlaire 16

 Formulation : transformations

g(x)  0 -g(x)  0

Introduction Michel Bierlaire 17

 Formulation : règles

Introduction Michel Bierlaire 18

 Formulation : exemple

sous contraintes

Introduction Michel Bierlaire 19

 Formulation : exemple

sous contraintes sous contraintes

Introduction Michel Bierlaire 20

 Approche intuitive
 Considérons des exemples triviaux
1. Une entreprise gagne 5F chaque fois qu’elle
vend 1 litre de produit chimique. Elle désire
maximiser son profit.
Profit (F)

1 Litres
Introduction Michel Bierlaire 21
 Approche intuitive
 Observations :
– Fonction objectif linéaire
– Pas de contraintes
– Solution infinie
 Commentaire :
– La solution est toujours infinie lorsque la
fonction objectif est linéaire et qu’il n’y a pas
de contraintes

Introduction Michel Bierlaire 22

 Approche intuitive
2. Un laboratoire achète 30F le litre de produit
chimique. Il dispose d’un budget de 1000F.
Quelle quantité maximale peut-il acheter ?
Coût (F)

300

10 Litres
Introduction Michel Bierlaire 23
 Approche intuitive
 Observations :
– Réponse évidente : 1000 / 30 litres
– Bien que l’on puisse dépenser 1000F ou moins, on
dépense exactement 1000F
 Commentaires :
– Si la fonction objectif et les contraintes sont linéaires, il
y a au moins une contrainte active à la solution
– La contrainte g(x)  0 est dite active en x* ssi g(x*)=0

Introduction Michel Bierlaire 24

 Approche intuitive
3. Un laboratoire achète 30F le litre de produit
chimique. Il dispose d’un budget de 1000F et
doit en acheter au minimum 40 litres. Quelle
quantité maximale peut-il acheter ?
Coût (F)

300

10 40 Litres
Introduction Michel Bierlaire 25
 Approche intuitive
 Observations :
– Problème impossible
– Contraintes incompatibles
 Commentaire :
– La solution peut ne pas exister. On dit que le
problème ne possède pas de solution
admissible.

Introduction Michel Bierlaire 26

 Approche intuitive
4. Un laboratoire achète 3F un microprocesseur. Il
dispose d’un budget de 10F. Quelle quantité
maximale peut-il acheter ?
Coût (F)

1 10/3 Microprocesseurs
Introduction Michel Bierlaire 27
 Approche intuitive
 Observations :
– Impossible d’acheter des parties de microprocesseurs
– Malgré que la fonction objectif et les contraintes soient
linéaires, le budget ne sera pas totalement dépensé
 Commentaire :
– Lorsque les variables sont entières, les résultats
théoriques peuvent être différents

Introduction Michel Bierlaire 28

 Approche intuitive
5. Un objet est lancé à la verticale à la vitesse de
50 m/s. Quand atteindra-t-il son point culminant
?
Tangente
Hauteur (m)

horizontale

Temps (sec)
Introduction Michel Bierlaire 29
 Approche intuitive
 Observations
– Fonction objectif non linéaire
– Pas de contraintes
– Solution finie
 Commentaires
– Si la fonction objectif est non linéaire, une solution
finie peut exister, même en l’absence de contraintes
– A la solution, la tangente à la courbe est horizontale
(i.e. la dérivée est nulle)

Introduction Michel Bierlaire 30

 Approche intuitive

Tangente
horizontale

mais pas un maximum, ni un minimum…

Introduction Michel Bierlaire 31

 Approche intuitive
 Observations
– Pas de solution finie
– Présence d’une tangente horizontale
 Commentaires
– Une solution finie n’est pas garantie par la non
linéarité de la fonction objectif
– Une tangente horizontale n’identifie pas
nécessairement une solution.

Introduction Michel Bierlaire 32

 Approche intuitive

Pas de tangente

Introduction Michel Bierlaire 33

 Approche intuitive
 Observation :
– La fonction n’est pas dérivable à la solution

 Commentaire:
– Attention aux fonctions non différentiables

Introduction Michel Bierlaire 34

 Approche intuitive
 Le plus haut sommet du monde est l’Everest
 Le plus haut sommet d’Asie est l’Everest
 Le plus haut sommet d’Europe est l’Elbrouz

Introduction Michel Bierlaire 35

 Types de problèmes
 Linéaire vs. non-linéaire
 Définition:
Une fonction f(x1,x2,…,xn) de x1,x2,…,xn est une
fonction linéaire si et seulement s’il existe un
ensemble de constantes c1,c2,…,cn telles que
f(x1,x2,…,xn) = c1 x1+c2 x2+…+cnxn
 Fonction objectif
 Contraintes

Introduction Michel Bierlaire 36

 Types de problèmes
 Avec ou sans contraintes
 Dans ce cours :
– Programmation linéaire
 Objectif linéaire
 Contraintes linéaires
– Programmation non linéaire
 Objectif non linéaire
 Sans contraintes

Introduction Michel Bierlaire 37

 Types de problèmes

x y
f(x) est concave sur X si pour tout x,yX, on a

Introduction Michel Bierlaire 38

 Types de problèmes
 Résumé des critères
– linéaire / non-linéaire
– contraintes / pas de contraintes
– convexe / non convexe
– concave / non concave
– différentiable / non différentiable
– variables continues / entières

Introduction Michel Bierlaire 39

 Algorithmes
 Al Khwarizmi, surnom du mathématicien arabe Muhammad Ibn Musa
(IXième siècle), né à Khwarizem, en Ouzbekistan.
– Il a écrit Al-jabr wa'l muqabala dont vient le mot « algèbre » [et les
équations]
 Algorithme:
suite finie de règles
à appliquer dans un ordre déterminé
à un nombre fini de données
pour arriver avec certitude,
en un nombre fini d’étapes,
à un certain résultat
et cela indépendamment des données.
 Résolution d’une classe de problèmes

Introduction Michel Bierlaire 40

 Algorithmes
La plupart des algorithmes considérés dans ce
cours auront la forme
 Soit x0 une estimation de la solution
 Pour k=0,…. faire
– Trouver xk+1 à partir de xk
 Tant que xk n’est pas acceptable
 De telle manière que
limk xk = x*
Introduction Michel Bierlaire 41