Einsendearbeit SoSe20 PDF

Preview

Summary

Sommersemester...

Description

Fakultät für Wirtschaftswissenschaft

Einsendearbeit zum Modul

31801 Problemlösen in graphischen Strukturen

Kurs

00857 Optimierung mit Intelligenten Strategien

Kurseinheit

1

Rechtswissenschaftliche Diese Einsendearbeit muss bis zu dem Ihnen bekanntgemachten Termin in Moodle hochgeladen werden. Eine spätere Fakultät Einreichung ist nicht möglich.

A. Vorbemerkungen 1. 2. 3.

Zur Erlangung der Teilnahmeberechtigung an der Abschlussklausur müssen Sie mindestens die Hälfte der vorgesehenen Einsendearbeiten fristgerecht und erfolgreich bearbeitet haben.

Nach dem Ausschlusstermin werden die eingegangenen Einsendearbeiten korrigiert. Ihre korrigierte Arbeit steht Ihnen dann schnellstmöglich über Moodle zur Verfügung. Allgemeine Lösungshinweise können vier Tage nach Ende der Abgabefrist heruntergeladen werden.

B. Hinweise zur Bearbeitung 1.

Bitte verwenden Sie nur A4-Vorlagen für Ihre Dokumente.

2.

Fügen Sie bitte auf jeder Seite oben links Ihren Namen mit Matrikel-Nr. ein!

3.

Lassen Sie bitte das rechte Drittel einer jeden Seite für Korrekturbemerkungen frei!

4.

Bitte reichen Sie vorzugsweise PDF-Dokumente über Moodle ein.

Mit der Abgabe versichern Sie, dass Sie die eingereichte Einsendearbeit selbständig bearbeitet haben.

© FernUniversität in Hagen Alle Rechte vorbehalten 2020

00857-3-01-A1 002 625 903 (04/20)

Fakultät für Wirtschaftswissenschaft

Einsendearbeit zum Kurs 00857 Optimierung mit Intelligenten Strategien Kurseinheit 1 von 1

zur Erlangung der Teilnahmeberechtigung an der Prüfung zum Modul 31801

Problemlösen in graphischen Strukturen

Hinweise: 1. Die Einsendearbeit umfasst 3 Aufgaben. 2. Insgesamt sind max. 100 Punkte erreichbar. 3. Bei jeder Aufgabe ist die erreichbare Punktzahl vermerkt. 4. Sie benötigen mindestens 50 Prozent der insgesamt erreichbaren Punktzahl, damit diese Einsendearbeit als erfolgreich bearbeitet gelten kann.

002 625 903 (04/20)

00857-3-01-A1

Modul 31801: Problemlösen in graphischen Strukturen Kurs 00857: Optimierung mit Intelligenten Strategien

1

Einsendearbeit Aufgabe 1

30 Punkte

Sie besitzen ein Transportschiff, mit dem Sie Güter von den Häfen (A oder B) nach (C oder D) transportieren. Grundsätzlich in Frage kommen die in Tabelle 1.1 zusammengestellten (einmaligen) Frachtaufträge. Mit einer Fahrt Tabelle 1.1: Potentielle Frachtaufträge

Auftrag

Start

1 2 3 4

A A B B

Ziel Liefer- Gewinn datum [Te] C 4 6 D 7 9 C 4 7 D 9 4

kann nur ein Auftrag übernommen werden; für den nächsten Auftrag muss das Schiff wieder zu A oder B zurück. Akzeptieren Sie einen Auftrag, so muss bis einschließlich zum genannten Datum geliefert werden, da ansonsten (hohe) Strafzahlungen fällig werden und kein Gewinn entsteht. Der Auftrag wird dann deshalb nicht angenommen, die Fahrt entsprechend ohne Fracht durchgeführt. In Tabelle 1.2 stehen die für alle Fälle anzunehmenden Fahrzeiten (in Tagen [d]) der Schiffe von A/B nach C/D sowie die Zeiten für die Rückfahrten. Ziel ist es, alle Aufträge anzunehmen, die realisiert werden können und die in der Summe den höchsten Gewinn bringen. Tabelle 1.2: Fahrzeiten der Frachtschiffe

[d] nach von A B

C

D

3 2

2 3

[d] nach von C D

A

B

2 1

1 2

Ihnen stellt sich nun folgende Aufgabe: Sie planen Ihre Transporte für die nächsten 10 Tage und wollen in diesem Zeitraum mindestens 10 Te erwirtschaften. Als Verfahren setzen Sie die Breitensuche ein, wobei folgende Regeln einzuhalten sind. • Ein Knoten wird nur dann expandiert d. h. die Nachfolger werden nur dann (in alphabetischer Reihenfolge) generiert, wenn die Ankunft am Zielort der zugehörigen Fahrt am Tag 10 oder früher erfolgt. Ansonsten wird dieser Ast nicht gezeichnet. • Sie beenden die Suche nach einer geeigneten Kombination von Aufträgen, wenn Sie Ihr Ziel, mindestens 14 Te zu erwirtschaften, erreicht haben. Weitere Knotenexpansionen finden danach nicht mehr statt.

002 625 903 (04/20)

00857-3-01-A1

2

SS 2020 • Beginnen Sie im Heimathafen H (zum Zeitpunkt 0); die Fahrten zu A und B dauern beide 1 Tag. Zeichnen Sie unter Beachtung der obigen Anforderungen den zugehörigen Suchbaum. Notieren Sie an jedem Knoten gemäß nebenstehender Vorgabe den

1 1 A

0 H

1 1 B

Tag der Ankunft und am Pfeil die Fahrtzeit. Bewerten Sie jedes Blatt des Suchbaums mit dem dort realisierbaren Gewinn. Notieren Sie den nach Abbruch des Verfahrens maximalen Gewinn, und geben Sie an, welche Frachtaufträge dazu in welcher Reihenfolge ausgeführt werden müssen.

Aufgabe 2

35 Punkte

Ein Bandabgleichproblem bestehe in der Abtaktung eines Bandes für vierzehn Vorgänge bei vier Stationen. Ziel ist es, die vorgegebene Taktzeit von 17 ZE in jedem Fall einzuhalten. Die Vorgangsdauern entnehmen Sie Tabelle 2.1. Tabelle 2.1: Vorgangsdauern zum Bandabgleich

Vorgang: 1 Dauer (ZE): 6

2 6

3 3

4 6

5 5

6 8

7 5

8 5

9 8

10 11 12 13 14 5 1 2 2 1

Die Vorrangbeziehungen entnehmen Sie Abbildung 2.1. 2

3

8

6

9

12

1

14

4

5

10

7

11

13

Abbildung 2.1: Vorranggraph zum Bandabgleich

002 625 903 (04/20)

00857-3-01-A1

Modul 31801: Problemlösen in graphischen Strukturen Kurs 00857: Optimierung mit Intelligenten Strategien

3

a) Die Vorgangsreihenfolge x0 = [1|2|3|4|5|6|7|8|9|10|11|12|13|14] erfüllt offensichtlich die Vorrangbeziehungen. Ordnet man die Vorgänge in gewohnter Weise den Stationen zu, so ist festzustellen, ob das Ziel der Einhaltung der Taktzeit von 17 ZE bei vier Stationen eingehalten werden kann. Wenn ja, ist eine hinreichend gute Lösung gefunden. Wenn nicht, sei die Summe der Dauern der nicht mehr auf den vier Stationen eingelasteten Vorgänge ein Maß für die Qualität der (dann noch nicht den Anforderungen gerecht werdenden) Lösung. Diesen Wert gilt es zu minimieren; er ist im Optimum gleich 0. Notieren Sie den Wert für die angegebene Vorgangsreihenfolge x0 ; nutzen Sie Tabelle 2.2. b) Das vorliegende Problem soll mittels Tabu-Search gelöst werden. Zur Erzeugung der Nachbarschaft kommt die Operation Vertauschen zur Anwendung: Vertauschen bewirkt, dass zwei Vorgänge in den Positionen i und j vertauscht werden. Ist die durch den Vorranggraph gegebene Vorrangbeziehung verletzt, wird die Operation verworfen, d.h. nicht durchgeführt. Für die Erzeugung der Nachbarschaft werden jeweils Paare von Tauschpositionen (i-j) zufällig erzeugt. Es wird immer nur eine Tauschoperation bei der aktuellen Lösung durchgeführt. Die ersten drei sich ergebenden gültigen Reihenfolgen bilden dann die vollständig zu untersuchende Nachbarschaft. Ermitteln Sie zu x0 die vollständig zu untersuchende Nachbarschaft, die sich auf Basis folgender Paare ergibt: (3-8), (3-4), (6-7), (4-9), (10-11), (811). Tragen Sie Ihr Ergebnis in Tabelle 2.2 ein. Bestimmen Sie auch jeweils den Zielfunktionswert. c) Die Informationen zu einem Tausch sollen in der Tabu-Liste mittels Attribut zur Eigenschaft »Wert der i-ten Komponente« gespeichert werden. Notieren Sie in Zeile c) der Tabelle 2.2 die neue Lösung x1 und darunter in der Zeile c-F) den notwendigen Eintrag in die Tabu-Liste für das fromAttribut und in Zeile c-T) den für das to-Attribut. d) Wäre die Reihenfolge xk = [1|2|8|4|5|7|3|6|10|9|11|13|12|14] zulässig, wenn bei Betrachtung des from-Attributs c-F) noch in der tabu-Liste stehen würde? Bitte begründen Sie Ihre Antwort. e) Wäre die Reihenfolge xk = [1|2|8|4|5|7|3|6|10|9|11|13|12|14] zulässig, wenn bei Betrachtung des to-Attributs c-T) noch in der tabu-Liste stehen würde? Bitte begründen Sie Ihre Antwort. f) Welcher Zielfunktionswert ergibt sich für die Reihenfolge xk = [1|2|8|4|5|7|3|6|10|9|11|13|12|14]?

002 625 903 (04/20)

00857-3-01-A1

4

SS 2020 Tabelle 2.2: Lösungsschema

i a)

xi bzw. N (xi ) x0 = [1|2|3|4|5|6|7|8|9|10|11|12|13|14]

f (xi )

b1) b2) b3) c) Attribute c-F) c-T)

Aufgabe 3

35 Punkte

Im vorliegenden Fall soll ein Großkunde von einem Depot aus mit Waren beliefert werden. Einziges Ziel sei es, möglichst wenig Fahrten für die Belieferung durchzuführen, die LKWs also so zu beladen, dass möglichst wenig Leerraum entsteht. Die zur Verfügung stehenden LKWs haben ein zulässiges Gesamtgewicht von 7,5 t und ermöglichen eine Zuladung von 2500 kg, die voll ausgeschöpft werden kann. Zehn Objekte sind auszuliefern; ihr Gewicht entnehmen Sie Tabelle 3.1. Tabelle 3.1: Transportgewicht der Waren

Objekt: Gewicht (100 kg):

1 2 3 12 15 6

4 7

5 9

6 7 10 7

8 4

9 3

10 2

a) Wieviele LKW-Fahrten sind mindestens erforderlich? Begründen Sie Ihre Antwort der durchgeführten Berechnung. b) Die Objekte werden in einer als Liste gegebenen Reihenfolge verladen; sobald ein Objekt in einen LKW nicht mehr hinein passt, wird dieser verschlossen und macht sich auf den Weg. So bedeutet (1, 2, 3, 4, 5, 6, 7, 8, 9, 10), dass Objekt 1 in den ersten und Objekt 10 in den letzten LKW geladen wird. Wieviele LKW-Fahrten sind bei dieser Reihenfolge erforderlich? c) Beladungsreihenfolgen geben eine Lösung des beschriebenen Problems an und entsprechen dem Genotyp eines Individuums beim Genetischen Algorithmus.

002 625 903 (04/20)

00857-3-01-A1

Modul 31801: Problemlösen in graphischen Strukturen Kurs 00857: Optimierung mit Intelligenten Strategien

5

i) Geben Sie eine Regel für das Crossover derart an, dass das Verheiraten zweier Elternindividuen in jedem Fall zu zulässigen Lösungen führt. Beschreiben Sie kurz das Vorgehen. ii) Notieren Sie mindestens zwei weitere Crossover-Operatoren und machen Sie eine Aussage bezüglich Ihrer Anwendbarkeit für das beschriebene Problem. iii) Neben I10 = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) sei I 20 = (10, 9, 8, 7, 6, 5, 4, 3, 2, 1) ein zweites Individuum, bei dem diesmal die Objekte in umgekehrter Reihenfolge beladen werden. Erzeugen Sie gemäß Ihrer beschriebenen Methode mit den beiden bekannten Individuen sowie zwei weiteren in Tabelle 3.2 notierten Individuen I 30 und I40 vier Nachkommen I11 , I21 , I 31 , I41. iv) Nennen Sie eine geeignete Fitnessbewertung, und bestimmen Sie die Fitness aller Individuen. Tabelle 3.2: Lösungsschema mit Elternindividuen Nachkommen

= (1,2,3,4,5,6,7,8,9,10)

r 6

I20 = (10,9,8,7,6,5,4,3,2,1)

6

I 12 =

I30 = (4,7,1,3,2,9,8,6,5,10)

3

I 13 =

I40 = (5,7,2,3,9,10,6,1,8,4)

3

I 14 =

Elternindividuen

I10

Fitness

002 625 903 (04/20)

I 11

Fitness

=

00857-3-01-A1...