Dynamisches Programmieren | MathePrisma

Dynamisches Programmieren

Staplerfahren

Einleitung

Staplerfahren

Dyn. Programmieren

konkreter Fall

Selbst verfolgen

Arbeitsblatt

Aufgabe 1

(Zeit statt Strecke)

Statt die Länge des zurückgelegten Weges möchte man gewöhnlich lieber die benötigte Zeit minimieren.

a) Unter welchen (idealisierten) Voraussetzungen ist die Minimierung des Weges gleichbedeutend mit der Minimierung der Zeit?

b) Das Wenden eines Staplers innerhalb einer Gasse wird in der Regel einige Zeit kosten, ohne dass dabei Weg zurückgelegt wird. Geben Sie eine Möglichkeit an, wie man dies im Rahmen der vorgestellten Wegminimierungsaufgabe trotzdem berücksichtigen könnte.

Aufgabe 2

(Vergleich der Wege)

Im Applet der letzten Seite werden für jede zu befahrene Gasse stets ein roter (minimale Länge bei Ausfahrt am Nord-Ende) und ein blauer (minimale Länge bei Ausfahrt am Süd-Ende) Weg betrachtet.

Um wieviel unterscheiden sich die Längen der beiden Wege höchstens? Begründen Sie Ihre Antwort.

Aufgabe 3

(0/1-Rucksack)

Gegeben sind ein Rucksack mit einem Fassungsvermögen V und n Gegenstände G $_1$ ,..,G $_{\text{n}}$ . Gegenstand G $_{\text{i}}$ besitzt das Volumen V $_{\text{i}}$ und erbringt einen Ertrag E $_{\text{i}}$ .

Gesucht ist eine Füllung des Rucksacks mit Gegenständen, so dass der Gesamtertrag maximal ist ("optimale Füllung"). Das Gesamtvolumen der Gegenstände darf dabei natürlich V nicht überschreiten.

a) Bestimmen Sie eine solche optimale Füllung für das folgende Beispiel:

V = 100, n=10

G $_1$ : V $_1$ = 10, E $_1$ = 5
G $_2$ : V $_2$ = 20, E $_2$ = 8
G $_3$ : V $_3$ = 5, E $_3$ = 20
G $_4$ : V $_4$ = 30, E $_4$ = 30
G $_5$ : V $_5$ = 25, E $_5$ = 20
G $_6$ : V $_6$ = 15, E $_6$ = 10
G $_7$ : V $_7$ = 5, E $_7$ = 4
G $_8$ : V $_8$ = 10, E $_8$ = 12
G $_9$ : V $_9$ = 10, E $_9$ = 5
G $_{10}$ : V $_{10}$ = 25, E $_{10}$ = 25

b) Diese Aufgabe kann mit Dynamischem Programmieren gelöst werden. Bearbeiten Sie dazu folgende Fragen und Aufgaben:

Durch welche Optimalitätsbedingung ist die gesuchte Lösung charakterisiert?
Geben Sie verwandte Probleme kleinerer Größe an, die eine entsprechende Optimalitätsbedingung erfüllen. Mögliche Lösungen größerer Probleme sollen sich durch Erweiterung der Lösungen kleinerer Probleme gewinnen lassen. Was ist die Problemgröße?
Formulieren Sie ein Kriterium, wonach die Erweiterung der Lösung eines kleineren Problems nicht auf eine Lösung eines größeren Problems führen kann.
Formulieren Sie einen Algorithmus, der auf dem Prinzip des dynamischen Programmierens beruht.
Illustrieren Sie die Arbeitsweise des Algorithmus an dem Beispiel aus a).

Drucken

Jede Gasse besitzt zwei Enden, ein Nord- und ein Süd-Ende. Durch eines der Enden wird in die Gasse eingefahren, durch eines wird ausgefahren.

wie fährt man?

Wird die Gasse vollständig durchfahren, sind Ein- und Ausfahrt an verschiedenen Enden

Wird in der Gasse gewendet, sind Ein- und Ausfahrt am gleichen Ende

Start und Ziel ist jeweils die Verpackungsstation.

vereinfachende Einschränkung

Wird in eine Gasse eingefahren, werden immer alle dort liegenden Picks kommissioniert. Man fährt deshalb immer mindestens bis zum letzten Pick dieser Gasse vor, bevor man eventuell wendet.

Wie realistisch ist diese Einschränkung?

Auf diesem Grundriss sind die Gassen-Enden gelb markiert.
Durch Anklicken der Enden, jeweils abwechselnd als Ein- und Ausfahrt, fahren Sie einen Weg durch das Lager. Sie müssen an jedem Pick vorbeikommen. Klicken Sie auf die Verpackungsstation, wenn Sie alle Picks kommissioniert haben.
Vergleichen Sie Ihren Weg mit dem kürzesten.
"Reset" löscht den Weg.
"Neuer Auftrag" verteilt neue Picks.
"Lösung" gibt die optimale Lösung aus.
"schrittweise" erlaubt es, den Weg nochmals genau zu verfolgen.