Dynamisches Programmieren

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

die Situation

In einem Lager werden Pakete zusammengestellt mit Waren, die an verschiedenen Plätzen gelagert sind. Dazu fährt ein Staplerfahrer mit dem Paket die einzelnen Lagerplätze an und packt die Ware in das Paket.
In der Sprache der Logistik: Der Staplerfahrer kommissioniert einen Auftrag, indem er die Ware an den Lagerplätzen pickt.

die Frage

Wie bestimmt man einen optimalen (=kürzestmöglichen) Weg für den Staplerfahrer?

der Hintergrund

Diese Fragestellung wurde am Fachbereich in einer Kooperation im Rahmen eines studentischen Praktikums bei der Firma LCiG Logistik und Informatik Consulting GmbH bearbeitet.
Zur Lösung wird dabei das algorithmische Prinzip des dynamischen Programmierens verwendet.

Das nebenstehende Bild stellt einen einfachen Lagergrundriss dar. Klicken Sie auf die Knöpfe, um sich mit den Symbolen und Begriffen vertraut zu machen.

slideshow1Lager

slideshow1Verpstat

slideshow1Regale

slideshow1Gassen

slideshow1Weg