Contenu du sommaire : Recherche opérationnelle et aide à la décision

Il est classique de présenter l'histoire de la Recherche Opérationnelle (RO) comme faisant apparaître une «crise» au cours des années 1970 et 1980, cette crise faisant suite à l'«âge d'or» des années 1950 et 1960. Cet article se propose de revenir sur cette crise. Nous nous efforcerons de montrer que sa réalité même est problématique et que les raisons avancées, à l'époque, pour tenter de l'expliquer reposent essentiellement sur des malentendus. On proposera ensuite quelques pistes que nous croyons utiles pour aborder l'histoire de la RO sous un jour nouveau et, nous l'espérons, préparer son avenir.

Doignon et Fiorini (2003) déterminent toutes les facettes du polytope du vote approbatoire. Ils livrent ainsi une caractérisation d'un modèle probabiliste dû à Falmagne et Regenwetter (1996) : le modèle sous indépendance de taille pour le vote approbatoire. Le présent texte est un complément. Il donne d'abord une preuve alternative du résultat central, plus directe mais aussi constructive. L'interprétation combinatoire des facettes du polytope du vote approbatoire est ensuite étudiée. Enfin, une description linéaire du polytope est obtenue dans le cas où le nombre d'alternatives vaut 6.

Dans cet article, nous étudions et comparons des méthodes de partitionnement d'un ensemble d'éléments muni d'une distance, méthodes qui opèrent à partir de cette seule donnée. On cherche à construire une partition à nombre de classes fixé qui optimise un critère (séparation, diamètre ou inertie). Les méthodes étudiées fonctionnent sur le même principe : le nombre maximum de classes étant fixé, on construit une partition pour chaque valeur du nombre de classes variant de 2 au maximum. Tous les critères étudiés conduisent à des problèmes d'optimisation NP-difficiles. L'algorithme général combine des méthodes de descente et des métaheuristiques pour construire des partitions sous-optimales. Plusieurs façons d'évaluer la qualité des classes et de comparer ces partitions sont proposées ; elles sont indépendantes du critère optimisé et des cardinaux des classes. Elles permettent de choisir la partition la plus compatible avec une distance donnée. Par simulation de plusieurs types de distance (euclidienne, booléenne, ou distance d'arbre) on étudie les critères qui donnent en moyenne les meilleurs résultats.

Dans cet article, nous présentons des conditions suffisantes de monotonie d'une procédure de rangement obtenue par itération d'une procédure de choix. En se plaçant dans le cadre de l'agrégation des préférences individuelles, nous introduisons la notion de monotonie et présentons des résultats utilisant les propriétés de rationalisation et de stabilité des procédures de choix. Après avoir montré que ces résultats ne couvraient pas l'ensemble des procédures itératives de rangement monotones, nous introduisons de nouveaux résultats basés cette fois sur la notion de respect d'un score monotone. Ces résultats sont ensuite mis en application dans la dernière section pour prouver la monotonie de différentes procédures de rangement.

Dans ce travail, nous étudions les problèmes classiques d'agrégations de préférences. Nous proposons une suite aux travaux de J.M. Blin [5]. Sous certaines hypothèses, Blin ramenait le problème d'agrégation de préférences à celui de la recherche de la matrice de permutation la plus proche d'une matrice bistochastique (dite normalisée de la matrice d'agrément du problème, qui agrège les informations contenues dans les préférences individuelles exprimées). En affaiblissant ces hypothèses (notamment celles de préférences strictes qui doivent porter sur l'ensemble des candidats), nous proposons un schéma à deux phases pour résoudre le problème. La première phase consiste à approcher la matrice contenant les informations des préférences exprimées (qui n'est plus bistochastique) par une matrice bistochastique grâce à un algorithme mis au point par l'auteur [20]. On se ramène alors au même problème que celui considéré par Blin et qui peut être résolu par programmation linéaire ou plus simplement comme un problème de mariages dans un graphe bipartite pondéré (weighted bipartite matching problem, en anglais).