Chapitre 4.Modélisation du problème
posé
Nombre de contraintes
Le tableau suivant montre le nombre de contraintes
associés à notre modèle:
|
Type de contrainte
|
Nombre de contraintes
|
(1)
|
Nbrtaches
|
(2)
|
Nbrtaches * Nbrtaches
|
(3)
|
Nbrtaches
|
(4)
|
Nbrtaches
|
(5)
|
Nbrtaches
|
(6)
|
Nbrtaches
|
(7)
|
|
1
|
|
TABLE 4.2 - Tableau représentatif du nombre de
contraintes
Nous obtenons au total : Nbrcontraintes = 5 *
Nbrtaches + Nbrtaches * Nbrtaches + 1
contraintes.
4.4 Méthodes de résolution des PL
4.4.1 Les Méthodes exactes
Les méthodes de résolution exactes sont
nombreuses et se caractérisent par le fait qu'elle permettent d'obtenir
une ou plusieurs solutions. Elles se basent généralement sur une
recherche complète de l'espace des combinaisons afin de trouver une
solution optimale. Ces dernières sont souvent lentes et ne
résolvent que des problèmes dont l'espace de recherche est petit.
Tels que la programmation dynamique, séparation et évaluation,
ect.
La programmation dynamique
La programation dynamique est une méthode
d'optimisation qui a pour objet d'aider à prendre des décision
séquentielles indépendantes les unes des autres. Le concept a
été introduit au début des années 1950 par Richard
Belleman. À l'époque, le terme "programmation" signifie
planification et ordonnacement, elle consiste à résoudre un
problème en le décomposant en sous-problème, puis à
résoudre les sous-problème des plus petits aux plus grands en
stockant toujours les résultats intermiédiaires.[9]
37
| 
