Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

proba td13 L ?? Probabilités ?? - Guillaume Aupy ?? Vincent Neiger TD n Markov Polov Exercice - Analyse simpli ?ée de l ? algorithme du simplexe L ? algorithme du simplexe résout le programme linéaire min cx Ax b x ? o? b est de taille m et o? c et x sont

L ?? Probabilités ?? - Guillaume Aupy ?? Vincent Neiger TD n Markov Polov Exercice - Analyse simpli ?ée de l ? algorithme du simplexe L ? algorithme du simplexe résout le programme linéaire min cx Ax b x ? o? b est de taille m et o? c et x sont de taille n m Les solutions x sont des points extrêmes du domaine avec n ?? m composantes nulles L ? algorithme du simplexe passe d ? un point extrême à un autre meilleur en terme de la fonction objective Il y a N n m points extrêmes si bien qu ? on s ? attend à un nombre d ? itérations exponentiel On modélise le passage de l ? algorithme d ? un point extrême à un autre à l ? aide d ? une cha? ne de Markov On suppose que si on se trouve au j-ème meilleur point après l ? itération on se trouvera à l ? un des j ?? -èmes meilleurs points de manière équiprobable En d ? autre termes on a une matrice de transition P de taille N avec P et Pij i ?? pour i et ? j ? i ?? Soit Ti le nombre d ? itérations pour aller de l ? état i à l ? état Donner une formule liant E Ti et les E Tj pour j i Calculer E TN Donner une estimation de E TN Donner une estimation de E TN et en déduire que pour une certaine constante c on a pour N su ?samment grand P TN log N c log N Calculer V ar TN en écrivant TN comme une somme de variables indépendantes il faut trouver les variables et montrer l ? indépendance Donner une estimation de V ar TN et en déduire que pour une certaine constante c on a pour N su ?samment grand P TN log N c log N log N Que peut-on en déduire pour l ? algorithme du simplexe Exercice - Installateur d ? ascenseurs Un installateur d ? ascenseurs dispose d ? une seule équipe dont tous les membres travaillent sur le même chantier Les demandes d ? installations des clients qui lui parviennent peuvent être réparties en classes ?? travaux de moyenne importance durant une semaine désignés par A CL ?? Probabilités ?? - Guillaume Aupy ?? Vincent Neiger ?? travaux plus importants durant semaines désignés par B L ? installateur ne reçoit pas de demandes de travaux qui n ? entrent pas dans cette classi ?cation Il n ? y a pas de liste d ? attente Les demandes d ? installation parviennent à l ? entrepreneur au début de chaque semaine Une observation statistique a montré que les probabilités pour recevoir un lundi donné au moins une demande de travaux du type A ou au moins une demande de travaux du type B valent respectivement p et q Ces probabilités sont indépendantes Certaines semaines des travaux sont refusés l