Η παρούσα μεταπτυχιακή διπλωματική εργασία αποτελεί μια προσπάθεια εισαγωγής της θεωρίας παιγνίων σε προβλήματα της επιστήμης του δομοστατικού πολιτικού μηχανικού και πιο συγκεκριμένα της βελτιστοποίησης του σχεδιασμού των κατασκευών. Αντικείμενο του βέλτιστου σχεδιασμού των κατασκευών είναι να αποκτήσει μια κατασκευή τον καλύτερο συνδυασμό των επιθυμητών χαρα­κτηριστικών της, δηλαδή ασφάλειας, λειτουργικότητας και οικονομικότητας. Μια τέτοια προσπάθεια απαιτεί φυσικά την καλή κρίση του μηχανικού, καθώς και την κατανόηση του προβλήματος. Η θεωρία παιγνίων παρέχει χρήσιμες συμβουλές αναφορικά με την ανάλυση καταστάσεων και λήψη αποφάσεων. Συνεπώς, μπορεί, αν χρησιμοποιηθεί κατάλληλα, να αποτελέσει ένα πολύτιμο εργαλείο στα χέρια του μηχανικού, τόσο στο βέλτιστο σχεδιασμό των κατασκευών, όσο και σε άλλες εφαρμογές που απαιτούν καλή κρίση.

Στο Κεφάλαιο 2 γίνεται μια εισαγωγή στη θεωρία παιγνίων, ούτως ώστε ο αναγνώστης να εξοικειωθεί με το αντικείμενό της. Πρώτα εξηγούνται οι βασικές έννοιές της, όπως για παράδειγμα η ωφέλεια, που αποτελεί ένα μέγεθος που ποσοτικοποιεί την ικανοποίηση που προσδίδει σε κάθε άτομο ένα γεγονός. Έπειτα, ο αναγνώστης εξοικειώνεται με την Ισορροπία Nash, που αποτελεί ένα σύνολο στρατηγικών που αποτελούν ταυτόχρονα καλύτερη απάντηση η καθεμία στις υπόλοιπες. Εν συνεχεία παρουσιάζονται ορισμένοι κλάδοι, όπως η θεωρία δημοπρασιών και τα συστήματα ψηφοφορίας, στη μελέτη των οποίων η θεωρία παιγνίων έχει γνωρίσει μεγάλη άνθιση και παίζει καθοριστικό ρόλο. Το κεφάλαιο αυτό είναι πλήρως απαλλαγμένο από μαθηματικούς υπολογισμούς και έχει αποκλειστικό στόχο να εξοικειώσει με τις βασικές έννοιες της θεωρίας παιγνίων.

Το Κεφάλαιο 3 είναι περισσότερο προσανατολισμένο σε μαθηματικούς υπολογισμούς. Στο κεφάλαιο αυτό παρουσιάζονται οι τρόποι με τους οποίους είναι δυνατή η εύρεση Ισορροπίας Nash. Οι κυριότερες μέθοδοι που αναφέρονται είναι η διαδοχική διαγραφή κυριαρχούμενων στρατηγικών και η μέθοδος της πίσω επαγωγής, όσον αφορά σε Ισορροπίες Nash με χρήση καθαρών στρατηγικών, ενώ αναφέρεται και η μετατροπή σε ισοδύναμο πρόβλημα γραμμικής συμπληρωματικότητας, όσον αφορά σε Ισορροπίες Nash με χρήση μικτών στρατηγικών.

Στο Κεφάλαιο 4 παρουσιάζεται το πρόβλημα του βέλτιστου σχεδιασμού των κατασκευών που επιλύει η παρούσα εργασία, και εισάγεται η προτεινόμενη μεθοδολογία, η Μέθοδος Μεγιστοποίησης Ελάχιστης Ωφέλειας. Η μέθοδος αυτή παρέχει τη δυνατότητα ευρύτερης επιλογής αντικειμενικής συνάρτησης, ξεφεύγοντας από το κλασικό πρόβλημα του οικονομικότερου δυνατού σχεδιασμού, ενώ παράλληλα επιτρέπει τη χρήση περιορισμών που αφορούν οποιαδήποτε πιθανή μεταβλητή σχεδιασμού, συμπεριλαμβανομένων και των οικονομικών πόρων. Σύμφωνα με τη Μέθοδο Μεγιστοποίησης Ελάχιστης Ωφέλειας, το διακριτό πρόβλημα βέλτιστου σχεδιασμού των κατασκευών προσομοιώνεται ως παίγνιο, με παίκτες τον αμυνόμενο, που υπερασπίζεται το φορέα, διαχειριζόμενος την δυσκαμψία των υλικών του και τον επιτιθέμενο, ο οποίος διαλέγει τον τρόπο που θα επιτεθεί στο φορέα, επιλέγοντας ανάμεσα σε κάποια προκαθορισμένα σενάρια φόρτισης που περιγράφουν οι οικείοι κανονισμοί ή και άλλες πρόσθετες φορτίσεις. Παράλληλα, η μέθοδος αντιστοιχεί ωφέλεια στους δύο παίκτες ανάλογα με τα αποτελέσματα (σε όρους τάσεων, μετακινήσεων και χρηματικών δαπανών) που προκύπτουν από τις κινήσεις τους. Το παίγνιο προσομοιώνεται με τέτοιο τρόπο, ώστε να είναι πλήρως ανταγωνιστικό, παρεμποδίζοντας κάθε δυνατότητα συνεργασίας μεταξύ των δύο παικτών. Εν συνεχεία, το παίγνιο λύνεται με τη χρήση της θεωρίας παιγνίων και τη μέθοδο της πίσω-επαγωγής. Με αυτό τον τρόπο εντοπίζονται ταυτόχρονα ο βέλτιστος σχεδιασμός της κατασκευής, καθώς και η κρίσιμη φόρτιση που θα δεχτεί στην Ισορροπία Nash.

Το Κεφάλαιο 5 είναι αφιερωμένο στους ευρετικούς αλγορίθμους. Η εγγενής δυσκολία της μεθοδολογίας έγκειται στην συνδυαστική έκρηξη όλων των πιθανών παραλλαγών που καθορίζουν το χώρο των λύσεων, η πλήρης αντιμετώπιση των οποίων απαιτεί μεγάλο υπολογιστικό χρόνο και μνήμη υπολογιστή, σε σημείο που, παρά τη θεωρητική της ισχύ, η χρήση της να καθίσταται ασύμφορη. Η αδυναμία αυτή οφείλεται στο γεγονός πως, ακόμα και για μικρού μεγέθους προβλήματα, οι πιθανές στρατηγικές που είναι διαθέσιμες στον αμυνόμενο είναι μεν πεπερασμένες, αλλά έχουν πολύ μεγάλο πλήθος. Η θεωρία παιγνίων προϋποθέτει τη σειριακή εξέταση κάθε στρατηγικής, γεγονός που καθιστά ασύμφορη τη μέθοδο στην κλασική της μορφή. Για το λόγο αυτό χρησιμοποιήθηκαν τρεις ευρετικοί αλγόριθμοι (heuristics), οι οποίοι έχουν στόχο να εντοπίσουν τη βέλτιστη λύση εξετάζοντας κατάλληλα επιλεγόμενο τμήμα του χώρου των λύσεων σε πολύ μικρό χρονικό διάστημα, εκχωρώντας την βεβαιότητα της εύρεσης της μαθηματικά βέλτιστης λύσης, διατηρώντας όμως καλές προϋποθέσεις εύρεσης καλών λύσεων στη περιοχή της θεωρητικά βέλτιστης λύσης. Ένας εκ των αλγορίθμων που χρησιμοποιήθηκε αφορά στην Προσομοιωμένη Ανόπτηση, (simulated annealing), ενώ οι υπόλοιποι δύο αναπτύχθηκαν στα πλαίσια της παρούσας εργασίας.

Συνδυάζοντας τη Μέθοδο Μεγιστοποίησης Ελάχιστης Ωφέλειας (maximization of minimum utility) και τους ευρετικούς αλγορίθμους, προκύπτει ένα ισχυρό εργαλείο διακριτής βελτιστοποίησης, ικανό για επίλυση πλήθους προβλημάτων. Στο Κεφάλαιο 6 παρουσιάζεται ένα πλήθος αριθμητικών εφαρμογών που αφορούν προβλήματα διαστασιολόγησης, τοπολογίας, σχήματος και ελαχιστοποίηση μετακίνησης με οικονομικούς περιορισμούς. Η εγκυρότητα της μεθόδου επαληθεύεται επιλύοντας ήδη γνωστά προβλήματα από τη βιβλιογραφία. Σε κάθε περίπτωση, τα αποτελέσματα της μεθόδου ταυτίζονται με τα αποτελέσματα της βιβλιογραφίας.

Στο Κεφάλαιο 7 παρουσιάζονται τα συμπεράσματα της εργασίας και προτείνονται ιδέες για μελλοντική έρευνα. Τόσο η Μέθοδος Μεγιστοποίησης Ελάχιστης Ωφέλειας όσο και οι ευρετικοί αλγόριθμοι που χρησιμοποιήθηκαν για την επιτάχυνση της μεθόδου έχουν λειτουργήσει ικανοποιητικά. Η προτεινόμενη μεθοδολογία μπορεί να λύσει κάθε πρόβλημα βελτιστοποίησης, υπό την προϋπόθεση πως είναι διαθέσιμος ο αντίστοιχος επιλύτης. Ο φορέας προς βελτιστοποίηση επιτρέπεται να είναι δικτύωμα, πλαίσιο ή οποιαδήποτε άλλης μορφής. Παράλληλα, η προτεινόμενη μεθοδολογία καθιστά δυνατή τη μελέτη πλήθους σεναρίων φόρτισης. Βέβαια, οι ευρετικοί αλγόριθμοι χρίζουν περαιτέρω βελτίωσης, γεγονός που αναμένεται να μειώσει ακόμα περισσότερο το χρόνο εκτέλεσης.