Η δυαδικότητα στον γραμμικό προγραμματισμό. Συμμετρικά διπλά προβλήματα

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

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

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

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

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

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

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

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

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

Τα χαρακτηριστικά του μαθηματικού μοντέλου δυναμικού προγραμματισμού είναι τα εξής:

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

η αντικειμενική συνάρτηση (απόδοση) είναι προσθετική και ίση με το άθροισμα των αντικειμενικών συναρτήσεων κάθε βήματος:

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

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

Αυτό το μέγιστο (ή το ελάχιστο) καθορίζεται από όλα τα δυνατά κΚαι μικρόέλεγχος μεταβλητών τιμών Χ.

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

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

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

Η έννοια του «δυναμικού προγραμματισμού» χρησιμοποιήθηκε για πρώτη φορά τη δεκαετία του 1940 από τον Richard Bellman για να περιγράψει τη διαδικασία εύρεσης λύσης σε ένα πρόβλημα όπου η απάντηση σε ένα πρόβλημα μπορεί να ληφθεί μόνο αφού λυθεί ένα άλλο πρόβλημα που «προηγείται».
Έτσι, ο Αμερικανός μαθηματικός και ένας από τους κορυφαίους ειδικούς στον τομέα των μαθηματικών και τεχνολογία υπολογιστών — Ρίτσαρντ Ερνστ Μπέλμαν- έγινε ο πατέρας του δυναμικού προγραμματισμού.

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

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

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

Γενικά, για αρχή, άτυπος ορισμός του δυναμικού προγραμματισμούμπορεί να ακούγεται έτσι:

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

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

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

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

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

Μια άτυπη εξήγηση της ιδιότητας βελτιστοποίησης των υποπροβλημάτων μπορεί να αποδειχθεί χρησιμοποιώντας ένα διάγραμμα:
Υπάρχει ένα πρόβλημα που θέλουμε να λύσουμε χρησιμοποιώντας DP, π.χ. βρείτε κάποιο σχέδιο για να το λύσετε. Ας πούμε ότι αυτό το πρόβλημα είναι περίπλοκο και δεν μπορούμε να το λύσουμε αμέσως. Παίρνουμε ένα μικρό υποπρόβλημα και το λύνουμε πρώτα (για x1). Στη συνέχεια, χρησιμοποιώντας αυτή τη μικρή λύση x1, και χωρίς να αλλάξουμε τη δομή αυτής της λύσης, λύνουμε το επόμενο πρόβλημα με τα x1 και x2. Και τα λοιπά.

Ρύζι. 1.1. Μια άτυπη εξήγηση της ιδιότητας βελτιστοποίησης των υποπροβλημάτων

Η άτυπη εξήγηση συζητείται με περισσότερες λεπτομέρειες.

Παραδείγματα προβλημάτων που λύθηκαν με χρήση δυναμικού προγραμματισμού

Αρχικά, εξετάστε τα προβλήματα βελτιστοποίησης (εργασίες 1-5):

1. Διαδρομή βέλτιστου μήκους

Παράδειγμα:Υπάρχει κάποιος οδικός χάρτης που παρουσιάζεται με τη μορφή γραφήματος. Στόχος μας: να βγούμε από το σημείο ΕΝΑστο σημείο σι. Αυτό πρέπει να γίνει με τέτοιο τρόπο ώστε να ελαχιστοποιείται η απόσταση ή η σπατάλη καυσίμου.

Αντικειμενική λειτουργίαεδώ είναι η απόσταση από ΕΝΑπριν σι. Εκείνοι. στόχος μας είναι να ελαχιστοποιήσουμε την απόσταση.

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

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

2. Αντικατάσταση μηχανήματος (ελαχιστοποίηση του κόστους)

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

Αντικειμενική λειτουργία:ελαχιστοποίηση του κόστους (είτε το κόστος συντήρησης ενός παλιού αυτοκινήτου είτε η αγορά ενός νέου).

Μεταβλητή επιλογής:πάρτε μια απόφαση κάθε χρόνο να πουλήσετε το αυτοκίνητο ή να το κρατήσετε.

3. Ανταλλαγή χαρτοφυλακίου

Παράδειγμα:Παίζοντας στο χρηματιστήριο, αγορά μετοχών οποιωνδήποτε εταιρειών


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

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

4. Κατάρτιση σχεδίου βέλτιστης παραγωγής (logistics)

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


Αντικειμενική λειτουργία: μεγιστοποίηση κέρδους.

Μεταβλητή επιλογής:επιλέγοντας πόσες καρέκλες ή τραπέζια πρέπει να φτιαχτούν για να έχουν αρκετή εργασία.

5. Παιχνίδια (πιθανολογικά ή μη)

Παράδειγμα:Συμμετοχή σε διάφορα παιχνίδια


Αντικειμενική λειτουργία:μεγιστοποίηση της πιθανότητας νίκης ή μεγιστοποίηση της μέσης νίκης κ.λπ.

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

Τα προβλήματα 1 - 5 είναι παραδείγματα προβλημάτων βελτιστοποίησης.

Συνδυαστική:

6. Γραφήματα και δέντρα

Παράδειγμα:Το καθήκον είναι να αποφασίσετε πόσα δέντρα υπάρχουν που έχουν συγκεκριμένο αριθμό φύλλων. ή πόσα γραφήματα υπάρχουν για να λύσουν μια τέτοια εργασία κ.λπ.

7. Πρόβλημα ανταλλαγής νομισμάτων ή αριθμός τρόπων επιστροφής αλλαγών

Παράδειγμα:Υπάρχουν νομίσματα διαφορετικής ονομαστικής αξίας, με ποιους τρόπους μπορείτε να επιστρέψετε τα ρέστα.

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

Η έννοια του δυναμικού προγραμματισμού

Μια άτυπη εξήγηση της βελτιστοποίησης των υποπροβλημάτων DP.

Ας σκεφτούμε άτυποςιδέα DP.

Ετσι, ας πάρουμε ένα παράδειγμαμε εργοστάσιο κατασκευής επίπλων.

Για Για να επιτευχθεί ο στόχος της μεγιστοποίησης του κέρδους, είναι απαραίτητο να επιλυθούν πολλές δευτερεύουσες εργασίες:

• πόσες καρέκλες να παραχθούν - μεταβλητή X1,
• πόσοι πίνακες να παραχθούν - μεταβλητή X2,
• πόσοι εργαζόμενοι να προσληφθούν - μεταβλητή X3,
• ... Xn.

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

Ως εκ τούτου, η ΑΣ προτείνει τα εξής:

• Παίρνουμε μια δευτερεύουσα εργασία με τη μεταβλητή X1 και ξεχνάμε τις υπόλοιπες δευτερεύουσες εργασίες προς το παρόν.

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

• Αφού βρούμε τη βέλτιστη λύση για την πρώτη υποεργασία, παίρνουμε την δευτερεύουσα εργασία για δύο μεταβλητές X1 και X2 και τη λύνουμε χρησιμοποιώντας την ήδη βρεθεί λύση για την πρώτη υποεργασία.
• Λαμβάνουμε μια λύση για μια μεγαλύτερη υποεργασία, όπου εμφανίζονται οι μεταβλητές X1 και X2. Στη συνέχεια, χρησιμοποιώντας τη λύση που προέκυψε, αναλαμβάνουμε υποεργασίες που καλύπτουν τα Χ1, Χ2 και Χ3.
• Και έτσι συνεχίζουμε μέχρι να βρούμε μια λύση για όλο το γενικό πρόβλημα.

Επίσημη ιδέα του DP

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

Επιπλέον, μπορεί να προκύψει το εξής ερώτημα: για να βρούμε, για παράδειγμα, το ελάχιστο ή το μέγιστο, γιατί δεν βρίσκουμε την παράγωγο; ή μην χρησιμοποιείτε σετ La Grange ή άλλες μεθόδους της συσκευής μαθηματική ανάλυση? Γιατί χρειάζεστε το DP εάν έχετε μεγάλο οπλοστάσιο μέσων;

Το γεγονός είναι ότι:

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

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

Σπουδαίος:Για το λόγο αυτό, η διαίρεση μιας εργασίας σε δευτερεύουσες εργασίες και επίλυση αυτών των υποπροβλημάτων μόνο μία φορά (!), μειώνοντας έτσι τον αριθμό των συνολικών υπολογισμών - περισσότερο ο καλύτερος τρόπος, που είναι εγγενές στον δυναμικό προγραμματισμό

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

Ένα απλό παράδειγμα επίλυσης προβλημάτων με χρήση DP

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

Παράδειγμα:Είναι απαραίτητο να υπολογίσετε το άθροισμα των n αριθμών: 1 + 2 + 3 + ... + n

Ποια είναι η υποτιθέμενη «δυσκολία» αυτού του προβλήματος: ότι πρέπει να πάρετε έναν μεγάλο αριθμό αριθμών ταυτόχρονα και να πάρετε την απάντηση.

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

• Ας ξεκινήσουμε με το άθροισμα του πρώτου στοιχείου, δηλ. απλά πάρτε το πρώτο στοιχείο:
  F(1) = 1
• Τώρα, χρησιμοποιώντας τη λύση για το πρώτο στοιχείο, λύνουμε
  F(2) = F(1) + 2 = 1 + 2 = 3, δηλ. πρέπει να πάρετε το άθροισμα του πρώτου στοιχείου και να προσθέσετε το δεύτερο στοιχείο σε αυτό
• F(3) = F(2) + 3 = 6
• Κατ' αναλογία συνεχίζουμε και παίρνουμε λειτουργία στόχου:
  F(n) = F(n-1) + An

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

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

Ας δούμε ένα άλλο παράδειγμα.

Παράδειγμα:υπάρχει μια σκάλα n σκαλοπατιών, μπροστά από την οποία υπάρχει ένα άτομο που είναι πίσω 1 Το βήμα μπορεί είτε να ανέβει στο επόμενο βήμα είτε να πηδήξει πάνω από ένα σκαλί. Ερώτηση: με πόσους τρόπους μπορεί να φτάσει στο τελευταίο σκαλοπάτι;

Λύση:

Ας εξετάσουμε τα περισσότερα απλές επιλογές(υποεργασίες):

Ας δούμε ένα παράδειγμα βημάτων i

Πώς μπορούμε να φτάσουμε στο βήμα i:

1. από το βήμα i-1, και θα μπορούσαμε να φτάσουμε στο βήμα i-1 με τρόπους i-1
2. από το βήμα i-2, και θα μπορούσαμε να φτάσουμε στο βήμα i-2 με τρόπους i-2

Για παράδειγμα, πώς να φτάσετε 4ο βήμα:

Οτι., συνολικός αριθμός τρόπωνφτάστε στο βήμα i:
f(a i) = f(a i-1) + f(a i-2)

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

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

Ασκηση 1:εφαρμόστε ένα παράδειγμα για τα πρώτα δέκα βήματα (ουσιαστικά τους 10 πρώτους αριθμούς της σειράς Fibonacci), χρησιμοποιώντας την αναδρομή.

Συμπληρώστε τον κωδικό:

1 2 3 4 5 6 7 8 9 10 11 12 13

var c: ακέραιος ; διαδικασία getKolSposob(i, n: ακέραιος ) ; αρχίζω να γράφω (i+ n, " " ); Inc(c); αν ... τότε getKolSposob(...,...) τέλος ; αρχή c: = 1 ; getKolSposob(0, 1); τέλος.

var c:ακέραιος; διαδικασία getKolSposob(i,n: ακέραιος); start writeln(i+n," "); Inc(c); αν ... τότε getKolSposob(...,...) τέλος; έναρξη c:=1; getKolSposob(0,1); τέλος.

Εργασία 2:
Λύση 15ου τύπου εργασιών Ενιαίας Πολιτικής Εξέτασης (Γραφήματα. Εύρεση του αριθμού των μονοπατιών).

4.1. Αρχή βελτιστοποίησης

Σκεφτείτε το σύστημα

και λειτουργικότητα

(4.2)

που πρέπει να ελαχιστοποιηθεί. Το δεξί άκρο των συντεταγμένων φάσης είναι ελεύθερο.

Μαζί με αυτό το μεταβλητό πρόβλημα, θεωρούμε ένα βοηθητικό, όταν η διαδικασία εξετάζεται στο διάστημα
και η λειτουργικότητα ελαχιστοποιείται

. (4.3)

Ας βρεθεί πρώτα το ελάχιστο (4.2) και τον αντίστοιχο βέλτιστο έλεγχο (Εικ. 14α):

και μετά - ελάχιστο (4.3) και βέλτιστος έλεγχος (Εικ. 14β):

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

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

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

(4.6)

Ρύζι. 14 ΕΝΑΕικ.14 σι

Στη συνέχεια για το πρώτο πρόβλημα εισάγουμε τον έλεγχο

(4.7)

και να υπολογίσετε το λειτουργικό

Κατά την οδήγηση (4.7) λειτουργικό Το (4.2) παίρνει μικρότερη τιμή από το με (4.4). Αλλά έλεγχος είναι βέλτιστη. Επομένως, η υπόθεση (4.6) είναι εσφαλμένη.

Η μαντεψιά

έρχεται σε αντίθεση με τι
- διαχείριση που ελαχιστοποιεί
(4.3).

Έτσι, παραμένει αυτό

,

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

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

4.2. Βασική εξίσωση της μεθόδου δυναμικού προγραμματισμού

Ας εφαρμόσουμε την αρχή της βελτιστοποίησης στη λύση του μεταβλητού προβλήματος (4.1), (4.2). Για να το κάνετε αυτό, εξετάστε πρώτα τη λειτουργικότητα (4.3). Χαμηλότερη τιμήστις συνδέσεις (4.1) το συμβολίζουμε:

. (4.8)

Αν
- βέλτιστος έλεγχος, λοιπόν

.

Βέλτιστος έλεγχος
εξαρτάται από την αρχική κατάσταση
στη στιγμή
. Ως εκ τούτου, είναι συνάρτηση του Και :
, και από τον έλεγχο και οι παραλλαγές του λειτουργούν
δεν εξαρτάται. Καθορίζεται πλήρως από τις αξίες
.

Διάστημα
χωρίστε σε δύο διαστήματα
Και
και γράφουμε την έκφραση (4.8) με τη μορφή:

.

Σύμφωνα με την αρχή της βελτιστοποίησης, το τελευταίο τμήμα είναι επίσης βέλτιστο:

(4.9)

Ας υποδηλώσουμε:

, (4.10)

Οπου
- αύξηση του διανύσματος συντεταγμένων φάσης με την πάροδο του χρόνου
. Καθορίζεται σύμφωνα με τις εξισώσεις κίνησης (4.1). Αντικατάσταση
από (4.10) στην ισότητα (4.9), λαμβάνουμε:

.

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

.

Λαμβάνοντας υπ 'όψιν ότι

;

,

παίρνουμε τη βασική εξίσωση της μεθόδου δυναμικού προγραμματισμού:

(4.11)

Αυτή η σχέση αποτελείται από δύο δηλώσεις:

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

(4.12)

Εδώ
εξαρτάται από τον έλεγχο εξ ορισμού, τη συνάρτηση
δεν εξαρτάται από αυτόν. Ωστόσο, το παράγωγο εξαρτάται από τη διαχείριση. Αυτό μπορεί να επαληθευτεί εάν αντιπροσωπεύεται στη φόρμα

Και αντικαταστήστε σύμφωνα με το σύστημα (4.1):

.(4.13)

Αντικαθιστώντας το (4.13) στο (4.12) παίρνουμε την εξίσωση του R. Bellman:

. (4.14)

Αυτή είναι μια μερική διαφορική εξίσωση σε σχέση με
, το οποίο μετά την αντικατάσταση
γίνεται μη γραμμικό. Σύμφωνα με τον ορισμό (4.8) στο
πρέπει να πληρούται η τελική προϋπόθεση

.

Στην περίπτωση άπειρου διαστήματος στο
η διαδικασία πρέπει να είναι ασυμπτωτικά σταθερή, δηλ.
.

Στην περίπτωση που εξετάζεται η συνάρτηση Boltz

(4.15)

Η εξίσωση (4.12) παραμένει έγκυρη, η συνάρτηση vστη στιγμή
πρέπει να ικανοποιεί την προϋπόθεση

. (4.16)

4.3. Δύο βέλτιστα προβλήματα ελέγχου

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

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

. (4.17)

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

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

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

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

4.4. Το πρόβλημα του αναλυτικού σχεδιασμού των βέλτιστων ελεγκτών

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

(4.18)

Πίνακες
, διαστάσεις
Και
, κατά συνέπεια, έχουν γνωστές συναρτήσεις ως στοιχεία τους
.

Θεωρείται επίσης ότι η κατάσταση του συστήματος (4.18) σε κάθε χρονική στιγμή γνωστός.

Η τετραγωνική συνάρτηση Boltz θεωρείται ως κριτήριο βελτιστοποίησης

Οπου
- συμμετρικοί μη αρνητικοί ορισμένοι πίνακες,
- θετικός καθορισμένη μήτρα; *) - δείκτης μεταφοράς.

Απαιτείται η εύρεση του βέλτιστου (ελαχιστοποίηση της λειτουργικής 4.19) ελέγχου, που είναι συνάρτηση της τρέχουσας κατάστασης
.

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

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

. (4.20)

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

(4.21)

Οπου
- υπάρχει κάποια, ακόμη άγνωστη, τετραγωνική μορφή που, δυνάμει του (4.16), ικανοποιεί την τελική προϋπόθεση

. (4.22)

Έτσι, για γραμμικά συστήματαη εργασία καταλήγει στην εύρεση της συνάρτησης
. Διαφοροποιώντας το (4.21) λαμβάνοντας υπόψη το (4.18) λαμβάνουμε

Ελαχιστοποίηση (4.23) κατά
, παίρνουμε

(4.24)

Επειδή
, τότε ο έλεγχος (4.24) παρέχει στην πραγματικότητα ένα ελάχιστο στην έκφραση
.

Αντικαθιστώντας το (4.24) στο (4.23), παίρνουμε

Η τετραγωνική μορφή (4.25) ισούται με μηδέν για οποιαδήποτε
μόνο στην περίπτωση που ο πίνακας που τον σχηματίζει είναι ίσος με μηδέν. Έτσι, παίρνουμε την εξίσωση για τον προσδιορισμό του πίνακα

(2.26)

με οριακή συνθήκη (4.22).

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

από όπου, λαμβάνοντας υπόψη τη συμμετρία των πινάκων ακολουθεί ότι
.

Σημείωση 1. Στην περίπτωση που το σύστημα (4.18) είναι ακίνητο (μήτρες ΕΝΑΚαι σι – αριθμητικοί πίνακες), πίνακες - αριθμητικοί πίνακες,
(θεωρείται σταθερή κατάσταση). Μήτρα είναι επίσης αριθμητική και ικανοποιεί την αλγεβρική εξίσωση

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

4.5. Σύνθεση τοπικά βέλτιστου ελέγχου

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

Ας εξετάσουμε μια συνεχή ελεγχόμενη διαδικασία που περιγράφεται από ένα σύστημα διαφορικών εξισώσεων (4.18).

Ας δοθεί μια συνάρτηση (συνάρτηση).
εξαρτώμενο από τον παραμετρικό χρόνο και ορίζεται σε ένα σύνολο συναρτήσεων
Και
.

Πρέπει να βρούμε την εξίσωση
, ελαχιστοποίηση
, Οπου - αυτή τη στιγμήχρόνος. Αυτός ο έλεγχος ονομάζεται τοπικά βέλτιστος.

Ως κριτήριο βελτιστοποίησης θεωρούμε το λειτουργικό

μήτρα πληρούν τις ίδιες απαιτήσεις όπως στην παράγραφο 4.4.

Είναι εύκολο να δείξουμε ότι η τοπικά βέλτιστη εξίσωση
ικανοποιεί αναγκαστικά την προϋπόθεση

. (4.28)

Ας χρησιμοποιήσουμε αυτή τη συνθήκη.

Στη συνέχεια, διαφοροποιώντας το (4.27) δυνάμει του (4.18), βρίσκουμε μια έκφραση για τον προσδιορισμό της παραγώγου

από την κατάσταση
ας βρούμε τον τοπικό βέλτιστο έλεγχο

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

.

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

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

. (4.31)

Στη συνέχεια, αντικαθιστώντας το (4,30) σε (4,29), από το (4,31) βρίσκουμε

(4.32)

Από τη συνθήκη (4.32) προκύπτει ότι θα ικανοποιηθεί εάν ο πίνακας
θα καθοριστεί από την κατάσταση

Ας εξετάσουμε τώρα την ελεγχόμενη κίνηση στο τμήμα
, Οπου - κάποιο σταθερό χρονικό σημείο. Το απαιτούμε επίσης αυτή τη στιγμή συνάρτηση μήτρας
ικανοποίησε την τελική προϋπόθεση

(4.34)

Στη συνέχεια από σύγκριση των τύπων (4.24), (4.26), (4.22) και (4.30), (4.33), (4.34) προκύπτει ότι τοπικά βέλτιστος έλεγχος (4.30) σύμφωνα με το κριτήριο (4.27) με τον πίνακα
, που προσδιορίζεται από την εξίσωση (4.33) με συνθήκη (4.34) συμπίπτει με τον έλεγχο (4.24), βέλτιστη σύμφωνα με το τετραγωνικό κριτήριο (4.19) στο διάστημα
.

5. Βέλτιστος έλεγχος στοχαστικών συστημάτων υπό συνθήκες αβεβαιότητας.

5.1. Χαρακτηριστικά τυχαίων σημάτων

Το εγχειρίδιο χρησιμοποιεί στοχαστικές (τυχαίες) διαδικασίες και ακολουθίες ως μαθηματικά μοντέλα διαταραχών και σφαλμάτων μέτρησης.

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

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

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

Όπως είναι γνωστό, το πιο πλήρες χαρακτηριστικό μιας τυχαίας διαδικασίας είναι - νόμος κατανομής διαστάσεων

ή -διαστατική πυκνότητα κατανομής

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

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

Μαθηματική προσδοκία (μέση τιμή)

; (5.3)

Διακύμανση μιας τυχαίας διαδικασίας

Δεύτερη αρχική στιγμή

Οπου
- κεντραρισμένη τυχαία διαδικασία με μηδενική μαθηματική προσδοκία.

Τυπική απόκλιση

. (5.6)

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

. (5.7)

Αν η μαθηματική προσδοκία
Η τυχαία διαδικασία δεν εξαρτάται από το χρόνο και η συνάρτηση συσχέτισης είναι συνάρτηση ενός ορίσματος
, τότε μια τέτοια διαδικασία ονομάζεται ακίνητη με την ευρεία έννοια.

Εάν η πυκνότητα κατανομής έχει Gaussian χαρακτήρα, τότε μια τέτοια διαδικασία ονομάζεται Gaussian

.

Η διαδικασία Gauss προσδιορίζεται πλήρως καθορίζοντας τη μαθηματική προσδοκία
και συνάρτηση συσχέτισης
.

Ένα σημαντικό χαρακτηριστικό μιας στατικής τυχαίας διαδικασίας με ευρεία έννοια είναι η φασματική πυκνότητα
- πυκνότητα κατανομής διασποράς (ενέργειας) στις συχνότητες.

Φασματική Πυκνότητα
και συνάρτηση συσχέτισης
συνδεδεμένο με άμεσο και αντίστροφο μετασχηματισμό Fourier:

; (5.8)

. (5.9)

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

Μαζί με βαθμωτές τυχαίες διεργασίες, μπορούμε επίσης να εξετάσουμε διανυσματικές τυχαίες διαδικασίες:

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

Αναμενόμενη αξία :

; (5.11)

Πίνακας διασποράς
:

(5.12)

με στοιχεία

; (5.13)

Πίνακας συνδιακύμανσης
:

(5.14)

με στοιχεία

; (5.15)

Μήτρα

με στοιχεία

. (5.17)

Εδώ
σημαίνει μεταφορά.

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

Πίνακες
,
Και
έχουν τις ακόλουθες ιδιότητες:

; (5.18)

για όλα Και (5.I9)

Για μια στατική διανυσματική τυχαία διαδικασία
εισάγεται μήτρα φασματικές πυκνότητεςως μετασχηματισμός Fourier του πίνακα παραλλαγής
, δηλ.

. (5.21)

Μήτρα
έχει την εξής ιδιότητα:

(5.22)

5.2. Μαθηματική περιγραφή γραμμικών συστημάτων υπό τυχαίες διαταραχές.

Γενικά, η εξίσωση ενός ελεγχόμενου δυναμικού συστήματος μπορεί να γραφτεί ως εξής:

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

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

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

Σε αυτό εγχειρίδιοΘα ληφθούν υπόψη μόνο γραμμικά συστήματα.

Ας εξετάσουμε συστήματα που περιγράφονται με διαφορικές εξισώσεις.

Ας υποδηλώσουμε με

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

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

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

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

Σε ορισμένες περιπτώσεις, είναι βολικό να αναπαραστήσουμε τη λύση του συστήματος (5.24) σε ολοκληρωμένη μορφή μέσω του θεμελιώδους πίνακα λύσεων
, η οποία ικανοποιεί την ακόλουθη εξίσωση πίνακα:

(5.26)

Σε ολοκληρωμένη μορφή, η λύση του συστήματος (5.24), σύμφωνα με τον τύπο Cauchy, μπορεί να αναπαρασταθεί με την ακόλουθη μορφή:

(5.27)

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

Όσον αφορά το σύστημα (5.24), (5.25), κάνουμε τις ακόλουθες παραδοχές:

(5.28)

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

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

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

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

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

για (5.29)

Οπου - μια αλληλουχία χρονικών στιγμών, που δεν είναι απαραίτητα σε ίση απόσταση μεταξύ τους.

Αν μας ενδιαφέρει η κατάσταση του συστήματος μόνο σε διακριτές χρονικές στιγμές , τότε το συνεχές σύστημα (5.24) σε αυτές τις στιγμές, χρησιμοποιώντας τη σχέση (5.27), μπορεί να γραφτεί σε την παρακάτω φόρμα:

(5.30)

Λαμβάνοντας υπόψη το (5.29), ξαναγράφουμε τη σχέση (5.30) ως εξής:

(5.31)

Ο τρίτος όρος στη σχέση (5.3I) μπορεί να θεωρηθεί ως κάποια τυχαία ακολουθία. Στην περίπτωση που η τυχαία διαδικασία είναι τύπου λευκού θορύβου, τότε ισχύει η ακόλουθη σχέση:

,

Οπου
- καθαρά τυχαία ακολουθία.

Εισαγωγή ονομασιών

(5.32)

γράφουμε το σύστημα των εξισώσεων (5.31) με τη μορφή:

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

Η εξίσωση μέτρησης, επομένως, μπορεί να γραφτεί ως εξής:

Μερικές φορές το σύστημα (5.33) - (5.34) γράφεται με την ακόλουθη μορφή:

Όσον αφορά τα συστήματα (5.33), (5.34), θα υποθέσουμε ότι:

(5.37)

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

, (5.38)

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

(5.39)

παίρνουμε τις εξισώσεις κίνησης του αντικειμένου μέσα κανονική μορφή:

(5.40)

Για αυτό το σύστημα εξισώσεων ο θεμελιώδης πίνακας
αποτελείται από δύο διανυσματικές λύσεις στηλών στο ακόλουθο σύστημα εξισώσεων

με αρχικές συνθήκες

Από αυτό προκύπτει ότι η μήτρα
έχει τη μορφή:

(5.41)

Το ίδιο αποτέλεσμα προκύπτει αν αναζητήσουμε τον πίνακα
με τη μορφή σειράς:

Ας εξετάσουμε τη συμπεριφορά του συστήματος (5.40) σε τακτά χρονικά διαστήματα σε στιγμές , δηλ.
.

Με βάση τις σχέσεις (5.3I) - (5.33), υποθέτοντας ότι
συνεχώς στο διακριτό βήμα, λαμβάνουμε το ακόλουθο ισοδύναμο διακριτό σύστημα:

(5.43)

(5.44)

Στο μέλλον, πρέπει να αποκτήσετε εξάρτηση
όχι μόνο από Και
, αλλά από και όλα τα προηγούμενα
. Χρήση σχέσεων (5.33), για διάφορα μπορεί να γραφτεί:

Συνεχίζοντας τους αντίστοιχους υπολογισμούς, μπορούμε να λάβουμε τη σχέση

, (5.45)

πού είναι η μήτρα
ορίζεται ως εξής:

και
στο
.

Οι σχέσεις που προκύπτουν (5.45), (5.46) θα χρησιμοποιηθούν όταν Στατιστική ανάλυσηδιακριτά συστήματα.

5.3. Εξισώσεις ροπών για γραμμικά συστήματα

Ας εξετάσουμε πρώτα συνεχή συστήματα. Έστω οι εξισώσεις κίνησης να έχουν τη μορφή.

. (5.47)

Σχετικά με τις ενοχλητικές επιρροές
και αρχική κατάσταση θα υποθέσουμε ότι πληρούν τις προϋποθέσεις (5.28).

Κατά τη λήψη σχέσεων για τη μαθηματική προσδοκία της κατάστασης του συστήματος
Ας πάρουμε τη μέση εξίσωση (5,47):

Λαμβάνοντας υπόψη το (5.28), λαμβάνουμε:

. (5.48)

Με βάση τις (5.47), (5.48), την εξίσωση για την κεντραρισμένη συνιστώσα
έχει τη μορφή:

. (5.49)

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

(5.50)

Να υπολογίσετε τη μαθηματική προσδοκία
χρησιμοποιούμε τον τύπο Cauchy (5.27):

. (5.51)

Πολλαπλασιασμός της έκφρασης (5.51) στα δεξιά με
, με μέσο όρο λαμβάνοντας υπόψη το (5.28), λαμβάνουμε:

(5.52)

Λαμβάνοντας υπ 'όψιν ότι

, (5.53)

Η εξίσωση (5.50) θα πάρει τη μορφή.

με αρχική κατάσταση
.

Τώρα αφήστε τη συμπεριφορά του συστήματος να περιγραφεί από τη διακριτή εξίσωση

Θα υποθέσουμε ότι η αρχική συνθήκη και ενοχλητικές επιρροές
ικανοποιούν σχέσεις (5,37). Ας βρούμε τις εξισώσεις για τη μαθηματική προσδοκία και τον πίνακα διασποράς.

Με μέσο όρο (5,55) και λαμβάνοντας υπόψη το (5,37), παίρνουμε:

Εξίσωση για την κεντραρισμένη συνιστώσα
έχει τη μορφή:

Χρησιμοποιώντας τα (5.57) και (5.37), βρίσκουμε την εξίσωση για τον πίνακα διασποράς
:

(5.58)

Ας ορίσουμε τη μαθηματική προσδοκία
, χρησιμοποιώντας τη σχέση (5.45) και τις ιδιότητες (5.37):

(5.59)

Επίσης

.

Έτσι, η εξίσωση για τον προσδιορισμό του πίνακα είναι
έχει τη μορφή:

5.4. Το βέλτιστο πρόβλημα φιλτραρίσματος και η επίλυσή του με τη μέθοδο Kalman

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

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

Οπου
--διάνυσμα κατάστασης διαστάσεων,
--διάνυσμα διαστάσεων ενοχλητικών επιρροών,
Και
μήτρες αντίστοιχων διαστάσεων.

Ας είναι μετρήσιμο
-διάνυσμα διαστάσεων ορισμένων συνδυασμών συναρτήσεων καταστάσεων (5.25)

Οπου
- σφάλμα μέτρησης.

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

Μαθηματικά, το πρόβλημα του βέλτιστου φιλτραρίσματος τίθεται ως το πρόβλημα της εύρεσης μιας εκτίμησης
κατάσταση συστήματος (5.61)
με βάση τις διαθέσιμες πληροφορίες
.

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

(5.63)

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

Επειδή
, τότε θα υπάρχει πάντα ένα σφάλμα εκτίμησης

.

Στη συνέχεια, για να προσδιοριστούν οι απαιτούμενοι πίνακες
Και
μπορείτε να χρησιμοποιήσετε την συνθήκη της αμερόληπτης εκτίμησης

(5.64)

και η προϋπόθεση για τη βελτιστότητά του

Οπου
είναι ένας συμμετρικός θετικός καθορισμένος πίνακας.

Για να χρησιμοποιήσουμε τις συνθήκες (5.64) και (5.65), βρίσκουμε μια εξίσωση για το σφάλμα εκτίμησης. Αφαιρώντας το (5.63) από το (5.61) λαμβάνοντας υπόψη το (5.62), παίρνουμε

Αν το βάλουμε τώρα αυτό

τότε η εξίσωση για το σφάλμα εκτίμησης είναι
θα λάβει τη μορφή:

με αρχική κατάσταση

. (5.68)

Από (5.67), (5.68) προκύπτει ότι η προϋπόθεση για την αμερόληπτη εκτίμηση (5.64) θα ικανοποιηθεί εάν θέσουμε

. (5.69)

Για να το επαληθεύσουμε αυτό, αρκεί να λάβουμε τη μαθηματική προσδοκία από τις εκφράσεις (5.67), (5.68)

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

Απομένει να ορίσουμε τη μήτρα
από την προϋπόθεση του ελάχιστου κριτηρίου (5,65). Ας υποθέσουμε για απλότητα των υπολογισμών ότι
είναι λοιπόν ένας σταθερός πίνακας ταυτότητας

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

. (5.71)

Είναι εύκολο να δείξουμε ότι η ελαχιστοποίηση της παραγώγου του κριτηρίου παρέχει ένα ελάχιστο για το ίδιο το κριτήριο

Ας γράψουμε την έκφραση
, παραλείποντας χρόνο για απλότητα :

. (5.72)

Αντικαθιστώντας στην (5.72) την έκφραση για από (5.67) και την αντίστοιχη έκφραση για , παίρνουμε:

(5.73)

Θα βρούμε
, για την οποία γράφουμε την εξίσωση Cauchy για (5.67):

Οπου
- συνάρτηση μήτρας βάρους. Επειτα

Χρησιμοποιούμε την ιδιότητα της συνάρτησης δέλτα:

,

Αν έχει ένα κενό στο σημείο
.

Επειδή η

. (5.74)

Ομοίως μπορείτε να βρείτε
:

. (5.75)

Αντικατάσταση των παραστάσεων που προκύπτουν με
και αντίστοιχα μετατέθηκαν εκφράσεις για
στο (5.73) παίρνουμε:

Η ακόλουθη ταυτότητα μπορεί εύκολα να επαληθευτεί ανοίγοντας τις αγκύλες στη δεξιά πλευρά και χρησιμοποιώντας τη συμμετρία του πίνακα
:

Λαμβάνοντας υπόψη την ταυτότητα, ανάγουμε την εξίσωση (5.76) στη μορφή:

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

Στην περίπτωση αυτή, ο τελευταίος όρος στην εξίσωση (5.78) γίνεται μηδέν και η εξίσωση παίρνει τη μορφή

με αρχική τιμή
.

Έτσι, μπορούμε να γράψουμε την εξίσωση φίλτρου

Οι εξισώσεις (5.79), (5.80), (5.81) είναι οι εξισώσεις φίλτρου Kalman-Bucy.

Το σύστημα αξιολόγησης (φίλτρο) παρουσιάζεται σχηματικά στο Σχ. 16.

Πρέπει να σημειωθεί ότι η εξίσωση του φίλτρου και οι παράμετροί του δεν εξαρτώνται από τη μήτρα
, ωστόσο, το τελευταίο πρέπει να είναι θετικό οριστικό.

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

Ας γράψουμε τις εξισώσεις του στατικού φίλτρου Kalman με την ακόλουθη μορφή:

; (5.83)

Μία από τις συχνά χρησιμοποιούμενες μεθόδους για την επίλυση της εξίσωσης (5.84) (συνήθως χρησιμοποιώντας ψηφιακό υπολογιστή) είναι η επίλυση της μη στάσιμης εξίσωσης (5.80) με τις αντίστοιχες σταθερές τιμές των συντελεστών από τους οποίους οι πίνακες A, C, Q, Τα R συντίθενται και ένας αυθαίρετος μη αρνητικός καθορισμένος πίνακας αρχικών συνθηκών για στον τρέχοντα χρόνο έως ότου η λύση που προκύπτει φτάσει σε μια σταθερή τιμή σταθερής κατάστασης. Αυτή η τελική τιμή λαμβάνεται ως η επιθυμητή λύση της εξίσωσης (5.84). Αυτή η μέθοδος λύσης είναι βολική επειδή οι αλγόριθμοι για την επίλυση διαφορικών εξισώσεων είναι, κατά κανόνα, πιο αποτελεσματικοί από τους αλγόριθμους για την επίλυση μη γραμμικών αλγεβρικών εξισώσεων.

Σημείωση 1.

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

.

Σημείωση 2.

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

που μπορεί να αναπαρασταθεί ως (5.62)

Σημείωση 3.

Για ελεγχόμενα συστήματα που περιγράφονται από ένα σύνολο εξισώσεων

Η εξίσωση του φίλτρου μπορεί να εξαχθεί με παρόμοιο τρόπο. Σε αυτήν την περίπτωση, η εξίσωση φίλτρου θα έχει τη μορφή

πού είναι η μήτρα
, και τον πίνακα συσχέτισης
, όπως και πριν, βρίσκεται από την εξίσωση του πίνακα

με αρχική κατάσταση
.

ΜΕ Το σύστημα αξιολόγησης (φίλτρο) παρουσιάζεται σχηματικά στο Σχ. 17.

5.5. Σύνθεση τοπικά βέλτιστου ελέγχου γραμμικών στοχαστικών συστημάτων με πλήρη και ακριβή πληροφόρηση.

Αφήστε την ελεγχόμενη κίνηση υπό συνθήκες διαταραχής να περιγραφεί από ένα σύστημα εξισώσεων

Τυχαία διαδικασία
και αρχική κατάσταση θα υποθέσουμε ότι είναι ανεξάρτητα και έχουν ιδιότητες (5.28). Υποτίθεται ότι η συνθήκη
οποιαδήποτε στιγμή γνωστός. Ας ψάξουμε για έλεγχο
όπως μερικοί γραμμική συνάρτησητωρινή κατάσταση

. (5.88)

Τότε το πρόβλημα του προσδιορισμού τοπικά βέλτιστου ελέγχου περιορίζεται στην εύρεση
-μήτρες
. Βέλτιστη μήτρα
Θα ψάξουμε ανάμεσα σε πίνακες των οποίων τα στοιχεία είναι συνεχείς συναρτήσεις με τιμές από τον ανοιχτό τομέα.

Ως συνάρτηση που χαρακτηρίζει την ελεγχόμενη κίνηση, παίρνουμε τη μαθηματική προσδοκία του τοπικού συναρτητικού
(4.27)

.

Ας εισαγάγουμε τον πίνακα των ροπών συσχέτισης

. (5.89)

Χρησιμοποιώντας (5.88), (5.89) λειτουργικά μπορούμε
μετατροπή σε μορφή

(5.90)

Έτσι, η τιμή του κριτηρίου ποιότητας την τρέχουσα στιγμή καθορίζεται από τον πίνακα των ροπών συσχέτισης.

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

πού είναι η μήτρα

Σύμφωνα με το (5.54), η εξίσωση για τον πίνακα
θα μοιάζει

ή, λαμβάνοντας υπόψη (5.91),

(5.92)

Η αρχική προϋπόθεση είναι προφανώς

Από (5.92), (5.93) λαμβάνοντας υπόψη την υπόθεση ότι οι πίνακες είναι συμμετρικοί ,
Αμέσως προκύπτει ότι η μήτρα
είναι συμμετρικό, δηλ.
.

Έτσι, το πρόβλημα του προσδιορισμού του βέλτιστου ελέγχου έχει περιοριστεί στο πρόβλημα του προσδιορισμού της μήτρας
από την ελάχιστη προϋπόθεση
(5,90). Για να το βρούμε χρησιμοποιούμε την συνθήκη (4.28). Διαφοροποιώντας το (5,90) και λαμβάνοντας υπόψη το (5,92), παίρνουμε

Ας γράψουμε τα εξαρτήματα
, εξαρτάται από
:

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

.

Οπου
- αυθαίρετη μικρή παραλλαγή της συνάρτησης μήτρας
από την εν λόγω τάξη.

Αύξηση
, που προκαλείται από διακύμανση πίνακα
, θα μοιάζει

Τότε από το (5,94) προκύπτει ότι

Λόγω αυθαιρεσίας
και υποθέτοντας ότι ο πίνακας
όχι ιδιαίτερο, λόγω των συνθηκών
παίρνουμε μια εξίσωση για τον προσδιορισμό του βέλτιστου πίνακα

Βρέθηκε τιμή
προσφέρει πραγματικά το ελάχιστο
, από τη δεύτερη παραλλαγή

λόγω της βέβαιης θετικότητας του πίνακα
. Εδώ.

Συγκρίνοντας τα (5.88), (5.95) με (4.30), βλέπουμε ότι ο τοπικά βέλτιστος έλεγχος που βρέθηκε συμπίπτει πλήρως με τον τοπικά βέλτιστο έλεγχο για την ντετερμινιστική περίπτωση.

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

Παρόμοιο αποτέλεσμα προκύπτει και με το κριτήριο της δευτεροβάθμιας ποιότητας (4.19).

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

5.6. Σύνθεση τοπικά βέλτιστου ελέγχου γραμμικών στοχαστικών συστημάτων (θεώρημα διαχωρισμού).

Αφήστε την ελεγχόμενη κίνηση να περιγραφεί από την εξίσωση (5.87) και την εξίσωση μέτρησης – (5.62).

Ας εξετάσουμε το πρόβλημα της σύνθεσης που είναι βέλτιστο σύμφωνα με το κριτήριο

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

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

Μαζί με το σύστημα (5.87), θεωρούμε και το αντίστοιχο ανεξέλεγκτο σύστημα

με εξίσωση μέτρησης

Για το βοηθητικό σύστημα έχει λυθεί το πρόβλημα φιλτραρίσματος και η εκτίμηση
ικανοποιεί την εξίσωση

(5.98)

με αρχική κατάσταση

πού είναι η μήτρα
προσδιορίζεται από τις εξισώσεις (5.79), (5.80).

Από τις εξισώσεις (5.87) και (5.97) προκύπτει ότι

, (5.99)

Οπου
- θεμελιώδης πίνακας λύσεων συστημάτων (5.87).

Ψάχνουμε για έλεγχο που καθορίζεται τη στιγμή τιμές της διανυσματικής συνάρτησης
στο τμήμα
. Στη συνέχεια για κάθε υλοποίηση
επεξεργάζομαι, διαδικασία
έλεγχος
δέχεται συγκεκριμένο νόημα, δηλ. Ο έλεγχος είναι ένας ντετερμινιστικός τελεστής σε ένα διάνυσμα παρατηρήσεων. Να γιατί

(5.100)

Από (5.99) και (5.100) προκύπτει ότι

Ας βρούμε τώρα την εξίσωση που θα προσδιορίσουμε
. Για να γίνει αυτό, διαφοροποιώντας το (5.100), λαμβάνουμε

Λαμβάνοντας υπόψη το (5,98), βρίσκουμε

(5.101)

Στη συνέχεια, η εξίσωση φίλτρου θα γραφτεί τελικά στη μορφή (5.85)

με αρχική κατάσταση

, (5.103)

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

Θεώρημα διαχωρισμού.Ο τοπικός βέλτιστος έλεγχος του συστήματος (5.87) σύμφωνα με το κριτήριο (5.96) έχει τη μορφή:

Εδώ
είναι οι δεδομένοι πίνακες του τοπικού συναρτητικού, και
- λύση της διανυσματικής εξίσωσης (5.102) με την αρχική συνθήκη (5.103).

Απόδειξη.Ας εξετάσουμε το λειτουργικό (5.96). Λαμβάνοντας υπόψη ότι οι εκτιμήσεις
και σφάλμα εκτίμησης
δεν συσχετίζεται για όλους , η λειτουργική (5.96) μπορεί να αναπαρασταθεί ως

,

Από τότε
ούτε επηρεάζει
, ούτε
, τότε το πρόβλημα περιορίζεται στην ελαχιστοποίηση υπό προϋποθέσεις (5.102), (5.103). Σε αυτή την περίπτωση, η εκτίμηση είναι απολύτως παρατηρήσιμη.

Σκεφτείτε την έκφραση

Δεδομένου αυτού, δεν είναι δύσκολο να το δείξουμε

Έτσι, στην εξίσωση (5.102), η έκφραση
μπορεί να θεωρηθεί ως ισοδύναμος "λευκός θόρυβος" με πίνακα συσχέτισης
.

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

Η ενότητα Δυναμικός Προγραμματισμός αντιπροσωπεύεται από τους ακόλουθους αριθμομηχανές:

1. Πρόβλημα κατανομής επενδύσεων. Για την ανασυγκρότηση και τον εκσυγχρονισμό της παραγωγής σε τέσσερις επιχειρήσεις, διατίθενται μετρητά C = 80 den. μονάδες Για κάθε επιχείρηση, είναι γνωστή η πιθανή αύξηση f i (x) (i = 1, 4) στην παραγωγή, ανάλογα με το κατανεμημένο ποσό.

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

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

Ας σκεφτούμε γενική περιγραφήπροβλήματα δυναμικού προγραμματισμού.
Αφήστε τη διαδικασία λήψης αποφάσεων σε πολλά στάδια να αναλυθεί nβήματα. Ας συμβολίσουμε με ε 0 την αρχική κατάσταση του συστήματος, με ε 1, ε 2, … ε n– κατάσταση του συστήματος μετά το πρώτο, το δεύτερο, n-ο βήμα. Γενικά το κράτος ε κ– διάνυσμα (ε κ 1 , …, ε k s).
Διαχείρισησε μια διαδικασία πολλαπλών βημάτων, καλείται ένα σύνολο λύσεων (μεταβλητές ελέγχου). u k = (u k 1 , ..., u k r) γίνεται σε κάθε βήμα κκαι μεταφορά του συστήματος από το κράτος ε κ-1 = (ε κ- 1 1 , …, ε κ -1 μικρό) να δηλώσω ε κ = (ε κ 1 , …, ε k s).
Στις οικονομικές διαδικασίες, η διαχείριση συνίσταται στη διανομή και αναδιανομή των κεφαλαίων σε κάθε στάδιο. Για παράδειγμα, η παραγωγή προϊόντων από οποιαδήποτε επιχείρηση είναι μια ελεγχόμενη διαδικασία, αφού καθορίζεται από αλλαγές στη σύνθεση του εξοπλισμού, τον όγκο των προμηθειών των πρώτων υλών, το ποσό της χρηματοδότησης κ.λπ. Ένα σύνολο αποφάσεων που λαμβάνονται στην αρχή του έτους, η περίοδος προγραμματισμού, για την παροχή στην επιχείρηση πρώτων υλών, αντικατάσταση εξοπλισμού, και το ποσό της χρηματοδότησης κ.λπ. είναι διαχείριση. Φαίνεται ότι για να επιτευχθεί ο μέγιστος όγκος παραγωγής, ο ευκολότερος τρόπος είναι να επενδύσετε το μέγιστο δυνατό ποσό κεφαλαίων και να το χρησιμοποιήσετε για πλήρης δύναμηεξοπλισμός. Αυτό όμως θα οδηγούσε σε ταχεία φθορά του εξοπλισμού και, κατά συνέπεια, σε μείωση της παραγωγής. Επομένως, η παραγωγή πρέπει να προγραμματιστεί με τέτοιο τρόπο ώστε να αποφεύγεται ανεπιθύμητες επιπτώσεις. Είναι απαραίτητο να ληφθούν μέτρα για να διασφαλιστεί ότι ο εξοπλισμός αναπληρώνεται καθώς φθείρεται, δηλαδή σε χρονικές περιόδους. Το τελευταίο, αν και οδηγεί σε μείωση του αρχικού όγκου παραγωγής, παρέχει τη δυνατότητα επέκτασης της παραγωγής στο μέλλον. Έτσι, η οικονομική διαδικασία παραγωγής μπορεί να θεωρηθεί ότι αποτελείται από πολλά στάδια (βήματα), καθένα από τα οποία επηρεάζει την ανάπτυξή της.
Ως έναρξη ενός σταδίου (βήματος) μιας ελεγχόμενης διαδικασίας θεωρείται η στιγμή που λαμβάνεται μια απόφαση (για το ύψος της επένδυσης κεφαλαίου, για την αντικατάσταση εξοπλισμού συγκεκριμένου τύπου κ.λπ.). Ένα στάδιο συνήθως νοείται ως επιχειρηματικό έτος.
Συνήθως στον έλεγχο σε κάθε βήμα u kισχύουν ορισμένοι περιορισμοί. Τα στοιχεία ελέγχου που ικανοποιούν αυτούς τους περιορισμούς καλούνται δεκτός.
Υποθέτοντας ότι ο δείκτης απόδοσης κτο βήμα της διαδικασίας εξαρτάται από την αρχική κατάσταση σε αυτό το βήμα κ-1 και από τον έλεγχο σε αυτό το βήμα u k, λαμβάνουμε την αντικειμενική συνάρτηση ολόκληρης της διαδικασίας πολλαπλών βημάτων με τη μορφή:
.

Ας διατυπώσουμε τώρα το πρόβλημα δυναμικού προγραμματισμού: «Προσδιορίστε το σύνολο των αποδεκτών ελέγχων ( u 1 , …, u n), μεταφέροντας το σύστημα από την αρχική κατάσταση ε 0 στην τελική κατάσταση ε nκαι μεγιστοποίηση ή ελαχιστοποίηση του δείκτη απόδοσης φά».
Έλεγχος που επιτυγχάνει το μέγιστο (ελάχιστο) της συνάρτησης φάπου ονομάζεται βέλτιστο έλεγχο u * = (u 1* ,…, u n *).
Αν μεταβλητές ελέγχου u kπάρτε διακριτές τιμές, τότε καλείται το μοντέλο DP διακεκριμένος. Αν οι μεταβλητές u kαλλάζει συνεχώς, τότε καλείται το μοντέλο DP συνεχής.
Ανάλογα με τον αριθμό των παραμέτρων κατάστασης μικρόκαι τον αριθμό των μεταβλητών ελέγχου rδιαφοροποιούν μονοδιάστατηΚαι πολυδιάστατηκαθήκοντα ΑΣ.
Ο αριθμός των βημάτων σε μια εργασία μπορεί να είναι τελικόςή ατελείωτες.

Εφαρμοσμένα προβλήματα δυναμικού προγραμματισμού

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