L'implémentation de problème relevant
de la programmation dynamique est un véritable défi. On
va voir dans cet exemple qu'une première mise ne place du
problème qui pourtant est simple , conduit à des
résultats faux alors que le solveur vous annonce que l'optimum
est atteint.
Vous pouvez suivre ces exemples en copiant sur votre disque les
fichiers exemples EXCEL :
On dispose d'une somme de 7 MF à investir,
somme à répartir entre 3 investissements A,B et C. Les
profits engendrés dépendent de la somme investie
suivant A, B ou C.
Le but est d'optimiser la répartition des 7 MF dans les divers
investissements pour gagner le plus d'argent. Voici le tableau des
gains correspondants (on l'appelle
TabInv):
Voici la feuille de calcul EXCEL correspondant à cette première modélisation:
L'image ne représente pas le tableau TabInv, mais il doit y figurer sur la feuillle EXCEL.
L'idée de cette première mise en forme
est d'aller chercher le gain dans le tableau
TabInv à l'aide
de la fonction INDEX(). Sur l'exemple il y a 4 MF investi sur A : on
va donc chercher le gain correspondant grace à INDEX(tab
,ligne,colonne).
Le problème est que la résolution ne marche pas. Et
pourtant le solveur donne la réponse :
Ce qui est faux puisque le bénéfice max
est de 7,2 MF.
Cette erreur vient de la fonction INDEX() ,qui n'est pas
linéaire et trompe le solveur. On est donc obligé de
trouver une implémentation du problème qui ne
nécessite pas INDEX().
L'idée est d'utiliser une multiplication de
matrices (qui est linéaire).
Voici la feuille de calcul (en ommétant le
TabInv):
On remplace INDEX() par la multiplication d'une
matrice de 0 et de 1 (ensemble des cellules variables) avec la
matrice des gains
TabInv . Il existe
pour cela une fonction EXCEL qui s'appelle SOMMEPROD().
Ce qui donne alors :
La résolution est ensuite sans problème. Il est utile de cocher la case Modèle supposé linéaire dans le menu Option du solveur pour gagner en rapidité. Le solveur trouve enfin la bonne solution.