Δυναμικός προγραμματισμός, βασικές αρχές

Κατά τη δεκαετία του 1950, ο Αμερικανός μαθηματικός R. Bellman και αρκετοί συνεργάτες του ανέπτυξαν μια νέα γενική μέθοδο επίλυσης μεταβλητών προβλημάτων, που ονομάζεται δυναμικός προγραμματισμός. Αυτή η μέθοδος είναι κατάλληλη για τη βελτιστοποίηση οποιουδήποτε πολύπλοκα συστήματα, που περιγράφεται όχι μόνο από διαφορικές εξισώσεις με περιορισμούς στη μεταβλητή ή χωρίς αυτούς, αλλά και από άλλες μαθηματικές συσκευές, συμπεριλαμβανομένων διαφόρων στατικών συστημάτων, QS και οικονομικών συστημάτων.

Το MDP στην ιδέα του διαφέρει σημαντικά από τον κλασικό λογισμό των παραλλαγών και την αρχή του μέγιστου Pontryagin. Η τεχνική για την επίλυση των δύο τελευταίων μεθόδων είναι ότι η βέλτιστη τροχιά θεωρείται ήδη κάπως γνωστή. Τότε ολόκληρη αυτή η βέλτιστη τροχιά μεταβάλλεται ως σύνολο· γενικά, το σύνολο των μεταβλητών τροχιών τους είναι βέλτιστο.

Στο MPE υιοθετείται ένας διαφορετικός τρόπος εύρεσης των βέλτιστων τροχιών, ο οποίος συνίσταται στο ότι η βέλτιστη τροχιά και η αντίστοιχη εξίσωση αναζητούνται σε ξεχωριστά τμήματα ή βήματα. Με άλλα λόγια, είναι πιο εύκολο να σπάσουν σε πολλά στάδια, καθένα από τα οποία έχει ένα σύνολο τροχιών και τα αντίστοιχα χειριστήρια. Τώρα θα φαινόταν αρκετό να τακτοποιήσουμε όλες τις τροχιές και να επιλέξουμε τη βέλτιστη, αλλά αυτό είναι ένα παράλογο τιτάνιο έργο. Οι δημιουργοί του TIR ακολούθησαν διαφορετικό μονοπάτι - σε κάθε στάδιο επιλέγουν το βέλτιστο και απορρίπτουν μη βέλτιστα, χωρίς πολλά υποσχόμενα τμήματα των τροχιών (σε ξεχωριστό στάδιο για το τμήμα είναι πολύ πιο εύκολο να γίνει αυτό παρά για την τροχιά ως ολόκληρος). Σε αυτήν την περίπτωση, αποδεικνύεται ότι όχι μόνο ένα μη βέλτιστο κομμάτι της τροχιάς απορρίπτεται σε αυτό το στάδιο, αλλά και ολόκληρη η τροχιά στο σύνολό της, η οποία περιλαμβάνει ένα χωρίς πολλά υποσχόμενο κομμάτι στο στάδιο που εξετάζουμε. Σε αυτή την περίπτωση, η επιλογή της βέλτιστης τροχιάς είναι πολύ πιο εύκολη και συντομότερη.

Για να επιβεβαιώσουμε όσα ειπώθηκαν, ας εξετάσουμε ένα στατικό πρόβλημα επιλογής της βέλτιστης τροχιάς.

Παράδειγμα.

Αφήστε ανάμεσα στα σημεία και θα πρέπει να τοποθετήσετε έναν σιδηρόδρομο ή αυτοκινητόδρομο του ελάχιστου κόστους. Το έδαφος είναι πολύ δύσκολο και οι προκαταρκτικές έρευνες έδειξαν ότι αν ο δρόμος στρωθεί σε ευθεία γραμμή, το κόστος του θα είναι πολύ υψηλό. Τοπογράφοι και οικονομολόγοι εξέτασαν ξεχωριστά, σχετικά εύκολα στην κατασκευή τμήματα μεταξύ και καθόρισαν το κόστος κατασκευής αυτών των τμημάτων. Το κόστος κατασκευής του δρόμου θα είναι το άθροισμα του κόστους κατασκευής αυτών των τμημάτων. Αυτή η εργασίαμπορεί να λυθεί απαριθμώντας όλες τις πιθανές τροχιές μεταξύ και επιλέγοντας τη φθηνότερη. Ωστόσο, αυτός ο δρόμος είναι πρακτικά απεριόριστος. Ως εκ τούτου, θα βρούμε το TIR στην πορεία. Ας αναλύσουμε ολόκληρη την περιοχή κατασκευής σε στάδια, από τα οποία μπορείτε να φτάσετε στο σημείο εκκίνησης ή στο τέλος με τον ίδιο αριθμό βημάτων. Στο TIR, η απόφαση αρχίζει στο τέλος, και παρόλο που στην περίπτωσή μας η αρχή και το τέλος δεν διακρίνονται, σύμφωνα με την παράδοση TIR, η απόφαση αρχίζει στο τέλος. Εξετάστε τη μετάβαση ενός σταδίου σε ένα σημείο. Επιπλέον, δεν μας ενδιαφέρει καθόλου η προϊστορία του κινήματος, δηλ. πώς φτάσαμε στη σκηνή, αλλά αν πετύχουμε τον πόντο ή, τότε μπορούμε να φτάσουμε στο σημείο σε ένα βήμα με κόστος 8 από τον πόντο ή 9 από τον πόντο. Βάζουμε αυτά τα κόστη στους κατάλληλους κύκλους. Δεν υπάρχουν άλλες τροχιές από στάδιο σε σημείο.

Ας πάμε ένα βήμα πίσω στη σκηνή και ας αναλύσουμε τις τροχιές κατά τις οποίες ένα σημείο μπορεί να φτάσει κανείς σε δύο βήματα από σημείο σε στάδιο μπορεί να φτάσει με μοναδικό τρόπο και ένα σημείο σε δύο βήματα μπορεί να φτάσει σε μια μόνο τροχιά και το κόστος αυτού του ιστότοπου είναι 8 νομισματικές μονάδες. Και από σημείο σε στάδιο μπορείς να φτάσεις εκεί με τον μόνο τρόπο και το κόστος αυτού του οικοπέδου είναι 25 μονάδες. Και μπορείτε να πάτε από σημείο σε στάδιο με δύο τρόπους (κόστος 10 μονάδες χρημάτων) και (κόστος 11 μονάδες χρημάτων). Και εδώ στη σκηνή (και όχι σε ολόκληρη την τροχιά) είναι πολύ εύκολο να επιλέξετε τη βέλτιστη διαδρομή () και να απορρίψετε το απρόοπτο (). Σε αυτή την περίπτωση, δεν απορρίπτεται μόνο η απρόβλεπτη διαδρομή, αλλά και όλες οι εξερχόμενες τροχιές από το σημείο και συμπεριλαμβανομένου του τμήματος k. Βάλτε σε κύκλο το μικρότερο κόστος της διαδρομής, μονάδες μονάδας.

Συνεχίζοντας την κατανοητή κίνηση και κόβοντας απρόβλεπτες τροχιές, φτάνουμε στο σημείο από το οποίο υπάρχουν δύο μονοπάτια για τη σκηνή και, κόβοντας τη μη βέλτιστη διαδρομή, επιλέγουμε την καλύτερη, που κοστίζει 4 μονάδες.

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

Είναι σαφές ότι απορρίπτοντας απρόβλεπτα μικρά τμήματα μεταξύ των σταδίων, έτσι, χωρίς να το κάνουμε αυτό άμεσα, απορρίπτουμε όλες τις μη βέλτιστες τροχιές που περιλαμβάνουν αυτό το απορριφθέν τμήμα, δηλ. η αποτελεσματικότητα της επιλογής της βέλτιστης τροχιάς είναι πολύ υψηλή.

Ας στραφούμε τώρα στο έκτο τυπικό πρόβλημα ελέγχου, δηλ. σε ένα δυναμικό πρόβλημα στο οποίο το αντικείμενο ελέγχου χαρακτηρίζεται από την εξίσωση .

Και -διάνυσμα συντεταγμένων κατάστασης

- διάνυσμα ελέγχου

Ας είναι και απαιτείται η ελαχιστοποίηση του ολοκληρώματος

Το TIR βασίζεται στην αρχή της βελτιστοποίησης. Αυτή η αρχή διατυπώθηκε από τον R. Bellman για ένα ευρύ φάσμα συστημάτων, η μελλοντική συμπεριφορά των οποίων καθορίζεται πλήρως από την κατάστασή τους στο παρόν. Επομένως, δεν εξαρτάται από τη φύση της «προϊστορίας» τους, δηλ. τη συμπεριφορά του συστήματος στο παρελθόν, εφόσον το σύστημα βρίσκεται επί του παρόντος σε αυτήν την κατάσταση. Για παράδειγμα, θεωρήστε τη βέλτιστη τροχιά στον διαστατικό χώρο φάσης με τις αρχικές και τελικές τιμές του διανύσματος ίσες στο και στο.

Ας δοθεί η αρχική συνθήκη, η τιμή, σε γενικές γραμμές, δεν είναι γνωστή.

Ας σημειώσουμε κάποιο ενδιάμεσο σημείο, τροχιά που αντιστοιχεί, όπου θα καλούμε το τμήμα τροχιάς από το πρώτο και από το προς το δεύτερο.

Το δεύτερο τμήμα αντιστοιχεί στο τμήμα του ολοκληρώματος (1) ίσο με

Το δεύτερο τμήμα της τροχιάς μπορεί επίσης να θεωρηθεί ως ανεξάρτητη τροχιά. Θα είναι βέλτιστο εάν το ολοκλήρωμα που αντιστοιχεί σε αυτό είναι ελάχιστο. Η αρχή της βελτιστοποίησης μπορεί να διατυπωθεί ως εξής:

Αυτό σημαίνει ότι στην περίπτωση που η αρχική κατάσταση του συστήματος είναι, και η αρχική χρονική στιγμή, δεν εξαρτάται από το πώς το σύστημα έφτασε σε αυτήν την κατάσταση. Η βέλτιστη μεταγενέστερη κίνησή του θα είναι η τροχιά 2. Πράγματι, ας ισχύει το αντίθετο - τότε το κριτήριο (1), που λαμβάνεται υπόψη για το χρονικό διάστημα από έως, θα είναι το μικρότερο όχι για την τροχιά 2, αλλά για κάποια άλλη τροχιά που εξέρχεται από το σημείο και φαίνεται από τη διακεκομμένη γραμμή στο Σχ. 2 ... Αλλά σε αυτήν την περίπτωση θα ήταν δυνατό να οικοδομήσουμε μια "καλύτερη" τροχιά από την τροχιά 1-2, και για το αρχικό πρόβλημα, πρέπει απλώς να επιλέξετε ένα χειριστήριο έτσι ώστε η περιγραφόμενη τροχιά να είναι 1 και μετά. Εν τω μεταξύ, προχωράμε από την υπόθεση ότι η τροχιά 1-2 είναι η βέλτιστη. Η αντίφαση αποδεικνύει την αδυναμία ύπαρξης μιας τροχιάς που παρέχει μικρότερη τιμή από την τροχιά 2. Και έτσι, η τροχιά 2 είναι βέλτιστη.

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

Η αρχή της βελτιστότητας φαίνεται σχεδόν ασήμαντη και, με την πρώτη ματιά, μια δήλωση φτωχή σε περιεχόμενο. Ωστόσο, μπορεί κανείς, όπως έδειξε ο Bellman, να συμπεράνει μεθοδικά απαραίτητη προϋπόθεσηγια τη βέλτιστη τροχιά, η οποία δεν είναι καθόλου ασήμαντη. Στην πραγματικότητα, η αρχή της βελτιστοποίησης δεν είναι τόσο ασήμαντη όσο μπορεί να φαίνεται στην αρχή. Αυτό είναι εμφανές τουλάχιστον από το γεγονός ότι η δήλωση, η οποία φαίνεται να είναι η γενίκευσή της: "Οποιοδήποτε τμήμα της βέλτιστης τροχιάς είναι η βέλτιστη τροχιά" - γενικά μιλώντας, δεν είναι αλήθεια. Έτσι, για παράδειγμα, το πρώτο τμήμα της τροχιάς στο Σχ. 2 μπορεί να μην είναι το ίδιο η βέλτιστη τροχιά, δηλ. μην δίνετε ελάχιστο στο ολοκλήρωμα αν δοθούν μόνο οι αρχικές προϋποθέσεις.

Ας διευκρινίσουμε αυτή τη δήλωση με ένα στοιχειώδες παράδειγμα. Πώς κατανέμει ένας καλός δρομέας τη δύναμή του όταν τρέχει σε μεγάλες αποστάσεις; Ενεργεί σύμφωνα με την αρχή: Τρέξτε κάθε τμήμα όσο πιο γρήγορα μπορείτε; Όχι βέβαια, γιατί ένας δρομέας μπορεί να «ξεμείνει από ατμό» πολύ πριν φτάσει στον στόχο. Κατανέμοντας σοφά τους πόρους του σύμφωνα με τον απώτερο στόχο, ο δρομέας στην αρχή εξοικονομεί δυνάμεις, για να μην «σβήσει» στο τέλος της απόστασης. Ομοίως, οποιαδήποτε διαχείριση δεν πρέπει να είναι «κοντόφθαλμη», δεν πρέπει να καθοδηγείται μόνο από την επίτευξη του καλύτερου στιγμιαίου, τοπικού αποτελέσματος. Πρέπει να είναι «προνοητικό», να υποτάσσεται στον απώτερο σκοπό, δηλ. ελαχιστοποίηση της λειτουργικής (1) σε όλο το διάστημα από έως. Μόνο εάν καθοριστεί το τελικό σημείο του πρώτου τμήματος στο, το πρώτο τμήμα είναι και το ίδιο το βέλτιστο μονοπάτι.

Μια άλλη διατύπωση της αρχής της βελτιστοποίησης μπορεί να δοθεί:

Η ισοδυναμία αυτής της διατύπωσης και της προηγούμενης διατύπωσης είναι προφανής αν κατανοήσουμε από την «ιστορία» του συστήματος εκείνη την τροχιά 1 κατά μήκος της οποίας το αντιπροσωπευτικό σημείο έφτασε στη θέση (Εικ. 2). Η κατάσταση του συστήματος τη δεδομένη χρονική στιγμή νοείται ως σε αυτήν την περίπτωσηακριβώς η κατάσταση που αντιστοιχεί στο σημείο στο.

Ας εξηγήσουμε τη μέθοδο συλλογιστικής του Bellman απλή αρχήδιαχειριζόμενο αντικείμενο με έλεγχο

.

Πού είναι η μόνη συντεταγμένη του συστήματος:

Η μόνη ελεγχόμενη πρόσκρουση, περιορισμένη σε μια συγκεκριμένη περιοχή.

Ας δοθεί η αρχική συνθήκη. Ας υποθέσουμε ότι απαιτείται να βρεθεί ο νόμος ελέγχου για το ελάχιστο ολοκλήρωμα

όπου για ευκολία παίρνουμε χρόνο ίσο με μηδέν, δηλ. ; Η τιμή θα θεωρηθεί ότι είναι σταθερή για λόγους απλότητας.

Καταρχήν διακριτοποιούμε το πρόβλημα, δηλ. που προσεγγίζεται με την τιμή ενός συνεχούς συστήματος είναι διακριτό-συνεχές. Οι λόγοι για αυτό είναι οι εξής: πρώτον, η διακριτοποίηση είναι ένα αναπόφευκτο στάδιο στην προετοιμασία ενός προβλήματος για την επίλυσή του σε υπολογιστή.

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

Διαιρούμε το διάστημα σε ίσα τμήματα μικρού μήκους και θα λάβουμε υπόψη μόνο διακριτές τιμές και σε χρονικές στιγμές. Τότε η διαφορική εξίσωση (27) του αντικειμένου μπορεί περίπου να αντικατασταθεί από την εξίσωση σε πεπερασμένες διαφορές

Η αρχική συνθήκη παραμένει η ίδια

Το διάστημα (28) αντικαθίσταται περίπου από το άθροισμα

Το καθήκον τώρα είναι να προσδιοριστεί η ακολουθία των διακριτών τιμών της ενέργειας ελέγχου, δηλ. Τιμές που ελαχιστοποιούν το άθροισμα (32) υπό τις συνθήκες (4), (30) και (31) που επιβάλλονται στο σύστημα με αυτόν τον τρόπο, απαιτείται να βρεθεί το ελάχιστο μιας σύνθετης συνάρτησης πολλών μεταβλητών. Ωστόσο, το MPE καθιστά δυνατή τη μείωση αυτής της λειτουργίας σε μια ακολουθία ελαχιστοποιήσεων πολύ περισσότερο απλές λειτουργίεςμία μεταβλητή.

Για την επίλυση του προβλήματος χρησιμοποιείται μια τεχνική, η οποία συνίσταται σε μια «κατανοητή» κίνηση για το τέλος της διαδικασίας, δηλ. από τη στιγμή μέχρι την αρχή του. Ας υποθέσουμε πρώτα ότι η στιγμή ... Όλες οι αξίες, εκτός από την τελευταία, έχουν ήδη πραγματοποιηθεί με κάποιο τρόπο, και κάποια αξία που αντιστοιχεί στη στιγμή ... Σύμφωνα με την αρχή της βελτιστοποίησης, ο αντίκτυπος δεν εξαρτάται από την «προϊστορία» του συστήματος και καθορίζεται μόνο από την κατάσταση και τον σκοπό της διαχείρισης.

Εξετάστε το τελευταίο τμήμα της τροχιάς από πριν . Η ποσότητα επηρεάζει μόνο τους όρους του αθροίσματος (32) που σχετίζονται με αυτό το τμήμα.

Ας υποδηλώσουμε το άθροισμα αυτών των όρων μέχρι.

από το (30) λαμβάνουμε

Επομένως, εξαρτάται επίσης από. Εύρημα επιτρεπόμενη τιμήικανοποιώντας (4) και ελαχιστοποιώντας την τιμή. Ας υποδηλώσουμε την ελάχιστη τιμή που βρέθηκε με. Αυτή η ποσότητα εξαρτάται προφανώς από την κατάσταση του συστήματος εκείνοι. στην αξία που περιλαμβάνεται στα (33) και (34). Έτσι

Ας δώσουμε προσοχή στο γεγονός ότι για να προσδιοριστεί είναι απαραίτητο να πραγματοποιηθεί ελαχιστοποίηση μόνο σε μία μεταβλητή απλής έκφρασης (33) (αντί ελαχιστοποίησης σε πολλές μεταβλητές) σύνθετης έκφρασης (32), έχοντας πραγματοποιήσει αυτή τη διαδικασία, λαμβάνουμε με τη μορφή συναρτήσεων από? αυτή η λειτουργία θα πρέπει να απομνημονεύεται, για παράδειγμα, σε κάποια συσκευή μνήμης κατά τον υπολογισμό σε υπολογιστή) κατά τη μετάβαση στα επόμενα στάδια της λύσης.

Για να επιλέξετε τη βέλτιστη λύση κατά την εκτέλεση εργασιών προγραμματισμού, μερικές φορές είναι απαραίτητο να επαναλάβετε ένας μεγάλος αριθμός απόσυνδυασμούς δεδομένων που φορτώνουν τη μνήμη προσωπικός υπολογιστής... Τέτοιες μέθοδοι περιλαμβάνουν, για παράδειγμα, τη μέθοδο προγραμματισμού «διαίρει και βασίλευε». Σε αυτή την περίπτωση, ο αλγόριθμος προβλέπει τη διαίρεση της εργασίας σε ξεχωριστές μικρές υποεργασίες. Αυτή η μέθοδος χρησιμοποιείται μόνο σε περιπτώσεις όπου οι μικρές δευτερεύουσες εργασίες είναι ανεξάρτητες μεταξύ τους. Προκειμένου να αποφευχθεί η εκτέλεση επιπλέον δουλειάΣτην περίπτωση που οι υποεργασίες είναι αλληλεξαρτώμενες, χρησιμοποιείται η μέθοδος δυναμικού προγραμματισμού που πρότεινε ο Αμερικανός R. Bellman τη δεκαετία του '50.

Η ουσία της μεθόδου

Ο δυναμικός προγραμματισμός συνίσταται στον προσδιορισμό της βέλτιστης λύσης σε ένα πρόβλημα n-διαστάσεων, διαιρώντας το σε n ξεχωριστά στάδια. Κάθε ένα από αυτά είναι ένα υποπρόβλημα σε σχέση με μία μεταβλητή.

Το κύριο πλεονέκτημα αυτής της προσέγγισης μπορεί να θεωρηθεί ότι οι προγραμματιστές ασχολούνται με μονοδιάστατα προβλήματα βελτιστοποίησης δευτερευουσών εργασιών αντί για το πρόβλημα n-διάστάσεων και η λύση στο κύριο πρόβλημα πηγαίνει από κάτω προς τα πάνω.

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

Πρόβλημα δυναμικού προγραμματισμού βελτιστοποίησης. Ο συγγραφέας αυτής της μεθόδου R. Bellman διατύπωσε την αρχή της βελτιστοποίησης: όποια κι αν είναι η αρχική κατάσταση σε καθένα από τα βήματα και η λύση που καθορίστηκε σε αυτό το βήμα, όλα τα ακόλουθα επιλέγονται βέλτιστα σε σχέση με την κατάσταση που παίρνει το σύστημα στο τέλος του το βήμα.

Η μέθοδος βελτιώνει την απόδοση των εργασιών που επιλύονται απαριθμώντας επιλογές ή αναδρομές.

Κατασκευή του αλγορίθμου του προβλήματος

Ο δυναμικός προγραμματισμός προϋποθέτει την κατασκευή ενός τέτοιου αλγορίθμου εργασιών στον οποίο η εργασία χωρίζεται σε δύο ή περισσότερες υποεργασίες με τέτοιο τρόπο ώστε η λύση της να αποτελείται από τη βέλτιστη λύση όλων των δευτερευουσών εργασιών που περιλαμβάνονται σε αυτήν. Επιπλέον, καθίσταται απαραίτητο να γραφτεί μια σχέση επανάληψης και να υπολογιστεί η βέλτιστη τιμή της παραμέτρου για το πρόβλημα ως σύνολο.

Μερικές φορές, στο 3ο βήμα, χρειάζεται να απομνημονεύσετε επιπλέον κάποιες βοηθητικές πληροφορίες σχετικά με την πρόοδο κάθε δευτερεύουσας εργασίας. Αυτό ονομάζεται backtracking.

Εφαρμογή της μεθόδου

Ο δυναμικός προγραμματισμός χρησιμοποιείται όταν υπάρχουν δύο χαρακτηριστικά γνωρίσματα:

• βελτιστοποίηση για δευτερεύουσες εργασίες.
• την παρουσία επικαλυπτόμενων δευτερευουσών εργασιών στο πρόβλημα.

Όταν λύνετε χρησιμοποιώντας δυναμικό προγραμματισμό, πρέπει πρώτα να περιγράψετε τη δομή της λύσης. Το πρόβλημα βελτιστοποιείται εάν η λύση του προβλήματος αποτελείται από βέλτιστες λύσεις στα υποπροβλήματά του. Σε αυτή την περίπτωση, συνιστάται η χρήση δυναμικού προγραμματισμού.

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

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

Ο δυναμικός προγραμματισμός (γνωστός και ως «δυναμικός προγραμματισμός») είναι μια ειδική μέθοδος για τη βελτιστοποίηση των αποφάσεων, ειδικά προσαρμοσμένη στις λεγόμενες λειτουργίες «πολλαπλών βημάτων» (ή «πολλαπλών σταδίων»).

Ας φανταστούμε κάποια επέμβαση Ơ, αποσύνθεση σε μια σειρά από διαδοχικά "βήματα" ή "στάδια" - για παράδειγμα, η δραστηριότητα ενός κλάδου κατά τη διάρκεια ορισμένων οικονομικών ετών. ή την υπέρβαση πολλών λωρίδων αεράμυνας από ομάδα αεροσκαφών· ή μια ακολουθία δοκιμών που χρησιμοποιούνται για τον έλεγχο της συσκευής. Ορισμένες λειτουργίες (όπως οι παραπάνω) αναλύονται σε βήματα φυσικά. Σε ορισμένες, η διαίρεση πρέπει να εισαχθεί τεχνητά - για παράδειγμα, η διαδικασία καθοδήγησης ενός πυραύλου σε έναν στόχο μπορεί να χωριστεί υπό όρους σε στάδια, καθένα από τα οποία χρειάζεται κάποιο χρόνο.

Λοιπόν, σκεφτείτε τη λειτουργία Ơ που αποτελείται από ΤΒήματα (στάδια). Αφήστε την αποτελεσματικότητα της λειτουργίας να χαρακτηριστεί από κάποιον δείκτη W, που για συντομία θα ονομάσουμε «κέρδος» σε αυτό το κεφάλαιο. Ας υποθέσουμε ότι η ανταμοιβή Wγια ολόκληρη τη λειτουργία αποτελείται από τα κέρδη σε μεμονωμένα βήματα:

Οπου Wi - κέρδη σε Εγώ-ο βήμα.

Αν Wκατέχει μια τέτοια ιδιότητα, τότε ονομάζεται "προσθετικό κριτήριο".

Λειτουργία Ώχ Ώχγια την οποία μιλάμε είναι μια ελεγχόμενη διαδικασία, δηλαδή μπορούμε να επιλέξουμε κάποιες παραμέτρους που επηρεάζουν την πορεία και την έκβασή της και σε κάθε βήμα επιλέγεται κάποια απόφαση, στην οποία η ανταμοιβή σε αυτό το βήμα και η ανταμοιβή για τη λειτουργία στο σύνολό της. . Αυτή τη λύση θα την ονομάσουμε «βηματικός έλεγχος». Το σύνολο όλων των βημάτων ελέγχου αντιπροσωπεύει τον έλεγχο της λειτουργίας στο σύνολό της. Ας το χαρακτηρίσουμε με το γράμμα NS,και χειριστήρια βημάτων - γράμματα X1, x2, ...,Xm:

Χ = (Χ1 , Χ2 , …, Xm). (12.2)

Θα πρέπει να ληφθεί υπόψη ότι X1, x2, …., Xmστη γενική περίπτωση, όχι αριθμοί, αλλά ίσως διανύσματα, συναρτήσεις κ.λπ.

Απαιτείται να βρεθεί ένας τέτοιος έλεγχος NS,στο οποίο το κέρδος Wστρέφεται στο μέγιστο:

Αυτή η διαχείριση NS*,στο οποίο επιτυγχάνεται αυτό το μέγιστο, θα ονομάσουμε βέλτιστο έλεγχο. Αποτελείται από ένα σύνολο βέλτιστων βημάτων ελέγχου:

X * =(). (12.4)

Η μέγιστη απόδοση που επιτυγχάνεται με αυτόν τον έλεγχο, θα υποδηλώσουμε W *:

W * = {W(NS)} . (12.5)

Ο τύπος (12.5) έχει ως εξής: η τιμή W* υπάρχει το μέγιστο όλων W{ Χ} κάτω από διαφορετικούς ελέγχους NS(το μέγιστο λαμβάνεται για όλους τους ελέγχους NS,είναι δυνατό υπό αυτές τις συνθήκες). Μερικές φορές αυτό το τελευταίο καθορίζεται στον τύπο και γράφεται:

Ας εξετάσουμε πολλά παραδείγματα λειτουργιών πολλαπλών βημάτων και για καθεμία από αυτές θα εξηγήσουμε τι σημαίνει «έλεγχος» και τι είναι το «κέρδος» (δείκτης αποδοτικότητας) W.

1. Προγραμματίζονται οι δραστηριότητες ομίλου βιομηχανικών επιχειρήσεων Π1, Π2, ..., Π κγια μια περίοδο Τοικονομικά έτη ( Μ-αφήνω). Στην αρχή της περιόδου διατέθηκαν κάποια κονδύλια για την ανάπτυξη του ομίλου. Μ,που πρέπει να κατανεμηθεί με κάποιο τρόπο μεταξύ των επιχειρήσεων. Κατά τη διάρκεια των εργασιών της επιχείρησης, τα κεφάλαια που επενδύονται σε αυτήν δαπανώνται εν μέρει (αποσβένονται) και εν μέρει εξοικονομούνται και μπορούν και πάλι να αναδιανεμηθούν. Κάθε εταιρεία παράγει εισόδημα για το έτος, ανάλογα με το πόσα χρήματα επενδύονται σε αυτήν. Στην αρχή κάθε οικονομικού έτους, τα διαθέσιμα κεφάλαια αναδιανέμονται μεταξύ των επιχειρήσεων. Τίθεται το ερώτημα: πόσα χρήματα στην αρχή κάθε έτους πρέπει να διατίθενται σε κάθε επιχείρηση, ώστε το συνολικό εισόδημα για Τχρόνια ήταν το μέγιστο;

Κέρδη W(συνολικό εισόδημα) είναι το ποσό του εισοδήματος σε μεμονωμένα βήματα (έτη):

Και, ως εκ τούτου, έχει την ιδιότητα της προσθετικότητας.

Ελεγχος ΧΕγώεπί Εγώ-το βήμα είναι αυτό στην αρχή Εγώουχρόνια, ορισμένα κεφάλαια διατίθενται σε επιχειρήσεις NSΕγώ1 , NSΕγώ2 , …, NSΙκ (ο πρώτος δείκτης είναι ο αριθμός του βήματος, ο δεύτερος είναι ο αριθμός της επιχείρησης). Έτσι, το βήμα ελέγχου είναι ένα διάνυσμα με κσυστατικά:

Xi = (Xi1 , Xi2 , …, Xik). (12.7)

Φυσικά οι ποσότητες Wiστον τύπο (12.6) εξαρτώνται από το ύψος των κεφαλαίων που επενδύονται σε επιχειρήσεις.

Ελεγχος NSη όλη λειτουργία αποτελείται από ένα σύνολο όλων των βημάτων ελέγχου:

Χ = (Χ1 , Χ2 , …, Xm ). (12.8)

Απαιτείται να βρεθεί μια τέτοια κατανομή κεφαλαίων ανά επιχειρήσεις και ανά έτη (βέλτιστη διαχείριση Χ* ), στην οποία η ποσότητα Wστρέφεται στο μέγιστο.

Σε αυτό το παράδειγμα, τα βήματα ελέγχου ήταν διανύσματα. στα ακόλουθα παραδείγματα, θα είναι πιο απλά και θα εκφράζονται απλά σε αριθμούς.

2. Ο διαστημικός πύραυλος αποτελείται από Τστάδια, και η διαδικασία εκτόξευσής του σε τροχιά - από Μστάδια, στο τέλος καθενός από τα οποία γίνεται επαναφορά του επόμενου σταδίου. Για όλα τα βήματα (εξαιρουμένου του "χρήσιμου" βάρους της καμπίνας), κατανέμεται κάποιο συνολικό βάρος:

σολ = σολ1 + σολ2 + … + Gm,

Οπου Gi - το βάρος Εγώ-ο βήμα.

Σαν άποτέλεσμα Εγώστάδιο (καύση και ρίψη του 1ου σταδίου), ο πύραυλος λαμβάνει μια αύξηση στην ταχύτητα, ανάλογα με το βάρος αυτού του σταδίου και το συνολικό βάρος όλων των υπολοίπων, συν το βάρος της καμπίνας. Το ερώτημα είναι πώς θα κατανεμηθεί το βάρος σολμεταξύ των βημάτων έτσι ώστε η ταχύτητα του πυραύλου Vκατά την εκτόξευσή του σε τροχιά ήταν το μέγιστο;

Σε αυτήν την περίπτωση, ο δείκτης απόδοσης (κέρδος) θα είναι

V = (12.9)

Πού είναι το κέρδος (αύξηση ταχύτητας). Εγώ-ο βήμα. Ελεγχος NSείναι ένα σύνολο βαρών όλων των σταδίων Gi:

X = (Gi, Gi, …, Gm).

Βέλτιστος έλεγχος NS*θα είναι η κατανομή των βαρών στα βήματα στα οποία η ταχύτητα Vτο μέγιστο. Σε αυτό το παράδειγμα, ο έλεγχος βήματος είναι ένας αριθμός, δηλαδή το βάρος του δεδομένου βήματος.

3. Ο ιδιοκτήτης του αυτοκινήτου το χειρίζεται κατά τη διάρκεια Τχρόνια. Στην αρχή κάθε έτους, μπορεί να πάρει μία από τις τρεις αποφάσεις:

1) πουλήστε το αυτοκίνητο και αντικαταστήστε το με καινούργιο.

2) να το επισκευάσει και να συνεχίσει να λειτουργεί.

3) συνεχίστε να λειτουργεί χωρίς επισκευή.

Ο έλεγχος βημάτων είναι η επιλογή μιας από αυτές τις τρεις λύσεις. Δεν εκφράζονται άμεσα σε αριθμούς, αλλά μπορούν να αποδοθούν στο πρώτο αριθμητική αξία 1, δεύτερο 2, τρίτο 3. Ποιες αποφάσεις πρέπει να ληφθούν με την πάροδο των ετών (δηλαδή, πώς να εναλλάσσονται οι έλεγχοι 1, 2, 3) ώστε το συνολικό κόστος λειτουργίας, επισκευής και αγοράς νέων μηχανών να είναι ελάχιστο;

Ο δείκτης αποδοτικότητας (σε αυτήν την περίπτωση, δεν είναι "κέρδος", αλλά "απώλεια", αλλά δεν έχει σημασία) ισούται με

W = (12.10)

Οπου Wi - έξοδα σε Εγώ-το αυτί μου. Η αξία Wαπαιτείται να ελαχιστοποιηθεί.

Χ = (3, 3, 2, 2, 2, 1, 3, …),

Που σημαίνει: να λειτουργήσει το αυτοκίνητο χωρίς επισκευή για τα δύο πρώτα χρόνια, να το επισκευάσει για τα επόμενα τρία χρόνια, να το πουλήσει στην αρχή του έκτου έτους, να αγοράσει ένα καινούργιο, μετά να το λειτουργήσει ξανά χωρίς επισκευή κ.λπ. Οποιοδήποτε στοιχείο ελέγχου είναι ένα διάνυσμα (ένα σύνολο αριθμών):

NS = (J1 , J2 , …; Jm), (12.11)

Πού είναι καθένας από τους αριθμούς J1 , J2 , …, Jmέχει μία από τις τρεις τιμές: 1, 2 ή 3. Είναι απαραίτητο να επιλέξετε ένα σύνολο αριθμών (12.11), όπου η τιμή (12.10) είναι ελάχιστη.

4. Ένα τμήμα της σιδηροδρομικής γραμμής τοποθετείται μεταξύ των σημείων Α και Β (Εικ. 12.1). Το έδαφος είναι τραχύ, περιλαμβάνει δασώδεις εκτάσεις, λόφους, βάλτους, ένα ποτάμι, μέσω του οποίου πρέπει να χτιστεί μια γέφυρα. Απαιτείται η χάραξη του δρόμου από Α και Β,ώστε το συνολικό κόστος για την κατασκευή του χώρου να είναι ελάχιστο.

Σε αυτό το πρόβλημα, σε αντίθεση με τα τρία προηγούμενα, δεν υπάρχει φυσική διαίρεση σε βήματα: πρέπει να εισαχθεί τεχνητά, για το οποίο, για παράδειγμα, ένα τμήμα ΑΒχωρίζεται σε Τμέρη, σχεδιάστε ευθείες γραμμές μέσα από τα σημεία διαίρεσης, κάθετα AB,και θεωρήστε τη μετάβαση από μια τέτοια ευθεία σε μια άλλη ως «βήμα». Αν τα πλησιάσετε αρκετά κοντά το ένα στο άλλο, τότε μπορείτε να θεωρήσετε ότι το τμήμα της διαδρομής είναι ευθύ σε κάθε βήμα. Ενεργοποιήστε τον έλεγχο βήμαείναι η γωνία που σχηματίζει ένα τμήμα της διαδρομής με ευθεία γραμμή ΑΒ.Ο έλεγχος ολόκληρης της λειτουργίας αποτελείται από ένα σύνολο βημάτων ελέγχου:

X = ().

Απαιτείται η επιλογή τέτοιου (βέλτιστου) ελέγχου NS*, όπου το συνολικό κόστος για την κατασκευή όλων των τμημάτων είναι ελάχιστο:

W = => Ελάχ . (12.12)

Έτσι, εξετάσαμε μερικά παραδείγματα ερευνητικών εργασιών πολλαπλών βημάτων. Τώρα ας μιλήσουμε για το πώς μπορείτε να λύσετε αυτό το είδος προβλήματος;

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

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

Με την πρώτη ματιά, η ιδέα μπορεί να φαίνεται αρκετά ασήμαντη. Πράγματι, το οποίο φαίνεται να είναι πιο απλό:

Εάν είναι δύσκολο να βελτιστοποιήσετε τη λειτουργία στο σύνολό της, χωρίστε την σε μια σειρά βημάτων. Κάθε τέτοιο βήμα θα είναι μια ξεχωριστή, μικρή λειτουργία, η οποία δεν είναι πλέον δύσκολο να βελτιστοποιηθεί. Είναι απαραίτητο να επιλέξετε έναν τέτοιο έλεγχο σε αυτό το βήμα, έτσι ώστε η αποτελεσματικότητα αυτού του βήματος να μεγιστοποιηθεί. Δεν είναι?

Οχι, καθόλου! Ο δυναμικός προγραμματισμός δεν σημαίνει ότι κάθε βήμα βελτιστοποιείται χωριστά, ανεξάρτητα από τα άλλα. Αντίθετα, ο σταδιακός έλεγχος θα πρέπει να επιλέγεται διορατικά, λαμβάνοντας υπόψη όλες τις συνέπειές του στο μέλλον. Τι ωφελεί εάν επιλέξουμε σε αυτό το βήμα τη διαχείριση στην οποία η αποτελεσματικότητα αυτού του βήματος είναι μέγιστη, εάν αυτό το βήμα μας στερεί την ευκαιρία να κερδίσουμε καλά στα επόμενα βήματα;

Ας υποθέσουμε, για παράδειγμα, προγραμματίζεται η εργασία μιας ομάδας βιομηχανικών επιχειρήσεων, από τις οποίες ορισμένες ασχολούνται με την παραγωγή καταναλωτικών αγαθών και οι υπόλοιπες παράγουν μηχανές για αυτές. Το καθήκον της επιχείρησης είναι να πάρει για Τέτη ο μέγιστος όγκος παραγωγής καταναλωτικών αγαθών. Ας πούμε ότι προγραμματίζονται επενδύσεις κεφαλαίου για τον πρώτο χρόνο. Με βάση τα στενά συμφέροντα αυτού του βήματος (έτος), θα έπρεπε να επενδύσουμε όλα τα διαθέσιμα κεφάλαια στην παραγωγή καταναλωτικών αγαθών. Θα ήταν όμως σωστή μια τέτοια απόφαση από την άποψη της αποτελεσματικότητας της λειτουργίας συνολικά; Προφανώς όχι. Αυτή η απόφαση είναι σπάταλη, κοντόφθαλμη. Έχοντας υπόψη το μέλλον, είναι απαραίτητο να διατεθεί ένα συγκεκριμένο μερίδιο κεφαλαίων για την παραγωγή μηχανών. Από αυτό, ο όγκος της παραγωγής τον πρώτο χρόνο, φυσικά, θα μειωθεί, αλλά θα δημιουργηθούν προϋποθέσεις για την αύξησή της τα επόμενα χρόνια.

Ενα άλλο παράδειγμα. Ας υποθέσουμε ότι στο Πρόβλημα 4 (τοποθέτηση σιδηροδρομικής γραμμής από ΕΝΑ v V) θα μας παρασύρει η ιδέα να σπεύσουμε αμέσως προς την πιο εύκολη (φθηνή) κατεύθυνση. Τι ωφελεί η εξοικονόμηση στο πρώτο σκαλοπάτι, αν στο μέλλον θα μας οδηγήσει (κυριολεκτικά ή μεταφορικά) σε «βάλτο»;

Που σημαίνει, Όταν σχεδιάζετε μια λειτουργία πολλαπλών βημάτων, είναι απαραίτητο να επιλέξετε τον έλεγχο σε κάθε βήμα, λαμβάνοντας υπόψη όλες τις μελλοντικές συνέπειές του στα επόμενα βήματα.Διαχείριση σε Εγώ-Το βήμα επιλέγεται όχι για να μεγιστοποιηθεί η απόδοση σε αυτό το συγκεκριμένο βήμα, αλλά για να επιλεγεί το μέγιστο ποσό κερδών σε όλα τα βήματα που απομένουν μέχρι το τέλος συν αυτό.

Ωστόσο, υπάρχει μια εξαίρεση σε αυτόν τον κανόνα. Ανάμεσα σε όλα τα βήματα υπάρχει ένα που μπορεί να προγραμματιστεί απλά, χωρίς να κοιτάξει το μέλλον. Ποιο είναι αυτό το βήμα; Προφανώς το τελευταίο! Αυτό το βήμα, το μοναδικό από όλα, μπορεί να σχεδιαστεί έτσι ώστε, ως τέτοιο, να αποφέρει το μεγαλύτερο όφελος.

Επομένως, η διαδικασία δυναμικού προγραμματισμού συνήθως ξεδιπλώνεται από το τέλος στην αρχή: πρώτα απ 'όλα, σχεδιάζεται το τελευταίο, Μτο βήμα. Και πώς να το σχεδιάσουμε αν δεν ξέρουμε πώς τελείωσε η προτελευταία; Δηλαδή δεν γνωρίζουμε τις συνθήκες υπό τις οποίες προχωράμε στο τελευταίο βήμα;

Εδώ αρχίζει το πιο σημαντικό. Όταν σχεδιάζετε το τελευταίο βήμα, πρέπει να κάνετε διαφορετικές υποθέσεις σχετικά με το πώς τελείωσε το προτελευταίο, (Τ - 1) το βήμα, και για καθεμία από αυτές τις παραδοχές, βρείτε τον υπό όρους βέλτιστο έλεγχο Μ-ο βήμα («υπό όρους» γιατί επιλέγεται με βάση την προϋπόθεση ότι το προτελευταίο βήμα τελείωσε με το τάδε).

Ας υποθέσουμε ότι το κάναμε αυτό και για καθένα από τα πιθανά αποτελέσματα του προτελευταίου βήματος, γνωρίζουμε τον υπό όρους βέλτιστο έλεγχο και την αντίστοιχη υπό όρους βέλτιστη απόδοση Μ-ο βήμα. Πρόστιμο! Τώρα μπορούμε να βελτιστοποιήσουμε τον έλεγχο στο προτελευταίο, (Τ- 1) το βήμα. Και πάλι, θα κάνουμε όλες τις πιθανές υποθέσεις για το πώς τελείωσε το προηγούμενο, ( Μ- 2) το βήμα, και για καθεμία από αυτές τις παραδοχές βρίσκουμε έναν τέτοιο έλεγχο στο ( Μ— 1) το οο βήμα, στο οποίο η ανταμοιβή για τα δύο τελευταία βήματα (εκ των οποίων Μ-ο είναι ήδη βελτιστοποιημένο!) είναι μέγιστο. Έτσι θα βρούμε για κάθε αποτέλεσμα ( Μ- 2) - ενεργοποιήστε τον βέλτιστο έλεγχο υπό όρους (Τ - 1) το βήμα και η υπό όρους βέλτιστη απόδοση στα δύο τελευταία βήματα. Περαιτέρω, "προχωρώντας προς τα πίσω", βελτιστοποιούμε τον έλεγχο με ( Μ- 2) ο σκαλοπάτι κ.λπ., μέχρι να φτάσουμε στο πρώτο.

Ας υποθέσουμε ότι γνωρίζουμε όλους τους βέλτιστους ελέγχους υπό όρους και τις βέλτιστες υπό όρους αποδόσεις για ολόκληρη την «ουρά» της διαδικασίας (σε όλα τα βήματα, από το δεδομένο μέχρι το τέλος). Αυτό σημαίνει: ξέρουμε τι πρέπει να γίνει, πώς να διαχειριστούμε σε ένα δεδομένο βήμα και τι θα πάρουμε στην «ουρά» γι' αυτό, ανεξάρτητα από την κατάσταση στην οποία βρίσκεται η διαδικασία στην αρχή του βήματος. Τώρα μπορούμε να κατασκευάσουμε όχι βέλτιστο υπό όρους, αλλά απλώς βέλτιστο έλεγχο NS*και να βρείτε όχι την υπό όρους βέλτιστη, αλλά απλώς τη βέλτιστη απόδοση W*.

Πράγματι, ενημερώστε μας σε ποια κατάσταση μικρό0 υπήρχε ένα ελεγχόμενο σύστημα (αντικείμενο ελέγχου μικρό) στην αρχή του πρώτου βήματος. Τότε μπορούμε να επιλέξουμε τον βέλτιστο έλεγχο στο πρώτο βήμα. Εφαρμόζοντάς το, θα αλλάξουμε την κατάσταση του συστήματος σε κάποια νέα. σε αυτή την κατάσταση, φτάνουμε στο δεύτερο βήμα. Τότε γνωρίζουμε και τον υπό όρους βέλτιστο έλεγχο , το οποίο, στο τέλος του δεύτερου βήματος, μεταφέρει το σύστημα στο κράτος κ.ο.κ.. Όσο για τη βέλτιστη απόδοση W *για όλη τη λειτουργία, το ξέρουμε ήδη: στο κάτω-κάτω, στο πρώτο βήμα επιλέξαμε τον διευθυντή.

Έτσι, κατά τη διαδικασία βελτιστοποίησης του ελέγχου με τη μέθοδο του δυναμικού προγραμματισμού, η διαδικασία πολλαπλών βημάτων «περπατάται» δύο φορές: την πρώτη φορά - από το τέλος στην αρχή, με αποτέλεσμα βέλτιστοι έλεγχοι υπό όρους και βέλτιστες πληρωμές υπό όρους για τα υπόλοιπα Βρέθηκαν «ουρά» της διαδικασίας. τη δεύτερη φορά - από την αρχή μέχρι το τέλος, όταν το μόνο που έχουμε να κάνουμε είναι να «διαβάζουμε» ήδη προετοιμασμένες συστάσεις και να βρούμε τον βέλτιστο έλεγχο χωρίς όρους NS*,που αποτελείται από βέλτιστους ελέγχους βημάτων

Το πρώτο στάδιο - βελτιστοποίηση υπό όρους - είναι ασύγκριτα πιο δύσκολο και χρονοβόρο από το δεύτερο. Το δεύτερο στάδιο δεν απαιτεί σχεδόν κανέναν πρόσθετο υπολογισμό.

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

Για το ζήτημα της οικονομίας και της διαχείρισης

Η οικονομία είναι ένα δυναμικό κοινωνικό σύστημα που διαμορφώνεται από ένα σύνολο στάσεων ατόμων απέναντι στο περιβάλλον, συμπεριλαμβανομένου του δικού τους είδους, το οποίο καθορίζει και διασφαλίζει τη χρήση, παραγωγή και κατανάλωση διαφόρων αγαθών που είναι απαραίτητα για την ύπαρξη και τη ζωή ενός ατόμου και ολόκληρης της κοινωνίας. (ορισμός που χρησιμοποιείται στο κοινωνικο-προσωπικό παράδειγμα)

Η οικονομία είναι δευτερεύουσα σε σχέση με την ανθρώπινη προσωπικότητα και την κοινωνία και αντανακλά έναν από τους τρόπους ύπαρξης ατόμων με ικανότητα και ικανότητα δημιουργίας (να μην συγχέεται με τη Δημιουργία), ως μεταμόρφωση του περιβάλλοντος προς την κατεύθυνση της επίτευξης του την άνεση της ύπαρξης και την ανάπτυξη (ή την υποβάθμιση) του εαυτού και των άλλων.
Στο επίκεντρο της οικονομίας και των οικονομικών σχέσεων βρίσκεται η ανθρώπινη προσωπικότητα και η κατευθυνόμενη δραστηριότητα της ζωής της, με όλα τα εγγενή της στοιχεία και χαρακτηριστικά που την κάνουν αυτό που είναι. Είναι οι υλικές και οικονομικές σχέσεις με το περιβάλλον και μεταξύ των ανθρώπων, που πραγματοποιούνται στην κοινωνία, που αποτελούν τη βάση της διαδικασίας που διασφαλίζει την ύπαρξη της κοινωνίας (η αφετηρία για τη ζωή ενός είδους ενός ανθρώπου, τόσο απλή λογική όσο και λογική ).
Από την άλλη πλευρά, οι οικονομικές, όπως και όλες οι άλλες σχέσεις, είναι αποτέλεσμα προηγούμενης κοινωνικής εμπειρίας που μεταδόθηκε από γενιά σε γενιά (αν χαθεί η εμπειρία, τότε επέρχεται κοινωνική και προσωπική υποβάθμιση, η οποία εκδηλώνεται στον αγώνα μεταξύ τους για τις δυνατότητες της ύπαρξης, που γίνεται μέσω του «ελεύθερου ανταγωνισμού», με άμεση βία).
Η βάση των οικονομικών σχέσεων είναι μια αρχή καθορισμού στόχων, ως ένα σύνολο προσωπικής και κοινωνικής ουσίας (συσσωρευμένη κοινωνική εμπειρία, που γίνεται αντιληπτή και μεταδίδεται από μια ορισμένη "γωνία θέασης") στην εστίασή τους στην ανάπτυξη ή την υποβάθμιση.
Η ίδια αρχή καθορισμού στόχων είναι μια εκδήλωση των φυσικών νόμων στην τρέχουσα πραγματικότητα και ο βαθμός κατανόησής τους από τους ανθρώπους αυτό το στάδιούπαρξη.
Η συνειδητοποίηση του προσανατολισμού προς την ανάπτυξη της προσωπικότητας δεν είναι δυνατή χωρίς τη διασφάλιση της ύπαρξης σε ένα επίπεδο που σας επιτρέπει να «ελευθερώσετε» κάποιο προσωπικό χρόνο από τη συνεχή αναζήτηση για «καθημερινό ψωμί», «μια στέγη πάνω από το κεφάλι σας», «τακτοποίηση ΖΩΗ". Ο ελεύθερος χρόνος είναι απαραίτητος όχι μόνο για την αποκατάσταση της ζωτικότητας, αλλά και για τη χρήση του για την κατανόηση του περιβάλλοντος (συσσώρευση νέας εμπειρίας) και την προσωπική εναρμόνιση (τόσο για τη διασφάλιση της σωματικής και ψυχικής υγείας, όσο και για τη φροντίδα των μελλοντικών γενεών).

Οι προϋποθέσεις (όρια) που είναι απαραίτητες για την ύπαρξη, ακολουθούν και τίθενται από τη ζωώδη αρχή του ανθρώπου, διαμορφώνοντας ένα εύρος αναγκών του ατόμου, όπως κάποιες δεδομένες, απαραίτητες για την ύπαρξη και τη ζωή του σε πραγματικές περιβαλλοντικές συνθήκες.
Φυσικά, αλλάζουν με το σχηματισμό και την ανάπτυξη της προσωπικότητας, συμπεριλαμβανομένων των συναισθηματικών και σωματικών της σχεδίων (αν περιορίζονται σε ένα άτομο και όχι σε μια κοινωνικά ανεπτυγμένη προσωπικότητα). Η παρουσία ενός διανοητικού σχεδίου κάνει ένα ζώο έξυπνο, αλλά δεν παρέχει νοημοσύνη. Η λογική είναι μια κοινωνική αρχή, που ορίζεται από μια ορισμένη ανατροφή και εκπαίδευση, ως μεταφορά ουσιαστικής (που όμως δεν συμβαίνει πάντα) εμπειρίας προηγούμενων γενεών και της επάρκειάς της στην πραγματικότητα.

Η σφαίρα των οικονομικών σχέσεων λειτουργεί κυρίως με υλικά αντικείμενα που διαθέτει ένα άτομο για μεταμόρφωση ή/και χρήση τους προκειμένου να εξασφαλίσει τη δική του ύπαρξη, άμεσα και έμμεσα μέσω της υπάρχουσας κοινωνίας.
Οι οικονομικές, όπως και κάθε άλλη σχέση και σχέση, προκύπτουν με βάση προσωπικές ανάγκες.
Αρχικά, είναι μια αντανάκλαση της ζωικής φύσης σε ένα άτομο (ανάγκες διατήρησης του σώματος σε λειτουργική κατάσταση).
Σε ένα ορισμένο επίπεδο κοινωνικής και προσωπικής ανάπτυξης, αποτελούν επίσης εκδήλωση της δημιουργικής (λογικής) αρχής, ως κοινωνικό συστατικό της προσωπικότητας (ορισμένος τρόπος σκέψης και επίγνωσης), παρέχοντάς της την ευκαιρία να επιτύχει κατευθυνόμενη ανάπτυξη την ύπαρξή της (συμπεριλαμβανομένης της οικονομικής δραστηριότητας).
Έτσι, ένα άτομο δρα τόσο ως αντικείμενο προικισμένο με δεδομένες ανάγκες ύπαρξης, όσο και ως υποκείμενο που συνειδητοποιεί την ανάγκη για δημιουργικότητα μέσω της ζωής σε αυτή τη σφαίρα σχέσεων.
Κατά συνέπεια, οι σχέσεις υποκειμένου-αντικειμένου και υποκειμένου-υποκειμένου αποτελούν τη βάση των οικονομικών σχέσεων, διακρίνοντάς τες από το σύνολο των κοινωνικών σχέσεων, στη βάση της υλικής (φυσικής) υποστήριξης για την ύπαρξη ενός ατόμου, κατ' αρχήν.

Από όσα ειπώθηκαν προκύπτει ότι σκοπός και κατεύθυνση τέτοιων σχέσεων είναι η ικανοποίηση των αναγκών του ατόμου, παρέχοντάς του μια ανεκτή ή άνετη ύπαρξη στο περιβάλλον. Αυτή η ύπαρξηπαρέχονται τόσο, με βάση τους πόρους του περιβάλλοντος, όσο και από τις προσπάθειες του ατόμου, ανεξάρτητα ή σε αλληλεπίδραση με την υπόλοιπη κοινωνία. Είναι επίσης δυνατό να χρησιμοποιηθούν τα αποτελέσματα των προσπαθειών της κοινωνίας για την κάλυψη προσωπικών αναγκών, χωρίς τη δική τους συμμετοχή στην επίτευξη αυτών των αποτελεσμάτων.
Επομένως, το κύριο ερώτημα οποιασδήποτε οικονομικής σχέσης είναι το ζήτημα του μέτρου των προσωπικών προσπαθειών και των αποτελεσμάτων τους, και των προσωπικών αποτελεσμάτων των προσπαθειών ολόκληρης της κοινωνίας.
Είναι το σύνολο των κυρίαρχων («καθιερωμένων») μέτρων που μιλά για σταθερότητα ή αστάθεια της οικονομίας ως συστήματος, και υποδεικνύει τους τόπους εφαρμογής των δυνάμεων και την κατεύθυνσή τους. Το συμπέρασμα που μπορεί να εξαχθεί από την ανάλυση των μέτρων (που λαμβάνουν χώρα ή προκύπτουν από τον τρέχοντα κοινωνικό καθορισμό) είναι τόσο η τρέχουσα κατάσταση της οικονομίας όσο και η πιθανότητα περαιτέρω ανάπτυξής της, συμμόρφωσης σε εξωτερική καταστροφή ή τάση αυτο- καταστροφή, και ποιες άλλες κοινωνικές διαδικασίες, ταυτόχρονα, μπορεί να επηρεαστούν. Αυτή η προσέγγιση καθιστά δυνατή τη μοντελοποίηση αποφάσεων (σε επίπεδο μακρο-διαχείρισης) στην ανάπτυξή τους και, με βάση πιθανά αποτελέσματα, αποτρέπει ανεπιθύμητες τάσεις στη δημόσια ζωή (χωρίς να περιμένουμε τις εμφανείς εκδηλώσεις τους) απορρίπτοντας λανθασμένες αποφάσεις.
Το κριτήριο, ως κατώτερο όριο, της «ορθότητας» της πορείας των διεργασιών στις οικονομικές σχέσεις υπό τις παρούσες συνθήκες, είναι η προσωπική ικανοποίηση στο επίπεδο των φυσικών (ενστικτωδώς βασισμένων) αναγκών του οργανισμού, που αντικατοπτρίζει τη ζωώδη φύση του ανθρώπου. όλα τα μέλη μιας συγκεκριμένης κοινωνίας. Αυτό αντανακλά τη συμμόρφωση του φυσικού προορισμού που καθορίζει την ύπαρξη του ζωικού κόσμου.
Το κριτήριο (ακριβέστερα, το σύνολο των κριτηρίων), που αντικατοπτρίζει το ανώτατο όριο (α), καθορίζεται από το επίπεδο προσωπικής ανάπτυξης ενός ατόμου που, σε ένα δεδομένο σύστημα σχέσεων, μπορεί να χρησιμοποιήσει πλήρως τις δικές του ικανότητες (ταλέντα, δεξιότητες , γνώση) προς όφελος της κοινωνίας και του ίδιου προσωπικά. Η υλοποίηση της κοινωνικής λειτουργίας του ατόμου προς την κατεύθυνση της υποβάθμισης της κοινωνίας, υποδηλώνει την ανισορροπία του συστήματος προς την κατεύθυνση της καταστροφής του, με την υποβάθμιση των εισερχόμενων στοιχείων του, δηλ. τελικά - στην εξαφάνιση του είδους του Homo sapiens.
Από αυτή την άποψη, η λειτουργία ρόλου του συστήματος των υφιστάμενων σχέσεων και η αλλαγή του είναι καθοριστική και το άτομο που το αντιλαμβάνεται είναι υποδεέστερο. Η ανεπάρκεια (μέτρο ασυμφωνίας) μεταξύ της προσωπικότητας και του λειτουργικού κοινωνικού ρόλου που «υπαγορεύεται» από το σύστημα μπορεί να είναι θετική και αρνητική — εδώ εκδηλώνεται ο ρόλος του ατόμου στην ιστορία.
Με τη γενική θετικότητα της τρέχουσας κοινωνικής δομής, η ασυμφωνία συνήθως φέρει έναν αρνητικό, διαφορετικά, είναι ένας θετικός παράγοντας (που φέρει ένα στοιχείο της αρχής ελέγχου, ενσωματωμένο στο ενεργό στοιχείο της προσωπικής ζωής, σε έναν επιπλέον μετασχηματισμό προς θετική κατεύθυνση )
Με τη γενική αρνητικότητα της τρέχουσας κοινωνικής δομής, η απόκλιση μπορεί να είναι θετική (λόγω της θετικότητας της προσωπικής αρχής, εάν η εφαρμογή της είναι καταρχήν δυνατή), διαφορετικά, είναι επιβαρυντικός αρνητικός παράγοντας (που φέρει στοιχείο της αρχής που διέπει εγγενές στο ενεργό συστατικό της προσωπικής ζωής, σε μια ακόμη μεγαλύτερη κατωτερότητα προς την κατεύθυνση της περαιτέρω υποβάθμισης του συστήματος, αν, φυσικά, δεν είναι ένας φυσικά καθορισμένος κοινωνικός κύκλος που οδηγεί σε μια ποιοτική αναδιοργάνωση, ιδίως στην απόσυρση, μια δεδομένη κοινωνία στο πλαίσιο της παγκόσμιας ακολουθίας ύπαρξης)

Με βάση τα παραπάνω, μιλώντας για τον έλεγχο, είναι απαραίτητο να διορθωθεί άμεσα ότι ο έλεγχος είναι πάντα μια δυναμική διαδικασία, η οποία ουσιαστικά διακρίνει τον έλεγχο από την απλή εκτέλεση μιας εντολής, η υλοποίηση της οποίας αντικατοπτρίζει ένα από τα βήματα (κύκλους) του ελεγχόμενου επεξεργάζομαι, διαδικασία. Εάν αυτά τα βήματα δεν συνδέονται με κάποιον γενικό αλγόριθμο ελέγχου (που περιλαμβάνεται σε αυτόν), τότε ο έλεγχος είναι διακοπτόμενος (ίσως και χαοτικός, ενστικτώδης) και, στην πραγματικότητα, δεν είναι έλεγχος, αντιπροσωπεύοντας ένα «χτύπημα κασσίτερου στον άνεμο».

Η διαχείριση της οικονομίας βρίσκεται στο φυσικό επίπεδο της ύπαρξης και συνδέεται με την αλληλεπίδραση των αντικειμένων και την προσωπική συμμετοχή σε αυτή την αλληλεπίδραση στο μέτρο του δυνατού και επιτρεπτού. Ο συνδυασμός του δυνατού και του επιτρεπτού σχηματίζει μια ορισμένη αλληλουχία (ως «διάδρομος») ελέγχου, σύμφωνα με την τρέχουσα αρχή καθορισμού στόχων του διαχειριστή υποκειμένου, η οποία βρίσκεται σε ορισμένες σχέσεις και αλληλεπιδράσεις, τόσο με αντικείμενα ελέγχου όσο και με θέματα ενεργούς δραστηριότητας για την εφαρμογή του γενικού αλγόριθμου ελέγχου.
Οι δυνατότητες του φυσικού επιπέδου συμπληρώνονται από τις υποκειμενικές ικανότητες λόγω της αρχής των κινήτρων στις δραστηριότητες των υποκειμένων που εφαρμόζουν τη διαχειριστική απόφαση.
Έτσι, η μετασχηματιστική (διαχειριστική, δημιουργική) αρχή - ως υποκειμενική-κοινωνική, ανήκει στο συναισθηματικό επίπεδο της ύπαρξης.
Σε αυτήν την περίπτωση, ολόκληρη η διαδικασία διαχείρισης βασίζεται στη γνώση, την κατανόηση και την πρόβλεψη της ανάπτυξης φυσικών (κυρίως φυσικών) διαδικασιών που καθορίζουν την ουσία των συνεχιζόμενων αλλαγών με τα αντικείμενα και την ίδια κατανόηση της υποκειμενικής συνιστώσας των κινητήριων δυνάμεων που χρησιμοποιούνται. για την ενεργό συμμετοχή τους σε αντικειμενικές διαδικασίες με όφελος για την κοινωνία και το άτομο σε μια παγκόσμια προοπτική (που καθορίζει τα κριτήρια για την εύρεση των «ορίων του διαδρόμου» για τη συμμόρφωσή του με τον επιλεγμένο, βάσει στόχων, φορέα δραστηριότητας ζωής).
Η δυναμική της διαχείρισης επιτυγχάνεται χρησιμοποιώντας την υποτακτική προσέγγιση στην ανάλυση του τι συμβαίνει και τη σύνδεσή του με τον καθορισμένο διάδρομο - και συνίσταται στις απαντήσεις στο σύνολο των πιθανών (ή αδύνατων) - και αν;
(η οποία, ειδικότερα, αντανακλά τη μέθοδο της γνώσης, συμπεριλαμβανομένης της ιστορικής - "η ιστορία, ως δεδομένη, δεν έχει υποτακτική διάθεση", αλλά η μέθοδος ιστορικής ανάλυσης μπορεί κάλλιστα να είναι "υποτακτική" - η αναζήτηση για ένας αλγόριθμος για την κοινωνική-προσωπική κατανόηση του γενικού, φυσικού-κοινωνικού, λειτουργικού που προσδιορίζει το ιστορικό δεδομένο).
Είναι το σύνολο των απαντήσεων που λαμβάνετε που σας επιτρέπει να εισάγετε μια διόρθωση σε κάθε βήμα (κύκλο) της ακολουθίας ελέγχου (και γνώσης), διατηρώντας τη διαδικασία στον αρχικά καθορισμένο διάδρομο.
Ο δυναμισμός της διαχείρισης αντανακλά το διανοητικό σχέδιο ύπαρξης και τις χρησιμοποιούμενες συνειδητές (σε αντίθεση με τη «μέθοδο πληκτρολόγησης» - τα προνόμια του συναισθηματικού σχεδίου) μεθόδους γνώσης του τι συμβαίνει.
Η «τελική χορδή» της διαχείρισης είναι η προνοητικότητα - η ερώτηση - τι θα γινόταν αν;
Το οποίο δεν βασίζεται στην τρέχουσα λογική της κατανόησης των εξελισσόμενων διεργασιών, αλλά αντανακλά την πιθανότητα «έρχονται στο μυαλό» σε αυτό που συμβαίνει (συνήθως ερμηνεύεται ως τυχαίο, αλλά ακριβώς λόγω προσωπικής παρανόησης και όχι ως αντανάκλαση μιας αντικειμενικά αναπτυσσόμενης φυσικής επεξεργάζομαι, διαδικασία). Οι απαντήσεις σε αυτό το ερώτημα «βρίσκονται» στο πνευματικό επίπεδο, το οποίο περιέχει το γενικό λειτουργικό της προσωπικής (και κοινωνικής) ανάπτυξης. Με μια ορισμένη προσωπική παιδεία στη χρήση του, καθίσταται δυνατή η λήψη απαντήσεων από το πεδίο της εκ των προτέρων (διαισθητικής) «γνώσης» αυτού που όχι μόνο συμβαίνει ήδη, αλλά και του μέλλοντος στο επίπεδο των υποκειμενικών δυνατοτήτων (από όπου η «μοίρα διατηρεί», αν και μόνο εκείνοι για τους οποίους αυτό το κανάλι είναι επαρκώς προσβάσιμο ώστε να έχει νόημα για ένα συγκεκριμένο άτομο).

Ως εκ τούτου προκύπτει ότι σε οποιαδήποτε κοινωνικό σύστημαυπάρχει μια βέλτιστη (γενικά, μεταβαλλόμενη με την πάροδο του χρόνου) αναλογία στοιχείων (συγκεκριμένα άτομα) και η θέση τους στο σύστημα (που προκαλεί την υλοποίηση λειτουργικών κοινωνικών ρόλων).
Το προκύπτον σύστημα κοινωνικών και προσωπικών σχέσεων (ιδίως των οικονομικών) είναι το κύριο αντικείμενο διαχείρισης, τόσο «αυθόρμητα» και με λογικό τρόπο.