Discussion :

[ol9245]

Bonjour à tous,

voilà mon problème du jour.

J'ai N tuyaux à connecter dans N pots. Chaque connexion du tuyau i dans le pot j est qualifiée par un nombre de 0 à 1, de mauvaise (0) à bonne (1).

Une fois mes N connexions faites, il y e a une pire que les autres : c'est le maillon faible du système.

Je veux optimiser mon système pour que son maillon faible soit le plus fort possible.

Ma question : ce problème correspond-il à (ou est-il voisin d') un problème connu de recherche opérationnelle dont je pourrais chercher et transcrire l'algorithme ?

merci

[pseudocode]

Comme ça, sans réfléchir (comme toujours :aie), je dirais : Maximum flow

[Biribibi]

Bonjour,

Il semblerait que ce problème soit connu sous le nom "min-max matching problem",
c'est à dire trouver un couplage parfait dans un graphe biparti qui maximise le poids minimal de l'ensemble des arêtes du couplage.

On peut trouver un algorithme polynomial dans le livre
Combinatorial Optimization: Networks and Matroids de Lawler
[ame="http://www.amazon.com/Combinatorial-Optimization-Networks-Eugene-Lawler/dp/0486414531"]Amazon.com: Combinatorial Optimization: Networks and Matroids (9780486414539): Eugene Lawler: Books@@AMEPARAM@@http://ecx.images-amazon.com/images/I/41FXBR6QPML.@@AMEPARAM@@41FXBR6QPML[/ame]

Malheureusement, je n'ai pas accès à ce livre.

Sinon un algorithme un peu naïf mais néanmoins polynomial est le suivant.

Je représente le problème par un graphe G = (A union B, E)
où A est l'ensemble des pots, B l'ensemble des tuyaux et E l'ensemble des arêtes entre A et B, c'est à dire l'ensemble des bonnes connexions.
On a aussi une fonction de poids w sur les arêtes E.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
tant qu'il existe un couplage parfait dans G
      C <- un couplage parfait de G
      retirer l'arête de plus faible poids dans G
fin tant que
renvoyer C

[ol9245]

@pseudocode : je vois pas bien comment transcrire mon problème en optimisation de flux. J'ai un problème multi-source, multi-puits et ce n'est pas le flux total que je veux maximiser, mais seulement celui de sa branche la plus faible.

@biribibi : J'ai pas tout compris !
je ne veux connecter que 1 seul trou à 1 seul bidon.
je peux commencer par une connexion non optimale (mais proche) puis rentrer dans une boucle d'optimisation.

Dans ce cas, si je débranche une arête, je dois reconnecter le trou et le bidon d'une autre manière.

sinon, je peux aussi commencer par tout connecter, puis déconnecter le pire de tous, tant que tous les bidons sont connectés et tous les trous aussi. C'est ça que tu veux dire ? Ca converge vers l'optimum ?

dans ce cas ça ferait qq chose comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
Matrice Cout de dimension (Trou, Bidon)
convention : 
Cout(t,b) réel : il y a connexion entre t et b et la matrice donne le cout.
cout (t,b) infini : il n'y a pas de connexion
 
calculer tous les couts
 
tant que (au moins un réel dans chaque ligne et dans chaque colonne)
    chercher le pire des couts parmi ceux qui ne sont pas seuls ni en ligne ni en colonne
    le supprimer
fin boucle
 
retourner la matrice Cout