Übung 01

Grundlagen & Standortplanung

Aufgabe 1 - Standortplanung ohne Kapazitätsbeschränkung

Ein Unternehmen plant die Belieferung von drei Abnehmern (\(j \in \{1, 2, 3\}\)) von potentiellen Standorten (\(i \in \{A, B, C\}\)) mit unbegrenzter Kapazität. Folgende Daten sind gegeben:

Transportkosten \(c_{ij}\) [€/ME] und Fixkosten \(f_i\) [€]:

Standort \(i\) Abnehmer 1 Abnehmer 2 Abnehmer 3 Fixkosten \(f_i\)
A 10 20 30 1.000
B 50 40 50 2.000
C 80 30 40 2.500

Bedarfe: \(d_1 = 100\) ME, \(d_2 = 150\) ME, \(d_3 = 200\) ME

  1. Bestimmen Sie den/die kostenminimalen Standort(e) unter der Annahme, dass jeder Abnehmer vollständig vom günstigsten Standort beliefert wird.
  2. Wie viele Kombinationsmöglichkeiten müssten theoretisch geprüft werden, wenn Sie alle möglichen Standortkombinationen untersuchen wollten?
  3. Interpretieren Sie Ihr Ergebnis aus a). Warum ist diese Lösung in der Praxis möglicherweise nicht optimal?

Lösung:

  1. Bestimmung der kostenminimalen Standorte:

Schritt 1: Berechnung der Gesamtkosten für jeden einzelnen Standort (vollständige Belieferung):

  • Standort A: \(K_A = f_A + c_{A1} \cdot d_1 + c_{A2} \cdot d_2 + c_{A3} \cdot d_3\) \(K_A = 1.000 + 10 \cdot 100 + 20 \cdot 150 + 30 \cdot 200 = 1.000 + 1.000 + 3.000 + 6.000 = 11.000\) €

  • Standort B: \(K_B = 2.000 + 50 \cdot 100 + 40 \cdot 150 + 50 \cdot 200\) \(K_B = 2.000 + 5.000 + 6.000 + 10.000 = 23.000\) €

  • Standort C: \(K_C = 2.500 + 80 \cdot 100 + 30 \cdot 150 + 40 \cdot 200\) \(K_C = 2.500 + 8.000 + 4.500 + 8.000 = 23.000\) €

Ergebnis: Standort A ist mit 11.000 € die kostenminimale Lösung.

Warum müssen keine weiteren Kombinationen geprüft werden?

Da die Standorte unbeschränkte Kapazität haben, kann jeder einzelne Standort alle Abnehmer vollständig beliefern. Das Hinzufügen eines weiteren Standorts würde immer zusätzliche Fixkosten verursachen, ohne die Transportkosten zu senken. Denn bei Belieferung von einem Standort aus wählt man ohnehin bereits die günstigsten Transportwege von diesem Standort. Da kein anderer Standort bei irgendeinem Abnehmer günstiger ist als A (Standort A hat für alle Abnehmer die niedrigsten Transportkosten), kann das Hinzufügen eines weiteren Standorts nur zu Mehrkosten führen. Daher ist die Einzelstandortlösung mit A garantiert optimal.

  1. Anzahl der Kombinationsmöglichkeiten:

Bei 3 Standorten gibt es \(2^3 - 1 = 7\) nicht-leere Kombinationen:

  • Einzelstandorte: {A}, {B}, {C}
  • Zweierkombinationen: {A,B}, {A,C}, {B,C}
  • Alle drei: {A,B,C}
  1. Interpretation:

Die Lösung mit nur Standort A minimiert zwar die Kosten, birgt aber Risiken:

  • Keine Redundanz: Bei Ausfall von A bricht die gesamte Versorgung zusammen
  • Keine Flexibilität: Keine Reaktionsmöglichkeit auf Nachfrageschwankungen
  • Transportrisiken: Alle Transporte gehen von einem Punkt aus
  • In der Praxis würde man möglicherweise einen zweiten Standort als Backup in Betracht ziehen

Aufgabe 2 - Mathematische Modellierung

Gegeben sei ein Standortplanungsproblem mit \(I\) potentiellen Standorten und \(J\) Abnehmern.

  1. Formulieren Sie die vollständige mathematische Modellierung des Standortplanungsproblems mit Kapazitätsbeschränkungen (Zielfunktion und alle Nebenbedingungen).
  2. Erläutern Sie, aus welchen zwei Teilproblemen das Standortplanungsproblem besteht.
  3. Formulieren Sie explizit die Zielfunktion für eine konkrete Instanz mit 3 Standorten (A, B, C) und 3 Abnehmern (1, 2, 3) mit folgenden Daten:
    • Fixkosten: \(f_A = 1.000\), \(f_B = 1.200\), \(f_C = 900\)
    • Transportkosten: \(c_{A1} = 1\), \(c_{A2} = 2\), \(c_{A3} = 3\), \(c_{B1} = 4\), \(c_{B2} = 5\), \(c_{B3} = 6\), \(c_{C1} = 7\), \(c_{C2} = 8\), \(c_{C3} = 9\)
  4. Welche Nebenbedingung stellt sicher, dass Standorte nur genutzt werden können, wenn sie auch errichtet wurden? Formulieren Sie diese für Standort B.

Lösung:

  1. Siehe Vorlesung:

  2. Die zwei Teilprobleme:

  1. Standortauswahlproblem: Welche Standorte sollen errichtet werden? (Entscheidung über \(\gamma_i\))
  2. Transportproblem: Wie sollen die Abnehmer von den gewählten Standorten beliefert werden? (Entscheidung über \(x_{ij}\))

Diese Probleme sind gekoppelt, da die Transportentscheidung von der Standortwahl abhängt.

  1. Explizite Zielfunktion:

\(Z = 1.000 \cdot \gamma_A + 1.200 \cdot \gamma_B + 900 \cdot \gamma_C\) \(\quad + 1 \cdot x_{A1} + 2 \cdot x_{A2} + 3 \cdot x_{A3}\) \(\quad + 4 \cdot x_{B1} + 5 \cdot x_{B2} + 6 \cdot x_{B3}\) \(\quad + 7 \cdot x_{C1} + 8 \cdot x_{C2} + 9 \cdot x_{C3}\)

  1. Kapazitätsbeschränkung für Standort B:

\(x_{B1} + x_{B2} + x_{B3} \leq b_B \cdot \gamma_B\)

Diese Nebenbedingung stellt sicher, dass:

  • Wenn \(\gamma_B = 0\) (Standort B nicht errichtet): \(x_{B1} + x_{B2} + x_{B3} \leq 0\), d.h. keine Lieferung möglich
  • Wenn \(\gamma_B = 1\) (Standort B errichtet): \(x_{B1} + x_{B2} + x_{B3} \leq b_B\), d.h. Kapazität begrenzt Lieferungen

Aufgabe 3 - Standortplanung mit Kapazitätsbeschränkung

Betrachten Sie folgendes Standortplanungsproblem:

Daten:

Standort \(i\) \(c_{i1}\) \(c_{i2}\) \(c_{i3}\) Fixkosten \(f_i\) Kapazität \(b_i\)
A 1 2 3 1.000 400
B 4 5 6 1.200 400
C 7 8 9 900 400

Bedarfe: \(d_1 = 200\), \(d_2 = 300\), \(d_3 = 250\)

  1. Gegeben sei folgende Lösung: \(\gamma_A = 1\), \(\gamma_B = 1\), \(\gamma_C = 0\)
    • Abnehmer 1 wird vollständig von A beliefert: \(x_{A1} = 200\)
    • Abnehmer 2 wird je zur Hälfte von A und B beliefert: \(x_{A2} = 150\), \(x_{B2} = 150\)
    • Abnehmer 3 wird vollständig von B beliefert: \(x_{B3} = 250\) Berechnen Sie den Zielfunktionswert dieser Lösung.
  2. Prüfen Sie die Zulässigkeit dieser Lösung bezüglich aller Nebenbedingungen.
  3. Ist folgende alternative Belieferung zulässig: Abnehmer 2 wird vollständig von A beliefert (\(x_{A2} = 300\))? Begründen Sie.
  4. Schlagen Sie eine verbesserte Lösung vor und begründen Sie Ihre Wahl.

Lösung:

  1. Berechnung des Zielfunktionswerts:

Fixkosten: \(f_A \cdot \gamma_A + f_B \cdot \gamma_B + f_C \cdot \gamma_C = 1.000 \cdot 1 + 1.200 \cdot 1 + 900 \cdot 0 = 2.200\)

Transportkosten:

  • Von A: \(c_{A1} \cdot x_{A1} + c_{A2} \cdot x_{A2} = 1 \cdot 200 + 2 \cdot 150 = 500\)
  • Von B: \(c_{B2} \cdot x_{B2} + c_{B3} \cdot x_{B3} = 5 \cdot 150 + 6 \cdot 250 = 2.250\)

Gesamtkosten: \(Z = 2.200 + 500 + 2.250 = 4.950\)

  1. Prüfung der Zulässigkeit:

Bedarfsdeckung (NB 1):

  • Abnehmer 1: \(x_{A1} + x_{B1} + x_{C1} = 200 + 0 + 0 = 200 = d_1\) ✓
  • Abnehmer 2: \(x_{A2} + x_{B2} + x_{C2} = 150 + 150 + 0 = 300 = d_2\) ✓
  • Abnehmer 3: \(x_{A3} + x_{B3} + x_{C3} = 0 + 250 + 0 = 250 = d_3\) ✓

Kapazitätsbeschränkung (NB 2):

  • Standort A: \(x_{A1} + x_{A2} + x_{A3} = 200 + 150 + 0 = 350 \leq 400 = b_A \cdot 1\) ✓
  • Standort B: \(x_{B1} + x_{B2} + x_{B3} = 0 + 150 + 250 = 400 \leq 400 = b_B \cdot 1\) ✓
  • Standort C: \(x_{C1} + x_{C2} + x_{C3} = 0 + 0 + 0 = 0 \leq 0 = b_C \cdot 0\) ✓

Ergebnis: Die Lösung ist zulässig.

  1. Alternative mit vollständiger Belieferung von Abnehmer 2 durch A:

Bei \(x_{A2} = 300\) wäre die Auslastung von A: \(x_{A1} + x_{A2} + x_{A3} = 200 + 300 + 0 = 500 > 400 = b_A\)

Nein, diese Lösung ist nicht zulässig, da die Kapazität von Standort A überschritten wird.

  1. Verbesserte Lösung:

Bei den geöffneten Standorten A und B kann die Belieferung optimiert werden:

Optimale Belieferungsstrategie:

  • Abnehmer 1: vollständig von A beliefern (da \(c_{A1} = 1 < c_{B1} = 4\))
  • Abnehmer 2: möglichst viel von A beliefern (da \(c_{A2} = 2 < c_{B2} = 5\))
  • Abnehmer 3: von B beliefern

Verbesserte Lösung: \(\gamma_A = 1\), \(\gamma_B = 1\), \(\gamma_C = 0\)

  • \(x_{A1} = 200\) (Abnehmer 1 vollständig von A)
  • \(x_{A2} = 200\) (maximale Belieferung von Abnehmer 2 durch A)
  • \(x_{B2} = 100\) (Restbedarf von Abnehmer 2)
  • \(x_{B3} = 250\) (Abnehmer 3 vollständig von B)

Gesamtkosten: \(Z = 2.200 + 600 + 2.000 = 4.800\)

Verbesserung: Die ursprüngliche Lösung kostete 4.950, die verbesserte Lösung kostet 4.800, was eine Ersparnis von 150 bedeutet.

Begründung: Durch die stärkere Nutzung des günstigeren Standorts A für Abnehmer 2 (200 statt 150 Einheiten) werden die Transportkosten reduziert, während alle Kapazitätsbeschränkungen eingehalten bleiben.

Aufgabe 4 - Heuristiken zur Standortplanung

Ein mittelständisches Unternehmen plant die Versorgung von drei regionalen Abnehmern. Folgende Daten liegen vor:

Transportkosten \(c_{ij}\) [€/ME], Fixkosten und Kapazitäten:

Standort \(i\) Abnehmer 1 Abnehmer 2 Abnehmer 3 Fixkosten \(f_i\) Kapazität \(b_i\)
A 4 4 9 60 25
B 8 7 2 60 20
C 6 3 5 70 25

Bedarfe: \(d_1 = 20\), \(d_2 = 10\), \(d_3 = 10\)

  1. Wenden Sie die Add-Heuristik an, um eine Lösung zu bestimmen. Dokumentieren Sie jeden Schritt.
  2. Sind heuristische Lösungen optimal? Begründen Sie Ihre Antwort.
  3. Auf welcher Managementebene sind Standortentscheidungen angesiedelt und warum?

Lösung:

  1. Add-Heuristik:

Schritt 1: Bestimme den besten Einzelstandort für vollständige Belieferung aller Abnehmer:

  • Standort A: Fixkosten 60 + Transportkosten \((4 \cdot 20 + 4 \cdot 10 + 9 \cdot 10) = 60 + 210 = 270\) €
  • Standort B: Fixkosten 60 + Transportkosten \((8 \cdot 20 + 7 \cdot 10 + 2 \cdot 10) = 60 + 250 = 310\) €
  • Standort C: Fixkosten 70 + Transportkosten \((6 \cdot 20 + 3 \cdot 10 + 5 \cdot 10) = 70 + 200 = 270\) €

Start mit Standort A (270 €, willkürlich)

Schritt 2: Prüfe Vorteilhaftigkeit eines zweiten Standorts:

Zusätzlich Standort B:

  • Abnehmer 3: Wechsel von A zu B → Einsparung: \((9-2) \cdot 10 = 70\) €
  • Zusätzliche Fixkosten: 60 €
  • Nettovorteil: \(70 - 60 = 10\) € ✓

Zusätzlich Standort C:

  • Abnehmer 2: Wechsel von A zu C → Einsparung: \((4-3) \cdot 10 = 10\) €
  • Abnehmer 3: Wechsel von A zu C → Einsparung: \((9-5) \cdot 10 = 40\) €
  • Zusätzliche Fixkosten: 70 €
  • Nettovorteil: \(50 - 70 = -20\) € ✗

Wähle Standort B zusätzlich

Schritt 3: Prüfe dritten Standort C (mit A und B bereits gewählt):

  • Abnehmer 2: Wechsel von A zu C → Einsparung: \((4-3) \cdot 10 = 10\) €
  • Zusätzliche Fixkosten: 70 €
  • Nettovorteil: \(10 - 70 = -60\) € ✗

Ergebnis Add-Heuristik:

  • Standorte: A und B
  • Zuordnung: Abnehmer 1 und 2 von A, Abnehmer 3 von B
  • Kosten: \(60 + 60 + 4 \cdot 20 + 4 \cdot 10 + 2 \cdot 10 = 120 + 80 + 40 + 20 = 260\) €
  1. Optimalität:

Heuristische Lösungen sind nicht notwendigerweise optimal, da:

  • Sie nur lokale Verbesserungen betrachten
  • Nicht alle Kombinationen systematisch geprüft werden

Die tatsächlich optimale Lösung müsste durch vollständige Enumeration oder Optimierungsverfahren ermittelt werden.

  1. Managementebene:

Standortentscheidungen sind auf der strategischen Managementebene angesiedelt, da sie:

  • Langfristige Auswirkungen haben (mehrere Jahre bis Jahrzehnte)
  • Hohe Investitionen erfordern
  • Schwer reversibel sind
  • Die Wettbewerbsposition fundamental beeinflussen
  • Mit der Unternehmensstrategie abgestimmt werden müssen