The distribution of a product from several sources to numerous localities. (Q2582822)

\(n\) Städte decken ihren Bedarf \(c_1, \ldots \!,c_n\) eines bestimmten Verbrauchsgutes bei \(m\) Produzenten, die die gerade ausreichenden Mengen \(f_1, \ldots \!,f_m\) desselben herstellen. Bezeichnet \(a_{ij}\) die Kosten einer vom \(i\)-ten Produzenten an die \(j\)-te Stadt gelieferten Mengeneinheit und \(x_{ij}\) die Anzahl der entsprechenden Mengeneinheiten, so ist diejenige Verteilung \(x_{ij}\) \((x_{ij} \geqq 0)\) der gelieferten Mengeneinheiten zu bestimmen, für welche die Gesamtkosten \[ y=\sum_{i=1}^{m} \sum_{j=1}^{n} a_{ij} x_{ij} \] ein Minimum sind, und welche die beiden Gleichungssysteme \[ x_{i1}+\cdots+x_{in}=f_i \quad (i=1, \ldots \!,m) \quad \text{und} \quad x_{1j}+\cdots+x_{mj}=c_j \quad (j=1, \ldots \!,n) \] mit \(f_1+\cdots+f_m=c_1+\cdots+c_n\) erfüllt. Geometrische Überlegungen zeigen, daß dann \((m \cdot n-m-n+1)\) der \(x\)-Werte verschwinden müssen. Die Aufgabe wird auf einfache Weise sukzessive gelöst, indem (\(f_i\) und \(c_j\) nach wachsender Größe numeriert) in dem Schema \[ \frac{\left. \begin{matrix} x_{11} & \quad\cdots & x_{1n}\;\\ \vdots & & \vdots\\ x_{m1} & \quad\cdots & x_{mn}\; \end{matrix} \right| \begin{matrix} f_1\\ \vdots\\ f_m \end{matrix}} {\left. \begin{matrix}\l\qquad&\quad\;&\l\\ c_1 & \;\cdots & c_n\quad \end{matrix} \right| \quad} \] in der ersten Zeile bzw. Spalte alle \(x\) bis auf das letzte gleich Null gesetzt werden, wodurch sich das Schema um eine Zeile bzw. Spalte reduzieren läßt.