Cours sur la modélisation statistique

Chapitre 1
Modelisation
1.1 Exemples de Probl`emes
1.1.1 La Caf´etaria
Caf´etaria ouverte toute la semaine.
Statistique sur le personnel requis :
Jour Lundi Mardi Mercredi Jeudi Vendredi Samedi Dimanche
Nombre 14 13 15 16 19 18 11
Un employ´e travaille 5 jour d’affil´ee puis a deux jours de repos.
Probl`eme : nombre minimal d’employ´e requis.
Quelles inconnues :
– x le nombre d’employ´es le jour i. Pas pratique : comment d´efinir le nombre d’em-i
ploy´es?
– x le nombre d’employ´es qui commencent le jour i.i
Mod`ele :
i=7Σ x est le nombre d’employ´es `a minimiser : fonction objectifii=1
Les contraintes :
(i) Le nombre de travailleurs commencant leur service est positif ou nul :
x ≥ 0 i= 1,...,7i
(ii) Les x sont des entiers.i
(iii) Pour chaque jour le nombre de travailleur est sup´erieur ou´egal `a celui requis. Le jour
i, le nombre de travailleurs est (en comptant modulo 7) :
x +x +...+xi i−1 i−4
12 CHAPITRE 1. MODELISATION
D’ou` :
x +x +x +x +x ≥ 141 7 6 5 4
x +x +x +x +x ≥ 132 1 7 6 5
x +x +x +x +x ≥ 153 2 1 7 6
x +x +x +x +x ≥ 164 3 2 1 7
x +x +x +x +x ≥ 195 4 3 2 1
x +x +x +x +x ≥ 186 5 4 3 2
x +x +x +x +x ≥ 117 6 5 4 3
Ce probl`eme est un probl`eme de programmation lin´eaire en nombre entiers
Le probl`eme peut se mettre sous la forme :
Max z =c.x
A.x≤b
x≥ 0
R´esolution avec le logiciel Eclipse.
[eclipse 2]: {X1+X4+X5+X6+X7 >= 14,
X1+X2+X5+X6+X7 >= 13,
X1+X2+X3+X6+X7 >= 15,
X1+X2+X3+X4+X7 >= 16,
X1+X2+X3+X4+X5 >= 19,
X6+X2+X3+X4+X5 >= 18,
X6+X7+X3+X4+X5 >= 11,
X1>=0,
X2>=0,
X3>=0,
X4>=0,
X5>=0,
X6>=0,
X7>=0,
Z=X1+X2+X3+X4+X5+X6+X7},
minimize(Z).
X1 = 4
X2 = X2
X3 = X3
X4 = X4
X5 = X5
X6 = 3
X7 = 0
Z = 22`1.1. EXEMPLES DE PROBLEMES 3
% Linear constraints:
{
X5 = 7 - X4,
X3 = 8 - X2,
X4 =< 7,
X2 =< 7,
X4 - X2 =< 1,
X4 >= 4
}Yes (0.01s cpu)
1.1.2 Probl`eme de jeu
Ciseau/Pierre/Papier
Jeu `a somme nulle : Gain +1 si gagnant, perte -1 si perdu, 0 si ´egalit´e.
Tableau des gains/pertes
Question : Trouver la strategie optimale au jeu (en supposant que l’adversaire joue
du mieux possible). Si on consid`ere une suite de parties, on cherche une strat´egie sans
m´emoire : le coup jou´e ne d´epend pas de l’historique du jeu.
Principe : Joueur 1 joue Ciseau avec la probabilit´e x , Pierre avec x et Papier avec x .1 2 3
Contraintes :
0≤ x ≤ 1i
x +x +x = 11 2 3
Son esp´erance de gain est :
– Si joueur 2 joue Ciseau : x −x2 3
– Si joueur 2 joue Pierre : x −x3 1
– Si joueur 2 joue Papier : x −x1 2
Hypoth`ese : Joueur 2 joue du mieux possible donc le gain r´ealis´e par 1 est minimal i.e.
g =min(x −x ,x −x ,x −x )2 3 3 1 1 2
But : Maximiser g.
Apparemment le probl`eme n’est pas un probl`eme de programmation lin´eaire `a cause
du min dans la d´efinition de g.
Mais on peut s’y ramener :
Max(g)
g≤x −x2 3
g≤x −x3 1
g≤x −x2 1
g≥ 0
(avec g une variable).
∗ ∗ ∗ ∗Remarque : la solution est x =x =x = 1/3 avec g = 0.
1 2 34 CHAPITRE 1. MODELISATION
1.1.3 Placement Financier
Placer 1000 euros sur 6 ans de la mani`ere optimale sachant que : la caisse d’´epargne
rapporte5%par anet immobilise lecapital unan, l’obligation1 rapporte12%`a l’´ech´eance
si on le choisit la premie`ere ann´ee sinon elle rapporte 11%, immobilise le capital deux
ans, l’obligation 2 rapporte 18% `a l’´ech´eance, immobilise le capital trois ans, l’obligation
3 rapporte 24% `a l’´ech´eance. L’obligation 2 est disponible tous les ans sauf l’ann´ee 3,
l’obligation 2 n’est pas disponible l’ann´ee 1, et l’obligation 3 n’est disponible que l’ann´ee
1.
Ecrire le probl`eme de programmation lin´eaire qui correspond au meilleur placement
possible.
Id´ee : en d´ebut d’ann´ee i on place x `a la caisse d’´epargne, y en obligation i, z eni i i
obligation z et w en obligation w.i
Achaque ann´ee on´ecrit quelle somme est disponible (toutce qui arrive `a´ech´eance avec
les int´erˆets et on la place dans ce qui est disponible. On maximise la somme obtenue `a la
fin d’ann´ee 6.
1.2 D´efinition de la PL
1.2.1 Formes canonique et standard
   
x b1 1    .   .       .c = (c ,...,c ),x = . ,b = , A= (a ) 1≤i≤ m avec c,b ,a des r´eels.1 n i,j i j i,j   
1≤j≤ n   . .   
x bn m
Forme canonique
Max z =c.x
A.x≤b
x≥ 0
Silesvariablesdoiventprendredesvaleursenti`eres,onaunprobl`emedeprogrammation
lin´eaire en nombres entiers (plus difficile)
Forme standard
Max z =c.x
A.x =b
x≥ 0
IMPORTANT:onpeut transformer la formecanonique en formestandardet vice-versa.
Onpeut aussitransformer un maxen minparmax{x| ...}) =−min{−x| ...}.Demˆeme´1.2. DEFINITION DELA PL 5
si on a un probl`eme ou il n’y a pas de contraintes x≥ 0 mais x peut ˆetre quelconque, on
peutseramener`aunprobl`emeavecdesvariables≥ 0enposantx =x −x avecx ,x ≥ 0.1 2 1 2
Une solution admissible d’un probl`eme de PL (en forme standard ou canonique) est un
vecteur x qui satisfait les contraintes.
1.2.2 R´esolution Graphique
Fabriquant d’ordinateurs : portable ou PC. le portable rapporte 750 euros, le PC 1000
euros.LePCcommeleportableutiliseunmicroprocesseur.LePCadeuxunit´esdem´emoire
de 256Mb et le portable en a une. Il faut 4 minutes d’assemblage pour un portable et 3
minutes pour un PC. On dispose de 25 milliers minutes d’assemblage de 15 milliers de
m´emoires et de 10 milliers de processeurs.
x ,x nombre de millier de portables, PC, d’`ou le probl`eme de PL :1 2
Max z = 750x +1000x1 2
x +x ≤ 101 2
x +2x ≤ 151 2
4x +3x ≤ 251 2
x ,x ≥ 01 2
Les contraintes sont d´elimit´es par les droites x +x = 10, x +2x = 15, 4x +3x = 25,1 2 1 2 1 2
x = 0 et d´efinissent un polytope. Le maximum peut se calculer en faisant glisser la droitei
d’´equation 0,75x + x = K en augmentant la valeur de K (qui correspond au profit1 2
obtenu). On trouve que le maximum est atteint par le sommet P(1,7) qui donne un profit
maximum de 7750.
R´esolution avec Eclipse
[eclipse 3]: {
Z=750*X1+1000*X2,
X1+X2=<10,
X1+2*X2=<15,
4*X1+3*X2=<25,
X1>=0,
X2>=0
},
maximize(Z).
X1 = 1
X2 = 7
Z = 7750
Yes (0.00s cpu)6 CHAPITRE 1. MODELISATION
1.3 G´eom´etrie de la PL
1.3.1 Espaces Affines et Vectoriels
nUnvecteur deR est unn-uplet der´eels. Unsous-espace vectoriel est unsous-ensemble
stable par addition et multiplication par un scalaire. Une base d’un sous-espace vectoriel
V est un ensemble finis de vecteur e ,...,e tel que1 p
(i) tout vecteur v∈V est combinaison lin´eaire des ei
(ii) une combinaison lineaire des e est nulle ssi les coefficients sont nuls.i
Un espace affine est l’ensemble des points M=N+S avec N un point particulier (un
nelement de R et S un sous-espace vectoriel. La dimension de l’espace affine est celle de
l’espace vectoriel S.
1.3.2 Polyhedres et Polytopes
Un hyperplan H est un espace affine de dimension n−1 et se d´ecrit par une ´equation
a x +...+a x =K1 1 n n
Un demi-espace ferm´e d´elimit´e par H est d´efini par
a x +...+a x ≥K1 1 n n
ou
a x +...+a x ≤K1 1 n n
Definition 1 Un polyh`edre est une intersection de demi-espaces ferm´es.
Definition 2 Un polytope est un polyh`edre born´e.
Etant donn´es un polyh`edre P,un hyperplan H etHS un demi-espace ferm´e correspon-
dant `a H, si HS∩P ⊆H, alors P ∩HS est une face de P.
Une face de dimension 0 (donc un point) est appel´e un sommet de P
Une face de dimension 1 est appel´ee une arˆete de P
Une face de dimension n−1 est appel´ee une facette de P
On admettra la proposition suivante :
Proposition 1 Un polytope P n’a qu’un nombre fini de sommets et tout point M de P
peut s’ecrire comme combinaison lin´eaire convexe des sommets M = Σ λ S (avecS sommets i ii
Σλ = 1 et λ ≥ 0 pour tout i.i i1.4. OPTIMISATION DEFONCTION CONVEXES SUR UN POLYTOPE 7
1.4 Optimisation de fonction convexes sur un poly-
tope
′Unconvexe C est un sous-ensemble de points tels que pour tout couple de points M,M
′de C, le segment MM est inclus dans C. (le segment est l’ensemble des points de la forme
′λM +(1−λ)M avec 1≥λ≥ 0.)
Exercice : montrer que l’intersection de deux convexes est un convexe puis qu’un po-
lyh`edre est un convexe.
n ′Une fonction de f :R →R est convexe ssi pour tous points M,M on a
′ ′f(λM +(1−λ)M )≤ λf(M)+(1−λ)f(M )
Une fonction est concave si -f est convexe. Une fonction lin´eaire est convexe et concave, la
2parabole x→ x est convexe. On s’interesse `a calculer le minimum d’une fonction convexe
sur un ensemble convexe, plus particuli`erement sur un polytope, ce qui est identique `a
calculer le maximum de -f sur sur le mˆeme ensemble.
Proposition 2 Une fonction convexe f sur un polytope P a un maximum et celui-ci est
obtenu sur un sommet.
Preuve : On utilise le fait que tout point du polytope est combinaison lin´eaire convexe
de