Einige Aspekte in der Zuordnungstheorie
Tóm tắt
Gegeben seien endliche MengenX, Y undZ ⊂ X × Y, Z
x
={y¦(x,y)∈ Z},Z
y
={x¦(x,y)∈ Z}. Man nenntA ⊂ X (bzw.B ⊂ Y)zuordenbar, wenn es eine Injektionρ:A → Y (bzw.ψ: B →X) mitρ(x) ∈ Z
x
(bzw.ψ(y) ∈ Z
y
) gibt, und (A, B) mit #A=#B > 0 einZuordnungspaar, wenn eine Bijektionf:A →B mitf(x)∈Z
x
∩ B (bzw.f
−1
(y)∈ Z
y
∩ A) existiert. Die Bijektionf heißtZuordnungsplan fürA, B. In der vorliegenden Arbeit werden Fragen nach der Existenz von optimal zuordenbaren Mengen und optimalen Zuordnungspaaren behandelt, wenn man auf den MengenX undY Ordnungen vorgibt, wobei auch Nebenbedingungen berücksichtigt werden. In manchen Fällen lassen sich anhand der Beweise Zuordnungspläne oder ihre Berechnungsvorschrift explizit angeben. Zum Schluß werden die Aussagen an konkreten, dem Bereich der Wirtschaftswissenschaften entnommenen Beispielen erläutert.
Tài liệu tham khảo
Burkard, R. E.: Methoden der Ganzzahligen Optimierung, Wien-New York 1972.
Edmonds, J.: Matroids and the Greedy Algorithm, in: Math. Prog.1, 127–136, 1971.
Edmonds, J., andD. R. Fulkerson: Bottleneck Extrema, in: J. Comb. Theory8, 299–306, 1970.
Gale, D.: Optimal Assignment in an Ordered Set: An Application of Matroid Theory, in: J. Comb. Theory4, 176–180, 1968.
Kuhn, H. W.: The Hungarian Method for Solving the Assignment Problem, in: Naval Res. Logist. Quart.2, 83–97, 1955.
Ore, O.: Graphs and Matching Theorems, in: Duke Math. J.22, 625–639, 1955.
Ryser, H. J.: Combinatorial Mathematics, in: The Carus Mathematical Monographs14, 1963.
Welsh, D. J. A.:Kruskal's Theorem for Matroids, in: Proc. Camb. Phil. Soc.64, 3–4, 1968.
Whitney, H.: On the Abstract Properties of Linear Dependence, in: Amer. J. Math.57, 509–533, 1935.