un gentil mari

evaristos · 17-08-2010 16:13:28

Bonjour à tous

Le gentil mari

Suite à un incident imprévu, la famille Bottalico a vu tomber en panne en même temps le four, le lave-vaisselle, la TV , le lave linge et l’ordinateur. Heureusement le mari, Luigi peut réparer très vite tous les appareils électroménagers, mais il se trouve face à un dilemme : dans quel ordre devra t-il procéder aux réparations pour contenter sa femme, Rita ?

Si l’on suppose qu'on peut quantifier le désagrément de Rita (du fait de ne pas pouvoir utiliser les appareils) selon le tableau suivant :

   Four Lave-vaisselle Lave-linge Ordinateur TV
Nombre d’heures pour la réparation    3    2    5    4    6
Désagréments pour chaque heure    2    3    4    9    5
de non utilisation

Dans quel ordre Luigi devra-t-il réparer les 5 appareils de façon à minimiser le désagrément global de sa douce moitié ?
(attention, pas question de commencer un appareil avant d'avoir terminé le précédent)

Traduit de l'italien

PS : Le problème consiste en général à rechercher un algorithme permettant à un ordinateur d’optimiser les calculs. Pouvez vous en trouver un ?

Bon courage

Evaristos

Dernière modification par evaristos (17-08-2010 16:19:29)

nerosson · 17-08-2010 16:49:11

Salut, Evaristos,

Juste une idée en l'air, comme ça :

J'attribue à chaque appareil un coefficient obtenu par le produit du temps de réparation multiplié par l'intensité du désagrément. Ensuite je répare les appareils en commençant par le plus grand coefficient :
Ordinateur : 36.
T.V. : 30
Lave-linge : 20
Four et lave-vaisselle (au choix) : 6

Bien entendu, il peut y avoir d'autres facteurs qui interviennent : si j'ai pas de chemise propre, je commence par le lave-linge.

Dernière modification par nerosson (17-08-2010 16:54:58)

thadrien · 17-08-2010 17:48:31

Salut,

C'est un problème similaire à celui du Knapsack. Je crois que l'on peut montrer qu'il est NP-complet.

nerosson · 17-08-2010 19:47:03

Salut, Thadrien,

Ton intervention n 'a pas été inutile : je suis allé demander à Google ce que c'était qu'un Knapsack et j'ai ainsi enrichi mes connaissances !

L'ennui, c'est que ça ne va pas être facile à placer dans la conversation !

freddy · 17-08-2010 22:09:53

Salut nerosson,

si tu as bien lu, tu auras compris que ta réponse est inexacte.

En effet, si le début est bon (ORDI puis TV puis LL), la suite est moins efficace : il faut continuer par LV et terminer par FO.

Dans ce cas, le désagrément total = 237, et si on permutte FO par LV, on grimpe à 242, ce que Rita ne va pas aimer.

Pour autant, ne peut on faire mieux ???

Réponse : NON

Snif, yoshi ne pourra pas te féliciter chaleureusement ...

Dernière modification par freddy (17-08-2010 23:09:06)

freddy · 18-08-2010 08:47:19

Re,

en effet, il ne suffit pas de considérer le temps de réparation fois le désagrément durant ce temps, mais aussi le désagrément durant ce même temps lié à la non utilisation des autres appareils non encore réparés.

Le pb n'était pas assez compliqué et l'intuition géniale de nerosson a fait le reste, mais dans une autre situation ...

NP-complet c'est pour dire "Ni Pute Ni Soumise en complet-veston" ? ;-)

Dernière modification par freddy (18-08-2010 08:53:04)

nerosson · 18-08-2010 18:49:56

Salut, Freddy,

Je suis obligé de reconnaître : j'ai pris le désagrément appareil par appareil alors qu'il fallait le prendre globalement.

Mais j'ai tout de même droit aux circonstances atténuantes : J'ai bien dit que c'était une idée en l'air, une réaction instantanée, un peu à la légère.

Il reste que c'est toi qui a raison.

freddy · 18-08-2010 22:21:39

Salut mon ami !

Il doit faire au moins très beau soleil à minuit en Haute Savoie pour que tu ne contestes pas un peu ;-)))

evaristos · 18-08-2010 23:16:30

Bonjour

Je pense qu’il ne faut pas s’égarer dans des considérations qui n’entrent pas dans le cadre de la rubrique de ce forum. Mes connaissances en maths sont trop élémentaires et le problème proposé fait appel au programme de 1ère d’autres temps…et à des notions actuelles de TS en ce qui concerne la formulation mathématique sous forme de sommes indiciées ou de Maths sup, les programmes ayant été allégés depuis la construction de l’Europe ( c’est mon analyse…).

Cela dit, j’ai compris qu’un problème NP-complet, signifie qu'il n'existe pas de méthode générale connue pour construire une solution optimale. Or dans le problème du « gentil mari », il y a , quelles que soient les données et le nombre (fini) de données, une solution sinon Rita divorcerait !
Donc pas de théorie complexe mais des mathématiques « élémentaires » en ce qui concerne le problème numérique. Seule sa généralisation et la découverte d’un « algorithme » à 2 fois n données est délicate à démontrer (pour moi en tout cas)
Pour les curieux pas trop matheux, je pourrai les aider le cas échéant mais une intervention rationnelle de Freddy peut mettre les indécis sur la bonne voie.

Bonne réflexion

Evaristos

freddy · 19-08-2010 11:19:35

Salut,

si on appelle [tex]T_i[/tex] le temps de réparation de la machine i=1 à 5, [tex]D_i[/tex] l'intensité du désagrément horaire d'indisponibilité et [tex]DT=\sum_{i=1}^5 D_iT_i[/tex] le désagrément total de Sainte Rita (oui, car il faut être une sainte pour supporter Luigi ...), le pb se pose de la manière suivante :

[tex]\begin{cases}DT_1= T_1\times (D_1+ D_2+ D_3+D_4+D_5) \\ DT_2=T_2\times (D_2+ D_3+D_4+D_5) \\ DT_3=T_3\times (D_3+D_4+D_5) \\ DT_4=T_4\times (D_4+D_5) \\DT_5=T_5\times (D_5) \end{cases}[/tex]

Il faut trouver la combinaison (l'ordre des réparations) qui minimise la quantité [tex]DT=\sum_{i=1}^5T_i\times \left(\sum_{j=i}^5D_j\right)=\sum_{k=1}^5D_k\times \left(\sum_{l=1}^kT_l\right)[/tex]

Cela relève, si j'ai bien vu, de la programmation dynamique avec intervention du principe de Bellman : on déroule tout l'arbre de décision possible puis on descend de l'arbre en sélectionnant à chaque étape la meilleure décision (celle qui donne la meilleure conséquence possible possible en fonction de l'objectif). Cf Livre de Luce et Raïffa en français publié en 1972 (s'il est toujours disponible).

L'idée est que la bonne décision initiale est telle que chaque conséquence conduit à prendre la bonne décision suivante qui conduit à la bonne décision suivante, sachant qu'à chaque nœud de l'arbre, c'est la nature (ou le hasard) qui décide (et donc nous branche sur une jonction imprévue au départ).

Dans le problème ci dessus, il n'y a pas de hasard, mais simplement un ordonnancement à trouver pour que Rita soit la moins irritée possible (il faut ménager l'ire de Rita qui irrite Luigi).

En regardant d'un peu plus près le système d'équations ci dessus, on "voit" vite qu'il faut réparer les machines par ordre d'irritabilité décroissante, pour éviter que les grosses valeurs ne se répètent trop souvent.

Une vraie recherches sur un problème plus ardu aurait nécessité de mettre en place une procédure de calcul combinatoire (faire toutes les évaluations possibles, soit 5!=120, pour trouver la plus petite valeur => le bon ordre recherché) qui doit rendre le problème très rapidement lourd à résoudre.

Merci l'ami de m'avoir permis de renouer avec d'anciennes amours.

Bb

Dernière modification par freddy (19-08-2010 23:20:24)

thadrien · 19-08-2010 11:47:03

evaristos a écrit :

Cela dit, j’ai compris qu’un problème NP-complet, signifie qu'il n'existe pas de méthode générale connue pour construire une solution optimale. Or dans le problème du « gentil mari », il y a , quelles que soient les données et le nombre (fini) de données, une solution sinon Rita divorcerait !

Ce n'est pas exactement ça. Un problème P est NP-complet si :

* Une solution potentielle de P puisse être vérifiée en un temps polynomial.
* Tout problème Q peut se ramener à P en un temps polynomial.

@freddy : comme tu le dis, on peut résoudre ce problème avec l'algorithme de Bellman ou, mieux, de Dijkstra.

freddy · 19-08-2010 17:12:50

lRe,

bon, maintenant, regarde bien : je vais faire comme Bellman l'a démontrer, c'est à dire commencer par la fin !

Donc, quelle est la dernière machine qui induit le plus petit désagrément : c'est soit le four (6) soit le lave vaisselle (6).

Supposons que je finisse avec le four. Quelle est alors l'avant dernière machine à réparer qui génère le plus petit désagrément : le lave vaisselle, qui engendre 2*(3+2)=10.

Si j'avais choisi en dernier le lave vaisselle, alors le four engendre 3*(3+2)=15 d'irritabilité, à exclure !

Ensuite; cherchons la troisième machine à réparer, sachant que continuerai pas le lave vaisselle puis le four :

j'ai le choix avec :

le lave linge : 5*(4+3+2)=45 ou bien

l'ordinateur : 4*(9+3+2) = 64 ou bien

la TV : 6*(5+3+2)=60.

Donc il faut prendre le lave linge.

Ensuite, on voit bien qu'il faut réparer en second l'ordinateur (car [tex]6\times (5+4+3+2) > 4\times (9+4+3+2)[/tex] )et en premier la TV sauf que je réalise qu'à ce stade, le choix est sous optimal : je peux faire mieux en commençant par l'ordinateur et continuant par la TV.

Je vois bien ici comment j'ai obtenu de proche en proche la bonne stratégie, sans me coltiner les 120 cas possibles !

Dernière modification par freddy (19-08-2010 23:19:44)

freddy · 19-08-2010 17:41:34

Re,

je propose le sujet suivant, modifiant le sujet pour rendre le critère de nerosson inopérant et mieux refléter l'ire de Rita la ménagère de moins de 50 ans qui a la décision d'achat dans le couple :

(machine, durée, indice de courroux horaire)

TV 2 15

LL 5 6

LV 10 3

ORDI 6 5

FOUR 2,5 12

Je n'ai pas encore la solution, j'espère ne pas faire un four !

freddy · 20-08-2010 13:07:46

Re,

Si on veut exprimer ce problème formellement, voilà comment faire.

Soient [tex]E=\{1,\,2,\,3,\,4,\,5\}[/tex] et [tex]\sigma(E)[/tex] l'ensemble des permutations circulaires de E.

On cherche à résoudre le programme suivant :

[tex]\text{trouver}\;p* \in \sigma(E)\;:\;\forall p\in \sigma(E),\;DT(p*) \leq DT(p)[/tex]

Remarque : j'ai mis plus de temps à écrire cette formalisation qu'à trouver la solution !

Dernière modification par freddy (20-08-2010 13:08:26)

evaristos · 22-08-2010 00:35:35

Bonjour à tous

J’ai bien aimé la démonstration de Freddy car je n’ai pas étudié les problèmes d’optimisation. Voici une autre approche de ce problème.

Luigi, n’ayant pas fait d’études supérieures de Mathématiques, n’a pas de notion de graphes et bien sûr les algorithmes lui sont étrangers .
Voici les questions qu’il 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 ? Je m’adresserai pour la justification à l’un de mes enfants qui a une bonne formation secondaire en mathématiques.

Et vous, pouvez vous répondre à ces 4 questions ?

Oui, je sais que vous pouvez et même à la question 4 plus délicate en utilisant le mot clé de ce problème : l’ordre et en lisant les interventions de Freddy sur le sujet
( Son allusion à un algorithme de Bellman n’est pas nécessaire) .

Bonne réflexion

Evaristos

evaristos · 22-08-2010 15:18:20

freddy a écrit :

lRe,
bon, maintenant, regarde bien : je vais faire comme Bellman l'a démontrer, c'est à dire commencer par la fin !
Donc, quelle est la dernière machine qui induit le plus petit désagrément : c'est soit le four (6) soit le lave vaisselle (6).
Supposons que je finisse avec le four. Quelle est alors l'avant dernière machine à réparer qui génère le plus petit désagrément : le lave vaisselle, qui engendre 2*(3+2)=10.
Si j'avais choisi en dernier le lave vaisselle, alors le four engendre 3*(3+2)=15 d'irritabilité, à exclure !
Ensuite; cherchons la troisième machine à réparer, sachant que continuerai pas le lave vaisselle puis le four :
j'ai le choix avec :
le lave linge : 5*(4+3+2)=45 ou bien
l'ordinateur : 4*(9+3+2) = 64 ou bien
la TV : 6*(5+3+2)=60.
Donc il faut prendre le lave linge.
Ensuite, on voit bien qu'il faut réparer en second l'ordinateur (car [tex]6\times (5+4+3+2) > 4\times (9+4+3+2)[/tex] )et en premier la TV sauf que je réalise qu'à ce stade, le choix est sous optimal : je peux faire mieux en commençant par l'ordinateur et continuant par la TV.
Je vois bien ici comment j'ai obtenu de proche en proche la bonne stratégie, sans me coltiner les 120 cas possibles !

Salut Freddy

Je vois que tu as très bien posé le problème et même commencé sa résolution. Tes remarques pertinentes permettent de progressser dans l'analyse et d'aboutir à une méthode de résolution (je ne parle pas du principe de Bellman que je ne connais pas mais qui a ouvert ma curiosité)
Sauf erreur de ma part , tu as trouvé l'ordre O,TV,LL,LV,F qui engendre un désagrément de 237.
J'en ai un : LV,O,LL,F,TV qui vaut 232.

Par ailleurs, connaissant le problème, je n'ai aucune difficulté à répondre à celui que tu as proposé

Bye

Evaristos

freddy · 23-08-2010 13:46:51

Salut evaristos,

tu as tout à fait raison, je n'ai pas pris le temps de bien vérifier que la solution était la bonne.

En fait, Bellman ne sert à rien car le hasard est absent !

De plus, j'ai regardé le pb du sac à dos (KP), et il faut faire tout les calculs associés pour trouver la bonne solution. Et je puis te dire qu'on en était loin !

La bonne et unique solution est l'ordre suivant :

ORDI, LV, TV, LL, FO (indice minimum 222) ! ...

Bb

Dernière modification par freddy (23-08-2010 14:24:37)

freddy · 23-08-2010 17:18:50

Evaristos mon ami, Luigi est un sage, un vrai !

regarde voir : si on a deux appareils, alors

[tex] T_1\times (D_1+D_2)+T_2\times D_2 \leq T_2\times (D_1+D_2)+T_1\times D_1 <=>\frac{T_1}{D_1} \leq \frac{T_2}{D_2}[/tex]

En classant les 5 appareils du plus petit au plus grand selon ce critère, on trouve la bonne réponse ...

Idem dans le second pb que j'ai posé.

je ne sais pas si on peut généraliser ...

PS : on peut dans ce cadre là, par récurrence. Donc grand et sage est Luigi !

je m'explique : supposons que l'on ait :

[tex] \frac{T_1}{D_1} \leq \frac{T_2}{D_2} \leq \ ... \leq \frac{T_n}{D_n}[/tex]

alors on montre assez facilement (par addition successive) que le rangement dans cet ordre donne la plus petite valeur possible de tous les ordres de rangement réalisables.

Dernière modification par freddy (23-08-2010 18:37:32)

thadrien · 23-08-2010 21:32:16

Salut,

@freddy : si tu n'as pas trouvé la bonne solution, c'est que tu n'as pas appliqué comme il fallait l'algorithme de Bellman. Il faut à chaque fois développer le plus petit chemin de l'ensemble des chemins possibles à chaque étape.

Cependant, la dernière solution est plus astucieuse, et bien plus rapide que l'algorithme de Bellman.

Dernière modification par thadrien (23-08-2010 21:33:14)

freddy · 23-08-2010 23:24:33

Salut,

eh bien mon cher thadrien, je te laisse me montrer comment il faut faire !

Allez, au travail, stp, tu m'obligeras.

evaristos · 24-08-2010 19:46:14

bonjour à tous

Freddy a écrit:"En classant les 5 appareils du plus petit au plus grand selon ce critère, on trouve la bonne réponse ..."

Il faudrait montrer que ce qui est valable pour 2 appareils, l'est également pour 5.

C'est-à dire démontrer que tout ordre différent de sa réponse implique un désagrément supérieur.

Quand à la généralisation par récurrence, c'est possible à condition de montrer le même théorème pour n à la place de 5.

Maintenant, il y a certainement d'autres méthodes.

Bye

Evaristos

freddy · 24-08-2010 23:21:22

'lut !

Je rappelle la règle de gestion :

[tex] T_1\times (D_1+D_2)+T_2\times D_2 \leq T_2\times (D_1+D_2)+T_1\times D_1 <=>\frac{T_1}{D_1} \leq \frac{T_2}{D_2}[/tex]

En classant les 5 appareils du plus petit au plus grand selon ce critère, on trouve la bonne réponse ...

En effet, on a dans le premier sujet :

FOUR = 1,5, LV = 0,67, LL = 1,25, ORDI = 0,44, TV = 1,20 => Ordre de réparation : ORDI, LV, TV, LL et FOUR.

Dans celui que j'ai modifié, on a :

FOUR = 0,21, LV = 3,33, LL = 0,83, ORDI = 1,20, TV = 0,13 => Ordre de réparation : TV, FOUR, LL, ORDI et LV (valeur indice 395).

Je prouve.

Supposons que l'on ait :

[tex] \frac{T_1}{D_1} \leq \frac{T_2}{D_2} \leq \ ... \leq \frac{T_n}{D_n}[/tex]

On sait alors qu'on commence par 1 et on continue par 2. Ensuite, on poursuit par 3 :

[tex] T_1\times (D_1+D_2+D_3)+T_2\times (D_2+D_3)+T_3\times D_3 \leq T_1\times (D_1+D_2+D_3)+T_3\times (D_2+D_3)+T_2\times D_2\;\text{puisque}\;T_2\times D_3\leq T_3\times D_2\[/tex] par hypothèse.

De la même manière, on continue par 4, puis 5, und so weiter !

J'espère avoir été clair. Quant à Bellman, je persiste et signe : inapplicable dans le cas d'espèce.

Bis bald

Dernière modification par freddy (25-08-2010 16:26:39)

thadrien · 25-08-2010 12:00:43

freddy a écrit :

Salut,
eh bien mon cher thadrien, je te laisse me montrer comment il faut faire !
Allez, au travail, stp, tu m'obligeras.

Tu fais un graphe dont les sommets sont les appareils en panne, les arêtes les réparations d'un seul objet et la longueur des arêtes le désagrément durant la réparation : temps de réparation de l'appareil x désagrément causé par les appareils en panne.

Trouver la solution optimale au problème revient à trouver le plus court chemin dans ce graphe. Pour cela, les algorithmes de Bellman et de Dijkstra sont tous deux très efficaces. (Dijkstra est applicable car les poids sont positifs)

Maintenant, pour la démonstration des algorithmes en eux-mêmes, je te laisse poser la question à Bellman et Dijkstra en personne. Comme les deux sont morts, il te faudra ressortir les outils habituels pour ce genre de communications téléphoniques et prévoir de l'argent (ce n'est pas une communication locale car, en France, c'est l'enfer, donc ce sera plus cher).

freddy · 25-08-2010 15:19:47

thadrien a écrit :

Tu fais un graphe dont les sommets sont les appareils en panne, les arêtes les réparations d'un seul objet et la longueur des arêtes le désagrément durant la réparation : temps de réparation de l'appareil x désagrément causé par les appareils en panne.
Trouver la solution optimale au problème revient à trouver le plus court chemin dans ce graphe. Pour cela, les algorithmes de Bellman et de Dijkstra sont tous deux très efficaces. (Dijkstra est applicable car les poids sont positifs).

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 ?

marin marais · 25-08-2010 16:23:02

Bonjour !

Ce problème ressemble à ceux qu'on rencontre en programmation linéaire... Dès que j'ai un peu de temps, je tenterai la méthode du simplexe. D'après ce que j'ai pu lire dans les posts précédents, ça a l'air d'être proche de la méthode de Bellman que je ne connais pas.

A+,
Thomas.

Forum de mathématiques - Bibm@th.net

#1 17-08-2010 16:13:28

un gentil mari

#2 17-08-2010 16:49:11

Re : un gentil mari

#3 17-08-2010 17:48:31

Re : un gentil mari

#4 17-08-2010 19:47:03

Re : un gentil mari

#5 17-08-2010 22:09:53

Re : un gentil mari

#6 18-08-2010 08:47:19

Re : un gentil mari

#7 18-08-2010 18:49:56

Re : un gentil mari

#8 18-08-2010 22:21:39

Re : un gentil mari

#9 18-08-2010 23:16:30

Re : un gentil mari

#10 19-08-2010 11:19:35

Re : un gentil mari

#11 19-08-2010 11:47:03

Re : un gentil mari

#12 19-08-2010 17:12:50

Re : un gentil mari

#13 19-08-2010 17:41:34

Re : un gentil mari

#14 20-08-2010 13:07:46

Re : un gentil mari

#15 22-08-2010 00:35:35

Re : un gentil mari

#16 22-08-2010 15:18:20

Re : un gentil mari

#17 23-08-2010 13:46:51

Re : un gentil mari

#18 23-08-2010 17:18:50

Re : un gentil mari

#19 23-08-2010 21:32:16

Re : un gentil mari

#20 23-08-2010 23:24:33

Re : un gentil mari

#21 24-08-2010 19:46:14

Re : un gentil mari

#22 24-08-2010 23:21:22

Re : un gentil mari

#23 25-08-2010 12:00:43

Re : un gentil mari

#24 25-08-2010 15:19:47

Re : un gentil mari

#25 25-08-2010 16:23:02

Re : un gentil mari

Pied de page des forums