un gentil mari

evaristos · 27-08-2010 15:19:11

Bonjour à tous

Je vais d’abord répondre aux questions, puis, je donnerai une solution qui utilise les réponses, en particulier en comparant les désagréments obtenus avant et après la permutation de deux couples de données consécutifs ainsi que le suggère les questions.
Voici les questions que Luigi se pose pour satisfaire Rita et pour minimiser son travail :

1) Si j’avais à réparer 2 appareils ayant le même nombre de désagréments, quel serait l’ordre de réparation ?
2) Si j’avais à réparer 2 appareils dont les durées et les désagréments sont proportionnels, quel serait l’ordre de réparation ?
3) Si je répare 2 appareils quelconques parmi les 5 proposés, pourrais je utiliser les réponses aux questions 1) et 2) ?
4) Si je décide d’utiliser le résultat 3) de ma réflexion, puis-je le généraliser aux 2 fois 5 données de mon problème ?

Solutions
Cas de 2 appareils

1° A égalité de désagréments, Luigi choisira de commencer par réparer l’appareil de durée la plus courte, sinon il choisira indifféremment l’un ou l’autre en cas d’égalité de durées. D’ailleurs il vérifie de la façon suivante : appelons a1, b et a2, b les 2 couples . Pour comparer les désagréments, il calcule leur différences D1-D2 = a1(b+b)+ a2*b – a2(b+b)-a1*b= a1*b-a2*b = (a1-a2)b.
En conséquence, D1≤D2 <==> a1≤a2 car b>0.
2° Si les couples sont proportionnels, Luigi comprend rapidement que dans ce cas, l’ordre est indifférent. Il se dit que si l’on multiplie (ou divise) la durée par un nombre non nul , le désagrément (pour Rita) est multiplié (ou divisé) par le même nombre . Vérification immédiate: on a a1,b1 et k*a1, k*b1 pour les couples. Il calcule D1-D2= a1(b1+kb1)+k*a1*kb1- k*a1( kb1+b1)-a1*b1= 0
En Conséquence D1=D2 et Luigi a parfaitement raison de commencer par l’un ou l’autre indifféremment.
3° Le problème est : s’il prend 2 appareils, ils n’entrent pas forcement dans le cadre 1° ou 2°! Après un moment d’hésitation, il multiplie les termes des deux couples par des nombres en s’arrangeant pour que les désagréments soient identiques (1°) . Mais Luigi est lucide et sait que s’il remplace un couple par un autre dont les termes sont proportionnels, le désagrément n’est plus le même et s’interroge sur les désagréments obtenus ; Il désigne a1,b1 et a2, b2 les couples, et D1, D2 leurs désagréments avant et après permutation. Puis il calcule D1-D2 et trouve a1*b2-a2*b1.
Il désigne a1*b2,b1*b2 et a2*b1, b2*b1 les couples, et D’1,D’2 leurs désagréments avant et après permutation. Puis, il calcule D’1-D’2 et trouve b1*b2(a1*b2-a2*b1).

A ce stade de la réflexion, il est en mesure de donner un résultat clé : D1 ≤ D2 si et seulement si a1/b1≤a2/b2

a1 a2
<==>det ≤ 0
b1 b2

Cas de 5 appareils

4°Pour minimiser ses calculs, Luigi décide , à partir d’un ordre quelconque, de permuter les réparations consécutives de 2 appareils et de comparer les désagréments obtenus. Il montre que

Théorème :
quel que soit i , 0< i < 5, si Di est le désagrément d’un ordre quelconque et Di+1 celui obtenu en permutant les couples consécutifs ai,bi et ai+1, bi+1,
      ai ai+1
Di ≤Di+1 < = > ai/bi ≤ ai+1/ bi+1 <== > det ≤ 0
   bi bi+1
Pour cela il n’a que 4 différences Di – Di+1 à calculer à partir de D1 , en permutant successivement les indices 1 et 2, 2 et 3 , 3 et 4 , et enfin 4 et 5 .(calculs sans problèmes)
Il peut ainsi définir l’ordre optimal des réparations et démontrer que tout autre ordre implique un désagrément supérieur sans calculer les 5 ! ordres. Ce qui l’amène à la solution en partant d’un ordre quelconque

Preuve : Ordonnons dans l’ordre croissant les quotients ak/bk et appelons :
t1 t2 t3 t4 t5
d1 d2 d3 d4 d5 la suite ordonnée des couples obtenus.

Appelons Dm le désagrément correspondant.

Montrons que Dm = min E, E désignant l’ensemble des désagréments

En effet, pour un ordre des (ak, bk) le total des désagréments D1 = Dm
   ai    ai+1
si et seulement si tous les déterminants    bi       bi+1 sont négatifs.

Sinon, si l’ un au moins de ces déterminants est strictement positif, en permutant les deux colonnes,
le désagrément obtenu D2 < D1 d’après le théorème.
On réitère une permutation si l’on a un autre déterminant strictement positif et on obtient D3 < D2 < D1.
Après un nombre fini de L permutations, on obtient :
Dm =DL< D(L-1) < D(L-2) < …< D3< D2 < D1.

C.Q.F.D.
En conclusion, il suffit simplement d’ordonner les 5 quotients ak/bk dans l’ordre croissant

Ce qui donne pour le cas particulier :

3 2 5 4 6
+ - + - D1= 287 + et – désignant le signe de chaque déterminant consécutif.
2 3 4 9 5

Pour illustrer la démonstration,
on permute de gauche à droite SUCCESSIVEMENT LES COUPLES dont le déterminant est strictement positif:

2 3 5 4 6
- + + - D2= 282
3 2 4 9 5

puis

2 5 3 4 6
- - + - D3=280
3 4 2 9 5

2 5 4 3 6
- + - + D4=261
3 4 9 2 5

2 4 5 3 6
+ - - + D5=232
3 9 4 2 5

4 2 5 3 6
- - - + D6 = 226
9 3 4 2 5

4 2 5 6 3
- - + - D7 = 223
9 3 4 5 2

4 2 6 5 3
- - - - D8=Dm = 222 (fin)
9 3 5 4 2

Le bon ordre : O,LV,TV,LL,F désagrément 222
Remarques : l’ordre le plus mauvais (décroissant) est F,LL,TV,LV,O et correspond à un désagrément de 336. La méthode obtient le résultat sans passer par un tri préalable

A+

Dernière modification par evaristos (27-08-2010 15:36:24)

freddy · 27-08-2010 17:31:55

Salut !

... c'est pourquoi Rita partit avec freddy, surnommé "l'homme qui réparait plous vite que son hombre" ! :-)))

thadrien · 30-08-2010 19:47:21

freddy a écrit :

Certes, certes. Toutefois, je me permets d'insister : j'aimerais bien que tu montres concrètement comment on fait pour résoudre le problème avec cet algorithme.
Tu auras remarqué qu'en général, ceux qui répondent aux demandes d'aide expliquent pas à pas et parfois avec force détail comment il faut faire pour arriver à la solution d'un problème.
C'est ce qu'on vient chercher : le pourquoi du comment des choses et quand quelqu'un sait dire pourquoi, il rend un grand service à ceux qui l'ignoraient jusque là.
Ton explication détaillée devrait contribuer à maintenir, voire embellir, l'aura pédagogique du site.
Qu'en penses tu ?

En fait, j'ai tout simplement pas eu le temps de donner plus de détails. Dès que j'ai du temps, je poste une solution utilisant les graphes. Elle est pas aussi performante que l'autre, mais je le fais pour l'honneur de l'esprit humain.

thadrien · 31-08-2010 20:00:05

Plus de détails sur l'application de Dijkstra à ce problème ici : http://dl.dropbox.com/u/10307619/Applic … jkstra.pdf

freddy · 31-08-2010 22:06:18

Salut,

si on pouvait avoir un brin d'explication, je serais preneur.

Merci si tu peux.

Freddy

freddy · 31-08-2010 23:43:30

Re,

OK, je crois que j'ai compris. Intéressant.

Mais bigre, faut pas être pressé ...

Merci.

Forum de mathématiques - Bibm@th.net

#26 27-08-2010 15:19:11

Re : un gentil mari

#27 27-08-2010 17:31:55

Re : un gentil mari

#28 30-08-2010 19:47:21

Re : un gentil mari

#29 31-08-2010 20:00:05

Re : un gentil mari

#30 31-08-2010 22:06:18

Re : un gentil mari

#31 31-08-2010 23:43:30

Re : un gentil mari

Pied de page des forums