Assignment problems and the location of economic activities. (English) Zbl 0098.12203

Koopmans, Tjalling C.; Beckmann, Martin

Econometrica 25, 53-76 (1957).

In der Standorttheorie spielen Zuordnungsprobleme von ganzzahligen Einheiten eine große Rolle. Zwei dieser Zuordnungsprobleme, interpretiert als die Zuordnung von Fabriken zu möglichen Orten bei gegebenen Gewinnaussichten (und Transportkosten) werden untersucht. Problem 1: Lineares Zuordnungsproblem. Gegeben sei eine quadratische Matrix \( A=\left(a_{k i}\right), a_{k i}>0 \). Gesucht ist eine Permutationsmatrix \( P=\left(p_{k i}\right) \) mit sp \( A P^{\prime}= \) Max. Problem 1 ist eine ganzzahlige lineare Programmierungsaufgabe. Seine Lösung ist sicher unter den Lösungen des Problems 1a: \[ \sum_{i} x_{k i}=\sum_{i} x_{k i}=1, \quad x_{k \imath} \geqq 0 \quad \sum_{k, i} a_{k i} x_{k \imath}=\operatorname{Max} \] enthalten. Da es sich hierbei um ein spezielles Transportproblem handelt, ist die Lösung einfacher als die von Problem 1. Úber das Koopmanssche Preistheorem folgt für jede lineare Programmierungsaufgabe die Existenz eines Preissystems (Lösung des Dualprogramms), das z. B. für Problem 1 eine optimale Zuordnung sichert. Die Ableitung des Preistheorems erfolgt im Anhang über das Lemma von MinkowskiFarkas. Eine Zurückführung des linearen Zuordnungsproblems auf eine leichter berechenbare Form kann über das Theorem von Birkhoff (Anhang) oder über ein äquivalentes Zweipersonen-Nullsummenspiel von v. Neumann erfolgen. Problem 2 : Quadratisches Zuordnungsproblem. Gegeben seien die quadratischen Matrizen \( A=\left(a_{k i}\right), B=\left(b_{k i}\right), C=\left(c_{k i}\right) \) mit \( c_{i j} \leqq c_{i k}+c_{k j}, b_{k k}=c_{k k}=0 \). Gesucht wird eine Permutationsmatrix \( P=\left(p_{k i}\right) \) mit \[ \sum_{k, i} a_{k i} p_{k i}-\sum_{i, j, k, l} b_{k l} p_{k i} c_{i j} p_{l \jmath}=\operatorname{Max} \] Für \( A=0 \) und \( B=\left(\begin{array}{cc}0 & I \\ 1 & -0 \\ 1\end{array}\right) \) geht das Problem in das Travelling Salesman Problem über. Wegen der rechnerischen Schwierigkeiten, die bei der Lösung des quadratischen Zuordnungsproblems entstehen, wird wie bei Problem 1 ein Preissystem gesucht, das eine optimale Zuweisung liefert. An Hand von einigen einfachen Beispielen wira gezeigt, daß es ein Preissystem von der Art wie bei Problem 1 nicht gibt.

This review text is based on a scanned copy of the printed version. It was converted to LaTeX using MathPix and a specifically developed LLM to assign the text parts to the metadata. It may contain errors, misassignments, or gaps; in particular, the reviewer signature has not yet been extracted reliably in general. If you notice any errors, please report them directly to our editorial team via the Contact Form.

Keywords:

Applications of probability theory and statistics