Cours de recherche opérationnelle I
Nadia Brauner
Grenoble, 2013-2014
1
Auteurs
Ont participé à la rédaction de ce cours (par ordre d’arrivée)
Nadia Brauner
Christophe Rapine
Julien Moncel
Laurent Beaudou
Ont aidé, corrigé, relu et donné des idées
Gerd Finke
Yann Kieffer
Van Dat Cung
Ont donné les TD et proposé des exercices
Ayse Akbalik
Sergei Lenglet
Aline Parreau
Guillaume Massonnet
2
Formations à Grenoble
Formation initiale
RO à l’UJF (M1 Info, L3 Miage, Polytech’RICM4)
Gestion de la production à l’UJF (M1 Miage)
Optimisation pour l’énergie (M2 Miage)
Outils Formels et Graphes (Polytech’RICM2)
RO à l’ENSIMAG (1A, 2A)
RO à l’ENSGI (1A, 2A)
Master 2 Mathématiques et Informatique, Option Recherche
Opérationnelle, Combinatoire et Optimisation
Formation continue
Recherche opérationnelle (tous les ans, 4 jours)
Graphes et optimisation (tous les ans, 3 jours)
3
Recherche Opérationnelle : faisons connaissance
Nadia Brauner
Nadia [email protected]
Professeur Grenoble I
Responsable Master 2 R
ROCO
Recherche Opérationnelle,
Combinatoire et Optimisation
Laboratoire
équipe Recherche Opérationnelle
équipe Opti-Com
Présidente de la
Société Française de RO-AD
4
Recherche Opérationnelle : faisons connaissance
Problèmes théoriques
Ordonnancement high-multiplicity (∈ NP ?)
Ordonnancement dans ateliers robotisées
OC appliquée à la micro-électronique
Contrats industriels
ILOG : Problèmes complexes de transport
IFP : Planification d’expériences chimiques
de Facto : Optimisation du test des circuits
Participation à la création d’une startup
OASIC : optimisation de la conception de
cellules logiques
5
La recherche opérationnelle
6
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Plan
1 La Recherche Opérationnelle
2 Applications
3 Outils
4 La RO en France
5 Références
N. Brauner
7
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Plan
1 La Recherche Opérationnelle
2 Applications
3 Outils
4 La RO en France
5 Références
N. Brauner
8
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle ou Science de la Décision
Définitions
Cambridge Dictionary
Operational research UK (US operations research)
The systematic study of how best to solve problems in business
and industry
Wikipedia
Operations research, operational research, or simply OR, is the use
of mathematical models, statistics and algorithms to aid in
decision-making
Roadef
Recherche Opérationnelle : approche scientifique pour la résolution
de problemes de gestion de systemes complexes
N. Brauner
9
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Science du (cid:28) comment mieux faire avec moins (cid:29)
Des outils pour
rationaliser
simuler
optimiser
planifier
l’architecture et le fonctionnement des systèmes industriels et
économiques.
Des modèles pour analyser des situations complexes
Permet aux décideurs de faire des choix efficaces et robustes
N. Brauner
10
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Approche quantitative pour produire les meilleures décisions
Une discipline à la croisée des mathématiques et de
l’informatique
prolongement de l’algorithmique
manipulant des structures plus élaborées : graphes, polyèdres...
domaine d’application de la théorie de la complexité
algorithmique
Une boite à outils de méthodes, tant positives que négatives,
pour aborder sainement et sereinement les problèmes
d’optimisation
N. Brauner
11
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Les outils de RO-AD
aident à trouver
une solution où l’homme n’en trouvait pas
une solution sur des problemes nouveaux ou l’homme n’a
aucune expérience
plusieurs solutions la ou l’homme n’en envisageait qu’une
aident à juger de la qualité d’une solution
aident à confirmer / justifier des décisions
N. Brauner
12
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Plan
1 La Recherche Opérationnelle
2 Applications
3 Outils
4 La RO en France
5 Références
N. Brauner
13
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Voyageur de commerce (TSP)
Un voyageur de commerce, basé à Toulon, doit visiter ses
clients à travers la France.
Il souhaite effectuer la tournée la plus courte possible.
N. Brauner
14
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Voyageur de commerce
Instance : n villes avec une matrice de distances
Solution : tournée visitant chaque ville et revenant à Toulon
N. Brauner
15
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Algorithme Glouton pour le TSP
N. Brauner
16
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Transport
de marchandises
des entrepôts vers les clients
coûts de transport, distance sur les arcs
trouver le meilleur plan de distribution
i
(cid:97)
ai
(cid:80)(cid:80)(cid:80)(cid:80)(cid:80)(cid:80)(cid:113)
cij
j
(cid:97)
bj
(cid:97)
(cid:97)
A
(cid:97)
(cid:97)
B
min (cid:80) cij xij
(cid:88)
j∈B
(cid:88)
i∈A
xij ≤ ai
xij ≥ bj
xij ≥ 0
N. Brauner
17
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Applications
Plus court chemin
Quel est le trajet le plus court
entre Grenoble et Nice
en voiture ?
N. Brauner
18
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
24h de RO
8h : optimisation de la récolte et du dépôt des déchets
recyclables
. . .
15h : placement automatique des véhicules pour une
association de partage de voitures
16h : gestion des retards dans les transports publics pour
minimiser l’impact sur les passagers
. . .
http://www.24hor.org/
N. Brauner
19
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
le 15 octobre 2012 :
N. Brauner
20
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
N. Brauner
21
The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2012Alvin E. Roth, Lloyd S. ShapleyEnglishEnglish (pdf)Swedish Swedish (pdf) Press Release15 October 2012The Royal Swedish Academy of Sciences has decided to award The Sveriges Riksbank Prize in Economic Sciences in Memoryof Alfred Nobel for 2012 toAlvin E. RothHarvard University, Cambridge, MA, USA, and Harvard Business School, Boston, MA, USAandLloyd S. ShapleyUniversity of California, Los Angeles, CA, USA"for the theory of stable allocations and the practice of market design". Stable allocations – from theory to practiceThis year's Prize concerns a central economic problem: how to match different agents as well as possible.For example, students have to be matched with schools, and donors of human organs with patients in needof a transplant. How can such matching be accomplished as efficiently as possible? What methods arebeneficial to what groups? The prize rewards two scholars who have answered these questions on a journeyfrom abstract theory on stable allocations to practical design of market institutions.Lloyd Shapley used so-called cooperative game theory to study and compare different matching methods. A key issue is toensure that a matching is stable in the sense that two agents cannot be found who would prefer each other over their currentcounterparts. Shapley and his colleagues derived specific methods – in particular, the so-called Gale-Shapley algorithm – thatalways ensure a stable matching. These methods also limit agents' motives for manipulating the matching process. Shapleywas able to show how the specific design of a method may systematically benefit one or the other side of the market.Alvin Roth recognized that Shapley's theoretical results could clarify the functioning of important markets in practice. In aseries of empirical studies, Roth and his colleagues demonstrated that stability is the key to understanding the success ofparticular market institutions. Roth was later able to substantiate this conclusion in systematic laboratory experiments. He alsohelped redesign existing institutions for matching new doctors with hospitals, students with schools, and organ donors withpatients. These reforms are all based on the Gale-Shapley algorithm, along with modifications that take into account specificcircumstances and ethical restrictions, such as the preclusion of side payments.Even though these two researchers worked independently of one another, the combination of Shapley's basic theory and Roth'sempirical investigations, experiments and practical design has generated a flourishing field of research and improved theperformance of many markets. This year's prize is awarded for an outstanding example of economic engineering.La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Mariages stables
Mariages stables
Des femmes : Alice, Bénédicte, Camille
Des hommes : Elie, François, Gondran
Préférences des femmes
Préférences des hommes
A : G E F
B :
F E G
C : G E F
E : A B C
F : B C A
G : A C B
Comment faire les couples ?
N. Brauner
22
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Mariages stables
Un couplage est instable s’il contient deux personnes A et B non
mariées ensemble qui se préferent mutuellement a leurs conjoints :
F est mariée avec g
G est marié avec f
F préfere G a g
G préfere F a f
Questions
Comment vérifier qu’un couplage est stable ?
Est-ce qu’il existe toujours un couplage stable ?
Est-ce qu’on sait trouver un couplage stable quand il existe ?
N. Brauner
23
Publicité
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Mariages stables
Applications
Situations où les mécanismes de marchés traditionnels ne
fonctionnent pas
Répartition de biens rares, hétérogènes, indivisibles
Affectations de candidats sur des places
élèves - écoles d’ingénieur
travailleurs - postes
internes - hôpitaux
étudiants - universités
Dons d’organes (reins)
N. Brauner
24
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Les challenges ROADEF
http://challenge.roadef.org/
2010 Gestion d’énergie
(EDF)
2009 Gestion des perturbations dans le transport aérien (Amadeus)
2007 Planification des techniciens et des interventions pour les
télécommunications
(France Telecom)
2005 Ordonnancement de véhicules pour une chaˆıne de montage
automobile
(Renault)
2003 Gestion des prises de vue réalisées par un satellite
d’observation de la Terre
(ONERA et CNES)
2001 Allocation de fréquences avec polarisation
(CELAR, armée)
1999 Gestion de stock de matériels
(Bouygues)
N. Brauner
25
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Le challenges ROADEF/EURO 2012
Réaffectation de machines
Proposé par Google
82 équipes enregistrées dans 33 pays
30 équipes qualifiées
Vainqueur Junior : équipe polonaise
Vainqueur Open Source et Senior : équipe bosniaques
N. Brauner
26
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
http://www.roadef.org/content/roadef/soireeRO.htm
Introduction et historique de la RO
Mesure de performance de la RO
Ingrédients d’une bonne approche RO
L’enseignement de la RO
Le serious game, un outil pour convaincre
Faut-il un modèle simple ou haute fidélité ? Solutions robustes
RO, SI et capacités de calcul
N. Brauner
27
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Emmanuel Guyot, Directeur Marketing et Revenue Management
TF1 PUBLICITE
Yves Caseau, Executive Vice-Président BOUYGUES TELECOM
Animation : Denis Montaut, Président d’Eurodécision
Nadia Brauner, Présidente de la Roadef, G-SCOP
Yvon Quérou, Directeur Informatique AIR FRANCE
Jean-Charles Billaut, Professeur à l’Université de Tours
Jean-Paul Hamon, ex Executive Vice-Président Développement
AMADEUS
N. Brauner
28
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Domaines d’application
Conception, configuration et exploitation
de systèmes techniques complexes
(réseaux de communication, systèmes d’information)
Gestion de la chaˆıne logistique
(transports, production, stocks. . . )
Gestion stratégique d’investissements
et aussi
santé, instruction publique, voirie,
ramassage et distribution de courrier,
production et transport d’énergie,
télécommunications, banques, assurances. . .
N. Brauner
29
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Domaines d’application
Production : maximiser le profit selon disponibilité de la main
d’œuvre, demande du marché, capacité de production, prix de
revient du matériau brut. . .
Transport : minimiser distance totale parcourue selon quantités de
matériaux à transporter, capacité des transporteurs, points de
ravitaillement en carburant. . .
(cid:73) grande importance dans le milieu industriel :
production, transport, emploi du temps, finance. . .
N. Brauner
30
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Face a un probleme pratique de décision
Aspects mathématiques
contraintes, objectifs, simplifications
Modélisation
graphes, programmation linéaire, PPC...
Analyse des modèles et résolution
étude de complexité : que peut-on espérer pour le temps de
résolution imparti ?
mise au point d’algorithmes
Implémentation et analyse des résultats
valider par rapport à la demande
itérer avec le demandeur si nécessaire
Déploiement des solutions
Intégration logicielle
N. Brauner
31
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Plan
1 La Recherche Opérationnelle
2 Applications
3 Outils
4 La RO en France
5 Références
N. Brauner
32
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Programmation linéaire
min le coût / max le profit
min / max
c1x1 + c2x2 . . . cnxn
satisfaire la demande
a1x1 + a2x2 . . . anxn ≥ b1
avec des ressources limitées
1x1 + a(cid:48)
a(cid:48)
2x2 . . . a(cid:48)
nxn ≤ b(cid:48)
1
quantités produites
x1, x2 . . . xn ≥ 0
N. Brauner
33
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Optimisation Combinatoire
Trouver la meilleure solution parmi un nombre fini mais très
grand de choix
Un problème d’OC se caractérise par :
La présence de choix, à faire parmi un ensemble fini
d’alternatives
Une notion de coût, ou de gain, ou de perte
La nécessité de faire globalement les bons choix, de maniere a
optimiser la valeur objectif
exemples : emplois du temps. . .
Combinatoire
échiquier tronqué
http://mathsamodeler.ujf-grenoble.fr/LAVALISE/
N. Brauner
34
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Graphes
(cid:16)(cid:16)(cid:16)(cid:16)(cid:16)(cid:16)(cid:16)(cid:49)
(cid:24)(cid:24)(cid:24)(cid:24)(cid:24)(cid:24)(cid:24)(cid:24)(cid:58)
sommet
arête
(cid:8)
(cid:97)
(cid:65)
(cid:65)
(cid:65)
b
(cid:65)
(cid:97)
(cid:8)(cid:8)(cid:8)
a
(cid:97)
(cid:80)(cid:80)(cid:80)(cid:80)(cid:80)(cid:80)
5
(cid:8)(cid:8)(cid:8)(cid:8)
(cid:72)(cid:72)(cid:72)(cid:72)
(cid:0)
(cid:97)
(cid:0)
(cid:97)
(cid:97)
Valuation des arêtes = coûts, temps, distance, capacités. . .
meilleur chemin de i à j
meilleurs parcours
passant par chaque ville
passant par chaque arête
. . .
Représentation de réseaux, de précédences en ordonnancement,
de compatibilité de produits...
N. Brauner
35
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
Autre outils
Files d’attente
Stochastique
Simulation
À l’interface de
Informatique : algorithmique
Mathématiques : modélisation
Économie : gestion, stratégie
dessin de Lionel Lagarde
N. Brauner
36
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Plan
1 La Recherche Opérationnelle
2 Applications
3 Outils
4 La RO en France
5 Références
N. Brauner
37
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle : entreprises en France
Grands groupes avec un pôle R&D en RO
Airfrance
La SNCF
EDF
France Telecom
Bouygues
GDF Suez
La poste
Renault
Air Liquide
SFR
N. Brauner
38
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle : entreprises en France
Pour les autres entreprises
Sociétés de conseil spécialisées
Logiciels sur étagère
Laboratoires académiques
N. Brauner
39
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle : entreprises en France
Sociétés de conseil
accompagnent les industriels pour mettre en place des systèmes
d’aide à la décision
EURODECISION
Conseil en optimisation des ressources et planification de la
production, outils d’aide à la décision
ARTELYS
Solutions en optimisation
...
N. Brauner
40
La Recherche Opérationnelle
Applications
Outils
Publicité
La RO en France
Références
Recherche Opérationnelle : entreprises en France
Éditeurs de logiciels
librairies dédiées a des problemes mathématiques
ILOG (IBM)
Optimization tools and engines, Visualization software
components, Supply chain applications
COSYTEC
offrir des solutions logicielles, à base de technologie de
programmation par contraintes, pour résoudre des problèmes
d’optimisation des ressources
FICO et ARTELYS
Fico XPress : logiciels de modélisation de problèmes linéaires
ou quadratiques avec variables réelles ou entières
Knitro : optimiseur non linéaire
Artelys Kalis : Programmation par contraintes
...
N. Brauner
41
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle : entreprises en France
Éditeurs de logiciels
librairies dédiées a des problemes métiers
ALMA : Placement et découpe
ex : petit bateau (habits), chantiers navals
AMADEUS : Voyage
plateforme de réservation centralisée pour l’industrie du
voyage et outils de gestion des compagnies aériennes
Optilogistics : transport et logistique
progiciels d’optimisation de tournées et de planification du
transport
Ordecsys, Oracle...
N. Brauner
42
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle : entreprises en France
Alma : Découpe
N. Brauner
43
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle : en France
Et dans le monde académique
enquête 2010 de la Roadef
≈ 75 équipes ou laboratoires
≈ 1400 membres
≈ 700 chercheurs, enseignants chercheurs, ingénieurs de
recherche permanents
≈ 500 doctorants
N. Brauner
44
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle : pour en savoir plus
Le Livre Blanc de la Recherche Opérationnelle en France
Comment les industriels s’organisent
D’incontestables réussites
Sociétés de conseil et éditeurs de logiciels
http://www.roadef.org/
N. Brauner
45
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Plan
1 La Recherche Opérationnelle
2 Applications
3 Outils
4 La RO en France
5 Références
N. Brauner
46
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Bibliographie
de Werra, D., Liebling, T.-M., and Hêche, J.-F.
Recherche Opérationnelle pour Ingénieurs, Tome 1.
Presses Polytechniques et Universitaires Romandes, 2003.
Sakarovitch, M.
Optimisation Combinatoire, Graphes et Programmation
Linéaire.
Hermann, Enseignement des sciences, Paris, 1984.
Sakarovitch, M.
Optimisation Combinatoire, Programmation Discrète.
Hermann, Enseignement des sciences, Paris, 1984.
Wolsey, L. A.
Integer Programming.
Wiley-Interscience, 1998.
N. Brauner
47
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Webographie
Cours
Poly de cours
http://www.g-scop.inpg.fr/~braunern/
Compléments au cours
http://www.g-scop.inpg.fr/~rapinec/
M2R de Recherche Opérationnelle, Combinatoire et Optim.
http://www.g-scop.inpg.fr/ROCO/
Vie de la RO en France
Société française de RO
http://www.roadef.org
Groupe de Recherche en RO du CNRS
http://www-poleia.lip6.fr/~fouilhoux/gdrro/
Séminaire de recherche en optim. combinatoire à Grenoble
http://oc.inpg.fr/index.php?page=5/
N. Brauner
48
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Webographie
Collection de ressources pour la RO
http://www2.informs.org/Resources/
http://www.ensta.fr/~diam/ro/
Logiciels pour la RO
http://www.coin-or.org/resources.html
http://www.wior.uni-karlsruhe.de/bibliothek/
Blogs sur la RO
http://blog.vcu.edu/lamclay/
http://mat.tepper.cmu.edu/blog/
Des challenges industriels internationaux en RO
http://challenge.roadef.org/
N. Brauner
49
La Recherche Opérationnelle
Applications
Outils
La RO en France
Références
Recherche Opérationnelle
En conclusion
faire le mieux
coût min, meilleur profit, plus courte distance, le plus rapide. . .
avec les ressources disponibles
temps machine, postes de travail, mémoire, ressource homme,
matiere premiere, camions. . .
Dessins de L. Lagarde
N. Brauner
50
Programmation linéaire
N. Brauner
51
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Plan
6
Introduction à la programmation linéaire
7
Interprétation géométrique
8 Bases et points extrêmes
9 L’algorithme du simplexe
N. Brauner
52
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Plan
6
Introduction à la programmation linéaire
7
Interprétation géométrique
8 Bases et points extrêmes
9 L’algorithme du simplexe
N. Brauner
53
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Programmation linéaire
Cadre de la PL
Programmation linéaire
nombre fini de variables réelles, contraintes linéaires, objectif
linéaire
Variables x1, x2 . . . xn réelles
Contrainte générique (contrainte i) :
n
(cid:88)
j=1
aij xj ≤ bi
Fonction-objectif générique (à maximiser / minimiser) :
f (x1, x2 . . . xn) =
n
(cid:88)
j=1
cj xj
N. Brauner
54
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Programmation linéaire
Exemple : culture de courgettes et navets
Contraintes concernant les quantités d’engrais et d’anti-parasites
8(cid:96) engrais A disponible
→ 2(cid:96)/m2 nécessaires pour courgettes, 1(cid:96)/m2 pour navets
7(cid:96) engrais B disponible
→ 1(cid:96)/m2 nécessaires pour courgettes, 2(cid:96)/m2 pour navets
3(cid:96) anti-parasites disponible
→ 1(cid:96)/m2 nécessaires pour navets
Objectif : produire le maximum (en poids) de légumes, sachant
que rendements = 4kg /m2 courgettes, 5kg /m2 navets
N. Brauner
55
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Programmation linéaire
Exemple : culture de courgettes et navets
Variables de décision
xc : surface de courgettes
xn : surface de navets
Fonction objectif
max 4xc + 5xn
Contraintes
2xc + xn ≤ 8
xc + 2xn ≤ 7
xn ≤ 3
xc ≥ 0 et xn ≥ 0
(engrais A)
(engrais B)
(anti-parasites)
N. Brauner
56
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Programmation linéaire
Intérêt de la PL
Problème général d’optimisation sous contraintes
⇒ AUCUNE méthode GÉNÉRALE de résolution ! !
Problème linéaire quelconque
⇒ existence de méthodes de résolution générales et efficaces
Ces méthodes sont efficaces en théorie et en pratique
⇒ existence de nombreux logiciels de résolution :
Excel, CPLEX, Mathematica, LP-Solve. . .
Cadre restrictif
variables réelles
contraintes linéaires
objectif linéaire
N. Brauner
57
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Programmation linéaire
Représentation in extenso
max 4xc + 5xn
2xc + xn ≤ 8
xc + 2xn ≤ 7
xn ≤ 3
xc ≥ 0 et xn ≥ 0
Représentation matricielle
(engrais A)
(engrais B)
(anti-parasites)
max
(4 5)
(cid:19)
(cid:18) xc
xn
2 1
1 2
0 1
(cid:18) xc
xn
(cid:19)
≤
8
7
3
xc ≥ 0
xn ≥ 0
N. Brauner
58
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Programmation linéaire
Représentation in extenso
max z = (cid:80)
j cj xj
s.c.
(cid:80)
Publicité
j aij xj
xj
≤
≥
=
≥
bi
0
i = 1, 2 . . . m
j = 1, 2 . . . n
N. Brauner
59
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Programmation linéaire
second membre b =
b1
b2
...
bm
n var. de décision X =
x1
x2
...
xn
matrice de format m × n
A =
a11
a21
a12
a22
am1 am2
a1n
a2n
. . .
. . .
. . .
. . . amn
coût (ou profit) c = (c1, c2 . . . cn)
Représentation matricielle
max z = cx
s.c.
Ax
x
≤
≥
=
≥
b
0
N. Brauner
60
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Programmation linéaire
Vocabulaire
xi variable de décision du problème
x = (x1, . . . , xn) solution réalisable (admissible)
ssi elle satisfait toutes les contraintes
ensemble des solutions réalisables = domaine ou région
admissible
x = (x1, . . . , xn) solution optimale
ssi elle est réalisable et optimise la fonction-objectif
contraintes inégalité ou égalité linéaire
a11x1 + a12x2 . . . + a1nxn ≤ b1
a21x1 + a22x2 . . . + a2nxn ≥ b2
a31x1 + a32x2 . . . + a3nxn = b3
fonction objectif (ou fonction économique) linéaire
max / min c1x1 + c2x2 . . . + cnxn
N. Brauner
61
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Programmation linéaire
Applications
Feuille de TD : Programmation linéaire
Exercice 1 : Production de vins
Exercice 2 : Publicité
Exercice 3 : Compagnie aérienne
Exercice 4 : Fabrication d’huile d’olives
Exercice 5 : Laiterie
N. Brauner
62
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Programmation linéaire
Forme canonique d’un PL
maximisation
toutes les variables sont non négatives
toutes les contraintes sont des inéquations du type “≤”
max z = (cid:80)
j cj xj
s.c. (cid:80)
j aij xj ≤ bi
i = 1, 2 . . . m
xj ≥ 0
j = 1, 2 . . . n
forme matricielle
max z = cx
s.c. Ax ≤ b
x ≥ 0
N. Brauner
63
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Programmation linéaire
Forme standard d’un PL
maximisation
toutes les variables sont non négatives
toutes les contraintes sont des équations
max z = (cid:80)
j cj xj
s.c. (cid:80)
j aij xj = bi
i = 1, 2 . . . m
xj ≥ 0
j = 1, 2 . . . n
forme matricielle
max z = cx
s.c. Ax = b
x ≥ 0
N. Brauner
64
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Programmation linéaire
Passage entre les formes
équation → inéquation
ax = b ⇐⇒
(cid:26) ax ≤ b
ax ≥ b
max ↔ min
inéquation → équation : ajouter une variable d’écart
max f (x) = − min −f (x)
ax ≤ b ⇐⇒ ax + s = b,
ax ≥ b ⇐⇒ ax − s = b,
s ≥ 0
s ≥ 0
variable non contrainte → variables positives
x ≶ 0 ⇐⇒
(cid:26) x = x + − x −
x +, x − ≥ 0
N. Brauner
65
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Programmation linéaire
Passage entre les formes
Feuille de TD : Programmation linéaire
Exercice 6 : Formes linéaires et canoniques
N. Brauner
66
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Programmation linéaire
Linéariser un problème non linéaire
ei : expression linéaire des variables de décision
obj : min max{e1, e2 . . . en}
(cid:26) min y
y ≥ ei
i = 1, 2 . . . n
obj : max min{e1, e2 . . . en}
(cid:26) max y
y ≤ ei
obj : min |e1|
i = 1, 2 . . . n
|e| = max(e, −e)
min y
y ≥ e1
y ≥ −e1
min e+ + e−
e1 = e+ − e−
e+, e− ≥ 0
N. Brauner
67
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Programmation linéaire
Linéariser un problème non linéaire
Feuille de TD : Programmation linéaire
Exercice 5 : Linéarisation
N. Brauner
68
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Programmation linéaire
Un peu d’histoire
années 30-40 : Kantorovitch, économiste soviétique
⇒ modèles linéaires pour la planification et l’optimisation de
la production
années 40-50 : Dantzig, mathématicien américain
⇒ algorithme du simplexe
application historique
Opérations Vittles et Plainfare pour ravitaillement de la trizone
pendant le blocus de Berlin par pont aérien (23 juin 1948 – 12
mai 1949)
simplexe exécuté a la main (des milliers de variables), jusqu’a
12 000 tonnes de matériel par jour !
1975 : prix Nobel économie Kantorovitch
XXIeme siecle : logiciels de PL disponibles partout, utilisation
de la PL dans tous les domaines industriels...
N. Brauner
69
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Plan
6
Introduction à la programmation linéaire
7
Interprétation géométrique
8 Bases et points extrêmes
9 L’algorithme du simplexe
N. Brauner
70
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Interprétation géométrique
Exemple : culture de courgettes et navets
Variables de décision
xc : surface de courgettes
xn : surface de navets
Fonction objectif
max 4xc + 5xn
Contraintes
2xc + xn ≤ 8
xc + 2xn ≤ 7
xn ≤ 3
xc ≥ 0 et xn ≥ 0
(engrais A)
(engrais B)
(anti-parasites)
N. Brauner
71
Programmation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Interprétation géométrique
Interpréter les contraintes
courgettes et navets
2x + y ≤ 8 ⇒ demi-plan de R2
x + 2y ≤ 7 ⇒ demi-plan
y ≤ 3 ⇒ demi-plan
x ≥ 0 et y ≥ 0 ⇒ demi-plans
Ensemble des solutions réalisables = intersection de ces
demi-plans : polyèdre
N. Brauner
72
xyProgrammation linéaire
Interprétation géométrique
Bases et points extrêmes
L’algorithme du simplexe
Interprétation géométrique
Optimiser l’objectif
Les lignes de niveau {4x + 5y = constante} sont des dr...