Dans un contexte de préférences non classiques (pouvant présenter des intransitivités et incomplétu­des, voire des circuits), les problèmes combinatoires de recherche d'une solution préférée sont semi-structurés. Leur résolution s'effectue généralement grâce à des interactions entre le Système Interactif d'Aide à la Décision (SIAD) et les décideurs selon un processus de décision. En proposant des algorithmes de résolution de problèmes connexes pertinents entièrement automatisables, le SIAD aide à obtenir des éléments de réponses aux questions que se pose un intervenant dans un processus de décision. Nous introduisons un tout nouveau type de SIAD, proposant des problèmes automatisables pertinents basés sur la déduction et le choix : les problèmes de consistance qualitative. Ainsi, nous présentons un algorithme glouton de consistance qualitative dans le cadre du problème d'arbre couvrant maximal basé sur une version ordinale de l'algorithme de Kruskal. Utilisés dans un processus itératif interactif, ce type de problèmes ne permet pas toujours d'aboutir à une solution maximale pour l'instance initiale. Le processus décisionnel est dit non pleinement rationnel. Pour y remédier, nous identifions algorithmiquement les arêtes critiques (présentes dans toute solution du sous-ensemble maximal courant). Enfin, nous fournissons des conditions nécessaires sur les préférences, en nous aidant des travaux en théorie du choix rationnel, pour que le processus conserve cette rationalité procédurale.