Cours de recherche op´erationnelle I
Nadia Brauner
Grenoble, 2013-2014
1
Auteurs
Ont particip´e `a la r´edaction de ce cours (par ordre d’arriv´ee)
Nadia Brauner
Christophe Rapine
Julien Moncel
Laurent Beaudou
Ont aid´e, corrig´e, relu et donn´e des id´ees
Gerd Finke
Yann Kieffer
Van Dat Cung
Ont donn´e les TD et propos´e des exercices
Ayse Akbalik
Sergei Lenglet
Aline Parreau
Guillaume Massonnet
2
Formations `a Grenoble
Formation initiale
RO `a l’UJF (M1 Info, L3 Miage, Polytech’RICM4)
Gestion de la production `a l’UJF (M1 Miage)
Optimisation pour l’´energie (M2 Miage)
Outils Formels et Graphes (Polytech’RICM2)
RO `a l’ENSIMAG (1A, 2A)
RO `a l’ENSGI (1A, 2A)
Master 2 Math´ematiques et Informatique, Option Recherche
Op´erationnelle, Combinatoire et Optimisation
Formation continue
Recherche op´erationnelle (tous les ans, 4 jours)
Graphes et optimisation (tous les ans, 3 jours)
3
Recherche Op´erationnelle : faisons connaissance
Nadia Brauner
Nadia [email protected]
Professeur Grenoble I
Responsable Master 2 R
ROCO
Recherche Op´erationnelle,
Combinatoire et Optimisation
Laboratoire
´equipe Recherche Op´erationnelle
´equipe Opti-Com
Pr´esidente de la
Soci´et´e Fran¸caise de RO-AD
4
Recherche Op´erationnelle : faisons connaissance
Probl`emes th´eoriques
Ordonnancement high-multiplicity (∈ NP ?)
Ordonnancement dans ateliers robotis´ees
OC appliqu´ee `a la micro-´electronique
Contrats industriels
ILOG : Probl`emes complexes de transport
IFP : Planification d’exp´eriences chimiques
de Facto : Optimisation du test des circuits
Participation `a la cr´eation d’une startup
OASIC : optimisation de la conception de
cellules logiques
5
La recherche op´erationnelle
6
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Plan
1 La Recherche Op´erationnelle
2 Applications
3 Outils
4 La RO en France
5 R´ef´erences
N. Brauner
7
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Plan
1 La Recherche Op´erationnelle
2 Applications
3 Outils
4 La RO en France
5 R´ef´erences
N. Brauner
8
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle ou Science de la D´ecision
D´efinitions
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´erationnelle : approche scientifique pour la r´esolution
de problemes de gestion de systemes complexes
N. Brauner
9
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
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`emes industriels et
´economiques.
Des mod`eles pour analyser des situations complexes
Permet aux d´ecideurs de faire des choix efficaces et robustes
N. Brauner
10
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
Approche quantitative pour produire les meilleures d´ecisions
Une discipline `a la crois´ee des math´ematiques et de
l’informatique
prolongement de l’algorithmique
manipulant des structures plus ´elabor´ees : graphes, poly`edres...
domaine d’application de la th´eorie de la complexit´e
algorithmique
Une boite `a outils de m´ethodes, tant positives que n´egatives,
pour aborder sainement et sereinement les probl`emes
d’optimisation
N. Brauner
11
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
Les outils de RO-AD
aident `a trouver
une solution o`u l’homme n’en trouvait pas
une solution sur des problemes nouveaux ou l’homme n’a
aucune exp´erience
plusieurs solutions la ou l’homme n’en envisageait qu’une
aident `a juger de la qualit´e d’une solution
aident `a confirmer / justifier des d´ecisions
N. Brauner
12
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Plan
1 La Recherche Op´erationnelle
2 Applications
3 Outils
4 La RO en France
5 R´ef´erences
N. Brauner
13
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
Voyageur de commerce (TSP)
Un voyageur de commerce, bas´e `a Toulon, doit visiter ses
clients `a travers la France.
Il souhaite effectuer la tourn´ee la plus courte possible.
N. Brauner
14
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
Voyageur de commerce
Instance : n villes avec une matrice de distances
Solution : tourn´ee visitant chaque ville et revenant `a Toulon
N. Brauner
15
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
Algorithme Glouton pour le TSP
N. Brauner
16
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
Transport
de marchandises
des entrepˆots vers les clients
coˆuts 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´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
Applications
Plus court chemin
Quel est le trajet le plus court
entre Grenoble et Nice
en voiture ?
N. Brauner
18
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
24h de RO
Advertisement
8h : optimisation de la r´ecolte et du d´epˆot des d´echets
recyclables
. . .
15h : placement automatique des v´ehicules 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´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
le 15 octobre 2012 :
N. Brauner
20
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
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´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Mariages stables
Mariages stables
Des femmes : Alice, B´en´edicte, Camille
Des hommes : Elie, Fran¸cois, Gondran
Pr´ef´erences des femmes
Pr´ef´erences 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´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Mariages stables
Un couplage est instable s’il contient deux personnes A et B non
mari´ees ensemble qui se pr´eferent mutuellement a leurs conjoints :
F est mari´ee avec g
G est mari´e avec f
F pr´efere G a g
G pr´efere F a f
Questions
Comment v´erifier 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
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Mariages stables
Applications
Situations o`u les m´ecanismes de march´es traditionnels ne
fonctionnent pas
R´epartition de biens rares, h´et´erog`enes, indivisibles
Affectations de candidats sur des places
´el`eves - ´ecoles d’ing´enieur
travailleurs - postes
internes - hˆopitaux
´etudiants - universit´es
Dons d’organes (reins)
N. Brauner
24
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
Les challenges ROADEF
http://challenge.roadef.org/
2010 Gestion d’´energie
(EDF)
2009 Gestion des perturbations dans le transport a´erien (Amadeus)
2007 Planification des techniciens et des interventions pour les
t´el´ecommunications
(France Telecom)
2005 Ordonnancement de v´ehicules pour une chaˆıne de montage
automobile
(Renault)
2003 Gestion des prises de vue r´ealis´ees par un satellite
d’observation de la Terre
(ONERA et CNES)
2001 Allocation de fr´equences avec polarisation
(CELAR, arm´ee)
1999 Gestion de stock de mat´eriels
(Bouygues)
N. Brauner
25
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
Le challenges ROADEF/EURO 2012
R´eaffectation de machines
Propos´e par Google
82 ´equipes enregistr´ees dans 33 pays
30 ´equipes qualifi´ees
Vainqueur Junior : ´equipe polonaise
Vainqueur Open Source et Senior : ´equipe bosniaques
N. Brauner
26
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
http://www.roadef.org/content/roadef/soireeRO.htm
Introduction et historique de la RO
Mesure de performance de la RO
Ingr´edients d’une bonne approche RO
L’enseignement de la RO
Le serious game, un outil pour convaincre
Faut-il un mod`ele simple ou haute fid´elit´e ? Solutions robustes
RO, SI et capacit´es de calcul
N. Brauner
27
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Emmanuel Guyot, Directeur Marketing et Revenue Management
TF1 PUBLICITE
Yves Caseau, Executive Vice-Pr´esident BOUYGUES TELECOM
Animation : Denis Montaut, Pr´esident d’Eurod´ecision
Nadia Brauner, Pr´esidente de la Roadef, G-SCOP
Yvon Qu´erou, Directeur Informatique AIR FRANCE
Jean-Charles Billaut, Professeur `a l’Universit´e de Tours
Jean-Paul Hamon, ex Executive Vice-Pr´esident D´eveloppement
AMADEUS
N. Brauner
28
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
Domaines d’application
Conception, configuration et exploitation
de syst`emes techniques complexes
(r´eseaux de communication, syst`emes d’information)
Gestion de la chaˆıne logistique
(transports, production, stocks. . . )
Gestion strat´egique d’investissements
et aussi
sant´e, instruction publique, voirie,
ramassage et distribution de courrier,
production et transport d’´energie,
t´el´ecommunications, banques, assurances. . .
N. Brauner
29
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
Domaines d’application
Production : maximiser le profit selon disponibilit´e de la main
d’œuvre, demande du march´e, capacit´e de production, prix de
revient du mat´eriau brut. . .
Transport : minimiser distance totale parcourue selon quantit´es de
mat´eriaux `a transporter, capacit´e 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´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
Face a un probleme pratique de d´ecision
Aspects math´ematiques
contraintes, objectifs, simplifications
Mod´elisation
graphes, programmation lin´eaire, PPC...
Analyse des mod`eles et r´esolution
´etude de complexit´e : que peut-on esp´erer pour le temps de
r´esolution imparti ?
mise au point d’algorithmes
Impl´ementation et analyse des r´esultats
valider par rapport `a la demande
it´erer avec le demandeur si n´ecessaire
D´eploiement des solutions
Int´egration logicielle
N. Brauner
31
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Plan
1 La Recherche Op´erationnelle
2 Applications
3 Outils
4 La RO en France
5 R´ef´erences
N. Brauner
32
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
Programmation lin´eaire
min le coˆut / max le profit
min / max
c1x1 + c2x2 . . . cnxn
satisfaire la demande
a1x1 + a2x2 . . . anxn ≥ b1
avec des ressources limit´ees
1x1 + a(cid:48)
a(cid:48)
2x2 . . . a(cid:48)
nxn ≤ b(cid:48)
1
quantit´es produites
x1, x2 . . . xn ≥ 0
N. Brauner
33
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
Optimisation Combinatoire
Trouver la meilleure solution parmi un nombre fini mais tr`es
grand de choix
Un probl`eme d’OC se caract´erise par :
La pr´esence de choix, `a faire parmi un ensemble fini
d’alternatives
Advertisement
Une notion de coˆut, ou de gain, ou de perte
La n´ecessit´e de faire globalement les bons choix, de maniere a
optimiser la valeur objectif
exemples : emplois du temps. . .
Combinatoire
´echiquier tronqu´e
http://mathsamodeler.ujf-grenoble.fr/LAVALISE/
N. Brauner
34
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
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ˆete
(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ˆetes = coˆuts, temps, distance, capacit´es. . .
meilleur chemin de i `a j
meilleurs parcours
passant par chaque ville
passant par chaque arˆete
. . .
Repr´esentation de r´eseaux, de pr´ec´edences en ordonnancement,
de compatibilit´e de produits...
N. Brauner
35
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
Autre outils
Files d’attente
Stochastique
Simulation
`A l’interface de
Informatique : algorithmique
Math´ematiques : mod´elisation
´Economie : gestion, strat´egie
dessin de Lionel Lagarde
N. Brauner
36
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Plan
1 La Recherche Op´erationnelle
2 Applications
3 Outils
4 La RO en France
5 R´ef´erences
N. Brauner
37
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle : entreprises en France
Grands groupes avec un pˆole 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´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle : entreprises en France
Pour les autres entreprises
Soci´et´es de conseil sp´ecialis´ees
Logiciels sur ´etag`ere
Laboratoires acad´emiques
N. Brauner
39
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle : entreprises en France
Soci´et´es de conseil
accompagnent les industriels pour mettre en place des syst`emes
d’aide `a la d´ecision
EURODECISION
Conseil en optimisation des ressources et planification de la
production, outils d’aide `a la d´ecision
ARTELYS
Solutions en optimisation
...
N. Brauner
40
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle : entreprises en France
´Editeurs de logiciels
librairies d´edi´ees a des problemes math´ematiques
ILOG (IBM)
Optimization tools and engines, Visualization software
components, Supply chain applications
COSYTEC
offrir des solutions logicielles, `a base de technologie de
programmation par contraintes, pour r´esoudre des probl`emes
d’optimisation des ressources
FICO et ARTELYS
Fico XPress : logiciels de mod´elisation de probl`emes lin´eaires
ou quadratiques avec variables r´eelles ou enti`eres
Knitro : optimiseur non lin´eaire
Artelys Kalis : Programmation par contraintes
...
N. Brauner
41
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle : entreprises en France
´Editeurs de logiciels
librairies d´edi´ees a des problemes m´etiers
ALMA : Placement et d´ecoupe
ex : petit bateau (habits), chantiers navals
AMADEUS : Voyage
plateforme de r´eservation centralis´ee pour l’industrie du
voyage et outils de gestion des compagnies a´eriennes
Optilogistics : transport et logistique
progiciels d’optimisation de tourn´ees et de planification du
transport
Ordecsys, Oracle...
N. Brauner
42
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle : entreprises en France
Alma : D´ecoupe
N. Brauner
43
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle : en France
Et dans le monde acad´emique
enquˆete 2010 de la Roadef
≈ 75 ´equipes ou laboratoires
≈ 1400 membres
≈ 700 chercheurs, enseignants chercheurs, ing´enieurs de
recherche permanents
≈ 500 doctorants
N. Brauner
44
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle : pour en savoir plus
Le Livre Blanc de la Recherche Op´erationnelle en France
Comment les industriels s’organisent
D’incontestables r´eussites
Soci´et´es de conseil et ´editeurs de logiciels
http://www.roadef.org/
N. Brauner
45
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Plan
1 La Recherche Op´erationnelle
2 Applications
3 Outils
4 La RO en France
5 R´ef´erences
N. Brauner
46
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Bibliographie
de Werra, D., Liebling, T.-M., and Hˆeche, J.-F.
Recherche Op´erationnelle pour Ing´enieurs, Tome 1.
Presses Polytechniques et Universitaires Romandes, 2003.
Sakarovitch, M.
Optimisation Combinatoire, Graphes et Programmation
Lin´eaire.
Hermann, Enseignement des sciences, Paris, 1984.
Sakarovitch, M.
Optimisation Combinatoire, Programmation Discr`ete.
Hermann, Enseignement des sciences, Paris, 1984.
Wolsey, L. A.
Integer Programming.
Wiley-Interscience, 1998.
N. Brauner
47
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Webographie
Cours
Poly de cours
http://www.g-scop.inpg.fr/~braunern/
Compl´ements au cours
http://www.g-scop.inpg.fr/~rapinec/
M2R de Recherche Op´erationnelle, Combinatoire et Optim.
http://www.g-scop.inpg.fr/ROCO/
Vie de la RO en France
Soci´et´e fran¸caise de RO
http://www.roadef.org
Groupe de Recherche en RO du CNRS
http://www-poleia.lip6.fr/~fouilhoux/gdrro/
S´eminaire de recherche en optim. combinatoire `a Grenoble
Advertisement
http://oc.inpg.fr/index.php?page=5/
N. Brauner
48
La Recherche Op´erationnelle
Applications
Outils
La RO en France
R´ef´erences
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´erationnelle
Applications
Outils
La RO en France
R´ef´erences
Recherche Op´erationnelle
En conclusion
faire le mieux
coˆut min, meilleur profit, plus courte distance, le plus rapide. . .
avec les ressources disponibles
temps machine, postes de travail, m´emoire, ressource homme,
matiere premiere, camions. . .
Dessins de L. Lagarde
N. Brauner
50
Programmation lin´eaire
N. Brauner
51
Programmation lin´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Plan
6
Introduction `a la programmation lin´eaire
7
Interpr´etation g´eom´etrique
8 Bases et points extrˆemes
9 L’algorithme du simplexe
N. Brauner
52
Programmation lin´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Plan
6
Introduction `a la programmation lin´eaire
7
Interpr´etation g´eom´etrique
8 Bases et points extrˆemes
9 L’algorithme du simplexe
N. Brauner
53
Programmation lin´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Programmation lin´eaire
Cadre de la PL
Programmation lin´eaire
nombre fini de variables r´eelles, contraintes lin´eaires, objectif
lin´eaire
Variables x1, x2 . . . xn r´eelles
Contrainte g´en´erique (contrainte i) :
n
(cid:88)
j=1
aij xj ≤ bi
Fonction-objectif g´en´erique (`a maximiser / minimiser) :
f (x1, x2 . . . xn) =
n
(cid:88)
j=1
cj xj
N. Brauner
54
Programmation lin´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Programmation lin´eaire
Exemple : culture de courgettes et navets
Contraintes concernant les quantit´es d’engrais et d’anti-parasites
8(cid:96) engrais A disponible
→ 2(cid:96)/m2 n´ecessaires pour courgettes, 1(cid:96)/m2 pour navets
7(cid:96) engrais B disponible
→ 1(cid:96)/m2 n´ecessaires pour courgettes, 2(cid:96)/m2 pour navets
3(cid:96) anti-parasites disponible
→ 1(cid:96)/m2 n´ecessaires pour navets
Objectif : produire le maximum (en poids) de l´egumes, sachant
que rendements = 4kg /m2 courgettes, 5kg /m2 navets
N. Brauner
55
Programmation lin´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Programmation lin´eaire
Exemple : culture de courgettes et navets
Variables de d´ecision
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´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Programmation lin´eaire
Int´erˆet de la PL
Probl`eme g´en´eral d’optimisation sous contraintes
⇒ AUCUNE m´ethode G´EN´ERALE de r´esolution ! !
Probl`eme lin´eaire quelconque
⇒ existence de m´ethodes de r´esolution g´en´erales et efficaces
Ces m´ethodes sont efficaces en th´eorie et en pratique
⇒ existence de nombreux logiciels de r´esolution :
Excel, CPLEX, Mathematica, LP-Solve. . .
Cadre restrictif
variables r´eelles
contraintes lin´eaires
objectif lin´eaire
N. Brauner
57
Programmation lin´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Programmation lin´eaire
Repr´esentation in extenso
max 4xc + 5xn
2xc + xn ≤ 8
xc + 2xn ≤ 7
xn ≤ 3
xc ≥ 0 et xn ≥ 0
Repr´esentation 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´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Programmation lin´eaire
Repr´esentation in extenso
max z = (cid:80)
j cj xj
s.c.
(cid:80)
j aij xj
xj
≤
≥
=
≥
bi
0
i = 1, 2 . . . m
j = 1, 2 . . . n
N. Brauner
59
Programmation lin´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Programmation lin´eaire
second membre b =
b1
b2
...
bm
n var. de d´ecision X =
x1
x2
...
xn
matrice de format m × n
A =
a11
a21
a12
a22
Advertisement
am1 am2
a1n
a2n
. . .
. . .
. . .
. . . amn
coˆut (ou profit) c = (c1, c2 . . . cn)
Repr´esentation matricielle
max z = cx
s.c.
Ax
x
≤
≥
=
≥
b
0
N. Brauner
60
Programmation lin´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Programmation lin´eaire
Vocabulaire
xi variable de d´ecision du probl`eme
x = (x1, . . . , xn) solution r´ealisable (admissible)
ssi elle satisfait toutes les contraintes
ensemble des solutions r´ealisables = domaine ou r´egion
admissible
x = (x1, . . . , xn) solution optimale
ssi elle est r´ealisable et optimise la fonction-objectif
contraintes in´egalit´e ou ´egalit´e lin´eaire
a11x1 + a12x2 . . . + a1nxn ≤ b1
a21x1 + a22x2 . . . + a2nxn ≥ b2
a31x1 + a32x2 . . . + a3nxn = b3
fonction objectif (ou fonction ´economique) lin´eaire
max / min c1x1 + c2x2 . . . + cnxn
N. Brauner
61
Programmation lin´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Programmation lin´eaire
Applications
Feuille de TD : Programmation lin´eaire
Exercice 1 : Production de vins
Exercice 2 : Publicit´e
Exercice 3 : Compagnie a´erienne
Exercice 4 : Fabrication d’huile d’olives
Exercice 5 : Laiterie
N. Brauner
62
Programmation lin´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Programmation lin´eaire
Forme canonique d’un PL
maximisation
toutes les variables sont non n´egatives
toutes les contraintes sont des in´equations 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´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Programmation lin´eaire
Forme standard d’un PL
maximisation
toutes les variables sont non n´egatives
toutes les contraintes sont des ´equations
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´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Programmation lin´eaire
Passage entre les formes
´equation → in´equation
ax = b ⇐⇒
(cid:26) ax ≤ b
ax ≥ b
max ↔ min
in´equation → ´equation : ajouter une variable d’´ecart
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´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Programmation lin´eaire
Passage entre les formes
Feuille de TD : Programmation lin´eaire
Exercice 6 : Formes lin´eaires et canoniques
N. Brauner
66
Programmation lin´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Programmation lin´eaire
Lin´eariser un probl`eme non lin´eaire
ei : expression lin´eaire des variables de d´ecision
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´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Programmation lin´eaire
Lin´eariser un probl`eme non lin´eaire
Feuille de TD : Programmation lin´eaire
Exercice 5 : Lin´earisation
N. Brauner
68
Programmation lin´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Programmation lin´eaire
Un peu d’histoire
ann´ees 30-40 : Kantorovitch, ´economiste sovi´etique
⇒ mod`eles lin´eaires pour la planification et l’optimisation de
la production
ann´ees 40-50 : Dantzig, math´ematicien am´ericain
⇒ algorithme du simplexe
application historique
Op´erations Vittles et Plainfare pour ravitaillement de la trizone
pendant le blocus de Berlin par pont a´erien (23 juin 1948 – 12
mai 1949)
simplexe ex´ecut´e a la main (des milliers de variables), jusqu’a
12 000 tonnes de mat´eriel par jour !
1975 : prix Nobel ´economie Kantorovitch
XXIeme siecle : logiciels de PL disponibles partout, utilisation
de la PL dans tous les domaines industriels...
N. Brauner
69
Programmation lin´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Plan
6
Introduction `a la programmation lin´eaire
7
Interpr´etation g´eom´etrique
8 Bases et points extrˆemes
9 L’algorithme du simplexe
N. Brauner
70
Programmation lin´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Interpr´etation g´eom´etrique
Exemple : culture de courgettes et navets
Variables de d´ecision
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´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Interpr´etation g´eom´etrique
Interpr´eter 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´ealisables = intersection de ces
demi-plans : poly`edre
N. Brauner
72
xyProgrammation lin´eaire
Interpr´etation g´eom´etrique
Bases et points extrˆemes
L’algorithme du simplexe
Interpr´etation g´eom´etrique
Optimiser l’objectif
Advertisement
Les lignes de niveau {4x + 5y = constante} sont des dr...