Transportproblem

Das Transportproblem — auch Hitchcock-Problem oder Hitchcock-Koopmans-Problem — ist das klassische lineare Programmierungsproblem (LP) der wöchentlichen Sendungsallokation zwischen m Quellen (Werke, Lager) und n Zielen (Kunden, Verteilstellen). Jede Quelle hat eine feste Kapazität (s_i), jedes Ziel einen festen Bedarf (d_j), jedes Quelle-Ziel-Paar einen Stückkostensatz (c_ij); die Entscheidungsvariable x_ij ≥ 0 minimiert die Gesamtfrachtkosten. Balanciert, wenn das Gesamtangebot gleich der Gesamtnachfrage ist; unbalancierte Fälle werden durch Hinzufügen einer Dummy-Quelle oder eines Dummy-Ziels gelöst. Gegründet durch Hitchcock (1941) und Koopmans (1947); Dantzig (1951) entwickelte die Simplex-Methode an diesem Problem. Das Zuordnungsproblem ist ein Spezialfall (gleiche Quelle-Ziel-Anzahl, Kapazität = Bedarf = 1). Moderne LP-Solver bewältigen Tausende Quelle-Ziel-Paare in Sekunden; Dual-Variablen (Schattenpreise) sind direkter Input für marginale Kapazitätsentscheidungen.