Algorithmen fur Ingenieure - realisiert mit Visual Basic 3834800155, 9783834800152 [PDF]

Zitiervorschau

Harald Nahrstedt Algorithmen for Ingenieurerealisiert mit Visual Basic

Lexikon fOr IT-Berufe

Grundkurs Theoretische Informatik

yon Peter Fetzer und Bettina Schneider

von Gottfried Vossen und Kurt-Ulrich Witt

Grundkurs IT-Berufe

Anwendungsorientlerte Wirtschaftsinformatik

von Andreas M. B6hm und Bettina Jungkunz

Pr0fungsvorbereitung fOr IT-Berufe von Manfred W~insche

Grundlegende Algorithmen von Volker Heun

Gmndkurs Programmieren mit Delphi von Wolf-Gert Matth~ius

Grundkurs Visual Basic von Sabine Kw

Visual Basic for technische Anwendungen von JOrgen Radel

Grundkurs SmalltalkO b j e k t o r i e n t i e r u n g von Anfang an von Johannes Brauer

Grundkurs Software-Entwicklung mit C++ von Dietrich May

Grundkurs JAVA von Dietmar Abts

Aufbaukurs JAVA von Dietmar Abts

Grundkurs Java-Technologien von Erwin Merker

Java ist eine Sprache yon Ulrich Grude

Middleware in Java von Steffen Heinzl und Markus Mathes

Das Linux-Tutorial - Ihr Weg zum LPl-Zertiflkat von Helmut Pils

Rechnerarchitektur von Paul Herrmann

Grundkurs Relationale Datenbanken von Ren~ Steiner

Grundkurs Datenbankentwurf von Helmut Jarosch

Datenbank-Engineering von Alfred Moos

Grundlagen der Rechnerkommunikation von Bernd SchOrmann

Netze - Protokolle - Speziflkationen von Alfred Olbrich

Grundkurs Verteilte Systeme von GUnther Bengel

Grundkurs Mobile Kommunikationssysteme von Martin Sauter

Grundkurs Wlrtschaftsinformatik von Dietmar Abts und Wilhelm M~lder

von Paul Alpar, Heinz Lothar Grob, Peter Weimann und Robert Winter

Business Intelligence - Grundlagen und praktische Anwendungen von Hans-Georg Kemper, Walid Mehanna und Carsten Unger

Grundkurs GeschMtsprozess-Management von Andreas Gadatsch

Prozessmodelllerung mlt ARIS | von Heinrich Seidlmeier

ITIL kompakt und verst~ndlich yon Alfred Olbrich

BWL kompakt und verstindlich yon Notger Carl, Rudolf Fiedler, William J6rasz und Manfred Kiesel

Masterkurs IT-Controlling von Andreas Gadatsch und Elmar Mayer

Masterkurs Computergraflk und Bildverarbeitung yon Alfred Nischwitz und Peter Haber~cker

Grundkurs Medlengestaltung von David Starmann

Grundkurs Web-Programmlerung von G~nter Pomaska

Web-Programmlerung von Oral Avcl, Ralph Trittmann und Werner Mellis

Grundkurs MySOJ. und PHP von Martin Pollakowski

Grundkurs SAP It/3 | von Andr~ Maassen und Markus Schoenen

SApe-gest0tztes Rechnungswesen von Andreas Gadatsch und Detlev Frick

Kostentrigerrechnung mit SAP R/3 | von Franz Klenger und Ellen Falk-Kalms

Masterkurs Kostenstellenrechnung mit S A P von Franz Klenger und Ellen Falk-Kalms

Controlling mit SAP | von Gunther Friedl, Christian Hilz und Burkhard Pedell

Logistikprozesse mit SAP It/3 | von Jochen Benz und Markus H~flinger

IT-Projekte strukturlert realisleren yon Ralph Brugger

Algorithmen for Ingenleure - realislert mit Visual Basic von Harald Nahrstedt

.............................................................

T......................................

Harald Nahrstedt

Algorithmen fi)r I ngen i e u r e realisiert mit V i s u a l Basic Eine anwendungsorientierte Einf(i hrung- Problemanalyse und L6sungsweg anhand konkreter Beispiele Mit 165 Abbildungen

v=eweg

Bibliografische Information Der Deutschen Bibliothek Die Deutsche Bibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet 0ber abrufbar.

Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnun8 nicht zu der Annahme, dass solche Namen im Sinne von Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten w~ren und daher von jedermann benutzt werden d0rfen. HSchste inhaltliche und technische Qualit~t unserer Produkte ist unser Ziel. Bei der Produktion und Auslieferung unserer B0cher wollen wir die Umwelt schonen: Dieses Buch ist auf s~iurefreiem und chlorfrei gebleichtem Papier gedruckt. Die Einschweil3folie besteht aus Poly~thylen und damit aus organischen Grundstoffen, die weder bei der Herstellung noch bei der Verbrennung Schadstoffe freisetzen.

1. Auflage Dezember 2005 Alle Rechte vorbehalten 9 Friedr. Vieweg & Sohn Verlag/GWV Fachverlage GmbH, Wiesbaden 2005 Lektorat: Dr. Reinald Klockenbusch /Andrea Brol31er Der Vieweg Verlag ist ein Unternehmen von Springer Science+Business Media. www.vieweg-it.de

Das Werk einschliel31ich aller seiner Teile ist urheberrechtlich s Jede Verwertung aul3erhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmun8 des Verlags unzulw und strafbar. Das gilt insbesondere for Vervielf~ltigungen, Ubersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. o.

Konzeption und Layout des Umschlags: Ulrike Weigel, www.CorporateDesignGroup.de Umschlagbild: Nina Faber de.sign, Wiesbaden Druck- und buchbinderische Verarbeitun8: Wilhelm & Adam, Heusenstamm Printed in Germany ISBN 3-8348-0015-5

Vorwort

Vo ort Warum dieses Buch

In Laufe meiner langj~hrigen beruflichen Erfahrung musste ich viele ingenieurm~.lgige Aufgaben 16sen. Dies gelang mir immer wieder, nach dem ich den ftir die L6sung richtigen Algorithmus gefunden hatte. Die Entwicklung eines Modells, die Suche nach dem Algorithmus und dessen formale Anwendung waren ftir mich immer die kreativsten Phasen eines L6sungsprozesses. Die Umsetzung des Algorithmus in die jeweilige Programmiersprache war dann ,,nur noch" handwerkliches K6nnen. So ergaben sich mit den Jahren die verschiedensten L6sungen im technischen Bereich mit den unterschiedlichsten Algorithmen. Damit wuchs aber auch mein Interesse an verschiedene Arten von Algorithmen und ihren M6glichkeiten. Mit Freude stelle ich fest, dass gerade in den letzten Jahren durch die sinnvolle Verkn~ipfung von Ingenieurwissenschaften und Informatik neue Mal~st~ibe gesetzt werden. Studienrichtungen wie Maschinenbauinformatik oder Ingenieurinformatik machen Hoffnung auf eine schnelle Weiterentwicklung. Ahnlich wie einst die Ingenieurdisziplin aus der Physik hervorgegangen ist, scheint auch die Informatik hier einen ~.hnlich kl~.renden Prozess zu erfahren. Hin zu einem Softwareingenieurwesen und weg vom Ktinstlertum und T~iftlerdasein. Ziel dieses Buches ist es, sowohl dem Ingenieurstudenten als auch dem praktizierenden Ingenieur Algorithmen und deren Anwendungsm6glichkeiten zu zeigen. Dabei kann und soil der Umfang dieses Buches nur einfache Anwendungen zeigen und so das Prinzip erkl~tren und das Interesse an einer Vertiefung des Stoffes wecken. So beschr~inken sich die mathematischen Herleitungen auf einfache Formen, ohne Untersuchung von Stetigkeit oder gC~ltigen Bereichen. Auch die Biologie hat schon immer die Ingenieurwissenschaften beeinflusst (Bionik) und erf~hrt im Moment ~iber die Informatik mit Prozessen aus der Natur neue Impulse. Dabei habe ich das Thema Neuronale Netze zun~.chst ausgespart. Vielleicht erlaubt mir eine sp~itere Ausgabe auch diesem Thema einige Seiten zu widmen. Ingenieure arbeiten oft in Teams. Dennoch werden durch Aufteilung bestehender Aufgaben die Probleme meist durch EinzelperV

Vorwort sonen gelOst oder zumindest stammt die Kernidee einer L6sung von dieser. Es ist die SchlOsselqualifikation eines Ingenieurs, diese Probleml6sungen zu liefern. In diesem Sinne ist ein Ingenieur auch forschend t~tig, soweit dies ihm zeitlich m6glich ist. Denn zeiteffektiv zu arbeiten, steht bei ihm an vorderster Stelle und so benOtigt er auch ein gutes Zeitmanagement. In diesem Sinne sollen die dargestellten Algorithmen auch zur schnelleren L6sungsfindung dienen.

Zum Aufbau Im ersten Kapitel gebe ich eine kurze l~lbersicht zur geschichtlichen Entwicklung von Algorithmen. Ebenso werden die Eigenschaften und Klassen von Algorithmen erl~tutert. Eine Betrachtung verwandter Begriffe schlielgt sich an. Die restlichen Kapitel haben eine grundlegende Einf~hrung zum Thema und die Anwendung des Algorithmus bis zur Realisierung an einem praktischen Beispiel. Dazu verwende ich die Entwicklungsumgebung von Microsoft Office Excel 2003.

Danksagung Ich danke all denen im Hause Vieweg, die stets im Hintergrund wirkend, zum Gelingen dieses Buches beigetragen haben. Ein besonderer Dank gilt meinem Lektor Dr. Reinald Klockenbusch. Er hat durch geduldiges Hinterfragen und mit wichtigen Ratschl~gen zu diesem Buch die richtigen Impulse gegeben.

An den Leser Dieses Buch soll auch zum Dialog zwischen Autor und Leser auffordern. Daher finden Sie sowohl auf der Homepage des Verlages www.vieweg.de, als auch auf meiner Homepage www.harald-nahrstedt.de ein Forum for erg~tnzenden Programme, Anregungen und Kommentare so wie LOsungen zu den Ubungsaufgaben. M6hnesee, im Oktober 2005

VI

Harald Nahrstedt

I n h a l t s v e r z e i c h n is

Inhaltsverzeich nis 1 A l g o r i t h m e n ...........................................................................................................

1

1.1 G e s c h i c h t l i c h e s ................................................................................................

1

1.2 F o r m a l e Definition ........................................................................................... 3 1.3 A s p e k t e d e r A l g o r i t h m e n ................................................................................ 3 1.4 A l g o r i t h m e n k l a s s e n ......................................................................................... 4 1.5 Das K o n z e p t e i n e r P r o b l e m l 6 s u n g ................................................................. 7 1.6 Heuristik ...........................................................................................................

9

2 L 6 s u n g e n v o n G l e i c h u n g e n .............................................................................. 13 2.1 L 6 s u n g e n y o n q u a d r a t i s c h e n G l e i c h u n g e n .................................................. 13 H~irteprtifung n a c h Brinell ....................................................................... 13 2.2 K u b i s c h e G l e i c h u n g e n .................................................................................. 17 T r i c h t e r v o l u m e n ........................................................................................ 22 2.3 L 6 s u n g e n y o n G l e i c h u n g e n h 6 h e r e n G r a d e s .............................................. 23 Minimaler M a t e r i a l v e r b r a u c h mit Regula Falsi ........................................ 24 Maximales V o l u m e n n a c h d e r N e w t o n M e t h o d e .................................... 31

3 L 6 s u n g e n linearer G l e i c h u n g s s y s t e m e ........................................................... 37 3.1 L 6 s u n g e n linearer G l e i c h u n g s s y s t e m e ......................................................... 37 T e m p e r a t u r v e r t e i l u n g n a c h der Gaufg-Elimination ................................. 38 3.2 Lineare O p t i m i e m n g mit d e r S i m p l e x - M e t h o d e .......................................... 44 P r o d u k t i o n s o p t i m i e m n g ........................................................................... 45 Z u s c h n i t t o p t i m i e m n g ............................................................................... 54

VII

I n h a l t s v e r z e i c h n is

4 F u n k t i o n e n ........................................................................................................... 58 4.1 Interpolation y o n F u n k t i o n e n d u r c h P o l y n o m e .......................................... 58 4.1.1 Interpolation n a c h N e w t o n ....................................................................... 59 Stahlseilverlauf .......................................................................................... 60 4.1.2 Interpolation mittels k u b i s c h e r Splines ..................................................... 65 Stahlseilverlauf .......................................................................................... 71 4.2 A p p r o x i m a t i o n v o n F u n k t i o n e n d u r c h P o l y n o m e ....................................... 72 S e n s o r k e n n l i n i e ......................................................................................... 74 4.3 N u m e r i s c h e Integration ................................................................................. 80 Tr~iger gleicher Zugfestigkeit .................................................................... 81 Ausflusszeit v o n Fltissigkeiten .................................................................. 87

5 D i f f e r e n t i a l g l e i c h u n g e n .................................................................................... 95 5.1 N u m e r i s c h e B e h a n d l u n g g e w 6 h n l i c h e r Differentialgleichungen ........................................................................... 95 B e w e g u n g s b e s t i m m u n g eines Schubkurbeltriebs d u r c h D i f f e r e n z e n q u o t i e n t e n .............................................................................. 97 D r e h s c h w i n g u n g e n ............................................................................... 111 5.2 N u m e r i s c h e B e h a n d l u n g partieller Differentialgleichungen .......................................................................... 119 B e s t i m m u n g einer Membranfl~iche mittels L a p l a c e - O p e r a t o r .............. 121

6 V e k t o r e n u n d Matrizen .................................................................................... 130 6.1 Matrizendefinitionen .................................................................................... 130 6.2 L6sen v o n G l e i c h u n g s s y s t e m e n .................................................................. 151 Gaulg-Elimination .................................................................................... 153 6.3 D i f f e r e n z e n v e r f a h r e n for g e w 6 h n l i c h e Differentialgleichungen .......................................................................... 158 Einseitig e i n g e s p a n n t e r Biegetr~ger ....................................................... 159

VIII ".

.

.

.

I n h a ltsverzeic h n is

6.4 E i g e n w e r t p r o b l e m e ..................................................................................... 163 Freie B i e g e s c h w i n g u n g eines g e r a d e n Balkens .................................... 164

7 P s e u d o z u f a l l s z a h l e n ......................................................................................... 173 7.1 Die Eigenschaft der Pseudo-Zufallszahlen ................................................. 173 Wahrscheinlichkeit u n d Gleichverteilung ............................................. 173 7.2 Integration nach der Monte Carlo M e t h o d e ............................................... 173 B e s t i m m u n g der Fl~iche eines Blechteils ............................................... 177 7.3 Probabilistische Simulation ........................................................................ 180 M a s c h i n e n w a r t u n g als W a r t e s c h l a n g e n p r o b l e m mit W a h r s c h e i n l i c h k e i t s w e r t e n ..................................................................... 180 Ermittlung der L e b e n s d a u e r y o n Maschinenteilen d u r c h Ausfallwahrscheinlichkeiten ....................................................... 186

8 M g o r i t h m e n a u f D a t e n s t r u k t u r e n ................................................................. 204 8.1 P e r m u t a t i o n e n .............................................................................................. 204 Bearbeitung am Flief~band als E n g p a s s z u o r d n u n g s p r o b l e m .................................................................. 207 8.2 Regression u n d Korrelation ......................................................................... 213 Experimentelle B e s t i m m u n g einer Feder .............................................. 219 8.3 Arrays u n d Datenfelder ............................................................................... 221 Nutzwertanalyse ...................................................................................... 222 8.4 Arbeiten auf Listenstrukturen ..................................................................... 228 Quicksort ................................................................................................. 228 Stticklistenorganisation ........................................................................... 231 8.5 Arbeiten auf B a u m s t m k t u r e n u n d G r a p h e n .............................................. 239 N e t z p l a n t e c h n i k ...................................................................................... 242

IX

In h a ltsverzeic h n is

9 V e r h a l t e n s - A l g o r i t h m e n .................................................................................. 253 9.1 Teile u n d Herrsche ...................................................................................... 253 S u c h e n nach der B i s e k t i o n s m e t h o d e .................................................... 253 9.2 Die G r e e d y - M e t h o d e ................................................................................... 256 Auftragsfolgenproblem .......................................................................... 256 9.3 Rtickverfolgung o d e r Backtracking ............................................................ 262 Einschrittige Codes ffir industrielle W e g m e s s u n g ................................. 263 9.4 ROckw~irtsrechnen o d e r Rekursive P r o z e d u r e n ......................................... 270 J e e p - P r o b l e m .......................................................................................... 270

10 A l g o r i t h m e n a u s d e r N a t u r ........................................................................... 274 10.1 Der A m e i s e n a l g o r i t h m u s ........................................................................... 274 M a s c h i n e n b e l e g u n g ................................................................................ 278 10.2 Evolutionsstrategien ................................................................................... 286 S t a b w e r k o p t i m i e m n g ............................................................................. 287 10.3 G e n e t i s c h e Algorithmen ............................................................................ 294 P a c k p r o b l e m ........................................................................................... 296

11 M g o r i t h m e n

als l d i n s t l i c h e I n t e l l i g e n z ...................................................... 303

11.1 Fuzzy Logik ................................................................................................ 303 Fuzzy Regelung eines Industrieofens .................................................... 308

L i t e r a t u r v e r z e i c h n i s ............................................................................................ 315 Sachwortverzeichnis

X

........................................................................................... 317

A bbiMu ngsverzeich n is

Abbildungsverzeichnis 1 M g o r i t h m e n ........................................................................................................... 1 1-1 S y s t e m w i s s e n v e r s u s A l g o r i t h m e n k l a s s e n .................................................... 6 1-2 Black B o x ........................................................................................................

7

1-3 S c h e m a d e r L 6 s u n g s f i n d u n g ........................................................................... 8 1 - 4 0 b l i c h e L6sung des B i e r d e c k e l p r o b l e m s ................................................... 10 1-5 L6sung n a c h d e r A u f g a b e y o n Restriktionen ............................................... 10 1-6 Eine d r e i d i m e n s i o n a l e L6sung ...................................................................... 11

2 L ~ s u n g e n v o n G l e i c h u n g e n .............................................................................. 13 2-1 K u g e l d r u c k p r o b e n a c h Brinell ..................................................................... 14 2-2 Eine T a b e l l e in e i n e r A r b e i t s m a p p e besitzt u n t e r VBA ein C o d e f e n s t e r .. 16 2-3 M e n t i p u n k t Eindringtiefe ..............................................................................

17

2-4 A u s w e r t u n g n a c h Brinell mit B e i s p i e l d a t e n ................................................. 17 2-5 Menti K u b i s c h e G l e i c h u n g .......................................................................... 22 2-6 Geschweilgter Blechtrichter ........................................................................... 22 2-7 B e r e c h n u n g s f o r m u l a r ....................................................................................

23

2-8 M e t h o d e Regula Falsi ....................................................................................

24

2-9 Zylindrischer Behiilter for M i n i m a l a u f g a b e .................................................. 25 2-10 Menti for Minimale Oberfliiche ................................................................... 30 2-11 A u s w e r t u n g d e r T e s t d a t e n .......................................................................... 30 2-12 B l e c h z u s c h n i t t for m a x i m a l e s V o l u m e n ..................................................... 31 2-13 M e t h o d e n a c h N e w t o n ................................................................................ 32 2-14 Menti for m a x i m a l e s V o l u m e n ................................................................... 35 2-15 A u s w e r t u n g d e r T e s t d a t e n for m a x i m a l e s V o l u m e n ................................. 35

3 L/Jsungen l i n e a r e r G l e i c h u n g s s y s t e m e ........................................................... 37 3-1 Gitternetz zur T e m p e r a t u r v e r t e i l u n g ............................................................ 39 3-2 Menti T e m p e r a t u r v e r t e i l u n g ......................................................................... 43

XI

A bbildu ngsverzeich n is 3-3 T e m p e r a t u r f e l d der Testdaten ...................................................................... 44 3-4 Grafische L6sung der P r o d u k t i o n s o p t i m i e r u n g ........................................... 46 3-5 Rechteckregel ................................................................................................ 47 3-6 MenO Simplex ................................................................................................ 54 3-7 Bauteile Ubersicht ......................................................................................... 54 3-8 Zuschnitte zur O p t i m i e m n g .......................................................................... 55 3-9 A u s w e r t u n g der Testdaten zur Zuschnittoptimierung ................................. 56

4 Funktionen ........................................................................................................... 58 4-1 StOtzstellen eines I n t e r p o l a t i o n s p o l y n o m s ................................................... 58 4-2 Stahlseilverlauf ............................................................................................... 60 4-3 MenO zur Interpolation nach N e w t o n .......................................................... 63 4-4 A u s w e r t u n g der Testdaten zum Seilverlauf ................................................. 64 4-5 A n e i n a n d e r r e i h u n g kubischer P o l y n o m e ..................................................... 66 4-6 MenO zur Interpolation mittels kubischer Splines ....................................... 71 4-7 Seilverlauf, ermittelt durch kubische Splines ............................................... 71 4-8 Grafische Darstellung der M e t h o d e der kleinsten Fehlerquadrate ............. 72 4-9 Lineare A p p r o x i m a t i o n ................................................................................. 73 4-10 Lineare A p p r o x i m a t i o n nach der F e s t p u n k t m e t h o d e ................................ 74 4-11 Lineare Approximation nach d e m Minimum der Fehlerquadrate ............. 75 4-12 MenO zur Interpolation nach N e w t o n ........................................................ 79 4-13 Beispiel der linearen A p p r o x i m a t i o n einer Sensorkennlinie .................... 79 4-14 Bestimmtes Integral ..................................................................................... 80 4-15 Einteilung nach der Trapezregel ................................................................ 80 4-16 Tr~iger mit gleicher Zugfestigkeit ................................................................ 82 4-17 MenO zur k o n s t a n t e n Z u g s p a n n u n g .......................................................... 85 4-18 A u s w e r t u n g der Testdaten zur k o n s t a n t e n Z u g s p a n n u n g ........................ 86 4-19 Ausfluss aus e i n e m Beh~lter ....................................................................... 87 4-20 Vorschrittige, r0ckschrittige u n d zentrale Differenzen .............................. 88 4-21 MenO zur Ausflusszeitbestimmung ............................................................. 93

XII

A bbiMu ngsverzeich n is 4-22 B e s t i m m u n g d e r Ausflusszeit einer Fltissigkeit .......................................... 94

5 Differentialgleichungen .................................................................................... 95 5-1 N/ i h er u n g n a c h E u l e r - C a u c h y ...................................................................... 95 5-2 S c h u b k u r b e l t r i e b ........................................................................................... 97 5-3 S c h u b s t a n g e u n d B o l z e n z u m S c h u b k u r b e l t r i e b ......................................... 98 5-4 K u r b e l w a n g e u n d K u r b e l z a p f e n z u m S c h u b k u r b e l t r i e b ............................. 99 5-5 I n d i k a t o r d i a g r a m m z u m S c h u b k u r b e l t r i e b ................................................ 100 5-6 D r e h m o m e n t e n v e r l a u f z u m S c h u b k u r b e l t r i e b ........................................... 100 5-7 S c h w u n g s c h e i b e z u m S c h u b k u r b e l t r i e b .................................................... 101 5-8 Menti z u m S c h u b k u r b e l t r i e b ...................................................................... 108 5-9 A u s w e r t u n g d e r T e s t d a t e n 1. Teil .............................................................. 109 5-10 A u s w e r t u n g d e r T e s t d a t e n 2. Teil ............................................................ 110 5-11 D i a g r a m m e zur A u s w e r t u n g ..................................................................... 111 5-12 T o r s i o n s p e n d e l ..........................................................................................

111

5-13 Menti D r e h s c h w i n g u n g e n ......................................................................... 115 5-14 S c h w i n g u n g s s y s t e m ...................................................................................

116

5-15 Ersatzsystem for D r e h s c h w i n g u n g e n ....................................................... 116 5-16 A u s w e r t u n g des S c h w i n g u n g s s y s t e m s ..................................................... 117 5-17 T o r s i o n s p e n d e l zur Feststellung eines Id ................................................. 118 5-18 G i t t e r p u n k t e ...............................................................................................

119

5-19 B e r e c h n u n g s o p e r a t o r ................................................................................

120

5-20 F o r m e i n e r e i n g e s p a n n t e n M e m b r a n ....................................................... 121 5-21 Einteilung eines M e m b r a n a u s s c h n i t t s ...................................................... 121 5-22 Menti zur M e m b r a n b e r e c h n u n g ............................................................... 128 5-23 M e m b r a n b e s t i m m u n g n a c h T e s t d a t e n ..................................................... 128 5-24 S c h e m a t i s c h e r Aufbau e in e r E l e k t r o n e n r 6 h r e ......................................... 129

6 Vektoren und Matrizen .................................................................................... 130 6-1 Erster Aufbau d e s MenOs M a t r i z e n o p e r a t i o n e n ......................................... 134 6-2 MenO M a t r i z e n o p e r a t i o n e n ......................................................................... 150

XIII

A bbildu ngsverzeich n is 6-3 Menti z u m G a u l g - A l g o r i t h m u s ....................................................................

157

6-4 T e s t d a t e n a u s w e r t u n g ..................................................................................

157

6-5 D i f f e r e n z e n ..................................................................................................

158

6-6 G l e i c h g e w i c h t e i n e s finiten E l e m e n t s u n t e r B i e g e b e l a s t u n g .................... 159 6-7 Einseitig e i n g e s p a n n t e r B i e g e t r ~ g e r ........................................................... 160 6-8 A u s w e r t u n g n a c h d e r G a u l g - M e t h o d e ........................................................ 162 6-9 B e i d s e i t i g e i n g e s p a n n t e r TrS.ger .................................................................

164

6-10 Menti zur M e t h o d e v o n Mises ..................................................................

170

6-11 1. Teil d e r A u s w e r t u n g z u m T e s t b e i s p i e l ................................................. 171 6-12 2. Teil d e r A u s w e r t u n g z u m T e s t b e i s p i e l ................................................. 171

7 Pseudozufallszahlen .........................................................................................

173

7-1 Viertelkreis im Q u a d r a t ...............................................................................

173

7-2 Menti zur M o n t e - C a r l o - M e t h o d e ................................................................

175

7-3 T e s t e r g e b n i s s e zur M o n t e - C a r l o - M e t h o d e .................................................. 176 7-4 Fl~iche e i n e s Blechteils ................................................................................

177

7-5 MenO zur F l ~ i c h e n b e r e c h n u n g ....................................................................

179

7-6 Blechteilfl~che n a c h d e r M o n t e - C a r l o - M e t h o d e b e s t i m m t ........................ 180 7-7 MenO zur M a s c h i n e n w a r t u n g .....................................................................

185

7-8 M a s c h i n e n w a r t u n g mit T e s t d a t e n ...............................................................

185

7-9 S c h e m a e i n e r P u m p e n e i n h e i t .....................................................................

186

7-10 W a h r s c h e i n l i c h k e i t s f u n k t i o n d e r d u r c h s c h n i t t l i c h e n L e b e n s d a u e r ......... 187

8 Algorithmen auf Datenstrukturen ................................................................. 204 8-1 MenO P e r m u t a t i o n e n ...................................................................................

206

8-2 P e r m u t a t i o n e n v o n n=5 ..............................................................................

207

8-3 S c h e m a e i n e r F l i e l g b a n d a r b e i t ....................................................................

207

8-4 Menti zur F l i e l g b a n d a r b e i t ...........................................................................

212

8-5 A u s w e r t u n g d e r T e s t d a t e n ..........................................................................

212

8-6 M e s s w e r t e u n d R e g r e s s i o n s g e r a d e ............................................................. 213 8-7 Menti zur B e s t i m m u n g d e r R e g r e s s i o n s g e r a d e n ....................................... 218

XIV

A bbildu ngsverzeichn is 8-8 A u s w e r t u n g der Testdaten .......................................................................... 219 8-9 F e d e r p e n d e l ................................................................................................. 220 8-10 B e s t i m m u n g der F e d e r k o n s t a n t e n aus d e n Beispieldaten ...................... 221 8-11 Aufbau eines Arrays .................................................................................. 222 8-12 Schema einer Nutzwertanalyse ................................................................. 223 8-13 Beispiel einer Nutzwertanalyse ................................................................. 224 8-14 MenO zur Nutzwertanalyse ....................................................................... 227 8-15 Ergebnis des Testbeispiels ........................................................................ 227 8-16 MenO z u m Quicksort ................................................................................. 231 8-17 Beispiel einer Produktstruktur .................................................................. 232 8-18 MenO zur ProduktstOckliste ...................................................................... 237 8-19 Baugruppen-StOcklisten z u m Beispiel ...................................................... 238 8-20 Struktur-StOckliste z u m Beispiel ............................................................... 238 8-21 Beispiel eines G r a p h e n ............................................................................. 239 8-22 Beispiel eines gerichteten u n d g e w i c h t e t e n G r a p h e n ............................. 240 8-23 Vergleich G r a p h u n d B a u m ...................................................................... 240 8-24 G o z i n t o g r a p h z u m StOcklistenbeispiel ..................................................... 241 8-25 Elemente in PERT ...................................................................................... 242 8-26 Scheinaktivit~.t ............................................................................................ 244 8-27 Netzplan z u m Beispiel .............................................................................. 245 8-28 MenO z u m Netzplan PERT ........................................................................ 251 8-29 1. Teil E i n g a b e d a t e n u n d Auswertungsteil z u m Netzplan ...................... 251 8-30 2. Teil restliche A u s w e r t u n g ..................................................................... 251 9 Verhaltens-Algorithmen

.................................................................................. 253

9-1 Schema einer B i s e k t i o n s m e t h o d e ............................................................... 254 9-2 MenO zur S u c h p r o z e d u r nach der B i s e k t i o n s m e t h o d e ............................. 255 9-3 MenO zur G r e e d y - M e t h o d e ......................................................................... 261 9-4 Ergebnis der Testdaten ............................................................................... 261 9-5 B a u m s t r u k t u r ............................................................................................... 262

XV

A bbiMu ngsverzeich n is 9-6 W e g m e s s u n g ............................................................................................... 263 9-7 Erste Schritte des Algorithmus .................................................................... 264 9-8 Ment~ zur Bestimmungsart .......................................................................... 269 9-9 Die ersten n e u n g e f u n d e n e n einschrittigen Codes ................................... 269 9-10 Die M e t h o d e des Rtickw~irtsrechnens ...................................................... 270 9-11 Men~ zum J e e p - P r o b l e m .......................................................................... 273 9-12 B e i s p i e l b e r e c h n u n g zum J e e p - P r o b l e m ................................................... 273

10 A l g o r i t h m e n aus der Natur ........................................................................... 274 10-1 Ktirzeste m a c h b a r e W e g e der Ameisen ................................................... 275 10-2 Beispiel for Wahrscheinlichkeiten einer L6sungsauswahl im A m e i s e n a l g o r i t h m u s ............................................................................... 277 10-3 Menti zum A m e i s e n a l g o r i t h m u s ............................................................... 285 10-4 Ein m{Sgliches Ergebnis der Testdaten ..................................................... 285 10-5 Stabwerk unter Belastung ......................................................................... 287 10-6 V e r s c h i e b u n g des 1. Knotens ................................................................... 288 10-7 V e r s c h i e b u n g des 2. Knotens ................................................................... 288 10-8 Der Endstab ............................................................................................... 289 10-9 Menti zur S t a b w e r k s o p t i m i e r u n g .............................................................. 293 10-10 Ergebnisse aus d e n Testdaten ................................................................. 293 10-11 Das g e o m e t r i s c h optimierte Stabwerk .................................................... 294 10-12 Menti zum g e n e t i s c h e n Algorithmus ...................................................... 301 10-13 A u s w e r t u n g der Testdaten zum g e n e t i s c h e n Algorithmus .................... 302 11 A l g o r i t h m e n als l d i n s t l i c h e I n t e l l i g e n z ...................................................... 303 11-1 Menge der a n g e n e h m e n R a u m t e m p e r a t u r ............................................... 304 11-2 F o r m e n yon Fuzzy-Mengen ...................................................................... 304 11-3 Beispiel einer Fuzzy-Zerlegung ftir R a u m t e m p e r a t u r .............................. 305 11-4 Das K o m p l e m e n t einer Fuzzy Menge ...................................................... 305 11-5 Die V e r e i n i g u n g s m e n g e der Fuzzy-Mengen ............................................ 305 11-6 Die D u r c h s c h n i t t s m e n g e der Fuzzy-Mengen ........................................... 306

XVI /

~

9 9

..

A bbildungsverzeichnis 11-7 Beispiel einer F u z z y f i z i e m n g .................................................................... 306 11-8 V e r k n t i p f u n g linguistischer Werte ............................................................ 307 11-9 Das S c h e m a einer Fuzzy-Regelung .......................................................... 308 11-10 Fuzzy-Set T e m p e r a t u r .............................................................................. 308 11-11 Fuzzy-Set D r u c k ....................................................................................... 309 11-12 Ventilstellung ........................................................................................... 309 11-13 Menti zur F u z z y - R e g e l u n g ...................................................................... 311 11-14 B e r e c h n e t e s Kennfeld ............................................................................. 314

XVII

P r o g ra m m v e r z e i c h n is

Programmverzeichnis .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

." 7 /

.

~

9

.

"~

2 L6sungen v o n Gleichungen .............................................................................. 13 2-1 B e s t i m m u n g der Eindringtiefe n a c h Brinell ................................................. 15 2-2 LOsungen k u b i s c h e r G l e i c h u n g e n ................................................................ 19 2-3 B e s t i m m u n g der m i n i m a l e n Oberfl~iche eines zylindrischen Beh~ilters ..... 27 2-4 B e s t i m m u n g des m a x i m a l e n V o l u m e n s eines Beh~tlters ............................. 33

3 L6sungen linearer Gleichungssysteme ........................................................... 37 3-1 B e s t i m m u n g der T e m p e r a t u r v e r t e i l u n g nach der Gaulg-Elimination .......... 40 3-2 S i m p l e x m e t h o d e ............................................................................................ 51

4 F u n k t i o n e n ........................................................................................................... 58 4-1 B e s t i m m u n g der Koeffizienten einer I n t e r p o l a t i o n s p o l y n o m s n a c h N e w t o n ............................................................................................. 61 4-2 Interpolation mittels k u b i s c h e r Splines ........................................................ 68 4-3 Lineare A p p r o x i m a t i o n ................................................................................. 76 4-4 Trliger gleicher Z u g s p a n n u n g ....................................................................... 83 4-5 B e s t i m m u n g der Ausflusszeit aus e i n e m Gef~t~ .......................................... 90 5 Differemialgleichungen

.................................................................................... 95

5-1 B e w e g u n g eines S c h u b k u r b e l t r i e b s ........................................................... 103 5-2 D r e h s c h w i n g u n g e n ..................................................................................... 113 5-3 B e s t i m m u n g einer M e m b r a n f o r m ............................................................... 125

6 Vektoren und Matrizen .................................................................................... 130 6-1 M a t r i z e n o p e r a t i o n e n ................................................................................... 132 6-2 Matrizenaddition .......................................................................................... 135 6-3 Matrizensubtraktion ..................................................................................... 137 6-4 S k a l a r p r o d u k t .............................................................................................. 139 6-5 M a t r i z e n p r o d u k t .......................................................................................... 141 6-6 B e s t i m m u n g der D e t e r m i n a n t e einer Matrix .............................................. 145

XVIII

.

A bbildu ngsverzeich n is 6-7 Bestimmung der k o m p l e m e n t ~ r e n Matrix ................................................. 147 6-8 Gaulg-Elemination in Matrizenform ............................................................ 154 6-9 Von Mises Verfahren ................................................................................... '7 P s e u d o z u f a l l s z a h l e n

168

.........................................................................................

173

7-1 F l ~ c h e n b e r e c h n u n g eines Viertelkreises nach der Monte-Carlo-Methode ............................................................. 175 7-2 Fl~ichenberechnung eines Blechteils nach der Monte-Carlo-Methode ..... 178 7-3 Einfaches Modell einer Maschinenwartung ............................................... 182 7-4 Ersatzproblem nach der 1. Methode .......................................................... 190 7-5 Ersatzproblem nach der 2. Methode .......................................................... 195 7-6 Ersatzproblem nach der 3. Methode .......................................................... 200 8 Algorithmen

auf Datenstrukturen

................................................................. 204

8-1 Erzeugung yon Permutationen nattirlicher Zahlen .................................... 205 8-2 P r o z e d u r e n zum E n g p a s s p r o b l e m .............................................................. 209 8-3 Bestimmung einer linearen Regression ...................................................... 216 8-4 Nutzwertanalyse ..........................................................................................

224

8-5 Quicksort .....................................................................................................

230

8-6 StOcklistenorganisation ................................................................................

232

8-7 PERT Netzplan .............................................................................................

247

9 V e r h a l t e n s - A l g o r i t h m e n .................................................................................. 253 9-1 Suchen mittels Bisektionsmethode in einer g e o r d n e t e n Liste .................. 255 9-2 Suchen einer L6sung for ein A u f g a b e n f o l g e p r o b l e m nach der GreedyMethode .................................................................................................. 258 9-3 Bestimmung einschrittiger Codes ............................................................... 266 9-4 Das J e e p - P r o b l e m ........................................................................................

272

10 A l g o r i t h m e n a u s d e r N a t u r ........................................................................... 274 10-1 P r o z e d u r e n zur Bestimmung einer optimalen M a s c h i n e n b e l e g u n g ....... 280 10-2 S t a b w e r k s o p t i m i e m n g nach der Evolutionsstrategie ............................... 291 10-3 Formblatt u n d Daten zum P a c k p r o b l e m .................................................. 296

XIX 9

.~__

~ .

..--

9

\~

P r o g r a m m v e r z e i c h n is

10-4 Initialisierung d e r Eltern ............................................................................ 297 10-5 S e l e k t i o n .................................................................................................... 298 10-6 R e k o m b i n a t i o n .......................................................................................... 299 10-7 M u t a t i o n ..................................................................................................... 300 10-8 P o p u l a t i o n e n ............................................................................................. 301

11 Algorithmen als ldinstliche Intelligenz

...................................................... 303

11-1 Die A u s w e r t u n g s p r o z e d u r e n zur F u z z y - R e g e l u n g .................................. 311

XX

1 Algorithmen

l

Algorithmen Unter einem Algorithmus versteht man eine genau definierte Handlungsvorschrift zur L6sung eines Problems. Er stellt eine der wichtigsten mathematischen Begriffe dar, vergleichbar etwa mit dem Begriff der Funktion. Schaut man jedoch genauer hin, dann stellt man fest, dass der Algorithmus nicht nur for die Mathematik und Informatik von zentraler Bedeutung ist, sondern auch eng mit zentralen Themen der Geistesgeschichte verbunden ist. Seine Anwendung reicht in die Gebiete der Philosophie, der Medizin, der Biologie, der Kulturgeschichte, der Politik, u. v. a. Es gibt kaum eine Wissenschaft, in der der Algorithmus nicht bekannt ist und genutzt wird.

1.1

Geschichtliches L6sungsvorschriften sind sehr viel ~ilter, als es ihre Anwendung in den heutigen Computern vermuten l~sst.

Wurzelziehen nach babylonisch sumerischer Methode Euklid

Lineare Gleichungssysteme

Einer der ~iltesten festgehaltenen Algorithmen der Menschheit wurde um 1700 v. Chr. in Keilschrift auf Tontafeln verfasst und beschreibt das Wurzelziehen nach einer babylonisch sumerische Methode. Den ersten schriftlich festgehaltenen Algorithmus verfasste Euklid in seinem Buch ,,Die Elemente" im 3. Jh. v. Chr. Nebenbei bemerkt, diente dieses Buch etwa 2000 Jahre als L e h r b u c h - eine phantastische Leistung. In diesem Buch beschreibt Euklid unter anderem auch den bis heute benutzten Euklidschen Algorithmus. Lineare Gleichungssysteme mit zwei Unbekannten wurden schon um 1700 v. Chr. von den Babyloniern gel6st. Um 180 v. Chr. verfasste der chinesische Mathematiker Shang Cang ein allgemeines L6sungsverfahren for lineare Gleichungssysteme mit fOnf Ungekannten, in dem unschwer der Gaulgsche-Algorithmus zu erkennen ist. Bei Leonardo Fibonacci von Pisa (1170-1220) findet man diese L6sungsmethode wieder. Man vermutet, dass sie ihren Weg von den Babyloniern Ober die Griechen (Diophant) oder Araber in den Westen genommen hat.

1

1.1

Gesch ich tliches

Algorithmus

Das Wort Algorithmus wird auf den Autor des Buches Hisab aldschabr wa-l-muqabala mit Namen Muhammad ibn Musa al Chwarizmi zurOckgefOhrt. Dieser lebte um 830 n. Chr. am Hofe des Kalifen Mamum in Baghdad und er beschrieb in seinem Buch die Regeln der Arithmetik, wie sie bis dahin von den Indern entwickelt waren. Es ist sein Verdienst, dass sich damit die Algebra auch im Westen schnell verbreitete. Dazu trug auch im Mittelalter eine lateinische Obersetzung mit der Bezeichnung ,,algoritmi de numero Indorum" bei. Stand in dem ursprOnglichen Buch noch das Wort Algorism for Regeln der Arithmetik mit arabischen Zahlen, so wurde es sp~iter zu dem pseudogriechischen Wort ,,algorithmos" Obersetzt.

Raimundus Lullus Es war dann der spanische Philosoph und Theologe Raimundus Lullus, der im Jahre 1656 seine ber0hmte ,,Ars Magna" ver6ffentlichte. Darin beschreibt er einen allgemeinen Algorithmus als ein System grundlegender Begriffe, deren Kombination alle m6glichen Wahrheiten erzeugen sollte. Dazu stellte er sich die mechanische AusfOhrung seines Algorithmus als eine Anordnung von sechs konzentrischen Kreisen vor, die systematisch gegeneinander verschoben, alle m6glichen Kombinationen ergeben sollten. Ada Lovelace

Erst im Jahre 1842 wurde der erste for einen Computer gedachte Algorithmus von Ada Lovelace skizziert. Er war gedacht for die von Charles Babbage konstruierte Analytical Engine. Da er diese aber nicht vollendete, wurde auch der Algorithmus nie implementiert. Ada Lovelace gilt dennoch als die erste Programmiererin.

Leibnitz

Leibnitz war es dann, der bereits in seiner Jugend eine Methode aufzustellen versuchte, die jedes Problem auf algorithmische Weise 16sen sollte. Seine Dissertation ,,De arte combinatoria" aus dem Jahre 1880 hatte zum Ziel, neue Begriffe aus wenigen grundlegenden Begriffen abzuleiten. Die Basis sollte ein Alphabet menschlichen Denkens sein, dargestellt durch geeignete Symbole. Ihre Kombination sollte zu allen bekannten Begriffen fOhren und auch neue erzeugen. Die DurchfOhrbarkeit seines Systems sah Leibnitz durch Abbildungen aller Begriffe auf Zahlen und die der grundlegenden Begriffe auf Primzahlen. Rechnungen auf diesem System sollten dann alle Arten von Problemen 16sen, bis hin zu unterschiedlichen menschlichen Meinungen. So sollten sich damit aulgerdem Prozesse des menschlichen Denkens abbilden und auf Maschinen nachvollziehen lassen.

2

1 Algorithmen Kurt Gddel

Alan Turing

Kurt G6del zeigte dann im Jahre 1931 mittels Beweis, dass eine bestimmte Klasse mathematischer Probleme durch keinen Algorithmus aus einer exakt definierten Klasse von Algorithmen gel~Sst werden kann. In dieser Zeit wurde eine ganze Reihe von Ans~tzen zur Definition eines Algorithmus entwickelt. Insbesondere den Begriff der Berechenbarkeit untersuchte Alan Turing mit seiner Turing-Maschine. Ebenso entstanden die MarkovAlgorithmen. Mit dem Aufkommen digitaler Rechenanlagen durch die Raumfahrt, bekamen die Algorithmen eine neue Bedeutung. Ging es frOher nur um den L6sungsweg, so bekommen Begriffe wie Komplexit~it und Rechenzeit eine immer grOlgere Bedeutung. W~ihrend die Rechenzeit ihre Grenzen in den Erkenntnissen der atomaren Physik findet, entstehen aus der Komplexitfit Begriffe wie ,,ktinstliche Intelligenz" und ftihren zu scheinbaren WidersprOchen.

1.2

AlgorithmenEigenschafien

Formale Definition Obwohl wir doch alle begreifen, was unter einem Algorithmus zu verstehen ist, ist uns die Wissenschaft eine exakte Definition des Begriffs bis heute schuldig geblieben. Im Laufe der Zeit wurden jedoch folgende Eigenschafien fiir einen Algorithmus abgeleitet: 9 Alle verwendeten GrOlgen mtissen bekannt sein 9

Die Umarbeitung geschieht in Arbeitstakten

9

Die Beschreibung des Algorithmus ist vollstfindig

9

Die Beschreibung des Algorithmus ist endlich

9

Alle angegebenen Operationen sind zuEissig

9

Angabe einer Sprache for die Regeln

Die in diesem Buch dargestellten Algorithmen k6nnen nur als Beispiel for eine Kategorie gleichartiger Methoden dargestellt werden, da sich fiber jeden Bereich leicht ein eigenes Buch schreiben liege. Der Leser soil diese Darstellungen als Anreiz empfinden, die Thematik weiter zu vertiefen.

1.3 Algorithmen in den Wissenschafien

Aspekte der Algorithmen Algorithmen verbinden in ihrer Anwendung oft sehr unterschiedliche Wissensgebiete miteinander. So wie der Euklidsche Algorithmus Geometrie und Algebra verbindet, gibt es Algorithmen

3

1.4

Algorithmenklassen im naturwissenschaftlichen Bereich als Simulation auf Wahrscheinlichkeiten. Algorithmen in den Sprachwissenschaften zur Beschreibung sprachlicher Regeln. Algorithmen in den Sozialwissenschaften zur Darstellung bestimmter Verhaltensmuster. Algorithmen in der Wirtschaft zur Darstellung von Wirkzusammenh~ingen. Und viele andere Gebiete mehr. Ja sogar in der Kunst werden Algorithmen zu Arbeitstechniken genannt. Ebenso lassen sich Algorithmen eines Fachgebiets auch auf andere ~ibertragen. Als Beispiel sei der Ameisenalgorithmus aus der Bionik genannt.

Algorithmen in den Ingenieurwissenschafien

Dieses Buch befasst sich mit der Anwendung von Algorithmen im ingenieurwissenschaftlichen Bereich und bedarf daher einer besonderen Sichtweise. Anders als der Naturwissenschaftler, kann sich der Ingenieur nicht ausgiebig mit allen Randbedingungen eines Problems befassen. Die Zeit, die ihm f~ir ein Projekt zur Verf~igung steht, ist ebenso endlich wie der finanzielle Rahmen. Er muss mit begrenzten Informationen Entscheidungen treffen und dabei Risiken absch~ttzen. Auf digitalen Rechenanlagen kann er sich mit Hilfe fachrelevanter Algorithmen diese Informationen durch Berechnungen und Simulationen in Mirzester Zeit effizient besorgen. Dies setzt allerdings Kenntnisse in einer g~tngigen Programmiersprache und entsprechendes Werkzeug voraus. W~ihrend die schnelllebige Hardware und Systemsoftware von geringer Bedeutung ist, sind die allgemeine Darstellung der Algorithmen und ihre Umsetzung in eine leicht verst~tndliche Programmiersprache Gegenstand unserer Betrachtung.

1.4

Algorithmenklassen Die Einteilung der Algorithmen geschieht je nach Sichtweise in unterschiedlichen Klassen. Ich will daher nachfolgend einige Begriffe erl~tutern.

Numerische Algorithmen

4

Die ~tltesten uns bekannten Algorithmen im klassischen Sinne sind die numerischen Algorithmen wie der Euklidsche Algorithmus zur Bestimmung des gr61gten gemeinsamen Teilers zweier nat~irlicher Zahlen oder das Sieb des Eratosthenes zur Ermittlung der Primzahlen einer vorher festgesetzten Zahlenmenge. Aber auch Algorithmen zur L6sung von Gleichungen und Gleichungssystemen sind hier zu finden. In der Neuzeit kamen mit der Differential- und Integralrechnung auch Algorithmen zur N~iherung, Integration, Differentiation, Interpolation und Approximation auf. Ebenso verschiedene Matrizen-Verfahren. Die Geschichte der

1 Algorithmen numerischen Algorithmen ist Teil der Geschichte der Mathematik. Determ i n istische Algorithmen

Unter deterministischen Algorithmen versteht man diejenigen, die bei gleicher Eingabe immer das gleiche Ergebnis liefern. Enth~lt ein Algorithmus Elemente eines Zufallsereignisses, so spricht man von nicht-deterministischen oder randomisierten Algorithmen. Das Monte-Carlo-Verfahren gehOrt zu diesen Algorithmen.

Iterative Algorithmen

Unter iterativen Algorithmen versteht man diejenigen, die mit Rechenschritten, ausgehend von bekannten GrOlgen, Zwischenergebnisse erzielen, die wiederum als Basis for eine erneute Ausftihrung der Rechenschritte dienen. Man unterscheidet diese Verfahren noch nach Algorithmen mit einer vorher bekannten Anzahl von Iterationsschritten, z. B. bilde n-Fakul6it n!= 1.2.3-....n, mit n Iterationsschritten oder nach einer vorher unbekannten Anzahl von Iterationsschritten, z. B. bestimme die Eulersche Zahl e hinreichend genau bilde x = 1+

i

i

, solange x n - Xn_1 < E,

wobei ~ eine sehr kleine Zahl darstellt. Rekursive Algorithmen

Rekursive Algor~tbmen sind eine besondere Art von iterativen A1gorithmen, bei denen die Rechenschritte aus dem eigentlichen Algorithmus bestehen, so dass dieser wiederholt angewendet wird, z. B. rekursive Bestimmung von n-Fakult~t n!=n.(n-1)!, ergibt sich aus der Bestimmung von (n-1)-Fakult~it und diese wiedemm aus (n-2)-Fakultfit (n-1)!=(n-1).(n-2)!, zurtick schreitend bis man das definierte 0!=1 erreicht. Bei rekursiven Algorithmen ist besonders auf die Endlichkeit der Prozedur zu achten.

Entscheidungsund OptimierungsAlgorithmen

Nach der Art der Problemstellung unterscheidet man zwischen Entscheidungs- und Optimierungsalgorithmen. Entscheidungsalgorithmen stellen in ihrer komplexesten Form ein Expertensystem dar. Optimierungsalgorithmen gibt es mit den unterschiedlichsten Methoden. Eine Einteilung l~sst sich vornehmen zwischen den Methoden die eine optimale L6sung und denen die zwar eine L6sung bieten, die aber nicht unbedingt die optimale 5 ,

,

.

1.4

A lgo rith m en k lassen sein muss. Ebenso zwischen denen, die nur eine L6sung bieten und denen, die alle L6sungen der Methode anzeigen.

Operation Research

Die Anwendungen von Optimierungsmethoden auf milit~irische, industrielle, wirtschaftliche, staatliche und soziale Prozesse sind unter dem Begriff Operation Research bekannt geworden. Erstmals im zweiten Weltkrieg eingesetzt, wurden diese Methoden Anfang der ftinfziger Jahre auch for die Industrie und staatliche Stellen interessant. Mit dem Aufkommen digitaler Rechenanlagen werden sie bei Simulationen, Kostenoptimierungen, Lagerhaltungstheorien, Warteschlangenproblemen, Netzwerkanalyse, Transportproblemen, Auftragsplanungen und vieles mehr. Das gr61~te Problem besteht heute in der Bestimmung des besten Verfahrens.

Kognitive Algorithmen

Auf der Suche nach immer neuen Algorithmen wurde auch wieder die Natur als Vorbild entdeckt. Es wurde und werden Mechanismen und Entscheidungsprozesse in der Natur gefunden, die sich auch in anderen Gebieten verwenden lassen. Ftir diese, als kognitive Algorithmen bezeichneten Methoden, spielen die M6glichkeitslogik (Fuzzy-Logic) und Minstliche neuronale Netze (KNN) eine wichtige Rolle.

Abb. 1-1 Systemwissen versus Algorithmenklassen

Genetische Algorithmen

Hybr~de Algorithmen 6

Ebenso die Gruppe der genetischen Algorithmen, die Fortpflanzungsmechanismen simulieren. Hierbei geht es mitunter um ftir das menschliche Verst~indnis sehr einfache F~ihigkeiten, deren Realisierung im Computer allerdings grol~en Aufwand erfordert. Es werden auch Kombinationen dieser Methoden zur L6sung eingesetzt, die als hybride Algorithmen bezeichnet werden. Be-

1 Algorithmen zeichnend ist, dass mit abnehmendem Systemwissen die Anwendungsm~Sglichkeiten kognitiver Algorithmen steigen.

K~nstliche Intelligenz

Die Zukunft hat gerade erst begonnen

Der Begriff K~nstliche Intelligenz (KI) stellt eher ein Forschungsgebiet, als eine einzelne Methode, geschweige denn einen Algorithmus dar. Mit den Expertensystemen ist ein erster sinnvoller Ansatz gefunden, dem sicher auch andere folgen werden. Was Algorithmen letztlich leisten k6nnen, l~isst sich heute noch nicht beantworten. Um es mit einem saloppen Ausspruch zu sagen, den ich erst ktirzlich gelesen habe: ,,Die Zukunft hat gerade erst begonnen!". Und dies gilt besonders for Algorithmen. Mit der immer weiter fortschreitenden Entwicklung der Computer sind neuronale Netze und parallele Algorithmen Wirklichkeit geworden. Aber auch an den Postulaten der Algorithmen wird gertittelt. Ein Algorithmus setzt voraus, dass alle Eingangsdaten bekannt sind. Es gibt jedoch Situationen, in denen Algorithmen erste Daten liefern mtissen, bevor alle Daten vorliegen. Die Entscheidungen treffen for etwas, was erst noch passiert. Die zuktinftige Neuund Weiterentwicklung von Algorithmen wird sicher spannend bleiben.

1.5

Das Konzepteiner Probleml6sung

ProblemlOsung

Computer sind ein unverzichtbares Hilfsmittel bei der Bearbeitung von Probleml6sungen geworden. Wurden sie bisher zur Ermittlung und Speicherung von Daten eingesetzt, so werden sie immer mehr auch aktiv zur Probleml~Ssung herangezogen. Mit Hilfe neuerer Algorithmen und immer schnellerer Systeme lassen sich selbst umfangreiche Probleme in kOrzester Zeit 16sen. Dabei hat die Simulation komplexer naturwissenschaftlich-technischer Zusammenh~inge einen hohen Stellenwert.

Abb. 1-2 blackbox

7

1.5

Das Konzept einer Probleml6sung

black box

Die Probleml6sung beginnt in der Regel bei der Beschreibung des Problems als Black Box. Uber die Definition des Outputs, l~sst sich der Input oft direkt herleiten. Und damit auch deren Umwandlung tiber mathematisch-physikalische Zusammenh~inge.

Abb. 1-3 Schema der L6sungsfindung

Schema einer L6sungsfindung

8

Mitunter sind jedoch auch Vereinfachungen und Abstraktionen notwendig. Immer mit der Malggabe, ein ad~iquates Modell des Problems zu erhalten, an dem sich die L6sung des Problems nachvollziehen l~isst. Die Abstraktion des Modells muss so lange erfolgen, bis ein geeigneter Algorithmus eingesetzt werden kann. Liegt der Algorithmus fest, erfolgt die L6sungsfindung unabh~ngig vom Computer, in Form eines Flussdiagramms, eines Struktogramms oder einer Pseudosprache. Erst danach sollte die Auswahl des Computers, die Wahl des Betriebssystems und der Programmiersprache erfolgen. Es folgt die Programmierung mit der

1 Algorithmen Wahl der Prozeduren und Datenstrukturen. Die Entwicklung schlielgt mit umfangreichen Tests und Ergebnisanalysen ab. Entspricht die gefundene L6sung nicht den Anforderungen, mtissen einzelne Schritte oder der gesamte Zyklus wiederholt werden. Diesen Zusammenhang zeigt anschaulich die Abbildung 1-3.

1.6

Heuristik Man kann kein Buch tiber Algorithmen schreiben, ohne wenigstens die Heuristik- die Wissenschaft des Probleml6sens zu erw~ihnen.

Heuristik

Die Geschichte der Algorithmen ist immer auch ein Teil der Heuristikgeschichte. So haben Euklid, Mohammed ben Musa al Khovaresni, Lullus, Descartes, Leibnitz, u. a. immer erst im heuristischen Sinne geforscht und ihre Ergebnisse waren nicht nur Algorithmen.

Fritz Zwicky und sein Morphologischer Kasten

Zur L6sung im heuristischen Sinne ist weder ein Algorithmus noch ein Computer erforderlich. Manchmal muss man zur LOsungsfindung noch ,,vor" dem Algorithmus einsteigen. An dieser Stelle m6chte ich ganz besonders den Namen Fritz Zwicky (1898-1974) nennen, der mit seiner Konstruktion und Auswertung des Morphologischen Kastens auch mir immer wieder neue Denkans~itze geliefert hat. Ich will nachfolgend seine fOnf Schritte zur L6sungsfindung kommentarlos wiedergeben.

Zwickys Schritte zur LOsungsfindu ng

Erster Schritt Erstellung einer genauen Umschreibung oder Definition sowie der zweckm~ilgigen Verallgemeinerungen des vorgegebenen Problems. Zweiter Schritt Bestimmung aller Parameter, die die L~Ssung beeinflussen. Dritter Schritt Erstellung des Morphologischen Kastens, in dem alle m6glichen L6sungen des Problems ohne Beurteilung eingetragen werden. Vierter Schritt Analyse aller im Morphologischen Kasten enthaltenen L6sungen bezOglich ihrer Realisierbarkeit oder anderer Werte. Ftinfter Schritt Wahl der nach der Analyse optimalen L6sung sowie deren Realisierung und Konstruktion. 9

1.6

Bierdeckelaufgabe

Heuristik Zwickys Morphologischer Kasten erlaubt die Aufgabe von Vorfixiemngen und Denkblockaden. Ein for Ingenieure typisches Denkbeispiel heilgt Bierdeckelaufgabe [1]. Dabei geht es datum, neun Punkte auf einem Bierdeckel mit m6glichst wenigen geraden Linien zu verbinden. Die tibliche L6sung finden Sie in Abb. 1-4.

Abb. 1-4 Ubliche L/Ssung der Bierdeckelproblems

Gibt man die Restriktion ,,auf dem Bierdeckel zeichnen" auf und ebenso die Restriktion, dass die Linien durch die Mitte der Punkte gehen mtissen, dann erh~ilt man eine L6sung mit drei Geraden (Abb. 1-5). Gibt man als weitere Restriktion die Unantastbarkeit des Bierdeckels auf, und zerschneidet man diesen, so gelingt sogar eine L6sung mit einer Linie.

Abb. 1-5 Ltisungnach der Aufgabe von Restriktionen

10

1 Algorithmen

Abb. 1-6 Eine dreidimensionale L6sung

Tab. 1-1 Teil eines Morphologischen Kastens Linienf0hrung

auf dem Bierdeckel

tiber den Bierdeckel hinaus

dreidimensional

Bierdeckel

keine _Anderung

falten

zerschneiden

Punkte

normal

stark vergr6Bert

./.

USW.

Morphologischer Kasten

Es gibt sogar eine Fuzzy-L6sung neben vielen weiteren L6sungen. Die Befreiung von Fixierungen gelingt fast methodisch durch den morphologischen Kasten.

Heuristische Probleml6sungsmethoden

Aber auch Groner & Groner [2] nennen heuristische Probleml6sungsmethoden. 9

Metakognitive Planung (Welche Heuristik?).

9

Aufgabenanalyse (Input, Output).

9

Abstraktion durch Reduktion und/oder Amplifikation (weglassen oder erg~inzen).

9

Wahl der Repr~isentation (Problemdarstellung).

9

Analogien (gibt es ein ~ihnlich gel6stes Problem).

der

einzusetzenden

Heuristiken

11 -

~..

9

.

.

1.6

Heuristik 9

Teill6sungen (top-down-design).

9

Hypothesen prtifen (angenommen dass ..., stimmt dann auch ...).

9

Trennung von Einflussgr61gen (ist y abh~tngig von x oder x und y abh~ngig von z).

9

Aufgabe von Fixierungen, Inkubation (Arbeit beiseite legen und sp~.ter wieder aufgreifen).

9

Nutzung des eigenen Unwissens (wie wgrde ich die Aufgabe 16sen, bevor ich recherchiert habe, was andere getan haben).

Diese Punkte sind weder vollst~tndig noch in der Reihenfolge anzuwenden. Die Heuristik ist ein weites und immer spannendes Bet~tigungsfeld.

12

2 LOsungen von Gleichungen

L6sungen von Gleichungen ~..

.

.

.

.

.

.

.

,

9

.~

~

"

;

.........

~

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

~

"

~

5

.

~

.

.

.

.

.

~ .

...

.

"

.

.

.

.

.

.

Gleichungen geh6ren nach den Zahlen zu den ersten mathematischen Errungenschaften der Menschheit. Bevor sich eine algebraische Schreibweise ftir Gleichungen gebildet hatte, wurden diese in Worte gefasst. Noch heute werden Dreisatzaufgaben gerne mit Worten beschrieben.

2.1

LSsungen von quadratischen Gleichungen Quadratische Gleichungen haben die allgemeine Form

Quadratische Gleichungen

x 2 + ax + b - 0

(2.1.1)

Sind die Koeffizienten dieser Gleichung reell, treten drei L6sbarkeitsf~tlle auf. Die L6sungen sind entweder reell und verschieden, reell und fallen zusammen oder konjugiert komplex ohne reelle L6sung. Die L0sungsformel ftir die reellen F~ille lautet allgemein

oI(2/

Diskriminante

Xl, 2 - - - ~ +

- b

(2.1.2)

Der Radikand der Wurzel wird als Diskriminante (lat. discriminare, trennen, scheiden) D -

-b

(2.1.3)

bezeichnet und ist ausschlaggebend ftir die Art der L6sungen. Ist D>0 gibt es zwei reelle L6sungen. Ist D=0 nur eine reelle L6sung. Und ist D 0 T h e n If O b l ( V , d2) 0 tI ' d e r

der Werte in der PivotSpalte

i

i

pz

i

For

=

0

i If

=

1 To

A(i, d

m

.

ps)

>

0 Then

= A(i,

n

+

If

End E n d If Next i

pz = 0 Or min = d pz = If

i) d

/ A(i, < min

ps)

Then

i

L_..........................................................................................................................................................................................................

52

3 L6sungen linearer Gleichungssysteme .....................................................................................................................................................................................................................................................................................-~

'U m f o r m u n g For i = 1 To For j = 1 If N o t Not B(i,

E n d If Next j Next i For i = 1 To n + 1 If N o t i = p s T h e n B(pz, i)= A(pz,

i)

E n d If Next i For i = 1 To m + 1 If N o t i = p z T h e n B ( i , ps) : - A ( i ,

ps)

E n d If Next i B ( p z , ps) 'N e u e

m + 1 To n + 1 i = pz And _ j = ps Then j)= A(i, j)A ( p z , j)

: 1

/ A(pz,

/ A(pz,

Cells(i Next Next i

/ A(pz,

ps)

ps)

B(i, j)

+ 2,

j)=

B(i,

'S c h l ei f e n b e d i n g u n g k = 0 For i = 1 To n If A ( m + I, Next i Loop While

j)

j

'Marken vertauschen z = Cells(pz + 2, n + 3) Cells(pz + 2, n + 3) = C e l l s ( m Cells(m + 5, ps) = z

ii E n d

ps)

Tabelle eintragen For i = 1 To m + 1 For j = 1 To n + 1

A(i, j ) = i !

A ( i , ps) * _ / A ( p z , ps)

k

+ 1 i)
2. Die Ableitungen ergeben sich zu Pi'(x) = b i + 2 c i ( x - x i ) +

3di(x-xi)

2.

(4.1.9)

und pi"(x ) = 2c i + 6 d i ( x - x i ) .

(4.1.10)

Aus der G15.ttebedingung zwischen zwei Polynomen folgt Pi" (xi ) - ei"-I (xi )

(4.1.11)

2c i = 2ci_ 1 + 6d/_l (x i - x i _ 1 )

und daraus mit hi-xi+,-x i 1 di-1 = - ~ i (ci - c i - 1 ) .

(4.1.12)

Aulgerdem mtissen die Polynome sich in jedem Knoten berOhren, woraus folgt Pi (xi ) = Pi-1 (xi ) = _ )3 ai ai-1 + bi_l (x i xi-1 ) + ci-1 (x i _ xi-1 ) 2 + di_l (x i _ Xi_l (4.1.13) Durch Umstellung und Einsetzen von (4.1.12) folgt

66

4 Funktionen 1 hi b i - g (ai+ 1 - a i ) ---~- (Ci+l - 2ci )

(4.1.14)

Aus der Stetigkeit folgt weiterhin, dass auch die ersten Ableitungen im Knoten gleich sein mtissen el' (xi ) = Pi'-I (xi )

(4.1.15)

bi = bi_l + 2ci_ 1 (x i _ Xi_l ) + 3di_ 1 (x i _ Xi_l )3 Durch Umstellung und Einsetzen ergibt sich ein lineares Gleichungssystem mit n-1 Gleichungen for n+l Unbekannte bei bekannten ai mit hi_lCi_ 1 + 2c i (hi-1 + h i )+ hiCi+l =

3 3 hT(ai+l - a i ) - ~ i _ l (ai - a i _ 1)

(4.1.16)

i = l(1)n - 1 Fassen wir diesen Berechnungsalgorithmus in Struktogrammform zusammen. Der Algorithmus enth/ilt einen Teil-Algorithmus zur L6sung eines Gleichungssystems, wie zuvor im Kapitel 3 unter Gaufg-Algorithmus beschrieben.

Als Beispiel zur Programmiemng benutzen wir den zuvor behandelten Seilverlauf. Tab. 4-3 Algorithmus zur Ermittlung der Koeffizienten eines kubischen Splines i=0,1,n

ai=y i

C0= Cn= 0

L6se Gleichungssystem for ci i=1,1,n-1 hi-Xi§

i

67

4.1.2

Interpolation mittels kubiscber Splines

hi_lCi_ 1 + 2C i (hi-1 + h i )+ hiCi+l 3

hi

3 (ai+ 1 - ai ) - 7 - - - (a i - ai_l )

ni_l

i=O,l,n-1

hi -~ (Ci+l - 2Ci )

1

bi = -hT (ai+l - ai ) i=O,l,n-1 1

di-1 =-~i (ci - c i - 1 ) i=O,l,n-1

Pi(x)=ai+bi(x

xi)+ci(x-xi)2+di(x

xi) 3

C _od._e4"2__Inte~ol_at!.o_n .._~.'_~..e._!s..kub!sc.h_er...S_p!i_nes.................................................................................................................................................................. Option

Explicit

S u b N e w t o n _ L e e r () Call Verlauf_Entfernen ThisWorkbook. Worksheets End Sub

( " N e w t o n " ) .C e l l s . C l e a r

Sub Newton_Testdaten () Call Newton_Leer Cells(l, i) = 0- C e l l s ( l , 2) = 30 Cells(2, i) = i0- C e l l s ( 2 , 2) = 18 Cells(3, I) = 20- C e l l s ( 3 , 2) = i i . 5 Cells(4, i) = 30- C e l l s ( 4 , 2) = i0 Cells(5, i) = 3 5 - C e l l s ( 5 , 2) = 1 0 . 5 Cells(6, i) = 40- C e l l s ( 6 , 2) = 1 2 . 5 C e l l s (7, i) = 50- C e l l s (7, 2) = 20 End Sub

t i.z

Private Sub Werte_Lesen(n, D i m i, j As I n t e g e r

A)

,

I 'Bestimmung belegter Zeilen i j 'und D e f i n i t i o n der notwendigen

68

Datenfelder

4 Funktionen '..............C-e-fi-s-({ows-.-Count-]

........

.............................................................................................

n = ActiveCell.Row R e D i m A ( n , n) A s D o u b l e For i = 1 To n For j = 1 To 2 A(i, j)= Cells(i, Next j Next i End Sub Private Dim

Sub Steigungen(n, i, j A s I n t e g e r

j)

A)

For

j = 3 To n + 1 For i = 1 To nj + 2 Cells(i, j) = ( C e l l s ( i + i, Cells(i, j - i)) / ( C e l l s ( i Cells(i, i)) Next i Next j Exit Sub End Sub Private

Sub

Dim Dim

v, i,

Verlauf

b, j,

x, k,

(n,

j +

- i) - _ j - 2, i)

-

A)

y, z A s D o u b l e p As Integer

p = 0 v = Cells(l, i) b = C e l l s (n, i) For x = v To b Step 1 y = Cells(l, 2) For j = 3 To n + 1 z = Cells(l, j) For k = 1 To j - 2 Next y Next

z = k

= y j

p = p + Cells(n Cells(n Next x !End

z +

1 + 2 + 2

*

(x

- Cells(k,

i))

z

+ p, + p,

i) 2)

= x = y

Sub

I i

i Sub

Auswertung

()

i

69

4.1.2

Interpolation mittels kubischer Splines

...................i ~ a i ~ - i g ~ - i Y 7

......-{-i .... ~

Dim

Integer

n As

......i ~ g a i ~ i - a

.............................................................................................................................................................................................. '

C a l l W e r t e _ L e s e n (n, A) C a l l S t e i g u n g e n ( n , A) C a l l V e r l a u f ( n , A) End Sub Sub Verlauf_Zeigen() Range("Al0-B60").Select Charts.Add ActiveChart.ChartType = xlXYScatterSmoothNoMarkers ActiveChart. SetSourceData Source:= _ Sheets("Newton").Range("Al0-B60"), PlotBy-= _ xlColumns ActiveChart.Location Where-=xlLocationAsObject, Name-="Newton" With ActiveChart .HasTitle = True .ChartTitle.Characters.Text = "Seilverlauf" .Axes(xlCategory, xlPrimary).HasTitle = True .Axes(xlCategory, _ xlPrimary).AxisTitle.Characters.Text = "Weite .Axes(xlValue, xlPrimary).HasTitle = True .Axes(xlValue, _ xlPrimary).AxisTitle.Characters.Text = "H~he

[m] "

Era] "

! End With i ActiveChart.Legend. Select ' Selection. Delete 1End Sub j Sub Verlauf_Entfernen() Dim Shp As Shape ! F o r E a c h S h p In W o r k s h e e t s ( " N e w t o n " ) . S h a p e s Shp. D e l e t e i Next !

Das Men/3 gestaltet sich analog zum vorherigen Beispiel. Die Auswertung der Testdaten finden Sie in Abbildung 4-7.

7O

4 Funktionen

Abb. 4-6 Menti zur Interpolation mittels kubischer Splines

Abb. 4-7 Seilverlauf, ermittelt durch kubische Splines

71

4.2

Approximation von Funktionen durch Polynome

Ubungen Die Methode versagt, wenn der 1. Koeffizient in der 1. Gleichung, der 2. Koeffizient in der 2. Gleichung, usw. Null sind. Dieses Problem kann durch Vertauschung behoben werden, da, wenn es eine L6sung gibt, dies auch m6glich ist. Der Algorithmus ist entsprechend zu erg~inzen.

4.2

Approximationvon Funktionendurch Polynome

Approximation

Im Gegensatz zur Interpolation, wird bei der Approximation nicht verlangt, dass die Funktion in den Sttitzstellen den vorgegebenen Wert annimmt. Hier z~ihlt vielmehr die bestm6gliche Ann~iherung an den Funktionsverlauf nach einer definierten Methode. Nachfolgend betrachten wir die Approximation nach der Methode der kleinsten Fehlerquadrate for lineare Gleichungen. Bei dieser Methode werden die Parameter so bestimmt, dass sich das Polynom mit dem kleinsten quadratischen Abstand an diese Werte anschmiegt.

Methode der kleinsten Feb lerquadrate

Abb. 4-8 Grafische Darstellung der Methode der kleinsten Fehlerquadrate

Lineare Approximation

72

Bei der linearen Approximation sind die Koeffizienten der Geraden y = ax + b (4.2.1)

4

Funktionen

gesucht, so dass die Summe der Abweichungen s i zu jedem Messwert (x i, yi) im Quadrat aller Messwerte n ein Minimum annehmen. Mathematisch lautet die Bedingung 2 n n Z b i --(ax i -k-b)] = Z s 2 = M i n i m u m . i=1 1=1

(4.2.2)

Wir erhalten ein lineares Gleichungssystem der Form a'l 1b + a12 a = ,ill

9

(4.2.3)

a21b + a22a - f12

Abb. 4-9 Lineare Approximation

In Matrizenschreibweise ergibt sich die Minimum-Bedingung y=A.c+s

(4.2.4)

mit

73

4.2

Approximation von Funktionen durch Polynome

y=

lyil Ii!l n

S--

lXl / A= ... ,

c=

/:i

und

~,lxn

(4.2.5)

Wir erhalten die gesuchte L6sung c = ( A T .A) -1 .(A T .y).

(4.2.6)

Beispiel: Sensorkennlinie Sensorkennlinie

Sensoren haben oft eine nichtlineare Ist-Kennlinie, die durch eine lineare Soll-Kennlinie beschrieben wird. Die Abweichung wird als Linearit~tsfehler bezeichnet und wird auf zwei verschiedene Arten definiert. Die erste Methode besteht darin, eine lineare Kennlinie durch Verbinden der beiden Endpunkte (xmin, janin) und (arnax, .}a'nax) zu bilden und wird Festpunktmethode genannt. 100%

Y yr~ax

~

J

', Nichtlmearitat

x X1TIaX

00% Abb. 4-10 Lineare Approximation nach der Festpunktmethode

Die zweite Methode erstellt eine lineare Approximation nach dem Minimum der Fehlerquadrate. Diese Methode ergibt typischerweise die H~ilfte des Linearit~itsfehlers der Festpunktmethode.

74

4 Funktionen

1 O0%

Y ymax

\

r

x 100% Abb. 4-11 Lineare Approximation nach dem Minimum der Fehlerquadrate

Das nachfolgende Programm ermittelt beide Geraden nach Eingabe von beliebigen Messwerten in den ersten beiden Spalten der Tabelle.

Tab. 4-4 Algorithmus zur Ermittlung der approximierenden Geraden

Einlesen der Daten i--1,1,n xi=Zelle(i, 1) yi=Zelle(i,2) EX-" Zx-I- x i

~y=Ey+ y~ 2

2

Ex =Ex + xi. x~ )-",xy=)-',Xy+ Xi . Yi

p

9 q_

~

~

Yn - Y l Xn

Xl

Yn

(Yn

-

Yl)

(x n - X l ) ' X n

75

4.2

Approximation von F u n k t i o n e n durch Polynome

Bestimmung der Geradenwerte

i=l,l,n Yi = P'Xi +q

p

q

~

---

Bestimmung der Geradenwerte

i=l,l,n Yi = P'Xi +q

Das Menti gestaltet sich analog zum vorherigen Beispiel. Die Auswertung der Testdaten finden Sie in Abbildung 4-13. Option

Explicit

Sub

LinAppro_Leer () ThisWorkbook. Worksheets ("Lineare Approximation" End Sub Sub

LinAppro_Testdaten Call LinAppro_Leer Cells(l, i) = 20i Cells(2, i) = 30" i Cells(3, i) = 40Cells(4, i) = 50' Cells(5, I) = 65' Cells(6, I) = 70Cells(7, i) = 80i Cells(8, i) = 90Cells(9, i) = i00, End Sub

) .C e l l s . C l e a r

()

,i

Cells(l, Cells(2, Cells(3, Cells(4, Cells(5, Cells(6, Cells(7, Cells(8, Cells(9,

'

2) 2) 2) 2) 2) 2) 2) 2) 2)

= = = = = = = =

20 55 70 75 82 86 89 90 = 91

! i I i i

i

Private Sub Werte_Lesen D i m i, j A s I n t e g e r

76

(n, A)

i

4 Funktionen ......T ...........................................................................................................................................................................................................................

i

'Bestimmung belegter Zeilen 'und Definition der notwendigen Datenfelder Cells (Rows. Count, i) . E n d ( x l U p ) . S e l e c t n = ActiveCell.Row ReDim A(n, 2) A s For

i = 1 To 2 For j = 1 To A(i, j)= Next

Next End Sub

Double 2 Cells(i,

j)

j

i

Sub LinAppro_Auswertung () ReDim A(I, i) A s D o u b l e D i m p, q, sx, sy, s x x , s x y , Dim

n,

i As

y

As

Double

Integer

i

'D a t e n lesen Call Werte_Lesen(n,

A)

!

'F e s t p u n k t m e t h o d e p = (Cells(n, q

2)

-Cells(l,

2))

/ _

(Cells(n, = Cells(n,

i) 2)

- Cells(l, - (Cells(n,

I)) 2)

- Cells(l,

2))

(Cells(n,

i)

- Cells(l,

i))

* Cells(n,

i)

Cells(l,

7)

"y

="

Cells(l, Cells(l, Cells(l,

8) = p 9) = "x i0) = q

=

+"

/ _

!

'F u n k t i o n s w e r t e For i = 1 To n y = p * Cells(i, Cells(i, 3) = y Next i

I)

+ q

i

'K l e i n s t e For

I

Fehlerquadrate

i = 1 To n sx = sx + Cells(i, i) sxx = sxx + Cells(i, i)

sy = sy + Cells(i, 2) sxy = sxy + Cells(i, i) Next i

i * Cells(i,

i)

* Cells(i,

2) I

i

i P = (n * s x y - s x * sy) / (n * s x x - s x * sx) i i q = ( s y * s x x s x y * sx) / (n * s x x s x * sx) i ...........................................................................................................................................................................................................................J 77 ~

.

Approximation von Funktionen durch Polynome

4.2

Cells(3,

8)

Cells(3, Cells(3,

9) = "x i0) = q

= p +"

'Funktionswerte For

i = y

= p

1 To

Cells(i, Next

n

* Cells(i, 4)

i)

+ q

= y

i

End

Sub

Sub

LinAppro_Diagramm

()

Range("Ai-D9").Select Charts.Add ActiveChart.ChartType ActiveChart.

= xlXYScatterSmoothNoMarkers

SetSourceData

Sheets("Lineare

Source-=

Approximation").Range("AI-D9"),

PlotBy-=xlColumns ActiveChart.

SeriesCollection(1).Name

"= ....S e n s o r k e n n l i n i e ActiveChart.

SeriesCollection(2).Name

"= ....F e s t p u n k t m e t h o d e ...... ActiveChart. SeriesCollection(3).Name "= ....M e t h o d e der ActiveChart.Location "Lineare With

= _

...... =

_

= _

kleinsten Fehlerquadrate ...... Where-=xlLocationAsObject,

ActiveChart .HasTitle = True .ChartTitle.Characters.Text = "Approximation einer Sensorkennlinie" .Axes(xlCategory,

xlPrimary).HasTitle

= True

.Axes(xlCategory, _ xlPrimary).AxisTitle.Characters.Text % ,, .Axes(xlValue,

xlPrimary).HasTitle

.Axes(xlValue, _ xlPrimary).AxisTitle.Characters.Text % ,, End With ActiveWindow.Visible End

Sub

! I

i i Sub

LinAppro_Entfernen() Dim

78

N a m e 9=

Approximation"

Shp

As

Shape

= False

=

"x / x m a x

=

"y / y m a x

= True

4 Funktionen i

For E a c h

Shp In W o r k s h e e t s ( " L l n e a r e tion") Shapes i ' l Shp. D e l e t e i Next i i E n d Sub

Approxima-

i i

i........................................................................................................................................................................................................................... ]

Abb. 4-12 Menii Interpolation nach Newton

Abb. 4-13 Beispiel der linearen Approximation einer Sensorkennlinie

79

4.3

Nu merische Integration

4.3

Numerische Integration Die geometrische Deutung eines bestimmten Integrals ist die FI~iche die zwischen x=a und x=b und von der Funktion y=f(x) und der x-Achse eingeschlossen wird.

Numerische Integration

Abb. 4-14 Bestimmtes Integral

In vielen F~.llen ist zwar die Funktion y=f(x) bekannt, aber es gibt keinen analytischen Ansatz zur Integration. Hier bedient man sich der Trapezregel oder der Simpsonschen Regel. Bei der Trapezregel wird das Intervall (a, b) in n gleich grolge Abschnitte unterteilt und die Kurvenstticke werden durch Geraden ersetzt.

Trapezregel

Abb. 4-15 Einteilung nach der Trapezregel

8O

4 Funktionen Ist h die Breite eines Trapezes und n die Anzahl der Intervalle so gilt

i_.h 2

h

h

(Yo + Yl)+-~(Y~ + Y2) +-"-~(Yn-1 + Y ) n

h = -~ ( f (x o ) + 2 f (x~) + 2 f (x 2 ) + ... + 2 f (Xn_1) + f (X,,)) mit

h-

b-a

.

(4.3.2)

n

Tab. 4-5 L6sungsalgorithmus:Numerische Integration nach der Trapezregel Eingabe der erforderlichen Parameter

X0, in, n, fix)

b-a h=~ n

i=O (1) n-1

Z y = Z y +f(xi )+ f(xi+l) h I=-~ZY

Die Trapezregel liefert umso genauere Werte, je kleiner h ist bzw. je mehr Intervalle n gesetzt werden. Die praktische Grenze liegt in den Rundungsfehlern der Berechnung. Bei der Simpsonschen Methode werden die Geraden durch Kurvenstticke tiber mehrere Intervalle ersetzt. Bei dieser Methode erwartet man in der Regel auch eine h6here Genauigkeit.

Trdger gleicher Zugfestigkeit

Beispiel: Tr~iger gleicher Zugfestigkeit Gesucht ist das Profil eines Stabes, der nach Abbildung 4-16 einer Zugkraft unterliegt, die in jedem Querschnitt konstant sein soil.

81

(4.3.1)

4.3

N u merische I n t e g r a t i o n

Abb. 4-16 Tr/igermit gleicher Zugfestigkeit

An einer beliebigen Stelle x mit dem Querschnitt A ergibt sich die Zugspannung

Px

Crx = ~ . A

(4.3.3)

Darin ist Fx die Kraft an der Stelle x, die sich zusammensetzt aus der ~iulgeren Kraft F u n d dem Gewicht der Masse unterhalb von X.

An der Stelle x+dx mit dem Querschnitt A+dA ergibt sich die Zugspannung Crx+~ =

Fx + P . A . d x . g A +dA

.

(4.3.4)

Darin ist p die Materialdichte und g die Erdbeschleunigung. Da die Spannung tiber die ganze Tr~igerl~inge 1 konstant sein soil, folgt aus der Gleichsetzung dA = p . g . dx . A o"

(4.3.5)

Das Integral liefert

~dAA = l n A

(4.3.6)

so dass sich ein logarithmischer Verlauf ergibt. Wir wollen dieses Integral auf numerischem Wege 16sen. Die einfachste Form bietet die Rechteckregel.

82

4

Funktionen

Tab. 4-6 L6sungsalgorithmus:Tr~igergleicher Zugspannung Eingabe der erforderlichen Parameter A0, 1, P, ~, n .

.

.

.

.

.

.

.

x=/Xx,(Ax),l

9

AA x

-

P'g

.Ax_ 1 .Ax

t7 A x = Ax_ 1 + AA x

Die Erstellung des Programms erfolgt nach dem Oblichen Schema Formblatt-Testdaten-Auswertung-Grafik. Option Sub

Explicit

Zugspannung_Leer() Dim Shp As Shape F o r E a c h S h p In W o r k s h e e t s ( " K o n s t a n t e nung").Shapes Shp.Delete Next ThisWorkbook.Worksheets("Konstante" "Zugspannung").Cells.Clear

Zugspan-

&

R a n g e ( "A1 :E1" ) .S e l e c t Selection.MergeCells = True Selection. Font.Bold = True Selection. Font. Italic = True Selection.Value = "Tr~ger mit konstanter Zugspannung" R a n g e ("A2 :AI6") . S e l e c t Selection. Font.Bold = True Selection. Font. Italic = True Range("A2") : "Ao [m" & C h r W ( 1 7 8 ) & " ]" Range("A3") = "i [m]" Range("A4") : ChrW(961) & " [kg/m" & C h r W ( 1 7 9 ) & " ]" ! Range("A5") = ChrW(963) & " [N/m" & C h r W ( 1 7 8 ) & " ]" ! R a n g e ("A6") = "n" i i R a n g e ( "B- B" ) .C o l u m n W i d t h = "15" ~............................................................................................................................................................................................................................

i i i l ! ]

83 ._

...

4.3

Nu merische Integration

:...............................................................................................................................................................................................

j! i

Range Range

( "C :C " ). C o l u m n W l d t h ' ( " D 2 " ) = "x [m] "

=

"2 "

Range("E2") : "A [m" & C h r W ( 1 7 8 ) R a n g e ( "D2 :E 2 " ) . S e l e c t Selection. Font. Bold = True Selection. Font. Italic R a n g e ( "B2" ) . S e l e c t End Sub

= True

Sub

()

Zugspannung_Testdaten Cells(2, 2) = 0 . 2 C e l l s (3, 2) = 0 . 5

Cells(4, Cells(5, Cells(6, End Sub Sub

2) 2) 2)

A0 1 r S n dx Ax i

= Cells(2, C e l l s (3, Celis(4, C e l l s (5, Cells(6, = 1 / n = A0 = 2

I

~ i [J

()

2) 2) 2) 2) 2)

x = dx To 1 + dx dA = r * 9.81 / S Ax = Ax + dA i = i + 1 Cells(i, 4) = x Cells(i, 5) = A x Next x End Sub Sub

" ]"

A0, i, r, S, n A s D o u b l e dx, x, dA, A x A s D o u b l e i As Integer

= = = =

For

&

= 0.00785 = 0.01 = 50

Zugspannung_Auswertung Dim Dim Dim

.............................................................................................

Step * Ax

dx * dx

Zeige_Querschnittsverlauf() Range("D3:E52").Select Charts.Add ActiveChart.ChartType = xlXYScatterSmoothNoMarkers ActiveChart. SetSourceData Source:= _ Sheets("Konstante Zugspannung") P l o t B y 9= x l C o l u m n s

.Range("D3-E52"),

j _

~ i

........................................................................................................................................................................................................................... ]

84

4 Funktionen i !

ActlveChart. SerlesCollectlon(1).Name = _ "= ....Q u e r s c h n i t t s v e r l a u f ...... ActiveChart.Location Where-= xlLocationAsObject, Name-="Konstante Zugspannung" With ActiveChart .HasTitle = True .ChartTitle.Characters.Text = "Trager mit konstanter Spannung" .Axes(xlCategory, xlPrimary).HasTitle = True .Axes(xlCategory, _ xlPrimary).AxisTitle.Characters.Text = "x [mm]" .Axes(xlValue, xlPrimary).HasTitle = True .Axes(xlValue, _ xlPrimary).AxisTitle.Characters.Text = "A

J

m

[mm^2] '' End With ActiveChart.Legend. Select S e l e c t i o n . L e f t = 229 S e l e c t i o n . T o p = 274 ActiveChart.Axes(xlValue).MajorGridlines. ActiveChart. PlotArea. Select Selection.Width = 314 ActiveWindow.Visible = False End Sub L6sche_Querschnittsverlauf() Dim Shp As Shape F o r E a c h S h p In W o r k s h e e t s ( " K o n s t a n t e nung").Shapes Shp. D e l e t e i Next i End Sub

Select

Sub

Zugspani ! i

Die Prozeduren werden wiederum durch MenOpunkte im MenO Konstante Zugspannung aufgemfen

Abb. 4-17 Menti Konstante Zugspannung

85

4.3

Nu merische Integration

Abb. 4-18 Auswertungder Testdaten

Abbildung 4-18 zeigt das Ergebnis aus den Testdaten. Daraus geht hervor, dass der Querschnitt des Stabes sich exponentiell ver~tndern muss, um eine konstante Zugspannung zu gew~thrleisten.

Obungen Der Algorithmus berechnet den Querschnittsverlauf nach der Rechteckregel. Zuvor haben wir schon die Trapezregel kennen gelernt. )kndern Sie die Berechnung in die nach der Trapezregel ab.

86 ..

.

.

.

.

.

"

. ~

4

Funktionen

Der Querschnittsverlauf sagt noch nichts tiber die eigentliche Tr~igerform (rund, quadratisch, rechteckig, ...) aus. Erg~inzen Sie das Programm um diese Berechnungsm6glichkeiten.

Beispiel: Ausflusszeit von FlOssigkeiten Wir betrachten einen Beh~ilter, in dem sich Fltissigkeit mit der H6he h befindet. A u s f l u s s z e i t von Flfissigkeiten

Nach dem italienischen Physiker Torricelli bestimmt sich die Ausflussgeschwindigkeit aus ,,,

v = ~/2. g- h .

(4.3.7)

Abb. 4-19 Ausfluss aus einem Behalter

Ebenso bestimmt sich die Ausflussmenge aus O=A.v.

(4.3.8)

Der variable Gef~ilgquerschnitt ist durch die Funktion y = f(x)

(4.3.9)

gegeben. Zum Zeitpunkt t betr~igt die Fltissigkeitsh6he x. FOr ein kleines Zeitintervall dt sinkt der Fltissigkeitsspiegel um dx und die austretende Menge berechnet sich, unter der Idealisierung, dass der Querschnitt im Zeitraum dt konstant ist, aus A o 9~/2. g. x . dt = A ( x ) . dx.

(4.3.10)

Umgestellt ergibt sich for das Zeitelement

87

4.3

Numerische Integration dt =

A(x) . dr

9

(4.3.11)

AO~/2. g . x Die Integration zum Zeitpunkt t, zu dem der FlOssigkeitsspiegel die H6he x hat, liefert t

o

x

ao

Die L6sung lautet

1 t=

X~A(x)

Ao 24g 4;x

dr.

(4.3.13)

Damit kOnnen wir den Berechnungsalgorithmus aufstellen. Diesmal verwenden wir einmal die Trapezregel zur Berechnung des Integrals und gleichzeitig bestimmen wir die Zeit aus dem Differenzenquotienten. Dazu gibt es nach Abbildung 4-20 drei M6glichkeiten.

D if f eren zenquotienten

Abb. 4-20 Vorschrittige, rtickschrittige und zentrale Differenzen

Im Algorithmus werde die Differenzen in einer Programmschleife bestimmt, w~ihrend dabei nur die Summe der Funktionen for die Berechnung nach der Trapezregel entsprechend der Darstellung in Tabelle 4-5 erfolgt. Nach der Programmschleife wird dann auch die Ausflusszeit nach der Trapezregel bestimmt. Tab. 4-7 L6sungsalgorithmus:Numerische Integration nach der Trapezregel

88

4

Funktionen

Eingabe der erforderlichen Parameter Ao, h, u, n h-u

AX~'~

n t v =O,t r =O,t m = 0

k

__

A o ~/-2. g xi = h ( - A x ) u + A x

A(xi) Y i = "~i

A(Xi+l) Yi+l = ~[Xi+l Y = Yi +Yi+I

At v = k

A(xi) r--'"

t v = t v + At v A(Xi+l) At r = k

Ax

Xi+l t r = t r + At r A ( x i ) + A(Xi+l) At m = k

1

Ax

2 ~ xi + Xi+l

2 t m = t m + At m

89

4.3

Nu merische Integration kac

t=-~-EY

FOr die Form des Trichters wird eine eigene Prozedur geschrieben. So k6nnen auch andere Formen integriert werden.

Option Sub

Explicit

Ausflusszeit_Leer() Dim Shp As Shape For Each Shp In Worksheets("Ausflusszeit").Shapes Shp. Delete Next

ThisWorkbook.Worksheets("Ausflusszeit").Cells.Clear Range("Al:El").Select Selection.MergeCells = True Selection. Font.Bold = True Selection. Font. Italic = True Selection.Value = "Ausflusszeit bei abnehmendem R a n g e ( "A2 :A 7 " ) . S e l e c t Selection. Font. Bold = True Selection. Font. Italic = True Range("A2") : "A [mm" & C h r W ( 1 7 8 ) Ranc'e ("A3") : "h [mm] " Ranc e("A4") = "u [mm]" Rang,e("A5") = "n" Ranc_'e("A7") : "t (TR) [s]" R a n t re ( "B- B" ) .C o l u m n W i d t h = "15" Ranc re("C-C") .ColumnWidth = "2" R a n c re("D2") : "x [mm] " RancFe("E2") = "yl" Ranc[e("F2") = "y2" R a n c Fe("G2") : "tl [s]" Ranc[e("H2") : "t2 [s]" Ranc[e("I2") = " t m [s]" Ranc[e("J2") : " d t m [s]" R a n g e ( "D2 :J 2 " ) . S e l e c t Selection. Font.Bold = True Selection. Font. Italic = True

9O

FlOssigkeitsstand"

&

" ]"

4 Funktionen

.............{an .........eT' End

Bg

i-Tse

ect .......................................................................................................................................................

Sub

Sub

Ausflusszeit_Testdaten Cells

(2,

2)

=

i0

Cells

(3,

2)

=

400

Cells(4,

2)

=

i0

Cells

2)

=

50

End

(5,

()

Sub

Sub

Trichter_Form(h,

x,

Ax)

Dim r As Double r = i00 + i00 / h * x Ax = r * r * 4 * Atn(1) End Sub

! i

Sub Ausflusszeit_Auswertung D i m A, A x , A x l , A x 2 , h,

() u, dx,

Dim

k,

dt,

tl,

Dim

i,

n

dtl,

As

= Cells(2,

2)

h

= Cells(3,

2)

u

= Cells(4,

2)

n = Cells(5, i = 2

2)

dx

/ n

=

(h - u)

Ji 'S u m m a t i o n

t,

x,

t2,

t2 : 0- t = 0 (A * S q r ( 2 * 9810)) h To u + dx Step -dx Trichter_Form(h, x, A x l ) Trichter_Form(h, xdx,

yl Su y2

nach : Axl = Su + : Ax2

Su

=

Su

yl,

Su

As

y2

As

Double

Double

Integer

A

tl : 0k : 1 / For x = Call Call

dt2,

Ax2)

der Trapezregel / Sqr(x) yl / Sqr(x - dx)

+ y2

'Bestimmung von dt aus dem Differenzenquotienten dtl = k * Axl / Sqr(x) * dx I

i,

tl = tl dt2 = k

+ dtl * Ax2

t2

=

t2

+ dt2

Ax

=

(Axl

/ Sqr(x

+ Ax2)

- dx)

I I

* dx

i i

i

/ 2

[...........................................................................................................................................................................................................................

]

91 9 _

~

,

4.3

Nu merische Integration

i........................................................................................................................................................................................................................... 7

i !

dt = k * Ax t = t + dt

i I i i

'A u s g a b e i = i + 1 Cells(i, 4) Cells(i 5)

!

i

Cells(i, Cells(i, Cells(i, Cells(i, Cells(i, Next x

6) 7) 8) 9) i0)

/ Sqr(x-

dx

/ 2)

* dx

i i

= x = yl = = = =

y2 tl t2 t = dt

'Bestimmung der Ausflusszeit nach der Trapezregel t = S u * d x / 2 / (A * S q r ( 2 * 9 8 1 0 ) ) C e l l s (7, 2) = t End Sub Sub

i i i

i~ i 9 i

Zeitdifferenzen_zeigen() Range("D3-D51").Select ActiveWindow. ScrollRow = 14 ActiveWindow. ScrollRow = 13 ActiveWindow. ScrollRow = 12 ActiveWindow. ScrollRow = ii ActiveWindow. ScrollRow = I0 ActiveWindow. ScrollRow = 9 ActiveWindow. ScrollRow = 8 ActiveWindow. ScrollRow = 7 ActiveWindow. ScrollRow = 6 ActiveWindow. ScrollRow = 5 ActiveWindow. ScrollRow = 4 ActiveWindow. ScrollRow = 3 ActiveWindow. ScrollRow = 2 ActiveWindow. ScrollRow = 1 Range("D3-D51,J3-J51").Select Range("J3").Activate Charts.Add ActiveChart.ChartType = xlXYScatterSmoothNoMarkers ActiveChart. SetSourceData Source:= Sheets("Ausflusszeit").Range( "D3-D51,J3.J51"), PlotBy-=xlColumns ActiveChart.Location Where:= _ xlLocationAsObject, Name-="Ausflusszeit" With ActiveChart .HasTitle = True

...........................................................................................................................................................................................................................

92

!

! j i i J

4 Funktionen

.Axes(xlCategory, xlPrimary).HasTitle = True .Axes(xlCategory, _ xlPrimary).AxisTitle.Characters.Text = "h [mm]" .Axes(xlValue, xlPrimary).HasTitle = True .Axes(xlValue, _ xlPrimary).AxisTitle.Characters.Text = "dt [s]" End With ActiveChart.HasLegend = False End Sub Sub

Zeitdifferenzen_16schen() D i m S h p As S h a p e F o r E a c h S h p In W o r k s h e e t s ( " A u s f l u s s z e i t " ) . S h a p e s Shp. D e l e t e

i Next i End Sub

Auch dieses Beispiel erh~ilt wieder die klassische Aufteilung des Mentis.

Abb. 4-21 Menti Ausflusszeitbestimmung

Die Auswertung der Testdaten in Abbildung 4-22 zeigt einen interessanten Verlauf. Danach nimmt die Zeitdifferenz At for ein Volumenelement Ax st~indig ab bis zu einer H6he von 135 mm. Danach nimmt sie wieder zu, und dies liegt an der geringer werdenden Masse der Fltissigkeit.

Obungen In der Berechnung kann als unterster Wert nicht Null eingegeben werden, weil sonst innerhalb der Berechnung eine Division durch Null erfolgt. L6sen Sie dieses Problem. Vielleicht hilft Ih93 i Y /

-

. .....

.

k...J

.....

:

4.3

Nu merische Integration nen die L6sung des Integrals weiter? Erg~.nzen Sie aulgerdem die Berechnung durch andere Beh~ilterformen.

Abb. 4-22 Bestimmung der Ausflusszeit einer Fliissigkeit

94

5 Differentialgleichungen

Differentialgleichungen ~

Differentialgleichungen

~

g

~

.

~

.

.

.

.

.

.

.

.

.

.

.

.

Bei den Differentialgleichungen zeigt sich die Anwendbarkeit der Mathematik in der Technik besonders deutlich. Bei Differentialgleichungen handelt es sich um Gleichungen, die zur Berechnung einer bestimmten Funktion dienen. Das wesentliche einer Differentialgleichung ist, dass neben der Funktion oder der unabh~ngig Ver~nderlichen auch mindestens eine Ableitung der gesuchten Funktion auftritt. Die Besch~.ftigung mit Differentialgleichungen begann zeitgleich mit der Einf~ihrung der Differential- und Integralrechnung durch Newton und Leibniz zum Ausgang des 17. Jahrhunderts.

5.1

NumerischeBehandlunggew6hnlicher Differentialgleichungen Die numerische Behandlung einer Differentialgleichung l~sst sich nach vielen Methoden durchf~ihren.

Abb.5-1 N~ihemngnach Euler-Cauchy

Euler-CauchyVerfahren

Das Euler-Cauchy-Verfahren ist eine einfache Methode und hat damit eine gr61gere Fehlerrate gegenOber anderen Methoden. Da sie aber einfach zu handhaben ist, soil sie hier benutzt werden.

95 :.

_

.

5.1

Numerische Behandlung gewdhnlicher Differentialgleichungen Es sei (5.1.1)

y= f(x) die analytische L6sung der Differentialgleichung

y'= f (x, y) .

(5.1.2)

Aus der Differentialgleichung folgt die Anfangsbedingung t

YO = f(xo, YO)

(5.1.3)

als bekannter Wert. Eine Verlinderung des Abzissenwertes (5.1.4) X1 = X0 + ergibt den neuen Ordinatenwert ?

Yl = Yo + YO "Ax.

Differentialquotient

(5.1.5)

Auf diese Weise erhlilt man einen Polygonzug, der der gesuchten L6sungsfunktion angeniihert ist. Bei diesem Verfahren, wird also der Differentialquotient

dy

(5.1.6)

dx durch den Differenzenquotienten

Differenzenquotient

Ay Ax

(5.1.7)

ersetzt. W~.hlt man Ax genfigend klein, kommt man der analytischen L6sung beliebig nahe. Der Nachteil wird aus der Darstellung ebenfalls recht deutlich. Mit zunehmenden Schritten entfernt sich die numerische L6sung immer mehr v o n d e r analytischen. Ein genaueres Verfahren ist z. B. das Runge-Kutta-Verfahren.

Die Bewegungsdnderung eines Massenpunktes

Die Betrachtung des Kr~tftegleichgewichts an beweglichen Massenpunkten ffihrt unmittelbar zu einer Differentialgleichung. Ob dies nun einfache Bewegungsmodelle wie z.B. Rotationen sind oder komplexere Modelle wie z.B. Schwingungssysteme. Der Anderung des Bewegungszustandes setzt der Massenpunkt seine tr~tge Masse entgegen

F =-m.a.

96

(5.1.8)

5

Differentialgleichungen

Die Momentanbeschleunigung a ergibt sich als Differentialquotient dv a = -- = v , (5.1.9) p

dt

so dass die erste Anwendung des Euler-Cauchy-Verfahrens die w~ihrend der Zeiteinheit dt auftretende GeschwindigkeitsSnderung dv liefert F v = ---t. (5.1.10) m

FOr die Momentangeschwindigkeit gilt weiterhin der Differentialquotient ds v=--=s dt

t

(5.1.11)

,

so dass die zweite Anwendung des Euler-Cauchy-Verfahrens den w~ihrend der Zeiteinheit dt zurtickgelegten Weg ds ann~ihernd beschreibt s=v.t. (5.1.12) Die Momentangeschwindigkeit wird dabei aus Einfachheitsgrtinden ftir die Berechnung durch die Anfangsgeschwindigkeit des betrachteten Zeitintervalls ersetzt.

Beispiel: Schubkurbeltrieb

V

r+l

i

! rsmq~ Abb.5-2

Schubkurbeltrieb

97

5.1

Numerische B e b a n d l u n g gew6hnlicher Differentialgleichungen

Sch ubku rbeltrieb

Der Kurbeltrieb dient zur Umwandlung von Schub- in Drehbewegung und umgekehrt. Der algebraische Ausdruck ftir die Kolbenbewegung ergibt sich, unter Betrachtung der Abbildung 5-2, aus

x = l + r - l . c o s f l - r . s i n ~0,

(5.1.13)

Weiterhin ist 2 - r = sin____fl_fl,

l

(5.1.14)

cos

cos fl= t / 1 - 2 2 cos 2 (/7,

(5.1.15)

x = r . (1-sin qg)+ l - ( 1 - i / 1 - 22 cos 2 (~0).

(5.1.16)

Bei allgemeiner Phasenverschiebung x = r - ( 1 - sin ~0)+ I. (1-~/1- 22 cos 2((p_ 00 "

(5.1.17)

Die Geschwindigkeit und Beschleunigung ergeben sich angen~ihert aus den Differenzenquotienten kx v =~ (5.1.18) At und mv

a = ~. At

Abb.5-3

98

Schubstange und Bolzen

(5.1.19)

5

Differentialgleichungen

Entsprechend den Bewegungen der Triebwerksteile unterscheidet man oszillierende und rotierende Massen. Die oszillierende Masse bestimmt sich aus rsr m 0 = rnsT.

(5.1.20)

+ m K + m B . l

Darin ist msT der Massenanteil der Schubstange, der durch den Faktor rsT/1 seinen oszillierenden Anteil hat, m K die Kolbenmasse und m B die Masse des Kolbenbolzens.

Abb.5-4 Kurbelwangenund Kurbelzapfen

Die rotierenden Massenanteile setzen sich aus 1- rST mR = m S T . ~ + m l

rw W.

r

(5.1.21)

+m Z +m N

zusammen. Darin ist msT(1-rsT)/l der rotierende Massenanteil der Schubstange, m w die Kurbelwangenmasse, die durch den Faktor rw/r auf den Drehmittelpunkt reduziert werden muss, m z die Kurbelzapfenmasse und m N die Nadellagermasse. Die oszillierende Massenkraft ergibt sich damit aus F 0 = m 0 9a K (5.1.22) und die rotierende Massenkraft (5.1.23)

F R =m R .r.(.o 2 .

Die durch die Zfindung eines Gasgemisches auf den Kolben einwirkende Kraft, sorgt ffir eine Entspannungsbewegung des Systems, d. h. eine Vergr61gerung des Zylinderraumes durch die Kol-

99 "

"

9 ........

,

2

5.1

Numerische Behandlung gewOhnlicher Differentialgleichungen

benbewegung. Die Kraft liegt in der Regel indirekt als Indikatordiagramm vor. Indikatordiagramm

Abb.5-5 Indikatordiagramm

Diese praktische Messwertaufnahme zeigt den Zylinderdruck tiber dem Weg. Die obere Kurve stellt die Entspannungsphase und die untere die Kompressionsphase dar. Die eingeschlossene Flfiche ist ein Malg ffir die geleistete Arbeit. Die Kolbenkraft ergibt sich tiber die Kolbenfl~.che und den indizierten Druck zu z.d 2 (5.1.24) FK = ~ . p . 4

In der Kompressionsphase wird die in einem Schwungrad bei der Entspannungsphase gespeicherte Energie tibernommen.

Abb.5-6 Drehmomentverlauf

100

5 Differentialgleicbungen Das Schwungrad ist ftir die Laufruhe eines Motors von entscheidender Bedeutung. Durch die Triebwerksbewegung und durch die Ver/inderung des indizierten Drucks ergeben sich wechselnde Drehmomentverl~iufe. Daraus resultiert ein mittleres Drehmoment Md M. Die Abweichungen von diesem kennzeichnen das Arbeitsverm6gen W. Dieses wiederum bestimmt das Tr~igheitsmoment der Schwungscheibe. Aus der vorhandenen Winkelgeschwindigkeit und einem angenommenen UngleichfOrmigkeitsgrad ergibt sich das TrSgheitsmoment aus der Gleichung W Id = ~ . (5.1.25) 6.(_0 2

Der UngleichfOrmigkeitsgrad ist das Verh~iltnis der Differenzen der gr61gten und kleinsten Winkelgeschwindigkeit der Schwungmassen m..... d mminZU ihrem Mittelwert. Er wird aus Erfahrung bestimmt.

Abb.5-7 Schwungscheibe

Der Durchmesser der Schwungscheibe ergibt sich aus der Ableitung

ld = ~--~.mS -(D 4 - d 4 ) . b 32

(5.1.26)

g

zu

101

5.1

N u m e r i s c h e B e h a n d l u n g g e w 6 h n l i c h e r Differentialgleichungen

D

=I

32.Id

4

--+d

ms g

.

(5.1.27)

~.b

Tab. 5-1 Algorithmus zur Bestimmung der Schubkurbelbewegung

Eingabe der Schubkurbeldaten d, 1, r, rsT , mST , m,, mz, m~, rw, m w, m N, m o, m R Eingabe Indikatordiagramm: for alle Winkel q) die zugeh6rigen p-Werte mit einer Schrittweite yon 10 Grad Bestimmung der Massenaufteilung m 0 = mST 9

rST

l

+mK +mB

1 - rST m R =mST.~+m l

W.

rW r

+m Z+m N

r

l xa=0, t=0, v = 0 FOr alle Winkel ~p = -90, 10, 270 p = f(~o) x = r . (1-sin co)+ 1. ( 1 - 4 1 - 22 cos 2 (co) Z~f = X - - X a ;

Xa = X

rg.d 2 FK ='~ . p

4

a csin(r cosl

102

5

Differentialgleicbungen

FST = ~

COS/~

F R = EST"

cos(90- q~- fl)

IFR

(2)=

~mR. r At = Arp (2)

t-t+At Ax 12 ~ - m

At Av=v-v

a

~

a ; Va = v

Av

m

At g 0 = m 0 .a Fr = Fsr.

sin(90- 9,- fl)

M d =FT'r W = W + M d .Ar

Durch Einffigen eines Tabellenblattes tblSchubkurbeltrieb, kann der Algorithmus darin programmiert werden. Option Explicit Sub Schubkurbel_Leer() Dim Shp As Shape For Each Shp In W o r k s h e e t s ( " S c h u b k u r b e l t r i e b " ) . S h a p e s Shp. Delete Next ThisWorkbook.Worksheets("Schubkurbeltrieb").Cells.Clear Range("Ai-Bl").Select Selection.MergeCells = True Selection. Font.Bold = True 103 .....

i

. . . .

5.1

Numerische Behandlung gewOhnlicher Differentialgleichungen

. . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Selection.Value

=

"Schubkurbeltrieb"

Range("C'C").ColumnWidth

=

"2"

Range("Dl:El").Select Selection.MergeCells = True Selection. Font.Bold = True Selection. Font. Italic = True Selection.Value = "Indikatordiagramm" Range("D2") = ChrW(966) & " [Grad]" Range("E2") = "p [N/m" & C h r W ( 1 7 8 ) & R a n g e ("D2 :E2" ) . S e l e c t Selection. Font.Bold = True Selection. Font. Italic = True

i i i z

Range("F'F") .ColumnWidth = "2" R a n g e ( "GI :HI" ) .S e l e c t Selection.MergeCells = True Selection. Font.Bold = True Selection. Font. Italic = True Selection.Value = "Auswertung" Range("G2") = "x [mm] " Range("H2") = " F K [N]" Range("I2") = ChrW(946) & " [Grad]" Range("J2") = " F S T [N]" Range("K2") = " F R [N]" Range("L2") = ChrW(969) & " [i/s]" Range("M2") = ChrW(916) & "t [s]" Range("N2") = "t [s]" Range("02") = "v [ m m / s ] " Range("P2") = "a [ m m / s " & C h r W ( 1 7 8 ) Range("Q2") = " F O [N]" Range("R2") = " F T [N]" Range("S2") = "Md [Nmm]" Range("T2") = "W [ N m / s ] " R a n g e ( "G2 :T 2 " ) . S e l e c t Selection. Font. Bold = True Selection. Font. Italic = True R a n g e ( "G :T" ) . S e l e c t Selection.NumberFormat = "0.00"

"]"

&

"]"

t

i i ! i

Range("A2"Al6").Select Selection Font Bold = True Selection. Font. Italic = True Range("A2") = "d [mm] "

! i

i

Range("A3")

i

i

104

"

"

=

"i

[mm] "

5 Differentialgleichungen +,. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Ranc Fe("A4") Ranc_[e("A5") Ranc[e("A6") Rang[e("A7") Ranc_[e("A8") Rang[e("A9") RangFe("Al0")

= : : : : :

Ranc[e("All") Rangre("Al2") Rang[e("Al5") Ranc re("Al6")

"r [mm] " " r S T [mm] " " m S T [kg]" " m B [kg]" "mZ [kg]" " m K [kg]" : " r W [mm] " : : : :

"mW "mN "mO "mR

[kg]" [kg] " [kg]" [kg]"

R a n c re ( "B2 : B 2 0 " ) . S e l e c t Selection.NumberFormat R a n g e ( "B2" ) . S e l e c t End Sub Sub

Schubkurbel_Testdaten Cells(2, 2) : i 0 0 C e l l s (3, 2) = 3 0 0

=

"0.00"

()

Cells(4, Cells(5, Cells(6, Cells(7, Cells(8, Cells(9, Cells(10, Cells(ll, Cells(12,

2) 2) 2) 2) 2) 2) 2) 2) 2)

= = = = = =

Cells(3, Cells(4, Cells(5, Cells(6, Cells(7, Cells(8, Cells(9, Cells(10, Cells(ll, Cells(12, Cells(13, Cells(14, Cells(15, Cells(16, Cells(17,

4) 4) 4) 4) 4) 4) 4) 4) 4) 4) 4) 4) 4) 4) 4)

=-90: Cells(3, = -80: Cells(4, =-70: Cells(5, = -60: Cells(6, =-50: Cells(7, = -40: Cells(8, = -30: Cells(9, = -20: Cells(10, = -i0: Cells(ll, = 0: C e l l s ( 1 2 , = i0: C e l l s ( 1 3 , = 20: C e l l s ( 1 4 , = 30: C e l l s ( 1 5 , = 40: C e l l s ( 1 6 , = 50: C e l l s ( 1 7 ,

i Cells(18, ! Cells(19 j t C e l l s (20 t ....................................................................

4) 4) 4)

' "

50 124 60 23.2 6 32 = 12 = 61.66 = 4

= = =

607080-

Cells(18, Cells(19 C e l l s (20

,

5) 5) 5) 5) 5) 5) 5)

= i00000 = 70000 = 45000 = 25000 = 20000 = 20000 = 20000 5) = 2 0 0 0 0 5) = 2 0 0 0 0 5) = 2 0 0 0 0 5) = 2 0 0 0 0 5) = 2 0 0 0 0 5) = 2 0 0 0 0 5) = 2 0 0 0 0 5) = 2 0 0 0 0 5) 5) 5)

= = =

55000 i00000 190000

!

........................................................................................................... ' ................................................................................................................................................................

105

Numerische Behandlung gewfJhnlicher Differentialgleichungen

5.1 ..................

i T i - i - E ........4 ) .....- - - 6 - O - 7 - - g e K s - i K

Cells(22, Cells(23, Cells(24, Cells(25, Cells(26, Cells(27, Cells(28, Cells(29, Cells(30, Cells(31, Cells(32, Cells(33, Cells(34, Cells(35, Cells(36, Cells(37, Cells(38, Cells(39, End Sub

4) = 4) = 4) = 4) = 4) = 4) = 4) = 4) = 4) = 4) = 4) = 4) = 4) = 4) = 4) = 4) = 4) = 4)=

i00: ii0: 120: 130: 140: 150: 160: 170: 180: 190: 200: 210: 220: 230: 240: 250: 260: 270:

i-. . . . .

Cells(22, Cells(23, Cells(24, Cells(25, Cells(26, Cells(27, Cells(28, Cells(29, Cells(30, Cells(31, Cells(32, Cells(33, Cells(34, Cells(35, Cells(36, Cells(37, Cells(38, Cells(39,

630000 700000 735000 750000 720000 650000 560000 480000 400000 350000 305000 280000 250000 230000 200000 180000 135000 I00000

Sub Schubkurbel_Auswertung () D i m d, i, r, rST, m S T , mB, D i m mO, mR, ph, x, la, FK, D i m w, dx, xa, dph, dt, t,

mZ, mK, rW, mW, m N A s D o u b l e p, be, FST, FR, z A s D o u b l e v, va, dv, aK, F O A s D o u b l e

D i m FT, Md, W A A s D o u b l e Dim i As Integer d = C e l l s (2, 2) ! 1 = C e l l s (3, 2) r = Cells(4, 2) rST = Cells(5, 2) mST = Cells(6, 2) mB = Cells(7, 2) mZ = Cells(8, 2) mK = Cells(9, 2) r W = C e l l s (I0, 2) m W = C e l l s (ii, 2) m N = C e l l s (12, 2) 'M a s s e n a u f t e i l u n g mO = mST * rST / 1 + mK + mB m R = m S T * (i - r ST) / 1 + m W Cells(15, 2) = m O Cells(16, 2) = m R 'B e w e g u n g 'KonstanteAtn(1)=pi/4 la = r / 1 106

................................................................................... 5) = 5) = 5) = 5) = 5) = 5) = 5) = 5) = 5) = 5) = 5) = 5) = 5) = 5) = 5) = 5) = 5) = 5)=

* rW

/ r + mZ

+ mN

5 Differentialgleichungen xa

=

0

dph

=

t

0

=

va

=

WA

=

For

i0 0 0

i

=

3

ph

=

Cells(i,

p

=

ph x

To

39 4)

Cells(i, =

:

If

i

dx xa

ph

/

45

r

*

(i-

1

*

(i

-

3

Then

:

x

-

xa

=

x ^

2

=

d

7)

Cells(i,

Sqr(l xa

=

=

=

r

If

1

- be

be

=

A tn(be

=

0

_

(la

*

Cos(ph))

^

2))

x

x

=

be

+

-

* Atn(1)

8) *

* Atn(1) Sin(ph))

=

Cells(i, FK

5)

* p

/

i000000

FK

Cos(ph) * be

/ >= /

1 0

Then

Sqr(l

-

be

* be))

Else be End

If

Cells(i,

9)

FST

/ Cos(be)

=

FK

=

Cells(i,

i0)

FR

*

=

FST

Cells(i, w

=

=

dt

w

=

0

=

Abs

=

0

* Atn(1)

=

FR

=

w

/

12)

*

45

-

ph

FST

Sqr(Abs(FR Not

/ Atn(1)

Cos(2

ii)

Cells(i, If

be

(mR

*

r))

*

-

be)

9810)

Then

(dph

/ w)

Else dt End

If

Cells(i, t

=

t

13)

+

Cells(i, If

dt v

=

dt

=

t

dt 14)

>

0

=

dx

=

0

Then / dt

Else v End I

If

i

Cells(i

15)

If

i

=

3

Then

ii

dv

=

v

-

va

=

!

v va

=

v Ii

[...........................................................................................................................................................................................................................]

107 9

9

.

.

Numerische Behandlung gew6hnlicher Differentialgleichungen

5.1

va

= v

If

dt

>

0 Then

aK

=

dv

=

0

/ dt

Else aK End

If i

Cells(i, FO

=

aK

= mO

* aK

/

9810

Cells(i,

17)

=

FO

FT

=

FST

Cells(i, Md

=

FT

Cells(i, WA

*

Sin(2

18)

=

* Atn(1)

- ph

- be)

FT

* r 19)

= WA

+ Md

Cells(i,

20)

Next !End

16)

= Md * dph

/

I000

= WA

i

Sub

Die Programmliste enth~ilt diesmal keine Diagrammdarstellung. Somit enth~ilt die Symbolleiste nur drei Mentipunkte.

Abb.5-8 Menu Schubkurbeltrieb

Mit Hilfe der eingebauten Testdaten ergibt sich eine umfassende Darstellung.

108

5 Differentialgleichungen

Abb.5-9 Auswertung der Testdaten 1. Teil

109

Numerische Behandlung gewOhnlicher Differentialgleichungen

5.1

Abb.5-10 Auswertung der Testdaten 2. Teil

Obungen Die Erstellung der Diagramme, und hier gibt es einige, tiberlasse ich dem Leser. Sie kOnnen dies tiber die Funktion Einftigen/Diagramm tun und die entsprechenden Spalten ftir die xund y-Achse ausw~ihlen. Schalten Sie vorher den Makrorecorder ein, so erhalten Sie den Quellcode in einem Modul und kOnnen diesen dem Programm hinzuftigen. Die nachfolgende Darstellung (Abbildung 5-11) zeigt einige Beispiele. Wie kOnnen Sie mehrere Kurven in ein Diagramm zusammenfassen?

110 9

...-

.

-

..

5 Differentialgleichungen

Abb. 5-11 Diagramme zur Auswertung

Ergfinzen Sie aulgerdem das Programm um die Berechnung der Schwungscheibe. Die Formeln dazu habe ich Ihnen bereits geliefert.

Beispiel" Drehschwingungen Drehschwingungen

Ein Torsionspendel nach Abbildung 5-12 erffihrt bei Auslenkung um den Winkel 9 das rtickstellende Moment

G.Ip Mt = ~~0. l

(5.1.28)

Abb. 5-12 Torsionspendel

111 ~ . ~ . ~

i

.

~

.

5.1

Numerische

Behandlung

gew6hnlicher

Differentialgleichungen

Gist der Gleitmodul des Fadens und Ip sein polares Fl~ichentr~igheitsmoment. Daraus folgt als Bewegungsgleichung ffir freie Drehschwingungen die Differentialgleichung 9. G.Ip I d .q~=-~q~

l

.

(5.1.29)

Umgestellt 9.

G.Ip

tp

(5.1.30)

l.l a

und mittels Differentialquotienten 9- dr (/9=~ dt

(5.1.31)

folgt G.Ip do)= - ~ qg . d t . l.l a

(5.1.32)

Angen~ihert durch den Differenzenquotienten folgt G.Ip Ago= - ~ qg . A t . I.I d

(5.1.33)

Den Algorithmus ffir eine Drehschwingungsberechnung gibt das nachfolgende Struktogramm wieder. Tab. 5-2 Algorithmuszur Bestimmung einer Drehschwingung Eingabe G, IF, 1, Id, %, r So lange

to, At, tin.,,

t

J

=J

If ii If

jl > i T h e n = 1 ii > k T h e n

B(jl, E n d If Next 1

_

(Name)

j! i

k Then

i

ii)=

jl ii

A(j,

: jl

- 1

= Ii

- 1

I)

}

j

i i

[9...........................................................................................................................................................................................................................]

148

6 Next

3

Call

Matrix_Kofaktoren(B,

Blatt.Cells(i, Next i

Exit

Sub B

Set

=

n (-i)

^

(i

I, +

Det) k)

*

Det

k

Next Matrix

k)

VektorenundMatrizen

Neu-

Blatt

=

Blatt.Name

Worksheets.Add =

Name

Resume z

i End i

Sub

i Sub

Matrix_Kofaktoren(A, Dim

i,

Dim

Pro,

Det

=

q

n

=

If

j,

k, q

r

As

As

n,

Det)

Integer

Double

0 /

2

q

=

Int(q)

r

=

n

=

n

-

Then

1

Else r End

If

For

i j

= =

1

Pro

=

1

For

k

=

1

To

:

Pro

j

j

+

=

If

j

n * A(k,

j)

1

>

n

Then

De t

+

Pro

To

r

i

+

j

:

j

-

n

+

n

k

De t Next

r

Pro

Next =

i

For

i j

= =

Pro For

1 n

-

=

1

k

=

Det

To

=

Pro

j

j

-

=

If

Next

1

1

Pro

Next

End

To

i

j


x)

("Quicksort")

8 Algorithmen aufDatenstrukturen ...........................................................................................................................................................................................................................i

If

i 0 'S t r u k t u r erg~nzen Max = MyDocNew. UsedRange. Rows. Count For i = 3 To Max j = V a l ( M y D o c N e w . C e l l s (i, i) ) If j > 1 T h e n t

~_

For

i

i

i End

I! i!

k

= 2 To

j

t - t & "." Next k t - t & LTrim(Str(j)) MyDocNew. Cells(i, i) E n d If Next i

= t !

i

Sub

i

Mit Hilfe dieser Prozeduren, die durch das nachfolgende Menti aufrufbar sind, erstellen wir die Stticklisten for das Beispiel in Abbildung 8-17.

Abb. 8-18

Menti zur Produktsttickliste

Dazu werden die Stticklisten P001 bis P004 neu angelegt und mit den entsprechenden Daten geftillt.

237

8.4

Arbeiten auf Listenstrukturen

Abb. 8-19 Baugruppen-Stticklistenzum Beispiel

Struktursffickliste

Die Prozedur StOckliste_Struktur erzeugt aus diesen dann eine StrukturstOckliste.

Abb. 8-20 Struktur-Sttickliste zum Beispiel

Zur Erzeugung aktiviert man die entsprechende BaugruppenSttickliste (hier P001) und ruff dann den MenOpunkt StrukturStOckliste erstellen auf. Die StrukturstOckliste erhS.lt den gleichen Namen wie die BaugruppenstOckliste, lediglich ein S- wird vorangestellt. 238

8 Algorithmen aufDatenstrukturen

Ubungen Schreiben Sie Prozeduren zur Verwaltung von Rezepturen. Anders als Stticklisten dienen sie zur Herstellung von Produkten, die aus Mischungen, Mischungsreihenfolgen und deren Verarbeitung entstehen. Genauso wichtig wie Stticklisten sind Arbeitspl~ine. Verwalten Sie Arbeitspl~ine zu vorhandenen StOcklisten.

8.5

Arbeiten auf Baumstrukturenund Graphen

Baumstrukturen und Graphen

Die Graphentheorie ist eigentlich eine mathematische Disziplin. Allerdings ist sie auch ein wichtiges Werkzeug der Informatik, um bestimmte Zusammenh~tnge zu beschreiben. Ein besonderer Vorteil for den Anwender ist, dass sich die Sachverhalte leicht graphisch darstellen lassen.

Abb. 8-21 Beispiel eines Graphen

Einfacher ungerichteter Graph

Ein einfacher ungerichteter Graph besteht aus Knoten und Kanten. Die Kanten verbinden die Knoten. Sind die Kanten gerichtet (Pfeil), so spricht man von einem gerichteten Graphen. Haben die Kanten noch Wertigkeiten, wie z. B. die Entfernungen von Orten untereinander, so spricht man von einem gewichteten Graphen, ansonsten von ungewichteten Graphen.

239

8.5

Arbeiten a u f Baumstrukturen und Graphen

Abb. 8-22 Beispiel eines gerichteten und gewichteten Graphen

Baume

Eine spezielle Form von Graphen werden auch BS.ume genannt.

Abb. 8-23 Vergleich Graph und Baum

Wurzel und Knoten 240

Aus der Abbildung 8-23 geht hervor, welche Eigenschaft BS.ume haben. Alle Wege gehen von einem Knoten, der Wurzel aus.

8 Algorithmen aufDatenstrukturen Vorg~inger heilgen die Knoten auf dem Weg zur Wurzel und Nachfolger die davon weg. Der unmittelbare Vorganger heifgt Vater und alle Knoten mit demselben Vater heiigen Brtider. Ein Knoten ohne Sohn heilgt Blatt und mit mindestens einem Sohn innerer Knoten. Einen typischen Baum haben wir im vorangegangenen Kapitel kennen gelernt. In Abbildung 8-17 wird die Produktstruktur als Baum dargestellt. Die Betrachtung dieses Sachverhalts tiberlasse ich gerne dem Leser. Ein Beispiel for das Suchen in B~iumen finden Sie im Kapitel 9.3. Einen weiteren gerichteten Graphen in dem Zusammenhang erhalt man, wenn man for ein Produkt den Gozintographen erstellt. Dieser Graph beschreibt, aus welchen verschiedenen Teilen ein Produkt besteht. Die Teile bilden die Knoten und die Kanten geben als Gewichtung die Sttickzahl des Einzelteils ftir ein Produkt an. Der Name des Graphen ist auf den Mathematiker Andrew Vazsonyi zurOckzufOhren, der als Vater des Graphen den Mathematiker Zepartzat Gozinto nannte. Dieser Name ist jedoch eine Verballhornung des Begriffs ,,The Part that goes into".

1

1

2

1

Abb. 8-24 Gozintograph zum Stticklistenbeispiel

241

8.5

Arbeiten auf Baumstrukturen und Graphen Weitere Betrachtungen Oberlasse ich dem Leser und wir wollen uns einem klassischen Beispiel for die Anwendung von Graphen zuwenden, der Netzplantechnik.

Beispiel: Netzplantechnik Netzplantechnik

Die Netzplantechnik unterstiJtzt und kontrolliert die DurchfOhrung von Projekten. Weiterentwickelte Systeme erlauben sogar die Kapazit~its- und Kostenplanung. Diese einfache Graphenmethode ist im Projektmanagement die Erfolgsmethode schlechthin.

PER T u n d CPM

Netzpl~ine sind gerichtete und gewichtete Graphen, die nach bestimmten Regeln erstellt werden. Die zwei bekanntesten Techniken heilgen PERT (Program Evaluation an Review Technic) und CPM (Critical Path Method). Nicht nur, dass Netzpl~ine den Ablauf von Projekten anschaulich darstellen, sie zwingen auch zum Durchdenken des Projekts. Aul~erdem f6rdern sie die Kommunikation und das Verst~indnis ftir alle Beteiligten. Wir betrachten nachfolgend die Methode PERT. Knoten sind darin Ereignisse und Kanten Aktivit~iten.

~ Aktisit/it 1-2

"1 El~ignis 1

optimistische Zeit wahrscheinliche Zeit i pessimisttsche Zeit

4/7/12

7,3 el~'artete Zeit

Ereignis 2

Abb. 8-25 Elemente in PERT

Ereignisse und Aktivit~ten

Ereignisse (Events) sind genau definierte Zeitpunkte. Dabei kommt dem Anfangs- und Endereignis eine besondere Bedeutung zu. Aktivit~iten (Activitys) liegen immer zwischen zwei Ereignissen und verbrauchen Zeit. Sie werden als Pfeil dargestellt. Scheinaktivit~iten sind Hilfsgr6gen zur besseren Darstellung des Sachverhalts. Sie verbrauchen keine Zeit.

Zeitsch~tzungen

FOr die Dauer einer AktivitS.t werden drei ZeitschS.tzungen erstellt. Eine optimistische, eine wahrscheinliche und eine pessi-

242

8

Algorithmen aufDatenstrukturen

mistische Zeitsch~tzung. Ftir die optimistische Zeit t o gilt, eine Mirzere Zeit ist nicht m6glich und auch nicht denkbar. Die pessimistische Zeit tp darf auf keinen Fall tiberschritten werden. Die wahrscheinliche Zeit tw gibt die Zeit an, die man angeben wtirde, w~.re nur eine Zeitangabe erlaubt. Die erwartete Zeit berechnet sich aus der Formel to +4.t w +tp te =

6

.

(8.5.1)

Die erwartete Zeit T E ffir eine AktivitS.t ist die Summe aller t vom Startereignis an J (8.5.2) rE - Z t ei .

i=1

Die spfitm6glichste Zeit T, zu der eine Aktivitfit abgeschlossen sein muss, ist die Summe aller t vom Endergebnis bis zur betrachteten Aktivit~tt n

TL = Z tei 9 i=j Schlupf

(8.5.3)

Als Schlupf bezeichnet man die Differenz (8.5.4)

S =T L -T e .

Die Varianz, ist ein Malg for die Bewertung der der Unsicherheit bei der Angabe der Vorgangsdauer und bestimmt sich aus Standardabweichung

(

82 = ~j, tp - t o 9 6

,'7

)2

(8.5.5)

Als Standardabweichung 8 wird die Wurzel der Varianz bezeichnet. Sie ist ein Malg f/Jr die Gr61ge der Abweichung. Jede Aktivit~tt beginnt mit einem Ereignis und endet mit einem Ereignis. Die Ausnahme bilden das Start- und Endereignis. Eine Aktivit~it kann erst beginnen, wenn das vorherige Ereignis erzielt wurde.

243

8.5

Arbeiten auf Baumstrukturen und Graphen

Aktivit~t 1

Aktivit~t2

Aktivit~tt 1 I

, Schemaktivit~t Aktivit/at 2

Abb. 8-26 Scheinaktivitlit

Parallele Aktivitiiten, die von einem Ereignis ausgehen und im gleichen Folgeereignis enden, werden mit Hilfe von ScheinaktivitSten aufgel6st. Scheinaktivitiiten ben6tigen keine Zeit. Besonders zu beachten ist, dass in einem PERT Netzplan keine Schleifen entstehen. Als konkretes Beispiel betrachten wir die Daten in der nachfolgenden Tabelle 8-8. Es spielt for die Programmierung keine Rolle, um welche Ereignisse und AktivitS.ten es sich handelt. Lediglich die entsprechenden Daten eines Projektes sind for uns von Wichtigkeit. Die T~ttigkeit Nr. 5 ist eine Scheint~itigkeit und erh~.lt somit keine Zeiten. Mit Hilfe dieser Daten 1S.sst sich der Netzplan bereits zeichnen. Siehe Abbildung 8-27. Ein Ergebnis ist bereits eingetragen. Die stlirker gezeichneten Pfeile kennzeichnen den kritischen Pfad. Der kritische Pfad oder Weg ist nach DIN 69900 der Weg in einem Netzplan vom Anfangs- zum Endknoten, bei dem die Pufferzeiten minimal sind.

244

8 Algorithmen aufDatenstrukturen Tab. 8-8 Beispiel von Netzplandaten

Nr

T~.tigkeit

Zeit

Zeit

opti.

wahr.

pess.

1

1-2

2

3

5

2

1-3

3

4

5

3

1-4

4

6

9

4

2-5

2

4

7

5

3-6

0

0

0

6

4-6

3

5

8,5

7

5-7

1,5

4

7

8

6-7

1

3

7

9

7-8

2

5

9

3/4/5 ./ 4/.. ,/

~

Zeit

,

\ \ 0/0,,"0

/167a~f ~ 42/4/7 ~1,514/7~'~"~ 2/5/9 tJr 167 '~ ] .l qQ3 "1 I 5.167 "

, ~

.... ~ / 4/6/9 " , ~ _ ~ '..... / 1/3i7 6,167 f ........~ 3/5/8,5 j r ",~ 3,333 5,25 ~k,,~*

Abb. 8-27 Netzplan zum Beispiel

Nachdem wir nun alle Begriffe eingefOhrt haben und bereits an einem Beispiel die Begriffe geObt haben, kommen wir nun zum Algorithmus. Tab. 8-9 PERT-Netzplan

i = 1 (1) Max (fiber alle Eintr~ige) Bestimme die Knoten a(i,1) und a(i,2)

245

8.5

246

Arbeiten auf Baumstrukturen und Graphen

8 Algorithmen aufDatenstrukturen

FC~r die Programmausftihrung ben6tigen wir ein Formblatt, das Testbeispiel und die Auswertung. Cg~g...8:s

.........e..E~.~E..e..tZp.!...an ...........................................................................................................................................................................................................................

Option Explicit Sub Netzplan_Neu () ThisWorkbook. Worksheets ( "Netzplan" ) .C e l l s . C l e a r

i

247

8.5

Arbeiten auf Baumstrukturen und Graphen

Rancre("Bl") RancFe("Cl")

: =

"Optimis-" & vbLf & "tische Zeit" "Wahrschein-" & vbLf & "liche Zeit"

Rancre("Dl") RancFe("Fl")

= =

"Pessimis-" "Ereignis"

& vbLf

&

"tische

& vbLf

&

"Dauer"

Zeit"

RancFe("Gl")

=

"Erwartete"

RancFe("Hl")

=

"Abweichung"

RancFe("Ii")

=

"Sp~testens"

Rancre("Jl") RancFe("Kl")

= :

"Sp~testens" "FrOhester"

& vbLf & "enden um" & vbLf & "Start um"

RancFe("Ll")

=

"Sp~tester"

& vbLf

&

"Start

Rancre("Ml") Rancre("Nl") Rancre("Ol") Rancre("Pl")

: = = =

"FrOhestes" "Sp~testes" "Schlupf" "Kritischer"

& vbLf & vbLf

& &

"Ende "Ende

Rancre("Ql")

=

"Abweichung"

& vbLf

& vbLf

&

&

"starten

um"

um" um" um"

"Pfad"

Rancre("Al:Ql").Select Selection.

Font.Bold

Selection.

Font. Italic

= True = True

Columns("A:A").Select Selection.NumberFormat

=

"@"

Columns("B:D").Select Selection.NumberFormat

=

"#0.0"

=

"#0.000"

Columns("G:Q").Select Selection.NumberFormat Range("A2").Select End Sub Sub

i

Netzplan Cells(2, Cells(3, Cells(4, Cells(5, Cells(6,

Test() I) = " 1 - 2 " i) = " 1 - 3 " i) = " 1 - 4 " i) = " 2 - 5 " i) = " 3 - 6 "

Cells(7, Cells(8, Cells(9, Cells(10,

i) = " 4 - 6 " i) = " 5 - 7 " i) = " 6 - 7 " i) = " 7 - 8 "

Cells(2,

2)

: 2

Cells(3,

2)

= 3

Cells(4, Cells(5,

2) 2)

= 4 : 2

t

9 ~ Cells(6, 2) : 0 i i C e l l s (7 2) : 3 i ....................................................,.........................................................................................................................................................................................J.................................

248

8 Algorithmen aufDatenstrukturen (

)

Cells (9, Cells(lO,

2) = 1 2) - 2

C e l l s (2, C e l l s (3, C e l l s (4, C e l l s (5, Cells(6, C e l l s (7, C e l l s (8, C e l l s (9, Cells(10,

3) 3) 3) 3) 3) 3) 3) 3) 3)

= = : = = = = =

Cells(2, Cells(3, Celis(4, Cells(5, Cells(6, Cells(7, Cells(8, Cells(9, Cells(10, End Sub

4) 4) 4) 4) 4) 4) 4) 4) 4)

= = = = = = = =

Sub

3 4 6 4 0 5 4 3 =

5

5 5 9 7 0 8.5 7 7 = 9

Netzplan_Start() Dim MyDoc As Object D i m i, M a x A s I n t e g e r D i m tx, el, e2 A s S t r i n g D i m S(), F ( ) , a ( ) , e() A s D i m tl, t2, t3 A s D o u b l e D i m V, L, S L A s D o u b l e

Double

Set MyDoc = ThisWorkbook.ActiveSheet MyDoc .Activate Max : MyDoc.UsedRange.Rows.Count - 1 If M a x > 0 T h e n ReDim S(Max), F(Max), a(Max, 2), e ( M a x , For i = 1 To Max tx = Cells(i + i, i) el = L e f t ( t x , InStr(tx, '.... ) - i) e2 : R i g h t ( t x , InStr(tx, '.... ) - i) a ( i , i) = V a l ( e l ) a ( i , 2) : V a l ( e 2 ) tl = C D b l ( C e l l s (1 + i, 2 ) )

2)

,

i...........................................................................................................................................................................................................................

I ! i i i i

J

249

8.5

Arbeiten auf Baumstrukturen und Graphen

!.......................................................... i

.......

....... .......T-; .........77-7

............................................................................................................................................................

t3 = C D b l ( C e l l s ( i + 1 4)) e(i, i) = (tl + 4 * t2 + t3) / 6 e(i, 2) = ((t3 - tl) / 6) ^ 2 s(i)

F(i) Next i

=

'erwartete 'Varianz

Dauer

0

= 0

'Auffinden der frfihesten Startzeiten For i = 1 To Max If S ( a ( i , 2)) < S ( a ( i , i)) + e(i, S ( a ( i , 2)) = S ( a ( i , I)) + e(i, E n d If Next i F(a(Max, 2)) : S ( a ( M a x , 2)) 'Auffinden der spatesten Endzeiten For i = Max To 1 Step-i If F ( a ( i , i)) : 0 O r F ( a ( i , i)) > F ( a ( i , 2)) - e ( i , F ( a ( i , I)) = F ( a ( i , 2)) - e ( i , E n d If Next i

i) i)

Then

i) i)

Then

m

i i i

L = 0 V = 0 For i = 1 To Max S L = F ( a ( i , 2)) - S ( a ( i , i)) - e(i, i) If SL = v m : I n t ( ( v + b) If t > C e l l s ( m , v = m + 1 Else b = m - 1 E n d If i = v Loop

i

i

/ 2) i) T h e n

'A u s g a b e Cells(i, i) . A c t i v a t e MsgBox "Zeile:" & Str(i) & vbLf vbOKOnly, "Suchergebnis von-

& Cells(i, " & t

i),

Zum Aufruf der Suchfunktion genOgt ein einziger MenOaufruf.

Abb. 9-2 Menti zur Suchprozedur 255

9.2

Die Greedy-Methode Die Prozedur liefert immer eine Ausgabe, egal ob der Suchbegriff gefunden wurde oder nicht.

Ubungen Will man eine solche Liste noch pflegen, dann kommen zwei weitere Prozeduren hinzu, n~tmlich das Einf/~gen und Entfernen von Eintr~tgen. Schreiben Sie diese Prozeduren und benutzen Sie ein Formular zur Verwaltung. Hash-Methode

Nicht immer liegen Listen in geordneter Form vor. Eine sehr effiziente Methode, in diesen Listen Informationen zu finden, ist die Hash-Methode. Die Methode wurde in den fCmfziger Jahren bei IBM unter dem Begriff gestreute Speicherung entwickelt. Befassen Sie sich mit dem Thema und schreiben Sie eine entsprechende Prozedur.

9.2

Die Greedy-Methode

Greedy Methode

Die Greedy-Methode (engl.: greedy = gierig, geizig) beruht auf einer einfachen Entwurfstechnik. Aulgerdem kann sie auf eine Vielzahl von Problemen angewandt werden. Fast alle diese Probleme erfordern die Bestimmung einer Teilmenge, die bestimmten Bedingungen gentigt. Diese Teilmengen nennt man dann eine m6gliche L6sung. Ziel ist es dann eine Teill6sung zu finden, die eine gegebene Zielfunktion maximiert oder minimiert. Dies ist dann eine optimale L6sung. Gew6hnlich gibt es klare Anweisungen zur Bestimmung einer L6sung, aber nicht notwendiger weise einer optimalen L6sung.

Beispiel:Auftragsfolgenproblem Aufiragsfolgenproblem

Gegeben sei eine Menge von n Auftr~igen a i. Jeder Auftrag hat einen Endtermin ei>=0 und einen Gewinn g~>=0. Dabei wird der Gewinn nur erzielt, wenn der Auftrag bis zum Endtermin ausgeffihrt ist. Gehen wir weiter davon aus, dass ffir alle Auftr~.ge nur eine Maschine zur Verffigung steht, und jeder Auftrag diese Maschinen ftir eine bestimmte Zeiteinheit z i belegt. Eine L6sung dieses Problems ist eine Teilmenge der Auftr~.ge, die alle bis zum Ende erledigt werden k6nnen. Der Wert dieser L6sung wj ist die Summe der Gewinne wj - s

256

gi 9

(9.2.1)

9 Verhaltens-Algorithmen Folglich ist eine L6sung mit maximalem Wert eine optimale L6sung. Eine Greedy-Methode ist es nun, ein Optimierungsmalg ftir die Zusammenstellung der Gewinne zu finden. Ausgehend von einem beliebigen Auftrag ai, werden immer nur die Gewinne hinzuaddiert, die den gr61gtm6glichen Gewinn versprechen und dabei den Endtermin einhalten. Aus den so gewonnenen m6glichen L6sungen, wird die beste ausgew~ihlt. Sie ist allerdings kein Garant ftir die optimale L6sung.

Betrachten wir dies an den konkreten Zahlen eines Beispiels in Tabelle 9-2. Neben dem Wert und der belegten Zeit for die Maschinen ist aulgerdem die Zeit angegeben, die bis zur Erledigung des Auftrags verbleibt. Zur Vereinfachung betrachten wir die Zeiten in Stunden. Zur Ermittlung gehen wir von allen Auftr/igen aus und suchen die dazu passenden Folgeauftr/ige nach der zuvor erl~iuterten Greedy-Strategie. Diese ist in Tabelle 9-3 wiedergegeben.

Tab. 9-2 Beispieldaten ftir Auftr~ige

Auf.

Wert

Beleg.

Zeitraum

73

12

30

61

10

4O

55

5O

12

11

30

48

14

35

33

10

45

Tab. 9-3 Struktogramm zur Greedy-Methode

Eingabe der Auftragswerte, Belegzeiten und des Zeitraums for die Ausftihrung FOr alle vorhandenen Auftr/ige i= 1 (1)n

257 ~

~

~

:

.

Die Greedy-Methode

9.2

Das Programm bauen wir wieder wie gewohnt auf, so dass erst ein Formblatt erstellt wird. Dann h3nnen wahlweise eigene Daten eingegeben oder die Testdaten aufgerufen werden. C....o.~g...9.:2 .......~suc~..e..n...ejne..~...~.~ung.....e...u...rein..~.u...eg.a~en~.gep-r~!.~m..n.ach..~r9re.~d~:.~e.t~@ Option Sub

Greedy_Neu () ThisWorkbook.Worksheets

("Greedy")

Range("Al")

=

"Auf.Nr."

Range ("BI") Range("Cl")

= =

"Wert" "Beleg."

Range

=

"Zeitraum"

("DI")

vbLf Range("Fl")

=

&

& vbLf

Selection.

" [h]"

"Auf.Nrn."

Font. Bold

= True

s I i

Selection. Font. Italic = True R a n g e ( "E- E" ) .C o l u m n W i d t h = 2

! !

Range("A2")

258 ,.

.,.

,.

Select

Sub Greedy

Test()

&

& vbLf

Range("Gl") = "Ges.Wert" R a n g e ( " A 1 9G 1 " ) . S e l e c t

' End i ! i Sub

.............................................

Explicit

.C e l l s . C l e a r

"Zeit"

& vbLf

&

Erl. " & _

"zur

&

" [h]"

9 Verhaltens-Algorithmen Dim i As I n t e g e r For

i = 1 To 6 Cells(i + i, I) Next i C e l l s (2, 2) = 73 C e l l s (3, 2) = 61 Cells(4, 2) = 55 C e l l s (5, 2) = 12 Cells(6, 2) = 48 C e l l s (7, 2) = 33 C e l l s (2, 3) = 12 C e l l s (3, 3) = i0 Cells(4, 3) = 8 C e l l s (5, 3) = ii Cells(6, 3) = 14 C e l l s (7, 3) = i0 Cells(2, 4) = 30 Cells(3, 4) = 40 Cells(4, 4) = 50 Cells(5, 4) = 30 Cells(6, 4) = 35 Cells(7., 4) = 45 End Sub Sub

= i

GreedyStart() Dim MyDoc As Object D i m W, Z, wi, zi, ei A s D o u b l e D i m i, j, k, i, w M a x , k M a x , n A s D i m a() A s I n t e g e r Dim t As String

Integer

Set MyDoc = ThisWorkbook.Worksheets("Greedy") n : MyDoc.UsedRange.Rows.Count - 1 R e D i m a(n, 4) 'D a t e n i i b e r n e h m e n For i = 1 To n a(i, 2) = C e l l s ( i a(i, 3) = C e l l s ( i a(i, 4) = C e l l s ( i Next i

+ i, + i, + I,

2) 3) 4)

t

!' i'

i

For

i = 1 To n 'Merker 16schen For j = 1 To n

i! .= i 'i

259

Die Greedy-Methode

9.2

........................................................; 7 s

........i 7 - -

Next j 'Ersten a ( i , i)

.....-6-...........................................................................................................................................................................................................................

Wert = 1

setzen

'Sortierung For

j

der

= 2 To

'gr6sster W = 0 1 = 0 For k = If

freier

1 To

End

=

t

__

For

If

k

a(l,

i)

=

j

j der

Zulassigkeit

i! !1

Next

k + +

26O ,

~' .

" .

,,'~.~_

~

Ausgabe

j = 1 To n For k = 1 To n If a ( k , i) = j T h e n If Z + a ( k , 3) < = a ( k , 4) T h e n Z = Z + a ( k , 3) W = W + a ( k , 2) If j = 1 T h e n t = LTrim(Str(k)) Else t = t & ..... & L T r i m ( S t r ( k ) )

Next j Cells(i Cells(i Next i Sub

und

0

End E n d If k = n E n d If

End

n

If

Next

'PrOfung Z = 0 W

Wert

a ( k , I) = 0 T h e n If a ( k , 2) > W T h e n W = a ( k , 2) 1 = k

End

Next

Werte

n

i, i,

6) 7)

If

= t = W

9 Verhaltens-Algorithmen Der Aufruf der Prozeduren fiber das Menti in Abbildung 9-3 liefert die in Abbildung 9-4 dargestellten Daten.

Abb. 9-3 Menti zur Greedy-Methode

Danach ist die L6sung die Aufgabenfolge 5-1-2-3 mit einem Gesamtwert von 237. Auch for dieses Beispiel gilt, dass es nicht die optimale L6sung sein muss. Die Greedy-Methode liefert jedoch oft ein schnelles und hinreichend gutes Ergebnis.

Abb. 9-4 Ergebnis der Testdaten

Obungen W~ihlen Sie statt des Kriteriums Wert das Kriterium

Wert Belegzeit und vergleichen Sie beide Ergebnisse. Insbesondere, wenn noch die Kosten for die Maschinennutzung dem Gewinn entgegen gesetzt werden.

261

Ri2ckverfolgung oder Backtracking

9.3

Andern Sie den Algorithmus so ab, dass auch Vertauschungen der Reihenfolgen untersucht werden.

9.3

ROckverfolgung oder Backtracking

Ri2ckverfolgung, Backtracking

Die Ri~ckverfolgung stellt ein fundamentales algorithmisches Prinzip dar. Viele Probleme, bei denen man nach einer Menge von L6sungen bzw. nach einer optimalen L6sung sucht, k6nnen mit dieser Methode gel6st werden. Der Name Rtickverfolgung (engl.: backtracking) schildert im Wort bereits anschaulich die Methode. Der Backtracking-Algorithmus ~thnelt dem Suchen in B~tumen.

Abb. 9-5

Baumstruktur

Man durchl~tuft dabei alle Zweige eines Baumes (Abbildung 9-5) bis in die Spitzen und kehrt dann bis zur vorherigen Abzweigung zurtick, die man noch nicht durchlaufen hat. Von diesem Zurfickgehen hat der Algorithmus seinen Namen. Beim Durchsuchen der B~tume verf~thrt man nach einer Strategie. Zum Beispiel orientiert man sich immer nach rechts zu gehen, soweit das m6glich ist. Hat man die Spitze erreicht, geht man bis zur ersten M6glichkeit nach links zu gehen, die man noch nicht durchlaufen hat, wieder zurtick. Danach orientiert man sich wieder rechts. Wir kennen dieses Verfahren auch zum Finden eines Ausgangs aus einem Labyrinth. Ein klassisches Beispiel ist das 8-Damen Problem, das ich bereits im Jahre 1978 in der Wissenschaftszeitschrift Bild der Wissenschaft als Programmierbeispiel auf einem Taschenrechner beschrieben habe. Da wird nach den Positionen gesucht, die 8 262 9 . .

.

9 Verhaltens-Algorithmen Damen auf einem Schachbrett einnehmen k6nnen, ohne sich gegenseitig zu ,,schlagen". Weitere typische Anwendungsbeispiele for den Backtracking-Algorithmus sind die Suche nach einem Ausweg aus einem Labyrinth, angrenzende Fl~ichen mit unterschiedlichen Farben zu versehen und der Weg eines Handelsreisenden. Der Algorithmus spielt ebenfalls in der KI (KOnstlichen Intelligenz) eine bedeutende Rolle. Wir wollen nachfolgend eine industrielle Anwendung betrachten.

Beispiel: Einschrittige Codes for die industrielle Wegmessung Einschrittige Codes, Gray Code

Zur Wegmessung, ob inkremental oder absolut, wird in der Regel der Gray-Code benutzt. Er hat eine Eigenschaft, die der Bin~ircode nicht besitzt. Beim Wechsel von einer Zahl zur nachfolgenden oder zur vorhergehenden ~indert sich nur ein Bit in der Darstellung. l~mnE~naer

Abb. 9-6 Wegmessung

Industrielle Wegmessu ng

Nur dadurch, dass sich immer nur ein Bit ~ndert, sind fehlerfreie Messungen m6glich. Wtirden sich zwei Bits ~indern, Mime es m6glicherweise kurzzeitig zu einem falschen Wert, wenn diese sich nicht wirklich zeitgleich ~indern. Tab. 9-4 Binar- und Gray-Code

i

Bimir-Code

Gray-Code

0

000

000

1

001

001 263 ~ , ~ ; ~ ~ : : ~ .

9.3

Rfickverfolgung oder Backtracking 2

010

011

3

011

010

4

100

110

5

101

111

6

110

101

7

111

100

Wir wollen nachfolgend mittels Backtracking-Algorithmus untersuchen, ob es m6glicherweise noch andere so genannte einschrittige Codes gibt. Als Basis nehmen wir 4 Bit und ffir die Farben Weilg und Schwarz die Ziffern 0 und 1. Eine Ausgangskonstellation sei mit nur Nullen gegeben. Dann ergibt sich die n~ichste Konstellation durch Ver~inderung eines Bits (Abbildung 9-5). Ist eine solche Konstellation gefunden, dann beginnt die Ver~inderung wieder beim ersten Bit. Gibt es die Konstellation bereits, wird das zweite Bit ver~indert, usw.; so lange bis eine weitere Konstellation gefunden ist. Ausgang ist immer die zuletzt gefundene Konstellation. Die jeweilige Position der Bitver~inderung wird registriert, da mit Erreichen der 16. Bitkonstellation oder schon frtiher, wieder ein Rtickw~irtsschritt erforderlich ist.

Abb. 9-7 Erste Schritte des Algorithmus

264

9 Verhaltens-Algorithmen Ein Rtickw~irtsschritt ist immer dann erforderlich, wenn mit Ver~nderung des 4. Bits keine neue Konstellation erreicht wird. Dann wird auf die vorherige gtiltige Konstellation zurtickgegriffen, die noch kein 4. Bit ver~indert hat. Damit ist der Algorithmus umfassend beschrieben und wir wollen ihn im nachfolgenden Schritt als Struktogramm definieren. Tab. 9-5 Bestimmung einschrittiger Codes nach der Backtracking-Methode

265

R~ckverfolgung oder Backtracking

9.3

Da eine lange Laufzeit zu erwarten ist, habe ich noch ein Abbruchkriterium eingebaut, so dass nach Erreichen einer vorgegeb e n e n Anzahl Konstellationen der Prozess terminiert. g o ~ g . . 9 : ~ ......B ~ ! ~ n g . . e ! ~ S h ~ t * ~ . . . C e ~

...........................................................................................................................................................................................................................

Option Explicit S u b E i n C o d e s Start() D i m A(16, 4), U(4), M(16) As I n t e g e r D i m i, j, k, i, n As I n t e g e r D i m pl, p2 As I n t e g e r D i m y, z, s As I n t e g e r D i m t As S t r i n g 'Start i ThisWorkbook.Worksheets("EinCodes").Cells.Clear I Range("H-W").ColumnWidth = 1 i z = I n p u t B o x ( " A n z a h l d e r C o d e s bis z u m Stop a n g e b e n " )

i

y=l 'A u s g a n g s k o n f i g u r a t ion F o r j = 1 To 4 A(I, j) = 0

266

0000

9 Verhaltens-Algorithmen ' ...........................................

.......... j i

Next

.......... =

.......

...........................................................................................................................................................................................................................

j

'Merker Ausgangswerte F o r i = 1 T o 16 M(i) = 0 Next i 'Start i =

i

i

1

Do 'S c h r i t t vor For j = 1 U(j) = Next j If M ( i ) < M(i) = U(M(i))

To 4 A ( i , j) 4 Then M(i) + 1 = 1 - U(M(i))

'P r O f u n g 'Wird die gleiche Konstellation 'noch einmal gefunden, ist pl=l pl = 0 For k = 1 To i p2 = 0 For j = 1 To 4 If N o t U ( j ) = A ( k , j) T h e n Next j If p 2 = 0 T h e n p l = 1 Next k

p2

: 1

!

'Neue Konstellation If p l = 0 T h e n i = i + 1 For j = 1 To 4 A ( i , j) = U ( j ) Cells(i, j) = U ( j ) Next j If

i =

16

Then

'PrOfung,

!

ob

der

ist

Code

in

sich

geschlossen

j

: i

S =

0

i

For

j = 1 To

! 4

i

267

9.3

Rfickverfolgung oder Backtracking

.............................................................................................................. ~ ~ .....~ o ~

s End Next If s

j =

K-ii-< .......~-i- ........~ a - ~

.......; - i i i

= If

s

.........~ i ......."- ......

+

.......................................................................

1

1 Then

'Code

brauchbar

For

=

k t

._

1 To

und

wird

registriert

16

,, ,,

For

j

=

If

1 To

A(k, t

4

j)

:

1 Then

=

t

+ ChrW(9608)

=

t

+ ChrW(8901)

Else t

E n d If If j < Next

Cells(y, Next y

4 Then

t

=

t

+ vbLf

j 7

+ k)

=

t

k

= y

+

1

'Merkerstand For

k

=

1 To

Cells(k, Next

zeigen 16 6)

= M(k)

k

'A b b r u c h If y = z + 1 T h e n Exit Sub End End

If

If

'S c h r i t t M(i)

i End End

=

=

i

zurOck 0

-

1

If

If

Else 'Schritt

zurOck

M(i) = 0 i = i - 1 i

End

If

!

i Loop While i > 0 i i........................................................................................................................................................................................................................... End Sub 5 3

Als Menti wird lediglich ein Start benOtigt. 268

9 Verhaltens-Algorithmen

Abb. 9-8 Menti zum Bestimmungsstart

Die ersten neun gefundenen Codes sehen Sie in Abbildung 9-7. Die Spalten A-D zeigen die vier Bit der 16 Positionen der letzten gefundenen gOltigen Konstellation. In Spalte F sehen Sie den aktuellen Merker der 16 Positionen, und damit den Fortgang des Algorithmus. In den Spalten H-V eine grafische Darstellung aller gefundenen Konstellationen.

Abb. 9-9 Die ersten neun gefundenen einschrittigen Codes

Obungen Andern Sie den Algorithmus so ab, dass mit ihm die Ziffern 0 bis 9 dargestellt werden kOnnen. Es ergeben sich dann zehn Positionen von mOglichen sechzehn. Die restlichen sechs Positionen sind OberflOssig und werden als Redundanz bezeichnet. 269

9.4

Rfickwdrtsrechnen oder Rekursive Prozeduren Schreiben Sie zus~itzliche Prozeduren, die gefundene Codes z. B. auf Gewichtung oder andere Eigenschaften untersucht.

9.4

ROckwiirtsrechnen oder Rekursive Prozeduren

Rf2ckwdrtsrechnen, rekursive Prozeduren

Man spricht von einer rekursiven Methode, wenn in einer Prozedur ein Aufruf von ihr selbst steht. So berechnet sich n! aus seinem Vorg~inger (n-l)! Durch n!= n.(n-1)!. (9.4.1) Damit die Rekursion terminiert, muss ein Rekursionsanfang gegeben sein. FOr Null-Fakult~it gilt 0!= 1 (9.4.2) per Definition. Ein sehr bekanntes Beispiel for das RtickwS.rtsrechnen ist das nachfolgend dargestellte Beispiel, in der Literatur auch als JeepProblem bekannt.

Beispiel:Jeep-Problem Jeep-Problem

Ein Fahrer m6chte mit seinem Jeep eine Wtiste durchqueren. An seinem Ausgangspunkt steht ihm ein unbegrenztes Tanklager zur Verftigung. Der Jeep verbraucht 10 Liter auf 100 km und kann for eine Fahrt immer nur 60 Liter Treibstoff laden. Damit kann der Fahrer 600 km fahren. Der Fahrer ist also gezwungen, in der Wtiste ein Depot anzulegen, auf das er bei seiner Durchquerung zurtickgreifen kann. Die LOsung des Problems ergibt sich durch ROckw~irtsrechnen, das anschaulich in Abbildung 9-10 dargestellt ist.

Abb. 9-10 Die Methode des Riickw~irtsrechnens

Um vom letzten Depot D zum Ziel X zu gelangen, ist eine einzige Tankftillung n6tig.

270 9

9

9 Verhaltens-Algorithmen Um eine Tankftillung vom vorletzten Depot C nach D zu transportieren und dann von D nach C zurtickzukehren, muss der Jeep die Strecke CD dreimal fahren. Kommt er das erste Mal nach D kann er 1/3 der Tankladung zurticklassen. Beim zweiten Mal hat er noch 2/3 der Tankladung. C muss also 1/3 der Tankladung von D entfernt sein = 600/3 = 200 km. Um vom drittletzten Depot B nach C zwei Tankladungen zu bringen, muss der Jeep ftinfmal hin- und heffahren. Zweimal kann er eine 3/5 Tankladung deponieren und beim dritten Mal besitzt er noch 4/5 der Tankftillung. C muss also von B entfernt sein = 600/5 = 120 km.

(111 /

Allgemein betrachtet ergibt sich 600. 1 + - + - + - - + 3 5 7

....

(9.4.3)

Diese Summe divergiert und so llisst sich mit dieser Methode jede beliebige Strecke zurticklegen. Tab. 9-6 Das Jeep-Problem Starteingaben v=Verbrauch in Liter/100 km t=Tankftillung e=Entfernung

E=0 i=0 i=i+l

E=E+ ( i - 1 ) . 2 + 1 So lange wie - t- E

< e

v

Ausgabe der Anzahl Depots

271

9.4

R~ckwdrtsrechnen oder Rekursive Prozeduren Mit Hilfe variabler Eingabedaten sollen die Anzahl Depots bestimmt werden, die zur Oberbrtickung einer bestimmten Entfernung notwendig sind.

[email protected] .......B esti~_ung_eins.cMttj~_~r..Co#.s Option Explicit Sub

Jeep_Neu

.....................................................................................................................................................................................................

()

ThisWorkbook.

Worksheets

("JeepProblem"

) .C e l l s . C l e a r

Ranc re("Al") = " T a n k f ~ l l u n g [L]" R a n c re("A2") = " V e r b r a u c h [L/100km]" R a n c re("A3") = " E n t f e r n u n g [km]" R a n c "e("Dl") = " D e p o t " R a n g 'e("El") = " E n t f e r n u n g " Rang e("Fl") = "Differenz" Ranc e("Al:A3").Select Selection. Font.Bold = True Selection. Font. Italic = True Range("Dl:Fl").Select Selection. Font.Bold = True Selection. Font. Italic = True Range("A-A").ColumnWidth = 20 Range("C'C").ColumnWidth

=

5

Range("Bl").Select End Sub Sub

J e e p _ T e s t () Cells(l, 2) = 80 C e l l s (2, 2) = i0 C e l l s (3, 2) = 1 5 0 0 End Sub

Sub

J e e p _ S t a r t () D i m v, t, e, s, u, Dim i As Integer t v e i

i i

272

= = = =

Cells(l, C e l l s (2, Cells(3, 0

2) 2) 2)

w As

Double

I

i

s = 0

i i

u = 0

i

Do

I I ~ i

9 Verhaltens-Algorithmen 1

=

1

+

s

=

s

+

Cells(i w

ii !

((i4)

i) =

*

2

+

i)

i

*

I00

*

s

+

i,

5)

=

w

Cells(i

+

i,

6)

=

w

-

u

t

/ v

I00

*

s

Loop

/

/ i,

v

=

t

1 +

Cells(i

U

:

1

W

While

*


1 A n d Z e i l e > 1 T h e n F o r 1 = 1 To p If y(l, I) > 0 T h e n y(l, 2) = 1 For

i i i

r : 1 To Z e i l e ts = t & ..... & L T r i m ( S t r ( 1 ) ) If ts = m Left(Cells(r, i), L e n ( t s ) ) T h e n y(l, 2) = y ( l , 2) + _ V a l ( C e l l s (r, 3)) E n d If

I i i i

! i i

i........................................................................................................................................................................................................................... ]

282

10 Algorithmen aus der Natur Next End Next End

r

If

1

If

'W a h r s c h e i n l i c h k e i t s v e r t e i l u n g g = For

0 1 = g

1 To

: g

Next

p

+ y(l,

2)

1

x

: R n d (x)

w

=

Int(x

g

=

0

For

1 = g

* g

1 To

: g

If

+ p

+ y(l,

g

>=

v

=

w

i)

2)

Then

1

1 = p End

If

Next 1 If y ( v ,

i)

>

0 Then

y(v,

i)

=

0

y(v,

2)

=

0

If

k

=

t

= LTrim(Str

1 Then (v))

Else t End

=

t &

f (k) = v q = 1 End If Loop While q = 0 Next k Cells(j + i, 5 + m) z(j)

=

k For

=

der

1 To 1 =

If

k

=

t

Durchlaufzeit

p

1 To =

m

1 Then

u(1) Else If i

LTrim(Str(v))

t

'Bestimmung For

..... &

If

= Cells(f(k)

1 = u(1)

+

i,

1

+

4)

1 Then = u(1)

+ Cells(f(k)+

i,

1 +

4)

!

i i

i

Else

283

10.1

D e r A meisenalgorith m us

[...........................................................................................................................................................................................................................

If

u ( l - i) < u(1) u(1) = u ( 1 ) + _ Cells(f

Then

(k)

+ I,

1 + 4)

+ i,

1 + 4)

Else u(1)

= u(l

- i)

Cells(f E n d If E n d If E n d If Next 1 Next Cells(j + i, 6 + m) s(j) = u ( m ) Next j

+

(k)

= u(m)

'B e u r t e i l u n g 'Nur d i e m i n i m a l s t e n For j = 1 To n If j = 1 T h e n M i n = s(j) Else If

Werte

werden

eingetragen

s(j) < M i n T h e n M i n = s(j) E n d If E n d If Next j For j = 1 To n If s(j) = M i n T h e n q = 0 For k = 1 To Zeile If C e l l s ( k , i) : z(j) T h e n Cells(k, 3) = C e l l s ( k , 3) + 1 q = 1 k = Zeile E n d If Next k If q = 0 T h e n Zeile = Zeile + 1 Cells(Zeile, i) = z(j) Cells(Zeile, 2) = s(j) Cells(Zeile, 3) = 1 E n d If E n d If i Next j ! Next i i End Sub J i........................................................................................................................................................................................................................... ] 284

10 Algorithmen aus der Natur

Mit Hilfe eines Mentis werden die drei Prozeduren aufgerufen.

Abb. 10-3 Mentizum Ameisenalgorithmus

Die Testdaten liefern das bereits bekannte Ergebnis von 40 Stunden. Es werden gleich mehrere L6sungen ausgegeben, ohne dass deren Vollst~ndigkeit gew~hrleistet ist.

Abb. 10-4 Ein m6gliches Ergebnis der Testdaten

Bedingt durch die Pseudozufallszahlen, wird jedes Mal ein anderes Ergebnis erzeugt. Die Pheromonmatrix (links) und die Ergebnisse der letzten Gruppe (rechts) habe ich grau gekennzeichnet.

Obungen FOhren Sie eine Gewichtung der Produkte ein und berOcksichtigen Sie diese bei der Pheromonauswertung. Uberlegen Sie, wie Sie einen Verwitterungsfaktor realisieren k6nnen (Pseudozufallszahlen).

285

10.2

Evolutionsstrategien

10.2

Evolutionsstrategien

Evolutionsstrategie

Die ersten Anwendungen der Evolutionsstrategie sind Ende der 60er Jahre zu finden. Es wurden ~ihnliche Theorien und Verfahren an verschiedenen Orten publiziert. In Deutschland ist es der Name Rechenberg, der mit der simulierten Evolution in Verbindung gebracht wird. Er lieferte die ersten wichtigen theoretischen Betrachtungen und sinnvollen Anwendungen. Als Beispiele sind die Optimiemng eines Rohrkrtimmers, einer Oberschalldtise, eines pneumatischen Reglers, eines Stabtragwerkes, u. a. zu nennen. Die Evolutionsstrategie ist eine universelle Methode zur Optimierung technischer Probleme. Sie wird vor allem bei Problemen eingesetzt, for die keine geschlossene L6sung vorliegt. Die Methode ~hnelt dem Prinzip der biologischen Evolution und besteht meist aus L6sungsversuchen auf realen Parameters~itzen, die dadurch besonders zur LOsung technischer Probleme geeignet sind. Im Gegensatz zu genetischen Algorithmen, bei denen eher ein genetischer Code benutzt wird, und die wir im Anschluss behandeln werden. Beide Methoden wurden unabh~ingig zur gleichen Zeit entwickelt. Das Prinzip einer Evolutionsstrategie ist im nachfolgenden Struktogramm allgemein wiedergegeben.

Tab. 10-4 Das Prinzip der Evolutonsstrategie

286 -

. . . . .

..

10 Algorithmen aus der Natur

Obernahme des verbesserten Systems als Startkriterium for weitere Generierungen

./.

Wiederholung, bis ein Abbruchkriterium greift. Ausgabe der erzielten LOsung Betrachten wir die Methode am nachfolgend einfachen Beispiel eines Stabwerks.

Beispiel: Stabwerkoptimierung Stabwerkoptimierung

Das dargestellte Stabwerk unterliegt den angegebenen Kr~iften und soil mit dem geringsten Materialaufwand gestaltet werden. Die Daten sind a=100 mm, FI=1000 N, F2=500 N, F3=200 N.

Abb. 10-5 Stabwerk unter Belasmng

W~hrend der obere Gurt unverS.ndert bleiben soil, k6nnen die sttitzenden StS.be reduziert werden. Das bedeutet, dass die Knoten K1 und K2 ver~indert werden k6nnen. Wir legen in diese Knoten Koordinatensysteme und ver~indern deren Lage zufallsbedingt um 1 mm. Die Beziehungen ergeben sich aus den nachfolgenden Bildern.

287

10.2

Evolutionsstrategien

F1 a

l Ylx,

x t

1

Abb. 10-6 Verschiebung des 1. Knotens

L l = ~ ( a - y l ' ) 2 + X l '2

L2

__~(

a + x l ' ) 2 +Yl

(10.2.1)

,2

vl

.

,\yi

(10.2.2)

,Lv~

I ~

,

Abb. 10-7 Verschiebung des 2. Knotens

L 3 = ~/(a - Xl'+X2') 2 + (Yl'-Y2 ,)2 L4

288

=~/(

a-y 2

,)2

+x 2

,2

(10.2..3) (10.2.4)

10 Algorithmen aus der Natur

F2

F3 ,

It

Y2 x 2 Abb. 10-8 Der Endstab

L5 = ~/(a-x2') 2 + ( a - y2') 2

(10.2.5)

Nun k6nnen wir den Algorithmus in Struktogrammform aufstellen. Tab. 10-50ptimierung eines Stabwerks nach der Evolutionsstrategie

Startbedingungen xl=0, yl=0, x2=0, y2=0 a=100 Ll=a, L2=a, L3=a, L4=a, L5=a~/2 m 1=0, m2=0, m3=0 GI=LI+L2 Axl=Int(Rnd(x)*3-1) Ay 1=Int(Rnd(x)*3-1) xl'=xl+Axl yl'=yl+Ayl L1

=~/(

a - Yl

,)2

+ Xl

,2

289

10.2

290

Evo l u t io nsst ra teg ien

10 Algorithmen aus der Natur

m3