Lade Inhalt...

Theoretische Grundlagen der Standortoptimierung mit nichtlinearen Abstandsfunktionen in Wirtschaft, Industrie und Technik

Bachelorarbeit 2013 43 Seiten

Mathematik - Sonstiges

Leseprobe

Inhaltsverzeichnis

1 Einführung … 3

2 Mathematische Grundlagen des Standortproblems … 5
2.1 Mathematische Formulierung … 5
2.2 Praktische Bedeutung des Abstandsbegriffs … 5

3 Eigenschaften der Abstandsfunktion … 8
3.1 Algebraische und topologische Eigenschaften … 8
3.2 Lipschitz-Stetigkeit … 15
3.3 Differenzierbarkeitseigenschaften … 18
3.3.1 Das Fréchet Subdifferential … 21
3.3.2 Das Mordukhovich Subdifferential … 26

4 Optimalitätsbedingungen … 29

5 Vergleich mit anderen Abstandsfunktionen … 34

6 Beispielrechnung … 36

7 Schlussbetrachtung … 42

Abbildungsverzeichnis

1 Skizze zum Beweis von Proposition 3.2 … 10
2 Beispiel: Standortproblem für n = 4 … 41

1 Einführung

Standortoptimierung umfasst ein weites Gebiet von Anwendungen. Die Ermittlung eines geeigneten Standorts hat eine große Bedeutung für Wirtschaft, Industrie und Technik. Bei der Standortsuche spielen viele Faktoren eine Rolle. Beispiele sind Umweltfaktoren, Lohnniveau, Infrastruktur (z. B. Autobahnanbindungen oder Flughäfen), Grundstückspreise, Bildungsangebot und klimatische Bedingungen.

Neben der Verfügbarkeit von Rohstoffen sind auch Transportkosten und die Nähe von Zulieferbetrieben wichtige Standortfaktoren. Als praktische Anwendung wäre hier die Errichtung von Paketzentren und Lagerhallen von Versandhäusern zu nennen.

Onlineshops sind auf Grund ihres großen Angebots sehr beliebt, allerdings wird von ihnen auch eine schnelle Lieferung erwartet. Diese Tatsache führte bereits in den letzten Jahren dazu, dass Logistikzentren in der Nähe großer Städte gebaut wurden, um teilweise eine Lieferung am Tag der Bestellung zu gewährleisten [vgl. 5].

Da jedes Lager für mehrere Städte oder Bezirke verantwortlich ist, sollte der Standort so gewählt werden, dass die Summe der Entfernungen zwischen Lager und Zielstadt so klein wie möglich wird.

Auch der Pakethandel hat wegen der zunehmenden Bestellungen im Internet Konjunktur. Deshalb sollen zukünftig vermehrt Paketzentren in Deutschland errichtet werden, um die bisher 32 Umschlagszentren zu entlasten. Ziel ist es sogar, das Paket so schnell wie den Brief werden zu lassen [vgl. 4].

Neben diesem aktuellen Beispiel gibt es noch zahlreiche Anwendungen der Methoden, mit denen sich diese Arbeit beschäftigt. Weitere Möglichkeiten sind Einzugsbereiche von Schulen, Planung neuer Krankenhäuser oder Feuerwehrstationen, aber auch die Errichtung von Hotels und Parkplätzen.

Die vorliegende Arbeit befasst sich hauptsächlich mit den theoretischen Grundlagen, die notwendig für die Lösung dieser Probleme sind.

Anstoßgebend für das Thema meiner Bachelorarbeit war ein Artikel von Nam und Zǎlinescu [13], der sich mit einer völlig neuen Herangehensweise an das Problem der Standortoptimierung beschäftigt. Bei dieser Methodik wird keine Norm als problemspezifische Abstandsfunktion benötigt. Dies hat den Vorteil, dass Standortprobleme, auf die der geometrische Algorithmus1 nicht angewendet werden kann, mit der hier behandelten Vorgehensweise gelöst werden können.

Für meine Bachelorarbeit habe ich die Voraussetzungen aus [13] an das Standortproblem angepasst und vereinfacht. Nam und Zǎlinescu arbeiten beispielsweise mit reellen, normierten, linearen Räumen. In dieser Arbeit verwende ich in Anlehnung an geografische Koordinaten den zweidimensionalen reellen Vektorraum.

Auch die Beweise aus Kapitel 3 und 4 basieren auf dem Artikel [13], wurden allerdings für die vorliegende Arbeit von mir ausformuliert.

Nachdem ich die Eigenschaften der nichtlinearen Zielfunktion und die Optimalitätsbedingungen des Standortproblems vorgestellt und bewiesen habe, stellte ich einen Vergleich mit den bisher bekannten Methoden an.

Des Weiteren beschäftigte ich mich mit dem Abstandsbegriff und dessen praktisch relevanten Eigenschaften.

Zur Verdeutlichung der theoretischen Ergebnisse dieser Arbeit konstruierte und löste ich abschließend ein mathematisches Beispiel.

2 Mathematische Grundlagen des Standortproblems

Nachdem in der Einleitung die Notwendigkeit von Standortoptimierung anhand von praktischen Beispielen veranschaulicht wurde, wird im Folgenden das mathematische Optimierungsproblem aufgestellt.

2.1 Mathematische Formulierung

Gegeben ist eine endliche Anzahl von nichtleeren, abgeschlossenen Mengen Ωi _ R2 für i = 1, …, n und n Richtungsvektoren vi (i = 1, …, n). Weiterhin existiert eine nichtleere, abgeschlossene Menge Ω0 _ R2, die als zulässiger Bereich dient. Gesucht ist nun ein Punkt x _ Ω0, so dass die Summe der Entfernungen von x zu Ωi (i = 1, …, n) minimal wird. Der Abstand zwischen dem gesuchten Punkt und den gegebenen Mengen wird in diesem Modell anhand der Richtungsvektoren gemessen. Als Abstandsfunktion wird folgendes Funktional verwendet
Tvi(x,Ωi) := inf{t ≥ 0 │ x + tvi _ Ωi}. (1)

Somit ergibt sich das Optimierungsproblem
min x_Ω0 S(x), (P)
wobei die Zielfunktion S(·) gegeben ist durch
S(x) := ∑ni=1 Tvi (x,Ωi) mit x _ Ω0. (2)

2.2 Praktische Bedeutung des Abstandsbegriffs

Bei der hier betrachteten Abstandsfunktion handelt es sich nicht um eine Metrik, da sie nicht symmetrisch ist, wie das folgende Beispiel zeigen wird.

Beispiel 1. Sei Ω := {w} eine Einpunktmenge und Tv die Abstandsfunktion zu festem v _ R2 mit v ≠ 0, wobei
w := (12) und v := (11)
sei. Betrachtet wird der Punkt x = (-10) _ dom Tv. Dann ist Tv(x,Ω) = 2, denn es gilt x + 2v = w _ Ω.

Sei nun Ω := {x}. Dann existiert kein t ≥ 0, so dass w + tv = x ist. Es folgt Tv (w, Ω) = ∞ und somit gilt nicht Tv(x,w) = T v(w,x), wie es hingegen für Metriken gilt.

Für Einpunktmengen Ω := {w} und Ω := {x} gilt allerdings immer
Tv1(x,Ω) = Tv2(w,Ω)
mit v1 = -v2.

Wie man in Beispiel 1 sieht, ist die Abstandsfunktion Tv(·,Ω) zu festem v nicht für alle x _ R2 definiert. Von daher ist die Wahl der Richtungsvektoren vi für das Standortproblem (P) äußerst wichtig. Verändert man die Richtungsvektoren 0 ≠ vi _ R2, so kann sich auch die Optimallösung des Standortproblems ändern, ggf. sogar verbessern. Betrachtet man das Standortproblem hingegen vom praktischen Aspekt, so werden die Richtungen aufgrund des gegebenen Straßenverlaufs bestimmt. In Folge dessen wäre eine Veränderung der Richtungen nicht effektiv.

Das Infimum der Abstandsfunktion (1) wird immer in Abhängigkeit zum verwendeten Richtungsvektor angegeben. Daher ist es wichtig, nicht nur die Funktionswerte, sondern auch die Richtungsvektoren zu betrachten, wenn Entfernungen verglichen werden sollen.

Beispiel 2. Gegeben seien zwei Funktionswerte Tvi = 0,5 und Tv2 = 6 mit Richtungen
v1 = (129) und v2 = (10,75).

Betrachtet man nur die Funktionswerte, so erscheint die erste Entfernung um einiges geringer zu sein als die zweite. Werden allerdings auch die Richtungsvektoren berücksichtigt, erkennt man, dass für alle x _ R2 gilt

x + 0;5 · (129) = x + 6 · (10,75).

Es wird also für beide Vektoren und Funktionswerte der gleiche Punkt erreicht.

Wie bei der Norm2 auch, sollte man also keine Abstände miteinander vergleichen, wenn sie auf verschiedenen Richtungsvektoren basieren.

Um Entfernungen besser bewerten zu können, kann man die Richtungsvektoren normieren. Sofern keine bestimmten Vorgaben [vgl. Kapitel 5] gemacht werden, ist es bei der hier betrachteten Problemformulierung auch möglich jede Richtung durch eine andere Norm anzugeben.

Betrachtet man noch einmal Beispiel 2, so erkennt man leicht, dass Tv(·,Ω) umso größer ist, je geringer der Betrag des Vektors v gewählt wird. Damit wirkt sich die Wahl des Richtungsvektors auch auf den Zielfunktionswert des Standortproblems (P) aus. Dies ist praktisch relevant, wenn man durch die Zielfunktion nicht nur die Entfernung zwischen den Standorten repräsentieren will, sondern auch die Zeit, die man benötigt, um von einem Ort zum anderen zu gelangen. Ist z. B. auf einer Verbindungsstraße zweier Orte nur eine geringe Höchstgeschwindigkeit erlaubt, so kann dieser Sachverhalt durch einen Richtungsvektor mit kleinem Betrag in dem Optimierungsproblem dargestellt werden.

Da man die hier behandelte Abstandsfunktion gesondert von den bisher bekannten betrachten muss, werden im nächsten Kapitel einige Eigenschaften vorgestellt und bewiesen.

3 Eigenschaften der Abstandsfunktion

Dieses Kapitel beschränkt sich auf das Funktional (1). Im nächsten Kapitel wird sich zeigen, dass sich die Eigenschaften des einzelnen Funktionals (1) auf die Summe der Funktionale und damit auf die Zielfunktion (2) übertragen lassen.

Die Aussagen wurden anlässlich des Standortproblems für den zweidimensionalen reellen Raum R2 formuliert, lassen sich aber ohne weiteres auf einen beliebigen endlichdimensionalen, reellen, normierten, linearen Raum übertragen.

Die Theoreme und deren Beweise beruhen auf den Formulierungen des Artikels [13]. Wurden zusätzliche Informationen herangezogen, so sind diese Stellen durch einen Verweis auf die Quelle gekennzeichnet.

3.1 Algebraische und topologische Eigenschaften

Dieser Abschnitt behandelt grundlegende Eigenschaften, wie den Definitionsbereich, Stetigkeit und Konvexität.

Im Vorfeld werden an dieser Stelle zwei wesentliche mathematische Begriffe erklärt, deren Definition für das Verständnis der nachfolgenden Sätze erforderlich ist.

Für einen Vektor v _ R2 und eine Menge Ω _ R2 sei ein Skalarisierungsfunktional ϕv : R2 → R _ {+∞} definiert durch
ϕv (x,Ω) := inf{t _ R | x + tv _ Ω}.

Weiterhin ist der Rezessionskegel Ω bezüglich einer Menge Ω _ R2 definiert durch
:= {u _ R2 | w + λu _ Ω für alle w _ Ω und für alle λ ≥ 0}.

Proposition 3.1. Für den Definitionsbereich des Funktionals (1) gilt
dom Tv = Ω - cone{v}. (3)

Wenn ein Richtungsvektor v _ Ω gegeben ist, ergibt sich
dom Tv = Ω - span{v}, (4)
epi Tv = {(x,t) _ R2 x R | t ≥ 0,x + tv _ Ω} (5)
und
Tv(x,Ω) = max{ϕv (x,Ω), 0}. (6)

Beweis. Aus der Formulierung des Definitionsbereiches ergibt sich
dom Tv = {x _ R2 | Tv(x) < ∞}
= {x _ R2 | x + tv _ Ω für ein t ≥ 0}
= {x _ R2 | x _ Ω - tv für ein t ≥ 0}
= Ω - cone{v}.

Sei nun v _ Ω. Für jedes x _ Ω - span{v} existieren ein w _ Ω und ein λ _ R, so dass x = w - λv gilt. Ist λ ≥ 0, so folgt x _ Ω - cone{v} = dom Tv. Ist hingegen λ < 0, so gilt x = w + (-λ)v _ Ω, da v _ Ω. Da 0 _ span{v} ist, ist Ω + 0 = Ω _ dom Tv und damit x _ dom Tv. Die Inklusion dom Tv _ Ω - span{v} ist wegen (3) trivial.

Sei x _ R2 beliebig und Tv(x,Ω) = t. Dann ist x + tv _ Ω. Da v _ Ω ist, folgt (x+tv)+αv _ Ω für alle α ≥ 0. Das heißt x + βv _ Ω für alle β ≥ t und x + βv _ Ω für β < t. Nun folgt leicht, dass für den Epigraphen epi Tv = {(x,μ) _ R2 x R | Tv (x,Ω) ≤ μ} Gleichung (5) gilt.

Die Ungleichung Tv(x,Ω) ≥ max{ϕv(x,Ω), 0} ist offensichtlich. Um die andere Ungleichung zu beweisen, sei nun max{ϕv(x,Ω), 0} < λ. Dann gibt es ein t _ (-∞, λ) mit ϕv(x,Ω) = t. Also ist x + tv _ Ω. Dann folgt x + λv = x + tv + (λ - t)v _ Ω + R+v = Ω, da v _ Ω und somit Tv(x,Ω) ≤ λ. Also ist Tv(x,Ω) ≤ max{ϕv(x,Ω), 0} und somit gilt Gleichung (6).

Proposition 3.2. Das Infimum des Funktionals (1) wird für x _ dom Tv immer angenommen. Das bedeutet für die Projektion ∏v(x,Ω) := x + Tv (x,Ω)v
v(x,Ω) _ Ω für alle x _ dom Tv.

Es gilt sogar ∏v(x,Ω) _ bd Ω für alle x mit Tv(x,Ω) _ (0,∞).

Beweis. Sei x _ dom Tv und t := Tv (x,Ω). Dann existiert eine Folge tk → t mit tk _ [0, ∞) und x + t kv _ Ω für jedes k _ N0. Da Ω abgeschlossen ist, liegt auch der Grenzwert x + tv in Ω.

Sei nun t _ (0,∞). Angenommen ∏v(x,Ω) _ bd Ω. Dann ist ∏v(x,Ω) _ int Ω, d. h. es gibt ein δ > 0, so dass x+tv+B(0,δ) _ Ω und δ v/||v|| < tv gilt, wobei B(0,δ) einen Kreis um den Nullpunkt mit Radius δ darstellt [vgl. Abbildung 1]. Somit ist auch x+tv-δ/||v|| v _ Ω. Da t = inf{t ≥ 0 | x + tv _ Ω} ist, folgt t ≤ t – δ/||v|| , was ein Widerspruch ist. Demnach ist die Annahme ∏v(x,Ω) _ bd Ω falsch.

[Dies ist eine Leseprobe. Grafiken und Tabellen sind nicht enthalten.]
Abbildung 1: Die Projektion kann nicht im Inneren von liegen.

Proposition 3.3. Es gilt Tv(x,Ω) = 0 genau dann, wenn x _ Ω.

Beweis. Sei x _ Ω. Also ist x+0v _ Ω. Dann ist Tv(x,Ω) ≤ 0 und somit gilt Tv(x,Ω) = 0.

Sei nun Tv(x,Ω) = 0. Dann ist x = x + Tv(x,Ω)v _ Ω.

Proposition 3.4. Sei x _ dom Tv. Für 0 ≤ λ ≤ Tv (x,Ω) gilt
Tv (x + λv, Ω) = Tv (x,Ω) – λ. (7)

Ist λ > 0 und x - γv _ Ω für alle γ _ (0, λ], dann gilt
Tv (x – λv, Ω) = Tv (x,Ω) + |λ. (8)

Des Weiteren gilt für alle x _ R2 und t ≥ 0
Tv (x + tv,Ω) ≥ max{ Tv (x,Ω) – t, 0}. (9)

Die Gleichheit gilt, falls v _ Ω.

Beweis. Sei x _ dom Tv und 0 ≤ λ ≤ Tv (x,Ω). Da x + Tv (x,Ω)v _ Ω ist, ist auch x + λv + [Tv (x,Ω) - λ]v _ Ω. Also ist
Tv (x + λv, Ω) ≤ Tv (x,Ω) - λ < ∞. (10)

Sei t := Tv (x + λv, Ω) < ∞. Dann ist x + λv + tv _ Ω. Daraus folgt Tv (x,Ω) ≤ λ+t, also
Tv (x,Ω) - λ ≤ Tv (x + λv, Ω) (11)

Mit (10) und (11) folgt nun Tv (x + λv, Ω) = Tv (x,Ω) - λ.

Es wird nun die zweite Gleichung bewiesen. Sei y := x - λv. Dann ist x = y + λv und wegen (11) gilt Tv (y,Ω) = Tv (x – λv,Ω) ≤ T v (x,Ω)+λ < ∞. Dies impliziert y _ dom Tv. Da x - γv _ Ω für alle γ _ (0, λ], folgt y _ Ω und 0 < λ ≤ Tv (y,Ω) =: t. Dann ist y + tv = x - λv + tv = x - (λ - t)v _ Ω und somit λ - t _ (0, λ]. Daraus folgt, dass λ ≤ t = Tv (y,Ω) gilt. Mit (7) folgt nun T v (x,Ω) = Tv (y,Ω) - λ = Tv (x – λv,Ω) - λ. Also gilt (8).

Im Folgenden wird gezeigt, dass (9) gilt. Sei x _ dom Tv. Für t ≤ Tv (x,Ω) gilt wegen (11) die Ungleichung. Für t > Tv (x,Ω) ist max{ Tv (x,Ω) – t, 0} = 0 und die Ungleichung gilt laut der Definition des Funktionals (1). Ist x _ dom Tv, d. h. T v (x,Ω) = ∞, dann ist auch Tv (x + tv,Ω) = ∞. Die Ungleichung gilt somit.

Sei nun v _ Ω. Für Tv (x,Ω) = ∞ ist die Gleichung trivial. Also bleiben noch zwei Fälle zu betrachten:

1. Ist Tv (x,Ω) > t, so folgt x + tv + (Tv (x,Ω) - t)v = x + Tv (x,Ω) _ Ω und somit ist Tv (x + tv,Ω) ≤ T v (x,Ω) - t. Wegen der Gültigkeit der Ungleichung folgt die Gleichheit Tv (x + tv,Ω) = Tv (x,Ω) - t = max{ Tv (x,Ω) – t, 0}.

2. Ist Tv (x,Ω) ≤ t, so folgt x + tv = x + Tv (x,Ω)v + (t - Tv (x,Ω))v _ Ω + Ω = Ω. Also ist Tv (x + tv,Ω) = 0 = max{ Tv (x,Ω) – t, 0}.

[…]


1 Der geometrische Algorithmus zur Lösung von Standortproblemen arbeitet mit der Maximums- oder der Lebesguenorm als Abstandsfunktion [vgl. 8, S. 149-151].

2 Der Vergleich von Entfernungen, die auf verschiedenen Normen basieren, ist nicht aussagekräftig, da z. B. für die Lebesguenorm und die Maximumsnorm immer gilt ||x|| ≤ ||x||1.

Details

Seiten
43
Jahr
2013
ISBN (eBook)
9783668042810
ISBN (Buch)
9783668042827
Dateigröße
863 KB
Sprache
Deutsch
Katalognummer
v306320
Note
1,6
Schlagworte
Standortoptimierung Abstandsfunktion Abstandsbegriff nichtlineare Zielfunktion Standortfaktoren

Autor

Teilen

Zurück

Titel: Theoretische Grundlagen der Standortoptimierung mit nichtlinearen Abstandsfunktionen in Wirtschaft, Industrie und Technik