La modélisation des problèmes

Sans autre précision sur la nature de x, de S ou de f, la seule possibilité pour résoudre le problème (Min f(x) | xϵS ou Max f(x) | xϵS) est d'énumérer toutes les solutions.

Considérons le problème suivant : On doit organiser une tournée de livraisons d'un camion qui, partant d'un entrepôt, doit se rendre successivement chez un certain nombre de clients.

Enumérer la totalité des parcours possibles revient à lister toutes les permutations des clients.

Par exemple, avec 4 clients a, b, c, d, l'ordre des visites possibles est : a b c d a b d c a c b d a c d b a d b c a d c b .....

Ici nous n'avons que celles qui commencent par le client a ! Pour les dénombrer, on peut constater qu'il y a 4 choix possibles pour le client placé en 1, puis dans chaque cas 3 pour le deuxième, puis 2 pour le troisième, le quatrième étant alors celui qui reste, soit en tout 4*3*2*1 possibilités.

Rappelons que n! = 1*2*3....*n (factorielle n) représente le nombre de permutations de n éléments.

Pour 4 clients il y a donc 4! = 24 possibilités.

Ceci devient vite totalement inexploitable. Pour n = 10 on a déjà 10 ! = 10*9*8*... *3*2*1 = 3 628 800 tournées possibles !

L'énumération étant généralement impossible, pour résoudre un problème il faut construire un modèle qui lui soit adapté, c'est-à-dire préciser la nature de x, de S, et de f(x).

Un modèle est une "structure formalisée utilisée pour rendre compte d'un ensemble de phénomènes qui possèdent entre eux certaines relations".

Préférences du décideur

Le problème étudié se place dans un certain contexte qui va être traduit par les préférences du décideur.

Ce sont des données pour le problème. Le modèle doit servir pour explorer les solutions ou simuler toutes les relations entre les données et les variables.

Il peut prendre la forme d'un modèle mathématique, auquel cas il s'appuiera sur un ensemble d'équations mathématiques et de relations.

Il peut aussi exploiter des représentations graphiques. La modélisation procède nécessairement par simplifications et omissions.

Le modèle ne peut être qu'une représentation partielle et schématique. Seuls les éléments jugés pertinents en vue de l'exploration des solutions sont retenus.

Dans la construction d'un modèle, il faudra tenir compte du caractère plus au moins aléatoire de l'environnement : on peut être dans un environnement déterministe ou présentant un certain degré d'incertitude mais modélisable par des lois de probabilité, mais on peut aussi se trouver face à l'incertitude.

Les critères

Un autre aspect de la conception d'un modèle concerne les critères qui seront mis en avant pour évaluer les décisions.

Dans certains cas, il peut être suffisant de ne retenir qu'un critère unique : ce sera généralement le cas de problèmes à caractère opérationnel.

Dans un contexte de décisions plus stratégiques, on sera amené à prendre en compte plusieurs critères qui risquent d'être contradictoires.

Il n'existe pas vraiment de règles pour construire un modèle. "On a pu prétendre que la modélisation constituait d'avantage un art qu'une technique.

Plus modestement, nous pensons qu'elle relève plutôt d'un artisanat alliant rigueur scientifique et s0voir faire.

La solution

Une fois le problème correctement représenté, il s'agira alors de le résoudre.

Pour cela, pour chaque type de modèle, on dispose de méthodes de résolution.

La nature du problème peut conduire à des modèles pour lesquels il est encore aujourd'hui très difficile d'obtenir une solution optimale.

Dans ce cas, on s'attachera essentiellement à construire en un temps raisonnable une bonne solution en utilisant des méthodes approchées encore appelées "heuristiques".

Le modèle peut aussi être exploité comme outil de simulation : les variables et données sont liées entre elles par des relations.

On peut utiliser le modèle pour simuler la conséquence de variation de certaines données ou paramètres du problème et mesurer l'impact de certaines décisions dans un contexte où l'expérimentation est souvent impossible.

La décision

Une fois une solution élaborée, on peut dans un premier temps l'analyser dans l'objectif de valider le modèle.

Nous avons vu que le modèle n'était qu'une représentation schématique de la réalité.

Une solution pourrait mettre en évidence que certaines contraintes n'ont pas, ou ont mal, été prises en compte.

Si ce n'est pas le cas,il s'agira alors de traduire la solution obtenue dans les termes du problème tel qu'il avait été posé et laisser au décideur le soin de l'accepter, la modifier ou... la rejeter !

La démarche

La démarche précédente qui illustre le passage du problème à la décision, peut être représentée dans le schéma suivant

- qui lui-même ne constitue qu'un modèle ! - :

Dans la plupart des cas, ces méthodes reposent sur des processus itératifs, c'est à dire des algorithmes de détermination des solutions.

Exemples Algorithme

Exemple1:

Calcul de la somme des carrés des n premiers nombres entiers. Lire n
Somme : = 0
Résultat : = 0
POUR i de 1 à n FAIRE
I2 : = i*i
Somme : = Somme + I2
FINFAIRE
FINPOUR
Résultat := Somme
LIRE Résultat
Exemple2
Algorithme 1
LIRE n
LIRE x
Résultat := 1
POUR i de 1 à n FAIRE
Terme := 1
POUR j de 1 à i
Terme := Terme * (x / j )
FINPOUR
Résultat := Résultat + Terme
FINFAIRE
FINPOUR
LIRE Résultat
FIN
Algorithme2
LIRE n
LIRE x
Résultat:= 1
Terme := 1
POUR i de 1 à n FAIRE
Terme := Terme * (x / i)
Résultat : = Résultat + Terme
FINFAIRE
FINPOUR
LIRE Résultat
FIN

Ces deux algorithmes fournissent le même résultat :

Résultat =1+x+x2/2!+ x3/3!+….+ xn/n! Qui donne une valeur approchée de ex pour les petites valeurs de x.

Exercice 1

Le responsable du personnel d'une entreprise est confronté au problème suivant : afin de réaliser un certain nombre de tâches différentes bien identifiées, il dispose de personnels dont la compétence est diverse et pour lesquels il faut envisager une formation.

Il y a autant de personnes que de tâches et chaque personne se verra confier une et une seule tâche.

Le coût de formation dépend de la personne et de la tâche. Il voudrait connaître le nombre de solutions possibles à ce problème sachant qu'il concerne 5 tâches.

Même question si le nombre de tâches est égal à 10 ou à 20. Pouvez-vous lui fournir la réponse ? Dans le cas de 5 tâches, il a constitué le tableau suivant donnant le coût de formation pour chaque personne :

Pour déterminer l'affectation des 5 personnes aux tâches qui conduira au coût total de formation le moins élevé possible, le responsable du personnel propose de considérer les personnes dans un ordre donné, personne 1 puis 2 ….et de leur affecter la tâche de moindre coût encore non affectée. A quelle solution cette politique conduit-elle ici ?

Quel est son coût ? Pensez vous que cette méthode fournisse la "meilleure" solution ?