An algorithm for optimal resource allocation in systems with linear constraints

algorithm convergence dynamic programming efficiency minimal storage requirements optimal resource allocation optimal strategy stockage systems with linear constraints utility function

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Utility theory (91B16)

Review text

Dans cet article l'auteur examine la problématique de la gestion des ressources de différents types, par exemple hydriques. A chaque instant t une fonction d'utilité \(G_ t\) est déterminée. L'auteur se propose d'élaborer une stratégie, solution d'un problème qui revient à maximiser une somme finie de valeurs de la fonction d'utilité pour \(t=1,2,...,N+1\). Soit \(D_ t\) le débit à l'instant t, il existe des constraintes comprenant l'équation de continuité du système \(X_{t+1}=g(X_ t,D_ t,Q_ t)\) ainsi que des limites opératives sur les débits et des limites physiques sur l'emmagasinage; la variable \(X_ t\) correspond à ce dernier. \(Q_ t\) représente l'afflux au dépôt au temps t. En vue du calcul d'une stratégie optimale, l'auteur propose un algorithme qui est neuf et qui possède plusieurs qualités requises: il est simple et opère sans la discrétisation de la variable d'état. En outre il ne demande pas trop de mémoires. L'algorithme converge de façon monotone en \((N+1)\) pas au plus, N désignant le nombre de phases et est efficace pour le calcul numérique. Le domaine d'application de l'algorithme est limité comme suit: l'équation d'état est linéaire et le problème examiné est à une dimension. D'autre part celui-ci est en sorte, du point de vue formel, un cas particulier d'un certain problème (\({\mathcal P})\), qui a été traité dans le cas linéaire par \textit{V. Levis} [Calcolo 1, 299-336 (1964; Zbl 0138.163)]. Soit \({\mathcal D}\) l'ensemble des stratégies D admissibles, c'est-à-dire de celles qui satisfont aux contraintes imposées. L'auteur démontre une condition nécessaire et suffisante d'existence d'une solution, un résultat se rapportant à l'unicité de celle ci est énoncé. En vue d'établir un algorithme déterminant une stratégie optimale, l'auteur traite d'abord le cas linéaire. Pour V t fixé, il suppose que \(G_ t(\cdot)\) est une fonction affine de x, \(x\in R\). Etant donné \(D\in {\mathcal D}\), il envisage la suite temporelle des stockages minimaux, qui rendent possibles le débit \(D_ t\) au temps t; cette suite est définie au moyen d'une relation de récurrence. Comme chaque stratégie optimale distribue le volume maximum de ressources, les stratégies ayant une norme maximale dans \({\mathcal D}\) vont être caractérisés. Au cas où la fonction d'utilité est concave et linéaire par morceaux, l'auteur utilise une procédure typique de la programmation linéaire. Dans le cas général il fait l'hypothèse que \(G_ t\) est une fonction non décroissante, qu'il convient de supposer concave dans les applications. La fonction \(G_ t\) est approchée par une suite de fonctions polygonales appropriée. Après avoir démontré un théorème de convergence, l'auteur présente le tracé de l'organigramme se rapportant à l'algorithme et traite un exemple numérique.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: An algorithm for optimal resource allocation in systems with linear constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1089747)