Mοντελοποίηση και Προσοµοίωση Σηµείωση Το ΕΑΠ είναι υπεύθυνο για την επιµέλεια έκδοσης και την ανάπτυξη των κειµένων σύµφωνα µε τη Μεθο- δολογία της εξ Αποστάσεως Εκπαίδευσης. Για την επιστηµονική αρτιότητα και πληρότητα των συγγραµ- µάτων την αποκλειστική ευθύνη φέρουν οι συγγραφείς, κριτικοί αναγνώστες και ακαδηµαϊκοί υπεύθυνοι που ανέλαβαν το έργο αυτό. ΕΛΛΗΝΙΚΟ ΑΝΟΙΚΤΟ ΠΑΝΕΠΙΣΤΗΜΙΟ Σχολή Θετικών Επιστηµών και Τεχνολογίας Πρόγραµµα Σπουδών ΠΛHPOΦOPIKH Θεµατική Ενότητα ΓPAMMIKOΣ ΠPOΓPAMMATIΣMOΣ KAI MONTEΛOΠOIHΣH Τόµος A' Mοντελοποίηση και Προσοµοίωση MANOΣ POYMEΛIΩTHΣ Eπίκουρος Kαθηγητής Tµήµατος Eφαρµοσµένης Πληροφορικής Πανεπιστηµίου Mακεδονίας ΠATPA 2001 ΕΛΛΗΝΙΚΟ ΑΝΟΙΚΤΟ ΠΑΝΕΠΙΣΤΗΜΙΟ Σχολή Θετικών Επιστηµών και Τεχνολογίας Πρόγραµµα Σπουδών ΠΛHPOΦOPIKH Θεµατική Ενότητα ΓPAMMIKOΣ ΠPOΓPAMMATIΣMOΣ KAI MONTEΛOΠOIHΣH Τόµος A' Mοντελοποίηση και Προσοµοίωση Συγγραφή MANOΣ POYMEΛIΩTHΣ Eπίκουρος Kαθηγητής Tµήµατος Eφαρµοσµένης Πληροφορικής Πανεπιστηµίου Mακεδονίας Κριτική Ανάγνωση XAPAΛAMΠOΣ MΠOTΣAPHΣ Kαθηγητής Tµήµατος Mαθηµατικών Πανεπιστηµίου Πατρών Ακαδηµαϊκός Υπεύθυνος για την επιστηµονική επιµέλεια του τόµου ΣΩKPATHΣ KATΣIKAΣ Καθηγητής Tµήµατος Mηχανικών Πληροφοριακών και Eπικοινωνιακών Συστηµάτων Πανεπιστηµίου Aιγαίου Επιµέλεια στη µέθοδο της εκπαίδευσης από απόσταση ΠETPOΣ ΓANOΣ Γλωσσική Επιµέλεια ΣTEΦANOΣ ΛOYNTZHΣ Τεχνική Επιµέλεια TYPORAMA Καλλιτεχνική Επιµέλεια – Σελιδοποίηση TYPORAMA Συντονισµός ανάπτυξης εκπαιδευτικού υλικού και γενική επιµέλεια των εκδόσεων ΟΜΑ∆Α ΕΚΤΕΛΕΣΗΣ ΕΡΓΟΥ ΕΑΠ / 2001 ISBN: 960–538–213–X Kωδικός Έκδοσης: ΠΛH 32/1 Copyright 2000 για την Ελλάδα και όλο τον κόσµο ΕΛΛΗΝΙΚΟ ΑΝΟΙΚΤΟ ΠΑΝΕΠΙΣΤΗΜΙΟ Οδός Παπαφλέσσα & Υψηλάντη, 26222 Πάτρα – Τηλ: (0610) 314094, 314206 Φαξ: (0610) 317244 Σύµφωνα µε το Ν. 2121/1993, απαγορεύεται η συνολική ή αποσπασµατική αναδηµοσίευση του βιβλίου αυτού ή η αναπαραγωγή του µε οποιοδήποτε µέσο χωρίς την άδεια του εκδότη. ¶ÂÚȯfiÌÂÓ· K∂º∞§∞π√ 1 ¶ÚÔÛÔÌÔ›ˆÛË Î·È MÔÓ٤Ϸ ™˘ÛÙËÌ¿ÙˆÓ Σκοπός, Προσδοκώµενα αποτελέσµατα, Έννοιες κλειδιά Eισαγωγικές παρατηρήσεις 9 ....................................................................................................................................... 1.1 Προσοµοίωση και εξοµοίωση 11 ............................................................................................................ 1.2 Oρισµός του συστήµατος και ιδιότητες συστηµάτων 15 ................................................... 1.3 Mοντέλα συστηµάτων 21 .............................................................................................................................. 1.3.1 Tύποι µοντέλων 24 ............................................................................................................................... 1.4 ∆ηµιουργία µοντέλων προσοµοίωσης 29 ........................................................................................ 1.4.1 Mοντέλα προσοµοίωσης 30 .......................................................................................................... 1.4.2 Kατασκευή µοντέλων προσοµοίωσης 31 .......................................................................... 1.4.3 Kριτήρια καλού µοντέλου 31 ....................................................................................................... 1.5 Φάσεις της προσοµοίωσης 33 .................................................................................................................... 1.5.1 Mηχανισµοί ελέγχου του χρόνου 34 ...................................................................................... Σύνοψη 38 ................................................................................................................................................................................... Bιβλιογραφία 39 ..................................................................................................................................................................... K∂º∞§∞π√ 2 MÔÓÙÂÏÔÔ›ËÛË ™˘Ó¯ÒÓ ™˘ÛÙËÌ¿ÙˆÓ Σκοπός, Προσδοκώµενα αποτελέσµατα, Έννοιες κλειδιά Eισαγωγικές παρατηρήσεις 41 .................................................................................................................................... 2.1 Aναλυτικά µοντέλα 43 ..................................................................................................................................... 2.1.1 Kατασκευή αναλυτικών µοντέλων 44 .................................................................................. 2.1.2 Προσδιορισµός των µεταβλητών 45 ...................................................................................... 2.1.3 Kαθορισµός των σχέσεων ανάµεσα στις µεταβλητές 45 ..................................... 2.1.4 Περιορισµοί 46 ......................................................................................................................................... 2.2 Mοντέλα ιστού 46 ................................................................................................................................................ 2.3 Aνάλυση ευαισθησίας συστηµάτων 50 ............................................................................................. Σύνοψη 54 ................................................................................................................................................................................... Bιβλιογραφία 55 ..................................................................................................................................................................... 6 M√¡∆∂§√¶√π∏™∏ ∫∞𠶃√™√ª√πø™∏ K∂º∞§∞π√ 3 AÓ¿Ù˘ÍË MÔÓÙ¤ÏˆÓ ¢È·ÎÚÈÙÒÓ ™˘ÛÙËÌ¿ÙˆÓ Σκοπός, Προσδοκώµενα αποτελέσµατα, Έννοιες κλειδιά Eισαγωγικές παρατηρήσεις 57 .................................................................................................................................... 3.1 Oρισµοί 59 .................................................................................................................................................................. 3.2 Προσοµοίωση γεγονότων 61 ...................................................................................................................... 3.2.1 O διαχειριστής της προσοµοίωσης γεγονότων 62 ...................................................... 3.3 Προσοµοίωση δραστηριοτήτων 65 ....................................................................................................... 3.3.1 ∆ιαγράµµατα κύκλου δραστηριοτήτων 65 ....................................................................... 3.3.2 O διαχειριστής της προσοµοίωσης δραστηριοτήτων 69 ...................................... 3.4 H µέθοδος των τριών φάσεων 72 ........................................................................................................... 3.5 Προσοµοίωση διεργασιών 73 .................................................................................................................... 3.5.1 Εκτέλεση των εργασιών 74 ........................................................................................................... 3.6 ∆ίκτυα Petri 78 ....................................................................................................................................................... 3.6.1 ∆οµή των δικτύων Petri 78 ............................................................................................................ 3.6.2 Γραφήµατα των δικτύων Petri 80 ............................................................................................. 3.6.3 Mαρκαρίσµατα των δικτύων Petri 82 ................................................................................... 3.6.4 Eκτέλεση των δικτύων Petri 82 ................................................................................................. 3.6.5 Xώροι καταστάσεων των δικτύων Petri 85 ..................................................................... 3.6.6 Σύγκρουση 85 ............................................................................................................................................ 3.6.7 Aσφάλεια των δικτύων Petri 86 ................................................................................................ 3.6.8 Mοντελοποίηση µε δίκτυα Petri 87 ........................................................................................ Σύνοψη 92 ................................................................................................................................................................................... Bιβλιογραφία 93 ..................................................................................................................................................................... K∂º∞§∞π√ 4 EÚÁ·Ï›· Case Σκοπός, Προσδοκώµενα αποτελέσµατα, Έννοιες κλειδιά Eισαγωγικές παρατηρήσεις 95 .................................................................................................................................... 4.1 Eξειδικευµένες γλώσσες προσοµοίωσης 97 .................................................................................. 4.1.1 Eπιλογή της γλώσσας προσοµοίωσης 98 ........................................................................... 4.1.2 Συγκριτικά στοιχεία των γλωσσών προσοµοίωσης 100 ....................................... 4.1.3 Simscript 101 ............................................................................................................................................. 4.1.3.1 Tα εργαλεία της Simscript 102 ............................................................................... 4.1.3.2 Aνάπτυξη προγραµµάτων προσοµοίωσης στη Simscript II 5 103 ...................................................................................................... ¶EPIEXOMENA 7 4.1.4 Modsim III 107 .......................................................................................................................... 4.1.4.1 To περιβάλλον της Modsim II 108 ....................................................................... 4.1.4.2 Aνάπτυξη προγραµµάτων προσοµοίωσης στη Modsim III 109 ........................................................................................................... 4.1.5 Simula 111 ..................................................................................................................................... 4.1.6 GPSS 112 ........................................................................................................................................ 4.1.6.1 Tα βασικά µπλοκ της GPSS 113 ............................................................................ 4.1.6.2 Eντολές ελέγχου της GPSS 123 ............................................................................. 4.1.6.3 Παραδείγµατα µοντέλων GPSS 128 ................................................................... 4.2 Γλώσσες γενικής χρήσεως 144 ................................................................................................................. 4.2.1 ∆οµές δεδοµένων 144 ......................................................................................................................... 4.2.2 Mηχανισµός ροής χρόνου 151 .................................................................................................... Σύνοψη 152 ................................................................................................................................................................................ Bιβλιογραφία 153 .................................................................................................................................................................. K∂º∞§∞π√ 5 M¤ıÔ‰ÔÈ ¢ÂÈÁÌ·ÙÔÏË„›·˜ Σκοπός, Προσδοκώµενα αποτελέσµατα, Έννοιες κλειδιά Eισαγωγικές παρατηρήσεις 155 ................................................................................................................................. 5.1 Tυχαίοι και ψευδοτυχαίοι αριθµοί 157 .............................................................................................. 5.2 Iδιότητες τυχαίων αριθµών 160 ............................................................................................................... 5.3 Γεννήτριες τυχαίων αριθµών 164 ........................................................................................................... 5.3.1 Γεννήτριες µεσαίων τετραγώνων 164 .................................................................................. 5.3.2 Γραµµικές ισοϋπόλοιπες γεννήτριες 166 ........................................................................... 5.3.3 Πολλαπλασιαστικές ισοϋπόλοιπες γεννήτριες 169 ................................................... 5.3.4 Άλλες ισοϋπόλοιπες γεννήτριες 170 ...................................................................................... 5.3.5 Γεννήτριες Tausworthe 170 ........................................................................................................... 5.4 Έλεγχος τυχαιότητας 170 .............................................................................................................................. 5.5 Παραγωγή τυχαίων δειγµάτων 173 ....................................................................................................... 5.5.1 Mέθοδος αντίστροφου µετασχηµατισµού 173 .............................................................. 5.5.2 Mέθοδος της αποδοχής–απόρριψης 177 ............................................................................ 5.5.3 Συνθετική µέθοδος 178 ..................................................................................................................... 5.5.4 H εµπειρική µέθοδος 180 ................................................................................................................ 5.6 Mέθοδος Monte Carlo 185 ........................................................................................................................... Σύνοψη 191 ................................................................................................................................................................................ Bιβλιογραφία 192 .................................................................................................................................................................. 8 TEXNO§O°IA §O°I™MIKOY II K∂º∞§∞π√ 6 AÓ¿Ï˘ÛË AÔÙÂÏÂÛÌ¿ÙˆÓ Σκοπός, Προσδοκώµενα αποτελέσµατα, Έννοιες κλειδιά Eισαγωγικές παρατηρήσεις 193 ................................................................................................................................. 6.1 Tύποι προσοµοίωσης 195 ............................................................................................................................. 6.2 Aρχικές συνθήκες και σταθερή κατάσταση 196 ....................................................................... 6.3 Συλλογή δεδοµένων 199 ................................................................................................................................ 6.3.1 Συλλογή ανεξάρτητων δεδοµένων 200 ................................................................................ 6.3.2 Συλλογή εξαρτηµένων δεδοµένων 201 ............................................................................... 6.4 Στατιστική ανάλυση των αποτελεσµάτων 203 ........................................................................... 6.4.1 Mέθοδος των επαναλήψεων 203 ............................................................................................... 6.4.2 Mέθοδος των µέσων παρτίδων 205 ........................................................................................ 6.4.3 Mέθοδος της αναγέννησης 206 .................................................................................................. Σύνοψη 208 ................................................................................................................................................................................ Bιβλιογραφία 209 .................................................................................................................................................................. Aπαντήσεις Aσκήσεων Aυτοαξιολόγησης 211 ........................................................................................... Aπαντήσεις ∆ραστηριοτήτων 229 ........................................................................................................................... Eυρετήριο 243 ......................................................................................................................................................................... 1 ∫ ∂ º ∞ § ∞ π √ ¶ÚÔÛÔÌÔ›ˆÛË Î·È MÔÓ٤Ϸ ™˘ÛÙËÌ¿ÙˆÓ ™ÎÔfi˜ Στο κεφάλαιο αυτό γίνεται µια γενική εισαγωγή στις έννοιες τις προσοµοίωσης και µοντελοποίησης. Ο στόχος του είναι να εξηγήσει τι είναι τα µοντέλα συστηµάτων και ποια είναι τα χαρακτηριστικά τους, καθώς και να αναλύσει τους λόγους για τους οποί- ους χρησιµοποιείται η προσοµοίωση για τη µελέτη συστηµάτων. ¶ÚÔÛ‰ÔÎÒÌÂÓ· ·ÔÙÂϤÛÌ·Ù· Όταν τελειώσετε τη µελέτη του κεφαλαίου αυτού θα είστε σε θέση να: • διακρίνετε τη διαφορά ανάµεσα στην εξοµοίωση και την προσοµοίωση και να µπο- ρείτε να πείτε αν µια εργασία είναι προσοµοίωση ή εξοµοίωση • αναφέρετε τουλάχιστον τρία είδη συστηµάτων • διακρίνετε αν µια δραστηριότητα είναι προσδιορισµένη ή στοχαστική • αναφέρετε τουλάχιστον πέντε λόγους για τους οποίους κατασκευάζονται µοντέλα συστηµάτων • αναφέρετε τους τέσσερις συνδυασµούς συστηµάτων – µοντέλων και ένα παράδειγ- µα κάθε συνδυασµού • αναφέρετε τουλάχιστον τέσσερις τύπους µοντέλων, καθώς και µια ταξινόµησή τους • διακρίνετε ένα απλό µοντέλο από ένα πολύπλοκο • εξηγείτε πώς λειτουργούν οι δύο µηχανισµοί ελέγχου του χρόνου κατά την προσο- µοίωση ŒÓÓÔȘ ÎÏÂȉȿ • προσοµοίωση και εξοµοίωση • µοντέλο • σύστηµα • φυσικά και µαθηµατικά µοντέλα, ανα- • κατάσταση συστήµατος, περιβάλλον λυτικά και αριθµητικά µοντέλα συστήµατος • οντότητα και χαρακτηριστικά της • ανοικτά και κλειστά συστήµατα, συνε- • δραστηριότητα χή και διακριτά συστήµατα, προσαρ- • ενδογενείς και εξωγενείς δραστηριό- µοζόµενα και µη προσαρµοζόµενα τητες, προσδιορισµένες και στοχαστι- συστήµατα κές δραστηριότητες 10 KEºA§AIO 1: ¶ƒ√™√ª√πø™∏ ∫∞π M√¡∆∂§∞ ™À™∆∏ª∞∆ø¡ • γεγονός • µηχανισµός ροής χρόνου (ΜΡΧ) • µηχανισµός επόµενου γεγονότος, µηχα- νισµός σταθερού διαστήµατος ∂ÈÛ·ÁˆÁÈΤ˜ ·Ú·ÙËÚ‹ÛÂȘ Η µελέτη συστηµάτων µε µαθηµατικές µεθόδους απαιτεί αφενός πλήρη γνώση του υπάρ- χοντος ή προτεινοµένου συστήµατος και αφετέρου δυνατότητα αναπαράστασης του συστή- µατος µε µαθηµατικά µοντέλα. Επειδή, όµως, οι δύο αυτές προϋποθέσεις σχεδόν ποτέ δεν πληρούνται σε πολύπλοκα συστήµατα, αναπτύχθηκαν άλλες µεθοδολογίες µελέτης και ανάλυσης συστηµάτων, οι οποίες αν και δεν είναι τόσο ακριβείς όσο οι µαθηµατικές µέθο- δοι, προσφέρουν σηµαντικά πλεονεκτήµατα. Μία από αυτές τις µεθόδους είναι η προσο- µοίωση, η οποία γνώρισε µεγάλη εξέλιξη κυρίως λόγω της ανάπτυξης των ηλεκτρονικών υπολογιστών. Η προσοµοίωση αποτελεί µία πειραµατική µέθοδο που έχει ως σκοπό τη βελτιστο- ποίηση συστηµάτων, την ανάλυση της ευαισθησίας τους και τη µελέτη της λειτουρ- γίας τους. Ως πειραµατική µέθοδος εξαρτάται πολύ από την πιστότητα του µοντέλου του συστήµατος που χρησιµοποιείται, καθώς και από την επιλογή εκείνων των παρα- µέτρων που απαιτούνται για την εξαγωγή αξιόπιστων και χρήσιµων συµπερασµάτων. Στην ενότητα 1.1 αναλύεται η έννοια της προσοµοίωσης και η διαφορά της από την εξοµοίωση. Στην ενότητα 1.2 δίνεται ο ορισµός του συστήµατος και αναπτύσσονται τα χαρακτηριστικά των συστηµάτων που αφορούν τη µοντελοποίησή του. Στην ενό- τητα 1.3 δίνεται ο ορισµός του µοντέλου και αναλύονται οι διάφοροι τύποι µοντέλων, οι οποίοι οδηγούν σε διάφορες ταξινοµήσεις µοντέλων. Στην ενότητα 1.4 αναπτύσ- σονται οι λόγοι δηµιουργίας µοντέλων προσοµοίωσης, οι τεχνικές κατασκευής των µοντέλων αυτών, καθώς και τα κριτήρια ενός καλού µοντέλου. Τέλος, στην ενότητα 1.5 δίνονται οι φάσεις της προσοµοίωσης και αναπτύσσονται περιληπτικά οι µηχα- νισµοί ροής χρόνου, που χρησιµοποιούνται κατά την προσοµοίωση. Για τη µελέτη του κεφαλαίου αυτού δεν απαιτούνται ιδιαίτερες γνώσεις από τον ανα- γνώστη εκτός από τις βασικές µαθηµατικές έννοιες γραµµικών και µη γραµµικών εξι- σώσεων, τις οποίες ο αναγνώστης µπορεί να αναζητήσει στα βιβλία του Λυκείου. 1.1 ¶ƒ√™√ª√πø™∏ ∫∞π ∂•√ª√πø™∏ 11 1.1 ¶ÚÔÛÔÌÔ›ˆÛË Î·È ÂÍÔÌÔ›ˆÛË Ο όρος προσοµοίωση (simulation στα αγγλικά) συγχέεται συχνά µε τον όρο εξοµοί- ωση (emulation στα αγγλικά), αν και οι όροι αυτοί υποδηλώνουν τελείως διαφορε- τικές µεθοδολογίες. (cid:2)Ορισµός 1.1 Προσοµοίωσηείναι µια µέθοδος µελέτης ενός συστήµατος και εξοικείωσης µε τα χαρακτηριστικά του µε τη βοήθεια ενός άλλου συστήµατος το οποίο στις περισσότερες περιπτώσεις είναι ηλεκτρονικός υπολογιστής. (cid:2)Ορισµός 1.2 Εξοµοίωση είναι µια µέθοδος αναπαραγωγής ενός συστήµατος εντός ή µέσω ενός άλλου συστήµατος παρόµοιου µε το πρώτο. Είναι λοιπόν εµφανές ότι κατά την προσοµοίωση δεν πρέπει να υπάρχει ούτε η εντύ- πωση ούτε η επιθυµία υλοποίησης του πραγµατικού συστήµατος, γιατί σκοπός είναι η µελέτη του συστήµατος και όχι η χρήση του. Αντίθετα, κατά την εξοµοίωση υπάρ- χει η εντύπωση υλοποίησης στο πραγµατικό σύστηµα γιατί σκοπός είναι η χρήση του. ¶·Ú¿‰ÂÈÁÌ· 1.1 Ως πρώτο Παράδειγµα ας εξετάσουµε την προσοµοίωση και την εξοµοίωση ενός αεροσκάφους τύπου Airbus A320. Η προσοµοίωση ενός αεροσκάφους του τύπου αυτού µπορεί να γίνει είτε εξ ολοκλήρου σε έναν ηλεκτρονικό υπολογιστή είτε µε την κατασκευή ενός συστήµατος που έχει όλα τα χειριστήρια και όργανα του αερο- σκάφους. Στην πρώτη περίπτωση είναι πιθανόν να απαιτείται η µελέτη της συµπεριφοράς του αεροσκάφους από αεροδυναµικής απόψεως, της αντίδρασής του σε ανέµους και κενά αέρος, κτλ. Για το σκοπό αυτό δηµιουργείται στον υπολογιστή ένα µαθηµατικό µοντέλο του αεροσκάφους και εισάγονται σ’ αυτό οι παράµετροι των φυσικών χαρα- κτηριστικών του αεροσκάφους καθώς και οι εξισώσεις αεροδυναµικής. Από την προ- σοµοίωση κατόπιν εξάγονται τα αποτελέσµατα που αφορούν την αντίσταση του αέρα, τις δυνάµεις άνωσης, την πιθανή δηµιουργία στροβίλων, κ.λπ. Στη δεύτερη περίπτωση είναι πιθανόν να επιδιώκεται η εκπαίδευση πιλότων του αεροσκάφους, πριν ακόµη αυτό κατασκευασθεί ή να επιλέγεται η προσοµοίωση για λόγους ασφαλείας ή οικονοµίας. Προς το σκοπό αυτό κατασκευάζεται ένα σύστηµα προσοµοίωσης, το οποίο έχει όλα τα απαραίτητα χειριστήρια και όργανα του αερο- σκάφους και ελέγχεται από ηλεκτρονικό υπολογιστή. Ο υπολογιστής αντιδρώντας