Au-delà de la programmation dynamique - article ; n°3 ; vol.20, pg 515-535

Jean-Marc Dethoor

Description

Revue économique - Année 1969 - Volume 20 - Numéro 3 - Pages 515-535
On peut assez aisément représenter l'imbrication des décisions de gestion au moyen de graphes séquentiels. L'algorithme de Bellman s'attache à déterminer le chemin optimal dans un tel graphe, mais cette méthode peut être raffinée de diverses manières, notamment en jumelant la programmation dynamique et les multiplicateurs de Lagrange ou encore par les méthodes S.E.P. (branch and bounds). Après une brève introduction montrant comment il est possible de formaliser l'enchaînement des décisions sous une forme graphique, mais sans rappeler ce qu'est la programmation dynamique, l'auteur souligne des limites de cette méthode, puis montre comment il est possible de les dépasser en prenant compte des fonctions de coût non additives comme le taux de rentabilité ou des contraintes exogènes (enveloppe budgétaire...). La procédure S.E.P. fait l'objet d'un rapide exposé méthodologique et d'exemples numériques didactiques.
Imbrication of management decisions can readily be depicted by means of sequential graphs. Bellman's algorithm is concerned to define the optimal path for such a graph, but the method can be reflned in various ways, especially by bringing together dynamic programming and Lagrange's multipliers, or by using branch and bounds methods (S.E.P.). After a brief introduction showing how it is possible to express decision sequences in the form of a graph, but without going into explanations of what dynamic programming constitutes, the author stresses the limitations of the method and then shows how it is possible to get round them by taking non-additive cost functions into account such as the profit rate or exterior checks (budgetary envelope...). Branch and bounds procedure is the subject of a rapid methodological expose with mathematical illustrations.
21 pages
Source : Persée ; Ministère de la jeunesse, de l’éducation nationale et de la recherche, Direction de l’enseignement supérieur, Sous-direction des bibliothèques et de la documentation.

Sujets

• Sociologie, société et politique

Informations

• Publié par: REVUE_ECONOMIQUE
• Publié le: 01 janvier 1969
• Nombre de lectures: 26
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

Monsieur Jean-Marc Dethoor
Au-delà de la programmation dynamique
In: Revue économique. Volume 20, n°3, 1969. pp. 515-535.
Résumé
On peut assez aisément représenter l'imbrication des décisions de gestion au moyen de graphes séquentiels. L'algorithme de
Bellman s'attache à déterminer le chemin optimal dans un tel graphe, mais cette méthode peut être raffinée de diverses
manières, notamment en jumelant la programmation dynamique et les multiplicateurs de Lagrange ou encore par les méthodes
S.E.P. (branch and bounds). Après une brève introduction montrant comment il est possible de formaliser l'enchaînement des
décisions sous une forme graphique, mais sans rappeler ce qu'est la programmation dynamique, l'auteur souligne des limites de
cette méthode, puis montre comment il est possible de les dépasser en prenant compte des fonctions de coût non additives
comme le taux de rentabilité ou des contraintes exogènes (enveloppe budgétaire...). La procédure S.E.P. fait l'objet d'un rapide
exposé méthodologique et d'exemples numériques didactiques.
Abstract
Imbrication of management decisions can readily be depicted by means of sequential graphs. Bellman's algorithm is concerned
to define the optimal path for such a graph, but the method can be reflned in various ways, especially by bringing together
dynamic programming and Lagrange's multipliers, or by using branch and bounds methods (S.E.P.). After a brief introduction
showing how it is possible to express decision sequences in the form of a graph, but without going into explanations of what
dynamic constitutes, the author stresses the limitations of the method and then shows how it is possible to get
round them by taking non-additive cost functions into account such as the profit rate or exterior checks (budgetary envelope...).
Branch and bounds procedure is the subject of a rapid methodological expose with mathematical illustrations.
Citer ce document / Cite this document :
Dethoor Jean-Marc. Au-delà de la programmation dynamique. In: Revue économique. Volume 20, n°3, 1969. pp. 515-535.
http://www.persee.fr/web/revues/home/prescript/article/reco_0035-2764_1969_num_20_3_407872AU-DELA
DE LA PROGRAMMATION DYNAMIQUE *
RESUME ' On peut assez aisément représenter l'imbrication des décisions de
gestion au moyen de graphes séquentiels. L'algorithme de Bellman s'attache à
déterminer le chemin optimal dans un tel graphe, mais cette méthode peut être
raffinée de diverses manières, notamment en jumelant la programmation dyna
mique et les multiplicateurs de Lagrange ou encore par les méthodes S.E.P. (branch
and bounds) .
Après une brève introduction montrant comment il est possible de formaliser
l'enchaînement des décisions sous une forme graphique, mais sans rappeler ce qu'est
la programmation dynamique, l'auteur souligne des limites de cette méthode, puis
montre comment il est possible de les dépasser en prenant compte des fonctions
de coût non additives comme le taux de rentabilité ou des contraintes exogènes
(enveloppe budgétaire...). La procédure S.E.P. fait l'objet d'un rapide exposé
méthodologique et d'exemples numériques didactiques.
ABSTRACT Imbrication of management decisions can readily be depicted by
means of sequential graphs. Bellman's algorithm is concerned to define the optimal
path for such a graph, but the method can be refined in various "ways, especially
by bringing together dynamic programming and Lagrange's multipliers, or by
using branch and bounds methods (S.E.P.).
After a brief introduction showing how it is possible to express decision
sequences in the form of a graph, but without going into explanations of "what
dynamic programming constitutes, the author stresses the limitations of the method
and then shows how it is possible to get round them by taking non-additive cost
functions into account such as the profit rate or exterior checks (budgetary envel
ope...). Branch and bounds procedure is the subject of a rapid methodological
exposé with mathematical illustrations.
* Cet article n'a pu être inséré faute de place dans notre numéro spécial de
mars 1969. Il apporte une contribution originale sur les limites de la program
mation dynamique et sur certaines possibilités de dépassement de cette technique
(N.D.R.). 516 REVUE ECONOMIQUE
I. DU BON USAGE DE LA PROGRAMMATION DYNAMIQUE
A. Les applications immédiates de la programmation dynamique
La programmation dynamique est un véritable outil de gestion des
systèmes économiques.
Toute décision peut être importante car, en plus de son effet
immédiat généralement bien connu, elle a un retentissement sur
l'avenir : chacune conditionne en partie les suivantes. Il ne s'agit donc,
en réalité, pas tant de prendre une décision, que de choisir une poli
tique, c'est-à-dire adopter une règle de conduite, une véritable règle
de décision.
1. Enchaînement des décisions
Les décisions sont séquentielles et les graphes constituent un moyen
commode de représentation de leur enchaînement. Dans le cas simple
où l'on connaît parfaitement l'effet des décisions, où l'on n'agit qu'à
coup sûr, on peut caractériser une décision prise au vu d'un certain
état du système par l'effet produit. C'est-à-dire qu'une décision simple
n'est autre qu'une transition entre deux états du système.
Etat Ei DECISION Etat Ej
FlG. 1 : Représentation d'une décision simple
Envisageons toutes les décisions possibles de la date 0 à la date T.
On peut représenter l'évolution virtuelle du système par un graphe
dans lequel les sommets représentent les états du système et les arcs
les transitions (les décisions) possibles. Par nature, ce graphe est
sans circuit.
T
Fig. 2 : Exemple d'enchaînement des décisions AU-DELA DE LA PROGRAMMATION DYNAMIQUE 517
L'état initial (date 0) du système est l'état (1). Il est possible,
en jouant sur les décisions possibles D12, D14, D23, D24, D35,
D43, D45, D46) de l'amener dans l'un des états finals (5) ou (6) en
passant par l'un ou plusieurs des états (2), (3), (4).
Les différentes politiques possibles sont au nombre de 7.
Ce sont :
D12 — D23 — D35 " D"
— — D J-— -i *O — Do, <jO D^,
- D,4 - D45 - D12
- D2, - D4tt - D»
- D43 - D,5 - D14
- D45 - Di4
- D4G - D14
Une politique est représentée par un chemin joignant le sommet
représentatif de l'état initial à l'un des sommets terminaux.
2. Valuation du graphe
II est souvent possible d'affecter à chaque décision une quantité
égale à ce qu'elle « rapporte ». On peut alors valuer l'arc figuratif
de cette quantité. Dans le cas très général où cette évaluation de ce
que « rapporte » la décision est additive, c'est-à-dire que la somme
des valeurs des arcs sur un chemin est égale à ce que rapporte la
politique correspondante, le choix d'une politique optimale se réduit
à la recherche d'un chemin de longueur maximale dans le graphe.
Nous venons de déterminer la politique qui assure au gestionnaire
le rapport maximal ; il va sans dire qu'il n'y aurait aucune difficulté
à déterminer la politique qui assure le coût minimal. En affectant à
chaque arc le coût de la décision correspondante, il ne reste plus
qu'à le chemin de longueur minimale dans le graphe.
La condition d'additivité de la « fonction de coût », évidemment
indispensable, n'est pas aussi contraignante qu'il pourrait paraître à
première vue et l'expérience montre qu'il est généralement possible,
moyennant d'éventuels artifices, de concevoir une telle fonction de
coût bien adaptée à la nature du problème posé.
3. Présentation du graphe sous forme séquentielle
II est possible de « mettre de l'ordre » dans le graphe en le rame
nant à une succession d'étapes.
Ainsi l'exemple précédent (cf. fig. 2) peut être présenté sous la
forme suivante : 518 REVUE ECONOMIQUE
Fig. 3 : Mise sous [orme séquentielle d'un graphe sans cycle
Pour ce faire, on a dû représenter deux fois l'état (3) et trois
fois l'état (4). Dans ce nouveau graphe, les transitions d'un état
vers lui-même sont évidemment affectées d'une valeur nulle.
Sous cette forme, la recherche du chemin n'est autre que le
calcul d'