next up previous
suivant: Application du problème de monter: Problèmes faisant intervenir le précédent: Le problème des représentants

Le problème de l'arrondi cohérent

Soit $ D$ une $ n\times m$ matrice de nombres réels. On note respectivement $ \alpha_i,\quad i\,\in\, 1..n$ et $ \beta_j,\quad j\,\in\,1..m$ les sommes des éléments sur les lignes et les colonnes. Le but de ce problème est d'arrondir chacun des nombres stocké dans la matrice de manière à ce que, pour chaque ligne et pour chaque colonne, la somme des nombres arrondis soit l'arrondi de la somme. En d'autres termes, et si l'on note $ \eta^*$ l'arrondi du nombre $ \eta$, on doit avoir :

\begin{displaymath}
\left\{
\begin{array}{@{\forall\,}c@{\,\in\,}c@{\quad}l@{=...
...um\limits_{i=1}^n d_{ij}^* & \beta_j^*
\end{array}
\right.
\end{displaymath}

Contrairement à de nombreuses applications où l'arrondi est imposé à l'entier le plus proche, ici $ \eta^*$ est choisi librement parmi $ \lfloor
\eta \rfloor$ et $ \lceil \eta \rceil$. Il est possible de modéliser ce problème très facilement à l'aide d'un réseau. Il suffit de considérer, en plus des sommets $ s$ et $ t$, deux ensembles de sommets $ L$ et $ C$ modélisant respectivement les lignes et les colonnes de la matrice. Chaque sommet $ l_i \in L$ est ainsi associé à la i $ ^{\text{\\lq eme}}$ ligne de la matrice. Les arcs $ (s,\,l_i)$ ont pour capacités le couple $ (\lfloor
\alpha_i \rfloor,\,\lceil \alpha_i \rceil)$. Réciproquement, chaque sommet $ c_j \in C$ étant associé à la j $ ^{\text{\\lq eme}}$ colonne de $ D$, les arcs $ (c_j,\,t)$ ont pour capacités $ (\lfloor \beta_j \rfloor,\,\lceil
\beta_j \rceil)$. Reste à modéliser chacun des éléments de la matrice par un arc reliant sa ligne et sa colonne. Ainsi, l'élément $ d_{ij}$ est représenté par l'arc $ (l_i,\,c_j)$ de capacités $ (\lfloor \eta \rfloor,\, \lceil \eta
\rceil)$. D'ordinaire, il existe plusieurs solutions à ce problème, chacune étant associée à un flot compatible sur ce réseau. Toutefois, le flot max est associé à la solution utilisant le plus de valeurs supérieures alors que le flot min est associé à la solution utilisant le plus de valeurs inférieures. La figure suivante illustre ce modèle sur un exemple simple.

Figure 5.5: Modélisation du problème de l'arrondi cohérent d'une matrice par un réseau
\begin{figure}
\leavevmode
\begin{center}
Données de la matrice~:
\begin{dis...
...4 & 14,5 \\ \hline
\end{array}
\end{displaymath}
\end{center}
\end{figure}


next up previous
suivant: Application du problème de monter: Problèmes faisant intervenir le précédent: Le problème des représentants
Bruno Garcia 2000-12-17