Le problème de construire un horaire acceptable pour les infirmières d'un grand hôpital est extrêmement difficile à résoudre. Il ne s'agira donc pas ici de présenter les différentes méthodes qui sont utilisées. Cela dit, afin d'illustrer comment la mathématique peut intervenir dans de telles questions, nous avons construit une situation qui, bien qu'artificielle, nous servira très bien.

Imaginons donc un tout petit hôpital dans lequel ne travaille que trois infirmières que nous nommerons Anna, Berthe et Colombe. Dans cet hôpital il y a trois périodes possibles de travail :

Tel que posé, le problème est très simple à résoudre : on affectera Anna à la période jour, Berthe travaillera le soir et Colombe la nuit. Mais un tel horaire pourrait fort bien ne pas convenir à ces infirmières.
Dans le but de tenir compte, autant que faire se peut, de leurs préférences, l'administrateur en chef leur a demandé de répondre à un questionnaire. Ainsi, chaque infirmière devait évaluer, pour chaque quart de travail, son intérêt.
- Un 1 signifiait : Je n'apprécie pas du tout
- Un 2 signifiait : J'aime très peu
- Un 3 signifiait : Ça peut toujours aller
- Un 4 signifiait : J'aime beaucoup
- Un 5 signifiait : J'adore

Tel que posé le problème est suffisamment simple pour que l'on puisse penser à le résoudre par simple raisonnement. Nous vous invitons donc à le faire : il s'agira pour vous de trouver l'horaire qui, globalement, serait le plus satisfaisant pour les infirmières et de justifier votre réponse. Par la suite, vous pourrez comparer votre solution à celle obtenue par la mathématique.

Nous indiquons maintenant comment un tel problème peut être ramené à un problème de programmation linéaire. Nous introduirons tout d'abord 9 variables. Ces variables, qui ne pourront prendre que deux valeurs 0 ou 1, sont définies comme suit :

Il est à noter que lorsque nous avons présenté la programmation linéaire à l'aide du problème de la cabane à sucre, les variables pouvaient, en principe, prendre n'importe qu'elle valeur mais cela n'est pas le cas ici alors que les variables ne peuvent prendre que les valeurs 0 et 1. Cela détermine un domaine de la mathématique appelé Programmation linéaire en nombres entiers dont les méthodes de résolution se rapprochent de celles de la Programmation linéaire. Vous verrez plus loin comment on doit tenir compte de cette différence en résolvant des problèmes.

Ces contraintes sont à l'effet qu'une infirmière ne peut travailler plus de 8 heures/jour. Pour Anna, par exemple, on peut représenter cette contrainte en spécifiant que la somme de x, y et z ne peut dépasser 1. Cela veut dire, par exemple, que si x vaut 1 alors y et z vaudront 0.

Si on se limitait à ces 3 contraintes, on pourrait découvrir, par exemple, que la solution optimale est y = 1 (Anna travaille le soir), w = 1 (Berthe travaille la nuit) et s = 1 (Colombe travaille la nuit) ce qui, bien entendu, ne serait pas une solution acceptable car il n'y aurait pas d'infirmières le jour. Il est donc nécessaire d'introduire des contraintes à cet effet.

Il nous faut spécifier, mathématiquement que deux infirmières ou plus ne peuvent travailler sur une même période. Une façon de faire, pour le jour, consiste à écrire que x + u + p doit être plus petit ou égal à 1 ce qui signifie que le jour il y aura au plus une infirmière. Pour chaque période de travail nous avons une telle contrainte. Voici donc les trois nouvelles contraintes :

Intéressons- nous maintenant à ce que l'on cherche à optimiser à savoir la satisfaction globale des infirmières. Pour cela nous allons construire une fonction, que nous nommerons P, en utilisant les éléments de la matrice de satisfaction.

Nous cherchons donc à déterminer un horaire, c'est-à-dire la valeur des 9 variables, de telle sorte que P soit le plus grand possible. Un horaire sera donc un 9-tuplet ou vecteur à 9 composantes comme par exemple (1,0,0,0,1,0,0,0,1). Cet horaire nous dirait qu'Anna va travailler le jour, Berthe le soir et Colombe la nuit. Fait intéressant à noter, on ne peut utiliser une méthode graphique pour résoudre le problème car, avec des contraintes portant sur 9 variables, nous nous situons dans un espace à 9 dimensions!

Notons cependant qu'il existe une méthode générale appelée Méthode du Simplexe pour résoudre de tels problèmes (vous avez peut-être déjà expérimenté cette méthode dans le cas du problème de la cabane à sucre). Cette méthode, que nous n'expliquerons pas ici, peut être utilisée, à la main, seulement pour des problèmes impliquant très peu de contraintes et de variables. Pour des problèmes réels, on a implanté la méthode sur ordinateur et vous pourrez l'expérimenter sur un site internet que nous vous indiquons plus loin.

Mais, dans l'exemple considéré, qui est très simple, on n'a pas besoin de cette méthode ni d'un ordinateur. Voyons pourquoi. Au fonds il n'y a que 6 horaires différents possibles que nous illustrons dans le tableau suivant :

N'ayant que 6 horaires possibles, il est facile d'évaluer la fonction P pour chacun de ces horaires. Évaluons la fonction P pour le premier horaire. Dans ce cas x vaut 1, v vaut 1 et s vaut 1. Toutes les autres variables valent 0. P est donc égal à 1 + 1 + 5 = 7.

Nous vous invitons à faire les mêmes calculs pour les 5 autres horaires possibles. Vous découvrirez ainsi le ou les horaires qui, globalement, sont le plus satisfaisant pour les infirmières. S'il y a deux solutions optimales, vous vous demanderez laquelle devrait être choisie afin de satisfaire au mieux les préférences individuelles des infirmières. Une satisfaction optimale globale n'implique pas nécessairement une satisfaction optimale pour chaque infirmière. Il se peut fort bien que la solution mathématique soit équivalente à la solution intuitive que vous avez peut-être déjà trouvée. Mais, pour un problème réel, l'intuition ne serait pas suffisante!

- Une fois votre texte collé dans l'espace qui sert à définir le problème, vous pouvez sélectionner INTEGER signifiant ainsi que vous recherchez une solution optimale pour laquelle il n'y a pas de fractions. Imaginez, par exemple, que dans la solution optimale Anna doive travailler deux heures le jour, trois heures le soir et trois heures la nuit. Ce ne serait certainement pas là un horaire acceptable.

- En cliquant sur SOLVE le logiciel solutionnera le problème à l'aide de la méthode du Simplexe. Une petite limitation du logiciel : s'il y a plusieurs solutions il n'en fournira qu'une seule. Comparez cette solution avec celle que vous aurez trouvée.

- Si maintenant vous déroulez la page, vous verrez apparaître une série de tableaux : la méthode du Simplexe demande justement que l'on construise de tels tableaux jusqu'à ce que l'on arrive à la solution.