| Περίληψη : | Στην παρούσα εργασία αναπτύσσονται και επιλύονται διάφορα προβλήματα εφαρμόζοντας δυναμικό προγραμματισμό. Ασχολούμαστε με προβλήματα ντετερμινιστικά, στοχαστικά και προβλήματα γραμμικού προγραμματισμού. Εξετάζουμε συγκεκριμένα «το πρόβλημα της άμαξας», στο οποίο ένας κυνηγός της τύχης ψάχνει τη συντομότερη διαδρομή με την οικονομικότερη ασφάλεια. Επιπλέον, εξετάζουμε την καταλληλότερη κατανομή των πωλητών των βιβλίων ενός εκδοτικού οίκου, προκειμένου να αυξηθούν οι πωλήσεις. Ακόμη, τον πιο κερδοφόρο συνδυασμό από άποψη υλικών, προκειμένου να κατασκευάσουμε δύο διαφορετικών ειδών σπαθιά και το «οικονομικότερο» σε ώρες ταξίδι που μπορούν να κάνουν κάποιοι ταξιδιώτες ξεκινώντας από την Αθήνα με προορισμό τη Βαρσοβία επισκεπτόμενοι κι άλλες ευρωπαϊκές πόλεις. Τέλος, υπολογίζουμε την πιθανότητα μιας γυναίκας στατιστικού να κερδίσει ένα παιχνίδι στο καζίνο του LasVegas, εφαρμόζοντας τα κατάλληλα βήματα ενός αλγορίθμου. Τα πέντε προβλήματα με τα οποία ασχολούμαστε παρουσιάζουν κοινά σημεία και συμπεριφορές και αυτός είναι ο λόγος για τον οποίο μπορούν όλα να επιλυθούν με τη βοήθεια του Δυναμικού Προγραμματισμού. Ψάχνουμε λοιπόν, για καθένα από αυτά τη βέλτιστη πολιτική η οποία θα μας οδηγήσει στη λύση με το ελάχιστο κόστος.
Subject of this thesis is Dynamic Programming and the study, analysis and solution of problems using this technique. We see deterministic, probabilistic and linear programming problems. We examine the “Stagecoach problem”, in which a fortune seeker searches for the smallest route combining the cheapest insurance. Furthermore, we examine the most appropriate distribution of salespersons of a publisher of college textbooks to some regions, in order to maximize sales. Moreover, the most profitable combination of materials in order to construct two different types of swords and the most “inexpensive” (in hours) trip that some family travelers can make, starting from Athens having as destination Warsaw whilst visiting different European cities. Finally, we calculate the possibility of a woman statistician of winning a very popular casino game in Las Vegas, applying all the appropriate steps of an algorithm. The five problems, that we investigate, have some common characteristics and behavior and that is the reason why all of them can be solved using Dynamic Programming. So, we search for the optimal policy of everything of the above, which leads us to the minimum cost solution.
|
|---|
Copyright © 2013 Βιβλιοθήκη Ο.Π.Α. Με την επιφύλαξη παντός δικαιώματος.